二级公共基础知识(41)课件

《二级公共基础知识(41)课件》由会员分享，可在线阅读，更多相关《二级公共基础知识(41)课件（94页珍藏版）》请在金锄头文库上搜索。

1、全国计算机等级考试二级公共基础知识,约12课时,青岛工学院,学习方法,逻辑推理运算必须理解 概念性、理论性知识点要加强记忆 适当记忆一些名词 与所学的VF程序设计知识结合起来，以增加对知识的理解能力,做大量习题,青岛工学院,一、 数据结构与算法,考点提示： 1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。 3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基

2、本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。,青岛工学院,本章考点点评及考核情况,考点点评：该部分属于重点考核知识点，在此7个考点中，经常会考到的知识点是1、4、6点，特别是二叉树的遍历，基本上每年必考的内容。 分值情况：本部分内容所占分值在3-5分。,青岛工学院,1.1 算法,算法： 是指解题方案的准确而完整的描述。 算法不等于程序，也不等于计算方法；算法是解题思路，而程序是解题思路在其编译环境中的具体描述。 算法的特征： （1）可行性：在具体环境中可执行和正确与否

3、 （2）确定性：每一步必须有明确的定义 （3）有穷性：在有限步骤（时间）内执行完毕 （4）拥有足够的情报：初始数据或初始状态必须要充足且正确。,青岛工学院,算法的基本要素： 一是对数据对象的运算和操作（四类） 二是算法的控制结构（各操作之间的执行顺序）。 基本运算和操作包括： 算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构： 顺序、选择、循环。 算法设计的基本方法： 列举法、归纳法、递推、递归、减半递推技术、回溯法。,青岛工学院,算法复杂度(包括)： 算法时间复杂度和算法空间复杂度。 算法时间复杂度： 是指执行算法所需要的计算工作量（运算的执行次数）。 衡量算法时间复杂度的主要因素：

4、 一方面依赖于问题的规模，（如NN矩阵乘法运算，f(n)=O(n3)） 另一方面，某些情况下还和问题的输入数据集有关（如冒泡排序）,此时用两种方法分析： （1）平均性态：用基本运算次数的加权平均值来衡量-A(n)= （2）最坏情况复杂性：最大执行次数 -W(n)=,青岛工学院,算法空间复杂度： 是指执行算法所占用的空间，包括算法程序所占用的空间、输入的初始数据所占用的空间、算法执行过程中所需要的额外空间。 算法设计的要求： （1）正确性（2）可读性（3）健壮性 （4）效率与低存储量需求,青岛工学院,例题,算法的时间复杂度是指_。A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过

5、程中所需要的基本运算次数D. 算法程序中的指令条数 算法的空间复杂度是指_。 A. 算法程序的长度B. 算法程序中的指令条数C. 算法程序所占的存储空间D. 执行算法所需要的空间 下面叙述正确的是_。A. 算法的执行效率与数据的存储结构无关B. 算法的空间复杂度是指算法程序中指令（或语句）的条数C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止D. 以上三种描述都不对,(C),(D),(C),青岛工学院,算法一般都可以用哪几种控制结构组合而成_。A. 循环、分支、递归B. 顺序、循环、嵌套C. 循环、递归、选择D. 顺序、选择、循环 在下列选项中，哪个不是一个算法一般应该具有的基本特征_

6、。A. 确定性B. 可行性C. 无穷性D. 拥有足够的情报 算法的时间复杂度取决于_。 A. 问题的规模 B. 待处理数据的初态 C. 问题的难度 D. A和B 在计算机中，算法是指_。A. 查询方法B. 加工方法C. 解题方案的准确而完整的描述D. 排序方法,(D),(C),(D),(C),青岛工学院,1.2 数据结构的基本概念,数据结构（两个，注意区分）： 反映数据元素之间关系的表示。 数据结构研究的三个方面 ： （1）各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）各数据元素在计算机中的存储关系，即数据的存储结构（又叫物理结构）； （3）对各种数据结构进行的运算。 数据的逻辑结

7、构： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的逻辑结构是数据元素之间固有的，是与计算机硬件没有关系的结构,青岛工学院,数据逻辑结构的四种形式： 集合、线性结构、树形结构、图形结构 数据存储结构： 是指数据的逻辑结构在计算机存储空间中的存放形式，也称数据的物理结构。 数据的物理结构反映的是数据的存储方法，这受到具体的物理存储介质制约(与计算机硬件有关系)。 数据存储结构的三种形式： 顺序、链接、索引。 数据结构中的数据元素，其逻辑结构和存储结构不一定相同。,青岛工学院,按逻辑（前后件）关系的复杂程度，将数据的逻辑结构简单分为线性结构和非线性结构： 线性结构（什么

8、是线性结构？线性结构有那几个？）（线性表、线性链表、栈、队列）： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 在一个线性结构中插入或删除任何一个节点后还应该是线性结构。 非线性结构：不满足线性结构条件的数据结构。 线性结构和非线性结构都可以是空数据结构，对于空数据结构的运算是按线性结构的规则来处理的，则属于线性结构；否则属于非线性结构。,图1.5 线性结构特列,青岛工学院,例题,在数据结构中，与所使用的计算机无关的数据结构是_。A. 逻辑 B. 存储 C. 逻辑和存储 D. 物理 在数据结构中，从逻辑上可以把数据结构分成_。A. 动态结构和静态结构B. 紧凑

9、结构和非紧凑结构C. 线性结构和非线性结构D. 内部结构和外部结构 数据的存储结构是指_。A. 数据所占的存储空间量B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式D. 存储在外存中的数据,(A),(C),(B),青岛工学院,1.3 线性表及顺序存储结构,线性表（是什么？是表？是线表？）： 线性表是最常用且最简单的一种线性数据结构。简言之，一个线性表是n个数据元素的有限序列。线性表有两种存储结构（顺序存储和链式存储） 如26个英文字母的字母表 （A,B,C,D,Z）是一个线性表，表中的数据元素是单个字母字符。 数据元素的定义在不同情况下各不相同 在复杂线性表中，一个数据元

10、素可以由若干个数据项（item）组成。在这种情况下，常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）,青岛工学院,每个学生的情况为一个记录，它由姓名、学号、 性别、年龄、班级和健康状况等6个数据项组成,青岛工学院,非空线性表的结构特征： （1）有且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。,青岛工学院,线性表的顺序存储结构(典型结构是 数组存储)： 指用一组地址连续的存储单元依次存储线性表的数据元素。 线

11、性表的顺序存储结构具有以下两个基本特点： （1）线性表顺序存储结构中所有元素所占的存储空间是连续的； （2）线性表顺序存储结构中各数据元素在存储空间中是按逻辑顺序依次存放的。,ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,， ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。 可以看出，顺序存储是一种随机存取的存储结构,链式存储是一种顺序存取的存储结构。只要知道某元素地址，其他任何元素地址都可以计算出来,青岛工学院,顺序表的运算（时间复杂度）： 插入： 在平均情况下，要插入一个元素，需要移动表中一半的元素。 删除： 在平均情况下，要删除一个元素，需要移动表中一半的元

12、素。 线性表顺序存储缺点：线性表的顺序存储结构，插入和删除元素时需大量移动元素，故不便于插入和删除操作,青岛工学院,例题,对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为_。A. N+1B. NC. (N+1)/2D. N/2 顺序存储方法是把逻辑上相邻的结点存储在物理位置_的存储单元中。 用数组表示线性的优点是（ ） A便于插入和删除操作 B便于随机存储 C可以动态地分配存储空间 D不需要占用一片相邻的存储单元,(B),相邻,(B),青岛工学院,1.4 栈和队列（线性结构）,栈： 是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底

13、。 栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。,栈的基本运算： （1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素 还有初始化、置空、判断栈是否为空或满,青岛工学院,队列： 是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾（最后一个元素），front指针指向队头（第一个元素的前面）。 队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。 队列运算： （1）入队运算：从队尾插入一个元素； （2）退队运算：从队头删除一个元素。,青岛工学院

14、,例题,下列关于栈的叙述中正确的是_。A. 在栈中只能插入数据B. 在栈中只能删除数据C. 栈是先进先出的线性表D. 栈是先进后出的线性表 栈和队列的共同点是_。A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点 栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是_。A. CABEDB. DBCEAC. CDABED. DCBEA,(D),(C),(D),青岛工学院,下列关于队列的叙述中正确的是_。A. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表 下列不是

15、栈的运算的是_。A. 删除栈顶元素B. 删除栈底元素C. 判断栈是否为空D. 将栈置为空栈 若进栈序列为1，2，3，4，进栈过程中可以出栈，则下列不可能的一个出栈序列是_ 。 A. 1432B. 2341C. 3142D. 3421 栈的基本运算有三种：入栈、退栈和_。 在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有_个元素,(C),(B),(C),读栈,(3) 计算公式是： （尾指针-头指针+容量）%容量,青岛工学院,下列关于线性表、栈和队列的叙述，错误的是（） A线性表是给定的n（n必须大于零）个元素组成的序列 B线性表允许在表的任何位置上进行

16、插入和删除操作 C栈只允许在一端进行插入和删除操作 D队列允许在一端进行插入在另一端进行删除 一个队列的入队序列是1，2，3，4，则队列的输出序列是（） A4，3，2，1B1，2，3，4 C1，4，3，2D3，2，4，1 设初始输入序列为1，2，3，4，5，利用一个栈产生输出序列，下列（）序列是不可能通过栈产生的。 A1，2，3，4，5B5，3，4，1，2 C4，3，2，1，5D3，4，5，2，1,(A),(B),(B),青岛工学院,设栈S的初始状态为空，6个元素入栈的顺序为e1，e2，e3，e4，e5和e6。若出栈的顺序是e2，e4，e3，e6 ，e5 ，e1，则栈S的容量至少应该是（） A6B4C3D2,(C),青岛工学院,1.5 线性链表,由于顺序存储有一些缺点，某些情况我们需采用链式存储结构。链式结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存