|
|
《数据结构》在线考试考前辅导资料
一、考试复习教材
《数据结构（C语言版）》（严蔚敏，清华大学出版社）
二、考试题型及分值介绍
（一）题型概况
考试时间为90分钟，满分为100分，试题共分五个部分：
1、单项选择题（10题，每题4分，共40分）
2、判断题（5题，每题2分，共10分）
3、综合题（1题，每题20分，共20分）
4、简答题（2题，每题10分，共20分）
5、名词解释题（2题，每题5分，共10分）
（二）注意事项
概念题请结合多结合教材；
试卷试题整体难度中等；
请各位考生必须认真复习、精心准备。
以下样题及分析请务必仔细阅读
三、备考重点
（一）绪论
本章重点：
1、计算机算法必须具备输入、输出、可行性、确定性、有穷性５个特性。
2、算法分析的两个主要方面是空间复杂度和时间复杂度。
3、数据元素是数据的基本单位。
4、数据项是数据的最小单位。
5、数据结构是带结构的数据元素的集合。
6、数据的存储结构包括顺序、链接、散列和索引四种基本类型。
更多详细内容可参考复习提纲：
（二）线性表
本章重点：
1. 线性表的相关基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念。
2. 线性表的结构特点，主要是指：除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。
3. 静态链表与顺序表的相似及不同之处。
4. 线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。在链表的小题型中，经常考到一些诸如：判表空的题。在不同的链表中，其判表空的方式是不一样的，请大家注意。
5. 线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储结构的各自好处。
更多详细内容详见下图提纲：
（三）栈和队列
本章重点：
1. 栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。
2. 递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib数列问题，Hanoi问题，背包问题，二叉树的递归和非递归遍历问题等。
3. 栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解。
4. 循环队列中判队空、队满条件，循环队列中入队与出队算法。
更多详细内容可见下图提纲：
（四）串
本章重点：
1. 串的基本概念，串与线性表的关系（串是其元素均为字符型数据的特殊线性表），空串与空格串的区别，串相等的条件。
2. 串的基本操作，以及这些基本函数的使用，包括：取子串，串连接，串替换，求串长等等。运用串的基本操作去完成特定的算法是很多学校在基本操作上的考查重点。
3. 顺序串与链串及块链串的区别和联系，实现方式。
4. KMP算法思想。KMP中next数组以及nextval数组的求法。明确传统模式匹配算法的不足，明确next数组需要改进之外。其中，理解算法是核心，会求数组是得分点。不用我多说，这一节内容是本章的重中之重。可能进行的考查方式是：求next和nextval数组值，根据求得的next或nextval数组值给出运用KMP算法进行匹配的匹配过程。
（五）数组和广义表
本章重点：
1. 多维数组中某数组元素的position求解。一般是给出数组元素的首元素地址和每个元素占用的地址空间并组给出多维数组的维数，然后要求你求出该数组中的某个元素所在的位置。
2. 明确按行存储和按列存储的区别和联系，并能够按照这两种不同的存储方式求解1中类型的题。
3. 将特殊矩阵中的元素按相应的换算方式存入数组中，包括对称矩阵，三角矩阵，具有某种特点的稀疏矩阵等。熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的二元组，十字链表存储。
4. 广义表的概念，特别应该明确表头与表尾的定义。比如给出对某个广义表L若干个求了若干次的取头和取尾操作后的串值，要求求出原广义表L。大家要留意。
5. 与广义表有关的递归算法。由于广义表的定义就是递归的，所以，与广义表有关的算法也常是递归形式的。比如：求表深度，复制广义表等。这种题目，可以根据不同角度广义表的表现形式运用两种不同的方式解答：一是把一个广义表看作是表头和表尾两部分，分别对表头和表尾进行操作；二是把一个广义表看作是若干个子表，分别对每个子表进行操作。
（六）树和二叉树
本章重点：
1. 二叉树的概念、性质和存储结构、二叉树的顺序存储和二叉链表存储的各自优缺点及适用场合。
2. 二叉树的遍历算法：先序遍历，中序遍历，后序遍历
3.熟练掌握二叉树的递归和非递归遍历算法。
4. 最优二叉树（哈夫曼树）：比如一般是给你一组数据，要求你建立基于这组数据的最优二叉树，并求出其最小权值之和。
5.二叉搜索树(二叉排序树)：熟练掌握二叉搜索树的构造,以及节点的删除操作。
6. 树与森林：树与森林之间的转换
（七）图
本章重点：
1. 考查有关图的基本概念：无向图，有向图，入度，出度，完全图，生成子图，路径长度，回路，（强）连通图，（强）连通分量等概念。
2. 考查图的几种存储形式：图的存储形式包括：邻接矩阵，（逆）邻接表，十字链表及邻接多重表。
3. 考查图的两种遍历算法：深度遍历和广度遍历深度遍历和广度遍历是图的两种基本的遍历算法。
4. 生成树、最小生成树的概念以及最小生成树的构造PRIM算法和KRUSKAL算法。
5. 关键路径问题：理解关键路径的关键有三个方面：一是何谓关键路径，二是最早时间是什么意思、如何求，三是最晚时间是什么意思、如何求。
6. 最短路径问题：最短路径问题分为两种：一是求从某一点出发到其余各点的最短路径；二是求图中每一对顶点之间的最短路径。着重明白DIJSKTRA算法和FLOYD算法。
（八）查找和排序
本章重点：
1. 线性表上的查找：主要分为三种线性结构：顺序表，有序顺序表，索引顺序表。着重理解二分查找算法。
2. 基本哈希表的查找算法(应掌握哈希表的用法)：基于哈希表的考查点有：哈希函数的设计，冲突解决方法的选择及冲突处理过程的描述。
3.插入、(冒泡),选择、希尔、归并、快速等五种内部排序算法的时空复杂度。
复习题
一、单选题 ( 每题4分 共10题 总分值40分 )
1、线性表采用链接存储时，其地址（ ）。（4分）
A 必须是连续的 B 部分地址必须是连续的
C 一定是不连续的 D 连续与否均可以
【解答】 D
【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。
2、G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。（4分）
A 6 B 7 C 8 D 9
【解答】D
【分析】n个顶点的无向图中，边数e≤n(n-1)/2，将e=28代入，有n≥8，现已知无向图非连通，则n=9。
3、设有5000个元素，希望用最快的速度挑选出前10个最大的，采用（ ）方法最好。
A快速排序 B堆排序 C希尔排序 D 归并排序
【解答】B
【分析】堆排序不必将整个序列排序即可确定前若干个最大（或最小）元素。
4、快速排序在（ ）情况下最不利于发挥其长处。
A 待排序的数据量太大 B 待排序的数据中含有多个相同值
C 待排序的数据已基本有序 D 待排序的数据数量为奇数
【解答】C
【分析】快速排序等改进的排序方法均适用于待排序数据量较大的情况，各种排序方法对待排序的数据中是否含有多个相同值，待排序的数据数量为奇数或偶数都没有影响。
5、一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（ ）。(4分)
A 54321 B 45321 C 43512 D 12345
【解答】C
【分析】此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序（指的是元素的序号）的两个元素。
6、设计一个判别表达式中左右括号是否配对的算法，采用（ ）数据结构最佳。（4分）
A 顺序表 B 栈 C 队列 D 链表
【解答】B
【分析】每个右括号与它前面的最后一个没有匹配的左括号配对，因此具有后进先出性。
7、下面的说法中，不正确的是（ ）（4分）
A 数组是一种线性结构 B 数组是一种定长的线性结构
C 除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等
D 数组的基本操作有存取、修改、检索和排序等，没有插入与删除操
【解答】C
【分析】数组属于广义线性表，数组被创建以后，其维数和每维中的元素个数是确定的，所以，数组通常没有插入和删除操作。 (4分)
8、下面的说法中，不正确的是（ ）
A 对称矩阵只须存放包括主对角线元素在内的下（或上）三角的元素即可。
B 对角矩阵只须存放非零元素即可。
C 稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。
D 稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储
【解答】D
【分析】稀疏矩阵中大量值为零的元素分布没有规律，因此采用三元组表存储。如果零元素的分布有规律，就没有必要存储非零元素的行号和列号，而需要按其压缩规律找出相应的映象函数。
9、 下任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ ）。
A 肯定不发生改变 B 肯定发生改变 C 不能确定 D 有时发生变化
【解答】A
【分析】三种遍历次序均是先左子树后右子树。
10、含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（ ）。
A 1 B n/2 C n-1 D n
【解答】C
【分析】若超过n-1，则路径中必存在重复的顶点。
二、判断 ( 每题2分 共5题 总分值10分 )
11、线性表的逻辑顺序和存储顺序总是一致的。（  ） (2分)
【解答】错，顺序表的逻辑顺序和存储顺序一致，链表的逻辑顺序和存储顺序不一定一致。
12、栈可以作为实现过程调用的一种数据结构。
【解答】对。只要操作满足后进先出性，都可以采用栈作为辅助数据结构。 (2分)
13、使用三元组表存储稀疏矩阵的元素，有时并不能节省存储空间。(2分)
【解答】对。因为三元组表除了存储非零元素值外，还需要存储其行号和列号。
14、二叉树是度为2的树。(2分)
【解答】错。二叉树和树是两种不同的树结构，例如，左斜树是一棵二叉树，但它的度为1。
15、堆排序所需的时间与待排序的记录个数无关。(2分)
【解答】错。堆排序最好、最坏及平均时间均为Ο(nlog2n)，是待排序的记录个数n的函数。一般来说，待排序的记录个数越多，排序所消耗的时间也就越多。
三、综合题 ( 每题20分 共1题 总分值20分 )
16、已知关键字的初始序列为（30，22,65,24,73,32），请写出利用直接插入法对其进行升序排序的每一趟得到的排序结果 (20分)
【解答】
初始序列：30、22、65、24、73、32
第一趟排序：22、30、65、24、73、32 (将22插入到{30})
第二趟：22、30、65、24、73、32 (将65插入到{22、30})
第三趟：22、24、30、65、73、32 (将24插入到{22、30、65})以此类推。
第四趟：22、24、30、65、73、32。
第五趟：22、24、30、32、65、73。
所以，最终的排序结果为：22、24、30、32、65、73。
四、简答题 ( 每题10分 共2题 总分值20分 )
17、将下图所示的森林转换为一颗二叉树，给出转换得出的二叉树的树形图示(10分)
【解答】
18、 什么是算法？一般来说设计一个“好”算法应当考虑达到哪些目标？ (10分)
【解答】
 算法：由基本运算及规定的运算顺序所构成的完整的解题步骤；
设计目标（如何评价）：正确性、可读性、健壮性、高效率与低存储要求。
一个好的算法一般从以下四个方面评价：
（1）正确性：算法应当正确地解决求解问题。
（2）效率与低存储量需求。
（3）可读性：算法应当具有良好的可读性，以助于人的理解。
（4）健壮性：当输入非法数据时，算法也能适当地做出反应或进行处理。
五、名词解释 ( 每题5分 共2题 总分值10分 )
19、文件的物理组织方式常见的有哪几种？ (5分)
【解答】
数据的物理组织方式也叫数据的的物理结构，是数据元素在计算机中的表示和关系的表示，包括顺序存储、链接存储、索引存储、散列存储。
20、什么是关键路径？ (5分)
【解答】
在AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。完成整个工期的最短时间就是关键路径长度所代表的时间，关键路径上的活动称为关键活动。既是最长路径，又是完成的最短时间。
|
|
IP卡
狗仔卡
发表于 2019-9-9 19:59:49
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
发表于 2019-9-9 20:03:01
客服一
