2003数据结构与C语言程序设计答案.docx

一．单项选择题
1. C 2.D 3.D 4.C 5.A
6.C 7.C 8.D

二．填空题
9.栈（或后进先出表） 10. n – i + 1 11. 11 12.无前驱（或入度为零）
13 物理存储14. n2 – 2e
15. b c e d a 16. ( s2 + 2s + n)/ (2s ) 或 (én/sù +1)/2 + (s + 1)/2
17. 384 18.A[4][8]
三．解答题
19. s -> next -> next = p –>next; p->next=s;
21. a1, a2, a3 a1, a3, a2 a3, a2, a1 a3, a1, a2
22.

33

32
.
(1)

(2) DFS: b, a, e, c, d BFS: b, a, d, e, c

四．算法阅读题
35.
(1)该函数的功能是调整整数数组 a[ ] 中的元素，并返回分界值i， 使所有小于x 的元素均落在a[ low .. i ] 上，使所有大于等于x 的元素均落在a[ i + 1 .. high ] 上。
(2) int f ( int b[ ], int n) { 或 int f (int b[ ], int n) {
int p, q; int p, q;
p = arrange( b, 1, n, 0); p = arrange( b, 1, n, 1);
q = arrange( b, p + 1, n, 1); q = arrange( b, 1, p, 0);
return q – p; return p – q;
} }

五．算法设计题
38．
ADT MinRootHeap{
数据对象：D={ Ki | Ki ε keySet,i=1,2,…,n n≥0 }
数据关系：R={< Ki , K2i >∧< Ki , K2i+1 > | Ki , K2i , K2i+1ε keySet, Ki £ K2i∧Ki £ K2i+1
且i=1,2,…,ën/2û }
基本操作：

InitHeap(& LH)
操作结果：构造一个空堆LH
SortHeap(&LH, L)
初始条件：在L中存在一组可进行比较的元素。
操作结果：对L中的数据在LH中实现堆排序。
InsertHeap(&LH, K)
初始条件：堆LH存在。
操作结果：在堆LH中的尾部插入一个元素K，并重新调整LH为堆。
DeleteHeap(&LH, &e)
初始条件：堆LH存在，且非空。
操作结果：从堆LH的堆顶删除一个元素，并由e返回其值，其余元素重新调整为堆。
}// ADT MinRootHeap
注：反映的是主要操作，次要操作可适当忽略。

37．
void ancestor(BiTree T, TElemType x, bool &found, int level)
{ // found 的初始值为false
if(T&&(!found)){
if(T->data = = x)
{
found=true;cout<<level<<endl;
}
else{
ancestor(T->lchild,x,found,level+1);
ancestor(T->rchild,x,found,level+1);
if(found)cout<<T->data<<" ";
}
}
}