数据结构模拟试卷.doc

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

1、数据结构模拟试卷（8）一、填空。1．算法的健壮性是指对于非法的输入也要能够给予正确的响应。2．对一个线性表分别进行遍历和逆置运算，其最好的时间复杂度分别为和O(n)O(n)。3．n个数入栈，所有可能的出栈序列共有种。4．下面程序段的时间复杂度为O()（n>1）。sum=1;for(i=0;sum

2、n树的根结点权值为30。7．线索二叉树的左线索指向其前驱，右线索指向其后继。8．若含n个顶点的图形成一个环，则它的生成树可能有n种。9．对于具有300个记录的文件，采用分块索引查找法查找，其中用二分查找法查找索引表，用顺序查找法查找块内元素，假定每块长度均为30个元素，则平均查找长度为29/10+31/2=18.4。10．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，经4次比较后查找成功。二、设一组记录的关键字为{4，5，7，2，

3、1，3，6}，请回答相关问题：（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求出在等概率情况下查找成功的平均查找长度。查找成功的平均查找长度18/7（2）按表中元素的顺序进行插入生成一棵AVL树，画出该树。并求出在等概率情况下查找成功的平均查找长度。?查找成功的平均查找长度?17/7三、下图是一个四阶B树，请回答相关问题：（1）B+树和B树的主要区别是什么？（2）插入关键字87，画出插入调整后树的形状。B树：每个结点的关键字个数等于指针个数减1。B+树：每个结点的

4、关键字个数等于指针个数。B+树中所有叶子结点包含了全部关键字信息,以及指向关键字记录的指针,叶子节点依关键字大小自小到大链接。非终端结点作索引,结点中含有其子树根结点的最大(最小)关键字。四、已知记录关键字集合为（53，17，19，61，98，75，79，63，46，49），要求散列到地址区间[0，10]中，散列函数选用除留余数法（mod11）。请回答相关问题：（1）画出形成的散列表（若产生冲突，用开放定址的线性探测再散列法解决）。01234567891075637946 491761195398（2）

5、计算在等概率情况下查找成功时的平均查找长度。18/10或1.8或9/5(2)在等概率情况下查找成功时的平均查找长度∞253∞∞∞∞∞2∞∞8∞∞∞∞135∞∞∞∞∞5∞∞∞∞∞∞∞39∞∞∞∞∞∞5∞∞∞∞∞∞∞五、有7个顶点（v1,v2,v3,v4,v5,v6,v7）的有向图的邻接矩阵如右图。请回答相关问题：（1）画出该有向图（2）画出邻接表（3）写出从v1出发的深度优先遍历和广度优先遍历序列（4分）深度dfsv1v4v5v7v6v3v2广度bfsv1v4v3v2v5v6?v7（4）将图看成AOE网，

6、画出关键活动及相应的有向边，写出关键路径的长度关键路径的长度为20六、设计算法。1．已知一棵树T用二叉树表示，其结点形式如下，试编写一算法求树T中各结点的度数。leftdatarightdegree（1）写出相应的结构定义。（2）编写算法。2．判断有向图是否存在回路。若存在返回1，否则返回0。（1）写出相应的结构定义。（2）编写算法。七、阅读下列函数，回答相关问题：intarrange(inta[],int1,inth,intx){//1和h分别为数据区的下界和上界inti,j,t；i=1；j=h；wh

7、ile(i=x)j--；while(i

8、有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数。intf(intb[],intn){intp,q;p=arrange(b,0,n-1,0);q=arrange(b,p+1,n-1,1);returnq-p;}八、数组a存储了N个整数，请回答相关问题：（1）请完善对数组a进行堆排序的程序。voidHeapAdjust（inta[],inth,ints）{rc=a[h];for（j=2*h;j<=s;j*=2）