2010《数据结构》期末试卷_B卷

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

一、（本题10分）

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

tail(head(tail(C))) =？

（2）满足什么条件可以实施二分查找？二分查找的时间复杂度是多少？

二、（本题10分）证明：一棵二叉树的先序序列和中序序列可惟一确定这棵二叉树。

三、（本题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分）以关键字序列（29，18，25，47，58，12，51，10）为例，执行以下排序

1

算法，写出每一趟结束时的关键字状态：

（1）增量序列为5，3，1的希尔排序（2）快速排序（3）堆排序。

六、（本题10分）在两个有序线性表中，寻找是否存在共同元素。如果存在共同元素，返回第一个共同元素在第一个有序表中的位置。请设计数据结构，并在其上设计算法。

七、（本题15分）在带头结点的非空线性链表中，试设计一算法，将链表中数据域值最小的那个结点移到链表的最前面，其余各结点的顺序保持不变。要求：不得额外申请新的链结点。

八、（本题15分）请利用两个队列Q1和Q2来模拟一个栈。已知队列的三个运算定义如下：bool EnQueue(Queue &Q,int e):插入一个元素e入队列； bool DeQueue(Queue &Q,int &e):删除一个元素e出队列；bool QueueEmpty(Queue Q)：判队列为空。假设数据结构Queue已定义，栈Stack的数据结构定义如下。请利用队列的运算来实现该栈的三个运算：Push(Stack ST,int x):元素x入ST栈；Pop(Stack ST, int x)：ST栈顶元素出栈，赋给变量x；StackEmpty(Stack ST)：判ST栈是否为空。 typedef struct {

Queue Q1; Queue Q2; } Stack;

2