[东北师范大学]《数据结构》19秋在线作业21(100分）

admin

【奥鹏】[东北师范大学]数据结构19秋在线作业2
# v/ X' `: a* l试卷总分:100    得分:100
第1题,递归过程的实现需用到 ( )。
A、线性表
B、链表
# x6 k' |2 E/ E6 g7 \5 iC、栈
D、队列
正确资料:

* C2 r9 A5 {5 b8 y$ Z
第2题,在下列情况中，可称为二叉树的是 ( )。
A、每个结点至多有两棵子树的树
B、哈夫曼树
/ d7 z; q+ i8 o6 a+ j# LC、每个结点至多有两棵子树的有序树
D、每个结点只有一棵右子树
正确资料:


- i& T# C0 X" [' f第3题,经过下列栈的操作后，GetTop(ST)的值是 ( )。InitStack(ST); push(ST,'a'); push(ST,'b'); pop(ST,x);
A、a
6 \+ C1 S* B$ e: I( G4 GB、b
3 y  R# L, M4 X" oC、1
, s- u( I, O8 K3 l) Q7 h: ^D、2
' n' V0 |" r' c% Q4 z: j4 z正确资料:


* F( Q# J0 O9 C8 w3 |$ d2 N第4题,若要求尽可能快地对序列进行稳定的排序，则应选 () 。
0 q) X% G3 v9 z% p# u' g/ WA、快速排序
0 W; z$ `5 r' {B、归并排序
7 E. I7 Q/ h5 pC、起泡排序
, M( U, O7 o0 |5 i4 v. vD、希尔排序
正确资料:

9 U. L& b: c8 T# T& b  X
第5题,一个算法应该是（）。
* j; [8 I/ B) wA、程序
# J# q- R" h, @5 ~8 bB、问题求解步骤的描述
0 F2 s7 s5 L8 X; E, v. ~C、要满足五个基本特性
D、A和C
9 D, d- z& l$ \1 S$ o正确资料:


3 b$ V% u: |. Y: z% G第6题,判断线索二叉树中某结点p有左子女的条件是 ( )。
A、p ! = NULL
0 y. z2 J, Q" ?6 @3 dB、p-lchild ! = NULL
C、p-ltag = = 0
) A* Q$ P- T4 Q, H( G0 dD、p-ltag = = 1
正确资料:

7 m# Z" f; }- M9 N
  G6 _" f- s9 R7 t( F" O4 r第7题,二叉树在中序线索化后，仍不能有效求解的问题是 ( )。
/ l0 x- O- {: I* T& H* ~/ pA、求指定结点的前序后继
B、求指定结点的中序前驱
C、求指定结点的中序后继
0 m& M5 _, m3 x/ A8 C$ sD、求指定结点的后序后继
正确资料:
- o8 z+ y+ g- O
& e# k$ P/ Y2 ^0 `, {) A
8 N& v0 }6 F, d# a! }第8题,顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。
  H: V2 Q, o7 C3 I2 VA、附加文件
B、按关键字大小排序
5 q1 r, N& L6 q% v5 O* Q- Q* XC、按记录输入先后排序
# E& j2 r8 r' a8 _  }! l2 ID、连续排序
5 R. o8 Y2 ]% @3 v' s; K正确资料:
# U+ ^7 p" ?5 u# Q

# n& W/ s2 e! W5 {( N) I- |第9题,广义表A=(a, b, ( c, d ) , (e，( f , g ) ) )，则式子head ( tail ( head ( tail ( tail ( A ) ) ) ) )的值为 ()。
7 w1 f+ i! p3 u* xA、( g )
' `/ C- S/ w! CB、( d )
C、c
+ _# Y# ~/ ]$ hD、d
正确资料:
  U4 [. u% y0 Q% u

第10题,( ) 的遍历仍需要栈的支持。
A、前序线索二叉树
B、中序线索二叉树
C、后序线索二叉树
/ e. P$ ~. o6 m. ~8 MD、前三种均需要
正确资料:
1 A7 F5 o' m, L  z; \
3 h/ i: h- s/ P+ \/ h
/ _0 \0 E5 L4 s  q! @) _第11题,线索二叉树是一种 ( ) 结构。
9 r3 \, z1 s3 E" _. Z" ~0 NA、逻辑
B、物理
& R; @& `9 W1 ~- jC、逻辑和存储
8 f. e( K% I3 j$ rD、线性
正确资料:

, V- x2 v7 W, Y( `9 d7 _
第12题,有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是 () 。
' H0 z" l2 |% s% zA、60
B、66
; z6 c# Y- J9 B# A! m! {2 DC、18000
8 O2 z. u$ ^# e8 U* qD、33
3 O7 b, q( _6 H. _1 e9 r, c正确资料:
! v  w: k( D% e
4 z. S& D# q! m# e' W4 [! m
第13题,就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。
# Y+ ]: H. |+ p0 |# U' w, k; PA、堆排序＜快速排序＜归并排序
B、堆排序＜归并排序＜快速排序
C、堆排序＞归并排序＞快速排序
( w9 v( I3 F! p; a1 W7 rD、堆排序＞快速排序＞归并排序
; A* Q) h* a  ~  e  J/ S: Y正确资料:


第14题,下列说法不正确的是 ()。
+ b) k; E4 w) }* n  vA、图的遍历是从给定的源点出发每个顶点仅被访问一次
, _/ E' N8 Q& h* Z! I5 f0 j* vB、遍历的基本方法有两种：深度优先遍历和广度优先遍历
1 O8 Y% T4 W- D& B- C8 s0 _C、图的深度优先遍历不适用于有向图
D、图的深度优先遍历是一个递归过程
+ G. J' t3 ~8 s( r* X. s& ?# [4 ?正确资料:

, J7 F1 x* h( j2 z9 i  V* o
第15题,在一个图中，所有顶点的度数之和等于图的边数的几倍 ()。
A、1/2
0 Z- T8 _! [5 ~2 MB、1
9 k" T6 A! o+ U5 b5 ^/ NC、2
7 V. }3 x8 h& t) Y) TD、4
# Y" V) J1 [. G- H正确资料:

1 ^: f$ [7 V% k- T2 b
第16题,在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行 ( )。
A、p-next = s; s-next = q;
B、s-next = p-next; p-next = s;
# f& f/ R8 B  U1 d3 `% _* F" ~- oC、p-next = s-next; s-next = p;
D、q-next = s; s-next = p;
% g! b- W) l* @$ x' j正确资料:


6 E, U6 E7 h) }$ L第17题,在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是 ()。
8 N) `3 v0 ]- A6 o) NA、O(log2n )
5 m. r' v: b" i& [B、O( 1 )
C、O(n )
D、O(nlog2n )
! M7 q, V- j& s, I1 B正确资料:

2 O; @) x8 h5 e3 [) F0 f( }
第18题,已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为LOC(a0)，则第i个结点的地址为 ( )。
A、LOC(a0)+(i-1)*c
B、LOC(a0)+i*c
6 F# _4 `8 k+ W: QC、LOC(a0)-i*c
D、LOC(a0)+(i+1)*c
正确资料:
; V, [5 p' ~' X) T7 G" n6 o

第19题,分块查找要求表中的结点 ()。
A、全部无序
! B1 ?* ?7 i- P! B" m4 Z$ J) d+ @) zB、块之间无序
C、全部有序
D、块之间有序
1 E0 C* j7 i' e$ s+ t( v( X. y正确资料:

9 R' x; ~' D) F9 |0 p) [: I; G# H
! \# C7 z% _& f( ]- R, v- ^6 R, {第20题,下面关于串的叙述中，哪一个是不正确的? ( )
4 f) h8 l4 t0 oA、串是字符的有限序列
B、空串是由空格构成的串
. ?/ R9 V  |% X$ T: e# nC、模式匹配是串的一种重要运算
0 [% y1 B. Y, K, u7 U' W6 L( e0 aD、串既可以采用顺序存储，也可以采用链式存储
7 Y& A% O  a7 H1 f正确资料:

* Z, U. E5 E& L3 O
4 X3 {0 |# y1 L/ ?0 [0 H4 H第21题,二叉树按某种次序线索化后，任一结点均有指向其前序结点和后继结点的线索。
A、错误
0 c5 L4 l8 m5 f9 q4 S+ w8 gB、正确
) G4 i4 A( Q" w5 v- J! a' n正确资料:
* k8 b) F) V9 |9 P# N: r" m2 T

5 e2 V! \2 F8 g5 e9 \9 G第22题,在执行某个排序算法过程中，出现了排序码朝着它最终排序位置相反的方向移动，则该算法是不稳定的。
A、错误
; J8 S' @- C; y2 D8 RB、正确
  Z* B7 L* P0 u# _  d$ }正确资料:
& T4 h$ @0 e9 Q# R! J

第23题,非空的二叉树一定满足：某结点若有左子女，则其中序前驱一定没有右子女。
6 y% `& s+ U# N4 `: S; y- IA、错误
+ B: Q3 j! t; g' KB、正确
正确资料:


第24题,数组是同类型值的集合。
A、错误
1 j: _: h* {. K! e* h/ U; _! qB、正确
, ]5 B. x( b0 h9 R0 ^7 L  m正确资料:

; j( I; a7 C! f- \- {9 w; J
$ u! h+ Q! U. [+ m/ @+ {第25题,用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
+ o) f4 R7 C, L# jA、错误
4 m! b9 i* B# t: X; `4 @5 y& A4 LB、正确
正确资料:
9 A" S1 @3 [% \$ \

6 o, h! G) U) m3 F第26题,链表中的表头指针与表头结点起到相同的作用。
5 j8 {* v  }7 A5 {2 H& lA、错误
) y5 t* A, f0 E; J' k4 rB、正确
正确资料:
9 G, h' b+ E3 a: F' I
* {& h* P- ~; r3 F5 l5 j
- X0 c8 G* \3 V. ?第27题,栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。
  p5 |( C" g" P/ [A、错误
4 L1 A; H; T; p# c( w! ]& t" vB、正确
/ R7 F8 K3 b8 ~8 \/ g3 @正确资料:

' g9 \) e# \! t* _0 t% A
第28题,一个有向图的邻接表和逆邻接表中结点的个数可能不等。
A、错误
: ?4 C0 j$ `1 G6 n& kB、正确
0 X/ L5 o) `4 e2 Z& g& a正确资料:
7 [! r+ ~" r+ n( I8 o4 X0 X% T
# M6 b: o$ M) j
第29题,对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。
# y4 I0 K: v; A* Q" QA、错误
. w4 J2 w6 Q4 FB、正确
正确资料:

# c) c2 `$ M9 \8 D
- d' K! V( W, Z1 F第30题,任何无向图都存在生成树。
; u4 g, }9 L( y9 G' d4 l3 KA、错误
B、正确
" g  V0 n: Y; o# D正确资料:
- `0 ~' v! R, U# {1 k9 T" c

第31题,在完全二叉树中，若一个结点没有左子女，则它必是树叶。
0 W/ R5 M' E7 J, P; L( t4 D2 ~' I: ZA、错误
8 e6 b' v- H+ v- k8 TB、正确
- [! Y- U; s3 S6 N1 ]/ u6 D正确资料:


第32题,链表中的表头结点仅起到标识的作用。
; S! D% Y9 z/ X- Y5 T3 [! W; qA、错误
8 j/ ]6 V2 ?  KB、正确
正确资料:
; k2 t* b. }1 v2 H4 u1 G1 d
) _/ ?$ V7 J. g5 H: K% |: p
第33题,将一棵树转成二叉树，根结点没有右子树。
A、错误
5 S) ~: ]9 i6 mB、正确
# J2 H5 r3 y3 o; Z6 J) f正确资料:


第34题,连通分量是无向图中的极大连通子图。
* K! R$ M: G+ [/ Y" YA、错误
B、正确
5 @. z- d* q- a! m2 O正确资料:


第35题,所谓取广义表的表尾就是返回广义表中最后一个元素。
" y1 e, S9 y. P& G/ P: s+ x$ uA、错误
B、正确
正确资料:
/ I: E/ ^6 Y5 a) K- }. H

0 I: y/ }  _, H8 o1 q第36题,需要借助于一个栈来实现DFS算法。
A、错误
B、正确
正确资料:
0 Z( I# }# y( r; J3 V4 @) R
% p' ~+ Q% V( a+ A- m- G+ T0 y
第37题,必须把一般的树转换成二叉树后才能进行存储。
2 M: q4 c4 @/ u$ q3 jA、错误
* L2 w% c: J; S8 ]% \B、正确
正确资料:


( A( D( v6 V( `$ L( \$ Z# {) Q第38题,对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。
4 e' {# B2 z: c/ Y, g6 |$ EA、错误
  ?" y9 ]& t+ Z2 v) ]$ i  h1 a7 yB、正确
& U+ i  S$ I. G: a) B0 Y正确资料:
! z6 Q7 s* b2 |) R/ r+ M8 G' K- m

: X+ Q2 @% I$ l; p第39题,后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。
! F0 r3 N' G# E& X- PA、错误
; m1 j" ^' l. N+ _9 ^B、正确
! n' I  x3 }. V+ z  p+ s9 [正确资料:


第40题,二维以上的数组其实是一种特殊的广义表。
A、错误
B、正确
/ W1 O3 [9 v4 V+ [; z+ ~! O9 c正确资料:
" `/ n+ E% ]' y0 b, i