2011年12月考试数据结构第三次作业一、填空题（本大题共20分，共 4 小题，每小题 5 分）
1. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按 ______ 次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 ______ 。
2. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 ______ ；末尾元素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，d3=1）
2. 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是无头结点单链表 ListNode *Q,*P; if(L&&L->next){ Q=L;L=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. 已知两个单链表中的元素递增有序，试写一算法将这两个有序表归并成一个递增有序的单链表。算法应利用原有的链表结点空间。
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，(6×7＋4)×6＋1000）＝1276
解题方案：
评分标准：
每空2分
3.
参：
O(n)
解题方案：
评分标准：
每空2分
4.
参：
叶
解题方案：
评分标准：
每空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 ，29 ，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 ，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 ，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.
参：
答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而 原来的第二个结点成为新的开始结点，返回新链表的头指针。
解题方案：
答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而 原来的第二个结点成为新的开始结点，返回新链表的头指针。
评分标准：
5
三、简答题（30分，共 2 题，每小题 15 分）
1.
参：
答：所谓“分块有序”指的是第二个子表中所有记录的关键字均大于第一个子表中的最大关键字，第三个子表中的所有关键字均大于第二个子表中的最大关键字，…，依次类推。
解题方案：
答：所谓“分块有序”指的是第二个子表中所有记录的关键字均大于第一个子表中的最大关键字，第三个子表中的所有关键字均大于第二个子表中的最大关键字，…，依次类推。
评分标准：
6
2.
参：
答： 使用广度优先搜索在访问了起始顶点v之后，由v出发，依次访问v的各个未曾被访问过的邻接顶点w1,w2,…,wt，然后再顺序访问w1, w2,…,wt 的所有还未被访问过的邻接顶点。 再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，…如此做下去，直到图中所有顶点都被访问到为止。
解题方案：
答： 使用广度优先搜索在访问了起始顶点v之后，由v出发，依次访问v的各个未曾被访问过的邻接顶点w1,w2,…,wt，然后再顺序访问w1, w2,…,wt 的所有还未被访问过的邻接顶点。 再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，…如此做下去，直到图中所有顶点都被访问到为止。
评分标准：
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表扫描指针，指向待比较结点的前一位置
q=lb->next;//q是lb表扫描指针，指向比较的结点
while(p->next)&&(q)
if (p->next->key<=q->key)
p=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 , *s; p=L -> next;
while( p->next && p->next->next) {q=p; //由于要做删除操作，所以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 && p->next->next) {q=p; //由于要做删除操作，所以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
