阵两种。
18．设广义表L=（（），（）），则表头是 （） ，表尾是 （（）） ，L的长度是 2 。
19．广义表A（（a,b,c）,(d,e,f)）的表尾为 （（d,e,f）） 。
S 2入栈 S 3入栈
X 3出栈 输出序列：13 S 4入栈
20．两个串相等的充分必要条件是_______串长度相等且对应位置的字符相等 X 4出栈 输出序列：134 ___。
21．设有n阶对称矩阵A，用数组s进行压缩存储，当i?j时，A的数组元素aij相应于数组s的数组元素的下标为__ i(i-1)/2+j _____。（数组元素的下标从1开始）
22．对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的___行下标____、___列下标___和___非零元素值____三项信息。 X 2出栈 输出序列：1342
6．有5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先的次序有哪几个？
答：从题中可知，要使C第一个且D第二个出栈，应是A入栈，B入栈，C入栈，C出栈，D入栈。之后可以有以下几种情况：
三、问答题
1．简述栈和一般线性表的区别。
答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。 2．简述队列和一般线性表的区别。
队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。 3．链栈中为何不设头结点？
答：因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现很简单，所以一般不设置头结点。 4．利用一个栈，则：
（1）如果输入序列由A，B，C组成，试给出全部可能的输出序列和不可能的输出序列。
（2）如果输入序列由A，B，C，D组成，试给出全部可能的输出序列和不可能的输出序列。
答：
（1）栈的操作特点是后进先出，因此输出序列有： A入，A出，B入，B出，C入C出，输出序列为ABC。 A入，A出，B入，C入，C出，B出，输出序列为ACB。 A入，B入，B出，A出，C入，C出，输出序列为BAC。 A入，B入，B出，C入，C出，A出，输出序列为BCA。 A入，B入，C入，C出，B出，A出，输出序列为CBA。
由A，B，C组成的数据项，除上述五个不同的组合外，还有一个C，A，B组合。但不可能先把C出栈，再把A出栈，（A不在栈顶位置），最后把B出栈，所以序列CAB不可能由输入序列A，B，C 通过栈得到。
（2）按照上述方法，可能的输出序列有：
ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA，CBAD，CBDA，CDBA，DCBA。
不可能的输出序列有：
DABC，ADBC，DACB，DBAC，BDAC，DBCA，DCAB，CDAB，CADB，CABD 5．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S和X操作串是什么？
答：应是SXSSXSXX。各操作结果如下： S 1入栈
X 1出栈 输出序列：1
（1）B出栈，A出栈，E入栈，E出栈，输出序列为：CDBAE。 （2）B出栈，E入栈，E出栈，A 出栈，输出序列为CDBEA。 （3）E入栈，E出栈，B出栈，A出栈，输出序列为CDEBA 所以可能的次序有：CDBAE，CDBEA，CDEBA 7．写出以下运算式的后缀算术运算式
⑴ 3x2+x-1/x+5 ⑵ (A+B)*C-D/(E+F)+G 答；对应的后缀算术运算式
⑴ 3x2^*x+1x/-5+ ⑵ AB+C*DEF+/-G+
8． 简述广义表和线性表的区别和联系。
答：广义表是线性表的的推广，它也是n(n>0)个元素a1 ,a2…ai… an的有限序列，其中ai或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这
种特性，线性表可以看成广义表的特殊情况，当ai都是原子时，广义表退化成线性表。 四、程序填空题
1．在下面空格处填写适当的语句，以使下面的链式队列取出元素的算法完整。 int write(LinkQueue *q) {QueueNode *p;
if (q->front==q->rear) /*队空*/ {printf(“underflow”); exit(0);}
while (q->front->next != NULL) {p=q->front->next;
(1) q->front->next=p->next;
printf(“M”,p->data); (2) free(p); }
（3） q->rear=q->front ; /*队空时，头尾指针指向头结点*/ } 五、综合题
1．设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5和e6依次通过S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是多少？
答：出队序列是e2,e4,e3,e6,e5,e1的过程：
5
⑴ e1入栈（栈底到栈顶元素是e1） ⑵ e2入栈（栈底到栈顶元素是e1,e2） ⑶ e2出栈（栈底到栈顶元素是e1） ⑷ e3入栈（栈底到栈顶元素是e1,e3） ⑸ e4入栈（栈底到栈顶元素是e1,e3,e4） ⑹ e4出栈（栈底到栈顶元素是e1,e3） ⑺ e3出栈（栈底到栈顶元素是e1） ⑻ e5入栈（栈底到栈顶元素是e1,e5） ⑼ e6入栈（栈底到栈顶元素是e1,e5,e6） void delqueue(LinkQueue *Q) /*出队算法*/ {
struct node *t; if (Q->rear==NULL) { printf(\队列为空!\\n\ return(0); }
else if (Q->rear->next==Q->rear) /*只有一个结点时*/ { t=Q->rear; Q->rear=NULL; }
else /*有多个结点时*/ ⑽ e6出栈（栈底到栈顶元素是e1,e5） ⑾ e5出栈（栈底到栈顶元素是e1） ⑿ e1出栈（栈底到栈顶元素是空）
栈中最多时有3个元素，所以栈S的容量至少是3。
2．假设用循环单链表实现循环队列，该队列只使用一个尾指针rear，其相应的存储结构和基本算法如下；
（1）初始化队列initqueue(Q):建立一个新的空队列Q。 （2）入队列enqueue(Q,x):将元素x插入到队列Q中。 （3）出队列delqueue(Q):从队列Q中退出一个元素。 （4）取队首元素gethead(Q):返回当前队首元素。 （5）判断队列是否为空：emptyqueue(Q)。 （6）显示队列中元素：dispqueue(Q)。 算法设计如下：
/*只有一个指针rear的链式队的基本操作*/ #include
struct node /*定义链队列结点*/ {
elemtype data; struct node *next; };
typedef struct queue /*定义链队列数据类型*/ {
struct node *rear; } LinkQueue;
void initqueue(LinkQueue *Q)/*初始化队列*/ {
Q=(struct queue *)malloc(sizeof(struct queue)); Q->rear=NULL; }
void enqueue(LinkQueue *Q,elemtype x) /*入队算法*/ {
struct node *s,*p;
s=(struct node *)malloc(sizeof(struct node)); s->data=x;
if (Q->rear==NULL) /*原为空队时*/ { Q->rear=s; s->next=s; }
else /*原队不为空时*/ { p=Q->rear->next; /*p指向第一个结点*/ Q->rear->next=s; /*将s链接到队尾*/ Q->rear=s; /*Q->rear指向队尾*/ s->next=p; } }
{ t=Q->rear->next; /*t指向第一个结点*/ Q->rear->next=t->next; /*引成循环链*/ }
free(t); }
elemtype gethead(LinkQueue *Q) /*取队首元素算法*/ {
if (Q->rear==NULL) printf(\队列为空!\\n\ else return(Q->rear->next->data); }
int emptyqueue(LinkQueue *Q) /*判断队列是否为空算法*/ {
if (Q->rear==NULL) return(1); /*为空,则返回true*/ else return(0); /*不为空,则返回flase*/ }
void dispqueue(LinkQueue *Q) /*显示队列中元素算法*/ {
struct node *p=Q->rear->next; printf(\队列元素:\ while (p!=Q->rear) { printf(\ p=p->next; }
printf(\}
六、完成：实验2――栈、队列、递归程序设计
根据实验要求（见教材P203）认真完成本实验，并提交实验报告。 数据结构（本）课程作业 作业3
（本部分作业覆盖教材第6-7章的内容） 一、单项选择题
1.假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ B ）。
A．15 B．16 C．17 D．47 2．二叉树第k层上最多有（ B ）个结点。 A．2k B．2
k-1
C．2k
-1 D．2k-1
3．二叉树的深度为k,则二叉树最多有（ D ）个结点。
A．2k B．2k-1 C．2k-1
D．2k
-1
4. 设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（ C ）。
A．abdec B．debac C．debca D．abedc
6
5．将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（ B ）。
A．33 B．34 C．35 D．36
6．如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（ A ）。
A．哈夫曼树 B．平衡二叉树 C．二叉树 D．完全二叉树 7．下列有关二叉树的说法正确的是（ A ）。
A．二叉树中度为0的结点的个数等于度为2的结点的个数加1 B．二叉树中结点个数必大于0
C．完全二叉树中，任何一个结点的度，或者为0或者为2 D．二叉树的度是2
8．在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。
A．4 B．5 C．6 D．7
9．在一棵度具有5层的满二叉树中结点总数为（ A ）。
A．31 B．32 C．33 D．16
10. 利用n个值作为叶结点的权生成的哈夫曼树中共包含有( D )个结点。 A. n B. n+1 C. 2*n D. 2*n-1
11. 利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为( A )。
A. 18 B. 16 C. 12 D. 30 12．在一棵树中，（ C ）没有前驱结点。
A．分支结点 B．叶结点 C．树根结点 D．空结点
13．在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ C ）。
A．2i B．2i-1 D．2i+1 C．2i+2
14．设一棵哈夫曼树共有n个叶结点，则该树有（ B ）个非叶结点。
A．n B．n-1 C．n+1 D．2n
15．设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2，则该树共有（ B ）个结点。
A．2n B．2n-1 C．2n+1 D．2n+2
16．在一个图G中，所有顶点的度数之和等于所有边数之和的（ C ）倍。
A．1/2 B．1 C．2 D．4
17．在一个有像图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。
A．邻接矩阵表示法 B．邻接表表示法 C．逆邻接表表示法 D．邻接表和逆邻接表 18．在图的存储结构表示中，表示形式唯一的是（ C ）。 A．n B．n?1 C．n?1 D．n/2 19．一个具有n个顶点的无向完全图包含（ A ）条边。
A．n（n?1） B．n（n?1） C． n（n?1）/2 D． n（n?1）/2
20．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为（ B ）。 A．n B．n C．n?1 D．（n?1）
2
2
21．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ D ）。
A．n B．e C．2n D．2e
22．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（ B ）邻接点。 A．入边 B． 出边 C．入边和出边 D． 不是入边也不是出边 23．邻接表是图的一种（ B ）。
A．顺序存储结构 B．链式存储结构 C．索引存储结构 D．散列存储结构
24．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该
图一定是（ B ）。
A．完全图 B．连通图 C．有回路 D．一棵树 25．下列有关图遍历的说法不正确的是（ C ）。
A．连通图的深度优先搜索是一个递归过程
B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次
26．无向图的邻接矩阵是一个（ A ）。
A．对称矩阵 B． 零矩阵 C．上三角矩阵 D．对角矩阵 27．图的深度优先遍历算法类似于二叉树的（ A ）遍历。 A．先序 B． 中序 C．后序 D．层次
28．已知下图所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ C ）。
A．V1V2V4V8V3V5V6V7 B．V1V2V4V5V8V3V6V7
C．V1V2V4V8V5V3V6V7 D．V1V3V6V7V2V4V5V8
二、填空题
V1 1．结点的度是指结点所拥有的 子树树木或后继结点数 。 2．树的度是指 树中所有结点的度的最大值 。
V2 V3 3．度大于0的结点称作 分支结点 或 非终端结点 。 4．度等于0的结点称作 叶子结点 或 终端结点 。
5．在一棵树中，每个结点的 子树的根 或者说每个结点的 后继结点 称
V4 V5 V6 V7 为该结点的 孩子结点 ，简称为孩子。
6．从根结点到该结点所经分支上的所有结点称为该结点的 祖先 。 7．树的深度或高度是指 树中结点的最大层数 。 8．具有n个结点的完全二叉树的深度是
?log2n??1 。
V8 9．先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的 根结点 ；先序遍历二叉树的 左子树 ，先序遍历二叉树
7
的 右子树 。
10．中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的 左子树 ；访问而叉树的 根结点 ，中序遍历二叉树的 右子树 。
11．后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的 左子树 ；后序遍历二叉树的 右子树 ，访问而叉树的 根结点 。
12．将树中结点赋上一个有着某种意义的实数，称此实数为该结点的 权 。 13．树的带权路径长度为树中所有叶子结点的 带权路径长度之和 。 14．哈夫曼树又称为 最优二叉树 ，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL 最小的二叉树 。
15．若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 69
。
16．具有m个叶子结点的哈夫曼树共有 2m-1 结点。
17．在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种
多对多 的关系。
18．图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中 所有顶点 各做
一次 访问的过程。
19．图的深度优先搜索遍历类似于树的 先序 遍历。 20．图的广度优先搜索类似于树的 按层次 遍历。 21．具有n个顶点的有向图的邻接矩阵，其元素个数为 n2 。 22．图常用的两种存储结构是 邻接矩阵 和 邻接表 。 23．在有n个顶点的有向图中，每个顶点的度最大可达 2(n-1) 。 24．在一个带权图中，两顶点之间的最段路径最多经过 n-1 条边。
25．为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为 栈 。 三、综合题
1．写出如下图所示的二叉树的先序、中序和后序遍历序列。
A。
3．已知一棵完全二叉树共有892个结点，求 ⑴ 树的高度 ⑵ 叶子结点数 ⑶ 单支结点数
答：二叉树的定义是递归的，所以，一棵二叉树可看作由根结点，左子树和右子树这三个基本部分组成，即依次遍历整个二叉树，又左子树或者右子树又可看作一棵二叉树并继续分为根结点、左子树和右子树三个部分…..，这样划分一直进行到树叶结点。
(1)先序为“根左右”，先序序列为：fdbacegihl (2)中序为“左根右”，中序序列为：abcdefghij (3)后序为“左右根”，后序序列为：acbedhjigf
2．已知某二叉树的先序遍历结果是：A，B，D，G，C，E，H，L，I，K，M，F和J，它的中序遍历结果是：G，D，B，A，L，H，E，K，I，M，C，F和J，请画出这棵二叉树，并写出该二叉树后续遍历的结果。
（1）二叉树图形表示如下：
ABDGLHKEIMCFJ （2）该二叉树后序遍历的结果是：G、D、B、L、H、K、M、I、E、J、F、C和
f ⑷ 最后一个非终端结点的序号 d g 答 ⑴ 已知深度为k的二叉树最多有2k-1个结点(K≥1)， 29-1<892< 210-1，故树的高度为10
b e c h i ⑵ 对于完全二叉树来说，度为1的结点只能是0或1 因为n=n0+n1+n2和n0=n2+1
a 得：设n1=0，892=n0+0+n2=2n2+1 得n2不为整数出错 j 设n1=1，892=n0+1+n2=2n2+2
得n2 =445→ n0=n2+1=446 叶子结点数为446。 ⑶ 由⑵得单支结点数为1
⑷ 对于n个结点的完全二叉树，最后一个树叶结点，即序号为n的叶结点其双亲结
8