《烟台大学数据结构试题2010~2011年度》由会员分享，可在线阅读，更多相关《烟台大学数据结构试题2010~2011年度（6页珍藏版）》请在金锄头文库上搜索。
1、烟台大学20 10 20 11 学年第 二 学期数据结构 试卷B（考试时间为120分钟）题号一二三四五总分得分阅卷人合分人（注：第三大题答案请写在后面的空白答题纸上）一、单项选择题(每小题2分，共20分) 1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( d ) A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 2.在长度为n的顺序表的第i (1in+1)个位置上删除一个元素，元素的移动次数为( B ) A.n-i+1 B.n-i C.i D.i-1 3.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( c ) A.顺序表 B.用头
2、指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表 4.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的出栈的不同排列个数为( b ) A.4 B.5 C.6 D.7 5.已给下图1，哪一项是该图的拓扑排序序列 （ a ） (图1) A1，2，3，4，5 B1，3，2，4，5 C1，2，4，3，5 D1，2，3，5，46. 一组记录的值为(12,38,35,25,74,50,63,90),按2路归并排序方法对序列进行一趟归并后的结果为( a )。A.12,38,25,35,50,74,63,90 B.12,38,35,25,74,50,63,90 C.12,25,35
3、,38,50,74,63,90 D.12,35,38,25,63,50,74,907.n个顶点的有向图中含有向边的数目最多为 ( d ) A.n-1 B.n C.n(n-1)/2 D.n(n-1) 8.AVL树是一种平衡的二叉排序树，树中任一结点的( b ) A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度 9.设有6个结点的无向图，该图至少应有( a )条边才能确保是一个连通图。 A.5 B.6 C.7 D.810.为查找某一特定单词在文本中出现的位置，可应用的串运算是( d ) A.插入 B.删除 C.
4、串联接 D.子串定位 二、填空题(每小题2分，共20分)1. 存储结构是逻辑结构的_物理_实现。2. 若一个算法中的语句频度之和为T(n)=n+4nlogn，则算法的时间复杂度为_ nlogn _。 3. 设二维数组A1.10,1.20按行优先顺序存储,每个元素占4个存储单元，A1，1的存储地址是1000，则A5，6的存储地址是 1260 。4. 在无向图的邻接矩阵A中，若Ai,j等于1，则Aj,i等于_1_。 5.在具有n个单元的循环队列中，队满时共有_ n-1_个元素。6.在序列(2,5,8,11,15,16,22,24,27,35,40)中采用折半查找查找元素24，需进行 4 次元素之间
5、的比较。 7.深度为h的完全二叉树至少有_ 2h-1_个结点，至多有_2h-1_个结点。8.直接插入排序需要_ O(1)_个记录的辅助空间。9.在直接插入排序和快速排序中，若初始数据基本有序，则选用_直接插入_；在冒泡排序和堆排序中，若要求数据的稳定性，则选用_冒泡_。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)进行堆排序，使之按关键字递增次序排列，请写出排序
6、过程中建初始堆的过程。3 已知散列表长度为11，散列函数为H(key)=key9，处理冲突的方法为拉链法，请画出依次插入关键字（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（图2） 无向图如图3所示，要求：写出该
7、图从顶点1开始的广度优先和深度优先搜索序列。 将图4所示的二叉树转化为森林。四算法设计题（共2小题，共20分）1 设有两个栈s1和s2共享同一数组存储空间stackm，请编写栈s1和s2的进栈操作push(i,x)和退栈操作pop(i)，其中i=1、2，分别表示栈s1和s2。要求：仅当整个空间stackm占满时才产生上溢。（10分）2写出求一棵二叉树的叶子结点个数的算法。二叉树的存储结构为二叉链表，要求写出二叉链表的类型定义。（10分）烟台大学20 1o 20 11 学年第 二 学期数据结构试卷A参考答案及评分标准考试方式： 闭卷 （开卷、闭卷、其他）院系： 计算机学院 年级： 02级专 专业
8、： 计算机 .注：标准答案、参考答案要点及评分标准须写清题号、每小题得分、共得分等。 此格式为题头，如本页不够，后面请附相同规格（A4）的纸张。.一、选择题(每小题2分，共20分) 1.A 2.D 3.A 4.C 5.C 6.D 7.D 8.D 9.A 10.D二、填空题(每小题2分，共30分) 1. 物理 2. nlogn 3. 913 4. 1 5. lq-front-next=lq-rear 6. (sq.front+1)%(m+1) 7. sq.front=(sq.front+1)%(m+1) 8. 4 9. top=0 10. 3 11. 2h-1 12. 4 13. 直接插入、冒泡
9、452453122890 14. (c,d) 15.(10,28,36,42,59,84)三、应用题(每小题5分，共35分)1.ASLsucc=(1*1+2*2+3*3)/6=7/35620237529613687562023872961367556206187292336752.568761752923362087756156292336203.地址0123456789101112元素2357465627408191021查找成功时的1724632109查找不成功时的ABFCHGDE4. 5. 前序序列：ABCDEFGH611571231654412161123165123165445712
10、3165446.V1V2V3V4V5V602/V13123/V176/V313111310/V413/V37.四算法设计题（共2小题，共15分）1. void DeleteEqual2(LinkekList L) 2. int BinTreeDepth(BitTree T) /删除元素非递减排列的链表L中所有值相同的元素 if(T=NULL)return 0; p=L-next;q=p-next; elsel=BinTreeDepth(T-lchild); while(p-next) r=BinTreeDepth(T-rchild); if(p-data!=q-data) return(lr?l:r)+1); p=p-next;q=p-next; else /当相邻元素相等时删除多余元素p-n
