[四川大学]《数据结构2264》18春在线作业1（参考资料）

admin

【奥鹏】[四川大学]《数据结构2264》18春在线作业1
试卷总分:100    得分:100
第1题,树最适合用来表示（    ）。
A、有序数据元素
; E! x9 i- M2 w5 V, C+ A+ `7 bB、无序数据元素
C、元素之间具有分支层次关系的数据
+ ~4 {0 j; c. D* }1 b2 M# iD、元素之间无联系的数据

4 B# g+ x  V/ T9 L
: z4 L! ?" J1 U/ c
第2题,下列关于数据结构的叙述中，正确的是（    ）。
A、数组是不同类型值的集合
/ s; @, Q" P7 b7 K) r% V  _( W) |B、递归算法的程序结构比迭代算法的程序结构更为精炼
4 S5 `3 W- D* {* `7 H, o- z2 a6 ?C、树是一种线性结构
D、用一维数组存储一棵完全二叉树是有效的存储方法
+ ^: K& T5 ~5 `1 U( t) [
& N9 `/ F& k" r; v" m

8 C' x; F( r2 s6 j7 Y6 ]第3题,从一个长度为n的顺序表中删除第i个元素（    ）时，需向前移动的元素个数是（    ）。
( d+ p* d& r8 cA、n-i
) l* r0 o8 ]1 W( ^' nB、n-i+1
, ]4 w2 T# z1 Y9 x' S1 D( NC、n-i-1
# L2 W/ A  q4 R: AD、i
( [, Q6 E/ X" U+ T+ G& _9 q

1 ^8 P8 k; c0 @! F1 F0 Y4 g# Y
  K" W. U1 Y# c9 A第4题,若有序表为（    ），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（    ）。
" P' p- [0 ~/ r. h4 w, k4 HA、f,c,b
B、f,d,b
C、g,c,b
! g' j( r* }6 V0 X' zD、g,d,b

: t0 C6 @* A7 X
4 `% m; h% _" J. K
. u  `( E' v+ Z1 B第5题,以下数据结构中哪一个是非线性结构？（    ）
1 q0 y/ Q+ U0 R* T* u; u" sA、队列
3 F* U* i9 J3 t9 e  bB、栈
# A. v/ @+ A6 `/ K3 b- n  [2 EC、线性表
% w8 h* V# d) V8 o  ^* YD、二叉树
1 C) d& `1 r, o0 G0 u2 N# C; C


第6题,队列的特点是（    ）。
A、先进后出
0 B7 y% E- H" Q  {# R- s# S& H$ LB、先进先出
6 U# L3 ?3 t3 X7 g* d! y5 EC、任意位置进出
D、前面都不正确

; J2 u) b( \1 X" Q  y# M
! X% g* C: Q  m
8 s5 Y- h$ ~' i+ t' h第7题,对n个记录进行堆排序，所需要的辅助存储空间为（    ）。
" E( c. G8 F, \9 G9 y* fA、O（1og2n
B、O（n）
5 n$ h6 N' q$ E4 sC、O（1）
D、O（n2）

5 i* y& V9 M6 \6 ^" G9 ]3 Z
+ s7 l8 n; k. r2 j! ^3 L3 |
: ]1 E0 W6 P7 o( i+ l( W& M$ i& S% i+ [第8题,在数据结构中，数据元素可由（    ）。
$ X0 b+ S2 K1 ]4 }' O% [! Q1 {A、实体
7 h. q. @- h0 V  O* pB、域
C、数据项
D、字段
" J7 b. j& w8 u5 @* j& a
( n5 W6 Z6 i9 ~5 @) o

2 B: A0 |( h8 h; b. B! J第9题,在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（    ）。
& I' [6 Q; z& |6 d& {0 XA、i
B、i+1
C、n-i
D、n-i+1
* |  ?* r5 d  b! W4 c1 W


第10题,一散列表长度m为100，采用除留余数法构造散列函数，即H（    ）=K%P （    ）,，为使散列函数具有较好的性能，P的选择应是（    ）。
# ~3 o6 R- N% {6 s# y7 ~4 HA、99
8 J% m- y7 a9 Z2 SB、100
C、97
D、93


1 f% A- Q0 {. D* ]7 q& K
$ \) ^! Y6 V, L8 }- l! C第11题,设有一个二维数组A[m][n] （    ），假设A[0][0]存放位置在600，A[3][3]存放位置在678，每个元素占一个空间，则A[2][3]的存放位置是（    ）。
6 }0 X+ t" B$ S, JA、658
B、648
C、633
D、653
  a3 f1 p) k* r  j% R0 S


3 \( ]$ q/ i' C" }  x第12题,对一个算法的评价，不包括如下（    ）方面的内容。
A、健壮性和可读性
. i0 u; [( R6 L) m/ b5 QB、并行性
5 G" Z) x, r0 {1 MC、正确性
* A3 v5 t4 c& I6 g5 H, O2 T7 c2 MD、时空复杂度
: E* L2 \3 X; L
+ P; }6 o# `8 q# U6 m" k7 J
1 @6 S2 _7 y9 K3 i' e7 r" q: Q: O. @
% ~1 H; {4 X1 J2 [4 ]1 h第13题,若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（    ）。
5 u! ~0 O+ J+ L1 ZA、图中每个顶点的入度
1 y1 [- [1 `4 h3 j' BB、图中每个顶点的出度
: U" j, P% ^, R1 p+ [. uC、图中每个顶点的度
- Y7 J, p5 J& @5 [0 b* }% UD、图中连通分量的数目
! `) O" V; f' E
2 Q% s: }9 {/ z2 }

0 R- P4 d" s1 N7 ~5 v! f第14题,若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（    ）。
! [! I/ n' P* |6 V! k* UA、1，2，3
3 M0 M" P7 w4 X: c& HB、9，5，2，3
+ s# T4 f+ A1 F: A* M9 sC、9，5，3
D、9，4，2，3
' P9 Q. w" V- V& u1 G. M: d: ~% S

% g1 y' G1 k) N! [5 g3 d  C3 W
0 P) R' T4 K# y  n" W( T  a第15题,对于关键字序列（    ）进行散列存储时，若选用H（    ）=K%7作为散列函数，则散列地址为0的元素有（    ）个。
A、1
B、2
C、3
/ j5 C+ Y( [  C% [, D# v7 Y8 |D、4


* [3 d! {, s) z
第16题,采用开放定址法处理散列表的冲突时，其平均查找长度（    ）。
A、低于链接法处理冲突
B、高于链接法处理冲突
C、与链接法处理冲突相同
D、高于二分查找

$ \. I0 B9 _$ w4 W5 @, n! N9 R

第17题,下面关于图的存储的叙述中正确的是（    ）。
5 ~2 G9 c% Z9 a, P$ ~8 GA、用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
B、用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C、用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
D、用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。

! U  c* J5 M6 B  \7 }; ~

* V, [% z/ T  z% C第18题,从二叉搜索树中查找一个元素时，其时间复杂度大致为（    ）。
A、O(n)
B、O(1)
) Z4 X% |% B5 @4 f5 Q. CC、O(log2n)
6 B, p: g9 }. W. B& VD、O(n2)


+ g% \+ B# i! X6 o* n# O
9 i, \2 j, o& F$ v第19题,假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（    ）次探测。
A、K-1次
& g" F/ |# Y: z( U- cB、K次
! I; I0 @; l6 Y8 @$ a! T6 }C、K＋l次
; t+ T* O: N, }- ]# ?1 I/ t' UD、K(K+1)/2次

) s+ e" l$ h3 [. l; X8 Q

第20题,对于线性表（    ）进行散列存储时，若选用H（    ）=K % 9作为散列函数，则散列地址为1的元素有（    ）个。
+ N3 k, \: B0 W/ mA、1
% @! h9 f+ ]$ |& jB、2
C、3
D、4



第21题,设Huffman树的叶子结点数为m，则结点总数为（    ）。
A、2m
B、2m-1
C、2m+1
8 h# s7 A% {' ^' q7 U5 m, bD、m+1


7 O* \5 r) `: P6 d( I
$ L% V# _  |- \第22题,一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（    ）。
: j5 j* k( B, d5 x# {6 V8 UA、2 3 1
, t2 I  Y  c6 l- l, {B、3 2 1
( r4 _) l0 T: fC、3 1 2
; v$ q: I/ e* F& oD、1 2 3
8 Z( d: J1 u7 [3 a) A( j
$ {) k) E* J  ~6 E

4 ]; S  k; F7 C2 \& n第23题,在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（    ）。
A、HL=p; p-next=HL;
5 B' T, e0 w5 O& \5 J( a  ZB、p-next=HL-next; HL-next=p;
4 Z: ]1 f3 ^! `; ]$ o: `+ GC、p-next=HL; p=HL;
D、p-next=HL; HL=p;
- I0 \# t: K  T& S$ q
6 r" d+ U# L0 w7 N

8 Q2 c; b+ T! j& h$ a. p+ S9 h' ^第24题,设有6个结点的无向图，该图至少应有（    ）条边才能确保是一个连通图。
A、5
9 h( L5 }) q% bB、6
# ]  `# F, A3 z# G; f& I9 ^' S+ bC、7
D、8
3 }+ M- P, y' P  y* E' |: y8 a
: P1 r/ K7 }2 \- H
% N% K  l6 G% }5 N8 j# F5 }
第25题,带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（    ）。
A、head= =NUL
/ X* X! d$ I  J& |4 B( N+ V; rB、head-next= =NULL
" l( _4 U& ~  i2 X; _C、head!=NULL
. _$ m5 |6 k" s3 h- E/ PD、head-next= =head
$ j6 u7 D' P, ]+ G
1 Y# p+ s$ u1 ?$ _5 F& \
( O& Z/ U. d; Q8 W; ?3 D' y" e
+ R2 A. o5 a7 H2 i" P. x第26题,对一个算法的评价，主要包括如下（    ）方面的内容。
A、健壮性和可读性
B、并行性
C、正确性
6 W$ i* l2 ^) HD、时空复杂度
2 O, Q- z: v8 a0 {* T# c" X+ qE、界面友好性
6 d0 v" h/ W1 |2 k2 X,C,D
4 r9 c( A' j. _* C
% `, `' |5 V0 J/ p8 J; F
& @& U  T" ~  s第27题,以下哪些是队列的基本运算？（    ）
3 Y$ z3 g9 j8 [# LA、在队列第i个元素之后插入一个元素
B、从队头删除一个元素
, I4 X! J3 y# e& FC、判断一个队列是否为空
D、读取队头元素的值
( F0 e, S% `" r, J0 kE、将队列中的元素排序
' h. \3 a8 \) m4 X8 }0 s6 a,C,D
. y- T1 R2 B* R& Z6 a( a' l

第28题,以下序列中，是堆（    ）的有（    ）。
2 Q, l0 `7 }: Q* L4 x! ]. _& U5 r4 vA、{15,26,38,49,27,51,39,62}
B、{15,23,71,94,72,68,26,73}
6 J* Z+ j# r+ |* e/ ?C、{15,27,26,49,38,62,39,51}
D、{15,23,26,68,94,72,71,73}
; A# l% H; Q/ E2 K- EE、{94,72,73,26,71,23,68,15}
; l. H- G0 M7 ?8 k: K5 ^,C,D,E
! e; ^5 [0 h; U% o% |
9 l9 ^. o$ w0 l- A
第29题,下述（    ）是顺序存储方式的优点。
A、存储密度大
! c3 y2 W% J4 ~. E& GB、插入和删除运算方便
C、获取符合某种条件的元素方便
D、查找运算速度快
E、可以很方便地存取第i个元素
,E
4 O( w1 g. U: T0 \3 D

$ |/ _" K4 F4 u6 S9 f6 z$ G6 o第30题,一个广义表（    ）,（    ）,c),（    ）))) 的表尾是（    ）,c),（    ）))。
A、错误
B、正确

* m$ }- ^" H1 }( P
7 _, [" \' ]: f% D
  c6 `5 P/ w# p3 ?9 T' v; @第31题,有回路的有向图不能完成拓扑排序。
A、错误
B、正确



第32题,对任何用顶点表示活动的网络（    ）进行拓扑排序的结果都是唯一的。
2 u* U& Z1 ]  [! bA、错误
B、正确
5 _2 d* T9 ^5 Y6 @

" H. A% f  \  z1 D, T. k  F7 l
9 [" d# o& G# `2 ?第33题,为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。
4 E; y1 e3 d3 J! y( `' NA、错误
B、正确
1 J( k6 j2 F* j% f
! G$ g! J2 ?, k

第34题,进行折半搜索的表必须是顺序存储的有序表。
6 C, W- p0 u5 U4 p; `) e0 LA、错误
9 e) h" E2 C1 }+ ~B、正确
& X, F" b+ O8 a$ \9 H

( x# h2 n  Z4 U6 O& B' u$ L
第35题,存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（    ）三角部分。
A、错误
% d. D; C( b( p" e3 ?$ CB、正确


; k- v! F0 P# ~; s$ r, Y
第36题,线性表若采用链式存储表示, 在删除时不需要移动元素。
A、错误
B、正确

/ n  A6 `# {+ T  l4 Q
6 x5 l: P4 L1 |. _+ G+ G
, D) v1 g; \3 M  P1 O( Q第37题,在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。
A、错误
4 j' T- N& t+ m' gB、正确
4 B' P2 Q" n" X  E1 m

1 i, Q! E( C& Q4 W, i9 Z
. }* c1 m" E0 V4 a$ H# q: I第38题,使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
A、错误
# K  _) k* N4 i4 h2 ]& TB、正确
2 q& s" d6 i& f4 ^! |


第39题,线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。
A、错误
B、正确



( |8 `* K9 W) h! ]4 j) h1 H5 _2 G  j第40题,二维数组是数组元素为一维数组的线性表，因此二维数组元素之间是线性结构。
A、错误
/ V& U0 A3 b. V1 l1 e9 p' S( JB、正确



7 i* U2 x3 o  z$ S第41题,链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。
A、错误
8 x5 f5 J$ S4 S; T$ UB、正确
, x* ~$ R0 u/ [0 B


9 s# ]4 p* F+ o! p+ s第42题,数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。
# e. l7 H' b* k& P$ n! W) b5 L' pA、错误
B、正确



. C- A" X- }+ P; [5 P9 \/ w5 V! M第43题,图G的某一最小生成树的代价一定小于其他生成树的代价。
& n) f; |. G! ?5 C2 ]1 n- LA、错误
B、正确

+ W' v- S+ x- \) b4 k0 ]1 u6 [5 ~
9 X, b$ k8 B' u9 ^
4 r7 X' l! e* g9 i; y5 r第44题,在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
! P# P# E& g$ s8 N% \1 JA、错误
& E; ?0 ?  a( Z3 ~6 g  cB、正确
" n: ^# \& U3 H! q, R9 N
/ ?5 @' c8 g$ B+ {, C3 Y
0 |. l1 P1 v. i- ]! K/ m


  f$ Q3 W9 q5 W; c: ~, V; Q) d
6 j* r3 M+ v2 |( L



8 N7 m/ H7 @9 v; \; c2 ]5 w  A# e+ q
1 f6 c" y( S9 R$ M6 Y+ S3 q


% ?/ v' f; ^9 w9 ]( m' z! Q
1 t/ ?8 T# g# c  b- a$ ?

taoxin217

学长介绍来的

wyyy9

顶顶，资料下载试试！