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

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业2
试卷总分:100    得分:100
/ K6 ~2 S  F4 i* u, \6 b, o2 @5 U第1题,判断两个串大小的基本准则是
) W  B0 T' ?( ~" b) N  [A、两个串长度的大小
B、两个串中首字符的大小
/ t, k9 w1 v, l0 x" SC、两个串中大写字母的多少
D、对应的第一个不等字符的大小
正确资料:

- ~1 \) V0 L. Z3 T% ?
第2题,已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为
8 z# C/ r; q7 X4 w* f; Y0 jA、ABCDEF
$ I$ g5 \, J* M. |+ ]B、ABCEFD
C、ABFCDE
D、ABCDFE
正确资料:


$ {+ r" c, K7 u" v' _9 m# }第3题,采用ISAM或VSAM组织的文件是
7 r  P. i% D2 b1 t- DA、索引非顺序文件
4 F* \, W1 L; LB、顺序文件
% [% i7 h$ F: Q2 P! T# jC、索引顺序文件
D、散列文件
0 G9 I7 e3 s1 m4 Z; N4 C正确资料:
; j" J* U" u) r! }6 D
! T/ ~4 f: n4 b, n8 n( a" O
* V4 X! p# D  s- O- x5 _第4题,如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
A、深度优先搜索算法
B、广度优先搜索算法
C、求最小生成树的prim算法
D、拓扑排序算法
# m( g2 o' w$ G2 \: b正确资料:
& S" ^  {7 q4 F) q4 e& q/ S1 |$ E
! F( ~0 P+ _! w, S; t
6 w; K9 }0 z3 `资料来源：谋学网（www.mouxue.com）,链栈与顺序栈相比，比较明显的优点是
A、插入操作更加方便
B、删除操作更加方便
C、不会出现下溢的情况
; h7 B5 J, d& O1 k7 U2 G, X$ C; ~D、不会出现上溢的情况
5 P/ ?7 Z8 @0 P0 }0 f: t正确资料:


第6题,用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
, |' V8 g" L  e( \/ v0 NA、n-1
B、n
9 U! \( ~" l! Q  x3 `9 pC、n+l
D、2n
正确资料:
5 {" `8 R" p5 o7 C; }$ t1 q

2 q: |. O" M/ e2 I8 c* n1 N5 [% x/ u第7题,一棵树高为K的完全二叉树至少的结点是
3 w( [) w' N" ?  K( r' U) WA、2k -1
9 A' Z/ V9 H" r2 A/ }( uB、2k-1 -1
8 F5 p) D3 A# V4 V$ T" OC、2k-1
D、2k
正确资料:


第8题,设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A、2
0 s- t% U# I* Q. \B、3
C、5
D、6
正确资料:


1 E) d  l- Y3 M6 j5 t/ K第9题,当采用分快查找时，数据的组织方式为
A、数据分成若干块，每块内数据有序
B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
6 P2 j( g* k: q; b2 OC、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D、数据分成若干块，每块（除最后一块外）中数据个数需相同
正确资料:


资料来源：谋学网（www.mouxue.com）,抽象数据类型的三个组成部分分别为
A、数据对象、数据关系和基本操作
4 W' C4 t; g  e: \B、数据元素、逻辑结构和存储结构
C、数据项、数据元素和数据类型
8 U& w' \# f: J0 ~2 eD、数据元素、数据结构和数据类型
  ^/ \' g2 X6 _: P9 h正确资料:
# c( o; ]) G5 @, q

2 K6 c' m$ O6 X" F第11题,下面关于线性表的叙述中，错误的是
A、线性表采用顺序存储，必须占用一片连续的存储单元。
2 O, q+ p* p' A9 y6 }. r! aB、线性表采用顺序存储，便于进行插入和删除操作。
C、线性表采用链接存储，不必占用一片连续的存储单元。
D、线性表采用链接存储，便于插入和删除操作。
$ |  e0 v% n7 D; `  L  ~3 Y  d正确资料:
# o, Q* f3 q% R

资料来源：谋学网（www.mouxue.com）,设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
A、8
B、3
% t  C% c2 X  W+ K( J+ y/ K) O' g) jC、5
/ q$ g* J' P3 |D、9
# J- W1 [6 l8 Z0 Y* ]1 [正确资料:

# v3 p3 C7 ^) [7 T( G
第13题,在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是
9 ^8 E8 S* j) `+ KA、G中有弧Vi，Vj
B、G中有一条从Vi到Vj的路径
2 C. q2 L- r2 O- g* OC、G中没有弧Vi,Vj
D、G中有一条从Vj到Vi的路径
$ @+ }' j- _1 ]; O2 \$ a5 k正确资料:
  j. q- h$ V- {7 [% b/ o
8 ]5 d! x, `  E. ?
3 W, A4 Q8 K* g8 ^+ q第14题,在待排关键字序列基本有序的前提下，效率最高的排序方法是
" G+ e" O3 U7 {7 QA、直接插入排序
$ H# ^/ D* T# @: I9 b; RB、快速排序
C、直接选择排序
" T* f9 H5 }' T4 \D、归并排序
- f) O  M" c. W" l! [. g% |0 z正确资料:

7 t, T/ }7 e1 G' ?: D7 w. e+ D
- A1 f8 [& u* I0 V# m/ G1 m% ?资料来源：谋学网（www.mouxue.com）,树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是
A、树的后根遍历与其对应的二叉树的后根遍历相同
8 l  ]  y4 G7 @2 e; U; ~7 VB、树的后根遍历与其对应的二叉树的中根遍历相同
C、树的先根遍历与其对应的二叉树的中根遍历相同
/ C3 j+ i; Q  {: A- N$ ?2 V6 wD、以上都不对
正确资料:
# S% X) S4 j  r& f) R
' T5 R$ ]0 I2 A2 T( j: w
7 p  I2 V% s' x6 n: t/ Y& P第16题,若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
3 ~6 n* q; \+ EA、4
6 D9 E+ `$ t& v( DB、5
- q8 ?3 [8 m( ~! k; z' _C、8
D、9
正确资料:

$ S# A1 X0 X3 e2 M
第17题,下面的叙述不正确的是
  z3 r& w2 v' F5 W0 J/ j" ZA、线性表在链式存储时，查找第i个元素的时间同i的值成正比
B、线性表在链式存储时，查找第i个元素的时间同i的值无关
C、线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
7 T5 |" Q6 P% ]+ @' oD、线性表在顺序存储时，查找第i个元素的时间同i的值无关
正确资料:
9 ]. u6 F! d8 Q! U) `! r+ i

第18题,若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为
A、n-1
B、?n/m?-1
" j+ k9 ~& o, f/ oC、é(n-1)/(m-1)ù
D、én/(m-1)ù-1
正确资料:


/ i# l& S# P% h! `, Z3 l第19题,在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是
A、LL型
! Q6 O8 d- |% O6 w/ JB、LR型
C、RL型
D、RR型
正确资料:

0 S4 j( f5 R+ [0 e7 H
资料来源：谋学网（www.mouxue.com）,二叉树中第5层上的结点个数最多为
A、8
B、15
C、16
- B7 T2 ^. X5 q) uD、32
正确资料:


6 M. ~2 |$ z1 b- V9 E/ m1 S6 ]
- a* I- S- w6 l+ ^8 K* {/ ]
9 Q4 F6 ]- B0 A6 }& e" k" o


; I) B! P) t. p1 P: G1 `, x& o
8 E+ ^( K# Z. g
( d: G% U3 r; Z- K7 b

& i; ~8 g% D4 Q- U. g! r2 [' g+ z

) A( D% m9 P! ~3 B: ]: |: r