全国计算机等级考试二级公共基础考点
● 算法是问题求解过程的精确描述， 它为解决某一特定类型的问题规定了一个运算过程。以下关于算法的叙述中，错误的是（62）。
（62）
A.流程图（flow chart）是算法的一种图形表示方法
B.用伪代码描述的算法易于转换成程序
C.用 N/S盒图可以保证算法的良好结构（即由顺序、选择和重复结构来表示算法）
D.用 E-R 图可以同时描述算法步骤和数据模型
一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现，这句话说明算法具有(62)特性。
A．有穷性
B．健壮性
C．可行性
D．确定性
解析：本题考查算法基本概念。一个算法是对某类给定问题求解过程的精确描述，算法有5个基本特性：有穷性、确定性、可行性、有输入和有输出。其中，有穷性是指对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即算法中的每个步骤都能在有限时间内完成。确定性是指对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行，并且在任何条件下，算法都只有一条执行路径。可行性是指算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。题目中的描述说明的是算法的可行性。
算法的基本特征是可行性、确定性、（ ）和拥有足够的情报。
有穷性
● 一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现，这句话说明算法具有 （62） 特性。
（62）
A. 有穷性
B. 可行性
C. 确定性
D. 健壮性
算法的基本特征是可行性、确定性、_________和拥有足够的情报。
【解析】算法是指解题方案的准确而完整的描述。它有4个基本特征，分别是可行性、确定性、有穷性和拥有足够的情报。
第一部分 数据结构部分考点1 算法的复杂度1. 算法的基本概念算法是对问题求解过程的精确描述。算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。算法的基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。算法的3种基本控制结构：顺序结构、选择结构、循环结构。算法基本设计方法主要有：列举法、归纳法、递推、递归、减半递推技术、回溯法。指令系统：一台计算机系统能执行的所有指令的集合。2. 算法的复杂度算法的复杂度包括时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量；空间复杂度是指执行算法所需要的内存空间。典型题例1算法的有穷性是指 。A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用2算法的空间复杂度是指 。A）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数3算法的时间复杂度是指 。 A) 算法的执行时间 B）算法所处理的数据量 C) 算法程序中的语句或指令条数 D）算法在执行过程中所需要的基本运算次数4下列叙述中正确的是 。A）算法就是程序B）设计算法时只需要考虑数据结构的设计C）设计算法时只需要考虑结果的可靠性D）以上三种说法都不对5算法的时间复杂度取决于 。A）问题的规模B）待处理的数据的初态C）问题的难度D）A）和B）6问题处理方案的正确而完整的描述称为 。算法考点2 逻辑结构和存储结构1. 数据结构的基本概念(1)数据结构：是指相互有关联的数据元素的集合。(2)数据结构主要研究3个方面的内容：数据集合中各数据元素之间的逻辑关系，即数据的逻辑结构；在对资料进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；对各种数据结构进行的运算。2. 逻辑结构数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。所以一个数据结构B可以表示成：B=(D，R)例如，如果把一年四季看作一个数据结构，则可表示成：B=(D,R)，其中D=春季，夏季，秋季，冬季，R=（春季，夏季）,（夏季，秋季），（秋季，冬季）。3. 存储结构数据的逻辑结构在计算机存储空间中的存放形式称数据的存储（物理）结构。数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序存储结构、链接存储结构。顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。链式存储结构就是在每个结点中至少包含一个指标域，用指标来体现数据元素之间逻辑上的联系。考点 3 线性结构和非线性结构1. 线性结构根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类：线性结构和非线性结构。如果一非空的数据结构满足：有且仅有一个根结点；每一个结点最多有一个前件，也最多有一件后件。则称该数据结构为线性结构或线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串等都是线性结构。2. 非线性结构如果一个数据结构不满足线性结构的两个条件的一个或两个，则该结构称为非线性结构。广义表、树和图等数据结构都是非线性结构。3. 线性表的顺序存储结构具有以下两个基本特点(1)线性表中所有元素所占的存储空间是连续的；(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。例如，对于线性表(a1,a2,ai,an)元素ai的存储位址为：ADR(ai)=ADR(a1)+(i-1)*k其中，ADR(a1)是第一个元素的位址，k代表每个元素所占的位元组数。4. 顺序表的运算顺序表是指线性表的顺序存储结构，对顺序表的运算有：查找、插入、删除等。典型题例1下列叙述中正确的是 。A）顺序结构存储的存储一定是连续的，链式存储结构的存储空间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间2下列数据结构中，属于非线性结构的是 。A）循环队列 B) 带链队列 C) 二叉树 D）带链栈3下列关于线性链表的叙述中，正确的是 。A）各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致B）各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续C）进行插入与删除时，不需要移动表中的元素D）以上三种说法都不对4下列链表中，其逻辑结构属于非线性结构的是 。A）双向链表B）带链的栈C）二叉链表D）循环链表5下列叙述中正确的是 。A）一个逻辑结构只能有一种存储结构B）逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理效率6链表不具备的特点是 。A）可随机访问任一结点B）插入和删除不需要移动任何元素C）不必事行估计存储空间D）所需空间与其长度成正比考点 4 栈1. 栈的基本概念栈(stack)是一种特殊的线性表，是限定只在一端进行插入与删除的线性表。在栈中，一端是封闭的，既不允许进行插入元素，也不允许删除元素；另一端是开口的，允许插入和删除元素。通常称插入、删除的一端为栈顶，另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是最后被插入的元素，从而也是最先被删除的元素。栈底元素总是最先被插入的元素，因而也是最后才能被删除的元素。栈是按照“先进后出” (First In Last Out,简称FILO)或“后进先出”的原则组织数据的。例如，枪械的子弹匣就可以用来形象地表示栈结构。子弹匣的一端是完全封闭的，最后被压入弹匣的子弹总是最先被弹出，而最先被压入的子弹最后才能被弹出。2. 栈的顺序存储及其运算 栈的基本运算有3种：入栈、退栈与读栈顶元素。入栈运算：在栈顶位置插入一个新元素；退栈运算：取出栈顶元素并赋给一个指定的变数；读栈顶元素：将栈顶元素赋给一个指定的变数。典型题例1下列关于栈的叙述正确的是 。A）栈按“先进先出”组织数据 B）栈按“先进后出”组织数据C）只能在栈底插入数据 D）不能删除数据2一个栈的初始状态为空。现、将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是 。A）12345ABCDE B）EDCBA54321C）ABCDE12345 D）54321EDCBA3假设用一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有_【1】_个元素。194下列数据结果中，能够按照“先进后出”原则存取资料的是 。A) 循环队列 B) 栈 C)队列 D)二叉树5下列关于栈的叙述中，正确的是 。A)栈顶元素最先能被删除 B)栈顶元素最后才能被删除、C)栈底元素永远不能被删除 D)以上三种说法都不对6下列关于栈的叙述中，正确的是 。A)栈底元素一定一定是最后入栈的元素B)栈操作遵循先进后出的原则C)栈顶元素一定是最先入栈的元素D)以上三种说法都不对7数据结构分为线性结构与非线性结构，带链的栈属于 【1】 。线性结构8设栈的存储空间为S（1：40），初始状态为bottom=0,top=0，现经过一系列入栈和出栈运算后，top=20，则当前栈中有 【1】 元素。209以下不是栈的基本运算的是 。A)判断栈是否为空B)将栈置为空栈C)删除栈顶元素D)删除栈底元素考点 5 队列1. 队列的基本概念队列是只允许在一端进行删除，在另一端进行插入的线性
算法是问题求解过程的精确描述，它为解决某一特定类型的问题规定了一个运算过程。以下关于算法的叙述中，错误的是( )。
A．流程图(玎ow chart)是算法的一种图形表示方法
B．用伪代码描述的算法易于转换成程序
C．用N／s盒图可以保证算法的良好结构(即由顺序、选择和重复结构来表示算法)
D．用E—R图可以同时描述算法步骤和数据模型
解析：流程图是表示算法图形化工具，伪代码也是描述算法时的常用工具，并且可以很容易的转变为程序；N／S也是表示算法的工具，并且可以保证算法的良好结构。E—R图则是指实体一联系图，用于表示数据库设计中的概念设计模型，不能表达算法步骤。
下列描述中正确的是（ ）。
A. 算法是指对解题方案的准确而完整的描述
B. 算法的有穷性是指算法程序的长度是有限的
C. 算法是否有效与拥有的情报无关
D. 算法的基本特征有可行性、确定性和有穷性
算法是指对解题方案的准确而完整的描述。算法具有4个特征：可行性、确定性、有穷性和拥有足够的情报。有穷性指算法必须在有限时间内做完，即算法必须能在执行有限个步骤之后终止。当算法拥有足够的情报时，此算法才是有效的；当提供的情报不够时，算法可能无效。
下列描述中正确的是（ ）。
A.算法是指对解题方案的准确而完整的描述
B.算法的有穷性是指算法程序的长度是有限的
C.算法是否有效与拥有的情报无关
D.算法的基本特征有可行性、确定性和有穷性
算法是指对解题方案的准确而完整的描述。算法具有4个特征：可行性、确定性、有穷性和拥有足够的情报。有穷性指算法必须在有限时间内做完，即算法必须能在执行有限个步骤之后终止。当算法拥有足够的情报时，此算法才是有效的；当提供的情报不够时，算法可能无效。
下列有关算法的描述中错误的是( )。
A．所谓算法是指解题方案的准确而完整的描述
B．算法的基本特征有：可行性、确定性、有穷性和拥有足够的情报等
C．算法的复杂度主要包括时间复杂度和空间复杂度
D．算法的时间复杂度是指执行算法程序所需要的时间
解析：算法的时间复杂度是指算法执行过程中所需要的基本运算次数。
下列有关算法的描述中，错误的是( )。
A．所谓算法是指解题方案的准确而完整的描述
B．算法的基本特征有：可行性、确定性、有穷性和拥有足够的情报等
C．算法的复杂度主要包括时间复杂度和空间复杂度
D．算法的时间复杂度是指执行算法程序所需要的时间
解析：算法的时间复杂度是指算法执行过程中所需要的基本运算次数。