《二级《公共基础知识》考试辅导(1)教材》由会员分享，可在线阅读，更多相关《二级《公共基础知识》考试辅导(1)教材（115页珍藏版）》请在金锄头文库上搜索。
1、辅导（1） 主讲教师主讲教师: : 巫张英巫张英 第第1 1章章 数据结构与算法数据结构与算法 1.1.1 算法的基本概念 所谓算法是指解题方案的准确而完整的描述。 1、算法的基本特征 可行性、确定性、有穷性、拥有足够的情报 。 2、算法的基本要素 （1）算法中对数据的运算和操作 （2）算法的控制结构 顺序、选择、循环三种基本控制结构 1.1.2 1.1.2 算法复杂度算法复杂度 1. 算法的时间复杂度 是指执行算法所需要的计算工作量。 算法的计算工作量用算法所执行的基本运 算次数来度量。 2. 算法的空间复杂度 是指执行这个算法所需要的内存空间。（ 包括程序、数据和额外空间） 选择题 (1)
2、 下列叙述中正确的是 A) 算法的效率只与问题的规模有关，而与数据 的存储结构无关 B) 算法的时间复杂度是指执行算法所需要的计 算工作量 C) 数据的逻辑结构与存储结构是一一对应的 D) 算法的时间复杂度与空间复杂度一定相关 B （5）算法的有穷性是指 A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的 D）算法只能被有限的用户使用 A (7) 下列叙述中正确的是 _ 。 A) 一个算法的空间复杂度大，则其时间复杂度也必定大 B) 一个算法的空间复杂度大，则其时间复杂度必定小 C) 一个算法的时间复杂度大，则其空间复杂度必定小 D) 上述三种说法都
3、不对 D （4）算法的空间复杂度是指 A （2）算法的时间复杂度是指 D （1）下列叙述中正确的是 _ 。 D 1.2 数据结构的基本概念 1.2.1 什么是数据结构 1.2.1 什么是数据结构 1.2.1 什么是数据结构 1.2.1 什么是数据结构 1.2.1 什么是数据结构 数据的逻辑结构 数据的存储结构 采用不同的存储结构，其数据处理的效率 是不同的。 数据的存储结构 数据的存储结构 1.2.3 线性结构与非线性结构 如果一个非空的数据结构满足下列两个条件： 有且只有一个根结点； 每一个结点最多有一个前件，也最多有一个后件 。 则称该数据结构为线性结构。 线性结构又称线性表。 如果一个数
4、据结构不是线性结构，则称之为 非线性结构。 1.3.1 线性表的基本概念 线性表是最简单、最常用的一种数据结构。 线性表是由一组数据元素组成。数据元素在线 性表中的位置只取决于它们的序号，即数据元素之 间的相对位置是线性的。 例如： 一个 n 维向量（x1, x2, x3, , xn） 是一个长度 为 n 的线性表，其中的每一个分量就是一个数据元 素。 一年中的四个季节（春，夏，秋，冬）是一个 长度为 4 的线性表，其中的每一个季节名就是一个 数据元素。 矩阵也是一个线性表，把一行看成一个数据元素 。 1.3.2 线性表的顺序存储结构 线性表的顺序存储结构具有以下两个基本特 点： 线性表中所有
5、元素所占的存储空间是连续 的； 线性表中各数据元素在存储空间中是按逻 辑顺序依次存放的。 注意：在线性表的顺序存储结构中，其前 后件两个元素在存储空间中是紧邻的，而且前 件元素一定存储后件元素的前面。 线性表的顺序存储结构 （5）下列叙述中正确的是 。 A）程序执行的效率与数据的存储结构密切相关 B）程序执行的效率只取决于程序的控制结构 C）程序执行的效率只取决于所处理的数据量 D）以上三种说法都不对 A （6）下列叙述中正确的是 。 A）数据的逻辑结构与存储结构必定是一一 对应的 B）由于计算机存储空间是向量式的存储结 构，因此，数据的存储结构一定是线性结构 C）程序设计语言中的数组一般是顺
6、序存储 结构，因此，利用数组只能处理线性结构 D）以上三种说法都不对 D B （7）下列叙述中正确的是 。 1.4.1 栈及其基本运算 栈的定义 栈的定义 栈的特点 2. 栈的顺序存储及基本运算 栈的顺序存储示例 p20 栈的基本运算 C （2）下列叙述中正确的是 。 (4) 按照“后进先出”原则组织数据的数 据结构是 A) 队列 B) 栈 C) 双向链表 D) 二叉树 B 填空题（每空2分） 4. 按 “先进后出” 原则组织数据的数据结 构是 【4】 。 栈 （7）下列关于栈的叙述正确的是 A）栈按 “先进先出” 组织数据 B）栈按 “先进后出” 组织数据 C）只能在栈底插入数据 D）不能删
7、除数据 B 一、选择题 （1）一个栈的初始状态为空。现将元素 1、2、3、4、5、A、B、C、D、E 依次入栈 ，然后再依次出栈，则元素出栈的顺序是 A）12345ABCDE B）EDCBA54321 C）ABCDE12345 D）54321EDCBA B 一、选择题（每小题2分） （1）下列叙述中正确的是 A）栈是“先进先出”的线性表 B）队列是“先进后出”的线性表 C）循环队列是非线性结构 D）有序性表既可以采用顺序存储结构， 也可以采用链式存储结构 D 二、填空题（每空2分） （1）假设一个长度为 50 的数组（数组元素的 下标从 0到 49）作为栈的存储空间，栈底指针 bottom 指
8、向栈底元素，栈顶指针 top 指向栈顶元 素，如果 bottom=49，top=30（数组下标），则 栈中具有 【1】 个元素。 20 A 1.4.2 对列及其运算 对列是“先进先出”或“后进后出”的线性表。 对头指针对尾指针 排头指针 队尾指针 队尾指针 排头指针 排头指针 队尾指针 2. 循环队列及其运算 队尾指针 排头指针 队尾指针 排头指针 排头指针 队尾指针 为了能区分队列空或队列满，故增加一个标志 S，S 值的定义如下 ： 0 表示队列空 S = 1 表示队列非空 (5) 下列对队列的叙述正确的是 A) 队列属于非线性表 B) 队列按 “先进后出” 原则组织数据 C) 队列在队尾删
9、除数据 D) 队列按 “先进先出” 原则组织数据 D 二、填空题（每空2分） (3) 线性表的存储结构主要分为顺序存 储结构和链式存储结构。队列是一种特殊 的线性表，循环队列是队列的 【3】 存储 结构。 顺序 二、填空题（每空2分） (3) 设某循环队列的容量为50，头指针 front=5（指向队头元素的前一位置），尾 指针 rear=29（指向队尾元素），则该循环 队列中共有 【3】 个元素。 24 即 29-5=24 一、选择题 （2）下列叙述中正确的是 A）循环队列有队头和队尾两个指针，因此， 循环队列是非线性结构 B）在循环队列中，只需要队头指针就能反映 队列中元素的动态变化情况 C
10、）在循环队列中，只需要队尾指针就能反映 队列中元素的动态变化情况 D）循环队列中元素的个数是由队头指针和队 尾指针共同决定 D （2）下列数据结构中，能够按照 “先进 先出” 原则存取数据的是 A）循环队列 B）栈 C）队列 D）二叉树 C （3）对于循环队列，下列叙述中正确的是 D 二、填空题（每空2分） A,B,C,D,E,F,5,4,3,2,1 15 （1）下列叙述中正确的是_。 A循环队列是队列的一种链式存储结构 B循环队列是一种逻辑结构 C循环队列是非线性结构 D循环队列是队列的一种顺序存储结构 D （2）下列叙述中正确的是_。 A栈是一种先进先出的线性表 B队列是一种后进先出的线性
11、表 C栈与队列都是非线性结构 D以上三种说法都不对 D 1.5 线性链表 在链式存储方式中，要求每个结点有两部 分组成：一部分用于存放数据元素值，称为数 据域；另一部分用于存放指针，称为指针域。 其中指针用于指向该结点的前一个结点（前件 ）或后一个结点（后件）。 在链式存储结构中，存储结构的存储空间 可以不连续。 链式存储结构既可以用于表示线性结构， 也可以用于表示非线性结构。 数据域 指针域 线性表的链式存储结构称为线性链表。 线性链表在插入或删除过程中不发生数 据元素移动的现象，只需改变有关结点的 指针。 线性单链表 循环链表比线性单链表增加了一个表 头结点。在对循环链表进行插入或删除过
12、程中，实现了空表与非空表的运算统一。 5. 数据结构分为线性结构和非线性结构 ，带链的队列属于 【 5 】 。 线性结构 （2）下列叙述中正确的是 _ 。 B （2）下列关于线性链表的叙述中，正确 的是 _ 。 C 桥1. 数据结构分为线性结构和非线性 结构，带链的栈属于 【 1 】 。线性结构 1.6 树与二叉树 1.6 树与二叉树 1.6.1 树的概念 树是一种简单的非线性结构。树中的所有元 素之间的关系具有明显的层次特性。 在树的图形中，用直线连起来的两端结点中 ，上端结点是前件，下端结点是后件。 树结构的基本特征和术语 在树结构中，每一个结点只有一个前件，称为父结点，没有 前件的结点只
13、有一个，称为树的根结点，简称为树的根。 在 树结构中，每一个结点可以有多个后件，它们都称为该结点的子 结点。没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件个数称为该结点的度。 在树中，所有结点中的最大的度称为树的度。 树是一种层次结构，根结点在树中的第一层。树的最大层次 称为树的深度。在树中，叶子结点没有子树。 根结点 叶子结点 第 1 层 第 2 层 第 3 层 第 4 层 该树的度为2 树的深度为4 一、选择题（每小题2分） （1）下列数据结构中，属于非线性结构 的是 A）循环队列 B）带链队列 C）二叉树 D）带链栈 C 1.6.2 二叉树及其性质 二叉树 二叉树 二叉树
14、 二叉树 二叉树 二叉树的基本性质 二叉树 二叉树 二叉树 二叉树 (7)在深度为7的满二叉树中，叶子结点的个数为。 A)32 B) 31 C) 64 D) 63 性质3(P34) 在任意一棵二叉树中，度为0的结点（即叶子结点 ）总是比度为2的结点多一个。 (P35)满二叉树每层上的结点数都达到最大值，即第k层上有2k -1个结点，且深度为m的满二叉树有2m-1个结点 解法1：= 27-1 = 26 = 64 解法2：设叶子结点（度为0）为n 27 -1 = n + n -1 n=64 解法3：直接推算出来 C 1 = 20 2 = 21 4 = 22 8 = 23 16 = 24 32 = 25 64 = 26
