2011《数据结构》期末试卷 - B卷

厦门大学《＿数据结构＿》课程期末试卷 信息科学与技术学院计算机科学系2009年级＿＿＿专业

主考教师：陈怡疆 庄朝晖 试卷类型：（B卷）

一、（本题10分）请根据下面的描述写出销售部门的数据结构（用C语言）：假设一个销售部门有n个职员（最多不超过N个，N为100），其中有一个是销售经理。每个职员都各自有一些客户，客户的个数不固定，不同职员的客户不重叠。 二、（本题15分）

（1）线性表和广义表的主要区别点是什么？已知广义表: C=(a,(b, (a,b)), ((a,b), (a,b))), 则tail(head(tail(C))) =？

（2）满足什么条件可以实施二分查找？二分查找的时间复杂度是多少？ 三、（本题10分）给定一组权值（5，9，11，2，6，16），试设计相应的哈夫曼树。 四、（本题15分）某带权有向图如下：

A 1 B 1 E 始点 3 2 3 2 C 1 F 5 G 终点 3 D 1

（1）写出深度优先搜索结点访问序列，并画出深度优先生成树（当有多种选择时，编号小的结点优先）；

（2）写出该图的拓扑序列（当有多种选择时，编号小的结点优先）； （3）将该图作为AOE网络，写出求关键路径的过程。 五、（本题10分）已知待散列存储的关键字序列为（4,15,38,49,33,60,27,71），哈希函数为H(key)=key MOD 11，哈希表HT的长度为11，采用线性探测再散列法解决冲突。试构造此哈希表，并求出在等概率情况下查找成功的平均查找长度。 六、（本题15分）在两个有序线性表中，寻找是否存在共同元素。如果存在共同元素，返回第一个共同元素在第一个有序表中的位置。请设计数据结构，并在其上设计算法。 七、（本题10分）编写一个遍历二叉查找树T的算法，要求遍历过程恰好按结点键值从大到小的次序进行。二叉树T数据结构采用二叉链表。 八、（本题15分）一个正整数序列存放在带头结点的链表L中，每个结点存放一个正整数。请编写算法将该链表调整为所有奇数在链表的前部分，所有偶数在链表的后部分，并且调整后的奇数序列和偶数序列都与它们在原来序列中的次序一致（例如：原序列1 2 3 4 5 6，调整后 1 3 5 2 4 6）。要求：除算法外，还要给出数据结构、算法思想和代码注释。

1

本文来源：https://www.bwwdw.com/article/mvmh.html