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

谋学网

谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。
$ _" }  c: P# o8 q3 E0 T
$ I4 ~* u; R3 D" k" s一、单选题（共 20 道试题，共 60 分。）V 1.  经过下列栈的操作后，GetTop(ST)的值是 ( )。InitStack(ST); push(ST,'a'); push(ST,'b'); pop(ST,x);
- J4 n$ G' H3 @( C6 U& XA. a
B. b
C. 1
2 M! O1 ?  f  e" |( d8 pD. 2
      满分：3  分
7 o7 G7 r$ G( O" o/ l0 X( Q2.  由3个结点可以构造出多少种不同的二叉树？( )
& z6 e" l1 Z2 x. bA. 15
* x7 G* p; Y/ h1 BB. 21
, S$ f+ u4 `- l- a6 ~6 mC. 30
D. 33
. q0 C3 u' L/ S, ?5 A4 w' p4 Z6 N      满分：3  分
3.  线索二叉树是一种 ( ) 结构。
9 L) @, Z2 R  |0 fA. 逻辑
0 _% m3 c& T( I) xB. 物理
C. 逻辑和存储
% @+ T- }% h" R6 aD. 线性
7 M. w3 U  p4 B" G* K* B$ i1 S      满分：3  分
- I; l: l- D. I8 `4.  设F是一个森林， B是由F变换得到的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有 ( ) 个。
A. n-1
  E# N( G0 ]5 j( C# H7 r5 M8 CB. n
C. n +1
D. n+2
      满分：3  分
) w4 L9 H3 l- z1 |% w, P, G5.  二叉树在中序线索化后，仍不能有效求解的问题是 ( )。
. Y2 u7 A8 y+ o5 _* ZA. 求指定结点的前序后继
B. 求指定结点的中序前驱
C. 求指定结点的中序后继
D. 求指定结点的后序后继
      满分：3  分
. S* ]5 E3 w0 j1 W8 y2 t$ ?6.  在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行 ( )。
" w4 f# b0 m+ j5 O, SA. p->next = s; s->next = q;
' U: @/ a9 q) `' E# H8 w4 Y) h# sB. s->next = p->next; p->next = s;
C. p->next = s->next; s->next = p;
3 y8 a0 [5 ?8 _7 o; m  sD. q->next = s; s->next = p;
      满分：3  分
$ a% Q/ c' C- j$ T7.  对于3个结点a、b、c，可构成不同的二叉树的棵数为 ( )。
A. 24
# H2 d: k: U& }4 x; gB. 28
C. 30
% U, n! x+ w( E3 jD. 32
" R7 ]# `% v; F+ P6 W3 Y      满分：3  分
7 D; Y: S4 y& _; e" M7 |8.  对于3个结点a、b、c，可构成二叉树的不同形态数为 ( )。
A. 3
B. 4
C. 5
, G/ ^& w; j8 s; r6 \) ]( gD. 6
      满分：3  分
9.  堆的形状是一棵 ( )。
; e% d- S( S0 d. t/ tA. 二叉排序树
' D# U2 a: W# }- G  Q7 d0 l& }B. 满二叉树
C. 完全二叉树
D. AVL树
      满分：3  分
10.  树最适合用来表示 ( )。
! L4 l8 u# ^- O4 AA. 有序数据元素
B. 无序数据元素
( s9 q) f0 x& v6 oC. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
9 k  v1 d) l0 R      满分：3  分
+ _3 K; l: ^, K7 _11.  相对于顺序存储而言，链接存储的优点是 ( )。
A. 随机存取
B. 节省空间
C. 插入、删除操作方便
D. 结点间关系简单
# u+ a  W" G1 e      满分：3  分
12.  一个栈的入栈序列是a、b、c，则栈的不可能的输出序列是 ( )。
A. acb
' }- u5 L  Q- ~( AB. abc
+ m9 o! D4 @  t1 A. F! NC. bca
7 Z! k+ |0 H/ h" v" I1 k$ o- R! DD. cab
      满分：3  分
13.  静态链表中的指针表示的是()。
# l/ O7 P/ Y5 K; C+ x* G% Q. m1 zA. 内存地址
2 q) N4 x4 X) aB. 数组下标
9 i+ s* M: Z& @C. 下一元素地址
D. 左、右子女地址
      满分：3  分
1 y2 w2 P8 M1 {8 L9 q, w14.  引入线索二叉树的目的是 ( )。
A. 加快查找结点的前驱或后继的速度
' ]1 C" ^5 z% V0 _% i( A8 V( @2 @B. 为了能方便地找到双亲
C. 为了能在二叉树中方便地进行插入与删除
' [6 i0 i- X: T4 PD. 使二叉树的遍历结果唯一
7 y: ^- m0 A% m( c$ F3 H      满分：3  分
; T3 E3 `. N( N8 ]; y+ w15.  顺序表中逻辑上相邻的结点其物理位置也 ( )。
5 v+ O8 Y7 D2 F1 sA. 一定相邻
. a0 Y+ \( P, H! c- J" }B. 不必相邻
5 y2 g3 U/ ~! g& d6 S4 @0 MC. 按某种规律排列
2 R" R. t3 [2 ^. sD. 无要求
9 M$ E# U3 d+ M  u' j9 R7 P- w      满分：3  分
) Z" Y- |5 C" o- H6 N16.  在下列情况中，可称为二叉树的是 ( )。
+ @% X( S/ j: F3 r) R5 n' i! UA. 每个结点至多有两棵子树的树
; Y. I7 p% g/ v- |# w- rB. 哈夫曼树
C. 每个结点至多有两棵子树的有序树
8 X- L; d1 |* M6 k* e1 I/ jD. 每个结点只有一棵右子树
1 Q% A  c3 d5 |3 @  r, ~& S      满分：3  分
17.  数据结构中的任一数据元素至多只有一个前驱和一个后继，该数据结构是 ( )
' f. p" ?9 {, K. sA. 线性表
# U& L* P0 n9 v8 b' f8 u$ O1 @+ YB. 广义表
3 l3 N' B$ a. E5 w/ cC. 树形结构
D. 图结构
      满分：3  分
18.  n个结点的线索二叉树上含有的线索数为 ( )。
A. n-1
B. n
C. n +1
0 N& C9 K, w2 v' `  jD. 2n
      满分：3  分
' p, C' B7 H+ T! h19.  某二叉树结点的中序序列为DGBAECHF，后序序列为GDBEHFCA，则该二叉树结点的前序序列为 ( )。
A. AHFECGDB
2 Y& E$ e9 W/ m8 P4 H# @( gB. AHFCEBDG
C. ABDGCEFH
D. BDGAECHF
      满分：3  分
20.  下面关于算法说法错误的是（）。
# Y* {' X' a/ x* Y# N; N* BA. 算法最终必须由计算机程序实现
B. 为解决某问题的算法同为该问题编写的程序含义是相同的
5 c! L. H* i7 Y+ BC. 算法的可行性是指指令不能有二义性
D. 以上几个都是错误的
1 c, }9 L( f* X5 I+ V# k- M& H- j      满分：3  分
* K  S$ V/ Z5 V& f. y# _! P
二、判断题（共 20 道试题，共 40 分。）V 1.  采用二叉链表作为存储结构，树的先根遍历和其相应的二叉树的前序遍历的结果是一样的。
A. 错误
B. 正确
      满分：2  分
2.  用一维数组存储二叉树时，总是以前序遍历顺序存储结点。
9 Y, w9 P' g' b( Y+ a8 \A. 错误
B. 正确
+ I1 L  c9 P$ f' N+ l      满分：2  分
3.  用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
A. 错误
B. 正确
      满分：2  分
6 o3 o0 b% |& r1 c; i6 L& f" A% L4.  若输入序列为1, 2, 3, 4, 5, 6，则通过一个栈可以输出序列1, 5, 4, 6, 2, 3。
7 @* R( L7 {$ n5 x; \9 ^" BA. 错误
B. 正确
      满分：2  分
% v7 _% l4 w- G. L' i3 B' C5.  将森树转成二叉树，根结点没有左子树。
0 g* \- L$ g& ]0 u0 l* ^; C9 PA. 错误
B. 正确
      满分：2  分
. c) h" X0 ~* ?6.  链表的存储密度大于顺序表的存储密度。
A. 错误
; B. b+ W  e# GB. 正确
5 X: e; z# r  w      满分：2  分
7.  二叉树结点的中序遍历序列与前序遍历序列可以唯一地确定该棵二叉树。
7 ^& u9 Z! Z- Y: r/ WA. 错误
2 ]) P1 z- O( P# [+ P! ZB. 正确
& q6 |2 N5 z  h- R      满分：2  分
8.  将森树转成二叉树，根结点没有右子树。
: Z0 j! `- l4 P1 u  t+ k! yA. 错误
& _8 m* Y& @+ c, R" M) s& KB. 正确
      满分：2  分
! T$ x. ~  ~  e' a5 \% S7 ?9.  顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A. 错误
B. 正确
% s; Q# A- W, t9 ]! v5 o9 x/ h) o      满分：2  分
10.  中序线索二叉树的优点是便于在中序下查找前驱结点和后继结点。
' ]) p( G( V' {6 MA. 错误
3 S  c/ c  ^. J- H& [+ ~B. 正确
      满分：2  分
6 c1 N# g+ z- U! h11.  二叉树只能用二叉链表表示。
9 q" n+ u- X  GA. 错误
. Q# x9 ?; X8 Z( z; vB. 正确
) p$ o! X% x( h6 d! n, a5 y- S% v% }      满分：2  分
' ]- j& v: v6 g7 a4 T. I12.  空串是由空格构成的串。
- z; F2 e1 a5 A5 M* iA. 错误
6 v8 d" j4 @  h! _! u5 V" f0 t5 X' EB. 正确
! X4 f% J% W( g, a% M  u      满分：2  分
13.  串是一种数据对象和操作都特殊的线性表。
A. 错误
B. 正确
      满分：2  分
4 M4 k- t$ y6 r4 ?- n7 \9 B14.  二叉树的叶结点，在前序遍历、中序遍历和后序遍历下皆以相同的相对位置出现。
& r2 q8 J  `+ w1 a/ l! SA. 错误
B. 正确
& C  l! i7 ~* S      满分：2  分
* e; V, b( I9 m0 T$ f15.  链表中的表头结点使得插入、删除操作简单。
A. 错误
B. 正确
# ?* I! _+ q2 U; _# ~) Y% S      满分：2  分
  s1 K% A0 I* }/ X16.  栈是实现过程和函数等子程序所必需的结构。
6 E; I9 V  z. s5 W) J5 k" XA. 错误
4 N4 b. O% A! A& I+ \B. 正确
      满分：2  分
17.  为了方便的插入和删除数据，可以使用双向链表来存放数据。
A. 错误
  C6 e# f' |+ |2 U& ~B. 正确
      满分：2  分
18.  栈和队列都是限制存取点的线性结构。
A. 错误
$ p- }1 e2 m  m' }( gB. 正确
6 p2 a* h; r" e# W# q  D* S      满分：2  分
/ b* {  W' R0 Q19.  二叉树结点的前序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。
7 Z8 G6 h+ ]1 SA. 错误
7 \! q& ]* r& a/ \B. 正确
      满分：2  分
( s/ O2 Y/ e" u6 v. Y  p( b4 p20.  串只能按顺序存储方式进行存储。
A. 错误
$ z& E' r9 p- Q! h8 QB. 正确
2 t2 n; l9 K+ P2 F! {      满分：2  分
: \4 v4 D* D' P( V4 N
谋学网: www.mouxue.com 主要提供奥鹏作业资料，奥鹏在线作业资料，奥鹏离线作业资料以及奥鹏毕业论文，致力打造中国最专业远程教育辅导社区。