一、 单项选择题(每题2分，共30分)
1. 下述关于顺序存储结构优点的说法，哪个是正确的（ ）
A. 插入运算方便 B. 可方便地用于各种逻辑结构的存储表示
C. 存储密度大 D. 删除运算方便
2. 假设根结点为第1层，深度为h层的二叉树至少有( ) 个结点(h>1)；
A. 2h B. 2h-1 C. 2h+1 D. 2h-1
3. 用单向链表来实现容量为n的堆栈时，链表头指针指向堆栈顶部元素，链表尾指针指向堆栈底部元素，则以下说法错误的是( )
A. 入栈操作的复杂度为O(1) B. 出栈操作的复杂度为O(1)
C. 删除底部元素的复杂度为O(1) D. 插入一个新的堆栈底部元素复杂度为O(1)
4. 以下关于递归算法的论述，不正确的是( )
A. 递归算法的代码可读性好 B. 递归算法可以提高程序运行效率
C. 递归调用层次太深有可能造成堆栈溢出 D. 递归调用层次太深会占用大量内存
5. 设有字符集合{4,6,3,W,S}，将字符序列6W43S中的字符按顺序进入堆栈，出栈可发生在任何时刻。则以下的出栈序列错误的是（ ）。
A. 64WS3 B. 4W36S C. 6W34S D. WS436
6. 在管理城市道路交通网络据时，最适合采用（ ）数据结构来对其进行存储。
A．有向图 B．无向图 C．树 D．矩阵
7. 具有k个顶点的完全有向图的边数为( )。
A. k(k-1) B. k(k-1)/2 C. k2 -1 D. k2+1
8. 若线性表最常用的操作是增加或者删除某个元素, 则采用( )存储方式节省时间.
A. 单链表 B. 双链表 C. 单循环链表 D. 顺序表
9. 由权为6,3,2,8的四个叶子结点构造一个哈夫曼树，该树的带权路径长度为（ ）。
A. 36 B. 35 C. 34 D. 33
10. 为了提高哈希表的查找效率，以下方法说法不正确的是( )。
A. 设计好的哈希函数 B. 增加哈希函数的个数
C. 增大存储空间 D. 采用更好的地址冲突解决方法
11. 以下数据结构中哪一个是非线性结构？( )
A. 队列 B. 栈 C. 线性表 D. 二叉树
12. 对于一个整数集合{11，37，29，55，80，46，73，17}进行散列存储时，若选用函数
H（K）= K %9作为散列(哈希)函数，则散列地址为1的元素有（ ）个。
A．3 B．4 C．5 D．6
13. 有一个100*90的整数稀疏矩阵，其中非0元素个数为10；设每个整数占用3个字节，则用三元组表示该矩阵时，总共需要的存储空间为( )字节。
A．30 B．33 C．90 D．99
14. 在一个双向链表中，当删除结点p时，错误的操作序列为 ( )。
A. p=p->prev; p->next->prev=p; p->next=p->next->next;
B. p=p->next; p->prev=p->prev->prev; p->prev->next=p;
C. p->prev->next=p->next; p->next->prev=p->prev;
D. p=p->prev; p->next=p->next->next; p->next->prev=p;
15. 在一个具有V个顶点的有向连通图中，若所有顶点的入度数之和为N，所有顶点的出度之和为M，则以下说法正确的是（ ）。
A．V=(M+N)/2 B．M>V C．M=N D．N>V
二、填空题(每空2分，共20分)
1. 对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为 。
2. 在单链表中，要将m所指结点插入到n所指结点之后，其语句表示为 。
3. 设有数组A[i][j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5][8]的存储首地址为 。
4. 设哈夫曼树中有199个结点，则该哈夫曼树中有 个叶子结点。
5. 对22个记录的有序表作折半查找，当查找失败时候，至多需要比较 次关键字，至少需要比较 次关键字。
6. 由3个结点可以构造出 种不同的二叉树。
7. 最大容量为s的循环队列，队尾指针是rear，队头是front，则队满的条件是 。
8. G是一个非连通无向图，共有28条边，则该图至少有 个顶点。
9. 数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用 排序算法最节省时间。
三．判断题（每题1分，共10分，正确的选T，错误的选F）
1. 对n个记录进行插入排序，最多只需要O(nlog(n))次两两比较。( )
2. 用链表(Linked list)来实现的堆栈，单次入栈/出栈操作的时间复杂度可达到O(1)。( )
3. 当图G中存在权重为负数的边时，Dijkstra算法不能用于计算G中两结点间最短路径。( )
4. 贪婪算法有时候能够求出全局最优解，有时候无法求出全局最优解。( )
5. 对含有n个记录的集合进行快速排序，在最坏情况下的时间复杂度是O(nlog(n))。 ( )
6. 哈希表查找效率高，当查找主键在范围[a,b]内所有的记录时，也应该优先选择哈希表。( )
7. 无向图的邻接矩阵是对称的，因此可只存储矩阵的下三角阵以节省存储空间。 ( )
8. 用Prime算法和Kruskal 算法求得的图的最小生成树一定相同。( )
9. 在一个有向图的邻接表或逆邻接表中，若某顶点的链表为空，则该顶点的度为零。( )
10. 在有n个顶点的无向图中，若边数>n-1，则该图必是连通图。( )
四、简答题（40分）
1. 简述逻辑结构的四种基本关系并画出它们的关系图。（10分）
2. 设二维数组 num[1….m, 1…n]含有m*n个整数，请分析判断数组中元素是否互不相同的算法的时间复杂度。（8分）
3. 设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18} ，请写出二路归并排序的方法下，每趟排序结束后关键字序列的状态。（6分）
4. 已知图1所示的有向图，请给出（1）每个顶点的入度与出度；（2）邻接矩阵。（10分）
5. 在一棵空的二叉排列树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排列树。（6分）
五、算法填空（共2小题，每空2分，共20分）
1. 在汉诺塔(hanoi tower)游戏中，总共有3根柱子和n个大小不一样的盘子。初始状态时n个盘子从小到大堆叠在1号柱子，下面的递归算法伪代码能够将这n个盘子从1号柱子移动到3号柱子。其中，该递归算法满足以下条件：(1)每次只移动1个盘子，(2)任何一个盘子只有当它上面没有堆放盘子时才能移动，(3)任何时刻在任何一个柱子上永远不能出现大盘子堆在小盘子之上的情况。请在_________处填上适当内容，使其成为一个完整的算法。
hanoi(from, tmp, to, n)
{ if(n==1){
move( (1) , (2) );
return;
}
hanoi( (3) );
printf ( "(%d,%d)", from, to );
hanoi( (4) );
return;
}
2. 假设一维数组A保存有N个整数，以下快速排序算法代码能够对数组A进行排序。请在__________处填上适当内容，使其成为一个完整的算法。
int partition(int* A, int N, int p, int r)
{ int x = A[r];
int i = (5) ;
for (int j = p; j<=r-1; j++){
if ( (6) ){
i = i + 1;
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
int temp = A[i+1];
A[i+1] = A[r];
A[r] = temp;
return (7) ;
}
void QuickSort(int* A, int N, int p, int r)
{
int q;
if ( (8) ){
q = partition(A, N, p, r);
QuickSort( (9) );
QuickSort( (10) );
}
return;
}void main()
{ QuickSort(A, N, 0,N-1);
return 0;
}
六．编写算法（30分）
1. 写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母与0-9这10个数字）。（10分）
2. 已知f为单链表的表头指针，链表中存储的都是整型数据，请写出实现下列运算的递归算法，求（1）链表中最大整数；（2）所有整数的平均值。（10分）
3. 采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径。（10分）
