四川大学《数据结构2264》19春在线作业2(100分)

奥鹏在线作业

试卷名称:《数据结构2264》18春在线作业2-0001
1.若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。
则该二叉树结点的前序遍历的序列为（    ）。
A.E、G、F、A、C、D、B
/ H  t* z* V* @1 ^+ I5 CB.E、A、G、C、F、B、D
4 f$ J3 C# n+ N$ S2 u5 {$ {/ TC.E、A、C、B、D、G、F
D.E、G、A、C、D、F、B
7 r! J" r) D6 ]! Y4 P' W4 `) y0 U资料:-

2.AOV网是一种（    ）。
9 p) a  x9 W5 k% e8 H$ O8 t. gA.有向图
3 `5 I3 S" b5 A8 H  y8 {, P' ~2 eB.无向图
* i" }7 y7 j3 A( cC.无向无环图
D.有向无环图
资料:-

3.队列的特点是（    ）。
& o% {# Z0 w2 k2 D' s* y' OA.先进后出
B.先进先出
, o3 `2 V2 _( s  J' f3 WC.任意位置进出
D.前面都不正确
( }! W( ^9 j* n7 Q- ^资料:-
/ Y, p. \4 P; e* {5 u) B! E
4.设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（    ）。
: u& f- q1 L/ i8 v, ZA.m-n-1
& q* Z7 W& w/ R8 h0 o3 MB.n+1
, X8 `& H, ^" w4 k! u) G' {C.m-n+1
D.m-n
资料:-

5.从L=（    ）,（    ）)中，取出banana元素的表达式为（    ）。
A.head(tail(L))
* y" T( c& \( W5 ~B.head(head(tail(L)))
: R. L, H5 f+ _, g% s% X* {7 }! jC.tail(head(tail(L)))
D.head(tail(head(tail(L))))
资料:-

. e. u) m1 e* w1 |& z6.带有头结点的单循环链表的头指针为head，则该链表为空的判定条件是（    ）。
A.head= =NUL
$ P% n8 R, |% h: i! dB.head-next= =NULL
, e! i5 [2 f. b9 `. ^$ _5 lC.head!=NULL
- ~6 }0 T8 z6 w4 m1 hD.head-next= =head
" W+ R7 L6 I& h( C资料:-

7.以下数据结构中哪一个是非线性结构？（    ）
A.队列
6 m8 r  ~; k9 W" [; yB.栈
: p! e) k9 s. L( z1 I% SC.线性表
/ j7 m9 I  Q8 ]D.二叉树
资料:-
9 L8 Y) l% i- L1 k& D
- m, h& h! A2 f$ V# }+ e8.在数据结构中，数据元素可由（    ）。
0 ]* P: W! W# r* e6 ~" YA.实体
/ s0 Z# |/ a$ ^6 NB.域
5 Y6 m) r+ n$ x. I8 p& s6 A. p* _C.数据项
D.字段
资料:-
6 ~3 X7 ]8 X+ s& N
4 F. r8 i3 L4 b' l) o: l9.在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中元素的个数为（    ）。
/ m) J, Z3 h7 x6 oA.i
4 R2 l/ o1 ]( e0 b! i9 q7 [* Z( XB.i+1
  r; Z" `$ v* V$ e+ D- F0 oC.n-i
: N8 l' |- u1 J1 c" cD.n-i+1
资料:-

10.已知一个图的顶点集V={1,2,3,4,5,6,7}；边集E={（    ）3, （    ）5, （    ）8, （    ）10, （    ）6, （    ）15, （    ）12, （    ）9, （    ）4, （    ）20, （    ）18, （    ）25}，用克鲁斯卡尔算法得到最小生成树，则在最小生成树中依次得到的各条边为（    ）。
A.(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
8 u  a' A* l4 u. W  k* E资料:-

* c* w0 f5 z: q$ M! o11.在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（    ）
8 z: w9 e3 ^9 o. EA.都不相同
3 O/ ~1 h/ ?; t0 z2 F3 R/ z4 y5 r( UB.完全相同
: X9 g' G8 d+ n* s" h/ WC.先序和中序相同，而与后序不同
& S) _9 q% z+ Q! d% VD.中序和后序相同，而与先序不同
1 h9 \' J6 A9 k! P1 U5 T资料:-
: |6 N1 o$ ~* Z% u
12.k层（    ）二叉树的结点总数最多为（    ）。
. H: }1 G& {  c2 ^+ n2 t8 K1 z, [A.2k-1
B.2K+1
C.2K-1
: \8 h& i. T4 J! d" J$ H! ^D.2k-1
( \: {" r3 u: k' P! R' i% x0 b资料:-

& u+ f, ]! P+ b; N4 H13.设有一个二维数组A[m][n] （    ），假设A[0][0]存放位置在600，A[3][3]存放位置在678，每个元素占一个空间，则A[2][3]的存放位置是（    ）。
/ `1 U" t! e. p9 u3 qA.658
B.648
0 n, J! Q. F8 c. f0 S- BC.633
' G) F0 d+ w2 q- Y! jD.653
资料:-

14.设有6个结点的无向图，该图至少应有（    ）条边才能确保是一个连通图。
' `  ?. c% r& w8 PA.5
* w; }4 V4 x/ S' uB.6
C.7
7 N- \3 K- t0 I% q% o3 ~2 cD.8
- L" w3 m/ G/ v, ?4 ^) R3 ~  W资料:-
. V& {) Z$ k/ G, e
" M+ j9 E5 c) J1 E# J% s6 ?15.采用开放定址法处理散列表的冲突时，其平均查找长度（    ）。
$ p5 F8 [1 B* s; a% XA.低于链接法处理冲突
. F, |7 j& \9 RB.高于链接法处理冲突
C.与链接法处理冲突相同
D.高于二分查找
( r% R+ n1 Z, C& H6 w; r$ E! U资料:-
9 u1 R# }2 W0 ~6 L2 Q
16.假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（    ）次探测。
A.K-1次
: ]1 |, D; h& h$ U% t3 XB.K次
! e! p) A4 @2 ?& d; g! ^9 `0 x8 ]# [, wC.K＋l次
) x' C3 |3 U% F/ F; v" m* D) B; WD.K(K+1)/2次
资料:-

" |& x) D$ L4 l17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（    ）。
A.1，2，3
B.9，5，2，3
C.9，5，3
  I8 X. y+ L/ M: f. iD.9，4，2，3
1 Z2 z& v+ e, ?/ b资料:-
' }, G" o9 C4 g1 U
) y' n' |% W, O2 ~0 d18.对线性表，在下列哪种情况下应当采用链表表示？（    ）
A.经常需要随机地存取元素
B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间
+ h6 D8 Y3 j, aD.表中元素的个数不变
! H9 E, N' v4 _- Y资料:-

: H& \, d' ^7 l8 ^- [19.树最适合用来表示（    ）。
A.有序数据元素
B.无序数据元素
* B: N% E# K( X: aC.元素之间具有分支层次关系的数据
$ J0 u  N* l- [1 A( \D.元素之间无联系的数据
3 f) Z& V4 O) j$ B+ Q# M  T资料:-

20.如表r有100000个元素，前99999个元素递增有序，则采用（    ）方法比较次数较少。
! i7 S2 K7 X. O# ]  P( t! f4 @A.直接插入排序
B.快速排序
* T4 K/ v3 C& P/ VC.归并排序
3 Y# E7 _% N+ ]% |( l! v" nD.选择排序
" J( x4 A9 M# `1 N1 g, I2 L资料:-
6 a6 n8 {: c9 F9 l7 o/ G
21.一散列表长度m为100，采用除留余数法构造散列函数，即H（    ）=K%P （    ）,，为使散列函数具有较好的性能，P的选择应是（    ）。
- F) B- Z) n+ B* v: fA.99
B.100
, C+ r) I3 t6 Z. lC.97
D.93
资料:-

7 n. z! J9 N4 g0 ]* r22.从一个长度为n的顺序表中删除第i个元素（    ）时，需向前移动的元素个数是（    ）。
8 D4 e) j- Y  ~* M' ~A.n-i
( y6 S' a& a1 pB.n-i+1
0 l: `, F/ _# E( y, Q. |2 H9 BC.n-i-1
D.i
资料:-
. A- G' T, u, a: Y
4 v8 n- U) n0 _) `/ L* ]& C0 J23.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（    ）语句序列。
& `0 g! |4 f6 @A.p=q; p-next=q;
: b; d/ i3 c* K: vB.p-next=q; q-next=p;
" ~, m. p  U* M" J3 R# IC.p-next=q-next; p=q;
% G+ f& s, h5 V6 x. YD.q-next=p-next; p-next=q;
8 j4 {* J: l- D% B4 Y& w5 A5 J9 J资料:-
6 b5 S- H7 _9 H! O
1 F3 M* Q; z' ^9 N/ u24.对一棵有100个结点的完全二叉树按层编号，根结点编号为1，则编号为49的结点的父结点的编号为（    ）。
A.24
B.5
/ z. r$ n0 U) P7 K: w4 {- a2 u2 oC.98
+ x* D1 k8 F! _4 \; D% fD.99
9 n' R+ V5 U) N( s* \资料:-
+ P9 N# [9 \) q" P8 X. e
25.从二叉搜索树中查找一个元素时，其时间复杂度大致为（    ）。
$ g) r: [& ^+ nA.O(n)
# X6 u. P0 u/ u. M5 }2 YB.O(1)
C.O(log2n)
! V" _+ e+ s1 L8 a  DD.O(n2)
; x. u3 G, k8 ?0 j! `* L资料:-

5 Y8 D  ?; x! f, T4 X, ?1.以下哪些是队列的基本运算？（    ）
* z% q% S4 p/ g+ U6 U0 yA.在队列第i个元素之后插入一个元素
& R. {2 U/ w7 o9 H) n( TB.从队头删除一个元素
9 M6 ]8 J3 F' N. f% d! S; k/ i0 |+ AC.判断一个队列是否为空
D.读取队头元素的值
E.将队列中的元素排序
1 k. _- D" s6 u# L: S' r  x资料:-

2.以下数据结构中哪一个是线性结构？（    ）
A.有向图
B.队列
C.线索二叉树
D.线性表
E.栈
资料:-

3.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列为（    ）。
A.3，2，6，1，4，5
B.3，4，2，1，6，5
5 K6 d* C1 _6 N) T: X0 W" bC.1，2，5，3，4，6
D.5，6，4，2，3，1
+ L- m1 A$ X8 v; d- }E.6，5，4，3，2，1
资料:-

4.对一个算法的评价，主要包括如下（    ）方面的内容。
A.健壮性和可读性
( C6 f' e0 I" Z+ U9 a! @, n! sB.并行性
C.正确性
6 X* F( x) C2 `/ \8 R& S. qD.时空复杂度
E.界面友好性
5 `! G4 s6 J0 x. ^) i* k7 O! [资料:-

8 i) P5 r; y2 d! `6 F1.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
A.错误
B.正确
3 d! M9 a. o. W; V" Z. b% A资料:-

: @2 {+ h4 b9 u: L) l- U2.为度量一个搜索算法的效率，需要在时间和空间两个方面进行分析。
% i: A5 y% B4 A) QA.错误
B.正确
资料:-

' x) G$ L5 x$ T4 S3.线性表若采用链式存储表示, 在删除时不需要移动元素。
, p$ \% ?/ g9 v: ?) R, y) e: K3 TA.错误
3 A6 v$ N! Z+ r5 TB.正确
# V: y- r; o1 r5 z- ~资料:-
. w0 j) `; X+ J1 L
4.一个广义表的表头总是一个广义表。
A.错误
# A; k$ v) _3 n9 IB.正确
* A& K9 [* F) n0 l$ \1 y. w资料:-
8 x% R9 W3 M1 ~/ j# E
5.在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。
% H, `+ |8 ~* T5 Z0 eA.错误
' n+ L5 o7 M9 f2 y2 P, tB.正确
资料:-

: E4 N7 s+ s) a6 t) v7 X3 ^6.若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。
A.错误
+ y3 r3 {* O8 B! t6 `, `B.正确
. W) @6 H+ d" O# c( t! U% e资料:-

9 @9 j9 F. L( p& M6 ^. x9 s9 S& e% Q7.快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。
A.错误
. b4 s0 Z- E+ H* O' xB.正确
资料:-

5 B/ Z4 [) U' k1 G+ B+ _8.图G的某一最小生成树的代价一定小于其他生成树的代价。
4 V* X4 u5 x7 b. Z1 {1 \A.错误
* A% J5 z4 k3 y: S* ~. J6 ~B.正确
资料:-
, s8 _3 h( O3 Q. [+ c" G& h
- A$ t$ r0 C9 r$ T6 g" L9.进行折半搜索的表必须是顺序存储的有序表。
A.错误
, o9 B: N9 i7 S1 v8 yB.正确
1 P) l0 C8 \, m/ e/ _4 D* h( j资料:-

10.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。
9 z& V: j( c  V1 {( [( ]) @' xA.错误
* D8 D1 Y  X, g: Z7 A$ l  NB.正确
资料:-
( l% v. W: P0 y7 e0 g8 s
11.线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。
A.错误
* _: U% C: t; X) WB.正确
资料:-
  B+ w+ y8 q+ W4 D
6 V. A4 b) @- a6 _5 s12.线性表的长度是线性表所占用的存储空间的大小。
* U* y# Z/ s& f8 @& _0 L) gA.错误
B.正确
资料:-

; I# P7 ~1 e  c13.在采用线性探测法处理冲突的哈希表中，所有同义词在表中相邻。
A.错误
8 z6 s- ?% @! ]" Q) JB.正确
资料:-
1 l; S+ J3 @# f1 ~" M1 u3 n
! L" O* z) j; E% P* U1 h14.顺序表用一维数组作为存储结构，因此顺序表是一维数组。
A.错误
3 _& F5 C( V8 n0 T4 {B.正确
$ e. @8 @( d& X3 q8 A9 g, u2 S; p资料:-

4 @- u+ K# j  {% }5 w15.有回路的有向图不能完成拓扑排序。
A.错误
B.正确
资料:-
& Z1 L% n1 @& b+ ?9 i6 B
) T: Q  J; `7 o3 h4 I