河北大学课程考核试卷
（2005 —2006学年第二学期）
考核科目数据结构课程类别必修课考核方式闭卷卷别B
注：所有题目的答案写清题号写在答题纸上。
一、单项选择题（共30分，每小题2分）
1．算法指的是（）
A．计算机程序B．解决问题的计算过程
C．排序算法D．解决问题的有限运算序列
2．线性表采用链式存储时，结点的存储地址（）
A．必须是不连续的B．连续与否均可
C．必须是连续的D．和头结点的存储地址相连续
3．一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是( )
A. 2 3 4 1 5
B. 5 4 1 3 2
C. 2 3 1 4 5
D. 1 5 4 3 2
4．若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( )存储方式最节省时间。
A.单链表
B.双向链表
C.带头结点的双循环链表
D.单循环链表
5．如下陈述中正确的是（）
A．串是一种特殊的线性表 B．串的长度必须大于零
C．串中元素只能是字母 D．空串就是空白串
6．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：
20，15，21，25，47，27，68，35，84
15，20，21，25，35，27，47，68，84
15，20，21，25，27，35，47，68，84
则所采用的排序方法是（）
A．选择排序B．希尔排序C．归并排序D．快速排序
7．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( ) A．e B．2e C．n2－e D．n2－2e
8．一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为( )
A. 0
B. 1
C. 2
D.不确定
9．对有18个元素的有序表作二分查找，则查找A［3］的比较序列的下标依次为( )
A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
10．数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )排序算法最节省时间。
A.堆排序
B.希尔排序
C.快速排序
D.直接选择排序
11．栈和队列的共同特点是( )
A.先进后出
B.先进先出
C.只允许在端点处插入和删除元素
D.没有共同点
12．对线性表进行二分查找时，要求线性表必须( )
A.以顺序方式存储
B.以链接方式存储
C.以顺序方式存储，且结点按关键字有序排序
D.以链接方式存储，且结点按关键字有序排序
13．下列说法错误的是( )
A.一个图的邻接矩阵表示是唯一的
B.一个图的邻接表表示是不唯一的
C.一个图的生成树必为该图的极小连通子图
D.一个无环有向图的拓扑排序序列必唯一
14．下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )
A.堆排序
B.冒泡排序
C.快速排序
D.直接插入排序
15．设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A．5 B．6 C．7 D．8
二、填空题（共20分，每空2分）
1．已知一棵完全二叉树中共有768结点，则该树中共有384 个叶子结点。
2．十字链表适合存放图，邻接多重表适合存放图。
3．已知数组A[1..10,1..10]为对称矩阵，其中每个元素占5个单元。
现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5，6]对应的地址是1225 。
4．在双链表中，在指针P所指结点前面插入一个结点S时的语句序列是：
S->next=P;S->prior=P->prior;P->prior=S; S->prior->next=S ；
5．二叉排序树上，结点的平衡因子定义为该结点(左)子树的高度减去该结点(右子树的高度)。
6．树的四种常用存储结构是：双亲表示法，孩子表示法，双亲孩子，孩子兄弟。
三．解答题（共20分，每小题5分）
1．用Kruskal 方法求出下图的一棵最小生成树。
2．已知一棵二叉树的先序遍历序列是ABCDEFGHIJK ，中序遍历序列是CDBGFEAHJIK ，请构造出该二叉树。
3．设无向图G 如图所示，试给出：
① 从V0出发的“深度优先”遍历序列（当存在多个邻接点时，标号小者优先）。
② 从V0出发的“广度优先”遍历序列（当存在多个邻接点时，标号小者优先）。
4．已知查找表为{19，01，23，14，55，20，84，27，68，11，10，77}，设定哈希函数为：H(key)=key % 13 ，采用开放地址法的线性探测法解决冲突，试在0～16的哈希地址空间中对该关键字构造哈希表，并求出查找成功时的平均查找长度。
四．算法设计题（共30分，每小题10分）
要求：1）给出主要的数据类型定义。
2）用C语言描述算法，并对主要语句加注释。
1．已知一顺序表A，其元素值非递减有序排列，编写一个算法删除顺序表中多余的值相同的元素。
2．一个线性表中的元素为非零实数。
设计算法将正数或负数分开，使线性表前一半为负数，后一半为正数。
不必对元素排序，要求算法的时间复杂度为O(n)。
3．编写算法实现带头结点的单链表的逆置，请借助栈来实现。