还剩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+l;A.0(2n)B.0(n)C.0(n)D.O(logsn)
6.以下数据结构中,多型数据类型结构是()A.栈B.广义表C.数组D.字符串
7.顺存储设计时,存储单元的地址()A.一定连续B.一定不连续C.不一定连续I),部分连续,部分不连续
8.串是一种特殊的线性表,其特殊形表现在()A.可以顺序存储B.数据元素是单个字符C.可以连接存储D.数据元素类型相同
9.以下可以用于定义一个完整的数据结构的是()A.数据元素B.数据对象C.数据关系ID.抽象数据类型
10.有关图中路径的定义,表述正确的是()A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是图中相邻顶点的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合
11.已知有向图G=(V,E),其中V=(V1,V2,V3,V4,V5,V6,V7),E={V1,V2),V1,V3,V1,V4,V2,V5,V3,V5,Y3,V6,V4,V6,V5,V7,V6,V7},则图G的拓扑序列是()0A.VI,V3,V4,V6,V2,V5,v7B.VI,V3,V2,V6,V4,V5,V7C.VI,V3,V4,V5,V2,V6,v7D.VI,v2,V5,V3,V4,V6,V
712.设单链表中指针p指向结点A,若要删除A的直接后继,则所需修改指针的操作为()oA.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:2B.1:1C.2:1D.4:l
16.含有n个结点的二叉树用二叉链表表示时,空指针域个数为()A.n-l B.n C.n+1D.n+
217.对称矩阵A[N]N],A[1I□为首元素,将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[l]至T[NN+l/2]中,则任一下三角元素A[J
[6]存于Tk]中,下标k为A.i*i-l/2+j B.jG-D/2+l C.iG-i/2+l D.j-l/2+l18,设有数组A[i,j],数组的每个元素长度为3字节,i的值为1到8,j的值为1到10,数组从内存首地址adr开始顺序存放,当用以列为主存放时,元素A[5,8]的存储首地址为A.adr+141B.adr+180C.adr+222D.adr+
22519.链表不具有的特点是A、插入/删除不需要移动元素B、可随机访问任一元素C、不必事先估计存储空间D、所需空间与线性长度成正比
20.已知二叉树中叶子数为40,仅有一个孩子的结点数为20,则总结点数为、91B、92C、98D、99A
二、填空题本大题共30个空项,每个空项1分,计30分
1.数据结构是一门研究程序设计中数据的1_以及他们之间的⑵和运算等的学科
2.在数据结构中,从逻辑上可以把数据结构分为_3_和4_两类
3.数据的存储结构是一个数据结构在计算机中的54,顺序存储结构是逻辑上6的节点存储在7_中5,算法的五个特性是
8、
9、
10、输入和输出
6.在线性表的链式存储中,元素之间的逻辑关系是通过11决定的;在线性表的顺序存储中,元素之间的逻辑关系是通过_12决定的
7.从数据结构定义看,栈和队列都是13_的线性表;栈具有_14_的特性
8.栈和队列的共同特点是只允许在端点处进行15和16o
9.用带头节点的单链表表示栈,则栈空的标志是17_
10.根据串的定义,串是含有n个字符的_18序列;串“how areyou!”的长度是
1911.两个串相等的充分必要条件是20o
12.递归关系指的是一个数列的若干21_之间的关系;递归过程指的是22或23_调用自身的过程
13.常常用到递归算法的三种情况是
24、
25、
2614.将f=l+l/2+l/3+……+l/n转化为递归函数,其递归出口是27,递归体是
2815.一维数组的逻辑结构是29,存储结构是30o
三、判断下列语句的正确性对/错本大题共15小题,每小题1分,计15分L顺序存储的线性表可以实现随机存取
2.在顺序栈栈满情况下,不能做进栈运算,否则会产生“上溢”
3.插入和删除操作是数据结构中两种基本的操作,所以这两种操作在数组中也会经常使用4,任何有向网拓扑排序的结果是唯一的
5.任何递归算法都有递归出口
6.在树形结构中,处于同一层上的各个节点存在兄弟关系
7.递归算法的执行效率一般高于功能相同的非递归算法的执行效率
8.KMP算法的最大特点是指示主串的指针不需要回溯
9.广义表的长度不小于任一子表的长度
10.完全二叉树中的每个节点的度或者是0或者为2o
11.哈夫曼树中权值较大的节点一般离根节点较近12o对图而言,所谓的简单路径指的是任何一个顶点在这条路径上不重复出现
13.图的邻接矩阵表示是唯一的
14.顺序查找既可以在顺序表上进行也可以在链表上进行,随机查找只能在链表上进行
15.二叉排序树主要是用来进行排序的
四、分析论述题共6个小题,每小题5分,计30分
1.简述数据元素、数据结构和数据类型以及三者之间的关系
2.分析叙述线性表的两种存储结构的特点3•叙述图的两种主要存储结构,说明它们各自的优缺点
4.简述顺序查找法、二分查找法和分块查找法;说明这三种查找方法对被查找的表中元素的要求;对于长度为n的表,三种查找方法在成功查找时的平均查找长度分别是多少?
5.1简要回答什么是内排序什么是外排序?⑵从时间复杂度和算法稳定性两个方面分析、比较以下几种排序方法直接插入排序、冒泡排序、快速排序、直接选择排序和归并排序
6.请从森林和二叉树的对应关系谈谈它们之间的转换规则
五、综合设计题共7个小题,每小题5分,计35分
1.KMP算法中有目标串S=aabcbaabbabcabaacbbbc”,模式申T=babababaa”,请写出T的next函数值及nextval函数值
2.针对广义表A=b,c,d,b,e,f,完成以下要求:⑴画出A的存储结构图;2给出A的长度与深度;3求出表头、表尾-2006-,0019~
02003.有矩阵A L005°.要求⑴给出A的三元组表示⑵画出A的十字链表表示
4.一棵二叉树有50个叶子结点,求该二叉树至少有多少个节点?要求写出计算过程
5.有一颗二叉树的中序遍历序列为DBKF1AHEJCG,后序遍历序列为DKIFBHLJEGCA,画出该二叉树,并给出该二叉树的先序遍历序列
6.以数据集合⑵5,7,9,13,36构造哈夫曼树,并计算带权路径长度
7.有带权图G如下图G,求图G的最小生成树可用普里姆算法或克鲁斯卡尔算法,要求给出生成过程酎G。
个人认证
优秀文档
获得点赞 0