15. 设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有_e=2m_____关系。
一个点的度数就等于该点连接的边数,一条边连接2个点,这两个点的度数都要加1,也就是说,有一条边总的度数就要加2,所以总度数是边数的2倍
16． 已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是
(1，3，4，5，2) ，BFS遍历的输出序列是 (1，3，2，4，5)
三、应用题
1、假定有四个元素A, B, C, D依次进栈，进栈过程中允许出栈，请写出所有可能的出栈
序列。
进一个出一个，ABCD
先进两个，AB进，进C出C,进D出D，出B出A，CDBA 进A进B，进C进D，出D出C出B出A，DCBA 下面的不解释了，不明白你再问 BCDA,BDCA,BCAD,BADC,BACD, 前三个一起进 CBAD,CBDA,CDBA 第一个进去就出来 ADCB,ACDB,ACBD 一共14种 例题
第 6 页 共 11 页
第 7 页 共 11 页
图3.2 有向图
用5个带权值{3,2,4,5,1}构造的哈夫曼树的带权路径长度是 （
第 8 页 共 11 页
）
8、 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输
入各个数据而生成的二叉排序树。
第 9 页 共 11 页
四、程序填空
1、如下为二分查找的非递归算法，试将其填写完整。
Int Binsch(ElemType A[ ],int n,KeyType K) {
int low=0; int high=n-1;
while (low<=high) {
int mid=_______________________________；
if (K==A[mid].key) return mid; //查找成功，返回元素的下标
else if (K<[mid].key)
______________________________________; //在左子表上继续查找
else __________________________________; //在右子表上继续查找
}
return -1; //查找失败，返回-1 }
答案： (low+high)/2 high=mid-1 low=mid+1
2．循环队列的插入。
循环队列数据结构定义如下：
四、算法设计题
1、设计算法，在顺序表test中插入元素a到第i个位置。要求考虑表满情况。
第 10 页 共 11 页
2、设计算法，实现二叉树的递归先序遍历。
3、设计算法，实现n个整数的快速排序。
4、统计出单链表HL中结点的值等于给定值X的结点数。 int CountX(LNode* HL,ElemType x) { int i=0; LNode* p=HL;//i为计数器 while(p!=NULL)
{ if (P->data==x) i++; p=p->next;
}//while, 出循环时i中的值即为x结点个数 return i; }//CountX
5、 设计判断两个二叉树是否相同的算法。
typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; int judgebitree(bitree *bt1,bitree *bt2) {
if (bt1==0 && bt2==0) return(1);
else if (bt1==0 || bt2==0 ||bt1->data!=bt2->data) return(0);
else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild)); }
6、 设计两个自小到大有序单链表ha，hb的合并排序算法，合并后的单链表头指针为hc。
7、实现对n个整数自小到大的直接插入排序 。
第 11 页 共 11 页