|
一、单选题(共 10 道试题,共 40 分。)V 1. 设深度为k的二叉树上只有度为0和度为2的结点,则这类二叉树上所含结点总数最少( )个。
% G7 r8 |/ `' D; P6 y7 nA. k+12 B( z) v+ i/ d1 [, w0 |3 b( X
B. 2k! b# X% s! R- ^' u
C. 2k-1
: \7 P4 k9 E0 X4 }% v& J4 [; ~D. 2k+1
' G& z0 O, H3 i3 e 满分:4 分) } s( c, O& g2 y, S( M
2. 带头结点的单链表head为空的判断条件是()。4 Z8 a* m& \ Z( b0 y
A. head=NULL
/ O! i+ V( d4 @" V! K3 p" pB. head->next=NULL o! h6 Y+ P. W& p
C. head->next=head, D% h& {# x6 L$ B3 X" j D/ [6 y
D. head!=NULL# y4 O: Q2 z% Q" h' t
满分:4 分
s5 v. y9 s; u4 {; V& f3. PUSH和POP命令常用于( )操作
9 M3 A/ k# Z. |3 ?$ uA. 队列1 s5 e( v. P0 X7 B% A
B. 数组9 z+ K: P4 j$ b
C. 栈' b/ C' v2 L+ e/ J" z
D. 记录
J( H$ [: R! O; U 满分:4 分
! y8 X& v) b6 X8 F5 \4 i7 \1 E9 a4. 非空的循环单链表head的尾结点(由指针p所指)满足( )。- n% p1 c) \8 k& O( b5 \) _) w
A. p->next=NULL: R" P0 r# V" I, {4 Y }( L
B. p=NULL
B; \" F; g3 f5 M8 g) j+ ]C. p->next=head, g) ^ Y: U/ s1 r! O* c( p
D. p=head& L7 W' W \4 K9 D: M) b( w7 ]
满分:4 分 q8 Z% o3 F5 D1 \" Y
5. 任何一颗二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置( )。5 `7 ^2 X2 k# n& D( R; z9 b* x+ S: I+ _
A. 肯定发生变化) G& Q5 C; N6 W" a9 B
B. 有时发生变化! v0 ]& o/ c( S" Q
C. 肯定不发生变化
D' L3 [5 Q" B& k3 b# u- S2 kD. 无法确定
+ @7 q0 h% O: ~# p9 F# \# w 满分:4 分
" V" k0 i6 j9 U/ H; U9 D$ I: ^9 W( L6. 链栈与顺序栈相比,有一个比较明显得优点是( )1 T1 P1 B3 s' s2 i
A. 通常不会出现栈满的情况3 W* L( M2 `8 j* ~/ X% |! }5 X
B. 通常不会出现栈空的情况, L/ I- `% X, p7 [6 P
C. 插入操作更加方便
) Z; ^8 F% [: VD. 删除操作更加方便5 }9 {6 J9 B3 X3 a- y Q
满分:4 分
d6 S+ g: {) \' C7. 含n个顶点的连通图中的任意一条简单路径,其长度不可能超过( )。
+ ?+ P- u) `5 Z) b6 j8 J N3 NA. 1
' |& V$ G8 D# ?7 p: e* T( P3 ^B. n/23 N: I9 [8 u& o' ^: f' V
C. n-1' \1 {. i- d- A2 }, V/ m
D. n* M& N6 N h: H, T h
满分:4 分" c. C5 j# U# o
8. 从具有n个结点的单链表中查找值等于x的结点时,在查找成功的情况下,平均需比较( )个结点。
! e1 _! C' U8 Y& wA. n
3 e, x1 _+ C! _" QB. n/22 V6 a6 d+ p) {2 a0 V
C. (n-1)/21 [7 s- w7 W/ p( ] c3 t
D. (n+1)/2' y$ v- l, i; y* z
满分:4 分
! C: y5 V( y/ h$ |* u8 H9. 当文件局部有序或文件长度较小的情况下,最佳的排序方法是( )。
2 a) F [" ?2 x0 gA. 直接插入排序, Z2 H+ X$ u/ S8 B0 p/ M
B. 直接选择排序# _# y$ Y3 }' I/ l! C2 V
C. 冒泡排序5 k, _% t1 A/ ]5 ]) s+ ]1 Z% Q
D. 归并排序8 f; p& T) \' f
满分:4 分6 x* h% R+ k- f2 U E- Y+ A% @
10. 在无向图中,所有顶点的度数之和是所有边数的( )倍。
- K8 j! S l0 L1 NA. 0.5
* d/ x; D- d+ W3 \' J) hB. 1
4 l( v- N& h9 @C. 2
/ d1 u; t3 K; w( X3 Y+ k0 \4 aD. 40 h% r* l! h" c, w! G0 V: j
满分:4 分 ( I8 w+ F/ s, l; Z
* Y, A; B3 B6 e) A" n0 {) A二、多选题(共 5 道试题,共 20 分。)V 1. 递归过程中要保存的信息包括( )
0 R8 J" X/ W8 ~) N i5 p# ]A. 返回地址
A6 R, Q( V6 {! X, {* }) zB. 本次调用中与形参结合的实参值
( ~" B& o1 j6 O# LC. 本次递归调用中的局部变量值9 v, a; |. P, P; H
D. 执行结果
2 J6 A% M4 X) u/ b6 b) i' z3 [3 [ 满分:4 分2 x' d0 u4 o; K( j2 k. z9 E! w
2. 数据结构指的是数据之间的关系,主要包含3部分的内容( )
( y2 s ^9 H( h( LA. 数据的逻辑结构
# f0 \% Y& j3 [' `6 zB. 数据的存储结构; N& h7 R3 f2 a: C
C. 对数据施加的操作+ t& o* [' y8 n+ C
D. 算法
! D, ~9 s" ~9 f: c+ l, Q 满分:4 分
+ W* A: z8 U0 Q! P3. 对线性表,可进行如下基本操作( )
: Q2 M5 o* H _& ~0 G9 q8 nA. 随机存取
* G3 H: r3 C* K; D7 |7 qB. 插入 v6 G! ]* l' V% H9 L
C. 删除
1 h) U: n h3 q: kD. 查找, U, g$ |( { ]8 Z, c. c
满分:4 分
# { J0 [0 k- o7 i' E4. 对有序表的查找方式有以下几种()
; D* P9 J0 ~. f5 R: p+ {A. 折半查找; {. O3 ^% D3 p- T
B. 斐波那契查找
) M, Q! Q3 ]+ ?2 CC. 插值查找
$ @- b- u% {' X; R5 oD. 二叉树查找5 S& r7 E. o; J3 h) R
满分:4 分
- M( S+ ^" p8 v, W" Y5. 图的存储结构有()
5 O% X( u6 J9 f: W9 _$ P2 ~: x1 e* [, AA. 邻接矩阵+ |2 A1 {% s' l. s- r% T
B. 邻接表
% O' |2 a; }5 K" `C. 数组表示法
& w' A; c+ q- i4 L6 K# u- zD. 十字链表1 R; H N0 h! e2 Q4 @
满分:4 分 7 P3 s8 ]2 s5 u2 K2 i3 W7 ^. W q
; w7 p) E; P( Y/ f* a# U* y
三、判断题(共 10 道试题,共 40 分。)V 1. 对于前序遍历和中序遍历结果相同的二叉树为所有结点只有右孩子的二叉树
$ f) M1 {% B+ a5 f" M& u& } ]A. 错误2 ?1 u) ]$ z( k3 \6 a* h! s
B. 正确
+ d% T0 }- c( q* _# y( }* m 满分:4 分6 Q! \; k7 i7 d [ \+ s7 K
2. 从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较,然后将其放在已排序序列的合适位置上,该排序方法称为插入排序. l! G/ [( T" s! K5 y1 g# p% q# m
A. 错误
# s. o2 p+ k6 |* n bB. 正确
5 ?) j) |6 V8 @4 t 满分:4 分4 J( h' I6 Q6 N7 ~# V! \: G) ~
3. 由权值为9,2,5,7的四个叶子结点构造一棵哈夫曼树,该树的带权路径长度44
/ L5 y0 E7 u% U4 H& \* x" F# nA. 错误' D: |: S) m R' G
B. 正确8 M5 H$ U6 y! a) n* M% v
满分:4 分
( B( r( M q, b) X) N) r8 A, ^4. 若需在O(nlog2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是归并排序
- A3 T5 B& I0 x* y' |A. 错误
1 Z4 k6 ^! i) g7 C+ oB. 正确
% i1 d# G+ w0 d' ]! A 满分:4 分
5 J6 ?6 ?, z3 S7 Z2 @$ r5. 在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是归并排序: E/ R0 s( T0 w9 h5 y
A. 错误
( M- i( n3 ~8 L% zB. 正确& u9 w6 d0 N* N# P
满分:4 分
1 h* q7 v4 n+ F- k! E6. 栈和队列都是限制取点的线性结构() z& Q: h% ^0 |8 \7 X# L. K5 e
A. 错误& u5 P* ?- y3 q+ B
B. 正确) Z. L4 p2 N; r7 X4 L
满分:4 分
3 J9 d# {- J, v1 n( y* ~7. 设有两个串p和q,求q在p中首次出现的位置的运算称作模式匹配
1 `+ j6 S! @4 t {6 F# Y1 M' k- ~A. 错误
3 M; y, L/ I% i$ sB. 正确: }9 _8 P5 l7 I3 h# C) ?. q6 t6 K
满分:4 分
2 \1 ?# H- ~7 f+ U: L8. 算法在发生非法操作时可以作出处理的特性称为健壮性
1 A! `6 g Q* _7 a ^3 C- }1 JA. 错误
1 P% M( O7 X' YB. 正确* ]5 h9 M0 q2 M7 Q# ?9 t6 ~
满分:4 分
6 a3 r5 O$ ?/ S( U9. 在一颗非空二叉树中,叶子节点的总数比度为2的节点总数多1个( L3 j$ U' k. B3 M7 p1 V7 p
A. 错误
1 J: B" S% P9 x7 \* |0 s9 VB. 正确
0 Q% |8 B! j# f6 f, X+ h7 D' ~ 满分:4 分) {9 {$ I$ ~/ X% f# y" Q
10. 在第一趟排序之后,一定能把数据表中最大或最小元素放在其最终的排序算法是冒泡排序" F# p# x1 A. m' G; j
A. 错误
2 E9 S& \; ^. K9 p5 uB. 正确
) v q2 \( n2 w+ }" Y 满分:4 分 ; E7 m% [ N/ {8 w# e) V* X2 N" w
4 Z/ C& T: J8 ^+ |4 l% ^: V
|
|