A．Q.front==Q.rear; B．Q.front-Q.rear==Maxsize;
C．Q.front+Q.rear==Maxsize; D．Q.front==(Q.rear+1)%Maxsize; 二、判断对错题：（正确的选A，错误的选B）
1. 取线性表的第i个元素的时间同i的大小有关。（ ）
2. 两个栈共用静态存储空间，对头使用也存在空间溢出问题。（ ） 3. 二叉树是一般树的特殊情形。（ ）
4. 两个串相等的充分必要条件是分配的存储空间一样。（ ） 5. 已知指针P指向键表L的某结点，执行语句P=P->next不会删除该链表中的结点。（ ） 6. 在链队列中，即使不设置尾指针也能进行入队操作。（ ） 7. 循环链表不是线性表. 。（ ）
8. 顺序存储结构通过数据元素存储的位置表示元素之间的关系。（ ）
9. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ ）
10. 循环队列的引入，目的是为了克服假溢出。（ ） 11. 链表中的头结点仅起到标识的作用。（ ） 12. 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以结点移动量为标准分析。（ ）
13. 为了很方便的插入和删除数据，可以使用双向链表存放数据。（ ） 14. 栈是实现过程和函数等子程序所必需的结构。（ ） 15. 在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字符出现的位置均为模式串的最末字符。（ ）
16. 在单链表中，指针p指向元素为x的结点，实现\删除x的后继\的语句是p->next=p->next->next。（ ）
17. 通常将链串的结点大小设置为大于1是为了提高存储密度。（ ）
18. 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（ ） 19. 单链表从任何一个结点出发，都能访问到所有结点。（ ） 20. 在数据结构中，空串和空格串的概念是一样的。（ ）
21. 如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（ ） 22. 循环队列通常用指针来实现队列的头尾相接。（ ） 23. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续单元向前移动。（ ）
三、应用题
1．借助堆栈将(A+B)*((C-D)*E+F)转换成后缀表达式，写出转换过程。 2．借助堆栈计算后缀表达式ABC*/DE*+AC*，写出计算过程。
第3章 树
一、单项选择题：（从给定的选项中选择出一个最恰当的答案）
1．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是_____ A．队列 B．栈 C．线性表 D．有序表
2．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系_____. A．不一定相同 B．都相同 C．都不相同 D．互为逆序 3. 在下述结论中，正确的是______. ①只有一个结点的二叉树的度为0; ②二叉树的度为2；
③二叉树的左右子树可任意交换;
④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④
4. 树是结点的有限**，它______根结点，记为T。其余结点分成为m（m>=0）个互不相交的**T1，T2， …，Ｔm，每个**又都是树。
A. 有0个或1个 B. 有0个或多个 C. 有且只有一个 D. 有1个或1个以上 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是____. A．9 B．11 C．15 D．不确定 6．对于有n 个结点的二叉树, 其高度为______.
A．nlog2n B．log2n C．?log2n?+1 D．不确定 7. 利用二叉链表存储树，则根结点的右指针是_____。
A．指向最左孩子 B．指向最右孩子 C．空 D．非空
8．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为_______。
A．CBEFDA B． FEDCBA C． CBEDFA D．不定 9．下面关于串的的叙述中，_______是不正确的？
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 10．有关二叉树下列说法正确的是_______。
A．二叉树的度为2 B．一棵二叉树的度可以小于2
C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 11．在一棵高度为k的满二叉树中，结点总数为_______。
A．2k-1 B．2k C．2k-1 D．?log2k?+1 12．树的后根遍历序列等同于该树对应的二叉树的_______。
A． 先序序列 B．中序序列 C．后序序列 D．层次序列 13．对于前序遍历和中序遍历结果相同的二叉树为_______。
A．根结点无左孩子的二叉树 B．根结点无右孩子的二叉树
C．所有结点只有左子树的二叉树 D．所有结点只有右子树的二叉树 14．下面的说法中正确的是_______。
（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变； （2）按二叉树定义，具有三个结点的二叉树共有6种。 A．(1)(2) B．(1) C．(2) D．(1)、(2)都错
15．在完全二叉树中，若一个结点是叶结点，则它没_______。 A．左子结点 B．右子结点
C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点
16．假设用于通信的电文由8个字母组成，其频率分别为0.07、0.19、0.02、0.06、 0.32、0.03、0.21、0.10, 为这8个字母设计哈夫曼编码，其中编码长度最大的字母的编码是_____位。
A．4 B．5 C． 6 D．7
17．采用邻接表存储的图的深度优先遍历算法类似于树的______。
A．中根遍历 B．先根遍历 C．后根遍历 D．按层次遍历 18．在n(n>0)个元素的顺序栈中删除1个元素的时间复杂度为_______。 A．O(n) B．O(nlog2n) C．O(1) D．O( ) 19．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用_____遍历方法最合适。
A．前序 B．中序 C．后序 D．按层次 20．由3 个结点可以构造出______种不同的二叉树？ A．2 B．3 C．4 D．5 21．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为______。 A．求子串 B．联接 C．匹配 D．求串长 22．若串P=”structure”,其子串的数目是_______。 A．46 B．45 C．41 D．40
23．设森林F对应的二叉树为B，它有m个结点，B的根为P, P的右子树结点个数为n,森林F中第一棵树的结点个数是_______。
A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 24．二叉树的第I层上最多含有结点数为_______。
A．2I B． 2I-1-1 C． 2I-1 D．2I -1
25．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为_______个
A．4 B．5 C．6 D．7 26．以下算法的功能是______。
int BTreeDepth(Btree *BT) //*BT为二叉树某结点的指针 {int leftdep, rightdep; if(BT==NULL) return(0);
{leftdep=BTreeDepth(BT->left); rightdep=BTreeDepth(BT->right);
if( leftdep>rightdep)return(leftdep+1); else return(rightdep+1); } }
A．求二叉树的深度 B．求二叉树结点数目
C．先序遍历二叉树的结点 D．求二叉树叶子结点的数目 二、判断对错题：（正确的选A，错误的选B） 1. 二叉树是一般树的特殊情形。（ ）
2. 树最适合用来表示元素之间具有分支层次关系的数据。（ ） 3. 哈夫曼树度为1的结点数等于度为2和0的结点数之差。（ ） 4. 完全二叉树一定存在度为1的结点。（ ）
5. 对一棵二叉树进行层次遍历时，应借助于一个栈。（ ） 6. 二叉树只能用二叉链表表示。（ ）
7. 树中的结点和图中的顶点就是指数据结构中的数据元素。（ ） 8. 度为二的树就是二叉树。（ ） 9. 二叉树的遍历结果不是唯一的。（ ）
10. 将一棵树转换为二叉树后，根结点没有左子树。（ ）
11. 对于一棵二叉树，如果度为2的结点数为n个，则叶子结点数为n＋1个。（ ） 12. 对一棵有n个结点，高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。（ ）
13. 在树中，如果从结点K出发，存在两条分别到达K’，K”的长度相等的路径，则结点K’和k”互为兄弟。（ ）
三、应用题
1. 证明存在这样的二叉树：其叶子节点在先根次序、中根次序、后根次序下的都按相同的相对位置出现（即每个叶子节点在先根次序、中根次序、后根次序排序结果中的位置相同）。 3. 某二叉树的结点数据采用顺序存储表示如下：
0 C
(1) 试画出此二叉树的图形表示。 (2分) (2) 写出结点D的双亲结点及左、右子女。 (2分)
(3) 将此二叉树看作森林的二叉树表示，试将它还原为森林。(2分)
3. 根据下面给定的几个数（6，11，6， 12，8，18，12，7，4）构造一颗赫夫曼树，并求出其带权路径长度。（给出具体过程）
4. 假如一颗二叉树有5个节点，请画出满足下列条件的所有二叉树：
（1） 先根序列和中根序列相同； （2） 中根序列和后根序列相同；
5. 分别画出有A、B、C、D三个节点所组成的所有树和所有二叉树。
6. 若一棵度为4的树中有n(1)个度为1的节点个数，n(2)个度为2的节点个数，n(3)个度为3的节点个数，n(4)个度为4的节点个数，问该树有多少个叶节点？
1 A 2 B 3 4 D 5 6 E 7 8 9 F 10 11 12 13 G
第4章 图
一、单项选择题：（从给定的选项中选择出一个最恰当的答案） 1．具有4个顶点的无向完全图有 __ 条边。 A．20 B． 16 C． 12 D． 6
2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 __ 倍。 A．4 B．2 C． 1 D．1/2 3．图中有关路径的定义是_______。
A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 4．设无向图的顶点个数为n，则该图最多有_______条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．n2 5．要连通具有n个顶点的有向图，至少需要_______条边。 A．n-l B．n C．n+l D．2n 6．从邻接阵矩 可以看出，该图共有_______个顶点。 A．9 B．3 C．6 D．1
7．设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有_______。 a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c A．5个 B．4个 C．3个 D．2个 8．在图采用邻接表存储时（n是图的顶点数，e是图的边数），求最小生成树的 Prim 算法的时间复杂度为_______。
A． O(n) B． O(n+e) C．O(n2) D． O(n3) 9．n个结点的完全有向图含有边的数目_______。
A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 10．无向图G=(V,E),其中：V={a,b,c,d,e,f},
E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是_______。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b
11．若以{4, 5, 6, 3, 8}作为叶子结点的权值构造哈夫曼树，则带权路径长度是 。 A． 28 B． 55 C． 59 D． 68
12．设m, n为一棵二叉树上的两个结点，在中序遍历时， n在m前的条件是 。 A．n在m右方 B．n是m 祖先 C．n在m左方 D．n是m子孙 13 下列说法不正确的是______。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．图的深度遍历不适用于有向图
C．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程
14．当各边上的权值_______时，BFS算法可用来解决单源最短路径问题。 A．均相等 B．均互不相等 C．不一定相等 D. 均相等或均不等
15．用Prim算法求下列连通的带权图的最小代价生成树，在算法执行的某刻，已选取的顶点**U＝{1，2，5}，边的**TE＝{（1，2），（2，5）}，要选取下一条权值最小的边，应当从______组中选取。 A．{（1，4），（3，4），（3，5），（2，5）} B．{（5，4），（5，3），（5，6）} C．{（1，2），（2，3），（3，5）} D．{（3，4），（3，5），（4，5），（1，4）}