湖大数据结构模拟卷

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

1、Source：http://210.43.96.230:10007/Course/Index.htm考试中心填写：湖南大学课程考试试卷课程名称：数据结构；试卷编号：A；考试时间：120分钟年月日考试用专业班级：题号一二三四五六七八九十总分应得分10105030100实得分评分：评卷人得分一、填空题（每空1分，共10分）1、在具有n个单元的循环队列中，队满时共有个元素。2、假设在有序线性表a[20]上进行折半查找，则比较3次查找成功的结点数为。3、对有序数组进行二分查找的时间复杂度为。4、设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q

2、，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是。5、当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用排序。6、一棵结点数为N的二叉树，其所有结点的度的总和是。7、设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为。8、散列法存储的基本思想是由决定数据的存储地址。9、对不带权图进行遍历可求得单源最短路径。10、设一个连通图G中有n个顶点e条边，则其最小生成树上有条边。装订线（答题不得超过此线）学号：姓名： 第1页（共4页）分二、单选题（每小题1分，共10分，本题所给四个答案中只有一个是正确的）1、若已知一个栈的入栈序列

3、是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）（Ａ）i（Ｂ）n=i（Ｃ）n-i+1（Ｄ）不确定2、线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（）（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以3.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（）（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）（B）在第i个结点后插入一个新结点（1≤i≤n）（C）删除第i个结点（1≤i≤n）（D）将n个结点从小到大排序4、具有n(n>0)个结点的完全二叉树的深度为（）。(Ａ)élo

4、g2(n)ù(Ｂ)ëlog2(n)û(Ｃ)ëlog2(n)û+1(Ｄ)élog2(n)+1ù5、有n个顶点e条边的无向图G,它的邻接表中的表结点总数是（）。(A)2n(B)n(C)2e(D)e6、静态查找表与动态查找表二者的根本差别在于（）（A）它们的逻辑结构不一样（B）施加在其上的操作不同（C）所包含的数据元素的类型不一样（D）存储实现不一样7、连通图G中有n个顶点,G的生成树是（）连通子图.(A)包含G的所有顶点(B)包含G的所有边(C)不必包含G的所有顶点(D)必须包含G的所有顶点和所有的边8、设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用（）法。（A）

5、冒泡排序（B）快速排序（C）堆排序（D）基数排序9、下面的排序算法中，（）是不稳定的？（A）希尔排序（B）冒泡排序（C）直接插入排序（D）基数排序10、散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系，所以选择好的（）方法是散列文件的关键。（A）散列函数（B）除余法中的质数（C）冲突处理（D）散列函数和冲突处理得分四、应用题（每小题10分，共50分）1.已知一棵二叉树的后序遍历的结果是ACDBHJIGFE,中序遍历的结果是ABECDFGHIJ,试画出这棵二叉树，并给出前序遍历的结果。2.假设某AVL树的输入关键码的顺序为16,3,7,11,9,26,1

6、8,14,15，请给画出这棵AVL树，（要求画出插入和调整过程）。∧∧454542310A1B2C3D4E5F∧∧∧∧3．已知一有向图的邻接表（如图），试写出:1）从顶点A出发进行广度优先搜索所得到的广度优先生成树；2）请对其进行拓扑排序，输出其拓扑排序序列。4.排序的排序码序列为{12,16,30,28,10,18},试分别写出使用以下排序方法按从小到大排列，每趟排序后的结果。(1)快速排序(2)冒泡排序5.设散列表为HT[13],散列函数为H(key)=key%13。用闭散列法解决冲突,对下列关键码序列12,23,45,57,20,03,78,31,15,36造表。(1)采用线性探查法寻找

7、下一个空位,画出相应的散列表,(2)计算等概率下搜索成功的平均搜索长度。得分五、算法设计题（共30分）1．请根据函数f(n)的C语言代码，写出f(n)的值和推导过程，并给出算法的阶O(?)：（5分）intf(intn){inti,j,k,sum=0;for(i=1;ii-1;j--)for(k=1;k