|
|
福建师范大学5 D6 f4 W* n% ]0 v; D
福师10秋学期《数据结构概论》在线作业二8 c$ _& [9 C; S+ X
单选题! u- Z P! T. v
1.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（ ）次比较。2 k" }+ A$ O/ b6 q8 Y
A. 3
* W a# |9 d8 t( _# S: m0 u: @B. 10
2 E+ r: n) r- I3 l: D$ ^9 yC. 15
7 `( v- b( f" pD. 25* }0 p2 A& _& \/ [# d5 I* y8 w
资料：C6 U; N T; f0 f: b# N8 V9 L1 j
2.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。
! Q* N" k% I4 R" {& W8 I+ Q* @3 ?A. 前序; k* B1 l' d. f# F
B. 中序7 R; X# O i3 x) S3 B8 T
C. 后序
8 U* W/ D* y9 n2 w9 T+ E0 tD. 按层次
# Y, h" V6 c, {( q1 U资料：C6 h$ V$ h J: h: G; a
3.下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。2 e# {# g; Q3 `" C2 x
A. 冒泡( q6 G5 \& x9 [& P
B. 希尔 W; V" f, L: v) ~5 j/ X9 t
C. 快速
0 T. z8 y( F0 _5 P( C) B7 K6 l7 iD. 堆
/ q$ R$ t( V8 V& k8 C资料：C6 }$ p( I" j, t& R
4.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。$ [( X& S) B* o3 V4 T9 j. W
A. 直接插入, E9 Z7 h2 k) G, H8 V5 b, m; H
B. 直接选择( U: Q% L, k6 a3 i) E' _( b
C. 堆" Q7 w+ A$ \+ P' A
D. 快速
$ \- _# S0 n/ _/ V- P& t资料：A- ~9 B& q0 a% c( E; e
5.设无向图的顶点个数为n，则该图最多有（ ）条边。
* Q/ E$ g" {) IA. n-14 R/ W) D& d$ M. w6 W4 N! O
B. n(n-1)/2
, I: t& g# G! u2 Z% e+ w; T0 D; |C. n(n+1)/20 F# P0 a c+ A& E X6 D. C) H2 O2 p
D. 0( B z" ^) t& R3 R: D$ H6 a
资料：B, ^7 O! M+ ^, p
6.算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）0 w) z) h& u# L# v/ r6 C, R
A. ab+cde/** e) W3 z9 M# G% }. X6 n" e
B. abcde/+*+; D0 U1 }! Y8 V+ L
C. abcde/*++
2 n0 I' L# {8 FD. abcde*/++: l3 @. O' S- \" V: p. Z! }
资料：B
( K1 ]. P G/ q# C0 O+ p0 g. f7.要连通具有n个顶点的有向图，至少需要（ ）条边。* B" X. }7 \- b) C ^& ^
A. n-l* ~& T% n# P% s6 K1 z4 I) a
B. n0 D9 f; j! Y4 W$ X7 O
C. n+l0 ?3 T& T" t1 {/ J4 F" D1 n
D. 2n6 l6 P+ v% E; ^- `) X* L
资料：B% P5 C7 x( d$ T. q! B+ V: o
8.若要求尽可能快地对序列进行稳定的排序，则应选（ ）
# s! G X6 H2 V4 L5 }! F* gA. 快速排序4 K+ k& ]4 K: K9 J# P/ n% Q! {
B. 归并排序
" I3 A" X5 V2 e' P% ~0 XC. 冒泡排序' R8 {; ]1 D* I4 G' q7 N, E
D. 堆
Q0 E2 f9 @3 I资料：B
( B! L3 x. H$ N0 P, ?9.表达式a*(b+c)-d的后缀表达式是( )
% T% c/ h+ S( s) zA. abcd*+-
) g! k. \8 G! RB. abc+*d-
2 M7 z# J) f1 i! ~1 qC. abc*+d-
3 x( A8 r; o# c/ RD. -+*abcd \+ X( P( E; O" p/ H+ O! S
资料：B# f/ {8 X0 y; m5 l* t- {* x
10.在下列存储形式中，哪一个不是树的存储形式（ ）
. N& {# @5 O6 p4 R( w; k+ zA. 双亲表示法
( R5 y3 J7 T& g1 }B. 孩子链表表示法; X& h. p: P) |
C. 孩子兄弟表示法& `/ U) P' ~2 Y) n* h5 C" E: l
D. 顺序存储表示法
* s, Q8 e! \/ U1 `" X资料：D
' S5 l3 O4 Z- w1 c; e11.在完全二叉树中，若一个结点是叶结点，则它没（ ）! _3 o( d' q' p: P1 F& [! G, b
A. 左子结点9 ]/ }$ D) q# a5 `* n
B. 右子结点5 f% w$ x% X( `5 ~' R8 Z5 `
C. 左子结点和右子结点6 }/ V+ F& b) N+ ~8 f
D. 左子结点，右子结点和兄弟结点
0 n& O: w6 x3 ^( P, K3 k I4 `: @" U资料：C
' e/ s3 B# q9 h' O4 @% Y7 t0 ^5 y12.广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）Head(Tail(Head(Tail(Tail(A)))))
: L$ b& j8 }9 t7 h. s! v$ i+ MA. （a）
9 R. t; i( w; S# e" ?B. A2 M5 I4 ? W$ Y" n! k' ^
C. a
; T7 M- q9 z2 x' ]9 A) c# dD. (b)
( R1 m2 y8 y1 l$ i6 X资料：D
, w6 v0 d* I8 ? H8 X13.设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）
% j& U5 s) a: }) SA. 1和1" k7 s# K" r- N9 q9 D+ e; ?6 B7 Y
B. 1和3* s0 @$ R3 s9 \. z" u' _) \
C. 1和2
" U% O( [' {( O9 g6 [D. 2和3- }+ }5 r6 m5 K
资料：C1 H. b' {1 [) R' R: Q4 `2 `
14.用二分（对半）查找表的元素的速度比用顺序法（ ）
+ J' O1 ?' s) V* q5 S+ ?0 Y0 iA. 必然快
2 T, J7 ^8 m8 `' FB. 必然慢% s- B+ a. v4 ~9 p' S U7 A
C. 相等+ Y4 \9 [' u2 _% p/ @
D. 不能确定0 ?; G' i( n- f% H& D: ^
资料：D
/ Y8 O- z4 J8 o) j) f& `& A15.数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）: \9 ^7 X; ]8 g( ]- t
A. 55, U4 i7 B2 Q9 L5 k& G2 ?7 _4 l5 W1 p
B. 45
3 n- q3 M# T) o: ]) N$ jC. 368 B% { T4 }& j& d8 E# d n3 u: z- M
D. 165 o" ]0 r- y1 M
资料：B* | j+ Y2 s- |7 g
16.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）
[: {/ @! u3 }% fA. （N+1）/23 \+ B* B1 W' P9 |! U4 T
B. N/2, S/ n( V" \1 r
C. N
: f0 C) @5 g' F2 q$ H9 AD. [（1+N）*N ]/2
& r, i' A _6 ^, _( s) ~. S资料：A
3 Z+ N6 u5 W- N) P8 ~17.关键路径是事件结点网络中（ ）% @& f0 A, b/ |% ~
A. 从源点到汇点的最长路径
& ^! P8 X6 B7 TB. 从源点到汇点的最短路径
% @% G% k8 C* m; V0 lC. 最长回路
* K: [) B, ]; K1 } ~1 t. G; LD. 最短回路
+ X8 E# @/ e+ m, D5 V. H( t2 c- h资料：A
4 g; V3 \, i1 f, q/ W5 w. E% S18.具有10个叶结点的二叉树中有（ ）个度为2的结点，
+ o, x2 ^0 b% mA. 84 \: b( g5 p* T3 Q
B. 9! v* _! X- t1 }) s
C. 10
$ w- y) Z8 P9 E: CD. ll
5 y! W1 h, O! L; z+ x资料：B( f9 X, D) g. T: ^2 ?7 r! M/ {
19.适用于折半查找的表的存储方式及元素排列要求为（ ）* F7 w6 i7 J1 f
A. 链接方式存储，元素无序
' Q3 @/ v8 L( p* VB. 链接方式存储，元素有序9 B R4 _2 y" w
C. 顺序方式存储，元素无序
2 U3 k+ E3 o$ C* Y9 t. vD. 顺序方式存储，元素有序
' K3 O: j5 S% c0 C) B% n资料：D
* }% A9 @( q; M& \20.对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。
& J6 t% g! ]+ t H# ?. G4 |0 h: BA. 选择7 W9 u% ~5 K$ n7 L4 b6 v4 Y* i _
B. 快速5 s' P+ L! C+ q8 @2 `4 h; R
C. 希尔
, M; Q$ w2 g9 }0 w! S) XD. 冒泡
# b& e5 p1 Q, a0 c) E: i资料：C7 o* m# [; V" s
21.求解最短路径的Floyd算法的时间复杂度为（ ）。; T+ p. r9 m( V! r' I' d! k3 ~
A. O（n）
- w8 ~8 G1 E* o6 F" }+ N5 G" rB. O（n+c）
! @; v% _/ k/ g+ z. _! |0 TC. O（n*n）5 M9 v2 ^ t3 S0 T$ b& F( l
D. O（n*n*n）
5 i4 w/ p* I, ~1 _资料：D
- D% K, ?3 v$ I( D2 U22.树的后根遍历序列等同于该树对应的二叉树的（ ）
7 y+ P& @; y& b4 k ZA. 先序序列0 W8 f2 E$ |" V* E6 r" o! z
B. 中序序列7 e( o3 { V( T; p3 |
C. 后序序列- K* s2 i7 b, v& G9 W K' S
D. 都不正确
" i2 S# O& Q: B% |8 g资料：B
5 u+ p4 ~3 m5 d: {: g23.由3 个结点可以构造出多少种不同的二叉树（ ）
7 B% Q, g: I' Q( B7 F, y+ iA. 2
' e8 p! R" e4 L9 H$ L5 cB. 31 |, R( {- m- Q. b
C. 4
- C- I5 `6 h& ~- Z! n6 nD. 56 ?+ t% \* u9 A" |' b3 v7 @
资料：D# a4 @) ~8 b! U$ i5 Y) x" L
24.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）& \5 B3 \* ~6 o% H% j
A. 选择排序法, p- g4 \6 J0 g4 D0 _3 ~8 g! E6 P. s
B. 插入排序法
) {2 }! B* N0 H L; }5 `3 tC. 快速排序法! y+ Y- j1 a* E* M! T
D. 堆积排序法
) c+ C' O- u* Z- ? t1 A& X+ `资料：A
8 _& h; w2 b0 _1 Y) Z( u25.下列排序算法中（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。
& z* Z! @' C" X3 C. \+ O VA. 堆排序5 R+ t) E% @0 \' ], M. ]
B. 冒泡排序
: Q4 P- {; U2 y; ZC. 快速排序
. u1 S, G+ U0 M' M- P( ND. 插入排序
7 y8 V9 O( f8 O i' p资料：D8 A9 }+ P: b! B0 k
1.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（ ）次比较。' m5 \+ T3 x5 A: S r$ B1 h
A. 3
( i) U; j. T) Z9 PB. 101 {+ h: I+ D, L" y
C. 152 n, b( B8 J# U4 B- G9 x' g
D. 25
# E T! _# \! O* k `+ C资料：C
- T, d$ f5 [ w( G1 O" `# H2.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（ ）遍历方法最合适。. [5 H [; V0 P& }) C- J9 x
A. 前序2 q e7 N1 j" E$ w& Y1 j; ~
B. 中序
* E" j9 |% w4 I& C8 J8 dC. 后序+ r1 @5 U) R) A! k7 t
D. 按层次5 B2 z/ ~: K$ L5 i+ Y. s
资料：C
0 s) S; N- }( r" a! l3.下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。: @! f- a6 o0 v$ _' d
A. 冒泡
7 Z. {+ z- C; @" S/ i- H" z' S7 C' EB. 希尔
/ A; k' T! S% R4 \* p& Z7 p9 {1 `+ FC. 快速
: v. T* p+ g/ t" ?& N8 xD. 堆
0 h$ C) ~# Z0 K3 l资料：C
( C0 _. p" t5 r! q" {4.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。
1 A4 \. X' B9 j: N- r8 zA. 直接插入
5 k! |! P* o MB. 直接选择
- K/ o( f" i1 S7 a# |" z9 n6 C, AC. 堆5 h2 Y: m, ?2 h i0 b) F7 ]
D. 快速
2 x$ i4 k7 ~2 H/ j! I; h8 T资料：A1 N' x) E, u6 @0 Y- ^8 Y8 H
5.设无向图的顶点个数为n，则该图最多有（ ）条边。
( p" P. b1 V: C! v4 a0 qA. n-1) \; _* S4 Y! O6 |
B. n(n-1)/2
, [% l$ ~0 s. O. M9 ^C. n(n+1)/2
& A3 T5 y) p, Z- o# `3 uD. 08 n; e3 Z; A- x1 q! X
资料：B" g; F. U! U4 e
6.算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）
, ~7 X7 O3 C3 N: UA. ab+cde/*
/ w6 ^' B$ m! wB. abcde/+*+8 N, V' g/ ~7 B7 s7 p* X
C. abcde/*++
2 r4 K# B' i( S! s( m: QD. abcde*/++
8 j5 d3 E% s0 d9 L: y资料：B
5 G5 F7 B& W* f9 k8 O2 U4 D7.要连通具有n个顶点的有向图，至少需要（ ）条边。
7 {. D0 W4 H- wA. n-l
$ M* N: u; z- A5 }' HB. n
5 x- q# h' A, x7 j4 o. q# M* qC. n+l" F. H" u4 H' Z7 f0 f, S1 t
D. 2n; f B' B3 y; g$ |
资料：B: ~7 y% M, }; O1 n/ ]
8.若要求尽可能快地对序列进行稳定的排序，则应选（ ）* x" J) e( K9 M
A. 快速排序
3 r1 C/ K7 V, F5 gB. 归并排序: A# y9 h* m# w% y4 c
C. 冒泡排序
4 v1 ]! a' u3 l) K cD. 堆
3 k4 n: V" n: r$ O( d* Q: w资料：B
2 _, Y# D; S( }0 M4 M9.表达式a*(b+c)-d的后缀表达式是( )
0 `3 q% c! D3 ^/ y( p. }A. abcd*+-2 L9 |+ ^6 @& A7 o4 @
B. abc+*d-3 w( U6 {& z# f( q2 P' j+ Z) A8 B
C. abc*+d-- _# W! k' _3 _. Y5 G2 }
D. -+*abcd3 v+ y# W g- \3 v" o
资料：久爱奥鹏网：www.92open.com
L: M* c2 L2 K T* a+ l10.在下列存储形式中，哪一个不是树的存储形式（ ）
- d# \2 U4 }) H2 Y' |; X; R; m2 X+ bA. 双亲表示法+ Y/ B' t9 M& N' s, r
B. 孩子链表表示法0 @4 f8 g, o9 N/ E R
C. 孩子兄弟表示法/ }9 a c1 z1 Q2 @$ Q( j9 J, C
D. 顺序存储表示法% \0 v) U! c" k
11.在完全二叉树中，若一个结点是叶结点，则它没（ ）, H2 f# o0 }/ D
A. 左子结点
5 l- ^, t( v ?2 i) W- T1 TB. 右子结点1 ?/ O' {, O1 g: Z- M2 `' V# V
C. 左子结点和右子结点. x& x) `! z0 v q7 m
D. 左子结点，右子结点和兄弟结点
& ?1 [% ? J9 m9 @+ o* w+ t12.广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）Head(Tail(Head(Tail(Tail(A)))))2 `( f; K: J; y
A. （a）: x8 c, S* b0 i: S) X
B. A
1 Q; M( ~& s* [( G5 }. |C. a
' ]6 V! H6 F* tD. (b)
8 E4 Z+ ]- J( Y' }13.设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）2 m/ ?2 X& _9 \
A. 1和1
, w: S9 d- K# u* y- K$ W" `B. 1和3
$ ]: l9 H, D( k8 bC. 1和2# x2 K4 Q/ v' ] n2 X( k$ x; d
14.用二分（对半）查找表的元素的速度比用顺序法（ ）
1 ^5 @+ J/ I1 E6 K$ _4 i, {A. 必然快
: t" k2 T8 G: T( u$ W) TB. 必然慢" K7 w- W* R( o2 [% M# }
C. 相等
/ y! j* Q" ^$ u* MD. 不能确定5 @3 U% N5 S8 H, S
15.数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）
; G3 h2 Q# l$ k6 e; VA. 55* ^/ d4 B* ^6 i, S5 r; |+ x( C
B. 45
2 F) r$ U* a: N) g. C: `C. 36% O( E& j8 E& I* u+ s3 u
D. 16
! a0 G: s' @! T/ U) h16.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）. v) e$ p! E& E- e3 p! a
A. （N+1）/2! M2 M! S, d1 x$ t9 W: s* l
B. N/29 B; v( M: Q& u4 q5 _
C. N" ]1 S$ {$ L: ?0 K- D$ z$ V1 M
D. [（1+N）*N ]/2
' N/ U$ o V @) g9 a2 E% Q6 [; r17.关键路径是事件结点网络中（ ）/ x8 @4 \4 L2 B, a9 Q2 K6 M
A. 从源点到汇点的最长路径! }8 A* p8 d! e( a' l
B. 从源点到汇点的最短路径8 o. v" v% O7 |) n1 }+ i
C. 最长回路1 [7 _6 h3 u, M5 M% c) @$ B5 }
D. 最短回路$ z. l! {7 d$ e6 o* \8 v
18.具有10个叶结点的二叉树中有（ ）个度为2的结点，' E+ q$ @$ u% q0 U/ {8 ]
A. 80 ?9 i: `1 h% X( B
B. 9/ G3 z8 |5 J/ P( e1 q' ]5 n& B) O+ e3 f
C. 10
) g4 C' t- |3 T* H$ u; O- g jD. ll
2 G& H/ r5 o- e19.适用于折半查找的表的存储方式及元素排列要求为（ ）8 P' [0 [( e- w# f9 t8 f, {& }+ A
A. 链接方式存储，元素无序1 R6 v% U& r( r7 F# l" I3 h3 r
B. 链接方式存储，元素有序$ q3 n, p: C" ]& c7 X
C. 顺序方式存储，元素无序& v& C# m$ P3 l: [* h3 T
D. 顺序方式存储，元素有序
% M( ^' F7 w( D" ], t20.对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。, }/ b! ^' e( e; X- c! ?5 C( J
A. 选择
+ O% f1 V4 D" y' E! P7 E. x% G' `B. 快速
4 V% ]3 f0 c8 {0 d1 f; Y: @C. 希尔
1 @# Q9 r# } f0 v" C3 zD. 冒泡; T- c1 \' h0 }# h) w$ |
21.求解最短路径的Floyd算法的时间复杂度为（ ）。* O, _% t4 I: J( w* l9 u
A. O（n）
9 z8 r7 o6 v8 W; _B. O（n+c）
5 S( t1 S8 M r8 K5 N- KC. O（n*n）/ L; e; Z5 V0 y0 M( b
D. O（n*n*n）
0 A6 h9 E$ U+ B1 |4 p$ Q1 A22.树的后根遍历序列等同于该树对应的二叉树的（ ）( C8 Z! ?. G9 r& b
A. 先序序列
x) ]9 F# e4 o$ zB. 中序序列
" u& E: o% E B3 j" ^C. 后序序列+ m6 H8 b. L4 v1 b6 k" C
D. 都不正确- m: [8 J1 w2 w, I& L0 @ ^
23.由3 个结点可以构造出多少种不同的二叉树（ ）
) a- [) x0 S+ f3 s e. H8 XA. 2
- ]. ~: g$ y! Z0 ~+ i. [B. 3
: h/ o9 k( F' P& _6 q7 SC. 48 U/ r- X6 N4 e6 i4 R+ V
D. 5
0 \, L5 ~( W4 `/ G6 s( A. A+ ? t0 q24.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）
& b; R& W, t ^; U% [6 T; MA. 选择排序法1 t9 G' C8 o$ h7 d) l9 n0 L
B. 插入排序法. b( r3 d. K1 M+ ]6 h4 M/ Q2 }
C. 快速排序法5 V. m- p, N" l& Y r; |
D. 堆积排序法- `; s) k1 V# J- z! @6 u7 e4 J7 C' D
25.下列排序算法中（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。
4 b, ^2 z- K: QA. 堆排序+ a2 m& [- _( E6 k$ H, l8 @
B. 冒泡排序
5 Z- Z& E# f1 iC. 快速排序+ D3 q) m, K Q
D. 插入排序
( B4 D1 v1 \, L% t多选题
. ]* Q, S* F% C- p$ j1.有关二叉树下列说法不正确的是（ ）* W! o# p7 E! A( \" ~7 C
A. 二叉树的度为2% i* e) m0 ?3 y$ r1 N
B. 一棵二叉树的度可以小于2
+ _7 }& {9 s1 I UC. 二叉树中至少有一个结点的度为2$ u6 I8 B. ?! z4 K+ c
D. 二叉树中任何一个结点的度都为2
- V9 S: T+ ?2 k9 F- i! l# M L2.在下列情况中，不能为二叉树的是（ ）
2 j8 u0 m% |" t- _A. 每个结点至多有两棵子树的树3 c9 j# g$ v) A; ` |, A
B. 哈夫曼树1 ^8 _* j4 W5 o9 }! c |- Z8 o
C. 每个结点至多有两棵子树的有序树: s3 I1 @% [0 P- B; B' g' [
D. 每个结点只有一棵右子树
6 v8 `8 f. ]- u0 o1 Z3.下面关于二分查找的叙述不正确的是（ ）
0 @$ v/ u9 I: t* F/ z2 pA. 表必须有序，表可以顺序方式存储，也可以链表方式存储( B$ I. V! X1 o
B. 表必须有序，而且只能从小到大排列
$ N$ H- }* V( T8 JC. 表必须有序且表中数据必须是整型，实型或字符型
& k8 C! p3 \( H' H! h' qD. 表必须有序，且表只能以顺序方式存储+ y7 R. R% `4 l3 T
4.下列哪种图的邻接矩阵不是对称矩阵（ ）
2 s( C; ], ]( Y$ ]A. 有向图
: H' i* g" Z: HB. 无向图4 n" h0 c- {4 D: W- r( s
C. AOV网
% Z0 V5 P. p \. t/ yD. AOE网
: h: W& W- @6 l5.下面说法正确的是（ ） }+ M4 K7 T c1 t5 U. t2 b
A. 广义表的表头总是一个广义表- Z# r$ b2 S# T- m; R6 R
B. 广义表的表尾总是一个广义表
2 b! d' }1 w& XC. 广义表难以用顺序存储结构
! j+ X* L5 g$ x zD. 广义表可以是一个多层次的结构, o" ~: q: }5 l: W6 Z
1.有关二叉树下列说法不正确的是（ ）
. ]6 C6 g% x+ G- \ l3 YA. 二叉树的度为2 L z, I# u( E ^
B. 一棵二叉树的度可以小于2
1 F# K' k6 Y9 ~! i6 s! @" @" NC. 二叉树中至少有一个结点的度为2
; `5 b" f1 B; i7 v" l5 JD. 二叉树中任何一个结点的度都为2- ]; C" s, W7 j+ d c
2.在下列情况中，不能为二叉树的是（ ）
% ]6 \6 X- O# w# D- i/ ]4 zA. 每个结点至多有两棵子树的树) s4 ?% L3 b" D) n1 o2 I
B. 哈夫曼树* w ?# C! {7 Y% B, a
C. 每个结点至多有两棵子树的有序树
8 O& v1 f$ Q$ E4 |! q, hD. 每个结点只有一棵右子树
0 C, `5 r: v. ^3.下面关于二分查找的叙述不正确的是（ ）: A% z' ~2 K, g6 G2 `- `- g
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
7 q, Q' O7 h9 iB. 表必须有序，而且只能从小到大排列+ g( x5 E2 \& @. A! f4 W
C. 表必须有序且表中数据必须是整型，实型或字符型5 t+ p% g0 u4 J6 ]! H
D. 表必须有序，且表只能以顺序方式存储
0 ~) {5 j' v7 Q( A4.下列哪种图的邻接矩阵不是对称矩阵（ ）
! e7 E0 d" M. d% e3 PA. 有向图
( I: v7 f0 B* j2 N) ?; K+ I( P! WB. 无向图
) {; }/ w# I8 [5 b+ x9 [: O' RC. AOV网; }6 J# f% \' T7 D; ^
D. AOE网
* N( M5 L/ Y1 U# C5.下面说法正确的是（ ）2 Z+ O8 ]9 y6 ?! e8 M( j
A. 广义表的表头总是一个广义表7 V+ N' m/ H: J$ T7 @6 \
B. 广义表的表尾总是一个广义表0 e9 ~) b6 \) U8 e B, W8 K
C. 广义表难以用顺序存储结构' y/ V0 S- e8 ^3 h9 M
D. 广义表可以是一个多层次的结构8 Y! n( G& n E; s- Y
判断题# t$ x( i+ W+ p8 ], [6 |3 m( T
1.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的（ ）
% E" U' M* I1 ~' ^/ C: mA. 错误7 o7 X& n) S" H: j) P; F4 Z
B. 正确$ x9 y2 A/ b6 q) {8 ^; R
2.二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）（ ）5 G4 S, _* i _# ?
A. 错误2 m/ _! V# J6 D. q; {% C
B. 正确
5 x1 U0 I1 O8 ^* f( b) e; t3.当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省（ ）。5 R+ J# n& a w% l/ Y7 t- ^
A. 错误
9 V+ U7 y0 ^( c6 I/ o1 iB. 正确: P. t4 r& i {" w1 U
4.任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间（ ）
# E% H) S$ Y" ^A. 错误- U6 T9 k5 R" B* h1 b1 U0 ~
B. 正确
9 i5 N0 j9 ~- K; c& \4 |5.查找相同结点的效率折半查找总比顺序查找高
" g2 y: z9 R2 Y+ JA. 错误; W: W+ x, }& j8 G8 U
B. 正确
% c: R* a( l5 ]- |! p) L6.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大（ ）) h; T$ T H0 f
A. 错误
4 m% z" h1 q; c9 YB. 正确/ J* S2 q! r: r$ u' \
7.对于有N个结点的二叉树，其高度为log2n（ ）
a& }1 U1 }! O3 L& B& cA. 错误
7 {/ F5 E4 X; MB. 正确
0 e: P b9 U" V# m8.折半查找法的查找速度一定比顺序查找法快（ ）9 `. f* R3 r5 o o
A. 错误3 r: p# n) }4 _- n, V2 X( \+ z
B. 正确
: Y+ i( E1 E. H, w9.顺序查找法适用于存储结构为顺序或链接存储的线性表（ ）! n8 c% ~( H# q0 B6 j9 `" |
A. 错误7 Y& f3 U# f. z3 e8 n+ S8 u
B. 正确$ d3 X- A/ g# q# o( Z z: E1 q9 m
10.完全二叉树一定存在度为1的结点（ ）
2 _, m4 f4 S! c. \) G' _7 L+ L8 iA. 错误
1 r ]$ E. I( q$ H- E5 jB. 正确; t1 t/ }. T5 d H6 |
11.若一个广义表的表头为空表，则此广义表亦为空表（ ）
% G, a" g5 \* v) \- F; Z+ dA. 错误
3 P/ b ]2 m$ Q$ IB. 正确
% {$ a1 x* p9 y. A. e, {12.在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面（ ）
9 o- o4 y: G7 e+ n) m" G bA. 错误
! G! d: P! A1 x1 k8 S: fB. 正确
4 Q9 E! Z- K/ Z4 Q+ d& e @13.用一维数组存储二叉树时，总是以前序遍历顺序存储结点（ ）# W3 C4 l9 Y8 h9 _5 M3 L+ {7 f: d: _
A. 错误1 m5 ~5 F) w5 x- j
B. 正确, ]- B1 G) Z- j5 M4 M
14.广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值（ ）9 f! y" ^* M, p4 c$ p$ v
A. 错误( |5 o" S+ T1 u% t- B9 M& F
B. 正确
9 T2 Z8 y1 v, E; k15.对一棵二叉树进行层次遍历时，应借助于一个栈（ ）
. {: ~: M" Y3 u+ Q2 {* Z! _7 lA. 错误* x9 ~& @7 ^ i% p& y3 _% `( Z& S1 w
B. 正确
0 ]) ]# ~6 h( h# _8 o) o* J16.二叉树是度为2的有序树（ ）
" L+ W8 v* x0 v* ]# WA. 错误, [* ]& {, y9 g0 _1 s5 a
B. 正确+ ?7 ~# f' r6 O- N4 ? C& u4 q, q/ D. n
17.二维以上的数组其实是一种特殊的广义表（ ）
k, m2 x3 N. I8 N/ B0 _1 lA. 错误
/ Y$ M- J7 p. l1 F# t" q; {B. 正确, U: L& ]* m. R; `' Z+ U
18.任何一棵二叉树都可以不用栈实现前序线索树的前序遍历（ ）4 B: V" s# d* k. f0 }4 `
A. 错误
" W* z( L( n6 c* U+ a7 p' G, X- qB. 正确
7 t* q( O; h7 |8 }- R: h19.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表（ ）
% z0 d7 c! M& \6 w. gA. 错误
; }# \$ l3 }6 r6 W, DB. 正确
3 v3 [2 V/ s5 A; Y20.用树的前序遍历和中序遍历可以导出树的后序遍历（ ）
& D9 S+ i9 u$ }1 R; HA. 错误9 Q, I6 G, n( }1 w/ g
B. 正确
- M" B5 s. p4 M1.一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的（ ）
1 a9 F& m) z( ]2 gA. 错误6 l2 J9 g$ I5 r4 V: B- K
B. 正确
+ S& k8 e( `3 z( p$ h2 ~0 ]/ H2.二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）（ ）
' i0 F7 J9 ^4 B& dA. 错误6 c: I8 W9 a W
B. 正确0 Q5 }# H& E* A, K, _
3.当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省（ ）。$ r! ^! G. ?" V
A. 错误8 O( E. \ V# H; R8 Y
B. 正确2 ^# E" C/ z5 J! l5 a) U
4.任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间（ ）. g5 h6 H4 E) m, V% V, a
A. 错误
' G: r$ P/ q* ~$ s4 CB. 正确
- F4 @4 v+ ^# ]) s4 O" R5.查找相同结点的效率折半查找总比顺序查找高
0 ]( l6 R. j2 F* ^A. 错误
8 Z3 N( X4 \ ?. _( ^B. 正确$ Y! m2 w# x. ^2 a5 ^
6.就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大（ ）
8 F, Q1 ~) `/ W$ Q9 [A. 错误
/ e: q" @3 ^- ~( RB. 正确
" W0 V7 r2 ]) K: Y: r9 r/ J7.对于有N个结点的二叉树，其高度为log2n（ ）' r$ |5 O2 }3 V
A. 错误8 [# |( r: Y4 B% z: t! B/ M& Q
B. 正确
* t/ s# Z; p' Y* @4 ^5 A" _; ]8 A8.折半查找法的查找速度一定比顺序查找法快（ ）
$ _2 k8 z* p, S# t: MA. 错误% d' e& x# T7 H ^( ` u! Z
B. 正确
: l$ y" P H- ^/ ^$ Y9.顺序查找法适用于存储结构为顺序或链接存储的线性表（ ）6 Q3 A" |8 V: ^# b: `* A
A. 错误! S) E0 P+ t; p c
B. 正确& a/ [* N8 N, t6 |! u- @# } S' J
10.完全二叉树一定存在度为1的结点（ ）8 [, O0 V# \& m
A. 错误" |( I$ N0 G! @# k+ h. S
B. 正确0 t) E3 W! B& v6 z) N
11.若一个广义表的表头为空表，则此广义表亦为空表（ ）7 ~1 i i$ X9 F1 Q
A. 错误2 J0 o4 y4 Z* R& I
B. 正确
- @% q* D( C1 H' E6 z9 P% H) h {$ j12.在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面（ ）
% E: a% h! `) z7 p% cA. 错误
& r: Y1 P% {6 w9 o; }) e. YB. 正确8 B2 S3 t. m8 d2 Z& z
13.用一维数组存储二叉树时，总是以前序遍历顺序存储结点（ ）
2 b' q" |7 c* l8 @4 B8 ~" n8 WA. 错误
- d3 o& g( a! P3 S( w5 LB. 正确
. X+ N) p, y. L( N: }8 r14.广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值（ ）
. E5 j& U0 l. m' CA. 错误6 r; y. z* ~9 U: n
B. 正确
8 \( |9 W- H# h1 k$ Y) g15.对一棵二叉树进行层次遍历时，应借助于一个栈（ ）0 q E7 v- c! _4 u _9 a
A. 错误
% h1 p, L* c/ t: l/ V7 ^+ OB. 正确* ?* S/ e7 M0 ?4 U
16.二叉树是度为2的有序树（ ）
* }$ b- n, Y7 I) n/ k$ I& Z8 j$ m9 FA. 错误
+ r' e; Q A" qB. 正确" I: P( B! v; _- ~8 n
17.二维以上的数组其实是一种特殊的广义表（ ）
8 y( W: F# W/ t5 b8 Z2 L9 hA. 错误
e! M* @7 t) k2 X4 mB. 正确2 q' r( C y. v
18.任何一棵二叉树都可以不用栈实现前序线索树的前序遍历（ ）
5 @4 [, m8 i% j. b1 I5 N L! vA. 错误
b$ T% m) X( J4 uB. 正确
; {% a' t" h+ r$ B. M3 y19.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表（ ）
$ z0 m$ b- Y8 k9 rA. 错误- ~- ]8 B# z4 t- L# C9 y
B. 正确
# _! I8 R. A5 Q8 u20.用树的前序遍历和中序遍历可以导出树的后序遍历（ ）$ p; B M. M/ B7 B) z
A. 错误
/ p; ]+ }* v: K" d* jB. 正确 |
|
IP卡
狗仔卡
发表于 2011-2-12 11:08:32
微信登陆 
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
客服一
