21年7月川大《数据结构2264》21春在线作业1

admin

资料来源：谋学网（www.mouxue.com）数据结构2264-[四川大学]《数据结构2264》21春在线作业1
( b6 s  a% u9 ^  ~6 _. R! e试卷总分:100    得分:100
第1题,采用开放定址法处理散列表的冲突时，其平均查找长度（    ）。
A、低于链接法处理冲突
B、高于链接法处理冲突
C、与链接法处理冲突相同
D、高于二分查找
正确资料:
* K( }3 U0 b( n7 N

* T  O! _; @* Q, m第2题,含有10个结点的二叉树中，度为0的结点数为4，则度为2的点数为（    ）。
* b, u( Y* p* `; t" I3 ]; ]/ l5 w! AA、3
B、4
C、5
D、6
正确资料:
9 l& b7 |  b5 A5 O3 A' K( W
6 G8 w( `6 W# f/ L. L8 M+ ?
; b, H7 g8 R- k& i4 T! R第3题,若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（    ）。
A、图中每个顶点的入度
# T, p( Q# S$ D3 pB、图中每个顶点的出度
7 x, a+ Y1 b' w! E$ o8 |C、图中每个顶点的度
D、图中连通分量的数目
) B) N# \$ V% F; B# a正确资料:


8 {7 ^% X% e+ `7 V) Y* V第4题,设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（    ）。
4 J8 b5 r( J9 \) _- m6 ?A、m-n-1
B、n+1
  V/ Y0 [. O4 f5 HC、m-n+1
. Y6 {4 X' m) t0 k0 S+ k5 I8 x9 vD、m-n
1 ^/ p3 I) C  p( s正确资料:


+ U" x' v; B' g资料来源：谋学网（www.mouxue.com）,中缀表达式2+X*（    ）的后缀形式是（    ）。
8 F8 L& ?0 D6 h4 F, P# o9 R0 z2 pA、3  Y  X  2  +  *  +
B、Y  3  +  X  *  2  +
: K: v/ B  S# ?( V$ ?! b8 B; s3 U, hC、2  X  Y  3  *  +  +
$ g; |1 d$ |4 S0 i' `! O3 A5 a" gD、2  X  Y  3  +  *  +
正确资料:
, `& _6 q' t! \6 n% X4 L

- E7 A1 q: K& P3 T第6题,假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（    ）次探测。
; F% I6 I6 M; r8 Z2 A0 Y3 Y7 R$ GA、K-1次
B、K次
C、K＋l次
D、K(K+1)/2次
7 ]8 o5 \. R& V4 D* H正确资料:


1 I% {& H7 m) W' a第7题,在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（    ）。
( }8 Z1 S# ?, E" n3 U2 mA、HL=p; p-next=HL;
2 M0 e. ]9 D3 x) KB、p-next=HL-next; HL-next=p;
C、p-next=HL; p=HL;
: d% ^: g" `: O3 KD、p-next=HL; HL=p;
正确资料:


9 C9 F0 m* @+ S6 m7 h第8题,已知一个图的顶点集V={1,2,3,4,5,6,7}；边集E={（    ）3, （    ）5, （    ）8, （    ）10, （    ）6, （    ）15, （    ）12, （    ）9, （    ）4, （    ）20, （    ）18, （    ）25}，用克鲁斯卡尔算法得到最小生成树，则在最小生成树中依次得到的各条边为（    ）。
! R& M( H7 C! @9 A1 `) y) L5 W3 k1 `5 zA、(1,2)3,  (4,6)4,  (1,3)5,  (1,4)8,  (2,5)10,  (4,7)20
B、(1,2)3,  (4,6)4,  (1,3)5,  (2,3)6,  (1,4)8,  (3,6)9
C、(1,2)3,  (1,3)5,  (1,4)8,  (4,6)4,  (2,5)10,  (4,7)20
D、(1,2)3,  (1,3)5,  (1,4)8,  (2,5)10,  (4,6)4,  (4,7)20
正确资料:
) s2 v; ^' f& g9 {" A! A- [
5 H3 N) [4 `! S# v" l( {6 W
第9题,对线性表，在下列哪种情况下应当采用链表表示？（    ）
A、经常需要随机地存取元素
1 F; V% X% V3 pB、经常需要进行插入和删除操作
: c" T0 W7 t5 d3 Z4 BC、表中元素需要占据一片连续的存储空间
D、表中元素的个数不变
正确资料:
, a5 {: h/ G; n

2 }7 f5 _1 X* s9 {3 i资料来源：谋学网（www.mouxue.com）,如表r有100000个元素，前99999个元素递增有序，则采用（    ）方法比较次数较少。
+ K2 ?6 t7 [$ D8 s( n) C. _A、直接插入排序
% r% z( _% p& sB、快速排序
1 y& x# w2 |  ~C、归并排序
- r6 |* g6 b9 Q7 V7 O5 H0 ~# {D、选择排序
正确资料:
. T+ {5 E2 |. Y, k: Z/ q; H' W
+ ^$ B& T: o. w9 W' x" i8 c
+ p" f: ?' K: _" g( q第11题,对于关键字序列（    ）进行散列存储时，若选用H（    ）=K%7作为散列函数，则散列地址为0的元素有（    ）个。
# W- Z* {, j; A. RA、1
1 b+ B7 m# F5 D; g* e: {5 ^B、2
- j7 E$ u* L8 D3 b1 jC、3
# ]) i" O8 o* h/ F; {; R2 AD、4
$ X: j; X8 s+ q, c" c# I正确资料:
+ }1 u2 K. P' ?+ L+ V- X
, L4 w8 N6 z; u" H: w6 W( V6 s
7 p7 N) o8 v( o3 D: L/ Z资料来源：谋学网（www.mouxue.com）,一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（    ）。
) B' ]0 z9 S6 C1 e9 ^- X& ?$ W' ZA、2 3 1
B、3 2 1
3 M% k! c: n. Q8 [C、3 1 2
: w& N6 o0 v- j& c5 ?' M+ W) VD、1 2 3
正确资料:
- E+ _4 G2 X8 Q, l: L' P

第13题,下面关于图的存储的叙述中正确的是（    ）。
A、用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
) Z( k! h# Q6 q. YB、用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
( c4 N" k# d5 l0 _: q6 _2 r8 ZC、用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关。
" Z; K7 m3 j2 E/ |  m7 KD、用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关。
. f. Y* c, Z+ _$ l正确资料:
$ {: ]2 B, X$ |/ E
8 A8 H! I, E0 v
- ~7 W4 {$ e# v7 d: X1 }0 o7 K2 c, k1 C第14题,若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（    ）。
A、1，2，3
B、9，5，2，3
, |7 Z" l+ Q0 t; w* g& {C、9，5，3
5 Q1 g( t2 A4 {" m0 w" D7 DD、9，4，2，3
正确资料:
) {! w( M7 i0 c+ G2 v2 `: P+ Z

  ?+ l% m; R0 B& r! B" R资料来源：谋学网（www.mouxue.com）,设Huffman树的叶子结点数为m，则结点总数为（    ）。
A、2m
& U1 z! w1 Y2 b& o! s% dB、2m-1
7 ?" q) C+ H) j  f# U8 e/ oC、2m+1
& Y6 z! \; U) X# [4 ?D、m+1
$ L1 F( h( Y- w5 m- x/ J4 `0 [正确资料:
) D9 R/ [+ p3 L# U( x! l- a( ?
- L0 X4 r, w# j' o+ p# h) K! s$ ~. j
: ^9 ]# W' q8 S, l9 E- c9 i  Q第16题,带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（    ）。
A、head= =NUL
3 A9 p' L& o2 U& T2 I+ E/ mB、head-next= =NULL
0 D( Z( [) I" C0 n, aC、head!=NULL
4 V- U' p: b; h7 F7 R) {% l) iD、head-next= =head
正确资料:
- i9 M6 N5 \/ v" p
7 a5 v3 ]! e) Z* @1 E0 Q6 o# U
第17题,树最适合用来表示（    ）。
A、有序数据元素
! M5 i! D2 m  B' s: r! U$ DB、无序数据元素
. ?+ ]& H; h/ f3 u; }+ ]5 R+ O9 OC、元素之间具有分支层次关系的数据
D、元素之间无联系的数据
+ t: f, s9 ]' H, E5 z6 q0 |1 q# `正确资料:
: t  \4 T8 s0 z5 h  }  N/ {& [
2 M5 z( ^5 |# h
! c! `! B* ~6 Q( R2 o第18题,AOV网是一种（    ）。
; I7 r+ J% z, }. qA、有向图
B、无向图
C、无向无环图
D、有向无环图
正确资料:


) u3 ?2 K+ }3 \" D, _3 R0 a第19题,对n个记录进行堆排序，所需要的辅助存储空间为（    ）。
A、O（1og2n
5 d( `: m! r$ f$ x8 l& KB、O（n）
C、O（1）
D、O（n2）
正确资料:

& [2 p! Q) ^! j) z
6 G- f6 n) e% ~# ]资料来源：谋学网（www.mouxue.com）,在线性表的下列运算中，不改变数据元素之间的结构关系的运算是（    ）。
A、插入
# p7 u. N0 D' W+ tB、删除
C、排序
D、查找
4 U; j' J2 ^- e$ R- r正确资料:

5 B3 U9 J6 E. u2 ?, J5 c' B1 P
第21题,若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。
/ `" a$ ]+ m5 }' u8 I则该二叉树结点的前序遍历的序列为（    ）。
1 ^9 {4 x! L( j* k1 HA、E、G、F、A、C、D、B
' c- ^6 ?8 e* u2 z0 QB、E、A、G、C、F、B、D
) R8 d  h: a+ w/ e% ~C、E、A、C、B、D、G、F
D、E、G、A、C、D、F、B
正确资料:


4 }; l9 q2 v7 [( `第22题,一散列表长度m为100，采用除留余数法构造散列函数，即H（    ）=K%P （    ）,，为使散列函数具有较好的性能，P的选择应是（    ）。
A、99
B、100
C、97
/ e  {& z6 [: mD、93
4 ^" a2 B6 D/ r( g5 g* f8 `3 O. o正确资料:


6 s/ D* E; g# y  z第23题,在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（    ）
4 K; t! a6 D' |6 ^% FA、都不相同
B、完全相同
5 e4 k! s+ `, V, d0 `C、先序和中序相同，而与后序不同
4 G1 H) E4 d; g+ m& OD、中序和后序相同，而与先序不同
正确资料:
" W" ^6 r1 w# T4 f

7 Z3 P* h# W7 `第24题,对广义表L=（    ）,（    ）,（    ）执行操作tail（    ）的结果是（    ）。
A、(e,f)
B、((e,f))
1 ~  h0 c& z% d/ b5 g5 {  `1 B( GC、(f)
: O5 V8 \8 x! c* H5 LD、( )
正确资料:

. P' n0 h; u, u0 \& a+ {! z
资料来源：谋学网（www.mouxue.com）,在数据结构中，数据元素可由（    ）。
+ t' D% G7 J2 ^0 Q% Z& R/ gA、实体
' N' I' N  E" JB、域
C、数据项
6 f6 U1 m; z/ U8 o% ]( \9 _D、字段
正确资料:

) `) ]6 H' N0 P
第26题,以下序列中，是堆（    ）的有（    ）。
. `/ U/ S' o9 {# i( T5 EA、{15,26,38,49,27,51,39,62}
4 b8 p- @+ A  h" `$ oB、{15,23,71,94,72,68,26,73}
C、{15,27,26,49,38,62,39,51}
( @( l/ ]9 o8 c1 A2 n* `% bD、{15,23,26,68,94,72,71,73}
E、{94,72,73,26,71,23,68,15}
正确资料:,C,D,E
4 M: P" l3 E5 Z5 u& O6 K
4 M: C7 [/ }8 S
+ f* t. k5 @; I/ A% S第27题,栈和队列的共同特点是（    ）。
$ J; ?4 {" F: ]7 b( A1 z. T* v* c& bA、只允许在端点处插入和删除元素
B、都是先进后出
C、都是先进先出
: H- K% A% C+ v6 C/ a1 zD、没有共同点
$ b% f- ^! ]& B1 [9 Z* VE、都可以采用顺序存储方式和链式存储方式
正确资料:,E


第28题,以下数据结构中哪一个是线性结构？（    ）
3 X/ o/ K4 Q: U( o" X- U5 G2 m" _0 p  yA、有向图
$ R1 r" b* c* Y9 KB、队列
C、线索二叉树
! O3 l7 x- r$ e( Q# g7 m+ XD、线性表
8 ^- s; d/ C- W: ]# ]E、栈
- q" d) p9 o' ]正确资料:,D,E
& d' ~2 d/ o3 H, I8 m
4 S, \8 Q# m+ D  M1 q2 I7 u1 K
第29题,以下哪些是队列的基本运算？（    ）
: i* D8 V0 h4 y; c5 `: A. zA、在队列第i个元素之后插入一个元素
- K9 j& _! `0 ]. c, x8 \B、从队头删除一个元素
9 A, b6 @9 i1 N" U# l" ]2 sC、判断一个队列是否为空
D、读取队头元素的值
E、将队列中的元素排序
正确资料:,C,D
& {: r' l' \% o1 i; R' j, I) E) B
% N/ g5 k: g* u  X; r* k" m& ]
资料来源：谋学网（www.mouxue.com）,线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。
- Z+ m/ n& u, n7 Y' ^: `, ~* m2 |A、错误
$ o7 o3 @0 y1 ~1 z# y2 a  AB、正确
- ]5 @+ J7 C: `' I正确资料:

' x4 _0 x7 n+ u
第31题,一个广义表（    ）,（    ）,c),（    ）))) 的表尾是（    ）,c),（    ）))。
' D# S- ^. z4 FA、错误
B、正确
正确资料:
: \; G, ]! j) c9 U. h) w8 |
# D  \5 `! d9 N" q$ H8 e
% h, @0 l' o% s9 J9 j* S第32题,若仅知道某二叉树的中序遍历序列和后序遍历序列，则不能够确定此二叉树的层次遍历的序列。
1 I/ g, A/ q4 v4 i% G4 k5 V  n$ nA、错误
B、正确
正确资料:


! ]' N6 A# a  o8 U0 ]& O. J2 @% M第33题,线性表的长度是线性表所占用的存储空间的大小。
A、错误
$ Q% e+ s* d9 i9 m2 e7 oB、正确
正确资料:

& K6 z7 C; ^2 P8 j+ a8 T  K
6 A$ v% n* R3 U" o第34题,图G的某一最小生成树的代价一定小于其他生成树的代价。
A、错误
B、正确
/ |+ f: q3 ^* N( _7 w* ^正确资料:


第35题,进行折半搜索的表必须是顺序存储的有序表。
5 ]8 [& K; B8 ~0 r+ X# n$ t, _A、错误
B、正确
正确资料:

0 T/ j) I3 X" S- P  J, g
第36题,数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。
% \; u5 y7 H% e4 O' h; y6 a( BA、错误
B、正确
正确资料:
. T, W$ h2 ?8 L$ V
3 d4 W3 [+ g3 e& ^" G
第37题,已知指针P指向链表L中的某结点，执行语句P：=P?NEXT不会删除该链表中的结点。
A、错误
. R4 J) P" m- T: }( h# E" h0 T, yB、正确
正确资料:
1 Q( [6 @- ?7 v& B* l
( q, Z, q4 g; ~3 M! W& P( I' \
# o8 }( p: y/ Z5 Y: U- B0 w第38题,存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（    ）三角部分。
4 }) [9 A# s) G3 zA、错误
B、正确
正确资料:
$ V. [% R3 D, c% k, D) o

第39题,快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。
A、错误
: G: {5 O, o) g8 u- VB、正确
/ m3 x, h) {: b: r  T正确资料:
. V$ {1 d- I  G/ {" E! v- x4 Q
# v, Y( e3 h! r! [5 R5 J
4 g# e8 @# g3 @0 x9 p! |第40题,邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。
A、错误
B、正确
正确资料:
% M0 o+ X2 u$ s9 p, o* ], z

第41题,栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。
A、错误
7 s- V) P: v6 c  g; M# ?* W' |; DB、正确
( w. g4 V6 M9 o6 Y正确资料:

4 `8 c- ^* A* o# ]5 c& g: a
第42题,使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
A、错误
3 k2 B; g3 _+ B) z) f0 s; [B、正确
) @& r# K* k% [8 [正确资料:

& d, c) @' I8 ^# v" R% E
第43题,在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
, Y" c+ D( J. V* J6 `7 O  {- {A、错误
& \+ O" ~, s2 P) ]* AB、正确
正确资料:


第44题,在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。
- J& r& o$ H$ \/ qA、错误
5 Q: x$ f7 S* Z- wB、正确
2 O% T$ Q: Y) L5 {  R正确资料:


0 F8 y( }& \# Y& `* c( z" P


: M+ l( }- U5 f" a  S
- J* t- P: H" V. q8 R3 s+ Z' H. V



; ?- `  x5 F9 w$ _! k" y6 g