22年春东北大学《数据结构Ⅱ》在线平时作业2

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业2
& y) i8 b+ c9 R4 d试卷总分:100    得分:100
第1题,判断两个串大小的基本准则是
A、两个串长度的大小
+ Y$ [) n1 F$ ?5 G, Q% i& MB、两个串中首字符的大小
* u, _- j# i  ~: K# Z7 CC、两个串中大写字母的多少
D、对应的第一个不等字符的大小
: z/ z- T; ?' _0 F) g( l, K' S. R正确资料:

0 r: O9 v1 H2 `; F
" d2 s2 H) j% L  w5 b第2题,已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为
A、ABCDEF
( g+ y$ U  J5 y& W5 L% @B、ABCEFD
$ g* c4 p0 v( w; EC、ABFCDE
) ^  d. }& j5 T$ aD、ABCDFE
$ ?2 G1 I- c  H. c正确资料:


第3题,采用ISAM或VSAM组织的文件是
9 q7 Z. n& C$ _& V/ M# R. nA、索引非顺序文件
9 m" {1 B0 q& k9 AB、顺序文件
C、索引顺序文件
5 T4 Q- H1 V; {7 A/ f8 \6 pD、散列文件
3 O$ j! e' u& X8 j! g正确资料:


第4题,如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
4 @; s) I: ~" G7 K5 C" ^- eA、深度优先搜索算法
B、广度优先搜索算法
- [) [- i- j6 Z- A+ O% jC、求最小生成树的prim算法
" l  t4 B$ g( E6 b. y! e6 qD、拓扑排序算法
+ L) V4 W7 P& A5 @/ n9 n" R6 t正确资料:

3 T* z+ k! Q; z9 V/ r
资料来源：谋学网（www.mouxue.com）,链栈与顺序栈相比，比较明显的优点是
A、插入操作更加方便
; w2 U( Y) ]; C+ {$ R% a* cB、删除操作更加方便
C、不会出现下溢的情况
1 \0 _6 O, ?" z3 v2 Y0 r( PD、不会出现上溢的情况
4 d0 N0 P9 E9 P; I2 G$ d) j! k0 T正确资料:
6 d+ e. |$ S3 W/ A* U  i+ M; Z
7 A4 Q: S0 v0 g# G9 ?
第6题,用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
A、n-1
4 R' G$ W( N  uB、n
C、n+l
+ }) o/ c/ Z$ tD、2n
0 t- S8 R  ]* p9 r正确资料:
8 t" \# v. f* \0 C
% U$ V+ K# [  O: D
第7题,一棵树高为K的完全二叉树至少的结点是
A、2k -1
B、2k-1 -1
9 |8 L8 X( L; O1 m; y  x6 wC、2k-1
, J- [7 e" S  R# }0 G; LD、2k
正确资料:


第8题,设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
& u& h% E- ~9 Z" ~0 O, `A、2
B、3
6 H# c, d9 {  m2 ^9 eC、5
D、6
: u8 l, \* w/ r" B+ h8 A' [正确资料:


第9题,当采用分快查找时，数据的组织方式为
A、数据分成若干块，每块内数据有序
% y( i( t6 A* `8 sB、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D、数据分成若干块，每块（除最后一块外）中数据个数需相同
5 e  O( t  H7 g) J8 Q正确资料:

: _( q3 P8 b7 c! E# o1 X
+ u- p# }8 g: V2 k0 J/ J2 S资料来源：谋学网（www.mouxue.com）,抽象数据类型的三个组成部分分别为
A、数据对象、数据关系和基本操作
) H2 e! W  u4 ^2 ~7 SB、数据元素、逻辑结构和存储结构
C、数据项、数据元素和数据类型
D、数据元素、数据结构和数据类型
正确资料:
  {: i; ]7 o; V4 }( e/ S3 r
. K- v" I& a* R8 i
第11题,下面关于线性表的叙述中，错误的是
A、线性表采用顺序存储，必须占用一片连续的存储单元。
B、线性表采用顺序存储，便于进行插入和删除操作。
# g; |7 _' W6 FC、线性表采用链接存储，不必占用一片连续的存储单元。
) c1 L6 Q3 W0 L- k) S0 KD、线性表采用链接存储，便于插入和删除操作。
! a& F; [9 P4 E/ G正确资料:
/ P6 A8 f2 e5 D/ T6 b

* ?5 e* ^) V3 b0 Z0 T9 e资料来源：谋学网（www.mouxue.com）,设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
* w) k$ k7 b( |) pA、8
B、3
" y' K6 |7 ^- x1 ~C、5
D、9
正确资料:

5 ^  {, H) P5 n5 b3 a. |) l6 R
第13题,在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是
A、G中有弧Vi，Vj
% j& `) |- k; T, l" h2 LB、G中有一条从Vi到Vj的路径
C、G中没有弧Vi,Vj
D、G中有一条从Vj到Vi的路径
正确资料:
( w( F) F9 R& V( l

第14题,在待排关键字序列基本有序的前提下，效率最高的排序方法是
7 ?% N+ B) u. d8 B3 E2 h6 Q$ [A、直接插入排序
B、快速排序
$ }# ?  q1 Y, ^1 _  _8 yC、直接选择排序
+ q$ ?" j" X- h8 V; d8 FD、归并排序
正确资料:


" y: ~  M9 y- D资料来源：谋学网（www.mouxue.com）,树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是
A、树的后根遍历与其对应的二叉树的后根遍历相同
3 H- b# R7 x' ^9 ]B、树的后根遍历与其对应的二叉树的中根遍历相同
C、树的先根遍历与其对应的二叉树的中根遍历相同
D、以上都不对
9 y+ j( G7 w4 t  F9 C* c正确资料:

% f* p( k- }8 l8 o/ V7 v9 [
  k) y! x  y5 X8 r, Y6 \3 j& Y第16题,若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
5 Q+ t0 f0 A6 g# {/ pA、4
" \7 F* b% x' ^; cB、5
C、8
D、9
$ C$ I, X3 ^" d8 b2 O1 b- |& h正确资料:


第17题,下面的叙述不正确的是
A、线性表在链式存储时，查找第i个元素的时间同i的值成正比
B、线性表在链式存储时，查找第i个元素的时间同i的值无关
C、线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
8 K/ l. X% F  H/ ?5 tD、线性表在顺序存储时，查找第i个元素的时间同i的值无关
正确资料:
6 Y( x/ X! S2 S5 W

第18题,若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为
A、n-1
B、?n/m?-1
2 E1 g5 x: ]. @1 T1 ?C、é(n-1)/(m-1)ù
/ k1 I2 c5 ?# vD、én/(m-1)ù-1
" I8 E' p# m- }正确资料:
7 N2 ?# [* H2 Q) k- b
+ j. t0 _9 j  ]% b8 M
/ h3 E4 C! ?7 @( }, X第19题,在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是
2 R0 @# b$ L8 V$ A( L4 M6 mA、LL型
B、LR型
: Z+ m6 b( |0 X& {C、RL型
+ [& Z" g# G, _0 DD、RR型
$ A" |0 I2 R  K: s2 O( _2 W+ w* \正确资料:


" \4 M- |1 m4 p/ Z资料来源：谋学网（www.mouxue.com）,二叉树中第5层上的结点个数最多为
A、8
* X! `& T" ]: |5 ~8 SB、15
9 D: E/ u5 I2 S" CC、16
D、32
正确资料:
* W5 r" S9 Y$ D1 H, h



2 q5 Y4 l9 @" c# ^  [, v# H




4 O* w. N' k4 \; H9 Z" o5 j; ?
, s, C. B& w: ^. G

8 q- V$ C+ d3 r/ j: r( S
# d. v- W4 M! l; C
5 }2 i" \; c5 t& O% ^' B