第六趟：（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);}
}
郑州大学远程教育学院数据结构试题及答案
