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

admin

【奥鹏】[东北师范大学]数据结构19秋在线作业1
) Q: M# \( e2 ]8 Q6 n8 f9 e试卷总分:100    得分:100
第1题,某二叉树结点的前序序列为ECBAD，中序序列为EBCDA，则该二叉树结点的后序序列为 ( )。
6 `) W7 V3 o6 ?A、ABCED
B、DECAB
1 x; h, o; H2 Q; N, P$ _C、DEABC
D、BDACE
, b+ f' H% l4 ~9 @/ C正确资料:

* w6 h1 x5 l! P5 O& c/ L4 M; v
. O; }+ y  s1 g6 V6 {第2题,存放在外存中的数据的组织结构是 ()。
3 I. n0 ?  H. J7 V- b  K5 m6 EA、数组
B、表
. ~: P7 ^$ X1 |' T+ p2 t8 T- hC、文件
. ^! X6 g1 d" c1 BD、链表
正确资料:
, \3 W8 D) n7 @

第3题,在下述几种排序方法中，不稳定的排序方法是 ()。
$ J) _/ \6 C! }2 IA、直接插入排序
* l; y. ?7 o4 w2 r. RB、冒泡排序
; a# E# U8 [; }C、直接选择排序
+ `6 ]4 m% M3 ^D、归并排序
正确资料:
5 G: e# x% {- v( m

第4题,“堆积”问题是由于()引起的。
8 v7 V) Q/ d- W; J  PA、同义词之间发生冲突
B、散列函数
C、不同的同义词子表结合在一起
D、散列表“溢出”
) M; z# R. A  B+ B; `正确资料:
* W* `$ U$ A) H8 ?2 m

: P, D/ m8 b! x8 h第5题,若要求尽可能快地对序列进行稳定的排序，则应选 () 。
A、快速排序
- n, G5 G* C9 F: x1 xB、归并排序
) t* \1 z- Y* f" ?C、起泡排序
D、希尔排序
& ]* g1 `" s0 i, s% C正确资料:

8 p+ h) @$ ?5 }9 w
第6题,采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 ()。
A、n
' j: \9 ~" A, P1 H2 _B、(n-1)/2
C、n/2
: c( N; M  F1 S/ W- c5 TD、(n+1)/2
- I2 T% W1 q- x; E: H正确资料:
2 @& ^) h! O7 \6 }+ k
& F1 t) C  G+ a3 Y0 n6 ?, k
9 t) a3 Q$ A& L8 K' |4 @! w3 ]第7题,用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是 ()。
A、逆拓扑有序
B、拓扑有序
C、无序的
# V8 l2 l5 {. y  G% t0 gD、部分有序的
正确资料:


- R: R' |6 V2 m4 a" I. W6 u第8题,设根结点的层数为0，若高度为h的二叉树上只有度为0和度为2的结点，则此二叉树上所包含的结点数至少为 ( )。
: q( {; R4 L1 f& @A、h+1
B、2h-1
C、2h
. c* H& m4 `6 {$ Y0 `D、2h+1
8 I9 L! k" u) m7 u: ?( m, J正确资料:
8 I) j: H% R% ?9 K3 e5 f
0 p8 h' h: X8 x! @
第9题,在下列情况中，可称为二叉树的是 ( )。
0 s' R! T* s) k4 j( ~  VA、每个结点至多有两棵子树的树
B、哈夫曼树
C、每个结点至多有两棵子树的有序树
D、每个结点只有一棵右子树
6 j# E1 i# l1 s% y正确资料:
& Y4 m3 N. q/ M9 e4 h! q* e, i
: F% c! G! _6 S' R. A
第10题,广义表 (( a , b , c , d ) ) 的表头是 ()。
A、a
B、( )
, i; ]4 W9 P0 C, dC、( a , b , c , d )
D、( b , c , d )
, `/ g+ k2 `; ?# R正确资料:


第11题,设散列地址空间为0～m-1，key为关键字，用p去除key，将得到的余数作为key的散列地址，即h(key) = key % p。为了减少发生冲突的频率，一般取p为 ()。
A、小于等于m的最大奇数
B、小于等于m的最大偶数
C、小于等于m的最大素数
+ Q: z4 r8 V. I: Z% tD、小于等于m的最大合数
8 L! U& l- R" S3 Q9 N- [正确资料:

4 y/ V! A* H0 M- Z& p$ I& |/ x
第12题,有m个叶结点的哈夫曼树所具有的结点数为 ( )。
A、m
B、m+1
4 b- Z, k" `  ~$ GC、2m-1
) H. |2 d9 O% ?( t- LD、2m
正确资料:

  l, L; n7 a6 g6 _8 A4 o
第13题,树最适合用来表示 ( )。
) t4 r+ a' R. ~1 O+ Y- Y6 JA、有序数据元素
* j; R' T; k2 L" ~7 OB、无序数据元素
C、元素之间具有分支层次关系的数据
& I! W% G) F; M& P1 K9 zD、元素之间无联系的数据
正确资料:

/ T6 ~8 W6 ^. [! f! y  L) ?: T
第14题,在下面的排序方法中，其比较次数与待排序记录的初始排列状态无关的是 ()。
. `' U8 X& N  oA、直接插入排序
B、快速排序
/ z% A% S& B# ?% @- bC、直接选择排序
1 y4 [. y6 v5 ND、归并排序
正确资料:
( \: M3 S7 h/ G  U1 V# @# Q
( g, A  s2 T  F) \
) W' g. r# O. d* |9 @第15题,有n个顶点的有向图的边数最多为 ()。
2 O: L4 B1 P, _" A  }4 h: jA、n
/ L1 [" _& V% vB、n(n-1)
C、n(n-1)/2
; C# y. l5 U& t# }D、2n
; B- j* \2 s: a8 q正确资料:
. F$ d. e5 o& @  q
. T+ r  B& J2 [" Q
+ Z1 h* g2 l6 b9 O  R第16题,假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测？（）
8 K+ t  x" y9 G: Q0 W% M4 mA、k-1次
B、k次
C、k+1次
; S# S  t! [, |) eD、k(k+1)/2次
正确资料:


$ Y) E: y- F, l# Q/ k( C/ |第17题,在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的一端的方法，称为 ()。
3 E) E9 P* L) U' ^$ g0 nA、希尔排序
. c" D6 _3 V; X  A9 _! F: b# uB、插入排序
6 G/ A9 s  V! k. sC、归并排序
D、选择排序
5 M& h4 y! t$ B8 w0 @正确资料:


! `* g( p) A9 z& f第18题,在下面的叙述中，正确的是 ( )。
A、树的先根遍历序列与其对应的二叉树的前序遍历序列相同
4 O5 d2 V+ Z/ n5 n# O& P: wB、树的先根遍历序列与其对应的二叉树的中序遍历序列相同
C、树的先根遍历序列与其对应的二叉树的后序遍历序列相同
D、树的后根遍历序列与其对应的二叉树的后序遍历序列相同
/ o7 `% H4 {4 r2 f# D5 E' k4 {4 V正确资料:
" x. x% A+ W4 W, x# F7 p
6 R7 i% K' Z2 P
第19题,有n个顶点的无向图的边数最多为 ()。
7 y7 J+ a% G$ g) r2 R& @A、n
B、n(n-1)
7 y3 Y  {+ b5 m- P8 A# `- W3 w/ _C、n(n-1)/2
D、2n
正确资料:
, M6 ~* b- D  o! U3 E
$ W! e0 J! `7 F' F! E' O
! r' Y. ^; a: {第20题,在排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 ()。
& Z4 `2 \+ }% o+ ?* t+ e. }A、直接选择排序
B、冒泡排序
. i, z! }0 P0 p( j# O  {C、直接插入排序
  E& X+ J* }7 }) U; TD、希尔排序
; ]1 P. D" b  y( Z$ R$ z& D! j正确资料:


第21题,快速排序的速度在所有排序方法中最快，而且所需附加空间也最少。
A、错误
/ A  n; v! V9 g; E! p; Q( \% ^: xB、正确
正确资料:
5 f: V5 s8 l' [! u6 ]
- u/ q2 [. p8 B" P! S5 r  n
第22题,在中序线索二叉树中，每一非空的线索均指向其祖先结点。
. Z" x4 o( x5 P& ^' j6 ZA、错误
$ d* \* Z$ Q% o% F0 l2 P: ?, ^B、正确
$ j" v6 |! ^. k+ w# S: y- r正确资料:


+ x: Z1 j% n1 P9 T第23题,当待排序记录已经从小到大排序或从大到小有序时，快速排序的执行时间最省。
A、错误
! s2 U: {- |8 S. w9 e% nB、正确
+ c  y2 W, e* p- F4 c# x( H正确资料:


" ^( G, b. R( K* V) F8 n第24题,快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n )。
' F' |% H# Z9 J2 @, J* P6 qA、错误
B、正确
, G0 N2 `( C2 M) P% g2 B正确资料:
, b9 i8 D7 h7 w: n2 b4 v: q
# y  J2 |! F- r) E+ R$ R9 J
第25题,二叉树中除叶结点外，任一结点X ，其左子树根结点的值小于该结点X的值；其右子树根结点的值大于等于该结点X的值，则此二叉树一定是二叉排序树。
A、错误
( y- @, ~! a6 x1 g* }; \% j8 vB、正确
; @3 G$ t  K& F' n8 b正确资料:
9 Z$ O- [, @. U$ }$ W

第26题,对有序的单链表可以进行折半查找。
) b5 L  @$ J- q3 x. V1 iA、错误
B、正确
正确资料:

9 N' W2 v( ~! k/ q2 f$ {
/ p" B8 K. r5 k3 j4 Q第27题,堆是完全二叉树。
A、错误
B、正确
0 Z7 i# Y* `% C2 I% K正确资料:
1 D0 T" |9 C3 E& A9 e7 x3 X. U
; V* {, k3 u4 ]4 i& O
第28题,对一棵二叉树进行层次次序遍历时，应借助于一个栈。
A、错误
% h) S1 \3 a( W; jB、正确
正确资料:


第29题,直接选择排序算法对n个记录排序，在最好情况下的时间复杂度为O(n)。
5 w7 K. g' }8 ~9 l2 L& M/ ?, bA、错误
B、正确
正确资料:

% L; s, H7 ]& J
( ?% R0 {8 x9 Z第30题,二维以上的数组其实是一种特殊的广义表。
: T4 f3 N/ G% z7 b9 u$ K0 O: I! V: jA、错误
B、正确
# Q; ]) U5 z" X& \  c6 J% a正确资料:
7 l2 C+ k: X# v' [# v0 g
+ B% V. W$ r( y  A
第31题,若一个广义表的表头为空表，则此广义表亦为空表。
A、错误
B、正确
% a7 t$ G" u* H) A/ r5 r% `( L正确资料:
! A0 q! S- |' U
0 o! b( k7 {* g
) z6 r1 a  e& w4 }" U第32题,空串与空格串是相同的。
: ~0 X( n5 |1 c' U+ L# A' f# EA、错误
' o; o  |5 O; T% r4 U* v8 X7 V3 E8 BB、正确
正确资料:


第33题,在待排数据基本有序的情况下，快速排序效果最好。
A、错误
B、正确
, Y! n% J8 i& w正确资料:

, C0 L7 l( I6 f- s
" d% z5 Y6 u8 o  m( c: Y8 x第34题,二叉树中每个结点至多有两个子结点，而对一般的树则无此限制。因此，二叉树是树的特殊情形。
A、错误
! \8 Y* Q5 x! Y2 _  NB、正确
; x1 c" M) S9 S; W# ]6 Z正确资料:

, i- y+ C% A" j* k3 V7 ~2 t
第35题,最小生成树问题是构造带权连通图 ( 网 ) 的最小代价生成树。
3 N+ _4 _; \* T( V" {A、错误
B、正确
正确资料:


/ j0 t4 X" k; G, V8 H第36题,串是一种数据对象和操作都特殊的线性表。
A、错误
B、正确
正确资料:
6 W/ Z! w7 o# A8 w3 r  R* N* C! y8 }

第37题,( 101, 88, 46, 70, 34, 39, 45, 58, 66, 10）是堆。
/ m4 y* j# s/ i# NA、错误
B、正确
正确资料:

  B& W, ~& T0 n) r/ U9 f
% e& [5 M% _. T$ l, i2 G第38题,二叉树结点的中序遍历序列与前序遍历序列可以唯一地确定该棵二叉树。
A、错误
B、正确
正确资料:
0 d( a) }9 ]8 m) s5 g* b9 t
% X  L& j% p1 l0 A, z6 R* Y- M
. e. G' ]9 o, r. N* M第39题,顺序存储结构的主要缺点是不利于插入、删除操作。
A、错误
B、正确
正确资料:
1 _; q* @* _( M& R  Z# [" `$ K; b
5 u) _, w6 k; T" k
. d6 g/ `. ~5 u3 D: |6 P第40题,文件系统采用索引结构是为了节省存储空间。
A、错误
B、正确
正确资料:
" l6 j) S* [4 p- O( v" D' x1 }9 h
3 ~$ R) U' y4 [& n$ G9 O7 `