2017年山东烟台大学数据结构考研真题.doc

历年考试真题2017年山东烟台大学数据结构考研真题一、单项选择题(本大题共20小题，每小题2分，共计40分)1.数据结构被形式的定义为(D,R),其中D是数据元素的有限集合，R是D上（）的有限集合A.操作 B.映象 C.存储 D.关系2.下面关于算法说法错误的是（）A.算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的3.线性表采用链式存储时，其地址（）A.必须是连续的 B.部分地址必须是连续的C.一定是连续的 D.连续与否均可4.在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为（）A.n B.n/2 C.(n-1)/2 D.(n+1)/25.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A.head==NULL B.head→next==NULL C.head→next==head D.head!=NULL6.若一个栈的输入序列为1,2,3,…,n,输出序列的第一个元素是i,则第j个输出元素是（）A.i-j-1 B.i-j C.j-i+1 D.不确定的7.顺序存储的循环队列，存储空间大小为n,队头结点下标为front,队尾结点下标为rear。

则此循环队列中的元素个数为（）A.n+front-rear B.rear-front+1C.(rear-front)%n D.(n+rear-front+1)%n8.判断一个表达式中左右括号是否匹配，采用（）实现较为方便A.线性表的顺序存储 B.队列 C.线性表的链式存储 D.栈9.串是一种特殊的线性表，其特殊性表现在（）A.可以顺序存储 B.数据元素是一个字符C.可以链接存储 D.数据元素可以是多个字符10.串‘ababaaababaa’的next数组为（）A.012345678999 B.012121111212 C.011234223456 D.012301232234511.对稀疏矩阵进行压缩存储目的是（）A.便于进行矩阵运算 B.便于输入和输出C.节省存储空间 D.降低运算的时间复杂度12.设广义表L=((a,b,c)),则L的长度和深度分别为（）A.1和1 B.1和3 C.1和2 D.2和313.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A.9 B.11 C.15 D.不确定14.设森林P中有三棵树，第一，第二，第三棵树的结点个数分别为M1,M2和M3。

与森林F对应的二叉树根结点的右子树上的结点个数是（）A.M1 B.M1+M2 C.M3 D.M2+M315.树的后根遍历序列等同于该树对应的二叉树的（）A.先序遍历序列 B.中序遍历序列 C.后序遍历序列 D.层次遍历序列16.要连通具有n个顶点的有向图，至少需要（）条边A.n1 B.n C.n+1 D.2n17.设使用的邻接表表示某有向图，则顶点vj在表结点中出现的次数等于（）A.顶点vj的度 B.顶点vj的出度 C.顶点vj的入度 D.无法确定18.对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（）A.0(n) B.O(e) C.0(n+e) D.0(n*e)19.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则查找成功前提下的平均查找长度为（）A.(N+1)/2 B.N/2 C.N D.[(1+N)*N]/220.若需在0(nloggn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）A.快速排序 B.堆排序 C.归并排序 D.直接插入排序二、判断题(本大题共10小题，每小题1分，共计10分)1.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

2.一棵有n个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i的结点的左儿子的编号为2i(2i

8. 当广义表中的每个元素都是原子时，广义表便成了（）9. 满二叉树上各层的节点数已达到了二叉树可以容纳的（） 满二叉树也是 （） 二叉树， 但反之不然10. 二叉树通常有（）存储结构和（）存储结构两类存储结构11. 如果结点a有三个兄弟，而且b是a的双亲， 则b的度是（） 12. 遍历图的基本方法有（） 优先搜索和（）优先搜索两种13. 若G为有向图，有n个顶点，则图至少有（） 条弧，最多有（）条弧14. 动态查找表和静态查找表的重要区别在于前者包含有 （）和（） 运算，而后者不包含 这两种运算15. 按照排序过程涉及的存储设备的不同，排序可分为（） 排序和（） 排序四、 综合题(本大题共10小题，每小题6分，共60分)1. 已知一个栈的进栈序列是1,2,3, …,n,其输出序列是pl,p2, …,pn,若pl=n,求pi的值2. 已知KMP 串匹配算法中子串为“abcabcaaa”,写出其next值3. 求下列广义表操作的结果：(1)GetHead((a,b,c)),（）（） (2)GetHead(GetTail((a,b),(c,d)))4. 设森林F中有3棵树A、B、C,其结点个数分别为11、8和12,计算与森林F对应的二叉树Bf 根节点A的左子树上的结点的个数，并画出该二叉树结构图。

5. 已知某二叉树按中序遍历次序是BDCEAFHG,按后序遍历次序是DECBHGFA,试画出该二叉树的 形状，并写出它的前序遍历序列6. 给出下图(1),写出采用克鲁斯卡尔算法构造最小生成树的过程7. 对于关键字序列{55,73,11,80,20,41,28,52,34,67},写出使用直接插入法进行排序的过程8. 对数据序列(4,3,8,9,11,10),请构造相应的哈夫曼树，并求出带权路径长度WPL9. 已知一组关键字为{22,18,51,2,53,38,32,4,69,67,59,11},构造相应的二叉排序树，并求在等概率的情况下查找成功的平均查找长度10. 编写一算法，求顺序表(al,a2,a3, …… ,an)中的最大元素五 、简答题(本大题共1小题，共10分)叙述顺序查找、二分查找和分块查找法对表中元素的要求对于长度为n的表来说，3种查找方法在查找成功时的平均查找长度各是多少?3 / 3。