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

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业2
试卷总分:100    得分:100
第1题,判断两个串大小的基本准则是
- v5 @5 I5 R0 N- \A、两个串长度的大小
3 s8 H1 Z. o$ j2 S, \. g* ?B、两个串中首字符的大小
C、两个串中大写字母的多少
D、对应的第一个不等字符的大小
5 U# c0 O" h2 z& w; ?* @正确资料:


第2题,已知一棵树的前序序列为ABCDEF后序序列为CEDFBA则对该树进行层次遍历得到的序列为
8 z  j$ x( u: f5 q7 U1 V, [A、ABCDEF
B、ABCEFD
C、ABFCDE
% [1 U& @( }0 P# i, U/ q7 E& N/ VD、ABCDFE
正确资料:


第3题,采用ISAM或VSAM组织的文件是
A、索引非顺序文件
. A2 ~1 ]; M6 {9 u, x2 t* u. EB、顺序文件
, U: e" G  X7 n8 d# ?! dC、索引顺序文件
" g2 Z, ]" r; M, B* vD、散列文件
) P: `7 P) M9 }6 t& f正确资料:
- I4 M5 ?) u/ U

) K! Q6 ]5 Y' O: @: }第4题,如果求一个连通图中以某个顶点为根的高度最小的生成树应采用
A、深度优先搜索算法
B、广度优先搜索算法
C、求最小生成树的prim算法
# b. K7 ~$ T1 OD、拓扑排序算法
6 L5 Z0 _5 `, W/ N; f正确资料:
" k( M  C- Z6 }7 T5 T6 {
# K# D0 j2 U5 a0 L5 t
资料来源：谋学网（www.mouxue.com）,链栈与顺序栈相比比较明显的优点是
% m' n% ?% q8 S4 bA、插入操作更加方便
B、删除操作更加方便
" B$ @4 [& v: w& \8 w! yC、不会出现下溢的情况
% h& p6 {/ Y3 j* ]# A7 I% o/ U7 }D、不会出现上溢的情况
正确资料:

1 w6 h2 R6 p" U: M0 A$ |
* u% h5 ~& n+ I) c6 e( L第6题,用二叉链表表示具有n个结点的二叉树时值为空的指针域的个数为
) l8 P& Q; a! r4 _+ T( b$ O- fA、n-1
B、n
. \. q, X' l! N; G' N3 tC、n+l
D、2n
正确资料:

4 r% N: c; j/ g. |0 g4 `; m  ~
8 l0 w, r6 x) P) U第7题,一棵树高为K的完全二叉树至少的结点是
A、2k -1
B、2k-1 -1
C、2k-1
D、2k
  E" G" p7 A2 f, ]正确资料:
+ J7 d$ n/ X* D' G, Z- Z
# |% R! A  g* W+ k
第8题,设有一个顺序栈6个元素1、2、3、4、5、6依次入栈如果6个元素出栈的顺序是2、3、4、6、5、1则栈的容量至少应该是
/ n( w2 Z! E  R  ^  D/ S" VA、2
+ b( N6 G7 Q8 |) K4 k+ u. hB、3
C、5
4 G( V- c/ y( |, r6 a' N4 s2 JD、6
6 V7 y! ^$ a8 n4 M6 j正确资料:
' P: V9 P/ C2 x4 w- g

- j: |3 ?+ \# U# m7 [第9题,当采用分快查找时数据的组织方式为
8 `7 j7 V- @, S# hA、数据分成若干块，每块内数据有序
B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
& d$ E$ f' f9 j3 z, r' wC、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
1 j/ Y) G5 h5 S$ XD、数据分成若干块，每块（除最后一块外）中数据个数需相同
正确资料:


资料来源：谋学网（www.mouxue.com）,抽象数据类型的三个组成部分分别为
A、数据对象、数据关系和基本操作
B、数据元素、逻辑结构和存储结构
C、数据项、数据元素和数据类型
. _, l2 f8 k, R/ X' n8 rD、数据元素、数据结构和数据类型
0 o; V) V; `- _& m& ~  |0 b正确资料:
' E% s! A3 o: k9 c
1 Q$ \& E2 r" v
; \5 v$ _  b$ `8 p第11题,下面关于线性表的叙述中错误的是
A、线性表采用顺序存储，必须占用一片连续的存储单元。
B、线性表采用顺序存储，便于进行插入和删除操作。
; \+ `9 }, g- @5 C% ^C、线性表采用链接存储，不必占用一片连续的存储单元。
D、线性表采用链接存储，便于插入和删除操作。
正确资料:

# M9 U. w* Z% Q. T
资料来源：谋学网（www.mouxue.com）,设哈希表长为14哈希函数Hkey=key％11表中已有数据的关键字为15386184四个现将关键字为49的结点加到表中用二次探测再散列法解决冲突则放入的位置是
A、8
4 d- H, Q2 H1 WB、3
C、5
D、9
1 I. j0 K" e$ n/ P; H# A正确资料:
* k$ v& I0 e6 r6 Y
7 P3 v$ S# F6 H) s8 s
第13题,在有向图G的拓扑序列中若顶点Vi在顶点Vj之前则下列情形不可能出现的是
A、G中有弧Vi，Vj
B、G中有一条从Vi到Vj的路径
" P( }4 V* H: n4 Y6 Y8 _C、G中没有弧Vi,Vj
D、G中有一条从Vj到Vi的路径
9 o5 L$ t4 ]3 F! q/ ?正确资料:


第14题,在待排关键字序列基本有序的前提下效率最高的排序方法是
A、直接插入排序
B、快速排序
C、直接选择排序
' x" A: @& ?: l$ C" A, N+ ~5 @9 h  N. rD、归并排序
) f! y/ U6 b) @; Z! T正确资料:


资料来源：谋学网（www.mouxue.com）,树有先根遍历和后根遍历树可以转化为对应的二叉树下面的说法正确的是
A、树的后根遍历与其对应的二叉树的后根遍历相同
# i2 h& n4 S8 t0 Q( F" m2 gB、树的后根遍历与其对应的二叉树的中根遍历相同
1 [6 W- o* }* Z" ?% p% i% rC、树的先根遍历与其对应的二叉树的中根遍历相同
D、以上都不对
正确资料:
1 \# }$ R! A% F3 q
# Y" a( W3 Z" o
第16题,若在9阶B树中插入关键字引起结点分裂则该结点在插入前含有的关键字个数为
# m* O: K5 z+ A7 X0 C& AA、4
B、5
C、8
D、9
9 f% }$ o- C6 E! N# l$ z+ Z正确资料:
8 B- @! o" G" E$ i

- Q5 z, F) z! d" w* q第17题,下面的叙述不正确的是
A、线性表在链式存储时，查找第i个元素的时间同i的值成正比
+ n! i; r  U5 {; @0 N# V3 qB、线性表在链式存储时，查找第i个元素的时间同i的值无关
C、线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
D、线性表在顺序存储时，查找第i个元素的时间同i的值无关
正确资料:

+ ^. U( ~/ b: M; e6 H. |' q
2 s- j$ S# s5 U/ n6 X3 ?2 |9 C" i第18题,若度为m的哈夫曼树中其叶结点个数为n则非叶结点的个数为
" D$ ]  a2 P! h4 t% zA、n-1
B、?n/m?-1
/ w7 d/ G3 a. I* c* y% d3 cC、é(n-1)/(m-1)ù
  v  g) B! v# G9 [/ zD、én/(m-1)ù-1
& |6 o& T8 o7 M% a+ n2 f正确资料:
! o" \3 ]4 X9 C" |0 d+ y0 d
4 w/ `5 u: m! d$ n  \
第19题,在平衡二叉树中插入一个结点后引起了不平衡设最低最接近于叶子的不平衡点是A并已知A的左、右孩子的平衡因子分别为1和0则应进行的平衡旋转是
A、LL型
B、LR型
; O4 N; ^% `! v% x# ^2 FC、RL型
D、RR型
$ r7 J1 n' c4 R' |: I) H2 i- d0 G正确资料:
& F1 C6 Q0 C3 j7 |, v$ U( l% a6 \

资料来源：谋学网（www.mouxue.com）,二叉树中第5层上的结点个数最多为
! f  [# v# I6 I1 W2 \A、8
B、15
- U# @9 L8 l% t$ a' xC、16
8 r# L/ {4 Z2 A" \. n0 J3 h( E4 q- ZD、32
正确资料:
8 u6 Y; H6 T- s4 f: ]; T





. [* C: W$ j3 B: |
* F' {9 i7 g+ B) M; H
, i& T" ]" U. N3 l5 ^5 K8 R  x
$ k/ z! d' |" @0 I% o2 J9 y
/ S$ P/ x/ d: B* @; i

, g# R% u# h" o& Q2 n
( M4 u  U* x) T
* f6 D& x; b; [' b