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

《2019年山东烟台大学数据结构考研真题.docx》由会员分享，可在线阅读，更多相关《2019年山东烟台大学数据结构考研真题.docx（4页珍藏版）》请在优知文库上搜索。

1、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=l;kn;k+）for（j=l;jn;j+）x=x

2、+l;A.0（2n）B.0（n）C.0（n）D.O（Iogsn）6 .以下数据结构中，多型数据类型结构是（）。A.栈B.广义表C.数组D.字符串7 .顺存储设计时，存储单元的地址（）。A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续8 .串是一种特殊的线性表，其特殊形表现在（）。A.可以顺序存储B.数据元素是单个字符C.可以连接存储D.数据元素类型相同9 .以下可以用于定义一个完整的数据结构的是（）。A.数据元素B.数据对象C.数据关系ID.抽象数据类型10 .有关图中路径的定义，表述正确的是（）。A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是图中相邻顶点的序列C.

3、路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合11 .己知有向图G=（V,E）,其中V=（V1,V2,V3,V4,V5,V6,V7）,E=V1,V2）,则图G的拓扑序列是（）。A.VI,V3,V4,V6,V2,V5,v7B.VI,V3,V2,V6,V4,V5,V7C.VI,V3fV4,V5,V2,V6,v7D.Vltv2,V5,V3,V4,V6,V712 .设单链表中指针P指向结点A,若要删除A的直接后继，则所需修改指针的操作为（）。A.p-next=p-next-nextB.p=p-nextC.p=p-next-nextD.p-next=p13 .数据表A中每个元素距其最终位

4、置较近，则最省时间的排序算法是（）。A.插入排序B.堆排序C.直接选择排序D.快速排序14 .一棵二叉树的中根遍历序列为debac,后根逸历序列为dabec,则先根遍历序列为（）。A.acbcdB.cedbaC.deabcD.becab15 .在一个有向图中，所有顶点的度数之和与图的边数的比是（）。A.1:2B.1:1C.2:1D.4:l16 .含有n个结点的二叉树用二叉链表表示时，空指针域个数为（）。A.nlB.nC.n+1D.n+217 .对称矩阵ANN,A1I为首元素，将下三角（包括对角线）元素以行优先顺序存储到一维数组元素l至TN(N+1)2中，则任一下三角元素AJ6存于Tk中，下标k

5、为()。A.i*(i-l)2+jB.JG-D/2+1C.iG-i)2+lD.j(-1)/2+118 .设有数组Ai,j,数组的每个元素长度为3字节，i的值为1到8,j的值为1到10,数组从内存首地址adr开始顺序存放，当用以列为主存放时，元素A5,8的存储首地址为()。A.adr+141B.adr+180C.adr+222D.adr+22519 .链表不具有的特点是()A、插入/删除不需要移动元素B、可随机访问任一元素C、不必事先估计存储空间D、所需空间与线性长度成正比20 .己知二叉树中叶子数为40,仅有一个孩子的结点数为20,则总结点数为()。A、91B、92C、98D、99二、填空题(本

6、大题共30个空项，每个空项1分，计30分)1.数据结构是一门研究程序设计中数据的(1)_以及他们之间的和运算等的学科。2 .在数据结构中，从逻辑上可以把数据结构分为一(3)和(4)_两类。3 .数据的存储结构是一个数据结构在计算机中的(5)04 .顺序存储结构是逻辑上(6)的节点存储在(7)一中。5 .算法的五个特性是(8)、(9)、(10)、输入和输出。6 .在线性表的链式存储中，元素之间的逻辑关系是通过(11)决定的；在线性表的顺序存储中，元素之间的逻辑关系是通过_(12)决定的。7 .从数据结构定义看，栈和队列都是(13)_的线性表；栈具有_(14)_的特性。8 .栈和队列的共同特点是只

7、允许在端点处进行(15)和(16)O9 .用带头节点的单链表表示栈，则栈空的标志是(17)_10 .根据串的定义，串是含有n个字符的_(18)序列；串“howareyou!”的长度是(19)。11 .两个串相等的充分必要条件是(20)。12 .递归关系指的是一个数列的若干(21)_之间的关系；递归过程指的是(22)或(23)一调用自身的过程。13 .常常用到递归算法的三种情况是(24)、(25).(26)14 .将f=l+l2+l3+ln转化为递归函数，其递归出口是(27),递归体是(28)。15 .一维数组的逻辑结构是(29),存储结构是(30)O三、判断下列语句的正确性(对/错)(本大题共

8、15小题，每小题1分，计15分)1 .顺序存储的线性表可以实现随机存取。2 .在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。3 .插入和删除操作是数据结构中两种基本的操作，所以这两种操作在数组中也会经常使用。4,任何有向网拓扑排序的结果是唯一的。5 .任何递归算法都有递归出口。6 .在树形结构中，处于同一层上的各个节点存在兄弟关系。7 .递归算法的执行效率一般高于功能相同的非递归算法的执行效率。8 .KMP算法的最大特点是指示主串的指针不需要回溯。9 .广义表的长度不小于任一子表的长度。10 .完全二叉树中的每个节点的度或者是0或者为2。11 .哈夫曼树中权值较大的节点一般离根节点较

9、近。12。对图而言，所谓的简单路径指的是任何一个顶点在这条路径上不重第出现。13 .图的邻接矩阵表示是唯一的。14 .顺序查找既可以在顺序表上进行也可以在链表上进行，随机杳找只能在链表上进行。15 .二叉排序树主要是用来进行排序的。四、分析论述题(共6个小题，每小题5分，计30分)1 .简述数据元素、数据结构和数据类型以及三者之间的关系。2 .分析叙述线性表的两种存储结构的特点。3 .叙述图的两种主要存储结构，说明它们各自的优缺点。4 .简述顺序查找法、二分查找法和分块查找法；说明这三种查找方法对被查找的表中元素的要求；对于长度为n的表，三种查找方法在成功查找时的平均查找长度分别是多少？5 .

10、(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)求出表头、表尾。0 0 60 1 92 0 00 5 02力二03 .有矩阵AL0要求：(1)给出A的三元组表示(2)画出A的十字链表表示4 .一棵二叉树有50个叶子结点，求该二叉树至少有多少个节点？(要求写出计算过程)5 .有一颗二叉树的中序遍历序列为Dbkfiahejcg,后序遍历序列为Dkifbhljegca,画出该二叉树，并给出该二叉树的先序遍历序列。6 .以数据集合(2,5,7,9,13,36)构造哈夫曼树，并计算带权路径长度。7 .有带权图G(如下图G),求图G的最小生成树。(可用普里姆算法或克鲁斯卡尔算法，要求给出生成过程)83G