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

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业2
试卷总分:100    得分:100
. i" }* f( W, }; c# ^+ r$ b. }, P" T4 O第1题,判断两个串大小的基本准则是
A、两个串长度的大小
; O- G( E/ [2 E& K: YB、两个串中首字符的大小
C、两个串中大写字母的多少
D、对应的第一个不等字符的大小
7 i' F! E# [1 N  D, x正确资料:
5 C1 m" M' h# C1 B

第2题,已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为
A、ABCDEF
( T& x' X7 ]7 A* k. gB、ABCEFD
C、ABFCDE
D、ABCDFE
7 N) f: f  x5 U! p正确资料:

% G$ g. c% H  ^, v
' R! {! @' B$ M1 Q8 r第3题,采用ISAM或VSAM组织的文件是
A、索引非顺序文件
B、顺序文件
+ Z$ E+ K$ n+ b8 U$ N* ?" ]% ]C、索引顺序文件
D、散列文件
; s; S7 a6 w- {6 G0 g正确资料:
/ V2 I2 X) M2 C! z
4 Z& }5 m4 @. p# }
第4题,如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
A、深度优先搜索算法
B、广度优先搜索算法
( ?) P7 @) Q2 }C、求最小生成树的prim算法
$ e' a- V5 X7 x2 _4 a9 L, ~D、拓扑排序算法
正确资料:
0 N, ]% f1 A2 a

资料来源：谋学网（www.mouxue.com）,链栈与顺序栈相比，比较明显的优点是
A、插入操作更加方便
B、删除操作更加方便
C、不会出现下溢的情况
$ V8 f5 Z. q# s* L4 j2 X) vD、不会出现上溢的情况
正确资料:
( j( Z! T8 t, s' b2 Q# O( a% l, E

第6题,用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
( F& ~4 o% R# K$ Z- ]0 _& ]4 cA、n-1
- o1 F: u1 f  Y( j# O1 r2 FB、n
C、n+l
D、2n
正确资料:
$ ]3 f; e2 i# g0 X+ E/ x: V
5 V" K2 d2 V* |
& `" `! a0 |# Y9 ~6 I. b% H第7题,一棵树高为K的完全二叉树至少的结点是
A、2k -1
8 Y. |& J3 q4 q  o% fB、2k-1 -1
0 b9 Z8 d$ v: s8 I1 p) [C、2k-1
D、2k
正确资料:


第8题,设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
2 l$ p2 D2 @1 n: A# _+ S  Q" a* LA、2
B、3
C、5
$ n. g: g0 S2 h& f* ED、6
正确资料:

5 F6 g1 [( E& ~- x7 h! [
' r" ?5 w2 q% e8 `: F, m第9题,当采用分快查找时，数据的组织方式为
A、数据分成若干块，每块内数据有序
( N8 f* l6 e8 n( {" K1 ~3 _& LB、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
1 S+ k* t: K$ r4 _C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D、数据分成若干块，每块（除最后一块外）中数据个数需相同
正确资料:


资料来源：谋学网（www.mouxue.com）,抽象数据类型的三个组成部分分别为
# n( G+ w' I; kA、数据对象、数据关系和基本操作
) c  U. d0 k6 K) iB、数据元素、逻辑结构和存储结构
" O" T" U- p1 m1 `6 G9 BC、数据项、数据元素和数据类型
D、数据元素、数据结构和数据类型
正确资料:

  r  l3 \8 H5 ?
7 ^9 B* U- j2 H  B" P) I6 ?) I第11题,下面关于线性表的叙述中，错误的是
2 z: J; y: b9 U4 X3 f  KA、线性表采用顺序存储，必须占用一片连续的存储单元。
; l3 a$ ]1 f! b6 `' g6 z, U6 R. aB、线性表采用顺序存储，便于进行插入和删除操作。
C、线性表采用链接存储，不必占用一片连续的存储单元。
4 [. E$ n4 u$ J8 ~, ^D、线性表采用链接存储，便于插入和删除操作。
( Y( D2 i' T3 j, z9 b正确资料:


资料来源：谋学网（www.mouxue.com）,设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
A、8
! {5 C; s% b3 }: W2 l- LB、3
3 n( \% [5 Y- T) h& @; B. BC、5
D、9
2 N; E: R- c( A6 L: x( C正确资料:
* ~7 Q+ ~6 m; I/ P& U7 U1 Q1 T

第13题,在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是
7 \2 z7 |) q# v) T; |A、G中有弧Vi，Vj
B、G中有一条从Vi到Vj的路径
C、G中没有弧Vi,Vj
# U  ^. R: I) o6 LD、G中有一条从Vj到Vi的路径
; E8 T& T5 O5 \4 e/ k正确资料:
6 M. l  p2 K9 F
. q( f3 O: T4 K7 ]
6 E; O: s6 u9 M3 K3 m第14题,在待排关键字序列基本有序的前提下，效率最高的排序方法是
A、直接插入排序
B、快速排序
C、直接选择排序
D、归并排序
: r7 F% y. f- A" o, G$ w# ?正确资料:

9 ?5 o8 ^: M  g6 V* [+ m1 R
- q  [/ `- R1 j* d& y* ?: |9 \5 p资料来源：谋学网（www.mouxue.com）,树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是
0 O$ _& u! D7 _+ h. lA、树的后根遍历与其对应的二叉树的后根遍历相同
5 [+ g3 f, U& J8 s3 d( cB、树的后根遍历与其对应的二叉树的中根遍历相同
C、树的先根遍历与其对应的二叉树的中根遍历相同
2 g# c! K+ {. X3 b5 }1 }D、以上都不对
: X( N9 E/ j$ f( L正确资料:


# e% o/ ?! k2 d- u+ ~  y第16题,若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
A、4
3 _" p# X1 l2 X2 @  y- |2 kB、5
; ^3 \- B: V3 `/ SC、8
D、9
正确资料:
4 }4 p* Y1 u4 W4 S& _
/ _6 f) `% _* v# e& W' P) P" _/ u
  z& N. `5 i- y第17题,下面的叙述不正确的是
* j6 b9 i  i, w" z: @% [A、线性表在链式存储时，查找第i个元素的时间同i的值成正比
B、线性表在链式存储时，查找第i个元素的时间同i的值无关
9 L! E# h8 E1 U5 i* D7 n8 o3 V7 qC、线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
( \# [! l. r( ~5 gD、线性表在顺序存储时，查找第i个元素的时间同i的值无关
正确资料:


第18题,若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为
A、n-1
/ f; z5 G3 E2 w' yB、?n/m?-1
C、é(n-1)/(m-1)ù
D、én/(m-1)ù-1
) b' X7 r$ a; W- v" N正确资料:


9 Y4 m7 x* o) u8 P! l9 i' F第19题,在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是
A、LL型
, W" v0 v. W- @( g6 kB、LR型
C、RL型
D、RR型
正确资料:
! F- t: V* T4 w0 W- D

资料来源：谋学网（www.mouxue.com）,二叉树中第5层上的结点个数最多为
; ^' G1 h# c5 e( ?7 k: T5 d. cA、8
/ F% B1 Y) R/ k4 |* s. c2 \/ t, _5 Y4 }B、15
C、16
D、32
( \( N  r: g% W- B' z& F8 \" N2 Q; C正确资料:

) s/ M' P3 d% S; ^+ a, X; d


+ {8 [7 @8 T. O4 k, m


; B6 H" l. L% P! O
. G4 `4 C) o" n% m

8 O; J( j3 I2 I# S, W
- @4 _9 I* q% D
  a2 p$ n. L. @* m6 G& O3 U

' e* k- Y8 l# A( z