2011年华南农业大学数据结构答案(A)

华南农业大学期末考试答案（A卷）

2011-2012学年第 1 学期 考试科目： 数据结构 考试类型：（闭卷）考试 考试时间： 120 分钟

一、选择题（本大题共 10 小题，每小题2分，共20分）

1 D 2 C 3 B 4 D 5 A 6 D 7 B 8 C 9 C 10 D 二、应用题（本大题共 5 小题，每小题6分，共30分）

1、参考答案：

B C D 二叉树

F A E G H I

2、参考答案：

（在队列的一端进入插入时，TOP值会增加，在另一端删除，当判断TOP==MAX-1为“是”，这说明队已满。但实际在队列的另一端还是有存储空间的，这就是“假溢出”。）当front?0，rear=M时，再有元素入队发生溢出，称之为“假溢出”，存储空间还有剩余。为了改进这种状况，可以将顺序队列想象为一个首尾相接的环状空间，称之为循环队列。 “假溢出”现象和循环队列的数据结构基本上描述清楚就可以。 其中：循环队列的队空条件：front == rear

队满条件：(Q.rear+1) % MAXQSIZE == Q.front 。

3、参考答案：

哈夫曼树HT的存储结构的初态 哈夫曼树HT的存储结构的终态 1 2 3 4 5 6 7 8 9 10 11 12 13 字符 A B C D E F G weight Parent lch 3 0 0 12 7 4 2 8 11 rch 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 字符 A B C D E F G weight Parent lch 3 8 0 12 7 4 2 8 11 5 9 15 20 27 47 12 10 9 8 10 11 9 11 12 13 13 0 0 0 0 0 0 0 5 4 3 9 2 11 rch 0 0 0 0 0 0 0 1 8 6 7 10 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

4、参考答案：

ASL=(1*6+2*4+3+4)/12=1.75

5、参考答案：

(1)一趟希尔排序：12,2,10,20,6,18,4,16,30,8,28（D=5）； (2)一趟快速排序：6,2,10,4,8,12,28,30,20,16,18。

三、程序填空题（本大题5小题，共15个空白处，每空2分，共30分，注意：

每空只填一个语句） (1) L=L->next (2) q=L (3) L=p (4) low <= high (5) key==ST[mid] (6) high=mid-1 (7) a[i]=t (8) (i=2;ilchild (15) p=p->rchild

2

四、程序设计题（本大题共2小题，每小题10分，共20分。请先简要说明算法

思想，然后写出算法的源代码实现）

1、参考答案：

void MiniDelete(LinkedList head) ∥head是带头结点的单链表的头指针，本算法按递增顺序输出单链表中各结点的数

∥据元素，并释放结点所占的存储空间。

{while(head->next!=null) ∥循环到仅剩头结点 ……………….………… ..1分 {pre=head； ∥pre为元素最小值结点的前驱结点的指针 p=pre->next； ∥p为工作指针 ………………………………………3分 while(p->next!=null)

{if(p->next->datanext->data)pre=p；∥记住当前最小值结点的前驱

p=p->next； } ………………………………………6分 Printf(pre->next->data)； ∥输出元素最小值结点的数据 u=pre->next；pre->next=u->next；free(u)；∥删除元素值最小的结点,放结点空间 }∥ while(head->next!=null) ………………………………..……9分 Free(head)；} ∥释放头结点 …………………………………… 10分

2、参考答案：

BiTree PostFirst(p)

{BiTree q=p; ………………………..…………..2分

if (!q) return(null); ……………………………… ...…3分

else while(q->lchild || q->rchild) //找最左下的叶子结点 …………...…………5分 {if(q->lchild) q=q->lchild; //优先沿左分枝向下去查“最左下”的叶子结点 else q=q->rchild; //沿右分枝去查“最左下”的叶子结点 ………..8分 }

return(q);

} …………………………….….….10分

以上两小题评分请注意：能够写出正确算法思想的酌情给3-4分。

本文来源：https://www.bwwdw.com/article/b4gh.html