2023年大连交通大学计算机科学与技术考研初试805考试大纲

考试大纲的内容一般包括当年全国研究生入学考试相应科目的考试范围、考试要求、考试形式、试卷结构等信息，对考生备考至关重要。希赛网整理了2023年大连交通大学计算机科学与技术（081200）考研805数据结构考试大纲信息，希望对考生备考有所帮助。

相关阅读推荐>>>2021-2022年全国考研复试线丨2023年全国考试科目汇总丨2023年全国研究方向汇总

（注：以下信息来自学院官网，仅供参考，具体内容以院校发布为准）

805 数据结构一初试考试大纲

科目代码： 805

科目名称：数据结构

适用专业：计算机科学与技术

考试时间：3小时

考试方式：笔试

总　　分：150分

考试范围：

一、数据结构绪论

理解数据结构基本术语;掌握数据结构的定义及研究内容;掌握逻辑结构分类及表示、常用存储结构;掌握算法的定义、算法的特性和定量评价标准。

二、线性表

理解线性表的概念及运算的定义;掌握线性表的顺序存储和链接存储方法及常用运算在两种存储结构上的实现算法;能够根据实际问题的需求来决定采用何种存储结构并给出具体的算法。

三、栈和队列

理解栈和队列的概念及运算特点;掌握栈和队列的存储以及运算的实现;能够根据实际问题的需求来决定采用栈和队列哪种存储结构并给出算法。

四、多维数组和广义表

理解数组和广义表的定义、特点及存储结构;掌握各种压缩存储方法;掌握广义表的运算。

五、树

理解树和二叉树的概念;掌握二叉树的性质、二叉链表存储结构、二叉树的遍历运算;掌握哈夫曼树的构建、编码、译码原理;掌握树和森林与二叉树的转换方法;能够针对实际问题利用树存储结构设计算法并给出具体实现。

六、图

理解图的基本概念;掌握图的邻接矩阵存储和邻接表存储的原理及特点;掌握图的深度优先遍历和广度优先遍历原理及对应生成树;理解求最小生成树、拓扑排序、关键路径和最短路径的算法原理;能够根据图的基本原理解决一些应用问题，如：判定图的连通性、判定是否有环等。

七、排序

理解排序的基本概念及常用的排序算法;掌握插入排序、快速排序、选择排序、归并排序、基数排序的基本思想及性能评价;可以利用各种排序算法解决实际问题。

八、查找

理解查找的概念;掌握顺序查找、索引查找方法的思想，对数据元素和存储结构的要求;掌握二叉排序树的定义及构造方法、常用运算在其上的实现;掌握散列表的定义、解决散列表冲突的方法及散列表创建的方法、查找散列表的方法;掌握各种查找算法平均查找长度的计算;可以利用各种查找算法解决实际问题。

样 题：

一、单项选择题(本大题共10小题，每小题2分，共20分)

1、在下列的叙述中，正确的是()

A.数据的逻辑结构是指数据的各数据项之间的逻辑关系。

B.数据的物理结构是指数据在计算机内的实际存储形式。

C.在顺序存储结构中，数据元素之间的关系是显示体现的。

D.链接存储结构是通过结点的存储位置相邻来体现数据元素之间的关系。

2、完成在双循环链表结点*p之后插入新结点*s的操作是()

A. 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，元素入栈的过程中允许出栈，则下列序列中，是栈的合法输出序列的是()

A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 2 1 5 D. 3 5 2 4 1

4、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当入队一个元素，再出队两个元素后，rear和front的值分别为()

A. 1和 5 B. 2和4 C. 4和2 D. 5和1

5、树最适合用来表示()

A.有序数据元素 B.无序数据元素

C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据

6、n个顶点的有向全图中有向边的数目最多为()

A. n-1 B. n C. n(n-1)/2 D. n(n-1)

7、在下面的排序方法中，平均时间复杂度为O(n2)且是不稳定的排序方法为()

A. 快速排序 B. 直接插入排序 C. 直接选择排序 D. 起泡排序

8、若结点的存储地址与其关键字之间存在某种函数关系，则称这种存储结构为()

A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构

9、将长度为m的单循环链表链接到长度为n的单循环链表之后，算法的时间复杂度最好可为()

A. O(n) B. O(1) C.O(m) D.O(m+n)

10、下面程序段的时间复杂度为()

sum=1;

for (i=0;sum1)

sum+=1;

A. O(n) B. O(1) C.O(01/2) D.O(n2)

二、填空题(本大题共10个空，每空2分，共20分)

1、设有一个10阶的对称矩阵A，以行优先顺序存储下三角元素，其中a00为第一元素，其存储地址为1，每个元素占一个字节，则a76的地址为 ;若a11为第一元素，那么a76的地址为 。

2、二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是 。

3、广义表((a,b),(c,d), e)的表尾是 。

4、 设无向图采用邻接矩阵存储，则存储空间的大小只与图中 的个数有关。

5、快速排序、堆排序和归并排序的平均时间复杂度都是 ，但其中稳定的排序方法只有 。

6、 在动态查找表中， 既拥有类似折半查找的特性，又采用了链表作存储结构。

7、 顺序表和链表中能实现随机存取的是 ，插入、删除操作效率高的是 。

三、简答题(本大题共6小题，共80分)

1、(15分)一棵二叉树的中序、后序遍历序列分别为： G L D H B E I A C J F K和L G H D I E B J K F C A，请回答：

(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={< v2,v1>,< v2,v3>,< v4,v1>,< 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版

数据来源：大连交通大学2023硕士研究生招生初试大纲