东师《数据结构（高起专）》2012秋第一次在线作业（随机）

谋学网

谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料和奥鹏毕业论文以及提供代做作业服务，致力打造中国最专业远程教育辅导社区
3 n. y' g% n, x
一、单选题（共 20 道试题，共 60 分。）V 1.  设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为 ( )。
A. 求子串
B. 求串长
C. 联接
D. 模式匹配
' J* O2 N+ m" F, u, a      满分：3  分
2.  二叉树在中序线索化后，仍不能有效求解的问题是 ( )。
; A  J4 p$ q( P6 D/ c% ^A. 求指定结点的前序后继
B. 求指定结点的中序前驱
9 T4 J: R1 I/ b! ~2 R' V, wC. 求指定结点的中序后继
D. 求指定结点的后序后继
      满分：3  分
3.  若X是中序线索二叉树中一个有右子女的结点，且X不为根，则X的中序后继为 ( )。
6 [% k7 ]; b* |* n% {A. X的双亲
B. X的右子树中最左下的结点
C. X的左子树中最右下的结点
D. X的右子树中最左下的叶结点
      满分：3  分
  v& q. m4 l0 Z6 a( P8 q4.  一个顺序栈一旦被说明，其占用空间的大小 ( )。
A. 可以改变
B. 不能固定
C. 已固定
D. 动态变化
      满分：3  分
5.  一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数是：( )。
* b% Q+ G+ U; F3 r0 ^. i! h5 U! u5 ~A. 不确定
% x9 k1 E' _6 DB. 0
8 K$ G. P' [/ pC. 1
D. 2
( t4 W. i! _+ {2 Z3 P) @      满分：3  分
- ^# {8 h' N) j: @6.  下面关于算法说法错误的是（）。
A. 算法最终必须由计算机程序实现
B. 为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性
D. 以上几个都是错误的
      满分：3  分
$ W' d. q( k' ]  C( N' l* m7.  经过下列栈的操作后，GetTop(ST)的值是 ( )。InitStack(ST); push(ST,'a'); push(ST,'b'); pop(ST,x);
A. a
B. b
. |! |5 S7 B0 L! H3 U& ^C. 1
D. 2
2 Z/ A- H4 T" f. V0 b( E      满分：3  分
8.  四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU,x)操作后，队头元素是 ( )。
; n' ^; r7 J9 H" ]( y# RA. U
B. V
8 Z% A- \# o% C8 Y# zC. X
D. Y
      满分：3  分
2 X' H# V6 X0 [0 r! i' \7 }. I9.  插入、删除只能在同一端进行的线性表，称为 ( )。
  {4 G4 l/ i1 @+ pA. 队列
B. 循环队列
& Z4 v5 i! B2 j& J8 r( z2 RC. 栈
$ B: r& _; d3 `/ J9 E) H% k/ oD. 循环栈
, ^6 f! i. ^6 y% B      满分：3  分
10.  一个栈的入栈序列是a、b、c、d，则栈的不可能的输出序列是 ( )。
/ Q, q& L# O6 d/ D/ |3 NA. acbd
8 O( U& a# }4 e& f6 ^B. abcd
C. dbca
6 H3 v/ A- J* t9 XD. adcb
      满分：3  分
11.  串是一种特殊的线性表，其特殊性体现在 ( )。
& U+ U* x* s9 bA. 可以顺序存储
% C* G9 x7 Y  T  |  ^: YB. 数据元素是一个字符
2 z3 N8 e5 S! dC. 可以链接存储
5 ~) I8 y; k& P  o0 ], dD. 数据元素可以是多个字符
      满分：3  分
12.  设s1 = "abc" ，则strlen(s1) = ( )。
+ v, y! x/ h& qA. 0
6 L% O$ S0 S6 N3 a1 eB. 1
/ @9 f: F1 `  ^' I- mC. 2
D. 3
  {5 ~  ^" U: o3 F1 y      满分：3  分
8 s$ M( n& j4 Z- P& J6 X7 ~13.  在下面的叙述中，正确的是 ( )。
A. 树的先根遍历序列与其对应的二叉树的后序遍历序列相同
3 ~& B8 K" _/ V9 sB. 树的后根遍历序列与其对应的二叉树的前序遍历序列相同
C. 树的后根遍历序列与其对应的二叉树的中序遍历序列相同
D. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同
8 e* g" o/ m* l) t      满分：3  分
14.  从一个栈顶指针top的链栈中删除一个结点时，用x保存被删除的元素，执行 ( )。
A. x = top; top = top->next;
B. top = top->next; x = top->data;
3 [* s; A+ F' l, Y! J& N& PC. x = top->data;
! {0 n* F6 q0 s; n& {D. x = top->data; top = top->next;
1 Z; W. H( S1 M* ?3 a      满分：3  分
15.  一个算法应该是（）。
A. 程序
B. 问题求解步骤的描述
C. 要满足五个基本特性
/ H8 l1 V* g7 m9 M/ H# d& BD. A和C
      满分：3  分
16.  在下列情况中，可称为二叉树的是 ( )。
A. 每个结点至多有两棵子树的树
2 Q- v5 `6 X, C7 tB. 哈夫曼树
C. 每个结点至多有两棵子树的有序树
D. 每个结点只有一棵右子树
      满分：3  分
) n2 ~( h3 r1 G7 i/ Z  y17.  由3个结点可以构造出多少种不同的二叉树？( )
A. 15
B. 21
C. 30
D. 33
/ p. ]( m; H/ m7 O) I3 s( R      满分：3  分
18.  某二叉树结点的前序序列为ECBAD，中序序列为EBCDA，则该二叉树结点的后序序列为 ( )。
A. ABCED
& ^7 P6 b& ~1 Z9 @- |B. DECAB
' H5 ^) A8 U% ?! ]C. DEABC
. ^1 }0 f6 M  v7 ~$ I. WD. BDACE
7 X" h9 ^6 w* T2 ?8 X6 Y( L& u4 B' l      满分：3  分
19.  树最适合用来表示 ( )。
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
5 @9 }  o* {+ J3 W6 d& W  e1 Q6 K3 K& y      满分：3  分
20.  顺序表中逻辑上相邻的结点其物理位置也 ( )。
+ r! u! r6 f% C$ U% S; i% M# kA. 一定相邻
B. 不必相邻
C. 按某种规律排列
& Z4 k( C# r5 B! X( k3 u4 RD. 无要求
      满分：3  分

二、判断题（共 20 道试题，共 40 分。）V 1.  健壮的算法不会因非法的输人数据而出现莫名其妙的状态。
A. 错误
B. 正确
& k: l; e1 b* B. ~4 I      满分：2  分
2.  循环队列也存在空间溢出问题。
A. 错误
B. 正确
4 g6 I5 d" u: s( a  [# V      满分：2  分
" d" J% ~3 [0 |( K; p: l7 V3.  二叉树的前序遍历序列中，任意一个结点均处在其子女结点( 若存在 )的前面。
& T7 P2 `- A: ]) KA. 错误
9 H/ _; W4 S! ~% {; B3 \0 t* G; AB. 正确
- k2 r: [- o8 J" U: n' L4 |      满分：2  分
* @! t6 a( I) ~7 c9 V( d. _0 L4.  将一棵树转成二叉树，根结点没有右子树。
8 y, \' ~- X9 Z7 I: X: l6 aA. 错误
; B  u5 d" Y1 w7 R' ?7 BB. 正确
! Q; V- p7 b6 _) ~) r      满分：2  分
5.  在中序线索二叉树中，每一非空的线索均指向其祖先结点。
4 `) Y4 e- L  l0 e( mA. 错误
- i8 Y' F( p& x  g; F4 U0 `1 z+ _" dB. 正确
1 {& @! ^4 K1 y# H* `! I      满分：2  分
3 I% |- ~- R! J0 C6.  任何一棵二叉树都可以不用栈实现前序线索二叉树的前序遍历。
A. 错误
B. 正确
      满分：2  分
# E$ I, e5 Y9 `7 E( t7.  链表的存储密度大于顺序表的存储密度。
A. 错误
5 Z/ V* J3 Z2 r0 F# K( M, c+ m! }B. 正确
      满分：2  分
- H: J' W/ E7 x4 B+ S. g5 O( |8.  对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。
) q! q' m' Y7 J( |, O0 o( oA. 错误
B. 正确
      满分：2  分
9.  完全二叉树的存储结构通常采用顺序存储结构。
* N% T6 o3 F2 W+ W( oA. 错误
B. 正确
      满分：2  分
10.  数据的存储结构是数据的逻辑结构在计算机存储器上的实现，它是依赖于计算机的。
A. 错误
  J1 x& L  e! {9 AB. 正确
      满分：2  分
11.  在二叉树中插入结点，则此二叉树便不再是二叉树了。
A. 错误
7 t$ I* f4 g. d( B+ t/ z8 L- _B. 正确
      满分：2  分
12.  哈夫曼树是带权 ( 外部 ) 路径长度最短的树，路径上权值较大的结点离根较近。
A. 错误
3 D! y4 [8 C4 H+ R" n3 }# C) OB. 正确
      满分：2  分
13.  顺序存储方式只能用于存储线性结构。
A. 错误
) c/ T* T6 Z4 a& y8 H+ y4 BB. 正确
      满分：2  分
14.  链接存储结构属静态存储方式。
A. 错误
* Y) y  S+ N4 Y0 E1 {- N4 T" aB. 正确
6 C# O" ^" z9 _6 _# m2 y1 l  u, O      满分：2  分
15.  二叉树的中序遍历序列中，任意一个结点均处在其左子女结点( 若存在 )的后面。
# O- F1 z  `  u) H6 Z; |A. 错误
B. 正确
      满分：2  分
9 l3 |* ]4 W/ F% k* M0 W16.  串是一种数据对象和操作都特殊的线性表。
A. 错误
# ?1 \# b' q" X: b% v3 gB. 正确
! u2 r+ W+ }) a      满分：2  分
17.  链表与顺序存储结构相比，在链表中进行插入、删除操作的效率高。
A. 错误
B. 正确
      满分：2  分
, v' f' K3 U1 U. C18.  后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。
A. 错误
* _. F9 l! l2 _% ^B. 正确
      满分：2  分
19.  树与二叉树是两种不同的树形结构。
% @" D0 e5 t; t" J9 ]9 t  z5 vA. 错误
B. 正确
      满分：2  分
20.  数据的存储(物理)结构是指数据在计算机内的实际存储形式。
A. 错误
B. 正确
      满分：2  分
& A5 A0 P7 S& O9 `( d" x0 T( t
8 H/ E0 z+ `9 o- X! \谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料和奥鹏毕业论文以及提供代做作业服务，致力打造中国最专业远程教育辅导社区