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

同学情

《数据结构Ⅱ》在线平时作业1
2 {9 D8 D/ a7 [# V, T试卷总分:100  得分:100
+ Z. @( F- ]" y" H  }4 {8 a. t& K一、单选题 (共 20 道试题,共 100 分)
) ~0 ?/ D: M% y, ~' @/ |! U: ^$ f1.判定“带头结点的链队列为空”的条件是
A.Q.front==NULL
B.Q.rear==NULL
* ^# _0 \* t5 LC.Q.front==Q.rear
2 K' I# m7 @6 [1 \! ED.Q.front!=Q.rear
: P% q0 N; b7 M! K5 Q9 l) C. [2 u) z资料:

2.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为
A.O(n)  O(n)
B.O(n)  O(1)
5 M  S6 P0 x- C$ GC.O(1)  O(n)
D.O(1) O(1)
& b& y& a7 r  c7 q& h资料:
6 W+ T, w7 B0 _/ z
! A4 d! w) ]$ S+ [' p  H8 ?3.由同一关键字集合构造的各棵二叉排序树
A.其形态不一定相同，但平均查找长度相同
B.其形态不一定相同，平均查找长度也不一定相同
, z$ u) ~( q  g- o5 `. |  }C.其形态均相同，但平均查找长度不一定相同
. _' i$ ^+ _" N% F1 FD.其形态均相同，平均查找长度也都相同
资料:

4.对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为
A.(19，23，56，34，78，67，88，92)
6 s' T8 b' t6 X0 cB.(23，56，78，66，88，92，19，34)
5 \+ z- `; R) ]: zC.(19，23，34，56，67，78，88，92)
D.(19，23，67，56，34，78，92，88)
资料:

5.可有效提高次关键字查找效率的文件是
A.顺序文件
B.倒排文件
C.散列文件
D.VSAM文件
资料:

6 z' V9 k4 k; x2 G4 p0 f4 T, L6.数据结构中所定义的数据元素，是用于表示数据的
* I7 [7 ^/ e& g, d' c- E2 L$ A$ m& fA.最小单位
9 F, t  ?9 E4 M+ \B.最大单位
C.基本单位
+ [, l6 C7 r' UD.不可分割的单位
资料:

7.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为
A.O(0)
B.O(1)
( V+ z( ~# j8 l6 VC.O(n)
D.O(n2)
0 a7 O" v; S' x9 e资料:
1 m4 s4 N9 R4 `" e+ O- H
0 [. l* |6 ?8 z' ^: l" j1 S8.若<vi, vj>是有向图的一条边，则称
A.vi邻接于vj
B.vj邻接于vi
0 r: G4 s, X: y/ o1 y. v/ j5 JC.vi和vj相互邻接
D.vi与vj&shy;不相邻接
资料:
! q! U: W# M: ^# t9 K/ y
% e8 z' k6 b1 V9.若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为
A.f,c,b
4 z& N  l1 S* @( {2 x( E2 J1 gB.f,d,b
0 K8 J$ Q! V" k/ lC.g,c,b
- u7 I# z$ m9 e' F/ uD.g,d,b
7 ]5 L+ b5 m1 F& K) J资料:
0 T8 \! L7 `, J
3 ^, O2 I% s, U9 @2 U' v10.高度为5的完全二叉树中含有的结点数至少为
A.16
B.17
C.31
7 q3 f& R& ?0 L2 rD.32
资料:
9 m% t, R! J/ W$ w- I1 c; d
+ e5 a& C) \' E( E3 y2 ]11.含n个关键字的二叉排序树的平均查找长度主要取决于
! [  g% L0 D% D# U, bA.关键字的个数
9 x5 Z, K* r7 |$ cB.树的形态
8 f  \# |" ?7 R" i8 p# uC.关键字的取值范围
3 I$ @* P3 }0 \4 CD.关键字的数据类型
资料:

12.队列和栈的主要区别是
% R; i) h+ Y8 i1 P% d3 gA.逻辑结构不同
B.存储结构不同
C.所包含的运算个数不同
D.限定插入和删除的位置不同
资料:
$ C+ L5 K. b+ |) m
13.已知散列表的存储空间为T[0..18]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是
6 `5 J: N; e0 Y  BA.T[2]
B.T[4]
C.T[8]
) k  j) |: @9 ~9 v5 f! wD.T[10]
, U# ]: q! s/ G  o4 H6 @资料:

14.根据数据元素的关键字直接计算出该元素存储地址的存储方法是
A.顺序存储方法
; Q* {  r& u" n; l( L0 SB.链式存储方法
C.索引存储方法
D.散列存储方法
资料:
5 M& v! y+ k6 ?
/ }$ V5 @4 X5 u2 N% y- |15.下列关键字序列中，构成小根堆的是
A.{84，46，62，41，28，58，15，37}
B.{84，62，58，46，41，37，28，15}
C.{15，28，46，37，84，41，58，62}
D.{15，28，46，37，84，58，62，41}
资料:

16.ISAM文件和VSAM文件的区别之一是
A.前者是索引顺序文件，后者是索引非顺序文件
B.前者只能进行顺序存取，后者只能进行随机存取
5 d0 c9 G: g& Q0 |% t' T2 H" LC.前者建立静态索引结构，后者建立动态索引结构
D.前者的存储介质是磁盘，后者的存储介质不是磁盘
资料:

17.适宜进行批量处理的文件类型是
A.顺序文件
B.索引顺序文件
! \/ [! L7 r5 {4 b7 FC.散列文件
D.多关键字文件
资料:

18.下面关于线性表的叙述中，错误的是
- S7 ]/ |! v& CA.线性表采用顺序存储，必须占用一片连续的存储单元。
B.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链接存储，不必占用一片连续的存储单元。
D.线性表采用链接存储，便于插入和删除操作。
* Z# a6 Z% Q2 b资料:
% N+ r# K" l$ j3 J; a) c3 s% G/ z! d) m
/ Z, z" l' P! _% n7 N! N  p19.某带头结点的单链表的头指针为head，判定该链表为非空的条件是
A.head==NULL
B.head->next==NULL
C.head!=NULL
0 y$ x% f$ E( V; F' E3 E# ^D.head->next!=NULL
资料:
8 z, e% |$ G; z# a! s: O
+ e' e. \( w8 h0 P, O20.计算机识别、存储和加工处理的对象被统称为
, W! X9 ?* z$ e' |4 AA.数据
B.数据元素
C.数据结构
D.数据类型
6 x- D& I, E0 q7 Z: a6 I5 f资料:


  }- c# e( [7 C+ p: p  a- ?
% H- B$ p( Q0 i$ r

: n/ p* K+ _! I, t




( `# P7 l/ H2 P: F* w% h0 ]9 H
. E; c7 _  f1 h! N4 l# Q* I
  D8 [( ]) P0 t4 \3 A& Q/ g
$ }, c% e% B/ [9 C
9 ]8 o- I, f" f
% y- V$ Y' T1 U3 O; @( G% _
% h. H5 I# M0 Y
, j: [& h! m. ?$ ]7 P: `: S6 t) F0 Z$ L

5 V7 w# k4 O& I: f# b$ e) t
+ C2 B( G2 X1 s2 r+ \, ?
《数据结构Ⅱ》在线平时作业2
& ]' u' c0 i) M) a试卷总分:100  得分:100
5 f/ }& M1 P3 S$ A0 H一、单选题 (共 20 道试题,共 100 分)
& i8 {% E+ B9 U6 R6 d1.判断两个串大小的基本准则是
# M/ B( a+ n6 P! I7 L  R" CA.两个串长度的大小
. Y3 }/ P) a' x& b& v+ c9 ]B.两个串中首字符的大小
C.两个串中大写字母的多少
D.对应的第一个不等字符的大小
! c8 U# M+ G' `- n- j) b资料:
- n4 w; e1 {7 }! E' k( |
2.已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为
+ z$ R* J$ D3 Q% cA.ABCDEF
3 r, X9 L! P3 _9 [B.ABCEFD
: R3 n+ B# y: ^; j2 i. _C.ABFCDE
6 G" s7 B$ c0 d0 ^- M, r7 i' J  XD.ABCDFE
. O5 j! ^1 n% X1 `资料:

3.采用ISAM或VSAM组织的文件是
! y$ E/ b0 z+ Z4 @/ ]2 ]3 ^A.索引非顺序文件
* u, }7 C- i7 _B.顺序文件
C.索引顺序文件
; M7 L6 C% r% i. l) e2 K2 y6 {D.散列文件
资料:
0 V) U: c- @6 W, a/ X3 X
2 E# y0 D+ J# w% h6 m4.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
  _  N: t0 a* m' s) ]A.深度优先搜索算法
B.广度优先搜索算法
9 S* A4 i: B# HC.求最小生成树的prim算法
. f( l% J* |3 h8 ID.拓扑排序算法
资料:

6 A: Z6 {% u' W1 [' S0 E- Q5.链栈与顺序栈相比，比较明显的优点是
* e3 l$ l$ Z& z8 t0 VA.插入操作更加方便
+ O* J" i2 P" n; `5 w. b- qB.删除操作更加方便
C.不会出现下溢的情况
D.不会出现上溢的情况
/ F* A" [5 I; p7 E8 ?资料:
, f& W8 z0 U& X" z1 }6 w/ w) N
& h+ d; ]- Y! J  S8 f2 X0 U. @6.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
A.n-1
. {* X* V; t9 F0 L, E- ~: L9 S  XB.n
/ U& D! C* o& P$ _C.n+l
9 L* V; J. y/ {- XD.2n
资料:

$ ~/ I* }/ C8 V: k& H  F: u) n5 s7.一棵树高为K的完全二叉树至少的结点是
1 e9 b! C$ c2 P( x# G, PA.2k &ndash;1
B.2k-1 &ndash;1
/ n2 N9 [+ C& z& U3 gC.2k-1
, R' [% _* D6 `9 v, U) y$ ?D.2k
资料:
, o( e7 j+ ^7 s1 X# S1 g; N  s
8.设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
6 F. l. p+ A. x4 e4 A0 e: IA.2
. |* \2 M% R4 kB.3
C.5
. c7 M/ Q- E  Q/ n6 @D.6
6 \" h/ |3 q0 a  `" r" Y* V" Z资料:

9.当采用分快查找时，数据的组织方式为
A.数据分成若干块，每块内数据有序
B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
, B- n/ R7 C1 e: e6 F( S' MC.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
" g0 i3 w% T) \: v* Q6 fD.数据分成若干块，每块（除最后一块外）中数据个数需相同
资料:

0 {; W8 G& @: @5 z10.抽象数据类型的三个组成部分分别为
A.数据对象、数据关系和基本操作
B.数据元素、逻辑结构和存储结构
C.数据项、数据元素和数据类型
+ V2 H- k8 Q7 J% M3 WD.数据元素、数据结构和数据类型
7 O7 Q! n9 s0 L  H/ {" T+ ^资料:

11.下面关于线性表的叙述中，错误的是
2 a3 B, `4 L; W$ HA.线性表采用顺序存储，必须占用一片连续的存储单元。
B.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链接存储，不必占用一片连续的存储单元。
D.线性表采用链接存储，便于插入和删除操作。
资料:

12.设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
0 i. t. _8 M7 c9 jA.8
+ O9 t3 M. Z/ F* u+ {2 cB.3
4 P' K* M' N" p8 @% s4 gC.5
D.9
资料:

13.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是
1 u, C, s" q# ^$ }1 c* W5 hA.G中有弧<Vi，Vj>
6 I, V# K2 O# ]/ Q* _* BB.G中有一条从Vi到Vj的路径
/ r7 \( l1 w3 ?6 XC.G中没有弧<Vi,Vj>
D.G中有一条从Vj到Vi的路径
$ f1 Y5 Y& J& D! P: V% V- r; t资料:
  t0 ?4 X% u9 K8 ~3 K" e
14.在待排关键字序列基本有序的前提下，效率最高的排序方法是
+ X( F4 w9 q2 f, j$ h& pA.直接插入排序
1 R% x7 q* F  N  B* C8 q5 \B.快速排序
C.直接选择排序
D.归并排序
: }! ~0 j1 z8 ?% c) o- i9 V  \资料:

15.树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是
( z' S( {" {6 T1 T8 PA.树的后根遍历与其对应的二叉树的后根遍历相同
* p! @) r( y3 F' i8 a% v0 X3 Z8 wB.树的后根遍历与其对应的二叉树的中根遍历相同
C.树的先根遍历与其对应的二叉树的中根遍历相同
, D" |% q% K" Q6 R" eD.以上都不对
资料:
0 y- c4 R# x( M+ w5 {
16.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
+ P% k" D. N' F) [9 TA.4
5 W. d" D9 f( y- }- k# k2 xB.5
C.8
' _' V- J8 f7 r' [" m7 R- iD.9
: B+ ]  E) N$ F- M4 L资料:
9 e& Z1 s9 [' \2 O( [
( e0 V" v. d% x17.下面的叙述不正确的是
1 D! H2 ]8 L5 j# T* ^) q+ J0 c! }) |+ mA.线性表在链式存储时，查找第i个元素的时间同i的值成正比
  v% f$ E" P; ~5 `B.线性表在链式存储时，查找第i个元素的时间同i的值无关
% L5 @; y$ q$ l8 t" _/ n7 ]. ?C.线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
D.线性表在顺序存储时，查找第i个元素的时间同i的值无关
% ]+ P- s8 H  P- {& f% t资料:

# S# n' Q* d4 D6 f* a+ }4 f& x  ^+ z# r/ Y18.若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为
' ?3 w+ M) Q3 l' A/ y$ FA.n-1
+ ?' V) s( [( q6 y3 l& ]2 `9 ZB.&euml;n/m&ucirc;-1
C.&eacute;(n-1)/(m-1)&ugrave;
$ T8 x0 d) Q% U' Y- U& K' }  bD.&eacute;n/(m-1)&ugrave;-1
  Z* V+ g: a3 \0 v; n( t) N资料:

19.在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是
! F9 F4 ?& t7 s2 S# u+ YA.LL型
) z6 |  R! G8 g0 }! ]' ^; O! MB.LR型
C.RL型
D.RR型
( D  t! Y: B( N1 i' _资料:
& ~; l* V, v' W$ V$ G
20.二叉树中第5层上的结点个数最多为
A.8
5 L8 a( h& I* ?- P* vB.15
C.16
D.32
资料:
/ ^* D$ x; f  _2 x2 Q
. v1 O/ b( h# I( ^- R/ m  K2 }


1 Y! L6 I7 D% o) Y* f& B
# o; o, _" ?7 s

( |: }6 o& Y4 K# w# X# u% f
3 P: M/ {- L2 k1 d
7 G' @' g0 d/ P5 J8 d2 p; S

% m# {- ^* y  u$ N* c& g+ h! v2 z9 i
( Z4 t. U! Y/ V0 q3 C7 ~! H
6 B  Y7 ?6 U, U# R5 s- b《数据结构Ⅱ》在线平时作业3
试卷总分:100  得分:100
一、单选题 (共 20 道试题,共 100 分)
1.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
A.O(n)
B.O(e)
C.O(n+e)
D.O(n2)
资料:

2.索引非顺序文件的特点是
% T; R& _- Y3 @A.主文件无序，索引表有序
B.主文件有序，索引表无序
6 K8 l# |% H0 y, p; A& G2 sC.主文件有序，索引表有序
D.主文件无序，索引表无序
* i6 M" `2 w* q8 V& [资料:
  K  v! j8 k- U$ e* e
3.二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为
A.470
B.471
C.472
9 {. d" h5 ^5 ~D.473
( O4 C7 ~8 G3 K, c+ j6 g资料:
; g, @- ], }- a/ d6 `8 B
4.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是
A.p=p->next;
B.p->next=p->next->next;
8 Q7 {/ A& D7 G( @C.p->next=p;
D.p=p->next->next;
$ ?* H$ f: r' R" g资料:

: @1 |4 b5 f& }" g( G" r5.引入二叉线索树的目的是
A.加快查找结点的前驱或后继的速度
4 P$ F  g$ m, Q  P; f" t: X. |& GB.为了能在二叉树中方便的进行插入与删除
3 H  y1 [1 p6 WC.为了能方便的找到双亲
% L, r1 f6 C0 B2 U5 F* i0 ?D.使二叉树的遍历结果唯一
, G& g0 R: U+ c( d" v资料:
! Z  r% ~# X8 s0 s  d6 Q
$ |0 h7 p+ ~: U$ v- Z6.一棵树高为K的完全二叉树至少的结点是
+ z$ ~- ~! ?* E% b4 KA.2k &ndash;1
B.2k-1 &ndash;1
C.2k-1
, [! @, t  i5 h5 G1 |" OD.2k
资料:

7.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
* a  C* G! E. DA.分块查找
B.顺序查找
7 t& [4 I! G- s- SC.二分查找
D.散列查找
& \, g% |2 n/ i/ O3 u资料:
2 t' r( k5 H5 y3 \- k+ S
9 a  `+ ~1 h3 t+ H* `" W# k% ]6 P8.某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是
) f+ w0 {+ w9 d- j% S& r6 A- NA.1
5 V$ u, n: `0 C# ?$ y4 ]5 z+ NB.2
C.3
D.4
; p; `) q  @0 O3 B% Q/ a2 C资料:

9.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
A.5
B.6
C.16
D.17
, ]2 @! H: Z1 }" H- ?8 B5 G资料:

! r  c) H* p1 v8 i2 Y/ e' W* S9 s10.在长度为n的顺序表中删除第i个元素(1&le;i&le;n)时，元素移动的次数为
A.n-i+1
6 e# h  H3 Q, mB.i
2 l' h* U- D8 NC.i+1
D.n-i
资料:

11.从逻辑上可以把数据结构分为两大类，即
A.动态结构、静态结构
  J6 G3 X0 z$ \/ B) j0 \B.顺序结构、链式结构
6 o; {' n5 o% eC.线性结构、非线性结构
0 u2 M7 N+ r( o* [. tD.初等结构、构造型结构
. J- \3 K* c8 ^6 T. S7 n8 ~, x资料:
# W: O. P. v5 ^( y9 `0 u
5 p( U6 w; x0 |! H3 X12.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
A.深度优先搜索算法
  U* c  @  i8 J+ hB.广度优先搜索算法
C.求最小生成树的prim算法
3 G7 G0 U: I. N% _, }8 uD.拓扑排序算法
8 \. r5 C. M5 h1 D" v资料:

8 u' }0 G0 ]0 a. Y3 D5 C+ i  E13.为便于判别有向图中是否存在回路，可借助于
2 [/ ?4 n$ F9 C( m9 o) d( X" vA.广度优先搜索算法
6 ~5 N/ y- E) u0 ?. KB.最小生成树算法
C.最短路径算法
D.拓扑排序算法
资料:
# t3 b# f/ v0 w: w* H0 x
# P+ t$ T1 ]7 M% O0 _14.队列和栈的主要区别是
6 ]9 o1 Z3 i! e* f; _; }3 VA.逻辑结构不同
B.存储结构不同
/ z7 C0 r1 W9 V2 XC.所包含的运算个数不同
- {# u- M3 `& [1 Z% v' XD.限定插入和删除的位置不同
2 S( A& j9 T0 D8 o, u! r. \3 Y资料:
5 ]4 ~" \: a% k) X6 X8 n2 ^1 |
8 ^! ?. }) y" \7 d( I15.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=
) A* N8 E  c, t; X5 r" a9 I$ b) _  head,则
A.p指向头结点
B.p指向尾结点
C.p的直接后继是头结点
- o4 `' A  G& D) X: @& l1 VD.P的直接后继是尾结点
& i& \0 q. ]; {$ Z/ F# M6 v9 i资料:
4 ?' g) p2 w/ Y2 ~  Q
0 d. j1 e8 M. F( D% d, R2 a1 k' {1 w16.若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上
' O) C' N9 ]# f9 @( \0 ?, [A.操作的有限集合
( Y9 N; G; ^, X! rB.映象的有限集合
C.类型的有限集合
6 W1 F; `7 \; ~0 cD.关系的有限集合
3 F  s' F, v2 Z0 `5 M% ]- \) A: ^0 r资料:

17.通常将链串的结点大小设置为大于1是为了
A.提高串匹配效率
B.提高存储密度
C.便于插入操作
D.便于删除操作
资料:

18.对长度为n的关键字序列进行堆排序的空间复杂度为
A.O（log2n）
6 d: Y7 L* j1 [B.O（1）
- W8 G0 z* `, L4 a- l2 _C.O（n）
# ]% h, f6 I& {D.O（n*log2n）
: a1 _# `, y! Y* [+ M资料:
/ {9 D# I: ^% E+ }' y
8 t, j$ a; u; b19.在一个带权连通图G中，权值最小的边一定包含在G的
A.最小生成树中
* \. K  S* N1 w1 \2 r9 p/ gB.深度优先生成树中
2 E% l: t) X$ @9 Z7 [3 bC.广度优先生成树中
D.深度优先生成森林中
资料:
- P5 X# W7 m8 T
20.假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为
) E, M* y  K& @# e( EA.(rear-length+m+1)％m
B.(rear-length+m)％m
( P! l( \, Y( w0 Y4 L! UC.(rear-length+m-1)％m
$ V/ e3 }* \# x: D: N0 oD.(rear-length)％m
资料:

# Q* b# _$ }9 C

* w, e3 ]; ^9 \  R