国家二级C语言(数据结构与算法)机试模拟试卷1(题后含答案及解析)题型有:1. 选择题选择题1.算法具有五个特性,以下选项中不属于算法特性的是A.有穷性B.简洁性C.可行性D.确定性正确答案:B解析:算法的五个特性分别是:有穷性、可行性、确定性、输入和输出。
知识模块:数据结构与算法2.算法的有穷性是指A.算法程序的运行时间是有限的B.算法程序所处理的数据量是有限的C.算法程序的长度是有限的D.算法只能被有限的用户使用正确答案:A解析:算法的有穷性,是指算法必须能在有限的时间内做完,即算法必须能在执行有限个步骤之后终止。
知识模块:数据结构与算法3.算法的时间复杂度是指A.算法的执行时间B.算法所处理的数据最C.算法程序中的语句或指令条数D.算法在执行过程中所需要的基本运算次数正确答案:D解析:算法的时间复杂度,是指执行算法所需要的计算工作量。
算法的工作量可以用算法在执行过程中所需基本运算的执行次数来度量。
知识模块:数据结构与算法4.对存储器按字节进行编址,若某存储器芯片共有10根地址线,则该仔储器芯片的存储容量为A.1kbB.2kbC.4kbD.8kb正确答案:A解析:10根地址线,每根地址线有0和1两种情况,地址范围就是2的10次方=1024=1K。
知识模块:数据结构与算法5.磁盘处于写保护状态时其中的数据A.不能读出,不能删改B.可以读出,不能删改C.不能读出,可以删改D.可以读出,可以删改正确答案:B解析:磁盘处于写保护状态时其中的数据可以读出来,但是不能修改和删除。
知识模块:数据结构与算法6.在Windows环境下,单击当前窗口中的按钮“”,其功能是A.讲当前应用程序转为后台运行B.退Windows后再关机C.终止当前应用程序的运行D.退出Windows后重新启动计算机正确答案:C解析:在Windows中,单击窗口中的按钮“”表示关闭当前运行的程序。
知识模块:数据结构与算法7.下列描述中正确的是A.数据的逻辑结构与存储结构必定是一一对应的B.由于计算机存储空间是向量式的存储结构,因此,数据的存储结构一定是线性结构C.程序设计语言中的数据一般是顺序存储结构,因此,利用数组只能处理线性结构D.以上三种说法都不对正确答案:D解析:数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。
一般来说,一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接、索引等。
知识模块:数据结构与算法8.下列描述中正确的足A.线性链表是线性表的链式存储结构B.栈与队列是非线性结构C.双向链表是非线性结构D.只有根结点的二叉树是线性结构正确答案:A解析:线性表的链式存储结构称为线性链表。
线性表链式存储结构的基本单位称为存储结点,每个存储结点包括数据域和指针域两个组成部分。
各数据元素之间的前后件关系是由各结点的指针域来指示的,指向线性表中第一结点的指针HEAD称为头指针,当HEAD-NULL时称为空表。
栈、队列和双向链表是线性结构,树是一种简单的非线性结构。
在树这种数据结构中。
所有数据元素的关系具有明显的层次特征。
二叉树是非线性结构。
线性结构和非线性结构是从数据的逻辑结构角度来讲的,与该数据结构中有多少个元素没有关系,即使是空的二叉树也是非线性结构。
知识模块:数据结构与算法9.支持予程序调用的数据结构是A.栈B.树C.队列D.二叉树正确答案:A解析:栈是一种限定在一端进行插入与删除的线性表。
在主函数调用子函数时,要首先保存主函数当前的状态,然后转去执行子函数,把子函数的运行结果返回到主函数调用子函数时的位置,主函数再接着往下执行,这种过程符合栈的特点。
所以一般采用栈式存储方式。
知识模块:数据结构与算法10.下列关于栈的叙述中,正确的是A.栈底元素一定足最后入栈的元素B.栈顶元素一定是最先入栈的元素C.栈操作遵循先进后出的原则D.以上三种说法都不对正确答案:C解析:栈是限定只能在表的一端进行插入和删除操作的线性表,必须按“后进先出”的规则操作元素。
知识模块:数据结构与算法11.一个栈的初始状态为空。
现将元素1,2,3,A,B,C依次入栈,然后再依次出栈,则元素出栈的顺序是A.1,2,3,A,B,CB.C,B,A,1,2,3C.C,B,A,3,2,1D.1,2,3,C,B,A正确答案:C解析:栈是按照“先进后出”或“后进先出”的原则组织数据的。
所以出栈顺序是CBA321。
知识模块:数据结构与算法12.下列对队列的描述中正确的是A.队列属于非线性表B.队列按“先进后出”原则组织数据C.队列在队尾删除数据D.队列按“先进先出”原则组织数据正确答案:D解析:队列(queue)是指允许在一端进行插入、而在另一端进行删除的线性表。
允许插入的一端称为队尾;允许删除的一端称为队头。
在队列这种数据结构中,最先插入的元素将最先能够被删除;反之,最后插入的元素将最后才能被删除。
因此,队列又称“先进先出”或“后进后出”的线性表。
知识模块:数据结构与算法13.下列关于栈的描述中正确的是A.在栈中只能插入元素而不能删除元素B.在栈中只能删除元素而不能插入元素C.栈是特殊的线性表,只能在一端插入或删除元素D.栈是特殊的线性表,只能在一端插入元素,而在另一端删除元素正确答案:C解析:栈是限定在一端进行插入与删除的线性表,在栈中。
允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。
知识模块:数据结构与算法14.下列叙述中正确的是A.循环队列是队列的一种链式存储结构B.循环队列是队列的一种顺序存储结构C.循环队列是非线性结构D.循环队列是一种逻辑结构正确答案:B解析:本题主要考查循环队列的概念.循环队列作为队列的一种也应该是线性结构。
队列是一种逻辑结构,而循环队列是一种顺序存储结构的队列。
知识模块:数据结构与算法15.下列叙述中正确的是A.栈是一种先进先出的线性表B.队列是一种后进先出的线性表C.栈与队列都是非线性结构D.栈与队列都是线性结构正确答案:D解析:栈是先进后出.队列是先进先出。
栈和队列都是一种线性表,属于线性结构。
知识模块:数据结构与算法16.下列叙述中正确的是A.循环队列中的元素个数随队头指针与队尾指针的变化而动态变化B.循环队列中的元素个数随队头指针的变化而动态变化C.循环队列中的元素个数随队尾指针的变化而动态变化D.循环队列中的元素个数不会变化正确答案:A解析:所谓循环结构就是将队列存储空间的最后一个位置绕到第一个位置上,形成逻辑上的环状空间,循环使用。
在循环队列中,用队尾指针rcar指向队列中的队尾元素,用队头指针front指向队头元素的前一个位置,因此,队列中的元素之间的元素数量。
知识模块:数据结构与算法17.下列叙述中正确的是A.线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B.线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C.线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D.上述三种说法都不对正确答案:B解析:线性表的存储分为顺序存储和链式存储。
在顺序存储中,所有元素所占的存储空间是连续的,各数据元素在存储空间中是按逻辑顺序依次存放的。
所以每个元素只存储其值就可以了,而在链式存储的方式中,将存储空间的每一个存储结点分为两部分,一部分用于存储数据元素的值,称为数据域;另一部分用于存储下一个元素的存储序号,称为指针域。
所以线性表的链式存储方式比顺序存储方式的存储空间要大一些。
知识模块:数据结构与算法18.下列链表中,其逻辑结构属于非线性结构的是A.二叉链表B.循环链表C.双向链表D.带链的栈正确答案:A解析:二叉链表作为树的存储结构。
链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。
知识模块:数据结构与算法19.某系统总体结构图如下图所示。
该系统总体结构图的深度是A.7B.6C.3D.2正确答案:C解析:这个系统总体结构图是一棵树结构,在树结构中,根结点在第1层,同一层上所有子结点都在下一层,由系统总体结构图可知,这棵树共3层。
在树结构中,树的最大层次称为树的深度。
所以这棵树的深度为3。
知识模块:数据结构与算法20.某二叉树有5个度为2的结点,则该二叉树中的叶子结点数足A.10B.8C.6D.4正确答案:C解析:根据二叉树的性质,在任意二叉树中,度为0的结点(即叶子结点)总是比度为2的结点多一个。
知识模块:数据结构与算法21.一颗二叉树中共有70个叶子结点与80个度为1的结点,则该二义树中的总结点数为A.219B.221C.229D.231正确答案:A解析:在二叉树中,叶子结点个数为n 0 ,则度为2的结点数n 2 =n 0 -1。
本题中叶子结点的个数为70,所以度为2的结点个数为69,因而总结点数=叶子结点数+度为1的结点数+度为2的结点数=70+80+69=219。
知识模块:数据结构与算法22.设树T的深度为4,其中度为1,2,3,4的结点个数分别为4,2,1,1。
则T中的叶了结点数为A.8B.7C.6D.5正确答案:B解析:深度为m二叉树其总结点数为2 m -1=2 4 -1=15。
总结点数减去度为1,2,3,4的结点个数就是叶子结点数。
15-4-2-1-1=7。
知识模块:数据结构与算法23.对下列二叉树进行前序遍历的结果是A.DYBEAFCZXB.YDEBFZXCAC.ABDYECFXZD.ABCDEFXYZ正确答案:C解析:二叉树前序遍历的简单描述:若二叉树为空,则结束返回;否则:①访问根结点;②前序遍历左子树;③前序遍历右子树。
可见,前序遍历二叉树的过程是一个递归的过程。
根据题目中给出的二叉树的结构可知前序遍历的结果是ABDYECFXZ。
知识模块:数据结构与算法24.在长度为64的仃序线性表中进行顺序查找,最坏情况下需要比较的次数为A.63B.64C.6D.7正确答案:B解析:顺序查找又称顺序搜索。
顺序查找一般是指在线性表中查找指定的元素,其基本方法是:从线性表的第一元素开始,依次将线性表中的元素与被查找的元素进行比较,若相等则表示找到(即查找成功),若线性表中所有元素都与被查元素进行了比较但都不相等,则表示线性表中没有要找的元素(即查找失败)。
如果线性表中的第一个元素就是要查找的元素,则只需要做一次比较就查找成功;但如果要查找的元素是线性表中的最后一个元素,或者要查找元素不在线性表中,则需要与线性表中所有元素进行比较,这是顺序查找的最坏情况,比较次数为线性表的长度。
知识模块:数据结构与算法25.下列数据结构中,能用二分法进行查找的是A.顺序存储的有序线性表B.线性链表C.二叉链表D.有序线性链表正确答案:A解析:二分法查找只适应于顺序存储的有序表。