东师《数据结构》11春第一次在线作业

久爱奥鹏晓林

一、单选题（共 20 道试题，共 60 分。）V 1.  如果BT是由有序树T转换而来的二叉树，那么T中结点的后根序列就是BT中结点的 ( ) 序列。
A. 前序
B. 中序
3 x' q3 W/ o5 z! W( J; `: FC. 后序
D. 层次次序
      满分：3  分
2.  已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为LOC(a0)，则第i个结点的地址为 ( )。
$ N; U3 U3 m0 g# RA. LOC(a0)+(i-1)*c
# g" P/ B9 j5 {: c$ X& pB. LOC(a0)+i*c
  P6 d! V8 i3 Y' I* F5 XC. LOC(a0)-i*c
D. LOC(a0)+(i+1)*c
  }- L6 ]* U. @/ M9 v      满分：3  分
! `: k) E1 \) @; s; C( d% w3.  在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行 ( )。
A. p->next = s; s->next = q;
B. s->next = p->next; p->next = s;
C. p->next = s->next; s->next = p;
D. q->next = s; s->next = p;
6 [2 y9 p: K0 c) H* t  T8 t& o      满分：3  分
6 \( u* E3 s6 H4 S: ]  v4.  在线索二叉树中，p所指结点没有左子树的充要条件是 ( )。
  p- ^) `# s& z$ B+ I4 P! DA. p->lchild = = NULL
* D  l. [  d& w5 q: Y9 OB. p->ltag = = 1
3 d: |, D) A5 J. W8 w. b/ jC. p->ltag = = 1且p->lchild = = NULL
1 `2 M( d% _; O" _( HD. p->ltag = = 0
      满分：3  分
5.  插入、删除只能在同一端进行的线性表，称为 ( )。
A. 队列
B. 循环队列
8 r# A' @* s1 N! s) z; oC. 栈
" R; ~. E% M% x9 C* f# vD. 循环栈
      满分：3  分
) R# d/ C# v: _3 {$ r6.  在具有n个结点的完全二叉树中，若设根结点的编号为1，则编号为i(i>1)的结点的双亲结点的编号是 ( )。
A. 2i
. [" f% x3 R3 S4 \6 {B. 2i+1
C. ëi/2û
& S, Y. E8 W9 [- t+ ]D. 不存在
2 H- v! \4 A' r, a# W      满分：3  分
7.  判断线索二叉树中某结点p有左子女的条件是 ( )。
% S, B- C) Y1 Q2 `" w/ C- @1 @A. p ! = NULL
/ v- p, `+ p8 C, {+ C9 l/ I- zB. p->lchild ! = NULL
: w' T. G3 [8 J/ _0 v9 {C. p->ltag = = 0
D. p->ltag = = 1
      满分：3  分
8.  每一个(存储)结点不仅含有一个数据元素，还包含一组指针，该存储方式是 ( )。
A. 顺序存储
% N+ n8 A, d  Q' @B. 链接存储
6 K' Q: W" I# L2 s7 j: ?C. 索引存储
& O: _6 V9 o2 {, \; oD. 散列存储
      满分：3  分
3 u" P) D1 _8 z9.  线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ( )。
5 d. p( w4 {0 a, y8 KA. 必须是连续的
$ y( c- h5 C) u" [B. 部分地址必须是连续的
0 Y! p" j) `- J& d# LC. 一定是不连续的
( O9 L9 G/ c6 UD. 连续或不连续都可以
+ W1 J9 K% @* ^$ ]7 w# X4 [      满分：3  分
4 Y! ]4 Z. p2 \10.  设根结点的层数为0，若高度为h的二叉树上只有度为0和度为2的结点，则此二叉树上所包含的结点数至少为 ( )。
  R  S, w5 [" |% ]A. h+1
B. 2h-1
C. 2h
D. 2h+1
5 b) y% w+ M9 @( W# o      满分：3  分
11.  递归过程的实现需用到 ( )。
% ^$ _7 t# g% S7 i& TA. 线性表
0 C% P( w8 ]" CB. 链表
C. 栈
D. 队列
* j0 H" t, Y0 g) t0 J      满分：3  分
0 h- W' M3 H& Y12.  对于3个结点a、b、c，可构成不同的二叉树的棵数为 ( )。
A. 24
B. 28
C. 30
5 Q. w! f5 L: j+ [. OD. 32
      满分：3  分
7 u  N* K  E: H# ]7 R13.  下面关于算法说法错误的是（）。
A. 算法最终必须由计算机程序实现
B. 为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性
D. 以上几个都是错误的
7 C* W6 f, \& w6 v2 }4 U      满分：3  分
9 c# s% ^# G" F14.  一个顺序栈一旦被说明，其占用空间的大小 ( )。
" s/ Q* i/ i# F) z( s& \' KA. 可以改变
B. 不能固定
C. 已固定
D. 动态变化
- `) o, z+ J; m: [0 c      满分：3  分
& K3 Q( k7 Z2 g  B2 C2 _% O% o  ]  {% i15.  若一组记录的排序码为 { 46,79,56,38,40,84 }，则利用堆排序的方法建立的初始堆为 ( )。
$ d8 ^' ^" n! mA. 79,46,56,38,40,84
# ^" G0 {. y* x9 XB. 84,79,56,38,40,46
- L# o9 s1 q# f+ z. D. [C. 84,79,56,46,40,38
5 r2 j% i+ k) Q/ F1 f7 U& eD. 84,56,79,40,46,38
# ^0 {4 B  f: c6 ]6 `0 `      满分：3  分
16.  设二叉树有n个结点且根结点的层数为0，则二叉树的高度为 ( )。
5 i" f$ w; U1 R+ l. o' D7 mA. n-1
B. élog2(n+1)ù -1
C. ëlog2nû
D. 不确定
      满分：3  分
17.  一个栈的入栈序列是a、b、c，则栈的不可能的输出序列是 ( )。
A. acb
B. abc
0 l2 X& N+ D8 {1 h  _" YC. bca
1 G; m5 J5 _/ u& v- ND. cab
      满分：3  分
4 m9 h0 O* L. Z: h/ x+ d18.  在数据结构中，从逻辑上可以把数据结构分成 ( )。
8 r( W: s) m* ~! iA. 动态结构和静态结构
B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构
D. 内部结构和外部结构
      满分：3  分
/ f. e; N# ?6 l6 u- ?+ E19.  从一个栈顶指针top的链栈中删除一个结点时，用x保存被删除的元素，执行 ( )。
6 t) Y( ]+ j& K0 |3 gA. x = top; top = top->next;
B. top = top->next; x = top->data;
C. x = top->data;
D. x = top->data; top = top->next;
      满分：3  分
' O0 X* s5 p$ `; L+ {1 ?20.  若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是 ( )。
A. 根结点无右子树的二叉树
B. 根结点无左子树的二叉树
& ^( |  J& N) k6 c( F6 i" `C. 根结点可能有左子树和必有右子树
' {$ s* J! b: H5 ~& x: AD. 各结点只有一个子女的二叉树
      满分：3  分
二、判断题（共 20 道试题，共 40 分。）V 1.  顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
2 |% Z% F/ i, y9 x' o1 BA. 错误
' I/ _8 d+ M' @  wB. 正确
      满分：2  分
2.  树与二叉树是两种不同的树形结构。
3 @. }/ V! d; T1 eA. 错误
B. 正确
7 c4 t1 G" B5 p5 Z      满分：2  分
3.  任何一棵二叉树都可以不用栈实现前序线索二叉树的前序遍历。
( p; S& [4 \3 IA. 错误
- m1 w6 d/ I) L* C7 K: ^# IB. 正确
      满分：2  分
* p0 M  d0 j. {4 _4.  给定一棵树，可以找到唯一的一棵二叉树与之对应。
A. 错误
B. 正确
8 y. U8 }5 D$ y" d' e6 O% t0 d7 ?      满分：2  分
5.  对于查找运算来说，链接存储结构一定优于顺序存储结构。
A. 错误
) Z. S7 @- |% J6 sB. 正确
8 ^% t6 W& n1 f8 ~( E8 N      满分：2  分
$ @% s" v, A$ M& p$ u" I1 w6.  通常使用队列来处理函数或过程的调用。
; [$ O8 Y$ f" b3 W! |A. 错误
B. 正确
      满分：2  分
7.  栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。
A. 错误
% G" K& f$ f5 u' i5 qB. 正确
. F9 q- s$ Y3 T! Q* e) o      满分：2  分
8.  循环队列也存在空间溢出问题。
5 Z: y3 X) @# q' VA. 错误
B. 正确
      满分：2  分
9.  用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
A. 错误
( o/ Y  X- P! z/ m& tB. 正确
; m5 E; Z: ~; W3 l- p( T) V      满分：2  分
10.  结点(数据元素)是数据的最小单位。
A. 错误
! u5 g& O% L6 H' |5 U9 @) XB. 正确
6 I5 I5 s: z7 Z4 @, p      满分：2  分
  X: O- Q4 l& p% c5 h11.  链接存储结构属动态存储方式。
A. 错误
B. 正确
3 e  ^; R7 H% X* Z3 \  I" w7 k      满分：2  分
# j$ F- h6 [3 U& b2 g+ K0 C12.  链表中的表头结点仅起到标识的作用。
A. 错误
B. 正确
! j' f$ j( }3 t! [      满分：2  分
# F8 ~2 ~/ `! j) I6 a13.  顺序存储结构的主要缺点是不利于插入、删除操作。
, Q5 M1 I9 W$ M# u' HA. 错误
B. 正确
/ _) c" M9 O5 T. U1 M" |      满分：2  分
" O5 Y0 B1 j: A! P; X1 {) ?14.  算法的优劣与算法描述语言无关，但与所用计算机有关。
A. 错误
B. 正确
+ r$ B  u. x0 C! d      满分：2  分
: }+ E4 x! f$ ?& B15.  当一棵具有m个叶结点的二叉树的 WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。
A. 错误
: J8 n, d3 ^0 G5 gB. 正确
      满分：2  分
+ u' m4 O' d3 d: @- f2 _8 D16.  在指定结点之后插入新结点时，双链表比单链表更方便。
A. 错误
( A. X8 R5 I4 G- eB. 正确
+ |0 y/ P, d, J$ b- ]/ ~" {, G      满分：2  分
17.  采用二叉链表作为存储结构，树的先根遍历和其相应的二叉树的前序遍历的结果是一样的。
A. 错误
- r8 g# ^6 q  v6 ~& JB. 正确
      满分：2  分
18.  二叉树结点的前序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。
! x4 v1 }8 q4 F+ `# v. RA. 错误
) }7 ~  C$ ~- H6 C/ |9 oB. 正确
: R7 d' X: s1 O( m: m% |      满分：2  分
$ `7 d% v+ Y& j# Z7 `19.  任何二叉树的后序线索树进行后序遍历时都必须用栈。
A. 错误
) N! n8 N2 H, ^B. 正确
9 x; `7 Y* u6 R! r4 d0 u& |      满分：2  分
( d% k1 a$ j4 D  Z5 ~20.  将一棵树转成二叉树，根结点没有左子树。
A. 错误
' x. l/ N/ `4 O# W; hB. 正确
      满分：2  分