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

admin

数据结构19春在线作业2-0004
# i- c/ R8 A( e试卷总分:100  得分:100
0 j# `9 l" S3 _6 k0 \1 b8 z一、单选题 (共 20 道试题,共 60 分)
1.递归过程的实现需用到 ( )。
! |- G# K8 D5 K- _* ?  ^A.线性表
B.链表
C.栈
D.队列
$ G2 v& b) \: T7 V5 }正确资料
4 N1 \4 t) y0 g6 E& D8 e! z
* S9 U: j) f7 T/ C$ e4 ?2.在下列情况中，可称为二叉树的是 ( )。
( t  ]8 [' w! {A.每个结点至多有两棵子树的树
! ~0 [* a; V7 @" O. \. RB.哈夫曼树
( z  ^- o. g9 U2 H# XC.每个结点至多有两棵子树的有序树
- e$ `+ e& ]5 N/ ?/ oD.每个结点只有一棵右子树
正确资料:
% ^' z! H8 R4 y
3.经过下列栈的操作后，GetTop(ST)的值是 ( )。InitStack(ST); push(ST,'a'); push(ST,'b'); pop(ST,x);
A.a
, f$ i& @5 q: _- hB.b
C.1
! ]8 x  f. `- W( ~D.2
正确资料:

* b6 Z, v4 L  K4.若要求尽可能快地对序列进行稳定的排序，则应选 () 。
A.快速排序
B.归并排序
# E" z, E" k3 L% IC.起泡排序
$ H* f+ _$ T& a. d5 J' cD.希尔排序
3 _; N8 D: I( W$ C5 s# D9 L正确资料:

$ \4 ~$ W4 f( i) B5.一个算法应该是（）。
; R; ?- L$ P$ z7 U4 ]/ X( f$ ~3 VA.程序
: M) p& g; c4 [: oB.问题求解步骤的描述
C.要满足五个基本特性
$ d; O& m- f7 O' B& q8 t7 {D.A和C
8 K8 ^. q) V! C8 q9 \& y% R正确资料:
: Q; ]; c; I. ?1 L
6.判断线索二叉树中某结点p有左子女的条件是 ( )。
7 |  ^* ^; ~9 ~A.p ! = NULL
/ c; V/ Z6 l; \7 ^" }9 C. ?- B& JB.p->lchild ! = NULL
  O0 X' T% [  I2 x6 b: Y7 sC.p->ltag = = 0
D.p->ltag = = 1
2 {3 x# Q' `" `0 n: f正确资料

7.二叉树在中序线索化后，仍不能有效求解的问题是 ( )。
4 K, E7 s. t' V7 i) }3 s9 v- ?A.求指定结点的前序后继
  [* ]( @: ~6 j2 i- pB.求指定结点的中序前驱
/ y* t5 x  [5 qC.求指定结点的中序后继
: s3 K3 o2 H, m* i% F  a; x. SD.求指定结点的后序后继
正确资料来自谋学网（www.mouxue.com）
6 O+ N: d  U# f( z; g. \
8.顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。
& u5 t, ?1 {8 P7 M+ zA.附加文件
B.按关键字大小排序
2 ?& O# X4 l! C9 z/ k; A4 LC.按记录输入先后排序
D.连续排序
正确资料:

6 k! {. A7 X5 t5 h) j2 [9.广义表A=(a, b, ( c, d ) , (e，( f , g ) ) )，则式子head ( tail ( head ( tail ( tail ( A ) ) ) ) )的值为 ()。
A.( g )
B.( d )
C.c
D.d
7 c% x5 M: J0 f/ `8 _. V0 J正确资料来自谋学网（www.mouxue.com）

10.( ) 的遍历仍需要栈的支持。
/ V1 w5 p! r' d* g7 CA.前序线索二叉树
% W# j/ g$ Q* \, J; E" M. V9 d5 SB.中序线索二叉树
0 d. p& X6 i8 @" ?C.后序线索二叉树
D.前三种均需要
+ G; D$ _9 w  Z/ i4 c正确资料

9 g' n% `8 H, U6 E* p11.线索二叉树是一种 ( ) 结构。
" J) i& H* C- BA.逻辑
B.物理
, u! _) `2 a2 SC.逻辑和存储
, g. _- z* l8 z/ ?* p  k. k0 RD.线性
+ M" b- Z4 Z) \$ i正确资料:

12.有一个100*90的稀疏矩阵，非零元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是 () 。
9 O1 N4 h8 g. }+ y0 o) P1 ?. wA.60
/ [0 ]/ p( X' l( _3 a& WB.66
C.18000
0 P1 y+ H9 l6 J4 ]& }1 vD.33
0 [0 C% t: J; Y- `2 }正确资料:
5 d) l; X. H, o% _3 k& c7 D
8 S3 D: @7 k1 E8 Q& A  a: f6 Y. `13.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。
- e7 G4 F, W% rA.堆排序＜快速排序＜归并排序
5 W* x& L; o4 [B.堆排序＜归并排序＜快速排序
C.堆排序＞归并排序＞快速排序
" ]: ]' ~/ t! v1 @0 \D.堆排序＞快速排序＞归并排序
正确资料:
4 ]; W6 W1 D3 R8 ^0 P8 ^
( _) b' G; }8 H* S14.下列说法不正确的是 ()。
) ~) W* k$ @5 z2 |, HA.图的遍历是从给定的源点出发每个顶点仅被访问一次
B.遍历的基本方法有两种：深度优先遍历和广度优先遍历
( p+ w( g2 O, C4 w% e: VC.图的深度优先遍历不适用于有向图
1 i% E6 s, p; k* L1 ]D.图的深度优先遍历是一个递归过程
正确资料

! r' P5 b4 M# y( D) C2 W" i$ X15.在一个图中，所有顶点的度数之和等于图的边数的几倍 ()。
, \8 r8 ~5 Q6 K8 O0 A. ]. z* cA.1/2
. f7 Y! q9 Y  N* I2 ~4 t+ l+ tB.1
5 A9 B" w3 d1 }, s( F4 T. BC.2
$ i2 @) n7 |4 S" b+ r) hD.4
正确资料
/ G0 b4 E1 }- s: c* i
16.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行 ( )。
A.p->next = s; s->next = q;
1 u  c) v; e! I8 A4 b2 eB.s->next = p->next; p->next = s;
; l( d8 {% e4 y2 NC.p->next = s->next; s->next = p;
D.q->next = s; s->next = p;
正确资料来自谋学网（www.mouxue.com）
- h1 j1 f2 ^6 t, ^7 n" b
17.在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是 ()。
& ~# e- o5 d# H/ `, Z$ PA.O(log2n )
: E& x1 n+ }6 D& ~. aB.O( 1 )
C.O(n )
3 ]; J) N9 k) v# Z+ h1 H& W: kD.O(nlog2n )
* u& Q. P! |; h8 H正确资料:

( K* ^; F1 O9 A' K18.已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为LOC(a0)，则第i个结点的地址为 ( )。
A.LOC(a0)+(i-1)*c
B.LOC(a0)+i*c
6 X; r4 V7 I, V& k* iC.LOC(a0)-i*c
9 u* v9 g/ P% TD.LOC(a0)+(i+1)*c
正确资料:

19.分块查找要求表中的结点 ()。
% z+ S% K8 \! q5 V+ t1 i2 \) RA.全部无序
B.块之间无序
4 J- r! K3 T! f: f$ V  @  xC.全部有序
D.块之间有序
正确资料来自谋学网（www.mouxue.com）
8 ]( M8 \) f$ Y9 K  x
20.下面关于串的叙述中，哪一个是不正确的? ( )
' s( |/ S$ y) h$ g4 }A.串是字符的有限序列
4 a( M; i0 P: e! jB.空串是由空格构成的串
% i* c* r( Y9 I$ l* W9 x; NC.模式匹配是串的一种重要运算
, Z% F! u7 M3 ZD.串既可以采用顺序存储，也可以采用链式存储
& U+ o) l, t3 w- R2 J正确资料:
, g5 n+ x) o! t
二、资料来源：谋学网（www.mouxue.com） (共 20 道试题,共 40 分)
# J- u" l  S5 Z4 O21.二叉树按某种次序线索化后，任一结点均有指向其前序结点和后继结点的线索。
资料:错误
" b. J2 L0 n8 O* V& k6 [7 v1 l" J
22.在执行某个排序算法过程中，出现了排序码朝着它最终排序位置相反的方向移动，则该算法是不稳定的。
/ K! ^: X& }+ V  j资料:错误
8 P/ ~: Y& f+ _( _9 i& W
# U" G) [) Y6 F- L0 n: _23.非空的二叉树一定满足：某结点若有左子女，则其中序前驱一定没有右子女。
资料:正确
) W) O6 V' `' \# G# E
0 _* S; F& _1 m, f! O  G/ ?4 N24.数组是同类型值的集合。
资料:错误
! {" H3 ^8 `% e5 e$ X* H3 S
6 r# D& z/ R8 ~# l' j) j  z' j25.用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
资料:正确
+ d- r1 c5 v" ~& l0 G- [
26.链表中的表头指针与表头结点起到相同的作用。
资料:错误

6 _$ @( Z" u1 y* p; h27.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。
; u+ g6 C* J0 q0 _2 n1 W资料:正确

5 S0 f: Q  ?" c9 ~! h/ `28.一个有向图的邻接表和逆邻接表中结点的个数可能不等。
资料:错误
# d7 `/ T2 O0 C' ^% p5 G
29.对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。
资料:正确
. R" b" \  h5 L) w( k6 G  \
8 L+ L9 R: H& V9 K3 D2 L% @' [30.任何无向图都存在生成树。
资料:错误

31.在完全二叉树中，若一个结点没有左子女，则它必是树叶。
# H/ {" ?/ w5 n8 }9 @5 y& r  i资料:正确

& |" N) K! O% L" y- J32.链表中的表头结点仅起到标识的作用。
资料:错误
  S* ]0 f- m" r7 ~5 d
33.将一棵树转成二叉树，根结点没有右子树。
  \8 x  c3 o  s: Y; @6 J9 W1 v% j资料:正确
+ t- i5 d6 u" ^2 ]3 A
34.连通分量是无向图中的极大连通子图。
资料:正确

35.所谓取广义表的表尾就是返回广义表中最后一个元素。
& Q, d6 \  ?  `5 O# B" F; e; y6 E: V- F# g资料:错误
+ p; o1 o# T4 p+ B% `
# }0 N# v" @1 C+ R: C36.需要借助于一个栈来实现DFS算法。
资料:正确
# r1 z2 s/ z( X+ d: g; x* _
37.必须把一般的树转换成二叉树后才能进行存储。
  x% }; P  f8 P4 m资料:错误

; O1 J3 t4 L! l4 |4 [; B38.对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。
, U3 s7 ~, z" V7 j资料:正确
  a) ?# D- d% u- H8 {
3 T3 P# J- I8 r. f1 H* f& z39.后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。
  w3 l  e5 j  ^1 V5 N5 f4 `资料:正确

40.二维以上的数组其实是一种特殊的广义表。
资料:正确
3 \+ L0 ]3 E7 {9 M  T
0 D# o" d( U! n
) I$ c2 c4 t" `) S3 P2 ~
2 m3 u. t2 X( g, |# [5 C# M) Z

% \5 I0 h# P9 b! F


5 ^7 i# ~# w1 b4 |* u
0 r! [% c2 ~" P/ d* `
7 A  F/ {  ?; G! P; `) C. c
* m6 A- m5 ?; i) a6 b+ u