1、第 3 次作业一、填空题（本大题共 20 分，共 10 小题，每小题 2 分）1. 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_和记录的_。2. 具有 8 个顶点的无向图，边的总数最多为_。3. 树在计算机内的表示方式有 ， ， 。4. 三维数组 a456（下标从 0 开始计，a 有 4*5*6 个元素），每个元素的长度是 2，则 a234的地址是_。(设 a000的地址是 1000,数据以行为主方式存储) 5. 直接插入排序用监视哨的作用是_。6. AOV 网中,结点表示_,边表示_。AOE 网中,结点表示_,边表示_。7. 非空的单循环链表 head 的尾结点（由
2、p 指针所指）满足条件_。8. 一棵深度为 6 的满二叉树有_个分支结点和_个叶子。9. 已知二叉树前序为 ABDEGCF，中序为 DBGEACF，则后序一定是 。10. 在哈希文件中，处理冲突的方法通常有_、_ 、_和_四种。二、算法设计题（本大题共 20 分，共 2 小题，每小题 10 分）1. 设有一个线性表采用顺序存储结构，表中的数据元素值为正整数（n 个）。设在 O(n) 时间内，将线性表分成两为两部分，其中左半部分每个元素都小于原表的第一个元素，而右半部分则相反。2. 约瑟夫问题：设编号为 1，2，n 的 n（n0）个人按顺时针方向围坐一圈，每人持有一正整数密码。开始时任选一个正整
3、数作为报数上限值 m，从第一个人开始顺时针方向自 1 起顺序报数，报到 m 时停止报数，报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人起重新从 1 报数。如此下去，直到所有人全部出列为止。令 n 最大值取 30。要求设计一个程序模拟此过程，求出出列编号序列（采用循环单链表结构）。三、简答题（本大题共 20 分，共 4 小题，每小题 5 分）1. 已知一个无向图如下图所示，要求用 Kruskal 算法生成最小树（假设以为起点，试画出构造过程）。P_4F40AB2DD5C809AAA88A1FA81FC88E162. 一棵度为 2 的树与一棵二叉树有何区别？3. 试举一
4、个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 4. 设二叉树 BT 的存储结构如下:1 2 3 4 5 6 7 8 9 10Lchild 0 0 2 3 7 5 8 0 10 1Data J H F D B A C E G IRchild 0 0 0 9 4 0 0 0 0 0其中 BT 为树根结点的指针，其值为 6,Lchild,Rchild 分别为结点的左、右孩子指针域,data 为结点的数据域。试完成下列各题:（l）（3 分）画出二叉树 BT 的逻辑结构;（2）（3 分）写出按前序、中序、后序遍历该二叉树所得到的结点序列;（3）（4 分）画出二叉树的后序线索树。四、程
5、序设计题（本大题共 40 分，共 4 小题，每小题 10 分）1. 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。（注:已知树中结点数）2. 以二叉链表为存储结构，写出求二叉树叶子总数的算法 3. 设线性表的 n 个结点定义为(a 0,a1,.an-1)，重写顺序表上实现的插入算法：InsertList 4. 设顺序表中关键字是递增有序的，试写一顺序查找算法，将哨兵设在表的高下标端。然后求出等概率情况下查找成功与失败时的 ASL。答案：一、填空题（20 分，共 10 题，每小题 2 分）1. 参考答案：比较；移动解题方案：评分标准：2. 参考答案：28解
6、题方案：评分标准：3. 参考答案：双亲链表表示法，孩子链表表示法，孩子兄弟表示法解题方案：评分标准：4. 参考答案：1164解题方案：评分标准：5. 参考答案：免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。解题方案：评分标准：6. 参考答案：(1)活动（2）活动间的优先关系（3）事件（4）活动边上的权代表活动持续时间解题方案：评分标准：7. 参考答案：p-next=head 解题方案：评分标准：8. 参考答案：n1+n2=0+ n2= n0-1=31，26-1 =32解题方案：评分标准：9. 参考答案：DGEBFCA解题方案：评分标准：10. 参考答案：开放地址法、再哈希法、
7、链地址法、建立一个公共溢出区解题方案：评分标准：二、算法设计题（20 分，共 2 题，每小题 10 分）1. 参考答案：算法思想是：以第一个元素为轴，开始时设置 2 个指针（一个在最左端【不包括第一个元素】，一个在最右端）若两个指针没有重合，从右向左扫描每个元素，若遇到比轴小的元素则记录位置并停止向左扫描，开始从左向右扫描每个元素，若遇到比轴大的元素，则记录位置并停止扫描，将两个位置的记录交换，然后再从右向左扫描，重复上述过程，直到两个指针重合。typedef struct / ElemType *elem; /存储空间首地址int length; /线性表的当前长度 int listsize
8、; /当前分配的存储单元数SqList;int Partition(SqList *L)int low=0，int high=L-length-1ElemType pivot=L-elem1； /用区间的第 1 个记录作为基准 while(lowelem high=pivot) /pivot 相当于在位置low 上high-； /从右向左扫描，查找第 1 个关键字小于 pivot 的记录L.elem highif(lowelem low+= L-elem high； /相当于交换 L.elem low和L.elem high，交换后 low 指针加 1while(lowelem low piv
9、ot L-elem high-= L-elem low; /相当于交换 L.elem low和 L.elem high，交换后 high 指针减 1 /endwhileL-elem low=pivot； /基准记录已被最后定位return low； /partition解题方案：评分标准：2. 参考答案：#include #include #include struct linknodeint data;struct linknode *next;typedef struct linknode nodetype;nodetype *create(int n)/建立一个单向循环链表,且不带头节点
10、,节点长度为 nint i=1;nodetype *h=NULL,*s=NULL,*t;h=(nodetype *)malloc(sizeof(nodetype);if(!h) exit(“分配失败“);printf(“输入第 1 个节点的 data 域:“);scanf(“%d“,t=h;for(i=2;idata);s-next=NULL;t-next=s;t=s;/t 始终指向最后一个节点t-next=h;/t 指向最后一个节点return t;void display(nodetype *t,int n,int s,int m )nodetype *p=t,*q=NULL;int i,
11、j,k;for(i=1;inext;/使 p 指向开始出列节点的前驱for(j=1;jnext;/使 p 指向要出列的节点的前驱q=p-next;printf(“第%d 个报数的节点元素是：%dn“,j,q-data);p-next=q-next;/使 q 节点出列free(q);void main()nodetype *create(int );void display(nodetype *,int,int,int );nodetype *rear;rear=create(8);display(rear,8,1,4);system(“pause“);解题方案：评分标准：三、简答题（20 分，
12、共 4 题，每小题 5 分）1. 参考答案：构造最小生成树过程如下：（下图也可选(2,4)代替(3,4),(5,6)代替(1,5)）P_AAADA1606BD7938F7BB15D664E39AE3F解题方案：评分标准：2. 参考答案：度为 2 的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。解题方案：评分标准：3. 参考答案：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个
13、记录(有姓名，学号，身高和体重等字段) 就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录) ，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录 )。这几个关系就确定了这个表的逻辑结构是线性结构。这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示) 还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。解题方案：评分标准：4. 参考答案：（1）P_AC5918F9A266578EC4987B7C7C1011BD
