计算机二级考试真题及答案

1、计算机二级考试真题1） 在下列选项中，哪个不是一个算法一般应该具有的基本特征_。（ ）A. 确定性B. 可行性C. 无穷性D. 拥有足够的情报2） 下面叙述正确的是_。（ ）A. 算法的执行效率与数据的存储结构无关B. 算法的空间复杂度是指算法程序中指令（或语句）的条数（指的是算法所占用的空间）C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止D. 以上三种描述都不对3） 算法的空间复杂度是指_。（ ）A. 算法程序的长度 B. 算法程序中的指令条数C. 算法程序所占的存储空间 D. 算法执行过程中所需要的存储空间4） 数据的存储结构是指_。（ ）A. 数据所占的存储空间量 B. 数据的

2、逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式 D. 存储在外存中的数据5） 算法一般都可以用哪几种控制结构组合而成_。（ ）A. 循环、分支、递归 B. 顺序、循环、嵌套 C. 循环、递归、选择 D. 顺序、选择、循环6） 在计算机中，算法是指_。（ ）A. 查询方法B. 加工方法 C. 解题方案的准确而完整的描述 D. 排序方法7） 算法分析的目的是_。（ ）A. 找出数据结构的合理性 B. 找出算法中输入和输出之间的关系C. 分析算法的易懂性和可靠性 D. 分析算法的效率以求改进8） n个顶点的强连通图的边数至少有_。（ ）A. n-1 B. n(n-1) C. n D. n

3、+19） 数据结构中，与所使用的计算机无关的是数据的_。（ ）A. 存储结构 B. 物理结构 C. 逻辑结构 D. 物理和存储结构10）串的长度是_ 。（ ）A. 串中不同字符的个数 B. 串中不同字母的个数C. 串中所含字符的个数且字符个数大于零 D. 串中所含字符的个数11）下列叙述中，错误的是_ （ ）A. 数据的存储结构与数据处理的效率密切相关 B. 数据的存储结构与数据处理的效率无关 C. 数据的存储结构在计算机中所占的空间不一定是连续的D. 一种数据的逻辑结构可以有多种存储结构12）下列叙述中正确的是_。（ ）A. 线性表是线性结构 B. 栈与队列是非线性结构C. 线性链表是非线性

4、结构 D. 二叉树是线性结构13）栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是_。（ ）A. ABCED B. DBCEA C. CDABE D. DCBEA14）下列叙述中正确的是_。（ ）A. 线性表是线性结构 B.栈与队列是非线性结构C. 线性链表是非线性结构 D. 二叉树是线性结构15）线性表的顺序存储结构和线性表的链式存储结构分别是_。（ ） A. 顺序存取的存储结构、顺序存取的存储结构 B. 随机存取的存储结构、顺序存取的存储结构 C. 随机存取的存储结构、随机存取的存储结构 D. 任意存取的存储结构、任意存取的存储结构16）以下数

5、据结构中不属于线性数据结构的是_。（ ）A. 队列 B. 线性表 C. 二叉树 D. 栈17）在单链表中，增加头结点的目的是_。（ ）A. 方便运算的实现 B. 使单链表至少有一个结点C. 标识表结点中首结点的位置 D. 说明单链表是线性表的链式存储实现18）用链表表示线性表的优点是_。（ ）A. 便于插入和删除操作B. 数据元素的物理顺序与逻辑顺序相同C. 花费的存储空间较顺序存储少D. 便于随机存取19）线性表L=(a1,a2,a3,ai,an)，下列说法正确的是_ （ ）A. 每个元素都有一个直接前件和直接后件 B. 线性表中至少要有一个元素C. 表中诸元素的排列顺序必须是由小到大或由大

6、到小 D. 除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件20）非空的循环单链表head的尾结点(由p所指向)，满足_ （ ）A. p->next=NULL B. p=NULL C. p->next=head D. p=head21）栈和队列的共同点是_。（ ）A. 都是先进后出B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点22）下列关于队列的叙述中正确的是_。（ ）A. 在队列中只能插入数据 B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表23）如果进栈序列为e1，e2，e3，e4，则可能

7、的出栈序列是_ （ ）A. e3，e1，e4，e2 B. e2，e4，e3，e1 C. e3，e4，e1，e2 D. 任意顺序24）已知一个栈的进栈序列是1，2，3，n，输出序列是p1,p2,p3.pn,若p1=n，则pi(1<i<n)为_ （ ）A. i B. n-i C. n-i+1 D. 不确定25）向一个栈顶指针为HS的链式栈中插入一个s所指的结点时，则执行_（ ）A. HS->next=s ; B. s->next= HS->next ; HS->next=s;C. s->next= HS; HS=s; D. s->next= HS;

8、HS= HS->next;26）设栈S的初始状态为空，6个元素入栈的顺序为1,2,3,4,5,6。若出栈的顺序是2,4,3,6,5,1,则栈S的容量至少应该是_（ ）A. 6 B. 4 C. 3 D. 227）为了减少栈溢出的可能性，可以让两个栈共享一片连续存储空间，两个栈的栈底分别设在这片空间的两端，这样只有当_时才可能产生上溢。（ ）A. 两个栈的栈顶在栈空间的某一位置相遇 B. 其中一个栈的栈顶到达栈空间的中心点C. 两个栈的栈顶同时到达栈空间的中心点D. 两个栈均不空，且一个栈的栈顶到边另一栈的栈底28）下列关于栈的叙述中正确的是_。（ ）A. 在栈中只能插入数据 B. 在栈中只

9、能删除数据C. 栈是先进先出的线性表 D. 栈是先进后出的线性表29）下列关于队列的叙述中正确的是_。（ ）A. 在队列中只能插入数据 B. 在队列中只能删除数据C. 队列是先进先出的线性表 D. 队列是先进后出的线性表30）栈和队列的共同点是_。（ ）A. 都是先进后出 B. 都是先进先出C. 只允许在端点处插入和删除元素 D. 没有共同点31）对线性表，下列情况下应当采用链表表示的是_（ ）A. 经常需要随机地存取元素 B. 经常需要进行插入和删除操作C. 表中元素需要占据一片连续的存储空间 D. 表中元素个数不变32）在一个链式队列中，假设f和r分别为队头与队尾指针，则删除结点的运算是_

10、（ ）A. r = f->next B. r = r->next C. f = f->next D. f = r->next33）设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为_。（ ）A. 349 B.350C. 255D. 35134）若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_ （ ）A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca35）设树T的度为4，其中度为1,2,3,4的结点个数分别为4,2,1,1。则T中的叶子结点数为_ （

11、）A. 8 B. 7 C. 6 D. 536）树最适合用来表示_（ ）A. 有序数据元素 B. 无序数据元素C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据37）某二叉树的先序和后序遍历顺序正好相反，则该二叉树一定是_（ ）A. 空或只有一个结点 B. 完全二叉树 C. 二叉排序树 D. 深度等于其结点数38）设n，m为一棵二叉树上的两个结点，在中序遍历中，n在m之前的条件是_（ ）adcfA. n在m右子树上 Bn是m的祖先C. n在m左子树上 D. n是m的子孙39）如图所示二叉树的中序遍历序列是_（ ）A. abcdgef B. dfebagcC. dbaefcg D.

12、abcdefg40）树是结点的集合，它的根结点数目是_ （ ）A. 有且只有1 B. 1或多于1 C. 0或1 D. 至少241）在一棵二叉树上第5层的结点数最多是_。（ ）A. 8 B. 16 C. 32 D. 1542）对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为_。（ ）A. N+1B. NC. (N+1)/2D. N/243）顺序查找适合于存储结构为_的线性表（ ）A. 散列存储B. 顺序存储或链式存储C. 压缩存储D. 索引存储44）采用顺序法查找长度为n的线性表时，每个元素的平均查找长度为_（ ）A. nB. n/2C. (n+1)/2D. (n-1)/245）希

13、尔排序法属于哪一种类型的排序法_。（ ）A. 交换类排序法 B. 插入类排序法 C. 选择类排序法 D. 建堆排序法46）在待排序的元素序列基本有序的前提下，效率最高的排序方法是_ （ ）A. 冒泡排序 B. 选择排序 C. 快速排序 D. 归并排序47）设有1000个元素，希望用最快的速度选出其中前10个最大的元素，最好选用_排序法。（ ）A. 冒泡 B. 快速 C. 堆 D. 选择48）在下列排序法中，_算法可能出现下列情况：在最后一趟开始之间，所有的元素都不在其最终位置上。（ ）A. 冒泡 B. 快速 C. 插入 D. 堆49）在下列几种排序方法中，要求内存量最大的是_。（ ）A. 插入

14、排序 B. 选择排序 C. 快速排序 D. 归并排序50）已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是_。（ ）A. 堆排序 B. 直接插入排序 C. 快速排序 D. 直接选择排序9.2 填空题1） 算法的复杂度主要包括_ _复杂度和空间复杂度。2） 现有按中序遍历二叉树的结果为abc，那么有 种不同形态的二叉树可以得到这一遍历结果。3） 若要对1000个元素排序，要求即快又节省空间，则最好采用 方法。4） 在平均情况下速度最快的排序方法为 排序。5） 有关键码序列（16,9,4,25,15,2,13,18,17,5,8,24），要求按关键码递增顺序排序。采用冒泡排序法，

15、则第二趟冒泡后的结果为 。6） 有关键码序列（16,9,4,25,15,2,13,18,17,5,8,24），要求按关键码递增顺序排序。采用初始增量为4的希尔排序，则一趟扫描后的结果为 。7） 假定一组记录为（46,79,56,38,40,80）对其进行快速排序的过程中，共需要 趟排序。8） 假定一组记录为（46,79,56,38,40,80）对其进行快速排序的第一次划分结果为 。9） 对任意7个关键字进行排序，至少要进行 次关键字之间的两两比较。10）算法的基本特征是可行性、确定性、_ _和拥有足够的情报。11）顺序存储方法是把逻辑上相邻的结点存储在物理位置_ _的存储单元中。12）数据的逻

16、辑结构在计算机存储空间中的存放形式称为数据的_ _ _。agdbcefhi13）栈的基本运算有三种：入栈、退栈和_ 。14）如图所示的二叉树，其中序遍历序列是 ；前序遍历序列是 ；后序遍历序列是 15）设一棵完全二叉树共有499个结点，则在该二叉树中有_ _个叶子结点。16）在最坏情况下，冒泡排序的时间复杂度为_ _ _。17）在最坏情况下，堆排序需要比较的次数为_ _。18）在计算机中，可以采用 结构来表示算术表达式。19）具有90个结点的完全二叉树的深度为 。20）对具有n个元素的任意序列进行排序，在最坏情况下，采用简单排序法时需要 次比较；采用希尔排序法进行排序时，时间复杂度为 ；采用简

17、单排序法进行排序时，需要比较 次；采用堆排序法进行排序时需要比较的次数为 。1） 算法的复杂度主要包括_ _复杂度和空间复杂度。2） 现有按中序遍历二叉树的结果为abc，那么有 种不同形态的二叉树可以得到这一遍历结果。3） 若要对1000个元素排序，要求即快又节省空间，则最好采用 方法。4） 在平均情况下速度最快的排序方法为 排序。5） 有关键码序列（16,9,4,25,15,2,13,18,17,5,8,24），要求按关键码递增顺序排序。采用冒泡排序法，则第二趟冒泡后的结果为 。6） 有关键码序列（16,9,4,25,15,2,13,18,17,5,8,24），要求按关键码递增顺序排序。采用

18、初始增量为4的希尔排序，则一趟扫描后的结果为 。7） 假定一组记录为（46,79,56,38,40,80）对其进行快速排序的过程中，共需要 趟排序。8） 假定一组记录为（46,79,56,38,40,80）对其进行快速排序的第一次划分结果为 。9） 对任意7个关键字进行排序，至少要进行 次关键字之间的两两比较。10）算法的基本特征是可行性、确定性、_ _和拥有足够的情报。11）顺序存储方法是把逻辑上相邻的结点存储在物理位置_ _的存储单元中。12）数据的逻辑结构在计算机存储空间中的存放形式称为数据的_ _ _。agdbcegfbhei13）栈的基本运算有三种：入栈、退栈和_ 。14）如图所示的二叉树，其中序遍历序列是 ；前序遍历序列是 ；后序遍历序列是 15）设一棵完全二叉树共有499个结点，则在该二叉树中有_ _个叶子结点。16）在最坏情况下，冒泡排序的时间复杂度为_ _ _。17）在最坏情况下，堆排序需要比较的次数