数据结构附部分答案(2)

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)); }