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

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

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2019 年山东烟台大学数据结构考研真题一、单项选择题(本大题共 20 小题，每小题 2 分，计 40 分) 1.算法的时间复杂度主要取决于( )。 A.计算的环境 B.待处理数据的值 C.问题的规模 D.数据的类型 2.算法应具备( )这三个特性。 A.可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性 3.以下与数据的存储结构无关的术语是( )。 A.循环队列 B.链表 C.哈希表 D.栈 4.以下数据结构中，哪一个是非线性结构( )? A. 串 B.队列 C.栈 D.广义表 5.分析下面的程序，算法的时间复杂度为( )。 for(k=1;k,, ,,,,,},则图 G 的拓扑序列是()。 A.V1,V3,V4,V6,V2,V5,v7 B.V1,V3,V2,V6,V4,V5,V7 C.V1,V3,V4,V5,V2,V6,v7 D.V1,v2,V5,V3,V4,V6,V7 12.设单链表中指针 p 指向结点 A,若要删除 A 的直接后继，则所需修改指针的操作为( )。 A.p->next=p->next->next B.p=p->next C.p=p->next->next D.p->next=p 13.数据表 A 中每个元素距其最终位置较近，则最省时间的排序算法是( )。 A.插入排序 B.堆排序 C.直接选择排序 D.快速排序 14.一棵二叉树的中根遍历序列为 debac,后根逸历序列为 dabec,,则先根遍历序列为( )。 A.acbed B.cedba C.deabc D. becab 15.在一个有向图中，所有顶点的度数之和与图的边数的比是( )。 A. 1:2 B.1:1 C. 2:1 D.4:1 16.含有 n 个结点的二叉树用二叉链表表示时，空指针域个数为( )。 A.n-1 B.n C.n+1 D.n+2 17.对称矩阵 A[N]N],A[1I[]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一

维数组元素 T[1]至 T[N(N+1)/2]中，则任一下三角元素 A[J[6]存于 Tk]中，下标 k 为( )。 A.i*(i-1)/2+j B.jG-1)/2+1 C.iG-i)/2+1 D.j(-1)/2+1 18.设有数组 A[i,j],数组的每个元素长度为 3 字节，i 的值为 1 到 8,j 的值为 1 到 10,数组从内存首地址 adr 开始顺序存放，当用以列为主存放时，元素 A[5,8]的存储首地址为()。 A. adr+141 B. adr+180 C. adr+222 D. adr+225 19.链表不具有的特点是( ) A、插入/删除不需要移动元素 B、可随机访问任一元素 C、不必事先估计存储空间 D、所需空间与线性长度成正比 20.已知二叉树中叶子数为 40,仅有一个孩子的结点数为 20,则总结点数为( )。 A、91 B、92 C、98 D、99 二、填空题(本大题共 30 个空项，每个空项 1 分，计 30 分) 1.数据结构是一门研究程序设计中数据的(1)_以及他们之间的(2)和运算等的学科。 2.在数据结构中，从逻辑上可以把数据结构分为_(3)_和(4)_两类。 3.数据的存储结构是一个数据结构在计算机中的(5)。 4.顺序存储结构是逻辑上(6)的节点存储在(7)_中。 5.算法的五个特性是(8)、(9)、(10)、输入和输出。 6.在线性表的链式存储中，元素之间的逻辑关系是通过(11)决定的；在线性表的顺序存储中，元素之间的逻辑关系是通过_(12)决定的。 7.从数据结构定义看，栈和队列都是(13)_的线性表；栈具有_(14)_的特性。 8.栈和队列的共同特点是只允许在端点处进行(15)和(16)。 9.用带头节点的单链表表示栈，则栈空的标志是(17)_ 10.根据串的定义，串是含有 n 个字符的_(18)序列；串“how are you!”的长度是(19)。 11.两个串相等的充分必要条件是(20)。 12.递归关系指的是一个数列的若干(21)_之间的关系；递归过程指的是(22)或(23)_调用自身的过程。 13.常常用到递归算法的三种情况是(24)、(25)、(26)· 14.将 f=1+1/2+1/3+……+1/n 转化为递归函数，其递归出口是(27),递归体是(28)。 15.一维数组的逻辑结构是(29),存储结构是(30)。三、判断下列语句的正确性(对/错)(本大题共 15 小题，每小题 1 分，计 15 分) 1.顺序存储的线性表可以实现随机存取。 2.在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。 3.插入和删除操作是数据结构中两种基本的操作，所以这两种操作在数组中也会经常使用。 4,任何有向网拓扑排序的结果是唯一的。 5.任何递归算法都有递归出口。 6.在树形结构中，处于同一层上的各个节点存在兄弟关系。 7.递归算法的执行效率一般高于功能相同的非递归算法的执行效率。 8.KMP 算法的最大特点是指示主串的指针不需要回溯。 9.广义表的长度不小于任一子表的长度。 10.完全二叉树中的每个节点的度或者是 0 或者为 2。 11.哈夫曼树中权值较大的节点一般离根节点较近。 12。对图而言，所谓的简单路径指的是任何一个顶点在这条路径上不重复出现。 13.图的邻接矩阵表示是唯一的。 14.顺序查找既可以在顺序表上进行也可以在链表上进行，随机查找只能在链表上进行。

15.二叉排序树主要是用来进行排序的。四、分析论述题(共 6 个小题，每小题 5 分，计 30 分) 1.简述数据元素、数据结构和数据类型以及三者之间的关系。 2.分析叙述线性表的两种存储结构的特点。 3.叙述图的两种主要存储结构，说明它们各自的优缺点。 4.简述顺序查找法、二分查找法和分块查找法；说明这三种查找方法对被查找的表中元素的要求；对于长度为 n 的表，三种查找方法在成功查找时的平均查找长度分别是多少? 5.(1)简要回答：什么是内排序?什么是外排序? (2)从时间复杂度和算法稳定性两个方面分析、比较以下几种排序方法：直接插入排序、冒泡排序、快速排序、直接选择排序和归并排序。 6.请从森林和二叉树的对应关系谈谈它们之间的转换规则。五、综合设计题(共 7 个小题，每小题 5 分，计 35 分) 1.KMP 算法中有目标串 S=“aabcbaabbabcabaacbbbc”,模式申 T=“babababaa”, 请写出 T 的 next 函数值及 nextval 函数值。 2.针对广义表 A=(((b)),(c),d,(b),(((e,f)))),完成以下要求： (1)画出 A 的存储结构图；(2)给出 A 的长度与深度； (3)求出表头、表尾。 3.有矩阵 A 要求： (1)给出 A 的三元组表示 (2)画出 A 的十字链表表示 4.一棵二叉树有 50 个叶子结点，求该二叉树至少有多少个节点?(要求写出计算过程) 5.有一颗二叉树的中序遍历序列为 DBKFIAHEJCG,后序遍历序列为 DKIFBHLJEGCA,画出该二叉树，并给出该二叉树的先序遍历序列。 6.以数据集合(2,5,7,9,13,36)构造哈夫曼树，并计算带权路径长度。 7.有带权图 G(如下图 G),求图 G 的最小生成树。(可用普里姆算法或克鲁斯卡尔算法，要求给出生成过程)

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料