[东北师范大学]《数据结构》20春在线作业2（资料100分）

admin

资料来源：谋学网（www.mouxue.com）-[东北师范大学]数据结构20春在线作业2
试卷总分:100    得分:100
. c/ [; M" `8 Y: \第1题,递归过程的实现需用到 ( )。
" {) s; l  ^, \/ e0 jA、线性表
0 t' z1 N( [( Z; G& E& }& ?0 O2 CB、链表
& Z9 U" E1 B: \3 L: C9 b& H* EC、栈
D、队列
9 @: J6 q/ [& n- j- I- E, w( F9 C正确资料:
  S4 e+ o* S) @  J$ g. @1 E" y

第2题,在下列情况中，可称为二叉树的是 ( )。
A、每个结点至多有两棵子树的树
B、哈夫曼树
C、每个结点至多有两棵子树的有序树
D、每个结点只有一棵右子树
正确资料:
: z) k1 K( }/ l6 F

+ h: ^. w4 M( {第3题,经过下列栈的操作后，GetTop(ST)的值是 ( )。InitStack(ST); push(ST,'a'); push(ST,'b'); pop(ST,x);
) U* O9 c1 M2 r3 P0 @4 d8 F# oA、a
B、b
) o0 M3 h6 n- v# |# h" q6 RC、1
D、2
$ [2 y7 a8 a2 q! y4 Y7 X/ G正确资料:


; ~1 g# o6 \1 ]6 f3 {3 ~第4题,若要求尽可能快地对序列进行稳定的排序，则应选 () 。
A、快速排序
B、归并排序
( g; T2 {  c, j! M( EC、起泡排序
D、希尔排序
正确资料:

6 ?4 v5 r) I2 L: @( Y# V6 S
资料来源：谋学网（www.mouxue.com）,一个算法应该是（）。
A、程序
  H: L$ ^& m! L% J, o- wB、问题求解步骤的描述
C、要满足五个基本特性
" L' ]; X( N0 _1 \" R0 cD、A和C
正确资料:


第6题,判断线索二叉树中某结点p有左子女的条件是 ( )。
4 _* ~+ k- Q4 k5 x' ?1 ]A、p ! = NULL
( j1 n0 y+ t2 ]5 UB、p-lchild ! = NULL
! s8 a5 E. i- D+ U  qC、p-ltag = = 0
( i# \3 x% a! i) {7 ?D、p-ltag = = 1
正确资料:

) P2 v1 Y; U4 K8 w8 y5 ?- k. V: F
第7题,二叉树在中序线索化后，仍不能有效求解的问题是 ( )。
, r* H# L5 r8 H$ H9 y  V( c5 q9 bA、求指定结点的前序后继
( h, P* }; J+ U- CB、求指定结点的中序前驱
C、求指定结点的中序后继
D、求指定结点的后序后继
正确资料:


$ I; E4 D" T" ^第8题,顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。
$ y7 g+ \2 ]7 Z  w  _/ dA、附加文件
3 ?, Y: a& \7 U8 I! dB、按关键字大小排序
6 f! w+ X& `4 kC、按记录输入先后排序
7 b# [# j8 t- E8 M' Q% gD、连续排序
7 m2 s, z% m2 m: |0 _7 ^: |' j正确资料:

$ ~' Z. N+ A7 W. s$ D
& I8 b% X8 P1 M" u! w8 [第9题,广义表A=(a, b, ( c, d ) , (e，( f , g ) ) )，则式子head ( tail ( head ( tail ( tail ( A ) ) ) ) )的值为 ()。
A、( g )
0 V0 }! l6 U1 ]/ AB、( d )
; }' ^- T# i; N0 R0 _C、c
D、d
正确资料:
+ F+ d5 a7 A7 ?, F2 X2 ^8 Z1 c  `
- C  }3 r! z  m0 ?  i) d! T# w) C" }
! O: s" s: ^. K5 }- v资料来源：谋学网（www.mouxue.com）,( ) 的遍历仍需要栈的支持。
' B" y6 M: F6 L/ U* g  Z8 F- a# c2 zA、前序线索二叉树
B、中序线索二叉树
" _- ?6 j( Z& e% Y: l+ m$ |C、后序线索二叉树
' P, R; @* L5 ^, B' q: Q7 LD、前三种均需要
正确资料:


6 y% N  R0 d! X* l7 o第11题,线索二叉树是一种 ( ) 结构。
A、逻辑
B、物理
C、逻辑和存储
' ]- u7 N! H8 i& `  y: j9 Q' A4 PD、线性
正确资料:
/ c2 z; b( n! E6 R. t! E6 _4 s( S

; i  D6 c; k6 Y" ~7 X0 y8 L  o资料来源：谋学网（www.mouxue.com）,有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是 () 。
/ T: C; R4 ]6 u2 Z5 {6 bA、60
B、66
$ \6 Q; p) t3 U3 ~. `( gC、18000
D、33
正确资料:

7 ]' Y* K+ b) N" {% ~7 @7 a5 x
第13题,就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。
( h( _# c( b) J. }$ i' F3 R" U0 [A、堆排序＜快速排序＜归并排序
; c) Q9 Z/ w% Y- w1 z1 ]B、堆排序＜归并排序＜快速排序
  h% o2 V8 ?  W# e7 @C、堆排序＞归并排序＞快速排序
* X- {9 I) [# _! `! r# A. }0 |D、堆排序＞快速排序＞归并排序
* v: N  G8 r- T3 x2 d! I2 P正确资料:


第14题,下列说法不正确的是 ()。
6 a! z: C) `* I/ L9 y5 BA、图的遍历是从给定的源点出发每个顶点仅被访问一次
6 W0 r! e  S4 }, H+ {B、遍历的基本方法有两种：深度优先遍历和广度优先遍历
C、图的深度优先遍历不适用于有向图
D、图的深度优先遍历是一个递归过程
7 G. R4 d* g1 ^正确资料:

/ Y1 {& x3 y% U
* N2 L' E: S- d- B: c* N资料来源：谋学网（www.mouxue.com）,在一个图中，所有顶点的度数之和等于图的边数的几倍 ()。
A、1/2
  G8 x0 `  A7 FB、1
C、2
+ `5 B1 w2 N# v3 ?+ y/ LD、4
( Q! E$ Y- H, E. \3 Y5 ~正确资料:
% w+ J5 V  P$ w
* B) Z9 ?3 l7 [5 p) D" p8 s
  a6 n* Y4 z7 {5 u- C第16题,在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行 ( )。
, J: V5 D# m1 ?, J' nA、p-next = s; s-next = q;
B、s-next = p-next; p-next = s;
4 x' M, A3 T, W! o* sC、p-next = s-next; s-next = p;
5 F- |1 X2 X" h" r" \# DD、q-next = s; s-next = p;
正确资料:


第17题,在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是 ()。
( z3 o7 k* F2 \) S/ _" pA、O(log2n )
B、O( 1 )
" E  u) G+ z, S9 }# rC、O(n )
D、O(nlog2n )
* ^+ U/ \9 n9 a  E: n0 r% z正确资料:
5 M3 U6 w* r6 j$ C: @$ x1 B
+ S* U2 G6 _  _: O6 R; `7 O/ ~
第18题,已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为LOC(a0)，则第i个结点的地址为 ( )。
0 [* S/ x5 Z4 P8 C0 H8 W9 j0 FA、LOC(a0)+(i-1)*c
B、LOC(a0)+i*c
C、LOC(a0)-i*c
  ?. L/ T, z, A; g% UD、LOC(a0)+(i+1)*c
正确资料:


第19题,分块查找要求表中的结点 ()。
A、全部无序
B、块之间无序
& u7 a* M! ?; M9 tC、全部有序
) ~+ V8 j- g* h3 H- vD、块之间有序
正确资料:


资料来源：谋学网（www.mouxue.com）,下面关于串的叙述中，哪一个是不正确的? ( )
A、串是字符的有限序列
, D! ?) z( Y( w# z% W4 V! TB、空串是由空格构成的串
0 s- h/ e6 o$ ~; B4 @  hC、模式匹配是串的一种重要运算
5 K/ W5 ^8 N% S9 @$ C# \8 F/ e5 lD、串既可以采用顺序存储，也可以采用链式存储
& H. s7 K+ h! m1 V1 u8 h. R正确资料:
( N0 X5 ^6 r5 p3 P7 W9 L9 J

& v( S/ Y0 D8 n4 b* _第21题,二叉树按某种次序线索化后，任一结点均有指向其前序结点和后继结点的线索。
A、错误
, w9 P! ~: [7 s  o$ \B、正确
  R+ U; p- K5 N8 P! z正确资料:
7 ?0 s& x* V+ ?6 k% v/ V6 }* k

第22题,在执行某个排序算法过程中，出现了排序码朝着它最终排序位置相反的方向移动，则该算法是不稳定的。
A、错误
- z; ~$ Y9 H5 @' }1 \* zB、正确
! R7 H2 R1 }5 }1 N; {+ n, d, X: w正确资料:
. i6 }( l9 {/ i5 t, D

, R/ T! W& N" z: K8 g第23题,非空的二叉树一定满足：某结点若有左子女，则其中序前驱一定没有右子女。
A、错误
B、正确
' n" x0 `( O0 \* ]1 k8 }正确资料:
2 J9 V- U8 T& e9 S3 n# D% J0 h3 j

第24题,数组是同类型值的集合。
0 m5 I/ f) K# X9 M$ t" \A、错误
/ `9 E/ A. \+ u4 A! y8 |# XB、正确
' W0 x1 k  G0 ], `  W正确资料:

( p! J3 f+ b! U$ X# n; q
资料来源：谋学网（www.mouxue.com）,用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
A、错误
7 ^$ Y3 b( O/ F  q, v8 O! I/ jB、正确
: Z" t/ U1 E. @+ b! `9 u正确资料:
* B/ ^/ ]+ h; C: B, L. N/ U
) x+ S- W1 J, }  _& b2 O
第26题,链表中的表头指针与表头结点起到相同的作用。
A、错误
) y; W( R6 h9 W% w  {B、正确
( n+ q1 U& V/ b正确资料:


; ~) [4 s1 h& R0 I! S第27题,栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。
A、错误
. N8 Z6 w+ C" E- q2 m( hB、正确
! `8 R/ M' }7 k) H2 O" k正确资料:
4 g" {3 R+ |7 n4 {
$ t  n% [* E+ G* k8 j) z, N
4 K5 f: `% d$ {第28题,一个有向图的邻接表和逆邻接表中结点的个数可能不等。
A、错误
. Y: {2 q6 @% OB、正确
正确资料:

' R9 [9 y  L7 y& Q  T6 h0 `
第29题,对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。
7 R; _& i; X/ V4 g1 {A、错误
B、正确
1 E0 ^, }( l; I7 P! @0 y正确资料:

# J2 B" e! t' m. V2 U8 \, N4 z
& t! X1 d! n. F) `7 e- D. S9 x资料来源：谋学网（www.mouxue.com）,任何无向图都存在生成树。
: {; `3 Z- i' q7 f$ T/ ?/ JA、错误
" J( b4 C3 Q; y9 Q# y# v# C4 K7 }: G: SB、正确
" {( P3 H6 U6 _' n; g. w: h正确资料:
# I/ j1 E5 Q3 A6 u2 [6 i

+ r& z7 k& ]: M* f( \第31题,在完全二叉树中，若一个结点没有左子女，则它必是树叶。
A、错误
3 j$ l- S' r! LB、正确
正确资料:


第32题,链表中的表头结点仅起到标识的作用。
+ _. R/ b, w( s' a4 x, {$ T' hA、错误
7 B/ Q% y4 R# l7 a0 JB、正确
正确资料:


第33题,将一棵树转成二叉树，根结点没有右子树。
A、错误
3 c$ z6 p; T/ r2 s" A! ]- F' U6 RB、正确
正确资料:
: ]5 O* c0 Q. Y8 }" X/ X5 a9 d

, \. g: b- u4 J+ ~, r: S第34题,连通分量是无向图中的极大连通子图。
A、错误
B、正确
正确资料:
  i8 F+ d  c: }; ?

4 e0 e7 y8 l" H% X+ m第35题,所谓取广义表的表尾就是返回广义表中最后一个元素。
* ^% m: W, W+ m- XA、错误
B、正确
5 D$ ?4 E3 q- b: z正确资料:
) \6 e0 Y/ c+ R% C6 Z

第36题,需要借助于一个栈来实现DFS算法。
7 u! ?5 m/ h2 PA、错误
B、正确
正确资料:
2 z+ |2 k) F+ q$ [! o

第37题,必须把一般的树转换成二叉树后才能进行存储。
A、错误
; ^0 S" D  k, B  A0 y% TB、正确
正确资料:

6 A# x0 A. O9 x5 a; \# T
7 y8 {7 u0 C5 G9 ?9 a/ u2 @第38题,对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。
- E5 @4 t- c: R3 k/ r! jA、错误
4 P! O' m/ V( q6 F. ~- bB、正确
正确资料:
  F; g! H" q, M; N% y2 s
( {: p  ~& ]2 t/ \! B# f5 x/ [
2 w# f+ q2 ?' c( X' {' J# z" W! C$ S第39题,后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。
  b0 X' T. }7 i8 RA、错误
, a% P. f* R8 \# w/ ZB、正确
正确资料:


第40题,二维以上的数组其实是一种特殊的广义表。
8 F- o7 r2 {& J7 GA、错误
B、正确
正确资料:

, o( w. b. e& p
  g; }0 I: |# _. b
0 @  R  _4 \: H7 w# h! O; [( f2 V
  r6 q/ }% `8 [' r" n, ]& b
$ b/ s% s7 [  S1 Q$ K6 `; R
  R( t6 C; M( |6 S/ {# @



. U( Q3 b9 h' ~7 s. Y( M! K; t1 L! y+ l
  d; b' b3 K7 v# W* U
6 l' y. q, q6 k3 z! e3 y

" z& `* h+ T9 d, {: p- J( H2 T8 D