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

计算机二级考试真题1）

在下列选项中，哪个不是一个算法一般应该具有的基本特征 ______。（）A. 确定性 B.可行性 C.无穷性 D.拥有足够的情报2）下面叙述正确的是

______。（）算法的执行效率与数据的存储结构无关算法的空间复杂度是指算法程序中指令（或语句）的条数（指的是算法所占用的空间）算法的有穷性是指算法必须能在执行有限个步骤之后终止以上三种描述都不对3）

算法的空间复杂度是指______。（A. 算法程序的长度 B.C.算法程序所占的存储空间 D.

）算法程序中的指令条数算法执行过程中所需要的存储空间4）数据的存储结构是指______。（）A. 数据所占的存储空间量 B.数据的逻辑结构在计算机中的表示C.数据在计算机中的顺序存储方式 D.存储在外存中的数据5）算法一般都可以用哪几种控制结构组合而成 ______。（）A. 循环、分支、递归 B.顺序、循环、嵌套 C.循环、递归、选择

D.顺序、选择、循环6）

在计算机中，算法是指______。（A. 查询方法 B.加工方法

）C.解题方案的准确而完整的描述

D.排序方法7）8）

算法分析的目的是______。（）A. 找出数据结构的合理性C.分析算法的易懂性和可靠性n个顶点的强连通图的边数至少有

B.找出算法中输入和输出之间的关系D.分析算法的效率以求改进______。（）A. n-1

B.n(n-1)

C.n

D.n+19）

数据结构中，与所使用的计算机无关的是数据的

______。（ ）A. 存储结构 B.物理结构 C.逻辑结构10）串的长度是______。（）A. 串中不同字符的个数C.串中所含字符的个数且字符个数大于零

D.物理和存储结构B.串中不同字母的个数D.串中所含字符的个数11）下列叙述中，错误的是 ______（）数据的存储结构与数据处理的效率密切相关数据的存储结构与数据处理的效率无关数据的存储结构在计算机中所占的空间不一定是连续的一种数据的逻辑结构可以有多种存储结构12）下列叙述中正确的是______。（）A. 线性表是线性结构 B.栈与队列是非线性结构C.线性链表是非线性结构 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）以下数据结构中不属于线性数据结构的是 ______。（）A. 队列 B.线性表 C.二叉树 D.栈17）在单链表中，增加头结点的目的是 ______。（）A. 方便运算的实现C.标识表结点中首结点的位置

B.使单链表至少有一个结点D.说明单链表是线性表的链式存储实现18）用链表表示线性表的优点是A. 便于插入和删除操作

______。（）B.数据元素的物理顺序与逻辑顺序相同C.花费的存储空间较顺序存储少 D.便于随机存取19）线性表L=(a1,a2,a3, ⋯ai,，⋯下an)列说法正确的是______（）每个元素都有一个直接前件和直接后件线性表中至少要有一个元素表中诸元素的排列顺序必须是由小到大或由大到小除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件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，则可能的出栈序列是______（）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;C. s->next=HS;HS=s;

B.D.

s->next=HS->next;HS->next=s;s->next=HS;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）为了减少栈溢出的可能性，可以让两个栈共享一片连续存储空间， 两个栈的栈底分别设在这片空间的两端，这样只有当 ______时才可能产生上溢。（）两个栈的栈顶在栈空间的某一位置相遇其中一个栈的栈顶到达栈空间的中心点两个栈的栈顶同时到达栈空间的中心点两个栈均不空，且一个栈的栈顶到边另一栈的栈底28）下列关于栈的叙述中正确的是 ______。（）A. 在栈中只能插入数据 B.在栈中只能删除数据C.栈是先进先出的线性表29）下列关于队列的叙述中正确的是A. 在队列中只能插入数据C.队列是先进先出的线性表

D.栈是先进后出的线性表______。（）B.在队列中只能删除数据D.队列是先进后出的线性表30）栈和队列的共同点是______。（A. 都是先进后出C.只允许在端点处插入和删除元素

）

B.都是先进先出D.没有共同点31）对线性表，下列情况下应当采用链表表示的是

______（）A.经常需要随机地存取元素 B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间 D.表中元素个数不变32）在一个链式队列中，假设 f和r分别为队头与队尾指针，则删除结点的运算是______（）A. r=f->next B. r=r->next C. f=f->next D. f=r->next33）设一棵完全二叉树共有 699个结点，则在该二叉树中的叶子结点数为 ______。（）A.349 C.255 D.35134）若某二叉树的前序遍历访问顺序是 abdgcefh，中序遍历访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是 ______（）A. bdgcefha B.gdbecfha C.bdgaechf D.gdbehfca35）设树T的度为4，其中度为1,2,3,4的结点个数分别为 4,2,1,1。则T中的叶子结点数为______（）A. 8 B.7 C.6 D.536）树最适合用来表示______（）A.有序数据元素 B.无序数据元素C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据37）某二叉树的先序和后序遍历顺序正好相反，则该二叉树一定是 ______（）A. 空或只有一个结点 B. 完全二叉树 C. 二叉排序树 D.深度等于其结点数38）设n，m为一棵二叉树上的两个结点，在中序遍历中，______（）A. n在m右子树上 B．n是m的祖先C. n在m左子树上 D. n是m的子孙39）如图所示二叉树的中序遍历序列是 ______（）A. abcdgef B. dfebagcC. dbaefcg D. abcdefg

n在m之前的条件是acd40）树是结点的集合，它的根结点数目是______（）fA.有且只有1B.1或多于1C.0或1D.至少241）在一棵二叉树上第5层的结点数最多是______。（）A.8B.16C.32D.1542）对长度为 N的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。（）A. N+1

B.N

C.(N+1)/2

D.N/243）顺序查找适合于存储结构为

______的线性表（ ）A. 散列存储

B.顺序存储或链式存储

C.压缩存储

D.索引存储44）采用顺序法查找长度为

n的线性表时，每个元素的平均查找长度为

______（）A. n

B.n/2

C.(n+1)/2

D.(n-1)/245）希尔排序法属于哪一种类型的排序法 ______。（）A. 交换类排序法 B.插入类排序法 C.选择类排序法

D.建堆排序法46）在待排序的元素序列基本有序的前提下， 效率最高的排序方法是______（）A. 冒泡排序 B.选择排序 C.快速排序 D.归并排序47）设有1000个元素，希望用最快的速度选出其中前 10个最大的元素，最好选用______排序法。（）A. 冒泡

B. 快速

C. 堆

D. 选择48）在下列排序法中，______算法可能出现下列情况：在最后一趟开始之间，所有的元素都不在其最终位置上。（ ）A. 冒泡 B. 快速 C. 插入 D. 堆49）在下列几种排序方法中，要求内存量最大的是 ______。（）A. 插入排序 B.选择排序 C.快速排序 D.归并排序50）已知数据表A中每个元素距其最终位置不远， 为节省时间，应采用的算法是______。（）A. 堆排序

B.直接插入排序

C.快速排序

D.直接选择排序填空题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），要求按关键码递增顺序排序。采用初始增量为4的希尔排序，则一趟扫描后的结果为 。7）假定一组记录为（46,79,56,38,40,80）对其进行快速排序的过程中，共需要趟排序。8）假定一组记录为（46,79,56,38,40,80）对其进行快速排序的第一次划分结果为 。9）对任意7个关键字进行排序，至少要进行10）算法的基本特征是可行性、确定性、 __11）顺序存储方法是把逻辑上相邻的结点存储在物理位置____的存储单元中。12）数据的逻辑结构在计算机存储空间中的存放形式称为数据的______。13）栈的基本运算有三种：入栈、退栈和__。a14）如图所示的二叉树，其中序遍历序列是；c前序遍历序列是；后序遍历序列是bdef15）设一棵完全二叉树共有499个结点，则在该二叉树中有___个叶子结点。gh16）在最坏情况下，冒泡排序的时间复杂度为______。i17）在最坏情况下，堆排序需要比较的次数为____。18）在计算机中，可以采用结构来表示算术表达式。19）具有90个结点的完全二叉树的深度为。20）对具有n个元素的任意序列进行排序，在最坏情况下，采用简单排序法时需要次比较；采用希尔排序法进行排序时，时间复杂度为；采用简单排序法进行排序时，需要比较次；采用堆排序法进行排序时需要比较的次数为。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），要求按关键码递增顺序排序。采用初始增量为4的希尔排序，则一趟扫描后的结果为 。7）假定一组记录为（46,79,56,38,40,80）对其进行快速排序的过程中，共需要趟排序。8）假定一组记录为（46,79,56,38,40,80）对其进行快速排序的第一次划分结果为。9）对任意7个关键字进行排序，至少要进行次关键字之间的两两比较。10）算法的基本特征是可行性、确定性、____和拥有足够的情报。11）顺序存储方法是把逻辑上相邻的结点存储在物理位置____的存储单元中。12）数据的逻辑结构在计算机存储空间中的存放形式称为数据的______。13）栈的基本运算有三种：入栈、退栈和__。a14）如图所示的二叉树，其中序遍历