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

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业2
, N/ C# k: O5 J) K& `& B2 F6 ]试卷总分:100    得分:100
第1题,判断两个串大小的基本准则是
A、两个串长度的大小
B、两个串中首字符的大小
C、两个串中大写字母的多少
D、对应的第一个不等字符的大小
# X+ J  P1 p3 O2 B正确资料:

9 i% `; |" ^# |& P1 D
* D& [- t4 R7 i9 K1 U/ U' _第2题,已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为
% X1 b/ t6 `$ i4 \$ KA、ABCDEF
B、ABCEFD
C、ABFCDE
# x) `* B, T* F# _& h+ N/ J8 \D、ABCDFE
. Y' q& d" b: |. B( Z$ D, h8 K0 b- I正确资料:

. r: z/ x3 G  D8 |7 H% g
4 w% M; {9 Z8 h# Y第3题,采用ISAM或VSAM组织的文件是
A、索引非顺序文件
2 }; x6 L/ w9 G% y$ jB、顺序文件
; b7 s7 z$ O0 a* ?0 l; wC、索引顺序文件
D、散列文件
正确资料:
1 e! A3 b9 Y. `- P- h) A
  \$ e+ O) f! F  C: o8 T
) \8 p/ ~6 F  u  Q( L% ^第4题,如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
A、深度优先搜索算法
: S7 [8 Q  r3 v- _B、广度优先搜索算法
  Y2 b, u3 Q% c' D; ]C、求最小生成树的prim算法
D、拓扑排序算法
正确资料:

. z1 t' ~# g' P# `9 k% V
资料来源：谋学网（www.mouxue.com）,链栈与顺序栈相比，比较明显的优点是
A、插入操作更加方便
B、删除操作更加方便
C、不会出现下溢的情况
9 j. v6 x% U0 C- i$ g& O% LD、不会出现上溢的情况
$ n, X) q, a( S+ _, ^正确资料:
8 s: P! L5 H& z- q* A

第6题,用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
6 x9 p7 v& ]( R+ x, s% x9 kA、n-1
B、n
C、n+l
D、2n
1 N4 r8 [; K2 E8 i4 e: {& x正确资料:
6 p1 o( c* ]* E- N/ S4 e. h

/ M# W, P+ V/ g$ u9 \- H第7题,一棵树高为K的完全二叉树至少的结点是
A、2k -1
- H$ r) z- e+ f# ~& vB、2k-1 -1
& q$ E1 B6 g: \2 D. FC、2k-1
D、2k
, v. v/ z; k" s0 `& T正确资料:

+ h9 E$ x4 K& B& q7 z8 z
7 u) T& t6 Y+ m& y, h* d0 c第8题,设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A、2
9 l9 s9 `# `" ?1 w, U" NB、3
7 h+ |) S4 A, H" N/ _3 BC、5
( ~2 f( U! a+ h( v) D& o) T0 l  pD、6
. f  q- L0 c2 F正确资料:


第9题,当采用分快查找时，数据的组织方式为
A、数据分成若干块，每块内数据有序
B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
. a6 O6 _, d& b5 C  pC、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D、数据分成若干块，每块（除最后一块外）中数据个数需相同
正确资料:
% H  g* [; T' H' D* k3 D- B
5 B) f" _* T9 T
5 H7 \) B% u+ {: p资料来源：谋学网（www.mouxue.com）,抽象数据类型的三个组成部分分别为
A、数据对象、数据关系和基本操作
4 z& M) k( t, p1 X4 i0 qB、数据元素、逻辑结构和存储结构
& S! Z. I0 g& |: c& f2 wC、数据项、数据元素和数据类型
9 j) I+ H2 e1 R3 L; d: }6 WD、数据元素、数据结构和数据类型
正确资料:

, I  S5 M* A$ M3 f7 C0 j8 D  `
第11题,下面关于线性表的叙述中，错误的是
, x$ U1 J! x1 S" G# ?1 O! ?$ ]A、线性表采用顺序存储，必须占用一片连续的存储单元。
B、线性表采用顺序存储，便于进行插入和删除操作。
C、线性表采用链接存储，不必占用一片连续的存储单元。
D、线性表采用链接存储，便于插入和删除操作。
: i1 m$ b. `0 X正确资料:
9 i, E# }! l6 X* D% ]3 e
, G* v, @( l5 Y  O7 o
/ P% T4 n8 e8 {. q3 Z) z) r资料来源：谋学网（www.mouxue.com）,设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
. w2 q7 @+ t. k% w3 i% }A、8
B、3
C、5
9 o% i" r. ?/ L& R5 Q3 ED、9
( C5 J+ M. J; Q) m) j+ n+ \" K( x正确资料:
4 L  Q9 f4 H5 z" l7 j4 g
! K0 _4 m+ M$ v" J. t% W: R
第13题,在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是
A、G中有弧Vi，Vj
B、G中有一条从Vi到Vj的路径
C、G中没有弧Vi,Vj
D、G中有一条从Vj到Vi的路径
" m1 M6 O8 H* a正确资料:
, B# t0 i1 q7 X  y% H; X; V
# E- U- Y: i; L, A
& Y" O. L: _% `0 j第14题,在待排关键字序列基本有序的前提下，效率最高的排序方法是
A、直接插入排序
B、快速排序
C、直接选择排序
' m$ ~4 ^/ [& d7 n( `3 AD、归并排序
正确资料:
- F! D2 n0 G) G. i/ g
* Q7 s4 [0 D; h' T1 r
* \* t& o* c& ]+ ^; Y# Z) K8 P5 D资料来源：谋学网（www.mouxue.com）,树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是
A、树的后根遍历与其对应的二叉树的后根遍历相同
B、树的后根遍历与其对应的二叉树的中根遍历相同
9 \. k2 I$ i5 X  T6 KC、树的先根遍历与其对应的二叉树的中根遍历相同
D、以上都不对
正确资料:
* }5 Z" m8 }( K' J  f* H" E
, V4 ?; X: ~2 A6 v
第16题,若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
: N! c. a, a" lA、4
B、5
C、8
D、9
正确资料:
4 P0 W1 Y8 z# Z! g
) c5 ?" m$ c# b/ l3 M
/ T; Z! Z$ j: v) u3 k" h第17题,下面的叙述不正确的是
A、线性表在链式存储时，查找第i个元素的时间同i的值成正比
+ Y% i& X7 p/ NB、线性表在链式存储时，查找第i个元素的时间同i的值无关
* X5 x: f  b) S0 b; r. b1 O  l0 mC、线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
- R# A3 \% r. Y- mD、线性表在顺序存储时，查找第i个元素的时间同i的值无关
正确资料:
& }" [! e3 ?$ V+ ~

第18题,若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为
# {5 p# A! q: E. W* SA、n-1
B、?n/m?-1
C、é(n-1)/(m-1)ù
% j+ C  {- x% x# iD、én/(m-1)ù-1
正确资料:

3 x% N$ S# z0 N' s8 i, F
第19题,在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是
A、LL型
; h6 x% M+ p/ ~B、LR型
: n( Y2 I% H& ]& x% rC、RL型
" o8 i  u6 p4 u$ x- j  V4 e: z3 fD、RR型
& I( h* S5 |- I9 g, Y正确资料:


* [* L* T# g1 J0 {2 Z9 r3 N/ `资料来源：谋学网（www.mouxue.com）,二叉树中第5层上的结点个数最多为
% m* i( p4 L: ]1 ~0 vA、8
B、15
C、16
0 d8 ]" o/ f3 tD、32
) G" ~; _- K5 p6 a+ e& b  {正确资料:
; O2 }: Q  }5 `' O6 f5 _

) w" i1 S( r  X3 r
/ Z, i8 p; Q: C5 B- _* ~& `' l

( f! @8 X. J+ c8 S% W+ b
8 [+ X3 t# y% ?
/ [! s1 c! q% X! O' ~( B& w

& v8 v, H1 d4 s; X; L! o( N
: U# F9 R$ I3 ~! |6 {' g4 s, B& J3 w
: }- |8 Q4 U* G; W1 A% V& i

& ^; [# G1 m( |1 ]5 T2 e0 s( t/ H
/ ~2 @" |# K$ J) s7 v6 q' F+ G( J$ q