河南理工大学万方学院 2006-2007学年第
2 学期
《数据结构》试卷（A卷）
考试方式：闭卷本试卷考试分数占学生总评成绩的80 %
复查总分总复查人
一、单选题（本题的每一备选答案中，
只有一个是正确的，请把你认为正确的答案
的题号填入题干的括号内，每小题2分，共
30分）
1. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为( )。
(1≤i≤n+1)
(1) O(0) (2) O(1) (3) O(n) (4) O(n2)
2.在单链表中p所指结点后插入s所指结点,则下列语句正确的是( )
(1) p→next=s; s→next=p; (2) s→next=p→next; p→next=s;
(3) s→next=p; p→next=s; (4) p→next=s→next; s→next=p;
3. 设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是( )
（1）A，B，C，D （2）D，C，B，A （3）A，C，D，B （4）D，A，B，C
4.若由树林转化得到的二叉树是非空的二叉树，则二叉树形状是（）
（1）根结点无右子树的二叉树（2）根结点无左子树的二叉树
（3）根结点可能有左二叉树和右二叉树（4）根结点只有一个孩子结点的二叉树
5．设二叉树的根为第一层，则深度为i的二叉树结点数最多为（）
（1）２i（2）２i+1 （3）２i-１（4）２i -1
6. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为()
（1）前序遍历（2）后序遍历（3）中序遍历（4）层次遍历
7．给定下列有向图，从顶点1出发，其广度优先搜索序列为（）
（1）12534 （2）12435 （3）14325 （4）12345
8．散列表中的冲突是指（）
（1）两个元素具有相同的序号（2）两个元素的关键字相同，而其他属性相同
（3）不同的关键字对应相同的存储地址（4）数据元素的地址相同
9. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（）
（1）必须是连续的（2）部分地址必须是连续的
（3）一定是不连续的（4）连续或不连续都可以
10．下面程序段的时间复杂度为（）
for (int i=1;i<m;i++)
for (int j=1;j<n;j++)
a[i][j]=i*j;
(1) O(m2) (2) O(n2) (3) O(m*n) (4) O(m+n)
11．当利用大小位的数组顺序存储一个队列时，该队列的最大长度为（）
（1）n-2 (2) n-1 (3) n (4)n+1
12．对线性表进行折半搜索时，要求线性表必须（）
（1）顺序存储（2）顺序存储且结点按关键字有序
（3）链式存储（4）链式存储且结点按关键字有序
13．采用线性探查法解决冲突时所产生的一系列后续地址
（）
（1）必须大于等于原散列地址（2）必须小于等于原散列地址
（3）可以大于或小于但不等于原散列地址（4）对地址在何处没有限制
14．栈的插入和删除操作在（）进行。
（1）栈顶（2）栈底（3）任意位置（4）指定位置
15．在一个顺序存储的循环队列中，对头指针指向队列的（）位置。
（1）前一个（2）后一个（3）当前（4）后面
二、填空题（每空1分，共20分）
1.数据的逻辑结构被分为
___0__________，________________，_________________，________________。
2.单链表与循环链表的区别是_______________________________。
3.在一个循环队列中，判断对空的条件是串是____________________，判断对满的条件是串是_______________________________
4. 从有序表（12，18，30，43，56，78，82，95）中一次折半搜索43和56元素是，其比较次数分别为_______和_______。
5.与哈西表的平均查找长度有关的三个因素分别是_____________________________，____________________ ，_____________________。
6.对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数个边数分别为_________和__________。
7.在二叉排序树中，左子树所有结点的关键字值都________该结点的关键码值，而右子树中所有结点的关键字值都_________该结点的关键码值。
8.在一个小顶堆中，堆顶元素的值是所有结点中的
______________，在一个大顶堆中，堆顶元素的值是所有结点中的______________。
9.假定一组纪录的关键字为（46，79，56，38，40，80），对其进行快速排序的一次划分的结果为__________________________________。
10.在一个网络的所有生成树中，各边权值之和最小的生成树，称为该网络的______________。
三、判断题（判断下列各题是否正确，
若正确在（）内打“√”，否则“×”。
每小
题1分，共10分）
（）1. 栈和队列的存储方式既可是顺
序方式，也可是链接方式。
（）2. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
（）
3.二叉树中任何一个结点的度都是2。
（）
4.有回路的有向图不能完成拓扑排序。
（）5.按先根次序遍历森林等同于按先序法遍历对应的二叉树。
（）6.n（n>1）个顶点的无向连通图最少由n-1条边。
（）7.有向图的邻接表表示中边表中结点的总数与有向图中有向边的条数相等。
（）8.一个无向图的邻接矩阵中各元素之和与图中边的条数相等。
（）9.归并排序要求待排序文件已部分排序。
（）10.顺序检索时数据的存储方式可以是顺序的，也可以是链接的。
四、综合题（共40分）
1．已知某系统在通信联络中只可能出现
8种字符，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。
(7分)
2．设待排序的记录的关键字序列为{12，2，16，30，10，20，18}，写出使用链式基数排序每趟的结果。
(6分)
3、拓扑排序的结果不是唯一的，对于下图的结点进行拓扑排序，试写出其中的任意5个。
(5分)
4．分别按前序、后序、对称序列写出下图二叉树的结点，并转化为树林，分别按先根次序、后根次序列出其结点。
(6分)
V
V
V
V
A
5.已知一组关键字为（19，14，23，01，68，20，84，27，55，11，10，79），则按哈希函数H(key)=key MOD 13,表长为13，分别用线性探查法和链地址法处理冲突构造哈希表，并计算各平均查找长度。
(10分)
6.程序填空(6分)
对有序表R[0]至R[n-1]进行二分查找，成功时返回记录在表中的位置，失败时返回0.
Struct sqlist
{ keytype key;
};
int binsrch(sqlist R[ ],keytype k)
//在表R中查找关键字k
{ int low ,high,mid;
low=0; high=n-1;
G H I
while( )
mid=(low+high)/2;
if (k==R[mid].key) return mid;
else if( k<R[mid].key )
;
else ;
}
return 0;
}。