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

发布时间：2023-11-14 发布人：admin 分类：说明书资料大小：0.04M 资料格式：doc 举报版权申诉

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2017 年山东烟台大学数据结构考研真题 D.(n+1)/2 B.i-j C.j-i+1 D.不确定的 D.head!=NULL B.n/2 C.(n-1)/2 C.head→next==head 一、单项选择题(本大题共 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 5.对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是（）。 A.head==NULL B.head→next==NULL 6.若一个栈的输入序列为 1,2,3,…,n,输出序列的第一个元素是 i,则第 j 个输出元素是（）。 A.i-j-1 7.顺序存储的循环队列，存储空间大小为 n,队头结点下标为 front,队尾结点下标为 rear。则此循环队列中的元素个数为（）。 A.n+front-rear C.(rear-front)%n 8.判断一个表达式中左右括号是否匹配，采用（）实现较为方便。 A.线性表的顺序存储 B.队列 C.线性表的链式存储 D.栈 9.串是一种特殊的线性表，其特殊性表现在（） A.可以顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是多个字符 10.串‘ababaaababaa’的 next 数组为（）。 A.012345678999 11.对稀疏矩阵进行压缩存储目的是（）。 A.便于进行矩阵运算 B.便于输入和输出 C.节省存储空间 D.降低运算的时间复杂度 12.设广义表 L=((a,b,c)),则 L 的长度和深度分别为（）。 A.1 和 1 13.若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是（）。 A.9 14.设森林 P 中有三棵树，第一，第二，第三棵树的结点个数分别为 M1,M2 和 M3。与森林 F 对应的二叉树根结点的右子树上的结点个数是（）。 A.M1 B.M1+M2 D.(n+rear-front+1)%n D.0123012322345 B.1 和 3 C.1 和 2 D.2 和 3 B.rear-front+1 B.11 C.15 D.不确定 C.011234223456 B.012121111212 C.M3 D.M2+M3

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

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),请构造相应的哈夫曼树，并求出带权路径长度 WPL。 9. 已知一组关键字为{22,18,51,2,53,38,32,4,69,67,59,11},构造相应的二叉排序树，并求在等概率的情况下查找成功的平均查找长度。 10. 编写一算法，求顺序表(al,a2,a3, …… ,an)中的最大元素。五、简答题(本大题共 1 小题，共 10 分) 叙述顺序查找、二分查找和分块查找法对表中元素的要求。对于长度为 n 的表来说，3 种查找方法在查找成功时的平均查找长度各是多少?

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料