公共基础知识(数据结构)

《公共基础知识(数据结构)》由会员分享，可在线阅读，更多相关《公共基础知识(数据结构)（84页珍藏版）》请在金锄头文库上搜索。

1、1.2 基本概念一、数据与数据结构二、数据类型一、数据与数据结构所有能被输入到计算机中，且能被 计算机处理的符号的集合。数据:是计算机操作的对象的总称。是计算机处理的信息的某种特定的 符号表示形式。是数据（集合）中的一个“个体”数据元素:是数据结构中讨论的基本单位数据项：是数据结构中讨论的最小单位数据元素可以是数据项的集合例如：描述一个运动员的数据元素可以是称之为组合项年 月 日姓 名学 号班 号性别出生日期入学成绩1.3 算法和算法的衡量一、算法二、算法设计的原则三、算法效率的衡量方法和准则四、算法的存储空间需求算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要

2、特性：1有穷性 2确定性 3可行性4有输入 5有输出一、算法二、算法设计的原则设计算法时，通常应考虑达到以下目标：1正确性2. 可读性3健壮性4高效率与低存储量需求1正确性首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解可以有以下四个层次：a程序中不含语法错误；b程序对于几组输入数据能够得出 满足要求的结果；c程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足 要求的结果；通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。d程序对于一切合法的输入数据都能得出满足要求的结果；2. 可读性算法主要是为了人的阅读与交流，其次才是为计算机

3、执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。3健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。4高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。三、算法效率的衡量方法和准则通常有两种衡量算法效率的方法:事后统计法事前分析估算法缺点：1必须执行程序2其它因素掩盖算法本质和算法执行时间相关的因素：1算法选用的策略2问题的规模3编写程

4、序的语言4编译程序产生的机器代码的质量5计算机执行指令的速度一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：T (n) = O(f(n)称T (n) 为算法的(渐近)时间复杂度。如何估算算法的时间复杂度？常见的时间复杂度：O(1), O(log2n), O(n), O(nlog2n), O(n2), O(n3), O(2n)从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。

5、语句的频度：在一个算法中该语句重复 执行的次数。四、算法的存储空间需求算法的空间复杂度定义为:表示随着问题规模 n 的增大，算法运行所需存储量的增长率 与 g(n) 的增长率相同。S(n) = O(g(n)算法的存储量包括:2输入数据所占空间1程序本身所占空间3辅助变量所占空间若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。第三章 栈和队列3.1 栈的类型定义3.2 栈的应用举例3.3 队列的类型定义3.4 队列类型的实现例1：

6、家里吃饭的碗，通常在洗干净 后一个一个地落在一起存放，在使用 时，若一个一个地拿，一定最先拿走 最上面的那只碗，而最后拿出最下面 的那只碗。例2：在建筑工地上，使用的砖块从 底往上一层一层地码放，在使用时， 将从最上面一层一层地拿取。3.1 栈的类型定义栈是一种特殊的线性表。其特殊性在 于限定插入和删除数据元素的操作只能在 线性表的一端(称为表尾)进行。a1, a2, a3, ., an 插入和删除 端进行插入和删除的一端是浮动端，通 常被称为栈顶，并用一个“栈顶指针”指 示；另一端是固定端，通常被称为栈底。a1栈顶栈底an进栈出栈. . .an-1a2栈中元素按 a1 ,a2 , ,an 的

7、次序进栈，退栈的第一个 元素应为栈顶元素。栈的修改时按后进后进 先出先出的原则进行的，栈 成为后进先出后进先出的线性表 。定义: 只允许在表的一端进行插入，而在另一端删除元素的线性表。 a1 ，a2， a3，an出队列入队列队 头队 尾3.4 队列的类型定义在队列中，允许插入的一端叫队尾（rear）， 允许删除的一端称为队头(front)。 特点：先进先出 (FIFO)6.1 树的定义和基本术语树的定义树是由n(n0)个结点组成的有限集合T， 非空树满足：1) 有一个称之为根(root)的结点。2) 根以外的其余结点被分成m(0mn，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；

8、 (3) 若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。 182345679 10典型考题分析 【例1-1】问题处理方案的正确而完整的 描述称为 。（2005年4月） 答案 算法 【例1-2】算法复杂度主要包括时间复杂 度和 复杂度。（2005年9月） 答案 空间 【例1-3】算法的时间复杂度是指 _。 A）执行算法程序所需要的时间 B）算法程序的长度 C）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数 答案 C 【例1-4】算法的空间复杂度是指 _。 A）算法程序的长度B）算法程序中的指令条数 C）算法程序所占的存储空间 D）算法执行过程中所

9、需要的存储空间 答案 D 【例1-5】下列叙述中正确的是 。（ 2006年9月）A）一个算法的空间复杂度大，则其时间复杂度也必 定大 B）一个算法的空间复杂度大，则其时间复杂度必定 小 C）一个算法的时间复杂度大，则其空间可复杂度必 定小 D）上述三种说法都不对 答案 D 【例1-6】下列叙述中正确的是 。（ 2005年9月） A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结 构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构 ，且各种存储结构不影响数据处理的效率 D）一个逻辑数据结构可以有多种存储结构 ，且各种存储结构影响数据处理的效率 答案 D 【例1-

10、7】数据结构分为逻辑结构和存储 结构，循环队列属于 结构。（2005 年9月） 答案 逻辑 【例1-8】数据结构分为线性结构和非线 性结构，带链的队列属于 。（2006 年9月） 答案 线性结构 【例1-9】下列叙述中正确的是_。 （2006年4月） A）线性链表是线性表的链式存储结构B）栈与队列是非线性结构 C）双向链表是非线性结构 D）只有根结点的二叉树是线性结构 答案 A 【例1-10】某线性表采用顺序存储结构 ，每个元素占4个存储单元，首地址为 200，则第12个元素的存储地址为 。 A）248 B）247 C）246 D）244 答案 D 【例1-11】在长度为n的顺序表的第i（ 1

11、in+1）个位置上插入一个元素，元 素的移动次数为 。 A）n-i+1 B）n-i C）i D）i-1 答案 A 【例1-12】在一个长度为n的顺序表中， 删除第i（1in）个元素时，需要移动 的元素个数为 。 A）n-i+1 B）n-i C）i D）i-1 答案 B 【例1-13】以下描述的中，不是线性表 的顺序存储结构的特征的是 。 A）不便于插入和删除 B）需要连续的存储空间 C）可随机访问 D）需另外开辟空间来保存元素之间的关系 答案 D 【例1-14】下列关于栈的描述中错误的 是_。（2005年4月） A）栈是先进后出的线性表 B）栈只能顺序存储 C）栈具有记忆作用D）对栈的插入与删

12、除操作中，不需要改变 栈底指针 答案 B 【例1-15】栈和队列的共同点是_ 。 A）都是先进先出 B）都是先进后出 C）只允许在端点处插入和删除元素 D）没有共同点 答案 C 【例1-16】栈的输入序列为1，2，3， ，n-1，n，输出序列的第1个元素为n， 则第个输出元素为_。 A）n-i+1 B）n-1 C）i D）哪个元素无所谓 答案 A 【例1-17】一个队列的入队序列是1、2 、3、4，则队列的输出序列是 。 A）4、3、2、1 B）1、2、3、4 C）1、4、3、2 D）3、2、4、1 答案 B 【例1-18】队列是限定只能在表的一端 进行插入和在另一端进行删除操作的线 性表。允

13、许插入的一端称作_。 答案 队尾 【例1-19】下列对于线性链表的描述中 正确的是 。（2005年4月）A）存储空间不一定是连续，且各元素的存储顺序是任意的 B）存储空间不一定是连续，且前件元素一定存储在后件元素 的前面 C）存储空间必须连续，且各前件元素一定存储在后件元素的 前面 D）存储空间必须连续，且各元素的存储顺序是任意的 答案 A 【例1-20】下列叙述中，错误的是 。 A）线性表是由n个数据元素组成的一个有限 序列 B）线性表是一种线性结构。 C）线性表的所有结点有且只有一个前件和 一个后件 D）线性表可以是空表。 答案 C 【例1-21】下列描述的不是链表的优点 是_。 A）逻辑

14、上相邻的结点物理上不必邻接B）插入、删除运算操作方便，不必移动结 点 C）所需存储空间比线性表节省D）无需事先估计存储空间的大小 答案 C 【例1-22】某线性表最常用的运算是插 入和删除，插入运算是指在表尾插入一 个新元素。删除运算是指删除表头第一 个元素，那么采用 存储方式最节省 运算时间。 A）仅有尾指针的单向循环链表B）仅有头指针的单向循环链表 C）单向链表 D）顺序存储 答案 A 【例1-23】一棵二叉树第六层（根结点 为第一层）的结点数最多为 个。（ 2005年9月） 答案 32 【例1-24】深度为5的二叉树至多有 _个结点。 A）16 B）32 C）31 D）10 答案 C 【

15、例1-25】设树T的度为4，其中度为1 ，2，3，4的结点个数分别为4，2，1， 1。则T中的叶子结点为_。 A）8 B）7 C）6 D）5 答案 A 【例1-26】某二叉树中度为2的结点有18 个，则该二叉树中有 个叶子结点。 （2005年4月） 答案 19 【例1-27】具有88个结点的二叉树，其 深度至少为_。 答案 7 【例1-28】在深度为7的满二叉树中，叶 子结点的个数为（2006年4月） A）32 B）31 C）64 D）63 答案 C 【例1-29】设一棵完全二叉树共有700个结点 ，则在该二叉树中有_个叶子结点。 答案 350 【例1-30】对如图1-30所示的二叉树， 进行后序遍历的结果为 。（2006年4 月） A）ABCDEF B）DBEAFC C）ABDECF D）DEBFCA 答案 D 【例1-31】假设一棵二叉树的后序遍历 序列为DGJHEBIFCA，中序遍历序列为 DBGEHJACIF，则其前序遍历序列为