二级公共基础知识(教师版)

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

1、全国计算机等级考试二级公共基础知识热烈欢迎你们来共同学习，有问题随时联系！二级公共基础知识点分值分布第一章 数据结构与算法(30%)n 考试大纲1. 算法的基本概念；算法复杂度的概念和意义（时间 复杂度与空间复杂度）。 2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图 形表示；线性结构与非线性结构的概念。 3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、 中序和后序遍历。 7. 顺序查找与二分

2、法查找算法；基本排序算法（交换类排序，选 择类排序，插入类排序）。一.算法的基本概念*1.所谓算法是指解题方案的准确而完整 的描述。严格来说，一个算法必须具有以下 五个主要特征：n有穷性（有限步骤内完成） 、 确定性（结果不能模棱两可）、 可行性（能够完成目标要求）、 输入 、 输出n输出和输出可说成：拥有足够的情报 2.算法的组成要素n算法中对数据的运算和操作n算法的控制结构一.算法的基本概念3.算法设计的要求 通常设计一个“好”的算法，应考虑达到以下目标。n正确性：算法应当满足具体问题的需求。n可读性：算法主要是为了人的阅读与交流，其次才是机 器执行。可读性好有助于人对算法的理解。n健壮性

3、：当输入数据非法时，算法也能适当地做出反应 或进行处理，而不会产生莫明其妙的输出结果。 n效率与低存储量需求。 效率指的是算法执行时间。对于同一个问题如果有多个 算法可以解决，执行时间短的算法效率高。低存储量需求 指算法执行过程中所需要的最大存储空间。一.算法的基本概念4.算法设计基本方法n列举法n归纳法n递推n递归n减半递推n回溯法一.算法的基本概念*5.算法的复杂度可分为时间复杂度 和空间复杂度，是衡量算法优劣的量度 。 （1）算法的时间复杂度n算法的时间复杂度是指执行算法所需 要的工作量。一般情况下，算法的时间 复杂度为算法中的基本操作重复执行的 次数。是问题规模n的某个函数f(n)。一

4、.算法的基本概念n何估算算法的时间复杂度？任何一个算法都是由一个“控制结构 ”和若干“原操作”组成的，因此一个算 法的执行时间可以看成是所有原操作的执 行时间之和( 原操作(i)的执行次数原操作 (i)的执行时间 )nFor i=1 to 100for j=1 to 100s=i*j 。 算法时间复杂度为：O（n2)一.算法的基本概念（2）算法的空间复杂度n算法的空间负杂度是指执行这个算法所需 要的内存空间。空间复杂度作为算法所需存 储空间的量度，记作：S(n)=O(g(n)，其中n 为问题的规模，表示随问题规模的增大，算 法运行所需存储量的增长率与g(n)的增长率 相同。n一般不估计空间复杂

5、度 (3)算法分析：对算法的效率进行分析，以 求改进的过程。典型例题1.一个算法是对某类给定的问题求解过程的精确描述，算法中的操作都 可能 通过将已经实现的基本操作执行有限次来实现，这句话说明算法具有什么特性？A 有穷性 B 可行性 C 确定性 D 健壮性 2.算法的时间复杂度是指（） A）执行算法程序所需要的时间 B）算法程序的长度 C）算法执行过程中所需要的基本运算次数 D）算法程序中的指令条数 3.下面叙述正确的是（） A）算法的执行效率与数据的存储结构无关 B）算法得空间复杂度是指 算法程序中指令（或语句）的条数 C）算法得有穷性是指算法必须能在执行 有限个步骤之后终止 D）以上三种描

6、述都不对 4.算法能正确地实现预定功能的特性称为算法的（ ）。A正确性 B易读性 C健壮性 D高效率 5. 算法的计算量的大小称为计算的（ ）。A效率 B. 复杂性 C. 现实性 D. 难度 二.数据结构1.数据结构的定义：是指相互有关联的数据元素的集合。备注： 1）数据元素：是数据的基本单位，由数据项组成。通 俗的说：数据元素就是现实世界中的一个实体的抽象。 2）数据项：数据的最小单位。 *2. 数据结构主要研究三个方面的问 题：1)数据集合中各数据元素之间的逻辑关系 ，即数据的逻辑结构。 2)在对数据进行处理时，各数据元素在计 算机中的存储关系，即数据的存储结构。 3)对各种数据结构进行的

7、运算。数据结构简单实例Student Student zhangsan Student lisi name; zhangsan; lisi;Sno; s20081001; s20081001; class; 计算机1班； 计算机1班 ；Rscore; 515； 501； 数据的逻辑结构n数据逻辑结构是对数 据元素之间存在的逻辑 关系的描述（本身固有 的），它可以用一个数 据元素的集合和定义在 此集合上的若干关系表 示。n与数据在计算机中的 存储位置无关，是独立 于计算机的。n常见的有线性结构和 非线性结构两种。 数据的存储结构n数据的存储结构是数据元素及其关系在计算机存储 器中的表示，也称为物

8、理结构。存储结构的主要内容 是指在存储空间中使用一个存储结点来存储一个数据 元素，在存储空间中建立各存储结点之间的关联，来 表示数据元素之间的逻辑关系。n常见的存储结构：n顺序存储结构、链式存储结构、索引存储结构、散列存储结 构典型例题（1）数据结构中，与所使用的计算机无关的是数据的 A）存储结构 B）物理结构 C）逻辑结构 D）物理和存储结构 （2）数据在计算机中的存储位置改变了，（）不变。 A.数据的存储地址 B.数据间的逻辑关系 C.数据的物理存储结构 D.逻辑结构和物理结构线性结构和非线性结构线性结构n在数据元素的非空有限集合中，线性结构的逻辑 特征如下：n存在一个唯一的被称为“第一个

9、”的数据元素n存在一个唯一的被称为“最后一个”的数据元素n除第一个之外，集合中的每个数据元素均有且只 有一个直接前驱n除最后一个之外，集合中的每个数据元素均有且 只有一个直接后继 非线性结构n非线性结构的逻辑特征是：一个结点可能有多个 直接前驱和直接后继，树和图都属于非线性结构。线性表n通常以下列 n 个数据元素的序列” 表示线性表 ：(a1,a2 ,.,ai ,.,an) n序列中数据元素的个数 n 定义为线 性表的表长；n=0 时的线性表被称为空 表。称 i 为ai在线性表中的位序。n元素大多数时候称为”结点“线性表的顺序存储n线性表的顺序存储结构用一组地址连续的存储单元依次 存放线性表中

10、的数据元素，即以“存储位置相邻”表示“位 序相继的两个数据元素之间的前驱和后继的关系，并以表中 第一个元素的存储位置作为线性表的起始地址，称作线性表 的基地址。 所有结点的存储位置均可由第一个结点的存储位置得到 ADR(ai) = ADR(a1) + (i-1)C 基地址 一个数据元素所占存储量 线性表的插入和删除运算n插入结点：要在第i(1in)个元素之前 插入一个新元素时，首先要从最后一个元素 开始，直到第i个元素之间共n-i+1个元素依 次向后移动一个位置，然后将新元素插入到 第i项。n删除结点：要删除第i(1in)个元素， 要从第i+1个元素开始，直到第n个元素，共 n-i个元素依次向

11、前移动一个位置。栈n栈是限定仅在表的一端进行插入和删除操作的线性表。允许插 入和删除的一端称为栈顶，另一端称为栈底。n栈顶元素总是最后被插入的元素，从而也是最先被删除的元素 ；栈底元素总是最先被插入，也是最后被删除的元素。因此，栈 是一种后进先出（LIFO）的线性表。n通常用指针top指示栈顶位置，用指针bottom指示栈底位置。栈的顺序存储及运算n用一维数组S(1:m)作为栈的顺序存储空间，m 为栈的最大容量。top=0表示栈为空，top=m表示 栈满。n栈的操作n入栈：在栈顶位置插入一个新元素，栈顶指针top加 1。n退栈：取出栈顶元素并赋值给一个指定的变量，栈 顶指针top减1。n取栈顶

12、元素：将栈顶元素的值赋给一个指定的变量 ，不删除栈顶元素，栈顶指针top不变。栈的溢出n上溢当栈满时再做进栈运算必定产生空间溢出，简称“上 溢”。n下溢当栈空时再做退栈运算也将产生溢出，简称“下溢” 。n备注(1)上溢是一种出错状态，应该设法避免之；下溢则可 能是正常现象。(2) 两个栈共享一块空间时，分配的存储空间要大于等 于栈元素较多的栈，这样可以减少“上溢”。栈n如果某栈的入栈顺序是ABCDEF，则出栈顺序不 可能是哪个（） A、DCEFBA B、ABCDEF C、EDFCAB D、 CBAEDF备注：这样的题目，字母出来的顺序不可以：先 大，后小，再中。例：如果进栈序列为e1,e2,e

13、3,e4，则可能的出栈序列 是 A）e3,e1,e4,e2 B） e2,e4,e3,e1 C）e3,e4,e1,e2 D）任意 顺序队列n队列是一种先进先出的线性表，它只允许在表的一 端插入元素(队尾)，在另一端删除元素(队头)。n向队尾插入一个元素的操作称为入队，头指针 front +1，从队头删除一个元素的操作称为退队，尾 指针rear+1。n队列和栈一样是一种特殊的线性表、是操作受限的 线性表、也称其为限定性数据结构。循环队列n将队列存储空间的最后一个位置绕到第一个位置，形成逻辑 上的环状空间。循环队列初始状态为空，即front=rear=0.nFront总是指示队头元素，rear指示队

14、尾元素加1的位置。n入队操作时，rear加1，若rear+1=容量，则置rear=0；n退队操作时，front加1，若front+1=容量，则置front=0 。n*当rearfront时，元素个数rearfront ；当rearnext删除节点：p-next= p-next-next插入节点：p-next= pxpx-next=p-after that双向链表和循环链表n在双向链表中的结点包含两个指针域，其中一个指向直接后继 ，另一个指向直接前驱。n循环链表的特点是表中最后一个结点的指针域指向第一个结点 ，整个链表成为一个由链指针相链接的环。据此，从表中任一节 点出发均可找到表中其它结点。在

15、循环链表中增加了一个表头结 点，其指针域指向第一个元素结点，头指针则指向头结点。HEADHEADHEAD回顾：例：已知一组数据原先采用顺序存储，现改为散列存储，则（）不 变。A.存储结构 B.逻辑结构 C.数据间的顺序 D.不确定 例：常见的线性结构有_,_,_ 例：在线性表中删除第5个节点，则原第6个节点的位置（），如果 单链表则（）A.6 B.5 C.不变 D.不确定 例：已知栈的头指针front当前位置为5，从栈中读取一个数据，则 front指向（）A.5 B.6 C.不变 D.不确定 例：如果某栈的入栈顺序是123456，则出栈顺序不可能是哪个（）A、435621 B.123456 C、546312 D、65432