时间:2015-02-09 18:55:15
非选择题部分
注意事项：
用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。
二、填空题(本大题共13小题，每小题2分，共26分)
16.数据的基本单位是_________。
17.双向循环链表中，在p所指结点的后面插入一个新结点*t，需要修改四个指针，分别为
t->prior=P;t->next=p->next;_________;p->next=t;。
18.在带有头结点的循环链表中，尾指针为rear，判断指针P所指结点为首结点的条件是_________。
19.若线性表中最常用的操作是求表长和读表元素，则顺序表和链表这两种存储方式中，较节省时间的是_________。
20.不含任何数据元素的栈称为_________。
21.稀疏矩阵一般采用的压缩存储方法是_________。
22.100个结点的二叉树采用二叉链表存储时，用来指向左、右孩子结点的指针域有_________个。
23.已知完全二叉树的第5层有5个结点，则整个完全二叉树有_________个结点。
24.n个顶点的有向图G用邻接矩阵A[1..n，1..n]存储，其第i列的所有元素之和等于顶点
Vi的_________。
25.具有10个顶点的有向完全图的弧数为_________。
26.要完全避免散列所产生的“堆积’’现象，通常采用_________解决冲突。
27.在长度为n的带有岗哨的顺序表中进行顺序查找，查找不成功时，与关键字的比较次数为_________。
28.归并排序算法的时间复杂度是_________。
三、应用题(本大题共5小题，每小题6分，共30分)
29.稀疏矩阵A如题29图所示，写出该稀疏矩阵A的三元组表示法。
30.设二叉树的中序遍历序列为BDCEAFHG，后序遍历序列为DECBHGFA，试画出该二叉树。
31.写出题31图所示无向图的邻接矩阵，并写出每个顶点的度。
题31图
32.已知散列表的地址空间为0至13，散列函数H(k)=kmod11，(mod为求余运算)，待散列序列为(26，61，38，84，49)，用二次探测法解决冲突，构造该序列的散列表，要求写出处理冲突的过程。
33.将一组键值(80，50，65，13，86，35，96，57，39，79，59，15)应用二路归并排序算法从小到大排序，试写出各趟的结果。
四、算法设计题(本大题共2小题，每小题7分，共14分)
34.设单链表及链栈S的结构定义如下：
typedef struct node
{ Data Type data;
struct node*next;
｝linkstack;
编写一个算法void ReverseList(1inkstack *head)，借助于栈S将带头结点单链表head中序号为奇数的结点逆置，序号为偶数的结点保持不变。(例如：单链表的逻辑结构为(a1，a2，a3，a4，a5，a6)，逆置后变为(a5，a2，a3，a4，a1，a6))。
说明：栈的初始化运算用InitStack(S);进栈运算用Push(S，x);判栈空运算用EmptyStack(S);出栈运算用Pop(S);取栈顶元素运算用Gettop(S)。
35.以二叉链表作为存储结构，试编写递归算法实现求二叉树中叶子结点个数。