2014上数据结构期末图习题答案(2)

（2） 希尔排序（增量选取5，3，1）

10 2 16 6 18 12 16* 20 30 28 （增量选取5） 6 2 12 10 18 16 16* 20 30 28 （增量选取3） 2 6 10 12 16 16* 18 20 28 30 （增量选取1） （3）快速排序 枢轴

12 [6 2 10] 12 [28 30 16* 20 16 18] 6 [2] 6 [10] 12 [28 30 16* 20 16 18 ] 28 2 6 10 12 [18 16 16* 20 ] 28 [30 ] 18 2 6 10 12 [16* 16] 18 [20] 28 30 16* 2 6 10 12 16* [16] 18 20 28 30

5. 设待排序的关键字序列为{30，60,8,40,70,12,10}，试使用堆排序， （1）画出将无序数据建成初始堆的图， （2）画出将第二个数排定顺序时的堆的图。 答（1）初始堆序列 为 70 60 12 40 30 8 10

70126040 （2）

30810

601281240104010

308 交换60和8

3060 四、程序填空题

1、 根据有向图的邻接矩阵求出序号为numb的顶点的度数(邻接矩阵可参考简答题第三题),

请填写算法中下划线的空白处。 int degree2(Graph & ga, int numb)

{ int i,j,d=0;

for(j=0; j

if(ga.arcs[ numb ][j]!=0 && ga.arcs[ numb ][j]!=MAXINT) d++ ;

for(i=0; i

if(ga.arcs[ I ][ numb ]!=0 && ga.arcs [ I ][ numb ]!=MAXINT) d++; return (d); }

2.. 已知r[1..n]是n个记录的递增有序表，用折半查找法查找关键字（key）为k的记录。如果查找失败，，则输出“ 失败”，函数返回值为0；否则输出“成功”，函数返回值为该

6

记录的序号值。

Int binary_search(struct recordtype r[ ],int n ,keytype k) /* r[1..n] 为N 个记录的递增有序表，k 为关键字 */ { int mid,low=1,hig=n; while( low<=hig) { mid=(low+hig)/2;

if(k

else if(k==r[mid].key){ printf(“ 成功”)；(2) return mid ;} else (3) low=mid+1 ; } if(low>high) printf(“失败”); return(0);

}

3. 建立huffman 树

void HuffmanCoding(HuffmanTree &HT, int *w,int n) // 算法6.12

{ // w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC int m,i,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; if(n<=1) return; m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用 for(p=HT+1,i=1;i<=n;++i,++p,++w) {

(*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; }

for(;i<=m;++i,++p) (*p).parent=0;

for(i=n+1;i<=m;++i) // 建赫夫曼树

{ // 在HT[1～i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 select(HT,i-1,s1,s2);

ht[s1].parent==I; ht[s2].parent==I; ht[i].lchild=s1; ht[i].lchild=s2; ht[i].weight=ht[s1].weight+ht[s2].weight;

7

} }

六．编程题

1.期中考试 二个程序题（循环队列入队出队、用栈处理进制转换（P48 算法3.1） 2. 以二叉链表作为二叉树的存储结构，编写以下算法： (看实习题)

（1）写出先序、中序、后序遍历二叉树的递归算法； （1）统计二叉树的结点个数。

3. 带头结点的单链表的插入和删除算法。（书上P30 算法2.9，2.10） 答.1. 期中循环队列入队出队

#define MAX 20 typedef struct {

int qu[MAX];

int rear，length; }Queue;

Int EnQueue( Queue &q, int e) { if( q.length==MAX) return -1; q.rear=(q.rear+1)%max; q.length=q.length+1; q.qu[q.rear]=e; return 1; }

Int DeQueue( Queue &q, int &e) { int front;

if( q.length==0) return -1;

front=(q.rear+1+MAX-q.length)%max; e=q.qu[front]; q.length--; return 1; }

8