全国计算机二级基础重点知识点解析

《全国计算机二级基础重点知识点解析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、全国计算机二级基础§1基本数据结构和算法1.1算法算法概念：是对一个问题求解步骤的一种描述，是求解问题的方法，它是指令的有限序列，其中每条指令表示一个或者多个操作。算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。(2011.9)（1）下列叙述中正确的是（）A)算法就是程序B)设计算法时只要考虑数据结构的设计C)设计算法时只需要考虑结果的可靠性D）以上说法都不对算法的基本特征：          （1）可行性；          （2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；         

2、 （3）有穷性，算法必须能在有限的时间内做完，取能在执行有限个步骤后终止，包括合理的执行时间的含义；          （4）输入(>=0)和输出性（>=1）。例 一个算法应该具有“确定性”等5个特性，下面对另外4个特性的描述中错误的是（  ）。    A．有零个或多个输入      B．有零个或多个输出    C．有穷性        D．可行性    答案：B 算法的基本要素：（1）算法中对数据的运算和操作在一般的计算机系统中，基本的运算和操作有以下4类：算术运算、逻辑运算、关系运算和数据传输。（2）算法的控制结构一个算法一般都可以用顺序、选择、

3、循环3种基本控制结构组合而成。     算法的复杂度：算法时间复杂和算法空间复杂度。      （1）算法时间复杂度是指执行算法所需要的计算工作量。      （2）算法空间复杂度是指执行这个算法所需要的内存空间。 程序设计语言是用于书写计算机程序的语言，其基本成分有以下4种，数据成分：用来描述程序中的数据。运算成分：描述程序中所需的运算。控制成分：用来构造程序的逻辑控制结构。传输成分：定义数据传输成分，如输入输出语言。例：程序设计语言的基本成分是数据成分、运算成分、控制成分和（）。A)对象成分B)变量成分C)语句成分D)传输成分1.2数据结构的基本

4、概念 数据结构研究的三个方面：          （1）数据集合中和数元素之间所固有的逻辑关系，即数据的逻辑结构；          （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；          （3）对各种数据结构进行的运算。(基于逻辑结构)数据的逻辑结构包含：          （1）表示数据元素的信息；          （2）表示各数据元素之间的前后件关系。数据的存储结构有顺序、链接、索引等。          线性结构条件：          （1）有且只有一个根结点；          （2）每一个结点最

5、多有一个前件，也最多有一个后件。          非线性结构：不满足线性结构条件的数据结构。(2011.3)（2）下列叙述中正确的是（）Ａ）有一个以上根结点的数据结构不一定是非线性结构Ｂ）只有一个根结点的数据结构不一定是线性结构Ｃ）循环链表是非线性结构Ｄ）双向链表是非线性结构1.3 线性表及其顺序存储结构线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。非空线性表的结构特征：（1）且只有一个根结点a1，它无前件；（2）有

6、且只有一个终端结点an，它无后件；（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)×k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。(2011.9)（2）长度为n的顺序存储的线性表中插入一个元素，最坏情况下需要移动表中【2】元素。(2010.9)（

7、1）下列叙述中正确的是A）线性表的链式存储结构与顺序存储结构所需要的空间是相同的B）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D)上述三种说法都不对1.4 栈和队列栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。(2011.9)（1）数据结构分为线性结构与非线性结构，带链的栈属于【1】。(2011.3)（1）下列关于栈叙述正确的是（）A)栈顶元素最先能被删除B)栈顶元素最后才能被删除C)栈底元素永远不能被删除D）以上三种

8、说法都不对栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。用top表示栈顶