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

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业2
试卷总分:100    得分:100
第1题,判断两个串大小的基本准则是
A、两个串长度的大小
- I6 e1 b6 a1 ]; ~! CB、两个串中首字符的大小
C、两个串中大写字母的多少
D、对应的第一个不等字符的大小
) T, a. ]( O2 E3 o$ v9 ]1 A( i% X正确资料:
9 g. U3 H% O# \! a" b7 K

第2题,已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为
8 V5 n" q* p9 ~& OA、ABCDEF
B、ABCEFD
0 o1 ~5 S0 d! k# rC、ABFCDE
D、ABCDFE
正确资料:
' B6 M% {0 H2 `7 d
/ W1 {( E8 _) _
第3题,采用ISAM或VSAM组织的文件是
9 Y/ E! @7 q5 x1 ^: x4 R8 h, JA、索引非顺序文件
# u; I+ W8 E  _: }  p" i5 Y2 pB、顺序文件
C、索引顺序文件
D、散列文件
; I3 h) B+ K( X2 w% t正确资料:
7 I4 {/ g8 V) s

第4题,如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
A、深度优先搜索算法
- U& @, G! r* w, E9 vB、广度优先搜索算法
C、求最小生成树的prim算法
D、拓扑排序算法
) i) ^9 B' s( z正确资料:


资料来源：谋学网（www.mouxue.com）,链栈与顺序栈相比，比较明显的优点是
! D( [! Z5 Y7 sA、插入操作更加方便
6 B+ M. b# h. X) x9 M* dB、删除操作更加方便
2 ?/ ?4 H1 A  _' Y1 [% GC、不会出现下溢的情况
/ ^3 K& }) l" [2 y. [% B. J4 cD、不会出现上溢的情况
' z  x; Z* q6 G7 C' i; U1 A正确资料:


7 \4 r7 O6 t. Y2 |# q第6题,用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
. i+ p, N8 o3 FA、n-1
, ^* P! M! t8 C8 o4 q9 |* b" IB、n
0 ^) z8 k( U. D+ r3 B2 t. QC、n+l
D、2n
正确资料:

2 K! q' @4 F1 _+ n+ N
第7题,一棵树高为K的完全二叉树至少的结点是
A、2k -1
B、2k-1 -1
5 [5 B5 V' Y2 _' X1 f1 VC、2k-1
D、2k
正确资料:

, a% R0 ^+ v" y! t2 A4 y
第8题,设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A、2
7 ]& S  [2 U+ Z. D; g/ WB、3
C、5
D、6
正确资料:

) o, x2 W& n: m9 I8 D% e( \; T3 Y  N" |
第9题,当采用分快查找时，数据的组织方式为
8 M- X( Q3 z4 G2 PA、数据分成若干块，每块内数据有序
0 h; d- A( R+ T, ^! w- rB、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
1 }: V5 a% N2 R; @6 E$ gD、数据分成若干块，每块（除最后一块外）中数据个数需相同
: p3 j( j. h2 y6 _正确资料:

0 i% a( A+ B/ @& O
资料来源：谋学网（www.mouxue.com）,抽象数据类型的三个组成部分分别为
A、数据对象、数据关系和基本操作
B、数据元素、逻辑结构和存储结构
5 D" P; f) w0 V' D& o* BC、数据项、数据元素和数据类型
D、数据元素、数据结构和数据类型
* c2 `8 H+ u& [正确资料:


" W8 j% K& t9 C- j2 Y- x; y. Z第11题,下面关于线性表的叙述中，错误的是
0 o; `' v+ t* J, iA、线性表采用顺序存储，必须占用一片连续的存储单元。
4 O, ^6 ^; Q: S4 h3 \) q# P" P5 g, AB、线性表采用顺序存储，便于进行插入和删除操作。
C、线性表采用链接存储，不必占用一片连续的存储单元。
! V" A  l0 J! e3 W+ fD、线性表采用链接存储，便于插入和删除操作。
正确资料:

- K* ~7 b; t8 i5 Q) U' Y) [( g
% M9 Y$ v% E2 c& ?1 p# Q资料来源：谋学网（www.mouxue.com）,设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
A、8
7 _; F0 V/ T4 {$ kB、3
5 N4 f! _" g/ S. _5 AC、5
D、9
正确资料:
3 {( i0 c9 z8 |5 {; ~. h4 A
5 @, Q8 c, B# {2 Z' g& q
第13题,在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是
2 S) i" O2 a* E% @- sA、G中有弧Vi，Vj
B、G中有一条从Vi到Vj的路径
C、G中没有弧Vi,Vj
- E# B$ D4 a1 h0 r! d4 I, \D、G中有一条从Vj到Vi的路径
正确资料:


第14题,在待排关键字序列基本有序的前提下，效率最高的排序方法是
A、直接插入排序
" G" ^7 w0 `  A# M1 w8 L% x$ uB、快速排序
C、直接选择排序
: p) O5 O7 s+ b1 HD、归并排序
正确资料:
  b  R- ]: Q2 K2 @; C" z! w4 b( |  k

资料来源：谋学网（www.mouxue.com）,树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是
A、树的后根遍历与其对应的二叉树的后根遍历相同
B、树的后根遍历与其对应的二叉树的中根遍历相同
C、树的先根遍历与其对应的二叉树的中根遍历相同
, V- g2 n+ X* A, x$ dD、以上都不对
% M4 D  Q1 D8 S正确资料:
- F7 e$ |- B7 ^8 t
! y+ l& o5 H# D; x% u
' e* g! A8 ?) i* }- f3 d9 b第16题,若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
A、4
B、5
' K1 k( \' O$ d! B) SC、8
D、9
正确资料:
7 s& J( l& G& N7 [, ^
5 q. {5 a$ X4 z$ t9 D
1 O& e; R9 H# d6 f+ q+ y第17题,下面的叙述不正确的是
A、线性表在链式存储时，查找第i个元素的时间同i的值成正比
/ `$ @& }7 b) l4 h1 j6 xB、线性表在链式存储时，查找第i个元素的时间同i的值无关
C、线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
7 q6 g5 I- t  ?/ j5 c: a" W# E5 jD、线性表在顺序存储时，查找第i个元素的时间同i的值无关
正确资料:
2 z: U% k& p  T) o5 b3 f
4 e) \; P0 m% N4 E% {
) U8 Q3 q" A7 V. I1 l7 b# H5 G第18题,若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为
" N% Z+ O. O2 k; ^8 m' GA、n-1
B、?n/m?-1
C、é(n-1)/(m-1)ù
D、én/(m-1)ù-1
# D+ J4 I$ g5 ]/ r9 i5 _+ p正确资料:


第19题,在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是
3 B7 V$ r4 I1 ]% \6 k/ RA、LL型
B、LR型
C、RL型
6 u7 C* A5 ^' N' h8 C$ {D、RR型
正确资料:

! m+ y0 P$ t7 g
资料来源：谋学网（www.mouxue.com）,二叉树中第5层上的结点个数最多为
, n2 B# K: W: a: g$ ZA、8
B、15
% U" [$ j* ]( {7 Y4 `* r# |8 MC、16
3 o3 W$ z4 o. _6 s2 dD、32
正确资料:
2 Y; g- e. C+ I3 q1 Q8 B

0 Y9 |9 X. `/ W1 A
8 l2 a3 F  P7 a" b5 \, Y

, J/ F4 w- y# V4 S6 Q& E

& B7 t, a' A8 [7 x& ]( M2 u+ X

$ S, v, D; V; S0 l
8 H6 g, F5 v, l6 ^! n, [

* ]& f$ c3 D; M" D6 E# b( V, ?
, l( K( x) p1 }* J/ L7 w2 l# e