[四川大学]《数据结构2264》20春在线作业2（答案）

skystar

【奥鹏】-[四川大学]《数据结构2264》20春在线作业2
试卷总分:100    得分:100
第1题,若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。2 Q+ D5 i, e$ p6 C* X8 e
则该二叉树结点的前序遍历的序列为（    ）。0 V$ l0 E, H- `6 V+ J3 z' X& q) j
A、E、G、F、A、C、D、B0 K% R0 ?5 F( k, T7 |& |
B、E、A、G、C、F、B、D/ t: D% u- a/ Q3 @6 l( T
C、E、A、C、B、D、G、F& |0 L  V# n" a3 v$ Z9 i
D、E、G、A、C、D、F、B6 ]0 [6 A6 }8 \+ j
正确答案:
2 x+ [, k/ `  H( V. u+ j
# C6 z# a( B2 w
第2题,AOV网是一种（    ）。
A、有向图
B、无向图# }3 r( U5 A( C6 K( _5 a7 C! }
C、无向无环图1 ^; q0 }6 Q( D4 M+ |0 e( y
D、有向无环图
正确答案:0 a6 ^8 M7 Z1 z

: |* L4 e3 T. C. q5 F7 }5 T
第3题,队列的特点是（    ）。  }! D  y6 c3 _/ W  G
A、先进后出
B、先进先出+ @) y2 p2 G' J9 p; \4 S
C、任意位置进出
D、前面都不正确
正确答案:


第4题,设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（    ）。
A、m-n-1
B、n+1
C、m-n+15 N6 q" X6 J, b9 F
D、m-n. Q; t; M# Y* r8 d, r& ]* e
正确答案:  l* K5 a4 b, B$ D
9 `# L% w- z. Y0 V, X

第5题,从L=（    ）,（    ）)中，取出banana元素的表达式为（    ）。/ V/ Q/ V6 y5 v. Q% U0 t
A、head(tail(L)); S) a1 J3 ~: h- Q
B、head(head(tail(L)))  t2 L6 c- v7 R) Y" A
C、tail(head(tail(L)))
D、head(tail(head(tail(L))))
正确答案:
* a) P1 T) Y0 F& q3 i

第6题,带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（    ）。! y; {, W$ k* E8 k; Q. ~/ Z
A、head= =NUL
B、head-next= =NULL
C、head!=NULL% h: y7 Z( h) V$ \' T8 ]
D、head-next= =head
正确答案:0 L6 H6 ^- [4 u2 y1 Z" [5 y9 c

7 s6 i8 P' z) P- Y, J+ z! k+ U
第7题,以下数据结构中哪一个是非线性结构？（    ）
A、队列
B、栈
C、线性表
D、二叉树( y% U' j2 {( Y  S4 M% B& k5 o7 N4 L
正确答案:
7 j5 n  i: S4 Q& u9 R
/ `' C: _, a. `9 i" s/ D
第8题,在数据结构中，数据元素可由（    ）。
A、实体9 X9 w8 o2 Q( N; G
B、域
C、数据项
D、字段
正确答案:
5 n, Y0 l! }3 V' r. d
% Q! Q  p8 F+ h# P3 `5 a( H
第9题,在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（    ）。
A、i( N5 ^5 m6 F9 C# l' q
B、i+1: `. c/ m; w7 ?2 E8 }' ]1 E
C、n-i
D、n-i+1" T6 `; v2 l5 i2 F5 ?! P( ^
正确答案:  l* H  T1 w5 p* N# r: b8 n8 d  ^* \/ D


第10题,已知一个图的顶点集V={1,2,3,4,5,6,7}；边集E={（    ）3, （    ）5, （    ）8, （    ）10, （    ）6, （    ）15, （    ）12, （    ）9, （    ）4, （    ）20, （    ）18, （    ）25}，用克鲁斯卡尔算法得到最小生成树，则在最小生成树中依次得到的各条边为（    ）。) f. s" U4 o0 U; c
A、(1,2)3,  (4,6)4,  (1,3)5,  (1,4)8,  (2,5)10,  (4,7)204 w' Z* l4 U$ u8 g" b) R3 M0 a
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
正确答案:


第11题,在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（    ）- F  Q% @0 t5 H! S; C
A、都不相同
B、完全相同
C、先序和中序相同，而与后序不同
D、中序和后序相同，而与先序不同
正确答案:


第12题,k层（    ）二叉树的结点总数最多为（    ）。
A、2k-1
B、2K+1: C- @7 G& U1 \3 f5 E4 ~
C、2K-1
D、2k-1
正确答案:, N: Z/ k5 |% [5 u3 f
! W- @& ]$ E# e, u) m+ ]

第13题,设有一个二维数组A[m][n] （    ），假设A[0][0]存放位置在600，A[3][3]存放位置在678，每个元素占一个空间，则A[2][3]的存放位置是（    ）。2 d/ L# H2 g# W0 t) D
A、658' h9 l+ s. l  M' o" x- _3 Q
B、648
C、633, F9 R* `# \  p3 g/ o. v
D、653  D# w% b# t; L# l! v  d
正确答案:
, J$ C3 R- E2 @: E3 G; \, U
8 u- H9 m) c  g0 F& I4 @
第14题,设有6个结点的无向图，该图至少应有（    ）条边才能确保是一个连通图。
A、5
B、6% u# K9 b0 A) |! K" k* @# ]8 Z
C、7* H1 ]2 E4 m. h7 {
D、8- V: W7 s* t$ l) y+ X# u
正确答案:7 w3 D5 h; R# X/ Y/ r. h

) w8 v2 G0 q* s, y  a  n1 u
第15题,采用开放定址法处理散列表的冲突时，其平均查找长度（    ）。
A、低于链接法处理冲突
B、高于链接法处理冲突
C、与链接法处理冲突相同9 h) c  m& {1 _3 V. q
D、高于二分查找
正确答案:+ y# f  t" k8 w+ {  m& p

4 N$ l" b# C  a9 E! v0 X
第16题,假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（    ）次探测。
A、K-1次
B、K次8 k8 u1 @4 a3 S9 G! V1 B
C、K＋l次
D、K(K+1)/2次, j: E6 T; R- h1 O4 p
正确答案:  v) Z" G. e" @0 A0 v: j! a" n

- V% ^/ ?# ?# b6 ~
第17题,若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（    ）。  e; P- I* j; M- ~' N: }
A、1，2，3% M! }/ }1 r9 K, s* p! u
B、9，5，2，3
C、9，5，3' W, k( _9 N3 y1 A5 A
D、9，4，2，3
正确答案:4 H! L2 p& L3 f


第18题,对线性表，在下列哪种情况下应当采用链表表示？（    ）
A、经常需要随机地存取元素- Q. V# ]& I: W4 L0 p
B、经常需要进行插入和删除操作9 i3 l5 }5 C4 R, ?5 }! B. B
C、表中元素需要占据一片连续的存储空间
D、表中元素的个数不变
正确答案:0 B) e7 f; k, i- @
/ }* }8 h% P% g! n

第19题,树最适合用来表示（    ）。3 C9 u8 i7 p4 B
A、有序数据元素4 W3 ^7 f9 V% U! H- l9 a9 z
B、无序数据元素
C、元素之间具有分支层次关系的数据
D、元素之间无联系的数据! o  i' |9 H+ x; X1 @+ [7 h
正确答案:
2 }* O- l7 ], b$ Q7 v8 A( `

第20题,如表r有100000个元素，前99999个元素递增有序，则采用（    ）方法比较次数较少。+ \0 q! ~  |* M% s. O6 h; v
A、直接插入排序( n. K8 J% v! i( V! a& I
B、快速排序+ Y- l8 E: ]# L( [2 F
C、归并排序
D、选择排序6 |2 M  W# i' h1 z' W% W
正确答案:4 X/ S. }9 v8 K  }# n

7 E- r1 u& N4 ]  X- S# [: J5 {
第21题,一散列表长度m为100，采用除留余数法构造散列函数，即H（    ）=K%P （    ）,，为使散列函数具有较好的性能，P的选择应是（    ）。6 R4 P& T# {8 S+ U8 o
A、99
B、100
C、97# D/ d# j+ r+ T+ A
D、93
正确答案:% C3 i& ^% U' m, T/ Q: ]
% L3 {( n# z! C* c, ?) X* @
/ R$ b2 s, Z' @/ P
第22题,从一个长度为n的顺序表中删除第i个元素（    ）时，需向前移动的元素个数是（    ）。
A、n-i7 t: B3 V: d# l7 M0 c7 h4 f) I0 E* b
B、n-i+1
C、n-i-1) g) b% J, a5 {( L9 s" l& r. L
D、i6 G0 {8 _: w" T3 T
正确答案:* ?7 s4 O4 f# B0 {+ E
7 p# `( s' z! ~5 i( k

第23题,在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（    ）语句序列。% H& P4 u& G2 x1 O: L  N( C7 \
A、p=q; p-next=q;
B、p-next=q; q-next=p;
C、p-next=q-next; p=q;) L9 |2 g& ~9 `2 n: O
D、q-next=p-next; p-next=q;
正确答案:
- s* l1 [# W9 T# ^
: {$ B) y. X) ^( V( G# p" l4 `
第24题,对一棵有100个结点的完全二叉树按层编号，根结点编号为1，则编号为49的结点的父结点的编号为（    ）。
A、24
B、5
C、986 a" _, e( d  D1 _
D、99
正确答案:0 A) i  ?+ [3 r7 c9 _9 n1 J

! i% O- H0 v$ G  W$ j
第25题,从二叉搜索树中查找一个元素时，其时间复杂度大致为（    ）。
A、O(n)- {7 G4 I4 j' u1 V$ _& B! ]
B、O(1)
C、O(log2n)
D、O(n2)* C1 P' h2 l: q! C" Y2 Y6 ^) I
正确答案:
& R" Q$ U! G4 x% Y
/ j+ T4 J1 I4 T: Z, w2 w# |
第26题,以下哪些是队列的基本运算？（    ）/ r( R* U: G6 h& V" ^4 E, c( v  p4 O
A、在队列第i个元素之后插入一个元素
B、从队头删除一个元素
C、判断一个队列是否为空
D、读取队头元素的值
E、将队列中的元素排序
正确答案:,C,D9 m! b! k' j6 Y' n/ M2 W, f: _
3 k6 \3 y9 K# ?/ P8 R

第27题,以下数据结构中哪一个是线性结构？（    ）2 ?- R$ v8 ]# X
A、有向图
B、队列" X# X9 g3 s& o: {1 z5 R1 W
C、线索二叉树
D、线性表
E、栈
正确答案:,D,E  I# m; I( b4 w/ T+ J" ^
0 k) u$ I0 V- D& V5 g
! ]) s5 Q1 S# u; }( E9 e6 M
第28题,若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列为（    ）。$ m( Y( [5 O5 O+ {: U( f5 B
A、3，2，6，1，4，5
B、3，4，2，1，6，5
C、1，2，5，3，4，6
D、5，6，4，2，3，1( r5 G# b( i3 O' b& E+ {6 D: q( e* ^
E、6，5，4，3，2，10 y0 g" t/ e) g! c; |9 Q) d% X
正确答案:,C,D


第29题,对一个算法的评价，主要包括如下（    ）方面的内容。7 [: B2 v+ v. N; m- c1 F. l) C
A、健壮性和可读性
B、并行性4 Y" B/ H7 M/ B# ~+ B$ P5 c1 m
C、正确性
D、时空复杂度
E、界面友好性7 C2 p/ {; h0 |8 n. e' N$ o
正确答案:,C,D  o5 f( P+ o+ Q2 F  ^* D8 B


第30题,在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
A、错误, b* |* a, v0 P2 R& [- p
B、正确" M5 o+ \! J+ V/ q
正确答案:  O6 Z9 v# S1 @8 J. ~
2 G  }# g% V3 I2 o2 G
- {# q. b7 P# v9 `% ~7 g7 v* L
第31题,为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。9 H1 G1 O# L3 u) b
A、错误
B、正确
正确答案:
4 Q' m; {+ M# H# b
) i$ U0 _) W& \+ _* i/ A7 M
第32题,线性表若采用链式存储表示, 在删除时不需要移动元素。
A、错误3 _  Q8 d* S, s  L4 B7 o* N
B、正确; z# p% D, ?( B, N) {' E# H: Z
正确答案:# w+ [- p" J) {$ S" g# M


第33题,一个广义表的表头总是一个广义表。
A、错误
B、正确% T7 L" N2 m7 l- S0 v& X+ W+ F
正确答案:

- w8 t* t" ~% {. P2 P
第34题,在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。
A、错误
B、正确
正确答案:


第35题,若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。4 j1 w4 G5 V. i$ m* n
A、错误
B、正确
正确答案:4 S* J- v4 {7 [


第36题,快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。# r( y5 Z& W1 O) C! q' h
A、错误: a3 P1 A9 l7 l( ^2 B2 z0 p( E
B、正确
正确答案:

' U$ Q5 K; ~$ S/ Q6 n. D
第37题,图G的某一最小生成树的代价一定小于其他生成树的代价。: H( g, V% M( x- {, K4 h$ ^
A、错误! a# a" \6 Q+ A( Y( l
B、正确
正确答案:: g: a4 D4 L  H7 ^8 E. O8 K

0 J4 }4 |! B7 o1 K5 D4 i0 C
第38题,进行折半搜索的表必须是顺序存储的有序表。
A、错误
B、正确0 C5 N9 z% `: \
正确答案:
! [3 e- g' m& S9 c& |
0 D5 @" U- g/ \: o: H
第39题,数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。. K6 o. X- g% D/ {7 p2 f2 V8 B
A、错误, j( Z: e0 m8 W) [1 f. @  X
B、正确
正确答案:
8 c6 n0 N4 k2 [( ^* X
9 C" L7 p% J, r! z
第40题,线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。
A、错误% I& _  d4 I4 T% A* S: t( [
B、正确1 ~9 a0 g& y$ _- ^. f) ?
正确答案:& J/ z: R. ~9 D7 u: l" ~

2 a" L& D& z! I  \* v. n
第41题,线性表的长度是线性表所占用的存储空间的大小。
A、错误" K# ?6 F+ V* Y0 K! o3 A& `" m9 f
B、正确
正确答案:


第42题,在采用线性探测法处理冲突的哈希表中，所有同义词在表中相邻。
A、错误& h( @. G6 [: g! m5 f
B、正确! _5 g% }0 I$ t3 k6 O9 k
正确答案:


第43题,顺序表用一维数组作为存储结构，因此顺序表是一维数组。
A、错误
B、正确9 ?/ _( A; P: s0 F: }; T7 D
正确答案:
" e" E) T5 |" @5 m- w) d8 R

第44题,有回路的有向图不能完成拓扑排序。9 H" \( K/ m1 p; x' x
A、错误+ Z0 G* M4 E' i7 z" W+ X
B、正确+ w# R/ T2 y2 a. w4 D, D8 U
正确答案: