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

admin

资料来源：谋学网（www.mouxue.com）数据结构Ⅱ-[东北大学]《数据结构Ⅱ》在线平时作业2
试卷总分:100    得分:100
! r5 O6 A, P4 s! h3 E( T第1题,判断两个串大小的基本准则是
A、两个串长度的大小
B、两个串中首字符的大小
+ e- g1 H  D( u9 |C、两个串中大写字母的多少
" b5 |  k- @- }7 z1 ~+ ~2 v4 _/ DD、对应的第一个不等字符的大小
) i1 u) r4 G- h9 D$ i8 f正确资料:


, F! W( _5 D0 m& g+ a3 W, e8 t第2题,已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为
A、ABCDEF
& v7 E: V' j" o( t, }( `; R' ]B、ABCEFD
" p! f4 D& |; [3 LC、ABFCDE
: j6 d) N; Y& K* T: Q4 \D、ABCDFE
4 S* ?4 ^0 f' s/ s' _正确资料:
+ V0 w' M: P! ~$ O/ I

, ~5 w7 N  W8 h8 m( r2 A1 e* W9 y第3题,采用ISAM或VSAM组织的文件是
: k# g! I/ u" x  c2 bA、索引非顺序文件
B、顺序文件
C、索引顺序文件
6 ^: z* N  L0 U: \& d2 i$ w" v* tD、散列文件
+ d" E9 d& F( b9 F" n正确资料:

. E. Z( ?. D. t7 p: K0 v
7 U- T2 f, w' j2 P" S8 M) g* k第4题,如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
: P0 @9 ], J6 w7 MA、深度优先搜索算法
( n! v# J: p1 ^1 n/ RB、广度优先搜索算法
C、求最小生成树的prim算法
D、拓扑排序算法
正确资料:


$ P8 A% m$ k0 @$ L资料来源：谋学网（www.mouxue.com）,链栈与顺序栈相比，比较明显的优点是
2 W9 K- `9 K# z' \1 J  J" w( LA、插入操作更加方便
B、删除操作更加方便
0 F. N* x. M: ~  J$ W) U3 p4 ]C、不会出现下溢的情况
* z- Q7 g) \3 G" P' P" iD、不会出现上溢的情况
正确资料:

2 J( [, o* b+ m. j
. d" V: x$ Y3 Y. ]1 S8 V  k第6题,用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
3 I! y/ y- V' y* M1 U! A6 ZA、n-1
B、n
4 s$ `3 ?8 w) b' `C、n+l
6 D! ^/ I7 ]( gD、2n
正确资料:


5 F- R4 A9 F; H- f) Q第7题,一棵树高为K的完全二叉树至少的结点是
/ k1 H) Z' I2 iA、2k -1
9 L) K9 i* K+ l. k5 {: gB、2k-1 -1
C、2k-1
) T$ ^' A/ v7 E+ BD、2k
0 A4 u! X# k- p! D. Q5 u  o' x正确资料:
4 v" a' ?6 Y; C8 L( D  j, O, t/ v+ `

6 U$ L( o' A$ x- z第8题,设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A、2
B、3
( u- V) l4 j, W8 _$ i6 LC、5
D、6
正确资料:


) G+ j9 b$ g- _- c第9题,当采用分快查找时，数据的组织方式为
A、数据分成若干块，每块内数据有序
B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
- ^- S* v; [& i- A8 SC、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
' L) _# R, ^. P' l3 q! v7 I# YD、数据分成若干块，每块（除最后一块外）中数据个数需相同
& p: A- z/ K/ E# w$ R. ^正确资料:


' m# r/ L5 z! a8 p4 T  K% i' \资料来源：谋学网（www.mouxue.com）,抽象数据类型的三个组成部分分别为
. Q+ \5 ?$ g8 NA、数据对象、数据关系和基本操作
& H9 `2 F9 u4 L' i' s* }B、数据元素、逻辑结构和存储结构
4 m  }: I; b+ _) ~0 H1 j1 |C、数据项、数据元素和数据类型
9 g: E. [6 r( h$ DD、数据元素、数据结构和数据类型
正确资料:
3 o% ?- M! B1 w. ]4 {! p; o
5 n% u% f- m: H& j( D/ X8 |! b$ E
第11题,下面关于线性表的叙述中，错误的是
) e5 K$ [9 w9 Q1 |A、线性表采用顺序存储，必须占用一片连续的存储单元。
B、线性表采用顺序存储，便于进行插入和删除操作。
% k& f, X( [5 r  r0 VC、线性表采用链接存储，不必占用一片连续的存储单元。
D、线性表采用链接存储，便于插入和删除操作。
正确资料:


/ G$ E. c5 S% \1 ?资料来源：谋学网（www.mouxue.com）,设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
$ o7 Q# s0 Q# H) ~+ n2 K/ tA、8
* W+ \; p  V/ Z5 I. ~; S. oB、3
: _& a6 O9 o/ n7 r- Z4 ]( c& ^C、5
% Z- E. ]/ C0 S! R9 Q$ Y2 z9 K/ ], JD、9
2 ]# f; D% F( {/ H# Q正确资料:
9 u( w. j6 X6 v% P- y

  }& f  E' z' ?) G, r) @第13题,在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是
A、G中有弧Vi，Vj
B、G中有一条从Vi到Vj的路径
C、G中没有弧Vi,Vj
3 w3 t& T/ k8 y  D( c/ qD、G中有一条从Vj到Vi的路径
正确资料:
$ e1 y% g  v# p/ r- Q

第14题,在待排关键字序列基本有序的前提下，效率最高的排序方法是
A、直接插入排序
B、快速排序
6 R3 o% A4 L2 Q+ o+ q: Q9 l5 b& YC、直接选择排序
D、归并排序
正确资料:

: s, p7 C! k; L  A; i" y
/ U: R5 C% F4 B" p, P资料来源：谋学网（www.mouxue.com）,树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是
A、树的后根遍历与其对应的二叉树的后根遍历相同
5 r2 x5 D$ C/ k0 U5 LB、树的后根遍历与其对应的二叉树的中根遍历相同
" v  ]) c3 w/ d* wC、树的先根遍历与其对应的二叉树的中根遍历相同
D、以上都不对
正确资料:
/ z' ^% V+ y' z
) c0 L8 [& J; C
第16题,若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
A、4
B、5
4 ]: a3 W9 ~7 |8 N+ M4 f7 y2 eC、8
( f! B9 C; Y( d) t) wD、9
正确资料:

* B7 {% I  Q+ ?5 J
第17题,下面的叙述不正确的是
$ y" N! f4 W6 M) O$ u* n  nA、线性表在链式存储时，查找第i个元素的时间同i的值成正比
B、线性表在链式存储时，查找第i个元素的时间同i的值无关
C、线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
! j& H& p' @, D5 q& M3 dD、线性表在顺序存储时，查找第i个元素的时间同i的值无关
9 o9 Z6 @) T# F! {4 p% e正确资料:
! o% g) \* O8 t# K# Q% z' z

* a! h) n8 z" `; p, V% z+ }第18题,若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为
A、n-1
B、?n/m?-1
( {* s* t% K& t2 wC、é(n-1)/(m-1)ù
D、én/(m-1)ù-1
# d0 x7 e* p/ Q% A3 ~' e' f正确资料:
5 \3 z$ X7 i7 g% h. X8 S
+ Q$ a. G+ t; z$ F+ R: j
第19题,在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是
A、LL型
" _1 X7 n2 H: K  q' nB、LR型
/ Y# B, ^0 s- FC、RL型
D、RR型
正确资料:
& R6 T. M; y; c0 R9 g6 `) y9 f
- W- q# Q! G+ m1 S/ q# _& f  V% Y4 p
资料来源：谋学网（www.mouxue.com）,二叉树中第5层上的结点个数最多为
$ ?) N* g5 ?$ C4 ?4 v& X% Y* SA、8
B、15
C、16
0 a9 O  k% K, f! q; iD、32
7 `  s1 w, K# V正确资料:

- q. M, W# B* |4 a$ d: i# a$ @% w

" |+ s& }# I) ~7 x# j

! N3 {1 u: I3 |/ @( U' ~
. ~; d, r6 k5 M& L) {2 l8 W9 \+ ~. ~
1 [$ \, m( m( @( t  E" {
# c  g$ {  M* ]4 J/ f. [$ a


, n5 p7 y4 \5 c+ N
; @! s% Y% @# k" Q7 t* k8 t. n
, U' b; c) P/ y9 f