A.top++； V[top]=x

B.V[top]=x； top++

C.top--； V[top]=x

D.V[top]=x； top--

正确答案：top--； V[top]=x

8、设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。

A.2

B.3

C.4

D.6

正确答案：3

9、循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（）。

A.队空：end1 == end2； 队满：end1 ==（end2+1） mod M

B.队空：end1 == end2； 队满：end2 ==（end1+1） mod（M-1）

C.队空：end2 ==（end1+1）mod M； 队满：end1 ==（end2+1） mod M

D.队空：end1 ==（end2+1）； 队满：end2 ==（end1+1） mod（M-1）

正确答案：队空：end1 == end2； 队满：end1 ==（end2+1） mod M

10、用链接方式存储的队列，在进行删除运算时（）。

A.仅修改头指针

B.仅修改尾指针

C.头、尾指针都要修改

D.头、尾指针可能都要修改

正确答案：头、尾指针可能都要修改

第四章单元测试

1、由3 个结点可以构造出多少种不同的树（）

A.2

B.3

C.4

D.5

正确答案：2

2、一棵树高为K的完全二叉树至少有（）个结点

A.

3、将含有83个结点的完全二叉树从根结点开始编号，根为1号，按从上到下、从左到右顺序结点编号，那么编号为41的双亲结点编号为（）

A.42

B.40

C.21

D.20

正确答案：20

4、对于有n 个结点的二叉树， 其高度为（）

A.

D.不确定

正确答案：不确定

5、给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3、1、7、5、6、2、4，则其遍历方式是（）

A.NRL

B.RNL

C.LRN

D.RLN

正确答案：RNL

6、如果T2是由有序树T转化而来的二叉树，那么T中结点的先序就是T2中结点的（）

A.先序

B.中序

C.后序

D.层次

正确答案：先序

7、下面几个符号串编码集合中，不是前缀编码的是（）

A.{0，10，110，1111}

B.{11，10，001，101，0001}

C.{00，010，0110，1000}

D.{b，c，aa，ac，aba，abb，abc}

正确答案：{11，10，001，101，0001}

8、二叉树先序遍历：EFHIGJK；中序遍历：HFIEJKG 。该二叉树根的右子树的根是（）

A.E

B.F

C.G

D.H

正确答案：G

9、以下说法错误的是（）

A.一般在哈夫曼树中，权值越大的叶子离根结点越近

B.哈夫曼树中没有度数为1的分支结点

C.若初始森林中共有N棵二叉树，最终求得的哈夫曼树中共有2N-1个结点