天津大学《数据结构(主干课程)》期末考试题集汇总.pdfVIP

天津大学《数据结构(主干课程)》奥鹏期末考试题库合集

本套合集为考前突击题集汇总，含答案

问答题：

1.何时选用顺序表、何时选用链表作为线性表的存储结构为宜?

标准答案：在实际应用中,应根据具体问题的要求和性质来选择顺序表或链表作为线

性表的存储结构,通常有以下几方面的考虑:

A.基于空间的考虑。当要求存储的线性表长度变化不大,易于事先确定其大小时,为

了节约存储空间,宜采用顺序表;反之,当线性表长度变化大,难以估计其存储规模

时,采用动态链表作为存储结构为好。

B.基于时间的考虑。若线性表的操作主要是进行查找,很少做插入和删除操作时,采

用顺序表做存储结构为宜;反之,若需要对线性表进行频繁地插入或删除等的操作

时,宜采用链表做存储结构。并且,若链表的插入和删除主要发生在表的首尾两端,

则采用尾指针表示的单循环链表为宜。

2.已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历

所得的深度优先生成树和广度优先生成树。

标准答案：

3.已知某哈希表的装载因子小于1,哈希函数H(key)为关键字(标识符)的第一个字母

在字母表中的序号,处理冲突的方法为线性探测开放定址法。试编写一个按第一个字

母的顺序输出哈希表中所有关键字的算法。

标准答案：此题装载因子a〈1,则哈希表未填满。假设表长为m,由此可写出下列形

式简明的算法:

voidPrintWord(HashTableht)

{//按第一个字母的顺序输出哈希表ht中的标识符。哈希函数为表示符的第一个字母

在字母表中的序号,处理冲突的方法是线性探测开放定址法。

for(i=1;i=26;i++){

j=i;

While(ht.elem[j].key){

if(Hash(ht.elem[j].key==i)printf(ht.elem[j].key);

j=(j+1)%m;

}

}

1

本页为预览页-

}//PrintWord

（4）解释拓扑排序,并简述如何进行拓扑排序。

标准答案：由某个集合上的一个偏序得到该集合上的一个全序,这个操作就成为拓扑

排序。

拓扑排序的操作如下:

(1)在有向图中选一个没有前驱的顶点并输出之;

(2)从图中删除该顶点和所有以它为尾的弧。

重复上述两步,直至全部顶点均已输出,或者当前图中不存在无前驱的顶点为止。后一

种情况则说明有向图中存在环。

（5）快速排序的执行时间,在什么情况下时间最长,这时的总比较次数为多少,在什么

情况下时间最短,这时最短的总比较次数又为多少?

标准答案：在待排序记录已经排序的情况下,时间最长,总比较次数为n(n-1)/2。每

趟递归调用一次,给一个记录的位置正好是文件的蹭,从而把原文件分成两个大小相等

的子文件,在这种情况下,时间最短,总的比较资料为O(nlog2n)。

（6）已知一棵二叉树的先序序列是ABCDEFGHIJK,中序序列是CDBGFEAHJIK,请构造出

该二叉树。

标准答案：

（7）用邻接矩阵法写出下图的存储结构。

标准答案：邻接矩阵:01001

00001

01000

00100

00010

（8）用标准C语言实现Hanoi塔问题。

标准答案：VoidHanoi(intn,charx,chary,charz)

{

2

本页为预览页-