东北师范《数据结构》》21秋学期在线作业2答卷

admin

数据结构19春在线作业2-0004
' Y- X8 B1 R; `8 u试卷总分:100  得分:100
! ^; @2 |3 C+ j一、单选题 (共 20 道试题,共 60 分)
6 `3 [' O/ y3 c# I1.递归过程的实现需用到 ( )。
A.线性表
, A2 h. X" }7 Y2 F7 q2 tB.链表
$ L) O- o" N9 b' F& r% X9 G2 ~5 a: a4 ZC.栈
, {; g6 }2 K- ~5 e2 G+ \# i8 ~+ BD.队列
  E5 V' T' R4 @6 |正确资料

2 u" y+ a" n1 p2.在下列情况中，可称为二叉树的是 ( )。
A.每个结点至多有两棵子树的树
B.哈夫曼树
C.每个结点至多有两棵子树的有序树
D.每个结点只有一棵右子树
$ y9 ?+ u7 \2 _7 |" o3 K2 E正确资料:
+ o7 O( z- ?' N1 k" [0 N8 I) A
/ v# m+ k1 u9 _* K$ W4 k& g3.经过下列栈的操作后，GetTop(ST)的值是 ( )。InitStack(ST); push(ST,'a'); push(ST,'b'); pop(ST,x);
* h! ]/ i/ G, P4 ]+ QA.a
B.b
C.1
9 O" J/ {0 W& DD.2
; d. r9 ?; x$ B  X正确资料:

4.若要求尽可能快地对序列进行稳定的排序，则应选 () 。
A.快速排序
B.归并排序
2 ^5 l* ~. X9 u; }" ?) Q5 ~9 Y2 sC.起泡排序
/ g6 V$ K' B9 e6 t" E0 F8 o) aD.希尔排序
- Q  l' V5 v4 |, q1 ]& f正确资料:
8 T; ]: ~" r- n: N; K( G
3 l# o9 {/ ?6 H5.一个算法应该是（）。
9 [( I9 S* l8 g; dA.程序
% [; J$ u- H9 ~3 a8 D# hB.问题求解步骤的描述
. p* }2 w/ X4 c, B" hC.要满足五个基本特性
D.A和C
正确资料:

8 ~. y# \9 }. i3 G; m6.判断线索二叉树中某结点p有左子女的条件是 ( )。
/ v" y; }( g7 QA.p ! = NULL
" G( p7 P4 ]* }5 W2 VB.p->lchild ! = NULL
C.p->ltag = = 0
D.p->ltag = = 1
8 x' G, \! @2 \) Q正确资料

7.二叉树在中序线索化后，仍不能有效求解的问题是 ( )。
4 J( D4 L+ b! O. y  ZA.求指定结点的前序后继
B.求指定结点的中序前驱
C.求指定结点的中序后继
0 j4 w) D- O) jD.求指定结点的后序后继
正确资料来自谋学网（www.mouxue.com）

- b! J+ e. {, G8.顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。
A.附加文件
B.按关键字大小排序
( C. ?* l2 l9 I) AC.按记录输入先后排序
, h# [8 {7 v$ ^D.连续排序
0 j, d% \$ M! B0 Z7 y正确资料:
- N. d' w( q) \" B8 a
- g1 N/ G+ q: k* `) r9.广义表A=(a, b, ( c, d ) , (e，( f , g ) ) )，则式子head ( tail ( head ( tail ( tail ( A ) ) ) ) )的值为 ()。
* M. q# I3 P! p6 Q( J2 D5 vA.( g )
B.( d )
C.c
D.d
% U8 z0 h5 I+ ]9 t" x# q正确资料来自谋学网（www.mouxue.com）

10.( ) 的遍历仍需要栈的支持。
4 c) |# S1 s4 n# U+ Q; C7 J1 ]( CA.前序线索二叉树
B.中序线索二叉树
C.后序线索二叉树
5 i, ]( K5 |( }" c, ]: PD.前三种均需要
. D2 ]+ U3 ^. d' q- `9 v正确资料
% J4 j; o1 Z8 u- U: A* j
+ ]7 M: B, n9 J; P4 A11.线索二叉树是一种 ( ) 结构。
+ J2 I/ E0 w3 i9 ?9 v  [* E9 X5 J7 dA.逻辑
B.物理
! Y2 T) h. T6 T2 _C.逻辑和存储
D.线性
正确资料:

12.有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是 () 。
6 {3 \6 T7 l! w- LA.60
B.66
C.18000
D.33
2 d) q$ U# I) P; s# f* M正确资料:

13.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。
A.堆排序＜快速排序＜归并排序
B.堆排序＜归并排序＜快速排序
C.堆排序＞归并排序＞快速排序
D.堆排序＞快速排序＞归并排序
1 p( `# u* A* \. w: L( A" r+ _正确资料:
# e5 s* \+ D0 s. U! v
14.下列说法不正确的是 ()。
& x* Z' w6 q) f$ EA.图的遍历是从给定的源点出发每个顶点仅被访问一次
B.遍历的基本方法有两种：深度优先遍历和广度优先遍历
0 n6 y5 U* \9 F; a1 E! f# V8 Z3 |C.图的深度优先遍历不适用于有向图
D.图的深度优先遍历是一个递归过程
正确资料
- c3 ?0 }8 U7 l2 D+ z
15.在一个图中，所有顶点的度数之和等于图的边数的几倍 ()。
A.1/2
B.1
C.2
D.4
正确资料

# X$ H& l' x. _# T8 t16.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行 ( )。
4 L; }5 f5 V4 Q0 _% q* H  BA.p->next = s; s->next = q;
B.s->next = p->next; p->next = s;
C.p->next = s->next; s->next = p;
D.q->next = s; s->next = p;
  _: D4 q0 a; o6 w5 I. }正确资料来自谋学网（www.mouxue.com）

1 G, q# L( b3 Y  Q" r/ q17.在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是 ()。
& d% b$ Y9 b& R2 G9 J+ qA.O(log2n )
B.O( 1 )
4 D6 \5 B6 T# `# S$ y5 W" w$ TC.O(n )
D.O(nlog2n )
正确资料:
6 l1 S& A7 u+ Z# [  R) a
18.已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为LOC(a0)，则第i个结点的地址为 ( )。
: T/ j8 F' Y$ s; P- I. kA.LOC(a0)+(i-1)*c
7 B( R) M; }* B. n7 T9 X3 KB.LOC(a0)+i*c
C.LOC(a0)-i*c
) V5 y+ E* Z2 xD.LOC(a0)+(i+1)*c
! n, w% R" L. V3 Q正确资料:

19.分块查找要求表中的结点 ()。
$ b+ A* V' Z: q5 p! ?A.全部无序
B.块之间无序
C.全部有序
. t& F/ O0 A/ U3 b2 j0 {D.块之间有序
4 q3 a% @+ h0 Y; d正确资料来自谋学网（www.mouxue.com）
: ~. Y! c. Q' k) _# h
, y' o, M4 e7 V% f' C# s  S20.下面关于串的叙述中，哪一个是不正确的? ( )
A.串是字符的有限序列
B.空串是由空格构成的串
C.模式匹配是串的一种重要运算
D.串既可以采用顺序存储，也可以采用链式存储
- l; W# d' }' j. D4 \1 \. }正确资料:

4 x/ D! r5 w9 N6 Z二、资料来源：谋学网（www.mouxue.com） (共 20 道试题,共 40 分)
21.二叉树按某种次序线索化后，任一结点均有指向其前序结点和后继结点的线索。
资料:错误
- y$ m6 o! r1 o  y# G: V. a& ?8 y
; y8 S7 V# i5 s1 c% u. H, ~22.在执行某个排序算法过程中，出现了排序码朝着它最终排序位置相反的方向移动，则该算法是不稳定的。
资料:错误

0 a: |- K( T: B' S* _& Z23.非空的二叉树一定满足：某结点若有左子女，则其中序前驱一定没有右子女。
) S6 n+ _/ z& K5 J& R  f资料:正确

24.数组是同类型值的集合。
资料:错误
6 t7 ]# `& j$ p: Y% b+ m0 w
% P: f) b) q0 i# U3 c$ m* f' d25.用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
资料:正确

6 A5 t. Y; H; M# U; Z: T26.链表中的表头指针与表头结点起到相同的作用。
3 ~. E7 c) K+ M" G& U; {; o- p资料:错误
% w, a' u9 m1 y
27.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。
资料:正确
" d: y' }. X! y. M6 [
28.一个有向图的邻接表和逆邻接表中结点的个数可能不等。
) T# v" s2 x" }! q5 v1 Q资料:错误
; h) V6 G! H! q4 e! c
# ~% N0 J& E9 X$ ]1 S9 K29.对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。
资料:正确
1 Z. _* I# F( n# u
3 ?! [" o# |( O" I0 o. Y& y1 S  a30.任何无向图都存在生成树。
资料:错误

( ?" p7 o% ?0 e/ r31.在完全二叉树中，若一个结点没有左子女，则它必是树叶。
资料:正确

32.链表中的表头结点仅起到标识的作用。
. [) f$ R2 o& E6 e6 A资料:错误
, {, a+ }! ]: k. c+ M) s
33.将一棵树转成二叉树，根结点没有右子树。
1 o7 j& Z2 `0 R; g+ T资料:正确
. S& d  j; b1 @( _
, a# ]& @  k0 ]34.连通分量是无向图中的极大连通子图。
! k& c7 [6 B" B# _8 P资料:正确

35.所谓取广义表的表尾就是返回广义表中最后一个元素。
资料:错误

36.需要借助于一个栈来实现DFS算法。
资料:正确

0 S& w" @; _7 j0 n6 H8 W: K37.必须把一般的树转换成二叉树后才能进行存储。
/ S& u7 W2 U% T& C5 U0 ^8 s资料:错误

38.对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。
6 G1 D: U7 P& T$ I9 q3 h8 t5 U资料:正确

0 H& M9 m& h, `5 P39.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。
资料:正确

40.二维以上的数组其实是一种特殊的广义表。
资料:正确
; l6 {1 b. H) n9 O$ `$ M' R

* \8 \: X( l7 @5 j; {( ?" w! s4 v

/ p3 l. M: R% p$ J1 f

5 z2 n3 s0 E  ]) Z1 U: ^1 E$ y* Q: [3 L
9 P- k: `- D0 B
9 P% S( l# c4 P  L- g