自考数据结构作业题及解析.doc

1、2013年 4月考试数据结构第三次作业 一、填空题（本大题共 20 分，共 4 小题，每小题 5 分） 1. 二叉树的基本组成部分是：根（ N）、左子树（ L）和右子树（ R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按 N L R次序），后序法（即按 _ 次序）和中序法（也称对称序法，即按 L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是 BEFCGDH，中序序列是 FEBGCHD，则它的后序序列必是 _ 。 2. 假设有二维数组 A68 ，每个元素用相邻的 6个字节存储 ，存储器按字节编址。已知 A的起始存储位置（基地址）为 1000，则数组 A的体积

2、（存储量）为 _ ；末尾元素 A57的第一个字节地址为 _ ；若按行存储时，元素A14的第一个字节地址为 _ ；若按列存储时，元素 A47的第一个字节地址为 _ 。 3. 一个算法的时间复杂度为 (3n2+2nlog2n+4n-7)/(5n)，其数量级表示为 _ 。 4. 在一棵树中， _ 结点没有后继结点。 二、程序阅读题（本大题共 20分，共 2 小题，每小题 10 分） 1. 对一组关键子 49， 7， 50， 5， 94， 16， 90， 29， 71 进行排序，写出分别用下列排序方法排序时，每一趟排序结束时这些关键字的序列。 1）简单插入排序 2）希尔排序（ d1=4,d2=2， d

3、3=1） 2. 下述算法的功能是什么 ? LinkList Demo(LinkList L) / L 是无头结点单链表 ListNode *Q,*P; if(LL=L-next;P=L; while (P-next) P=P-next; P-next=Q; Q-next=NULL; return L; / Demo 三、简答题（本大题共 30 分，共 2 小题，每小题 15 分） 1. 索引顺序表的查找要求 “ 分块有序 ” ，什么是 “ 分块有序 ” ？ 2. 请叙述图的广度优先搜索思想。 四、程序设计题（本大题共 30分，共 2 小题，每小题 15 分） 1. 已知两个单链表中的元素递增有

4、序，试写一算法将这两个有序表归并成一个递增有序的单链表。算法应利用原有的链表结点空间。 2. 写一算法将带头结点的单链表中值重复的结点删除，使所得的结果表中各结点值均不相同 答案： 一、填空题（ 20 分，共 4 题，每小题 5 分） 1. 参考答案： L R N， F E G H D C B 解题方案： 评分标准： 每空 2分 2. 参考答案： 288 B， 1282， (8+4)6+1000=1072 ， (67 4)6 1000） 1276 解题方案： 评分标准： 每空 2分 3. 参考答案： O(n) 解题方案： 评分标准： 每空 2分 4. 参考答案： 叶 解题方案： 评分标准： 每

5、空 2分 二、程序阅读题（ 20 分，共 2 题，每小题 10 分） 1. 参考答案： 答 ： 1） 简单插入排序： 7 ， 49 ， 50 ， 5 ， 94 ， 16 ， 90 ， 29 ， 71； 7 ， 49 ， 50 ， 5 ， 94 ， 16 ， 90 ， 29 ， 71； 5 ， 7 ， 49 ， 50 ， 94 ，16 ， 90 ， 29 ， 71； 5 ， 7 ， 49 ， 50 ， 94 ， 16 ， 90 ， 29 ， 71； 5 ，7 ， 16 ， 49 ， 50 ， 94 ， 90 ， 29 ， 71； 5 ， 7 ， 16 ， 49 ， 50 ， 90 ，94 ， 2

6、9 ， 71； 5 ， 7 ， 16 ， 29 ， 49 ， 50 ， 90 ， 94 ， 71； 5 ， 7 ，16 ， 29 ， 49 ， 50 ， 71 ， 90 ， 94； 2） 希尔排序： 49 ， 7 ， 50 ， 5 ，94 ， 16 ， 90 ， 29 ， 71 ； 49 ， 7 ， 50 ， 5 ， 71 ， 16 ， 90 ， 29 ， 94 ； 49 ， 5 ， 50 ， 7 ， 71 ， 16 ， 90 ， 29 ， 94； 5 ， 7 ， 16 ， 29 ， 49 ，50 ， 71 ， 90 ， 94 解题方案： 答： 1） 简单插入排序： 7 ， 49 ， 50 ，

7、 5 ， 94 ， 16 ， 90 ， 29 ， 71； 7 ， 49 ， 50 ， 5 ， 94 ， 16 ， 90 ， 29 ， 71； 5 ， 7 ， 49 ， 50 ， 94 ，16 ， 90 ， 29 ， 71； 5 ， 7 ， 49 ， 50 ， 94 ， 16 ， 90 ， 29 ， 71； 5 ，7 ， 16 ， 49 ， 50 ， 94 ， 90 ， 29 ， 71； 5 ， 7 ， 16 ， 49 ， 50 ， 90 ，94 ， 29 ， 71； 5 ， 7 ， 16 ， 29 ， 49 ， 50 ， 90 ， 94 ， 71； 5 ， 7 ，16 ， 29 ， 49 ，

8、50 ， 71 ， 90 ， 94； 2） 希尔排序： 49 ， 7 ， 50 ， 5 ，94 ， 16 ， 90 ， 29 ， 71 ； 49 ， 7 ， 50 ， 5 ， 71 ， 16 ， 90 ， 29 ， 94 ； 49 ， 5 ， 50 ， 7 ， 71 ， 16 ， 90 ， 29 ， 94； 5 ， 7 ， 16 ， 29 ， 49 ，50 ， 71 ， 90 ， 94 评分标准： 3 3 2. 参考答案： 答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而 原来的第二个结点成为新的开始结点，返回新链表的头指针。 解题方案： 答：该算法的功能是：将开始结点

9、摘下链接到终端结点之后成为新的终端结点，而 原来的第二个结点成为新的开始结点，返回新链表的头指针。 评分标准： 5 三、简答题（ 30 分，共 2 题，每小题 15 分） 1. 参考答案： 答：所谓 “ 分块有序 ” 指的是第二个子表中所有记录的关键字均大于第一个子表中的最大关键字，第三个子表中的所有关键字均大于第二个子表中的最大关键字， ，依次类推。 解题方案： 答：所谓 “ 分块有序 ” 指的是第二个子表中所有记录的关键字均大于第一个子表中的最大关键字，第三个子表中的所有关键字均大于第二个子表中的最大关键字， ，依次类推。 评分标准： 6 2. 参考答案： 答： 使用广度优先搜索在访问了起

10、始顶点 v之后，由 v出发， 依次访问 v的各个未曾被访问过的邻接顶点 w1,w2,wt ，然后再顺序访问 w1, w2,wt 的所有还未被访问过的邻接顶点。 再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点， 如此做下去，直到图中所有顶点都被访问到为止。 解题方案： 答： 使用广度优先搜索在访问了起始顶点 v之后，由 v出发，依次访问 v的各个未曾被访问过的邻接顶点 w1,w2,wt ，然后再顺序访问 w1, w2,wt 的所有还未被访问过的邻接顶点。 再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点， 如 此做下去，直到图中所有顶点都被访问到为止。 评分标准

11、： 3 3 四、程序设计题（ 30 分，共 2 题，每小题 15 分） 1. 参考答案： typedef struct node KeyType key; /关键字域 OtherInfoType info; /其它信息域， struct node * next; /链表中指针域 RecNode; /记录结点类型 typedef RecNode * LinkList ; /单链表用 LinkList表示 void mergesort(LinkList la,LinkList lb,LinkList lc) RecNode *p,*q,*s,*r; lc=la; p=la;/p是 la表扫描指针，

12、指向待比较结点的前一位置 q=lb-next;/q是 lb表扫描指针，指向比较的结点 while(p-next) else s=q;q=q-next; s-next=p-next; p-next=s;/将 s结点插入到 p结点后 p=s; if (!p-next) p-next=q; free(lb); 解题方案： 评分标准： 2. 参考答案： 解： 本题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。 void DeleteList ( LinkList L ) ListNode *p , *q , *

13、s; p=L - next; while( p-next /由于要做删除操作，所以 q指针指向要删除元素的直接前趋 while (q-next) if (p-data=q-next-data) s=q-next;q-next=s-next;free(s);/删除与 *p的值相同的结点 else q=q-next; p=p-next; 解题方案： 解： 本题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发 现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。 void DeleteList ( LinkList L ) ListNode *p , *q , *s; p=L - next; while( p-next /由于要做删除操作，所以 q指针指向要删除元素的直接前趋 while (q-next) if (p-data=q-next-data) s=q-next;q-next=s-next;free(s);/删除 与 *p的值相同的结点 else q=q-next; p=p-next; 评分标准： 3 3 4