21秋东北大学《数据结构Ⅱ》在线平时作业2

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业2
1 y5 v6 G# R) }" g: }" S试卷总分:100    得分:100
4 v+ o! j0 s- }! ]第1题,判断两个串大小的基本准则是
A、两个串长度的大小
B、两个串中首字符的大小
$ S! z4 J0 i) m# L8 HC、两个串中大写字母的多少
2 r+ n/ B- s% [1 Q6 [, ZD、对应的第一个不等字符的大小
' B+ {' L% g/ D; `, G正确资料:

7 r+ }; X7 c4 u2 j: C& i2 T
4 k2 ^& L3 L: |1 ^第2题,已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为
A、ABCDEF
1 l9 y+ H' v) OB、ABCEFD
# ^, w3 B8 u' B& ]% T' _/ aC、ABFCDE
D、ABCDFE
正确资料:
$ H: V" u1 _9 c- p2 L
) |. q* G) Q: `6 O' P( e$ b" l. F
第3题,采用ISAM或VSAM组织的文件是
1 u" m2 k+ ]$ r& k; t/ q$ ~0 cA、索引非顺序文件
B、顺序文件
0 M5 O, ]4 B$ D# T! p: m/ fC、索引顺序文件
# Q' K* d! V+ o0 R% w6 SD、散列文件
正确资料:


第4题,如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
A、深度优先搜索算法
5 b4 G* R7 l8 H- w+ T6 e" jB、广度优先搜索算法
C、求最小生成树的prim算法
+ S; n' N& }8 j' X* a3 ]) R5 |# `D、拓扑排序算法
正确资料:


资料来源：谋学网（www.mouxue.com）,链栈与顺序栈相比，比较明显的优点是
6 \6 d( q, A+ ^' l8 b( O' oA、插入操作更加方便
B、删除操作更加方便
C、不会出现下溢的情况
D、不会出现上溢的情况
9 T' I( x* }. L4 C" w6 b正确资料:
% j2 _8 k3 c( q) @2 e

第6题,用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
A、n-1
% |" E- B0 O. T. F: {B、n
C、n+l
D、2n
1 F/ u* P$ Z9 f; ^; b0 N* A正确资料:
! v# U5 ^, |; ~- G

9 z: j2 M) h  X第7题,一棵树高为K的完全二叉树至少的结点是
/ b8 n- }% e1 k3 F+ G2 X+ d& wA、2k -1
B、2k-1 -1
9 G' T  p3 W) H( s6 w+ h! J+ GC、2k-1
+ y. e% r  P7 W; ED、2k
9 x, ?: _: p+ Y; ]  d正确资料:

: w, z, u1 k& \* M% [
第8题,设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
: }0 _- @" T1 lA、2
" |& ?" M) }+ ^& t6 U/ `0 k  m/ eB、3
C、5
2 N$ e+ m: ?1 V( u# e/ g5 AD、6
# i0 J% \% x8 ]正确资料:
6 e9 b$ H7 ]; Z/ B
6 I/ W+ Y) |! v8 J
第9题,当采用分快查找时，数据的组织方式为
A、数据分成若干块，每块内数据有序
B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
" x6 c: {7 u3 }+ B6 l) N+ HD、数据分成若干块，每块（除最后一块外）中数据个数需相同
0 i0 H5 Q( ~8 y( r0 L- w正确资料:

9 j& w* m* t4 h/ p* Z5 N4 g$ ~1 q; [
资料来源：谋学网（www.mouxue.com）,抽象数据类型的三个组成部分分别为
1 N% C% ]5 s2 U7 C) L) tA、数据对象、数据关系和基本操作
) J; C1 a2 v- I/ M/ F0 `B、数据元素、逻辑结构和存储结构
C、数据项、数据元素和数据类型
D、数据元素、数据结构和数据类型
( u( T$ q# g9 ^: J正确资料:


第11题,下面关于线性表的叙述中，错误的是
A、线性表采用顺序存储，必须占用一片连续的存储单元。
B、线性表采用顺序存储，便于进行插入和删除操作。
* _5 T6 T, [) d7 pC、线性表采用链接存储，不必占用一片连续的存储单元。
D、线性表采用链接存储，便于插入和删除操作。
/ |4 I9 ]) g* u9 Y( r# S/ I% U正确资料:
( w5 b$ z+ W6 I3 d: [9 C0 {( w

- Y' x7 T- W  S( C! b资料来源：谋学网（www.mouxue.com）,设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
1 s1 G6 u5 U# g/ K/ [A、8
7 f# s6 z9 B) b) r+ H# ]& A0 Y* _6 EB、3
C、5
D、9
4 J: W! G. d" n正确资料:

, }, U% i; n* U. L5 [3 j: K
# T$ t2 c& S: H' F第13题,在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是
A、G中有弧Vi，Vj
B、G中有一条从Vi到Vj的路径
C、G中没有弧Vi,Vj
D、G中有一条从Vj到Vi的路径
正确资料:


$ [/ n2 m' M# v* w: q  P( e" q第14题,在待排关键字序列基本有序的前提下，效率最高的排序方法是
A、直接插入排序
% w. n, y/ S) l. [6 `& z& }B、快速排序
! R6 V! @( ^/ r. Z8 y% @! S: OC、直接选择排序
D、归并排序
  ?. S8 q. r* \6 c7 F9 o, a3 p8 F$ j正确资料:
% f& `2 c/ s, Z# y. n" b8 i

资料来源：谋学网（www.mouxue.com）,树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是
, {& x) `5 A; H: b" ?A、树的后根遍历与其对应的二叉树的后根遍历相同
B、树的后根遍历与其对应的二叉树的中根遍历相同
) R6 t6 m. D5 B; e% y# VC、树的先根遍历与其对应的二叉树的中根遍历相同
D、以上都不对
8 s/ z, ?% C' O: _) z  J* f  l- R, [- G: e正确资料:
; h/ o! G0 J& G+ D9 ~# ^

第16题,若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
A、4
B、5
C、8
D、9
6 G* P* h1 ~! c. S, d正确资料:

6 W1 Z; u* J$ X5 }' o+ J
第17题,下面的叙述不正确的是
9 `6 n$ L, Q( c* I1 ?. zA、线性表在链式存储时，查找第i个元素的时间同i的值成正比
! M7 T+ H9 j+ l; o' wB、线性表在链式存储时，查找第i个元素的时间同i的值无关
C、线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
D、线性表在顺序存储时，查找第i个元素的时间同i的值无关
: b8 ~* w0 t/ L$ Z/ L% \; F( [  J正确资料:
8 i" c, U8 }1 x1 ~5 f, E. Y% F
3 z, \3 o3 L) Y  L0 ]
$ N, d5 b- M, K6 @* I4 F' N第18题,若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为
3 k% [* e) `% t/ B1 l& fA、n-1
) V$ _0 G( z: k5 a# D7 ?6 TB、?n/m?-1
  i( ^5 E, L3 J. IC、é(n-1)/(m-1)ù
D、én/(m-1)ù-1
正确资料:
# R- K+ o  e/ b) d- ]
$ c2 P) s3 }* P
9 l, B+ O- r5 u! ]7 F第19题,在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是
A、LL型
4 c. l% s1 m) F9 N# k- jB、LR型
5 M9 r7 u7 n& ~" p( `& K" RC、RL型
; k0 x+ z; d; FD、RR型
正确资料:

# ~/ d6 C% [8 K1 l9 d2 r0 ^
  l/ o" a! B* q. @资料来源：谋学网（www.mouxue.com）,二叉树中第5层上的结点个数最多为
( ?, R0 C. q8 YA、8
B、15
C、16
D、32
正确资料:
% _, J# }" y2 X5 Q
3 J) z" Z+ r' N; y3 r8 K: ~



8 J6 k# [. E& X0 M8 f, a4 D
8 x1 |- a  G" `, `. ~
+ W; Q, K$ u. t$ E

( X, z. _; E" w( U/ [
9 z( ^- P+ j# ~6 q& J9 ?. o
; e7 m  h8 J( G8 l2 n" b/ L8 m$ i
! E$ o7 h2 j/ b
  K) `" K" E. E6 l, Y
( C# ~; u& `0 F4 E1 a, F% r6 ?# W