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

《数据结构期中期末考试试卷.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》课程期末考试试卷2009年6月27日，（时间）命题人：院系学号姓名成绩一、填空。（每题2分，共计20分）1．算法的健壮性是指。2．对一个线性表分别进行遍历和逆置运算，其最好的时间复杂度分别为和。3．n个数入栈，所有可能的出栈序列共有种。4．下面程序段的时间复杂度为（n>1）。sum=1;for(i=0;sum

2、向其，右线索指向其。8．若含n个顶点的图形成一个环，则它的生成树可能有种。9．对于具有300个记录的文件，采用分块索引查找法查找，其中用二分查找法查找索引表，用顺序查找法查找块内元素，假定每块长度均为30个元素，则平均查找长度为。10．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，经次比较后查找成功。二、设一组记录的关键字为{4，5，7，2，1，3，6}，请回答相关问题：（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求出在等概率情况下查找

3、成功的平均查找长度。（3分）（2）按表中元素的顺序进行插入生成一棵AVL树，画出该树。并求出在等概率情况下查找成功的平均查找长度。（4分）三、下图是一个四阶B树，请回答相关问题：（1）B+树和B树的主要区别是什么？（4分）（2）插入关键字87，画出插入调整后树的形状。（4分）四、已知记录关键字集合为（53，17，19，61，98，75，79，63，46，49），要求散列到地址区间[0，10]中，散列函数选用除留余数法（mod11）。请回答相关问题：（1）画出形成的散列表（若产生冲突，用开放定址的线性探测再散列法解决）。（4分）（2）计算在等概率情况下

4、查找成功时的平均查找长度。（2分）∞253∞∞∞∞∞2∞∞8∞∞∞∞135∞∞∞∞∞5∞∞∞∞∞∞∞39∞∞∞∞∞∞5∞∞∞∞∞∞∞五、有7个顶点（v1,v2,v3,v4,v5,v6,v7）的有向图的邻接矩阵如右图。请回答相关问题：（1）画出该有向图（2分）（2）画出邻接表（2分）（3）写出从v1出发的深度优先遍历和广度优先遍历序列（4分）（4）将图看成AOE网，画出关键活动及相应的有向边，写出关键路径的长度（4分）六、设计算法。（24分）1．已知一棵树T用二叉树表示，其结点形式如下，试编写一算法求树T中各结点的度数。（12分）leftdatarig

5、htdegree（1）写出相应的结构定义。（2）编写算法。2．判断有向图是否存在回路。若存在返回1，否则返回0。（12分）（1）写出相应的结构定义。（2）编写算法。七、阅读下列函数，回答相关问题：intarrange(inta[],int1,inth,intx){//1和h分别为数据区的下界和上界inti,j,t；i=1；j=h；while(i=x)j--；while(i

6、returni－1；}（1）写出该函数的功能（4分）（2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。（6分）八、数组a存储了N个整数，请回答相关问题：（1）请完善对数组a进行堆排序的程序。（6分）voidHeapAdjust（inta[],inth,ints）{rc=a[h];for（j=;j<=s;j*=2）{if（（j

7、）break;;h=j;};}voidHeapSort（inta[],intn）//对a[1]，a[2]，…，a[n]进行堆排序//{for（i=;i>0;--i）HeapAdjust（a,i,n）;for（i=;i>1;--i）{t=a[1];a[1]=a[i];a[i]=t;;}}（2）上面程序建成的堆是大顶堆还是小顶堆？（2分）（3）对n个元素进行初始建堆的过程中，最多进行次数据比较。（2分）（4）堆排序稳定吗？请举例说明。（3分）