数据结构期末考试试卷.doc

PAGE

第PAGE1页共NUMPAGES6页

数据结构期末考试试卷

一、判断题（每题1分，共10分）

1．线性表的逻辑顺序与存储顺序总是一致的。（错）

2．线索二叉树中，任一结点均有指向前趋和后继的线索。（错）

3．栈、队列、数组和串都是线性结构。（对）

4．KMP算法是一个不需要回溯的字符串模式匹配算法。（对）

5．图的生成树是该图的极小连通子图。（对）

6．树的后序遍历序列与其对应二叉树的后序遍历序列相同。（错）

7．二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。（错）

8.如果某排序算法是不稳定，则该排序算法没有实用价值。（错）

9．稀疏矩阵压缩存储后，就会失去随机存取功能。（对）

10．归并排序可以使用递归和非递归两种方法实现。（对）

填空题（共20分,每空2分）

设源串s=“bababaaba”，模式串p=“babaa”，按照KMP算法进行模式匹配，当“”=“”，而时，应与__p3__比较。

下列算法的时间复杂性是O(n1/2)。

intfun(intn)

{inti=1,s=1;

while(sn)s+=++i;

returni;

}

表达式3/(x+2)-8所对应的后缀表达式是3x2+/8-。

假设以一维数组作为n阶对称距阵A的存储空间，以行序为主序存储A的下三角，则元素A[5][8]的值存储在S[__41___]中。

5．下列函数的功能是实现两个字符串的比较，试根据字符串比较运算的定义，完善该函数：

intstrcmp(chars[],chart[])

{inti;

for(i=0;s[i]t[i];i++)

if(s[i]!=t[i])___return_s[i]-t[i]________;

return_s[i]-t[i];

}

6.最坏情况下，堆排序的时间复杂性为nlog2n。

7．具有100个结点的完全二叉树，其叶子结点数为50。

8．利用拓扑排序算法可以判断一个有向图是否存在回路。

9．对于具有100个记录的文件，用顺序查找法查找索引表和块内元素，假定每块长度均为10个元素，则平均查找长度为10。

三．简要回答下列问题（共30分）

1．评价一个排序算法好坏的标准是什么？你知道有哪些排序算法？试比较它们各自的性能。（10分）

正确性：逻辑

健壮性：多类数据测试

可读性：格式结构化

高效，低存储：空间/时间复杂度

2.图的存储方法主要有哪些？试举例具体说明图的存储结构；并说明Prim，Krurkal，Dijkstra，Floyed算法的功能。（10分）

图的存储方法有两种1：邻接表2：邻接矩阵

PrimKruskal求最小生成树算法

Dijkstra求图中从某个源点到其余各顶点的最短路径

Floyd求每一个顶点之间的最短路径问题

3.已知一组关键字为（26，36，41，38，44，15，68，12，06，51，25），Hash函数定义为：H(key)=key%13。用拉链法解决冲突，建立Hash表，分别计算查找成功和查找失败情况下的平均查找长度。（10分）

查找成功：ASL=(7*1+1*2+1*3+1*4)/11=16/11

查找失败时：ASL=(1+2+1+1+1+1+4)/13=11/13

四．试编写折半查找算法。（10分）

intSeqList::BinFind(inte)

{

intlow=0;

inthigh=m_Data.size()-1;

while(low=high)

{

intmid=(low+high)/2;

if(m_Data[mid]==e)

returnmid;

if(m_Data[mid]e)

low=mid+1;

else

high=mid-1;

}

return-1;

}

五、设有整型数组x,试编写算法：将负数集中在数组x的一端，正数集中在