2009年硕士研究生入学考试初试考试大纲.docx

2023年硕士研究生招生考试初试考试大纲科目代码：805科目名称：数据结构适用专业：计算机科学与技术考试时间：3小时考试方式：笔试总分：150分考试范围：一、数据结构绪论理解数据结构基本术语；掌握数据结构的定义及研究内容；掌握逻辑结构分类及表示、常用存储结构；掌握算法的定义、算法的特性和定量评价标准。二、线性表理解线性表的概念及运算的定义；掌握线性表的顺序存储和链接存储方法及常用运算在两种存储结构上的实现算法；能够根据实际问题的需求来决定采用何种存储结构并给出具体的算法。三、栈和队列理解栈和队列的概念及运算特点；掌握栈和队列的存储以及运算的实现；能够根据实际问题的需求来决定采用栈和队列哪种存储结构并给出算法。四、多维数组和广义表理解数组和广义表的定义、特点及存储结构；掌握各种压缩存储方法；掌握广义表的运算。五、树理解树和二叉树的概念；掌握二叉树的性质、二叉链表存储结构、二叉树的遍历运算；掌握哈夫曼树的构建、编码、译码原理；掌握树和森林与二叉树的转换方法；能够针对实际问题利用树存储结构设计算法并给出具体实现。六、图理解图的基本概念；掌握图的邻接矩阵存储和邻接表存储的原理及特点；掌握图的深度优先遍历和广度优先遍历原理及对应生成树；理解求最小生成树、拓扑排序、关键路径和最短路径的算法原理；能够根据图的基本原理解决一些应用问题，如：判定图的连通性、判定是否有环等。七、排序理解排序的基本概念及常用的排序算法；掌握插入排序、快速排序、选择排序、归并排序、基数排序的基本思想及性能评价；可以利用各种排序算法解决实际问题。八、查找理解查找的概念；掌握顺序查找、索引查找方法的思想，对数据元素和存储结构的要求；掌握二叉排序树的定义及构造方法、常用运算在其上的实现；掌握散列表的定义、解决散列表冲突的方法及散列表创建的方法、查找散列表的方法;掌握各种查找算法平均查找长度的计算；可以利用各种查找算法解决实际问题。样题：一、单项选择题（本大题共10小题，每小题2分，共20分）1、在下列的叙述中，正确的是OA.数据的逻辑结构是指数据的各数据项之间的逻辑关系。B.数据的物理结构是指数据在计算机内的实际存储形式。C.在顺序存储结构中，数据元素之间的关系是显示体现的。D.链接存储结构是通过结点的存储位置相邻来体现数据元素之间的关系。2、完成在双循环链表结点*p之后插入新结点*s的操作是OA. p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B. p->next->prior=s;p->next=s;s->prior=p;s->next=p->next;C. s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;D. s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;3、设一个栈的输入序列依次是1,2,3,4,5,元素入栈的过程中允许出栈，则下列序列中，是栈的合法输出序列的是OA.51234B.45132C.43215D.352414、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3,当入队一个元素，再出队两个元素后，rear和front的值分别为（）A.1和5B.2和4C.4和2D.5和15、树最适合用来表示（）A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6、n个顶点的有向全图中有向边的数目最多为OA.n-lB.nC.n(n-l)2D.n(n-l)7、在下面的排序方法中，平均时间复杂度为0(/)且是不稳定的排序方法为()A.快速排序B.直接插入排序C.直接选择排序D.起泡排序8、若结点的存储地址与其关键字之间存在某种函数关系，则称这种存储结构为OA.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构9、将长度为m的单循环链表链接到长度为n的单循环链表之后，算法的时间复杂度最好可为OA.0(n)B.0(1)C.0(m)D.0(m+n)10、下面程序段的时间复杂度为Osum=l；for(i=0;sum<n;i+)/(n>l)sum+=l;A.0(n)B.0(1)C.0(0z2)D.0(n2)二、填空题(本大题共10个空，每空2分，共20分)1、设有一个10阶的对称矩阵A,以行优先顺序存储下三角元素，其中为第一元素，其存储地址为L每个元素占一个字节，则利的地址为；若M为第一元素，那么a76的地址为O2、二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是O3、广义表(a,b),(c,d),e)的表尾是。4、设无向图采用邻接矩阵存储，则存储空间的大小只与图中的个数有关。5、快速排序、堆排序和归并排序的平均时间复杂度都是,但其中稳定的排序方法只有O6、在动态查找表中，既拥有类似折半查找的特性，又采用了链表作存储结构。7、顺序表和链表中能实现随机存取的是,插入、删除操作效率高的是O三、简答题(本大题共6小题，共80分)1、（15分）一棵二叉树的中序、后序遍历序列分别为：GldhbeiacjFK和LGHDlEBJKFCA,请回答：（1）画出二叉树逻辑结构的图示。（2）画出此二叉树的二叉链表存储结构的图示并给出C语言描述。2、（10分）假设用于通信的电文由字符集a,b,c,d,e,f,g,h中的字母构成，这8个字母在电文中出现的概率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10,试为这8个字母进行哈夫曼编码。请回答：（1）画出哈夫曼树（按根点权值左小右大的原则）。（2）写出依此哈夫曼树对各个字母的哈夫曼编码。（3）求出此哈夫曼树的带权路径长度WPL。3、（15分）设一个有向图为G=（V,E）,其中V=v1,v2,v3,v4,E=<v,v>,<v2,v3>,<V4,V>,<V1,V4>,<V4,V2>）,请回答下列各问：（1）画出该有向图，求出每个顶点的入度和出度。（2）圆出该图的邻接表存储结构图不。（3）对（2）中的邻接表，给出从顶点V2出发的DFS序列和DFS生成树。（4）对（2）中的邻接表，给出从顶点V2出发的BFS序列和BFS生成树。4、（10分）给出下列图的拓扑排序序列，并说明此图是否为有环图，依据是什么。5、（15分）设待排序文件各个记录的排序码序列为：19、23、2、67、39、91、43、25,进行堆排序，请回答：（1）画出初始建成的大根堆对应的完全二叉树。（2）写出初始大根堆序列。（3）画出第一趟堆排序后对应的完全二叉树。6、（15分）设关键字序列为（71,12,88,53,11,25,65,27,16）,散列函数为H（key）=key%7,采用链地址法解决冲突。请回答：（1）画出散列表示意图（用头插法向单链表中插入结点）。（2）查找关键字32（失败）时，需要依次与哪些关键字比较。（3）求等概率下查找成功的平均查找长度ASL四、算法设计（本大题共2小题，每小题15分，共30分）1、通常称正读和反读都相同的字符序列为“回文”，例如，“abcdeedcba”、“abcdcba”是回文。若字符序列存储在一个单链表中，编写算法判断此字符序列是否为回文。（提示：将一半字符先依次进栈）2、以二叉链表为存储结构，设计一个求二叉树高度的算法。参考书目1.霍利、董靓瑜等.数据结构与算法（C语言版）.清华大学出版社.2022年出版.第1版