烟台大学数据结构试题2010~2011年度

《烟台大学数据结构试题2010~2011年度》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、烟台大学2010～2011学年第二学期数据结构试卷B（考试时间为120分钟）题号一二三四五总分得分阅卷人合分人（注：第三大题答案请写在后面的空白答题纸上）一、单项选择题(每小题2分，共20分)1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为(d)A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构2.在长度为n的顺序表的第i(1≤i≤n+1)个位置上删除一个元素，元素的移动次数为(B)A.n-i+1B.n-iC.iD.i-13.对于只在表的首、尾两端进行插入操作的线性表

2、，宜采用的存储结构为(c)A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表4.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的出栈的不同排列个数为(b)A.4B.5C.6D.75.已给下图1，哪一项是该图的拓扑排序序列①（a）②③④⑤(图1)A．1，2，3，4，5B．1，3，2，4，5C．1，2，4，3，5D．1，2，3，5，46.一组记录的值为(12,38,35,25,74,50,63,90),按2路归并排序方法对序列进行一趟归并后的结果为(a)。A.12,3

3、8,25,35,50,74,63,90B.12,38,35,25,74,50,63,90C.12,25,35,38,50,74,63,90D.12,35,38,25,63,50,74,907.n个顶点的有向图中含有向边的数目最多为(d)A.n-1B.nC.n(n-1)/2D.n(n-1)8.AVL树是一种平衡的二叉排序树，树中任一结点的(b)A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度9.设有6个结点的无向图，该图至少

4、应有(a)条边才能确保是一个连通图。A.5B.6C.7D.810.为查找某一特定单词在文本中出现的位置，可应用的串运算是(d)A.插入B.删除C.串联接D.子串定位二、填空题(每小题2分，共20分)1.存储结构是逻辑结构的____物理______实现。2.若一个算法中的语句频度之和为T(n)=n+4nlogn，则算法的时间复杂度为___nlogn_____。63.设二维数组A[1..10,1..20]按行优先顺序存储,每个元素占4个存储单元，A[1，1]的存储地址是1000，则A[5，6]的存储地址是1

5、260。4.在无向图的邻接矩阵A中，若A〔i,j〕等于1，则A〔j,i〕等于__1______。5.在具有n个单元的循环队列中，队满时共有___n-1______个元素。6.在序列(2,5,8,11,15,16,22,24,27,35,40)中采用折半查找查找元素24，需进行4次元素之间的比较。7.深度为h的完全二叉树至少有___2h-1______个结点，至多有__2h-1_______个结点。8.直接插入排序需要____O(1)_____个记录的辅助空间。9.在直接插入排序和快速排序中，若初始数据基

6、本有序，则选用_直接插入________；在冒泡排序和堆排序中，若要求数据的稳定性，则选用__冒泡_______。10．广义表运算式TAIL(((a,b)，(c,d)))的运算结果为((c,d))。三．应用题（每小题5分，共40分）11．设有序列(45，24，53，12，28，90)，请构成一棵二叉排序树，并求其查找成功时的平均查找长度。2．对关键字序列(42，13，24，91，23，16，05，58)进行堆排序，使之按关键字递增次序排列，请写出排序过程中建初始堆的过程。3．已知散列表长度为11，散列函

7、数为H(key)=key％9，处理冲突的方法为拉链法，请画出依次插入关键字（8,10,14,19,21,23,28,32,48）以后的散列表。4．已知某二叉树按中序遍历次序是BDCEAFHG，按后序遍历次序是DECBHGFA，试画出该二叉树的形状，并写出它的前序扫描序列。5．以数据集（7，19，2，6，32，3，21，10）为叶结点的权值，构造一棵哈夫曼树。ABCEDFGH(图4)6．已给无向图如图2所示，用Prim算法画出该图从顶点1开始的最小生成树。123456（图3）12345626510378（

8、图2）７．无向图如图3所示，要求：写出该图从顶点1开始的广度优先和深度优先搜索序列。８．将图4所示的二叉树转化为森林。四．算法设计题（共2小题，共20分）1．设有两个栈s1和s2共享同一数组存储空间stack［m］，请编写栈s1和s2的进栈操作push(i,x)和退栈操作pop(i)，　其中i=1、2，分别表示栈s1和s2。要求：仅当整个空间stack［m］占满时才产生上溢。（10分）2．写出求一棵二叉树的叶子结点个数的算法。二叉树的存储结