东北师范《数据结构》2022年春学期在线作业2答卷

admin

数据结构19春在线作业2-0004
" J5 |6 p: v7 c3 E% b' {试卷总分:100  得分:100
一、单选题 (共 20 道试题,共 60 分)
1.递归过程的实现需用到 ( )。
A.线性表
+ S8 I/ p8 h9 T+ XB.链表
C.栈
2 b5 W% b6 V( f! [D.队列
正确资料

. z. ?6 n6 H; j, S/ S" o$ ^2.在下列情况中，可称为二叉树的是 ( )。
A.每个结点至多有两棵子树的树
B.哈夫曼树
. ^  s! Z( g$ N% J& pC.每个结点至多有两棵子树的有序树
D.每个结点只有一棵右子树
$ _+ w7 W, R3 W: d. V$ e正确资料:

3.经过下列栈的操作后，GetTop(ST)的值是 ( )。InitStack(ST); push(ST,'a'); push(ST,'b'); pop(ST,x);
A.a
B.b
C.1
D.2
正确资料:

; V& Z+ ^# O7 e& l- N! `2 _6 X4.若要求尽可能快地对序列进行稳定的排序，则应选 () 。
0 u  _! L+ y  V1 U, B8 m7 ^. xA.快速排序
B.归并排序
( e# C* l  \) z6 BC.起泡排序
1 |$ [! s* p* ?% S7 ^D.希尔排序
正确资料:
8 ~5 m$ V9 q7 u7 w: ]
% b, k/ z0 g5 b" d5.一个算法应该是（）。
8 r8 p3 [0 v4 cA.程序
: R! y. f0 a( H* IB.问题求解步骤的描述
  }. b( Y( a: K2 Z8 a- F9 `C.要满足五个基本特性
* i5 b2 H7 c9 JD.A和C
: @/ {; F) s  [3 d. F. d7 P正确资料:

8 l* _* R' m. o8 d4 N; |7 l8 O8 z/ Z" ]6.判断线索二叉树中某结点p有左子女的条件是 ( )。
  C/ G  y. u$ N/ G! S% h! V. B$ [7 zA.p ! = NULL
1 d- v( P0 ]7 QB.p->lchild ! = NULL
C.p->ltag = = 0
8 r+ p3 ?: q0 [D.p->ltag = = 1
正确资料
- G( i; u/ q# c
/ o, |, S: N: r, U4 e0 q7.二叉树在中序线索化后，仍不能有效求解的问题是 ( )。
6 s1 ?; H, e+ |A.求指定结点的前序后继
B.求指定结点的中序前驱
- \- z2 L; s4 p7 m2 `C.求指定结点的中序后继
" v' p/ ^1 q( K+ I! RD.求指定结点的后序后继
正确资料来自谋学网（www.mouxue.com）
% @4 @/ I, w1 s' p* p, J. v- _% ?
- G' h4 g  _; I# `8.顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。
A.附加文件
, I7 ~% ^% g3 i5 G2 `" l! X5 W+ P5 kB.按关键字大小排序
C.按记录输入先后排序
D.连续排序
0 r0 P4 ?) n8 q  n1 A7 p2 E" R正确资料:
# F9 f% B# K7 p: Y/ U' Z' N% p
9.广义表A=(a, b, ( c, d ) , (e，( f , g ) ) )，则式子head ( tail ( head ( tail ( tail ( A ) ) ) ) )的值为 ()。
A.( g )
B.( d )
; y# J9 c. Z' u  M% e& G  f3 MC.c
9 ~2 u* \' J5 H* CD.d
正确资料来自谋学网（www.mouxue.com）

0 v  _" a! p# M; g0 ~- l10.( ) 的遍历仍需要栈的支持。
A.前序线索二叉树
B.中序线索二叉树
C.后序线索二叉树
D.前三种均需要
9 u$ E3 X  |' ]& n, w0 Q正确资料
% }) N5 h4 j8 o& J0 [0 x
11.线索二叉树是一种 ( ) 结构。
A.逻辑
( g" L0 ]) w" _+ u2 x, TB.物理
0 J! \+ I0 v$ @4 ]3 M# y; ZC.逻辑和存储
2 @9 E- Y2 P, @7 K# c* yD.线性
正确资料:

12.有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是 () 。
A.60
B.66
C.18000
D.33
3 N( P6 y1 G* T% @$ }正确资料:

# w1 P! M: o7 L# J13.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。
* U( C5 f" t; _# X& UA.堆排序＜快速排序＜归并排序
" E# u& ^- |3 vB.堆排序＜归并排序＜快速排序
# }/ R" h: T: E$ XC.堆排序＞归并排序＞快速排序
D.堆排序＞快速排序＞归并排序
正确资料:

14.下列说法不正确的是 ()。
; @8 o9 ]" L+ Y- r8 p# BA.图的遍历是从给定的源点出发每个顶点仅被访问一次
5 s$ N% Y* m& r7 q0 wB.遍历的基本方法有两种：深度优先遍历和广度优先遍历
C.图的深度优先遍历不适用于有向图
D.图的深度优先遍历是一个递归过程
  Z: ^+ ^$ D9 g% X) b" v. o正确资料
0 \$ F$ l" U$ p& T" f6 A
3 r5 t2 j3 w9 i2 L3 D15.在一个图中，所有顶点的度数之和等于图的边数的几倍 ()。
( l- }# P4 t# P- jA.1/2
B.1
C.2
D.4
正确资料

8 E% e6 i) I& \3 c16.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行 ( )。
  e7 ?1 l4 p  y( c8 rA.p->next = s; s->next = q;
B.s->next = p->next; p->next = s;
2 U/ G8 X0 }/ Y) P( eC.p->next = s->next; s->next = p;
, S! b2 e2 c3 g' ~; nD.q->next = s; s->next = p;
正确资料来自谋学网（www.mouxue.com）

1 z, ]% `3 c8 S$ ^! Z1 ?17.在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是 ()。
A.O(log2n )
B.O( 1 )
& D& i8 |2 s4 l/ i0 HC.O(n )
D.O(nlog2n )
正确资料:

! P3 d9 B8 x; |/ \; W2 {2 ~18.已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为LOC(a0)，则第i个结点的地址为 ( )。
! ~4 A: G6 b4 q0 O) p4 ~, f& QA.LOC(a0)+(i-1)*c
B.LOC(a0)+i*c
C.LOC(a0)-i*c
% Z; h  S8 Q5 p4 D- ?8 C. AD.LOC(a0)+(i+1)*c
正确资料:
' u( A- p! w$ N% n8 S5 y3 Q3 w, d
19.分块查找要求表中的结点 ()。
" t9 t4 r! b  s( RA.全部无序
8 p0 Z. W+ Z7 d8 |( n  v2 V$ H  GB.块之间无序
C.全部有序
. X% d; e' ^6 ?+ B2 ^D.块之间有序
! F/ O- F' q) Y6 Z# G) d2 s正确资料来自谋学网（www.mouxue.com）
$ Q* u9 z- u2 t2 Q1 x: B% N
* C: w, L: W, i( Z2 e8 o20.下面关于串的叙述中，哪一个是不正确的? ( )
A.串是字符的有限序列
B.空串是由空格构成的串
1 {7 Q) q) P* l. t: tC.模式匹配是串的一种重要运算
! k8 w0 N4 p/ w1 zD.串既可以采用顺序存储，也可以采用链式存储
3 K+ D' R- P& G5 I) o1 ~) ~正确资料:

( E! _& r$ b3 m6 j& @9 d二、资料来源：谋学网（www.mouxue.com） (共 20 道试题,共 40 分)
: m* Z7 Z5 w3 v, L0 u9 a) v& t2 L21.二叉树按某种次序线索化后，任一结点均有指向其前序结点和后继结点的线索。
& x/ [7 N; U/ K' s1 H* c  E资料:错误

22.在执行某个排序算法过程中，出现了排序码朝着它最终排序位置相反的方向移动，则该算法是不稳定的。
资料:错误

7 v/ v  J4 L# I0 m: p: r: I23.非空的二叉树一定满足：某结点若有左子女，则其中序前驱一定没有右子女。
资料:正确

24.数组是同类型值的集合。
" d9 ^* T/ v, U; O' \) u8 w资料:错误

0 |, Z, [5 M: q& m- j6 m! @25.用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
资料:正确
0 z& W3 O% h$ P7 u
' Q3 A# q5 {, Z7 S$ t7 u26.链表中的表头指针与表头结点起到相同的作用。
资料:错误

+ N& X6 n. e* \- ~27.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。
资料:正确
) E+ k  U  C( |6 V0 u
- k, G$ Y( C  V4 a( n28.一个有向图的邻接表和逆邻接表中结点的个数可能不等。
资料:错误

1 [1 k' P- _. {$ |# X% z29.对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。
资料:正确

- A4 H$ d, m; A9 [30.任何无向图都存在生成树。
8 }7 c0 q) T! D) I5 T+ X' n资料:错误
- G$ W/ b5 u5 s2 W& F5 m% V+ D7 U0 }
31.在完全二叉树中，若一个结点没有左子女，则它必是树叶。
资料:正确
: M$ m* N: r- Z
32.链表中的表头结点仅起到标识的作用。
  t! b( y7 ~0 c6 @. t资料:错误
: A2 [2 ?* d$ Y! x% Z& S1 h
33.将一棵树转成二叉树，根结点没有右子树。
' f- V  U. n' p  y+ q4 {5 `0 O3 V2 V资料:正确
, K0 V6 F/ F- ?2 Z- t9 O5 l: r' N
! d4 q& p' K' ^34.连通分量是无向图中的极大连通子图。
) G) [. a% Y4 {, u* a1 b3 P, {资料:正确

2 o) P. \7 u" ~6 S2 `. n35.所谓取广义表的表尾就是返回广义表中最后一个元素。
: q4 S6 l0 ?1 _资料:错误

/ @' I+ s$ h5 e! x( p* u7 m36.需要借助于一个栈来实现DFS算法。
/ P4 _7 x. h  q资料:正确
# j* E$ z( W( c/ F4 F
6 N3 u% |( a! {7 Z2 [# [37.必须把一般的树转换成二叉树后才能进行存储。
0 T% m% h/ P% T4 h! N资料:错误
  R2 P: z0 d2 E% G5 G: M6 g' ]
38.对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。
5 \& v( J6 W: f& g6 T$ j资料:正确
7 v6 o* k9 |) F  X9 b! \" V
39.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。
& O: W' S' o5 d% ?' ]: }. g资料:正确
: |4 u4 V) f9 v
40.二维以上的数组其实是一种特殊的广义表。
6 l! G/ s# F; a7 w( D6 q资料:正确
: b. {! l8 V3 q$ t$ {" ^



" w" l! z% A: M/ p( {* Q8 |


/ T& `; B1 C3 u+ F- B+ G( M0 n9 ?( A
, ~( s2 ~6 y- ]8 n

3 J9 y# Z' \2 ]: q. n% p  R

& J; E7 ^1 l- a/ {! C! H