，再加入两个元素后，fro
t和rear的值分别为。A．5和1B．4和2C．2和4D．1和513、根据二叉树的定义，具有3个结点的二叉树有（）种树型。A．3B．4C．5D．614、如右图所示的二叉树，后序遍历的序列是（）A．A、B、C、D、E、F、G、H、IAB．A、B、D、H、I、E、C、F、G
DB
A
CEFG
C．H、D、I、B、E、A、F、C、GD．H、I、D、E、B、F、G、C、A15、下列陈述正确的是（）。A．二叉树是度为2的有序树C．二叉树中必有度为2的结点
HI
B．二叉树中结点只有一个孩子时无左右之分D．二叉树中最多只有两棵子树，且有左右子树之分）。Ｄ．2

16、在有
个叶子结点的哈夫曼树中，非叶子结点的总数是（Ａ．
1Ｂ．
Ｃ．2
1
第2页共5页
f17、对于一个具有
个顶点的有向图的边数最多有（
）。
A．
B．
1C．
12D．2
18、对于一个具有
个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（）。A．
1B．
1C．
D．
e19、下面关于图的存储结构的叙述中正确的是（）。A．用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关B．用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关C．用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关D．用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关20、二叉树为二叉排序树的（）条件是其任一结点的值均大于其左孩子的值，小于其右孩子的值。A．充分不必要B．必要不充分C．充分必要D．既不充分也不必要
二、分析运算题（本题共6小题，每题5分，共30分）
1、如果输入序列为123先进入栈结构后进入队列结构，试写出所有的出队列序列。2、假设一棵二叉树的前序先序遍历序列为ABDECF和中序序列为DBEAFC，画出二叉树并写出后序遍历序列。
图13、用二叉树表示算术表达式如图1所示。①按图画出对应的算术表达式
图2
图3
②写出后序（后缀）表达式
4、请写出有向图2中顶点16的入度和出度。5、给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为huffma
赫夫曼树。给定项及相应的权如下表：画出相应的huffma
树。
序号项权值1A152B63C74D125E256F47G68H19I15
6、已经邻接矩阵如图3所示，判断该图是有向图还是无向图，用顶点16画出该图。
第3页共5页
f三、程序填空题（本题共5空，每空2分，共10分）
1、下面程序段的功能是在单链表中查找元素数据x，若找到，返回指向该结点的指针；否则返回空r