东大19秋学期《数据结构Ⅱ》在线平时作业2（参考）

admin

【奥鹏】[东北大学]19秋学期《数据结构Ⅱ》在线平时作业2
' H5 ~% r  X3 C  i6 M  \: W试卷总分:100    得分:100
第1题,数据的四种基本存储结构是指
A、顺序存储结构、索引存储结构、直接存储结构、倒排存储结构
B、顺序存储结构、索引存储结构、链式存储结构、散列存储结构
" X' [& o6 j. C( L% \C、顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构
D、顺序存储结构、链式存储结构、树型存储结构、图型存储结构
正确资料:
" U2 I' |  S" F1 e# z; K. k
. }6 s' D* `; J0 \, f; J
第2题,若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是
3 }! J( z$ X! G! ~* qA、2，4，3，1，5，6
; M1 u9 A% d# aB、3，2，4，1，6，5
8 Y# W) f* \7 g& q) v0 ?C、4，3，2，1，5，6
( A* F; D! E0 I: g% l6 m5 X$ ?* [D、2，3，5，1，6，4
% v6 o% J3 W  S( k5 P正确资料:
, ?% I: E  O+ b0 r( o
! F5 f8 l% h7 G5 ]3 L0 J
: v$ X6 ^* M0 z0 a2 F第3题,有关二叉树下列说法正确的是
A、二叉树的度为2
3 S  G# {+ f) q' _+ `# p" F6 @! iB、一棵二叉树的度可以小于2
C、二叉树中至少有一个结点的度为2
D、二叉树中任何一个结点的度都为2
2 D( C# @5 c2 G6 E; {: \. |正确资料:
7 h0 ~5 K. I' _8 q, C6 v+ o7 Z
* b- w2 V) Q% B; C6 j
/ s7 B% W5 O; P. h1 M3 N- j+ {第4题,算法分析的目的是
A、辨别数据结构的合理性
B、评价算法的效率
& A  V' ?* N: T+ F. R) uC、研究算法中输入与输出的关系
( j% B/ G' ~/ b6 I0 c% FD、鉴别算法的可读性
正确资料:
# g4 S" k0 U( L3 C/ X( p3 U% H9 k( l
# \0 t5 A3 H" O& o( B
第5题,若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为
' u" p1 K8 H, `/ Z: kA、X的双亲
$ @2 ~' w- y' j0 a& K5 o) N3 EB、X的右子树中最左的结点
C、X的左子树中最右结点
* J5 W, ?9 G7 P1 {4 {  m% ^& LD、X的左子树中最右叶结点
正确资料:
: K5 M8 ~$ K2 e3 R9 h. Y. A$ W$ J: G
! ~  z5 t% r' t
( Y8 b& n1 r5 A. ?3 X第6题,在一个单链表中，已知q结点是p结点的前驱结点，若在q 和p之间插入结点s，则执行操作
A、s-next=p-next;p-next=s;
! _  |. ~1 u' @$ }& s6 FB、s-next=p; q-next=s
C、q-next=s;s-next=p;
D、p-next=s;s-next=q;
$ y4 W, O6 h3 T+ G3 w3 f1 f正确资料:


- Z1 p& {5 g2 i8 ~0 i2 q$ b第7题,已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为
$ s+ `1 ~2 T! U8 `( cA、0
B、1
0 o  _" t# V, K  J0 xC、48
D、49
正确资料:


2 K2 \4 d& q  o# w第8题,若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为
A、f,c,b
B、f,d,b
0 B3 r1 S2 ?. y  h! `0 k, kC、g,c,b
D、g,d,b
- b$ f1 Y  ?  E5 i+ C& l正确资料:


" Q9 g' w2 m0 R- N7 t第9题,对n个关键字的序列进行快速排序，平均情况下的空间复杂度为
9 _* L; C9 e% m' H! ]% nA、O(1)
B、O(logn)
! Y, W, `3 i+ w3 D- [  ?C、O(n)
D、O(n logn)
: R2 s( U: z9 ]# }4 H正确资料:
5 r* U" ~$ J' L( f" ?

+ }5 r% G0 M& C/ g( c& c8 ]9 i第10题,若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是
A、1234
B、4132
& V- B# U: C! z( YC、4231
D、4213
正确资料:

0 M, d% c- J- x) @  _
第11题,树的先根序列等同于与该树对应的二叉树的
: c( r( r; M' }8 l7 jA、先序序列
B、中序序列
C、后序序列
' p3 N& }  ^) V* O& N5 WD、层序序列
正确资料:
3 b% W8 ]7 G0 m) f

第12题,若vi, vj是有向图的一条边，则称
A、vi邻接于vj
& z% {: E& s, Q" fB、vj邻接于vi
C、vi和vj相互邻接
! b( y* F9 b% \; H9 R# @2 tD、vi与vj-不相邻接
正确资料:
* l$ q0 P$ {4 Z" A

第13题,已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
; q7 w& w: K3 t- v) [' iA、5
" e* w, j7 I) i6 A6 IB、6
' B8 P* t$ E  x5 o- n, S2 YC、16
3 _: B9 }$ d7 Q* F5 oD、17
正确资料:

& k1 |2 @. O1 s
) M5 B. s1 J7 M( s, W* s4 y; f第14题,一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
& _' K* J1 |1 E6 LA、O(n)
B、O(e)
C、O(n+e)
6 \& d$ e* a8 h# lD、O(n2)
# H" }% r" {' i正确资料:


8 o/ ?" Y( q+ n4 A% U第15题,导致栈上溢的操作是
A、栈满时执行的出栈
; q  l4 i" Q8 _1 Y2 oB、栈满时执行的入栈
( i+ z: A) P4 d1 U3 O0 SC、栈空时执行的出栈
% a& f7 S: K) G  qD、栈空时执行的入栈
正确资料:


5 z- s* d9 Q. m) B0 W5 A第16题,在下列存储形式中，哪一个不是树的存储形式
8 z; K: @5 }" k! r3 X7 T% E2 eA、双亲表示法
! S$ c  ]$ y6 |: M# XB、孩子链表表示法
C、孩子兄弟表示法
D、顺序存储表示法
正确资料:
. b' e( [  a9 \1 @( H
. t+ g1 I# a: @: a. y% |# X
第17题,文件中，主关键字能唯一标识
A、一个记录
B、一组记录
" \  _2 ^: o* zC、一个类型
4 t. W, f, Q2 r' @D、一个文件
% r* I& z# U7 K, \正确资料:
) C7 n' i- o. K+ c

7 Q( i7 V2 k9 `- L第18题,下面的说法中正确的是    (1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。    (2)按二叉树定义，具有三个节点的二叉树共有6种。
A、(1)，(2)
B、(1)
" k6 }0 [- _) |. u7 ~C、(2)
D、(1)，(2)都错
正确资料:
3 F5 s0 e; u0 m# A* L* O6 @% ~) c

0 `$ Y3 e( K: U! a8 _- T  b$ |第19题,设给定权值总数有n 个，其哈夫曼树的结点总数为
1 b: d. y. a) }: LA、不确定
/ A( n1 z! o( Y5 T/ [B、2n
. ~7 o( t% w- JC、2n+1
D、2n-1
/ R. d9 W# G3 g9 {$ o正确资料:
# h9 v2 @& b; E: q' T" m4 k
( w) }" S6 z+ _
第20题,已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t  到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到
( s+ U+ f2 w6 {+ x# F3 V& ]A、P=″SCIENCE″
B、P=″STUDY″
C、S=″SCIENCE″
- Y7 ]+ [: e# ]+ ZD、S=″STUDY″
- y' b" R7 I/ |* y& {正确资料:
. Y! d9 S0 \9 |) m3 x. V/ ~# m5 L