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

一单项选择题1. C2.D3.D4.C5.A6.C7.C8.D二填空题9.栈（或后进先出表） 10. n i + 1 11. 11 12.无前驱（或入度为零）13 物理存储14. n2 2e15. b c e d a 16. ( s2 + 2s + n)/ (2s ) 或 (n/s +1)/2 + (s + 1)/217. 38418.A48 三解答题19. s - next - next = p next; p-next=s;21. a1, a2, a3 a1, a3, a2 a3, a2, a1 a3, a1, a222. 3332. (1)(2) DFS: b, a, e, c, dBFS: 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;五算法设计题38ADT MinRootHeap 数据对象：D= Ki | Ki keySet,i=1,2,n n0 数据关系：R= | Ki , K2i , K2i+1 keySet, Ki K2iKi K2i+1且i=1,2,n/2 基本操作：InitHeap(& LH) 操作结果：构造一个空堆LHSortHeap(&LH, L) 初始条件：在L中存在一组可进行比较的元素。 操作结果：对L中的数据在LH中实现堆排序。InsertHeap(&LH, K) 初始条件：堆LH存在。 操作结果：在堆LH中的尾部插入一个元素K，并重新调整LH为堆。DeleteHeap(&LH, &e) 初始条件：堆LH存在，且非空。 操作结果：从堆LH的堆顶删除一个元素，并由e返回其值，其余元素重新调整为堆。/ ADT MinRootHeap注：反映的是主要操作，次要操作可适当忽略。37void ancestor(BiTree T, TElemType x, bool &found, int level) / found 的初始值为falseif(T&(!found)if(T-data = = x)found=true;coutlevellchild,x,found,level+1); ancestor(T-rchild,x,found,level+1);if(found)coutdata ;