严蔚敏《数据结构》考研C语言版考研笔记与考研真题.pdf

严蔚敏数据结构考研 C 语言版考研笔记与考研真题 第一部分 考研真题精选 一、单项选择题 1 若元素 a，b，c，d，e，f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。计算机统考（408）2010 年研【答案】D 查看答案【解析】4 个选项所给序列的进、出栈操作序列分别为：选项 A：Push，Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Pop 选项 B：Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Push，Pop 选项 C：Push，Push，Pop，Push，Pop，Pop，Push，Push，Pop，Push，Pop，Pop 选项 D：Push，Pop，Push，Push，Push，Push，Push，Pop，Pop，Pop，Pop，Pop 按照题目要求，不允许连续三次进行退栈操作，所以选项 D 所给序列为不可能得到的出栈顺序。2 若一棵二叉树的前序遍历序列为 a，e，b，d，c，后序遍历序列为 b，c，d，e，a，则根结点的孩子结点（）。计算机统考（408）2012 年研 A只有 e B有 e、b C有 e、c D无法确定 【答案】A 查看答案【解析】由题目可知，若一棵二叉树的前序遍历序列为 a，e，b，d，c，后序遍历序列为 b，c，d，e，a，其中 a 为这棵二叉树的根结点，接下来，在前序遍历的第二个结点为 e，而后序遍历的倒数第二个结点为 e，说明 a 的孩子结点只有 e。3 循环队列放在一维数组 A0.M1中，end1 指向队头元素，end2 指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳 M1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（）。计算机统考（408）2014 年研 A队空：end1end2；队满：end1（end21）mod M B队空：end1end2；队满：end2（end11）mod（M1）C队空：end2（end11）mod M；队满：end1（end21）mod M D 队空：end1（end21）mod M；队满：end2（end11）mod（M1）【答案】A 查看答案【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加 1 后是否等于头指针，若相等，则队满。而队空的条件还是首尾指针是否相等。4 已知关键字序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后的小根堆是（）。计算机统考（408）2009 年研 A3，5，12，8，28，20，15，22，19 B3，5，12，19，20，15，22，8，28 C3，8，12，5，20，15，22，28，19 D3，12，5，8，28，20，15，22，19 【答案】A 查看答案【解析】在堆中插入一个元素后，将不再满足堆的性质。为了使其成为新堆，需要重新调整剩余元素的位置。具体过程如图（1）（5）所示，（1）为原堆，（2）为插入 3 后，（3）、（4）为调整过程，（5）为调整后的小根堆。5 下列选项中，不能构成折半查找中关键字比较序列的是（）。计算机统考（408）2015 年研 A500，200，450，180 B500，450，200，180 C180，500，200，450 D180，200，500，450 【答案】A 查看答案【解析】折半查找也称二分查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。折半查找的过程是：先确定待查找记录所在的范围，然后逐步缩小范围直到找到或找不到该记录为止。折半查找的关键字序列满足：对每一个关键字，其后面的所有关键字序列或者都小于等于该关键字或者都大于等于该关键字。A 项错误，第三次比较的关键字为 450，说明待查关键字位于 200450 间，所以第四次比较时不会遇到关键字 180。6 已知字符串 S 为“abaabaabacacaabaabcc”，模式串 t 为“abaabc”，采用KMP 算法进行匹配，第一次出现“失配”（si!ti）时，ij5，则下次开始匹配时，i 和 j 的值分别是（）。计算机统考（408）2015 年研 Ai1，j0 Bi5，j0 Ci5，j2 Di6，j2【答案】C 查看答案【解析】模式匹配（KMP）算法对普通的暴力匹配的改进在于：每当匹配过程中匹配失败时，主串（本题为 S）的指针（i）不需要回溯，而是利用已经得到的“部分匹配”的结果将模式串（t）向右“滑动”尽可能远的一段距离后，继续进行比较。模式串“滑动”的距离是由模式串（t）本身决定的，即 t 的子串 t0j 1中前缀串和后缀串相等的最长长度。本题中第一次失配 i5，字串为“abaab”，其相等且最长的前后缀为“ab”，一次下一个 j2。7 下列关于无向连通图特性的叙述中，正确的是（）。计算机统考（408）2009年研 所有的顶点的度之和为偶数 边数大于顶点个数减 1 至少有一个顶点的度为 1 A只有 B只有 C和 D和 【答案】A 查看答案【解析】在图中，顶点的度 TD（Vi）之和与边的数目满足关系式：其中，n 为图的总结点数，e 为总边数。因此，项正确。对于、项中的特性不是一般无向连通图的特性，可以轻松地举出反例。“至少有一个顶点的度为 1”的反例如下图（1）所示，“边数大于顶点个数减 1”的反例如下图（2）所示。8 下列叙述中，不符合 m 阶 B 树定义要求的是（）。计算机统考（408）2009年研 A根结点最多有 m 棵子树 B所有叶结点都在同一层上 C各结点内关键字均升序或降序排列 D叶结点之间通过指针链接 【答案】D 查看答案【解析】B 树就是指 B树。根据 B树的定义，m 阶 B树中每个结点最多有 m 个分支，因此，根结点最多有 m 棵子树，A 项正确；B树中所有叶结点都在最底层，位于同一层，B 项正确；结点内各关键字互不相等且有序排列，C 项正确。但是，所有叶子结点之间通过指针链接，是 B树的定义，而 B树中没有。因此，D 项是错误的。9 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。计算机统考（408）2012 年研 简单选择排序 希尔排序 快速排序 堆排 二路归并排序 A仅、B仅、C仅、D仅、【答案】A 查看答案【解析】其中简单选择排序、堆排序属于选择类排序，每一趟排序结束时将确定最大（或最小）关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。第 1 章 绪 论 1.1 复习笔记 一、什么是数据结构 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。二、基本概念和术语 1 数据 数据是对客观事物的符号表示，是计算机科学中所有能输入到计算机中并能被计算机程序处理的符号的总称。2 数据元素 数据元素是数据的基本单位。3 数据对象 数据对象是性质相同的数据元素的集合，是数据的一个子集。4 数据结构 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。（1）数据结构的基本结构 根据数据元素之间关系的不同特性，通常有下列四类基本结构：集合。数据元素属于“同一个集合”，并无其他复杂关系。线性结构。数据元素之间存在一个对一个的关系。树形结构。数据元素之间存在一个对多个的关系。图状结构或网状结构。数据元素之间存在多个对多个的关系。【注意】区分这四种基本结构可以根据元素间的对应关系。如图 1-1 所示为上述四类基本结构的关系图。图 1-1 四类基本结构的关系图（2）数据结构的形式定义 数据结构的形式定义为：Data_Structure=(D,S)其中：D 表示数据元素的有限集，S 表示 D 上关系的有限集。（3）数据结构在计算机中的表示 数据结构包括数据元素的表示和关系，在计算机中称为数据的物理结构（又称存储结构）。其中，关系有两种表示方法：顺序映象和非顺序映象。这两种表示方法对应两种存储结构：顺序存储结构和链式存储结构。a顺序映象：用相对位置来表示数据元素之间的逻辑关系。b非顺序映象：用指针表示数据元素之间的逻辑关系。5 数据类型 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。6 抽象数据类型 抽象数据类型（ADT）由一个值域和定义在该值域上的一组操作组成。【注意】抽象数据类型是对数据类型架构的一种全局体现，使我们能够更加清晰地看待某一数据类型。7 多形数据类型 多形数据类型是指其值的成分不确定的数据类型。8 数据操作的类型 基本的操作主要有：（1）插入（2）删除（3）更新（4）查找（5）排序 从操作的特性来分，所有的操作可以归结为两类：加工型操作：改变了（操作之前的）结构的值；引用型操作：即不改变结构的值，只是查询或求得结构的值。上述 5 种操作中除“查找”为引用型操作外，其余都是加工型操作。9 算法 【定义】算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。【特性】（1）有穷性（2）确定性（3）可行性（4）输入（5）输出【注意】在考试中这五个特性可能出现在选择或者填空题中（通常直接考察其名称）。三、抽象数据类型的表示与实现 四、算法和算法分析 1 算法的描述 算法需要用一种语言来描述，程序框图，程序设计语言等都能对算法进行描述。【注意】考研笔试中，如果在对应语法不确定的情况下，使用伪码通常也是可以的。2 算法设计的要求（1）正确性（2）可读性（3）健壮性（4）效率与低存储量需求 3 算法效率的度量 算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量，度量一个程序的执行时间通常有两种方法：（1）事后统计（2）事前分析估算 事先考虑消耗时间的因素 时间复杂度 时间复杂度是关于问题规模的函数，通常用 O 表示，常见时间复杂度按照数量级递增排列为：O（1）O（log2n）O（n）O（nlog2n）O（n2）O（n3）O（nk）O（2n）【注意】需能够对具体的算法进行时间复杂度的分析与计算，尤其在考研中算法时间复杂度的计算不可避免。4 算法的存储空间需求 算法的空间复杂度是对算法运行所占空间的度量。在度量时一般只考虑算法运行所需额外开销的多少，包括算法实现时定义的中间变量，数组等对存储空间的影响。原地工作：算法运行所需的额外空间相对输入数据量是常量。