数据结构复习题及答案(2)

D. 线性存储结构和非线性存储结构

4. 判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。

A. top !=0 B. top= =0 C. top !=m0 D. top= =m0-1 5. 判定一个顺序栈ST（最多元素为m0）为栈满的条件是__D__。

A. top！=0 B. top= =0 C. top！=m0 D. top= =m0-1 6. 栈的特点是B____，队列的特点是____A。 A. 先进先出 B. 先进后出

7. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行。 (不带空的头结点)

A. HS.next=s;

B. s.next= HS.next; HS.next=s; C. s.next= HS; HS=s;

D. s.next= HS; HS= HS.next;

8. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行。(不带空的头结点)

A. x=HS; HS= HS.next; B. x=HS.data;

C. HS= HS.next; x=HS.data; D. x=HS.data; HS= HS.next;

9. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是____ 。 A. 4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，2，4，1

10. 判定一个循环队列QU（最多元素为m0）为空的条件是_C___。

A. rear - front= =m0 B. rear-front-1= =m0 C. front= = rear D. front= = rear+1 11. 判定一个循环队列QU（最多元素为m0, m0= =Maxsize-1）为满队列的条件是____A。

A. ((rear- front)+ Maxsize)% Maxsize = =m0

B. rear-front-1= =m0 C. front= =rear D. front= = rear+1

12. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是A____。

A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front 13. 栈和队列的共同点是__C__。

数据结构复习题及答案

A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点

3.2 填空题（将正确的答案填在相应的空中）

1. 顺序表、栈和队列都是____结构，可以在顺序表的____位置插入和删除元素；对于栈只能在____插入和删除元素；对于队列只能在____插入元素和____删除元素。

2. 向一个长度为n的顺序表的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动____个元素。

3. 向一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动____个元素。 8. 在具有n个单元的循环队列中，队满时共有____个元素。

习题答案

3.1 1. C 2. C 3. A 4. B 5.D 6. BA 7.C 8. B 9. C 10. C

11. A 12. A 13.C

3.2 1. 线性、任何、栈顶、队尾、队首 2. n-i+1 3. n-i

4.先移动栈顶指针，后存入元素 5. 先取出元素，后移动栈顶指针 6.前一个位置 7. 先移动队首元素，后取出元素 8. n-1 9. 不可能的 10. 可能的

习题6 树和二叉树

6.1 单项选择题

*1. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法__B__。

A. 正确 B. 错误

2. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 A．15 B．16 C．17 D．47

3. 按照二叉树的定义，具有3个结点的不同形状的二叉树有__C__种。

A. 3 B. 4 C. 5 D. 6

4. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有__C__种。

A. 5 B. 6 C. 30 D. 32

5. 深度为5的二叉树至多有___C_个结点。

A. 16 B. 32 C. 31 D. 10

6. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_ _A__。

A. 2h B. 2h-1 C. 2h+1 D. h+1

7. 对一个满二叉树，m个树叶，n个结点，深度为h，则___D_ 。

A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h-1

8. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序__A__。

A.不发生改变 B.发生改变 C.不能确定 D.以上都不对

9. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为___C_。 A. uwvts B. vwuts C. wuvts D. wutsv

10. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_A___。 A. 正确 B. 错误

11. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是__D__。

A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 12. 在一非空二叉树的中序遍历序列中，根结点的右边___A_。

A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 13. 如图6.1所示二叉树的中序遍历序列是_B___。

数据结构复习题及答案

A. abcdgef B. dfebagc C. dbaefcg D. defbagc

图6.1

图6.2

14. 一棵二叉树如图6.2所示，其中序遍历的序列为。

A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh

15．设a,b为一棵二叉树上的两个结点，在中序遍历时，a

在b前的条件是。

A．a在b的右方 B．a在b的左方 C．a是b的祖先 D．a是b的子孙

16. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac

，它的前序遍历序列是

__D__。

A. acbed B. decab

C. deabc D. cedba

17. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用__C__

存储结构。

A. 二叉链表 B. 广义表存储结构 C. 三叉链表 D. 顺序存储结构 18. 如图6.3所示的4棵二叉树，_C___不是完全二叉树。

(A) (B) (C) (D)

图6.3

6.2 填空题（将正确的答案填在相应的空中）

1. 有一棵树如图6.5所示，回答下面的问题： ⑴ 这棵树的根结点是____； ⑵ 这棵树的叶子结点是____； ⑶ 结点k3的度是____； ⑷ 这棵树的度是____； ⑸ 这棵树的深度是____；

⑹ 结点k3的子女是____； ⑺ 结点k3的父结点是____；

图6.5 一棵树

1. ⑴ k1 ⑵ k2,k5,k7,k4 ⑶ 2 ⑷ 3 ⑸ 4 ⑹ k5,k6 ⑺ k1

2. 指出树和二叉树的三个主要差别____、____、____。

3. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是。

4. 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图6.6所示，则该二叉树的链接表示形式为__ __。

数据结构复习题及答案

图6.6 一棵二叉树的顺序存储数组t

5. 深度为k的完全二叉树至少有____个结点。至多有____个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是____。

6. 在一棵二叉树中，度为零的 …… 此处隐藏：3155字，全部文档内容请下载后查看。喜欢就下载吧 ……