一、
1. 在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（ ）
A．O (n) B．O (1) C．O (n2 ) D．O (log2 n)
2. 设单链表中结点的结构为（data , link）。已知指针q所指结点是指针p所指结点
的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？（ ）
A．p->link=s->link ;s->link=p; B．s ->link= p->link ; p->link=s; C. p->link=s ;s->link=q; D．q->link=s ;s->link=p;
3. 若让元素1，2，3依次进栈，则出栈次序不可能出现（ ）种情况。
A．2，1，3 B．3，1，2 C．1，3，2 D. 3，2，1
4. 设有一个10阶的对称矩阵A，采用压缩存储方式按行将矩阵中下三角部分的元素存
入一维数组B[ ]中，A[0][0]存入B[0]中，则A[8][5]在B[ ]中（ ）位置。
A．33 B．41 C．65 D. 32
5. 若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个（） A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵 6. 用链表表示线性表的优点是（）
A. 便于随机存取 B. 花费的存储空间比顺序表少 C. 便于插入与删除 D. 数据元素的物理顺序与逻辑顺序相同 7. 具有65个结点的完全二叉树的高度为（ ）。（根的层次号为1）
A．8 B．7 C．6 D．5 8. 一个二叉树按顺序方式存储在一个维数组中，如图
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J 则结点E在二叉树的第（ ）层(根的层次号为1)。
A.1 B.2 C.3 D.4
9. 含5个结点（元素值均不相同）的二叉搜索树有（ ）种。 A.54 B.42 C.36 D.65
10. 在无向图中定义顶点V i与Vj之间的路径为从V i到达Vj的一个（ ）
A．顶点序列 B．边序列 C．权值总和 D．边的条数 11. 在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。
A．3 B．2 C．1 D．1/2 12. 一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位
置的对象为基准而得到的第一次划分结果为（ ）。
A．{38，46，79，56，40，84} B．{38，79，56，46，40，84} C．{40，38，46，56，79，84} D．{38，46，56，79，40，84} 13. 设有100个数据元素，采用折半搜索时，最大比较次数为（） A. 6 B. 7 C. 8 D. 10
1
二、
1． 队列的的插入操作在 进行，删除操作在 进行。 2． 设有一个顺序栈S，元素S1，S2，S3，S4，S5，S6依次进栈，如果6个元素的出栈顺
序为S2，S3，S4，S6，S5，S1，则顺序栈的容量至少应为 。 3． 链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的________域的
值。 4． 在一个链式栈中，若栈顶指针等于NULL则为________。 5． 在一棵树中，______结点没有后继结点。
6． 在一棵AVL树（高度平衡的二叉搜索树）中，每个结点的左子树高度与右子树高度
之差的绝对值不超过________。
7． n (n﹥0) 个顶点的无向图最多有________条边，最少有________条边。
三、
1． 已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。
前序序列：A, B, C, D, E, F, G, H, I, J
中序序列：C, B, A, E, F, D, I, H, J, G
后序序列：
2． 假定一组数据对象为（40，28，16，56，50，32，30，63），按次序插入每个对象生
成一棵AVL树（高度平衡的二叉搜索树），根据插入过程填写下表，在相应位置填写
所需要的调整类型：“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，若不需要旋转则填写“无”。
数据： 40 调整： 28 16 56 50 32 先右后左 30 63 3． 假定一组记录的排序码为(20,12,35,15,10,80,30,17,2,1)，利用堆排序方法画出初
始大顶堆（以树状表示）。
4． 已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组
a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 45, 58, 63, 83时的比较次数。
34 45 58 63 83 元素值 比较次数
5． 设散列表为HT[17], 待插入关键码序列为 { Jan, Feb, Mar, Apr, May, June, July,
Aug, Sep, Oct, Nov, Dec }，散列函数为H (key) = ?i ? 2?，其中，i是关键码第一个字母在字母表中的序号。现采用线性探查法解决冲突。
2
字母 A 序号 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8 I 9 J K L M 10 11 12 13 字母 N O P Q R S T U V W X Y Z 序号 14 15 16 17 18 19 20 21 22 23 24 25 26
(1) 试画出相应的散列表；
(2) 计算等概率下搜索成功的平均搜索长度
6． 按照普里姆算法从顶点1出发画出下图的最小生成树，试写出在最小生成树中依此
得到的各条边。
7． 试根据迪克斯特拉(Dijkstra)算法求出下图中从顶点A到其余各项点的最短路径。
8．阅读下列算法，并补充所缺语句
void purge_linkst ( ListNode * & la ) {
//从头指针为 la 的带表头结点的非递减有序链表中删除所有值相同的多余
3
元素，
//并释放被删结点空间。
ListNode* p, *q, *t; ElemType temp; p = la->link;
while (p != NULL ) {
q = p; temp=p->data ; p = p->link;
while ( p != NULL && ___ ) { t = p; p = p->link;
delete t;
}
}
9.下面给出一个排序算法，其中Vector[ ] 是存放数据表元素的一维数组，n是数据元素的个数，。
void unknown (int Vector[]，int n) {
int temp; int i, j;
for ( i = 1; i < n; i++ )
if ( Vector[i] < Vector[i-1] ) {
(1) 写出该算法的功能。
(2) 针对有n个数据对象的待排序的数据表，在最好情况下，算法的排序码比较次
数和对象移动次数分别是多少？
比较次数： 移动次数：
10.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
class BinTreeNode { public:
ElemType data;
BinTreeNode *leftChild, *rightChild;
};
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指
4
}
}
}
temp = Vector[i]; Vector[i] = Vector[i-1];
for ( j = i-2; j >= 0; j-- ) if ( temp < Vector[j]) Vector[j+1] = Vector[j]; else break; Vector[j+1] = temp;
}
针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的树根结点。 BinTreeNode* BinTreeSwopX ( BinTreeNode * BT ) { if ( BT == NULL ) return NULL; else {
}
}
BinTreeNode* pt = new BinTreeNode; pt->data = BT->data;
pt->rightChild = BinTreeSwopX ( BT->leftChild ); pt->lefthild = BinTreeSwopX ( BT->rightChild );
return pt;
四、
已知单链表的结点用ListNode表示，被定义为: class ListNode
{
public:
char data;
ListNode *link;
};
其中data为结点值域，link为指向后继结点的指针域。设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用两个链表的存储空间，不另外占用其他的存储空间。表中允许有重复的数据。算法声明如下： ListNode* MergeList ( ListNode* ha, ListNode* hb );
5
