东北师范大学《数据结构》2023年秋学期在线作业2

admin

资料来源：谋学网（www.mouxue.com）数据结构-[东北师范大学]《数据结构》2023年秋学期在线作业2
4 \) @6 p) o' J) s/ ~试卷总分:100    得分:100
7 r, S. W6 Y/ q% L第1题,递归过程的实现需用到 ( )。
/ H' q0 J1 ^1 p0 EA、线性表
, L' V/ B, t/ W5 Z. uB、链表
" y" [5 Y9 w) tC、栈
D、队列
& \: p1 u! C7 C: `3 X7 V$ `2 O. ?正确答案:


3 k  i# M4 o! ~) f3 v: p, y  r第2题,在下列情况中，可称为二叉树的是 ( )。
A、每个结点至多有两棵子树的树
; P1 ]5 d( A1 I' n" f" WB、哈夫曼树
C、每个结点至多有两棵子树的有序树
D、每个结点只有一棵右子树
正确答案:


第3题,经过下列栈的操作后，GetTop(ST)的值是 ( )。InitStack(ST); push(ST,'a'); push(ST,'b'); pop(ST,x);
A、a
. f( R& J+ H* H0 {B、b
# U( f( H9 K; H; o8 qC、1
D、2
正确答案:A
! W: b# j- L0 c2 H& h. ?
% J" V# I+ N( f" x. {, p
/ v/ ^# d% @& T0 d' q第4题,若要求尽可能快地对序列进行稳定的排序，则应选 () 。
* X9 `6 j! v" k: {, C0 AA、快速排序
B、归并排序
4 M# U" w- _6 K- x- S9 }  vC、起泡排序
6 W" A& W( N5 M1 I) J6 T& dD、希尔排序
正确答案:
6 e6 x9 C) G: v

资料来源：谋学网（www.mouxue.com）,一个算法应该是（）。
! E, G2 L, ]# ?' H4 u/ JA、程序
B、问题求解步骤的描述
% J% \5 G  E! xC、要满足五个基本特性
$ l; ^+ c0 n% C0 X  ?D、A和C
正确答案:
) W1 r' m- N# u% N9 y

第6题,判断线索二叉树中某结点p有左子女的条件是 ( )。
A、p ! = NULL
9 _0 e, \  s5 }: Q1 D4 [- h3 HB、p-lchild ! = NULL
C、p-ltag = = 0
D、p-ltag = = 1
0 r  A2 w3 J, D8 Z/ b! [正确答案:
2 Z8 Z' Z0 ~- W

第7题,二叉树在中序线索化后，仍不能有效求解的问题是 ( )。
A、求指定结点的前序后继
B、求指定结点的中序前驱
) v# O& S- ^# ZC、求指定结点的中序后继
D、求指定结点的后序后继
正确答案:
* u% D7 X: n  e* k1 S4 l

第8题,顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。
, f6 {7 [9 Q0 ]1 U* |& UA、附加文件
/ `, D9 R* g, I+ t6 T/ l2 E1 KB、按关键字大小排序
& l8 q5 j# c& }, z9 zC、按记录输入先后排序
$ v- l( T/ y; F! N1 m3 H/ |6 `1 DD、连续排序
正确答案:A
6 p) S; E0 {" f

第9题,广义表A=(a, b, ( c, d ) , (e，( f , g ) ) )，则式子head ( tail ( head ( tail ( tail ( A ) ) ) ) )的值为 ()。
1 n* {3 @1 m9 B3 E. sA、( g )
B、( d )
/ r! y; I; i% ]/ s( Z) v9 zC、c
4 j+ D+ O: K) _2 c8 fD、d
* ^* R6 R3 ~+ o; o% o正确答案:
, R- z( i  j3 Z8 t  h) \; q, N
5 q; {4 X2 `4 s$ e6 P- v
: H# k' A% u' d6 y. q! U/ X# ?资料来源：谋学网（www.mouxue.com）,( ) 的遍历仍需要栈的支持。
A、前序线索二叉树
& E! U: B5 ?+ m. @# CB、中序线索二叉树
9 K/ I; |( c0 q. i, s& ZC、后序线索二叉树
D、前三种均需要
" R6 q$ A! ?6 S. L9 G# E正确答案:
, l2 u" h9 j7 W& v. X; R: B9 J
4 B4 f! i, \& [% s
! h0 [" P  s5 {  b第11题,线索二叉树是一种 ( ) 结构。
8 X6 P/ [- Q* A- n3 s" m9 N; [' VA、逻辑
- i! B! X7 F5 }6 d0 VB、物理
" K9 E# m* G, M/ u6 Y& S1 JC、逻辑和存储
0 Z% F4 b5 v' s# D7 e# RD、线性
2 @+ q" {& h% o- X" m! k5 {正确答案:

- m9 K) {5 @0 U+ L# A
) ]5 e9 w5 b* d* V资料来源：谋学网（www.mouxue.com）,有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是 () 。
A、60
7 T0 U7 Q/ [% J) Z7 oB、66
0 U) d  n$ V. W, s7 Q+ LC、18000
! W& c$ T! J( R/ S7 j3 MD、33
正确答案:A

% ^6 d) j/ c" y, f
第13题,就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。
) K% \8 [4 c6 qA、堆排序＜快速排序＜归并排序
( J3 P: v6 a9 Y' \+ Y3 {- AB、堆排序＜归并排序＜快速排序
C、堆排序＞归并排序＞快速排序
D、堆排序＞快速排序＞归并排序
正确答案:A
5 a- A* O4 H4 a6 n

7 D0 M8 a5 p3 l( B4 [第14题,下列说法不正确的是 ()。
% V- b2 ]% `* Y8 m6 IA、图的遍历是从给定的源点出发每个顶点仅被访问一次
" e/ x, X& D$ b' z9 zB、遍历的基本方法有两种：深度优先遍历和广度优先遍历
, u1 t. F, D" g& ~6 e9 C% j+ F: S1 SC、图的深度优先遍历不适用于有向图
D、图的深度优先遍历是一个递归过程
正确答案:


) ]( p- E9 ?' x/ m7 g4 u, ~: o资料来源：谋学网（www.mouxue.com）,在一个图中，所有顶点的度数之和等于图的边数的几倍 ()。
9 M* s/ I- p. {( s8 k/ u$ qA、1/2
. {# i: W9 x' v/ L4 rB、1
. S) q6 m% E* I3 Z3 K& PC、2
D、4
正确答案:

6 C. \- ?) p7 a/ D6 o9 H. O% \, }
第16题,在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行 ( )。
% ^; o/ r* _! MA、p-next = s; s-next = q;
8 X- Q, E: U. B: O# }( BB、s-next = p-next; p-next = s;
C、p-next = s-next; s-next = p;
( \+ j7 h' v4 ~( pD、q-next = s; s-next = p;
* Q# |0 S6 _$ O& ]: _" c" b正确答案:

! q( }4 G5 j* i
/ \: r" |! P' f" I3 h第17题,在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是 ()。
A、O(log2n )
B、O( 1 )
C、O(n )
7 S6 K( N9 A; B  t7 Y' ED、O(nlog2n )
9 e* V4 P$ f3 d6 n% v' ]正确答案:

! O- u* M4 N9 e+ X7 U6 d
第18题,已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为LOC(a0)，则第i个结点的地址为 ( )。
A、LOC(a0)+(i-1)*c
$ z6 m( x$ U3 H) {; l& _2 xB、LOC(a0)+i*c
C、LOC(a0)-i*c
- m' P  N  Z  L" ]3 ^D、LOC(a0)+(i+1)*c
6 ^" E; n  o% t, b正确答案:

. d7 f& K8 z" W: p. P
第19题,分块查找要求表中的结点 ()。
A、全部无序
6 w8 t# ~$ v; B! RB、块之间无序
C、全部有序
. Q4 I2 [" g& k" s. Y0 oD、块之间有序
正确答案:
6 u2 T, \5 ?) N" ]
9 ^* E, E7 q) ]3 Q6 ], ^( k
资料来源：谋学网（www.mouxue.com）,下面关于串的叙述中，哪一个是不正确的? ( )
A、串是字符的有限序列
B、空串是由空格构成的串
C、模式匹配是串的一种重要运算
D、串既可以采用顺序存储，也可以采用链式存储
7 t! R: o, i0 H正确答案:
: ~/ \" @: ?, i/ G- Z7 O

第21题,二叉树按某种次序线索化后，任一结点均有指向其前序结点和后继结点的线索。
; v) V; U6 N8 LA、错误
/ n+ U$ T% [; n2 u" KB、正确
5 f$ }) v0 a4 ]$ x正确答案:A


第22题,在执行某个排序算法过程中，出现了排序码朝着它最终排序位置相反的方向移动，则该算法是不稳定的。
A、错误
B、正确
" t3 G8 }& v6 f$ `3 A正确答案:A
, m: M7 V  i4 t. A/ E: T( e! E8 ~  I
+ ~6 x8 e1 f6 o" |7 \) u0 w5 x
- K% @; f# A( L: t1 L第23题,非空的二叉树一定满足：某结点若有左子女，则其中序前驱一定没有右子女。
0 j0 b4 H% L$ j2 {  Q  eA、错误
B、正确
正确答案:

/ T) c1 F% b2 u* c
4 W# w6 C" A6 J! \第24题,数组是同类型值的集合。
A、错误
B、正确
正确答案:A
& b: q4 F# T5 Z% |4 x6 p
9 ]7 m: L! ^; P$ d1 n8 A% {2 i
资料来源：谋学网（www.mouxue.com）,用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
A、错误
& y& r6 y& U8 VB、正确
正确答案:
1 f1 n$ ^0 S# ]% z' f* ]  u
5 T! z& F' p. f
第26题,链表中的表头指针与表头结点起到相同的作用。
0 ?3 W6 ~; ^1 |8 aA、错误
$ ~$ y9 l6 b" j$ ^B、正确
$ o6 q$ O1 R0 ~# B  J, n# u* ~- r正确答案:A

0 h& R. j' ?: a. K9 q* d1 @
4 F! X# J* @  p4 l5 }第27题,栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。
1 h( K8 }' O' \1 r5 q) kA、错误
& Z% A6 ^4 w3 R$ p  B/ U6 J1 cB、正确
正确答案:
5 P4 H3 m( W$ I- g0 j

6 e/ o& d3 Z, X: y* Q' W: s6 A" j第28题,一个有向图的邻接表和逆邻接表中结点的个数可能不等。
A、错误
B、正确
. A1 b4 j' H* o. {$ ~正确答案:A

: G9 g9 _6 D  S2 e1 e# \& z' [
第29题,对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。
A、错误
2 I/ m& U  ^) [B、正确
3 q6 L( H4 I- p8 g  M1 z2 S: J. S正确答案:
* A/ y. A5 n) @" d, n& a0 z

资料来源：谋学网（www.mouxue.com）,任何无向图都存在生成树。
8 [1 w# }) n% J' R5 g! {6 BA、错误
6 g8 _" \/ v# K: x/ |( ^B、正确
正确答案:A
5 P* P& i' F* e* C% s9 L& J6 J
- @- }( x: V# _$ H- o- d
第31题,在完全二叉树中，若一个结点没有左子女，则它必是树叶。
A、错误
5 Y. M9 n# R, a/ V. oB、正确
正确答案:
% O2 A6 G! @) h, q1 N5 c! S6 b" V

第32题,链表中的表头结点仅起到标识的作用。
  W% u$ h6 i2 y- s/ nA、错误
B、正确
正确答案:A

1 [3 z$ B. C1 ?; A$ v4 S
4 g- x- o' V& n) D$ N8 L第33题,将一棵树转成二叉树，根结点没有右子树。
8 l' J, d. v) j! K% UA、错误
B、正确
2 f. s: q* g* @1 d正确答案:

$ Q# }* Q  |$ x: U7 X. r5 k
! g7 d; |8 y3 u1 V+ n% @; C- X2 e第34题,连通分量是无向图中的极大连通子图。
A、错误
B、正确
正确答案:

) F' O1 I7 g2 d/ T) M
第35题,所谓取广义表的表尾就是返回广义表中最后一个元素。
7 I: [$ w2 O9 NA、错误
4 P  ^5 {# w7 t& P4 Z0 [% MB、正确
正确答案:A
- E) Q6 E9 E" d- ^: N

  @% r. |( i# @# F第36题,需要借助于一个栈来实现DFS算法。
A、错误
7 M7 K* o2 y: j5 f% P3 t0 z$ }B、正确
正确答案:


第37题,必须把一般的树转换成二叉树后才能进行存储。
' c; e0 C+ [7 T) _) K& ?A、错误
B、正确
+ M: K/ `/ C% W) x/ c6 w/ T正确答案:A
: B0 e. Z& l- V/ f

1 s) z( D9 q; z7 ^$ h. v) Z4 p第38题,对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。
. ]$ t. w4 h! q7 R- g; u1 LA、错误
- a# d  ^% f7 }1 L& F/ ]B、正确
- W( l* D. @8 w# y" U( ?8 d3 C2 M3 _正确答案:
+ j/ b: v  i; s0 L. w" ^

第39题,后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。
# G" |, a. Y5 D& s2 r- XA、错误
& d  v. c0 i- m* Y( d. L  JB、正确
正确答案:
- Y8 Q% x. B7 j6 F8 j: P0 c

2 w1 ]! S' i( l- _/ t+ h* a* j第40题,二维以上的数组其实是一种特殊的广义表。
A、错误
& r# a1 E( p& ^  K- A, Z  x( bB、正确
正确答案:
, |' j+ f& H1 ~0 p. m1 U

* N9 |6 n- `; b  }) g7 P+ X: k
, e: w4 M% w: C' q. M6 j: N

$ x+ X6 g' C( i  d0 F* S$ P
& N& q( |/ L0 O/ T! _7 |

9 H# v# |3 G* u: c- |% n6 ]
) T: p# n% b9 h; S1 L+ {
, X/ W% G& _( |. f; k
; w& s. K' Y4 S, S/ m8 \
9 O! q$ |. ]3 b9 x( O  J* X
# r- l+ r# P2 Q. S% I; W- l
& n. `3 P% h7 a; P& R

ilqklvov

值得信赖

果てしない夢

谋学网老师确实厉害！

a33885711

每学期都来