郑州大学远程教育学院数据结构试题及答案

第六趟：（7，9，10，65，70，83，100），32 第七趟：（7，9，10，32，65，70，83，100） 快速排序每一趟结束时的关键字状态：：

初始序列：70，83，100，65，10，9，7，32 第一趟： （32，7，9，65，10），70，（100，83） 第二趟： （10，7，9），32，（65）

第三趟： 83，(100) 第四趟： (9，7)，10

第五趟： 7，9，10，32，65，70，83，100

4．（1）希尔排序： d1=3: {8 2 13 10 12 14} d2=2: {8 2 12 10 13 14} d3=1: {2 8 10 12 13 14}

(2) 堆排序初态: {10，2，14，8，12，13} 建堆:{14 12 13 8 2 10}

输出14之后再建堆：{13 12 10 8 2 14} 输出13之后再建堆：{12 8 10 2 13 14} 输出12之后再建堆：{10 8 2 12 13 14} 输出10之后再建堆：{8 2 10 12 13 14} 输出8之后再建堆：{2 8 10 12 13 14}有序

考试模拟题答案 客观题部分： 一、单项选择题：

7. B 二、判断题：

主观题部分： 一、简答题：

1.应采用顺序结构。因为顺序表是随机存取的存储结构，在顺序表中存取任何元素所花的时间都一样。而链表是顺序存取的存储结构。 2.

?0?0??03.??0?0??0?1000100100000010010000000?0??0?? 0?1??0??可能的拓扑序列为：156234 （注意4一定是最后一个，2一定在1和5之后） 4.

ASL=(1+1+1+2+5+1+1+4)/8

5. (1) 该序列不是堆。

原始序列： { 26，33，35，29，19，12，22 }

交换26和35，建大顶堆：{35，33，26，29，19，12，22 } （2）直接插入排序过程：

原始序列： { （26），33，35，29，19，12，22 }

i=2： { （26，33），35，29，19，12，22 } i=3： { （26，33，35），29，19，12，22 } i=4： { （26，29，33，35），19，12，22 }

=16/8=2

i=5： { （19，26，29，33，35），12，22 } i=6： { （12，19，26，29，33，35），22 } i=7： { （12，19，22，26，29，33，35）}

二、算法设计题：

1. int nodes(BiTree T) {

if(!T) return 0;

return nodes(T->lchild)+nodes(T->rchild)+1; }

2. int count (AlGraph G)

{

int i, sum;

for (i=0; i<; i++) visited[i]=false; sum=0; for (i=0; i< ; i++)

if (!visited[i]) {sum++; dfs (G, i);} return sum; }

void dfs (AlGraph G, int i) {

visited[i]=true;

for (p=[i].firstarc; p; p=p->nextarc) { k=p->adjvex;

if (!visited[k]) dfs(G, k);}

}