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

《计算机二级考试真题及答案.doc》由会员分享，可在线阅读，更多相关《计算机二级考试真题及答案.doc（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date计算机二级考试真题及答案计算机二级考试真题及答案计算机二级考试真题1） 在下列选项中，哪个不是一个算法一般应该具有的基本特征_。（ ）A. 确定性B. 可行性C. 无穷性D. 拥有足够的情报2） 下面叙述正确的是_。（ ）A. 算法的执行效率与数据的存储结构无关B. 算法的空间复杂度是指算法程序中指令（或语句）的条数（指的是算法所占用的空间）C. 算法的有穷性是指算法

2、必须能在执行有限个步骤之后终止D. 以上三种描述都不对3） 算法的空间复杂度是指_。（ ）A. 算法程序的长度 B. 算法程序中的指令条数C. 算法程序所占的存储空间 D. 算法执行过程中所需要的存储空间4） 数据的存储结构是指_。（ ）A. 数据所占的存储空间量 B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式 D. 存储在外存中的数据5） 算法一般都可以用哪几种控制结构组合而成_。（ ）A. 循环、分支、递归 B. 顺序、循环、嵌套 C. 循环、递归、选择 D. 顺序、选择、循环6） 在计算机中，算法是指_。（ ）A. 查询方法B. 加工方法 C. 解题方案的准确而完

3、整的描述 D. 排序方法7） 算法分析的目的是_。（ ）A. 找出数据结构的合理性 B. 找出算法中输入和输出之间的关系C. 分析算法的易懂性和可靠性 D. 分析算法的效率以求改进8） n个顶点的强连通图的边数至少有_。（ ）A. n-1 B. n(n-1) C. n D. n+19） 数据结构中，与所使用的计算机无关的是数据的_。（ ）A. 存储结构 B. 物理结构 C. 逻辑结构 D. 物理和存储结构10）串的长度是_ 。（ ）A. 串中不同字符的个数 B. 串中不同字母的个数C. 串中所含字符的个数且字符个数大于零 D. 串中所含字符的个数11）下列叙述中，错误的是_ （ ）A. 数据的

4、存储结构与数据处理的效率密切相关 B. 数据的存储结构与数据处理的效率无关 C. 数据的存储结构在计算机中所占的空间不一定是连续的D. 一种数据的逻辑结构可以有多种存储结构12）下列叙述中正确的是_。（ ）A. 线性表是线性结构 B. 栈与队列是非线性结构C. 线性链表是非线性结构 D. 二叉树是线性结构13）栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是_。（ ）A. ABCED B. DBCEA C. CDABE D. DCBEA14）下列叙述中正确的是_。（ ）A. 线性表是线性结构 B.栈与队列是非线性结构C. 线性链表是非线性结构 D.

5、 二叉树是线性结构15）线性表的顺序存储结构和线性表的链式存储结构分别是_。（ ） A. 顺序存取的存储结构、顺序存取的存储结构 B. 随机存取的存储结构、顺序存取的存储结构 C. 随机存取的存储结构、随机存取的存储结构 D. 任意存取的存储结构、任意存取的存储结构16）以下数据结构中不属于线性数据结构的是_。（ ）A. 队列 B. 线性表 C. 二叉树 D. 栈17）在单链表中，增加头结点的目的是_。（ ）A. 方便运算的实现 B. 使单链表至少有一个结点C. 标识表结点中首结点的位置 D. 说明单链表是线性表的链式存储实现18）用链表表示线性表的优点是_。（ ）A. 便于插入和删除操作B.

6、 数据元素的物理顺序与逻辑顺序相同C. 花费的存储空间较顺序存储少D. 便于随机存取19）线性表L=(a1,a2,a3,ai,an)，下列说法正确的是_ （ ）A. 每个元素都有一个直接前件和直接后件 B. 线性表中至少要有一个元素C. 表中诸元素的排列顺序必须是由小到大或由大到小 D. 除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件20）非空的循环单链表head的尾结点(由p所指向)，满足_ （ ）A. p-next=NULL B. p=NULL C. p-next=head D. p=head21）栈和队列的共同点是_。（ ）A. 都是先进后出B. 都是先进

7、先出 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(1inext=s ; B. s-next= HS-next ; HS-next=s;C. s-next= HS;

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

9、在栈中只能插入数据 B. 在栈中只能删除数据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）如图所示

19、的二叉树，其中序遍历序列是 ；前序遍历序列是 ；后序遍历序列是 15）设一棵完全二叉树共有499个结点，则在该二叉树中有_ _个叶子结点。16）在最坏情况下，冒泡排序的时间复杂度为_ _ _。17）在最坏情况下，堆排序需要比较的次数为_ _。18）在计算机中，可以采用 结构来表示算术表达式。19）具有90个结点的完全二叉树的深度为 。20）对具有n个元素的任意序列进行排序，在最坏情况下，采用简单排序法时需要 次比较；采用希尔排序法进行排序时，时间复杂度为 ；采用简单排序法进行排序时，需要比较 次；采用堆排序法进行排序时需要比较的次数为 。1-5 CCDBD 6-10 CDCCD 11-15 B

20、ADAB 16-20 CAADC 21-25 CCBCC26-30 CADCC 31-35 BCBDA 36-40 CDCBA 41-45 BBBCB 46-50 ACCDB1) 时间2) 5 3) 堆排序 4) 快速5) 4,9,15,2,13,16,17,5,8,18,24,256) 15,2,4,18,16,5,8,24,17,9,13,257) 38) 40,38,46,56,79,809) 15 题解： log2(n!)= log2(7!)10) 有穷性11) 相邻12) 模式（逻辑模式）（概念模式）13) 读栈顶元素14) dgbaechif , abdgcefhi , gdbeihfca 15) 250_16) n(n-1)/2或O(n(n-1)/2)17) O(nlog2n)18) 树型19) 720) n(n-1)/2, O(n1.5), n(n-1)/2, O(nlog2n)-