2010华南农业大学数据结构答案
- 格式：doc
- 大小：190.50 KB
- 文档页数：6
1 装订线 华南农业大学期末考试答案（A卷）
2010-2011学年第 1 学期 考试科目： 数据结构
考试类型：（闭卷）考试 考试时间： 120 分钟
学号 姓名 年级专业
题号 一 二 三 四 总分
得分
评阅人
一、单项选择题（本大题共 10 小题，每小题 2 分，共 20 分）
1 2 3 4 5 6 7 8 9 10
D A A B B D C A C
AB
二、应用题（本大题共 8 小题，第1~7题每题6分，第8题8分，共 50 分）
1.
得分
得分
G
A
B
C
E
D
H
K
I
F
J
L
2 2、
3、哈希表：
0 1 2 3 4 5 6 7 8 9
14 01 9 23 84 55 20 27
平均查找长度ASL：(1+1+2+1+1+2+5+3)*1/8=16/8
4、
初始：29，18，25，47，58，12，51，10
第一趟：12，18，10，47，58，29，51，25
第二趟：12，18，10，47，25，29，51，58
第三趟：10，12，18，25，29，47，51，58 53
17
12 17
12 53
66
58 17
12 58
66 53
70
58
17 66
70 12
87 53 58
17 70
87 12 66 53
25 56 60 3 装订线
5、各字符频率：A：9；B：1；C：5；D：3，以频率为权值构造以下哈夫曼树：
编码时左分支为0，右分支为1，则：
A：0
B：100
C：11
D：101
6、503，87，512，61，908，170，897，275，653，462
初始堆：
7、
平均查找长度：(1+2*2+3*4+4)*1/8=21/8
A
C
B D
503
87 512
61 908 170 897
275 653 462 908
653 897
503 462 170 512
275 61 87
4
2 6
1 3 5 7
8 4 8、
三、程序填空题（本大题共10空，每空2分，共20分，注意：每空只填一个语句）
说明：阅读下面的程序，并写出程序的运行结果。
1: p=p->next;
2: s->next = p->next;
3: p->next = s;
4: --high;
5: ++low;
6: low;
7: p=f;
8: flag=TRUE;
9: SearchBST(T->lchild,key,T,p,flag);
10: SearchBST(T->rchild,key,T,p,flag);
11 L->next
12 q=p;
13 L->next=q;
14 value*10+ch-‘0’;
15 sum+value
得分 V1
V2 V3
V4 V5 12 16
2
10 18
4 22 V1
V2 V3
V4 V5 12
2
10 4
5 装订线
四、程序设计题（本大题共1小题，每小题10分，共10分）
1 void min(LinkList L){
LNode *p,*q,*r,*s;
if(L->next==NULL) return;
q=L; r=L->next; m=r->data;
while(r->next!=NULL)
{ if(r->next->data { m= r->next->data; q=r; } s=r; r=r->next; } p=q->next; if(m%2==1) {q->next=p->next; free(p); else {s->next=p; q->next=p->next; p->next=q;} } } } 2 int Level(BiTree bt) //层次遍历二叉树，并统计度为1的结点的个数 {int num=0; //num统计度为1的结点的个数 if(bt){QueueInit(Q); QueueIn(Q,bt)；//Q是以二叉树结点指针为元素的队列 while(!QueueEmpty(Q)) {p=QueueOut(Q); printf(p->data); //出队,访问结点 if(p->lchild && !p->rchild ||!p->lchild && p->rchild)num++;//度为1的结点 if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入队 if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入队 } }//if(bt) return(num); }//返回度为1的结点的个数 得分 1.5CM 6
