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

同学情

《数据结构Ⅱ》在线平时作业1
试卷总分:100  得分:100
一、单选题 (共 20 道试题,共 100 分)
/ \0 V' w0 K! Q5 [& i* J; w1.判定“带头结点的链队列为空”的条件是
A.Q.front==NULL
+ O, m1 R! k* B; [- P) JB.Q.rear==NULL
C.Q.front==Q.rear
$ @3 s+ D' ?1 c9 }D.Q.front!=Q.rear
- r/ N" t# Q: D% G2 d# o资料:

% D! J- j# T( K( c0 b5 q2.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为
A.O(n)  O(n)
B.O(n)  O(1)
C.O(1)  O(n)
* ^& g/ E% d% k( R5 u2 qD.O(1) O(1)
' f9 I9 b8 t3 V+ e5 R, S资料:

, ^1 _% B# d, u& P* f3 H3.由同一关键字集合构造的各棵二叉排序树
A.其形态不一定相同，但平均查找长度相同
B.其形态不一定相同，平均查找长度也不一定相同
C.其形态均相同，但平均查找长度不一定相同
D.其形态均相同，平均查找长度也都相同
! n$ }4 ~/ ~1 C) M; t资料:
5 J0 N" n0 Z: P+ t; z0 Q
4.对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为
A.(19，23，56，34，78，67，88，92)
B.(23，56，78，66，88，92，19，34)
$ U( F0 F' J" ^$ kC.(19，23，34，56，67，78，88，92)
D.(19，23，67，56，34，78，92，88)
资料:
6 `. a  _& A" o2 t8 F# t# e  H
5.可有效提高次关键字查找效率的文件是
A.顺序文件
B.倒排文件
C.散列文件
D.VSAM文件
  C- Q# N5 y1 {1 t资料:
/ k5 N8 ^: z8 g/ \- r
6 i  J4 u1 Q  u6.数据结构中所定义的数据元素，是用于表示数据的
A.最小单位
& b0 M( U" W) JB.最大单位
% x; V) @* }5 ?4 m3 NC.基本单位
" p3 a- Y. q7 c2 m7 eD.不可分割的单位
资料:
$ _3 ~5 Q- O, v5 J: s
7.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为
% u4 W& c8 Q' j% s4 nA.O(0)
B.O(1)
3 ^6 f7 h, i5 l: v. S5 k( {C.O(n)
D.O(n2)
1 V1 s/ n- d/ _$ D' ]7 t资料:

( c" G: M! J% G1 }% E6 h# t8.若<vi, vj>是有向图的一条边，则称
A.vi邻接于vj
: b2 R/ t# R. r+ O" Q8 i& l0 G! jB.vj邻接于vi
5 Q' ?- A' c1 E% XC.vi和vj相互邻接
D.vi与vj&shy;不相邻接
" t9 y6 ~  a( _# H" l3 I, {资料:
' s2 m/ m9 Q$ T' M: s' i+ Y( t
. F& e$ @# T" ^( E. _* H( b9.若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为
0 |. a5 ?; U# G$ @' YA.f,c,b
8 ]3 w! d; F; c1 q$ XB.f,d,b
C.g,c,b
D.g,d,b
6 C- D4 q2 w0 }( x; l( N* p$ t) b资料:

* S% e# q( ]7 V4 z# G% \10.高度为5的完全二叉树中含有的结点数至少为
A.16
B.17
# @- e+ ?2 s+ Z8 W5 ~  ~C.31
D.32
资料:

. ]( d# ^( V. v11.含n个关键字的二叉排序树的平均查找长度主要取决于
  f1 y8 g1 z, `A.关键字的个数
B.树的形态
C.关键字的取值范围
D.关键字的数据类型
1 [/ x7 `7 f: ^# X+ r" [资料:

12.队列和栈的主要区别是
A.逻辑结构不同
B.存储结构不同
C.所包含的运算个数不同
% G6 o+ N+ N7 y0 ]7 N& xD.限定插入和删除的位置不同
3 r9 r" M* i$ ?8 M( [0 w6 k资料:

2 p7 T5 ~2 ]5 B13.已知散列表的存储空间为T[0..18]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是
0 K9 L" q6 S& y  x/ PA.T[2]
B.T[4]
C.T[8]
D.T[10]
资料:
1 N, P! U1 [3 `. C+ L
14.根据数据元素的关键字直接计算出该元素存储地址的存储方法是
A.顺序存储方法
) N3 u0 X" e. R! t+ F) wB.链式存储方法
C.索引存储方法
- j% C0 n5 k( `D.散列存储方法
资料:
4 r' H+ V9 i9 i7 H6 ]" i
5 P, E+ _* l1 N# _15.下列关键字序列中，构成小根堆的是
$ w. u+ L; P/ l3 z) y8 t% @/ ]A.{84，46，62，41，28，58，15，37}
$ Z6 D( @8 n, LB.{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}
资料:
0 B/ @0 B1 g1 W) J1 Q
2 A9 ^& B9 m) f1 P4 A" H16.ISAM文件和VSAM文件的区别之一是
A.前者是索引顺序文件，后者是索引非顺序文件
/ Z& G; I3 d" _7 h" N' wB.前者只能进行顺序存取，后者只能进行随机存取
C.前者建立静态索引结构，后者建立动态索引结构
" b. A; |  ?' S* j8 v, {) fD.前者的存储介质是磁盘，后者的存储介质不是磁盘
6 J9 F1 g* n8 ^: O资料:
) G. P* `, x8 \- e* x
17.适宜进行批量处理的文件类型是
3 R5 f; \. q+ o7 D$ [7 rA.顺序文件
B.索引顺序文件
C.散列文件
D.多关键字文件
资料:

5 e- G4 A6 i$ n, m18.下面关于线性表的叙述中，错误的是
A.线性表采用顺序存储，必须占用一片连续的存储单元。
4 r) F0 s3 B2 J) d* z& xB.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链接存储，不必占用一片连续的存储单元。
4 j: T* e! I9 k0 f" ~; e7 pD.线性表采用链接存储，便于插入和删除操作。
资料:
) b* Z0 J% d, b
19.某带头结点的单链表的头指针为head，判定该链表为非空的条件是
A.head==NULL
B.head->next==NULL
C.head!=NULL
7 V$ B+ E- \' `( M" ^# w) t1 WD.head->next!=NULL
* K. v% q& M4 Z2 \资料:
# J1 D6 y9 A) y! {. h, i1 x2 Y
20.计算机识别、存储和加工处理的对象被统称为
! |4 n! ?) `; [0 {) q! FA.数据
B.数据元素
C.数据结构
D.数据类型
资料:
0 `! t; M7 V$ ^. f


! f  ]  E/ J2 @1 R$ o! z: C
+ u2 o9 A2 e2 }

% T( L  O  C( U% i) V7 m




$ X" F" O* G* m& {2 v) h

( ?" j/ S8 j" Q; G  l9 P* J: T5 r

2 |; t0 s6 w, v
, N! b( j2 |% H2 }7 d




8 g- E4 Z; ?# @3 B% v. B《数据结构Ⅱ》在线平时作业2
试卷总分:100  得分:100
# g9 M& m) v* P1 i一、单选题 (共 20 道试题,共 100 分)
1.判断两个串大小的基本准则是
9 k. u: t& P; L' Z  N! M& rA.两个串长度的大小
B.两个串中首字符的大小
C.两个串中大写字母的多少
D.对应的第一个不等字符的大小
7 g% }! O9 D( ^3 F: n8 ?资料:

& I0 ~/ V  P, Q( _. m" R- b0 t$ [6 ~2.已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为
A.ABCDEF
. C/ N, h* s) c0 [- ~1 vB.ABCEFD
C.ABFCDE
' g, C5 [7 b3 j5 cD.ABCDFE
资料:

; ]$ C. v2 |- N' C9 O9 W3.采用ISAM或VSAM组织的文件是
# i+ x( m& c4 R9 C& {. oA.索引非顺序文件
; v9 r: [8 H1 _6 p  b1 JB.顺序文件
C.索引顺序文件
D.散列文件
5 H+ C8 p0 C" W. C: U  t资料:

+ {. ?/ i7 _4 v. m4.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
1 M( B4 U3 V1 NA.深度优先搜索算法
# r8 o) H7 {. l+ s+ j! ^- N; @B.广度优先搜索算法
$ }- `  \+ s. p% W: R! T/ z. jC.求最小生成树的prim算法
D.拓扑排序算法
资料:
8 @1 R: L6 X+ ]
5.链栈与顺序栈相比，比较明显的优点是
A.插入操作更加方便
1 d- l- }; }3 s2 hB.删除操作更加方便
C.不会出现下溢的情况
5 L% `) F! z" |6 b% c3 d# @/ SD.不会出现上溢的情况
" S7 [- f( `* @! Y- b5 c* `& ~资料:

6.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
A.n-1
7 p. A% z. w9 ?+ E( h, ?9 sB.n
5 D) m; X0 e7 z$ p$ y4 D( \3 s" ~C.n+l
# l- @* D, l, DD.2n
6 }5 i) V$ q+ j2 R- f资料:
  k2 l3 C8 y" J5 K4 j; L' ]
7.一棵树高为K的完全二叉树至少的结点是
/ y, t/ r6 T. z2 f: vA.2k &ndash;1
B.2k-1 &ndash;1
C.2k-1
D.2k
资料:
& l; y* g; l- z9 l. q9 T5 n
& p, a) j9 _/ c- I- a& Y8.设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A.2
( X2 z3 E; t. n) }B.3
" d5 c9 @$ s( l" v5 z: {3 tC.5
; n7 e6 T5 w$ \6 C' j- MD.6
1 _4 k/ M, i9 G7 M, D  z% c资料:
2 l/ q0 g% x3 R" P4 Z- [2 o# p
9.当采用分快查找时，数据的组织方式为
A.数据分成若干块，每块内数据有序
B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
1 T: L" F$ m( S/ O2 v+ @! jD.数据分成若干块，每块（除最后一块外）中数据个数需相同
1 N- T- ^; _$ `3 A0 v资料:
' W: U  `" H: _, P% p
9 R3 s# |/ |0 z' E0 Z1 Y  W0 Z10.抽象数据类型的三个组成部分分别为
2 R, k3 s  J, e/ U7 m( t* ~A.数据对象、数据关系和基本操作
, i6 I9 n0 C5 A3 j% ~* eB.数据元素、逻辑结构和存储结构
C.数据项、数据元素和数据类型
D.数据元素、数据结构和数据类型
资料:

11.下面关于线性表的叙述中，错误的是
' u/ P( r. X6 S6 |& BA.线性表采用顺序存储，必须占用一片连续的存储单元。
6 B' \1 D5 o- [+ J- ^B.线性表采用顺序存储，便于进行插入和删除操作。
% ]: P! i# i, Y6 Z5 H' g4 ^C.线性表采用链接存储，不必占用一片连续的存储单元。
D.线性表采用链接存储，便于插入和删除操作。
资料:
. b6 ~" `4 h0 p/ M+ O' x
12.设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
+ X; K5 o# G, S: S- a7 zA.8
% A8 k6 `2 G, T" T. |( w* `- oB.3
C.5
D.9
资料:

13.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是
A.G中有弧<Vi，Vj>
, B, Y6 b; H) b* ~1 @* J; FB.G中有一条从Vi到Vj的路径
C.G中没有弧<Vi,Vj>
D.G中有一条从Vj到Vi的路径
" V. Y9 s5 J- W! ~资料:

14.在待排关键字序列基本有序的前提下，效率最高的排序方法是
A.直接插入排序
- B! n; J$ B, oB.快速排序
C.直接选择排序
D.归并排序
0 p7 O* f5 G5 z/ H# N资料:
( b% n' x) F! B/ s/ l) E' h
. x8 W) y3 k. ]- O; I; x/ s9 ~15.树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是
A.树的后根遍历与其对应的二叉树的后根遍历相同
8 p3 f7 v- A3 L& fB.树的后根遍历与其对应的二叉树的中根遍历相同
$ A. o5 V3 d0 O- T5 qC.树的先根遍历与其对应的二叉树的中根遍历相同
- K8 y3 f; ?( z7 x+ s: J* xD.以上都不对
2 ]8 f+ K8 Q( Z# c4 ^! V资料:
0 `; F/ m: D" H+ o
0 c  {, }2 J8 ^- p" i16.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
8 I+ c7 B, h. j5 rA.4
B.5
! b* Y5 H* V. P0 tC.8
D.9
资料:
0 H4 r5 m2 s6 R1 B- b3 c( x
& W3 i- L9 N+ B' q3 d7 o8 r& g17.下面的叙述不正确的是
9 ]! d& \% x. {A.线性表在链式存储时，查找第i个元素的时间同i的值成正比
B.线性表在链式存储时，查找第i个元素的时间同i的值无关
C.线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
: e, ^' u2 C) g( iD.线性表在顺序存储时，查找第i个元素的时间同i的值无关
" M: L0 ?- k! O; e1 U. `% m资料:

8 F' U# l7 x& w' b# A' E  ^18.若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为
A.n-1
B.&euml;n/m&ucirc;-1
C.&eacute;(n-1)/(m-1)&ugrave;
D.&eacute;n/(m-1)&ugrave;-1
资料:
! w! S/ c' N& H/ F
19.在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是
A.LL型
B.LR型
C.RL型
! r! ?  @. j& ~( U* M0 pD.RR型
资料:
! j  `/ y+ Z& m/ @7 Q# y
2 a% N& J, l& u: |0 h* I. W20.二叉树中第5层上的结点个数最多为
A.8
B.15
C.16
D.32
资料:
$ c# x: ]9 s$ i  U" Y, k& \
) @* v9 J% v2 V4 s5 @+ I* x

+ X. H) ^* G2 N5 `" X



7 ?  f4 A" o6 y



$ q/ R/ y$ U/ m! P
- _- \# H5 b! S( g! h7 X0 H) A
《数据结构Ⅱ》在线平时作业3
) ]& Y$ h4 \1 G/ T2 d  d! Y3 h试卷总分:100  得分:100
一、单选题 (共 20 道试题,共 100 分)
9 f* ^8 B9 ~4 B: {; f8 h: ]  _7 V1.一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
% l; j. K( z; l1 j* MA.O(n)
% M% k) ~4 K0 H7 lB.O(e)
6 O0 l1 N- n: t8 d( A7 [& P- aC.O(n+e)
2 e. P* U) L& ID.O(n2)
资料:

2.索引非顺序文件的特点是
A.主文件无序，索引表有序
' [& l. y, b* S+ WB.主文件有序，索引表无序
+ r6 ^) D( b- Z2 i% K2 U6 S; X6 h+ |C.主文件有序，索引表有序
' C  F+ n9 k. @$ _8 q8 kD.主文件无序，索引表无序
+ J) b+ C) R  }. U! W资料:

3.二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为
A.470
5 X9 ], e5 T5 k7 H+ B, tB.471
C.472
! z2 U: L* ~# Q; _4 ]D.473
资料:
2 B! ], M+ ]$ o* i; H7 `" d
, O1 p6 i( Z4 c# w* L, y7 E- k9 ?  [$ T4.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是
A.p=p->next;
7 r+ d. B5 p+ ?: o5 tB.p->next=p->next->next;
. ?" b1 S8 {) OC.p->next=p;
# y- a1 h2 S7 `* p) P4 vD.p=p->next->next;
+ H$ |! d$ ?3 C( r7 t3 K% L5 R资料:

, I5 [0 g  `& c* `5.引入二叉线索树的目的是
A.加快查找结点的前驱或后继的速度
B.为了能在二叉树中方便的进行插入与删除
  B$ ~( O* f: }7 h4 {9 j& V* TC.为了能方便的找到双亲
D.使二叉树的遍历结果唯一
, ~7 Y* _" u9 \/ n7 @  w! r资料:

8 u% F& p% C# @$ z$ ~6.一棵树高为K的完全二叉树至少的结点是
5 i( [) e/ O; FA.2k &ndash;1
B.2k-1 &ndash;1
. C$ ^) V4 _0 Y2 ]- _' o  a7 dC.2k-1
D.2k
资料:

7 q5 N* a5 b9 \1 q$ s7.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
A.分块查找
' N+ b% n9 K1 O0 |7 H' x& R3 dB.顺序查找
C.二分查找
D.散列查找
8 I# d8 @, M, g2 |7 i$ |* F3 _8 a7 Z  b资料:
  l9 o5 B) c# P1 ^
8.某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是
7 t( f' J+ Q, y3 ~5 z$ z# O3 `A.1
B.2
C.3
$ x8 ^& W  s7 d& r$ XD.4
资料:

! d* U  }- s4 B! R& d9 Q1 S9.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
2 N2 p9 x, z+ X: D% n4 NA.5
& J! s% K! ?0 RB.6
C.16
D.17
" q! ?$ W5 ]: f# r资料:

10.在长度为n的顺序表中删除第i个元素(1&le;i&le;n)时，元素移动的次数为
A.n-i+1
3 G7 i- }4 t* y7 SB.i
8 S# V, ?, M; d9 G- l! C- rC.i+1
D.n-i
资料:
& G! W. h" X5 R1 R% a
11.从逻辑上可以把数据结构分为两大类，即
A.动态结构、静态结构
* E" H8 \; y. |- N0 g) c1 q1 ?B.顺序结构、链式结构
2 k+ A. u. y2 tC.线性结构、非线性结构
7 K' V0 u* S3 o+ ]D.初等结构、构造型结构
资料:

3 t/ W4 m. Y+ k+ T12.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
A.深度优先搜索算法
B.广度优先搜索算法
' w0 w7 c8 f3 ~+ t& pC.求最小生成树的prim算法
D.拓扑排序算法
/ d& x9 P  B' ?- W9 a: k资料:
" F8 v# A, S6 I% _3 W; d1 {3 E
  z3 ?+ F! R' m& \; u& F- f13.为便于判别有向图中是否存在回路，可借助于
, o/ d$ i  }  @  r2 A4 ?2 CA.广度优先搜索算法
( V) l( ^" `; ^; E* a+ x4 h! B/ kB.最小生成树算法
0 D% C1 |/ N% n4 E" N+ JC.最短路径算法
D.拓扑排序算法
资料:

0 z  \) i5 K; m: z1 o14.队列和栈的主要区别是
4 d* c5 J$ ^  t. [A.逻辑结构不同
$ ~' e% g# H6 G9 [6 c. G2 w" v' LB.存储结构不同
) C2 j; h4 h; G) I" r" [- o2 x3 YC.所包含的运算个数不同
. K5 Z  }: F4 M8 l. Y' kD.限定插入和删除的位置不同
; f( m+ Z* y9 \0 \资料:
) _$ _. t8 b9 t; y( t
& e5 g4 f2 g) A15.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=
  head,则
, l" X1 }) Q$ zA.p指向头结点
B.p指向尾结点
C.p的直接后继是头结点
D.P的直接后继是尾结点
" ?4 D+ @+ H0 R6 F* U资料:
, |1 G/ G' k3 _& o3 I
16.若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上
A.操作的有限集合
B.映象的有限集合
# J3 ~( S' t3 J; {" C  v; \C.类型的有限集合
& S- R% p9 Q# K% i+ d. c0 aD.关系的有限集合
资料:

- L5 o* \2 j. u( e' b& r17.通常将链串的结点大小设置为大于1是为了
A.提高串匹配效率
0 Z2 v9 `, h$ H$ O6 }, jB.提高存储密度
C.便于插入操作
D.便于删除操作
9 Y+ l$ s3 n3 w& ?8 y资料:
9 _2 a2 d0 J+ T* A2 [
18.对长度为n的关键字序列进行堆排序的空间复杂度为
# y) K' D4 Z% l1 n  s- `A.O（log2n）
4 E0 E! a6 `" N/ I2 p; KB.O（1）
+ a  \) }1 x# x; w- Y6 s7 D1 |C.O（n）
/ G: c4 z4 O/ a# D- J% a: z* Y+ ^# JD.O（n*log2n）
资料:

# w6 q, v2 |% _19.在一个带权连通图G中，权值最小的边一定包含在G的
" ~  K2 P  Z! @8 P: xA.最小生成树中
B.深度优先生成树中
C.广度优先生成树中
D.深度优先生成森林中
/ y# U- {# W3 @1 _, U5 e- j7 x. J资料:
2 g' h+ A+ P* B
# F4 W7 S# H6 y; h/ y  d7 h20.假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为
A.(rear-length+m+1)％m
B.(rear-length+m)％m
+ B/ e& @  s+ t, C0 tC.(rear-length+m-1)％m
: O- h: W1 @, ?8 c; y/ rD.(rear-length)％m
资料:

0 E/ O. E. k! t! w5 G5 C: f; I
  n9 n% _. u- w! f, ~# Q# A  i
% V0 j6 `8 r! C5 V! q# M
' k) x9 e4 }! s' P% ^0 @
% p9 H- X  A3 j8 n0 z