数据结构与算法复习题

1、全国计算机等级考试(二级公共基础相关习题(1数据结构与算法一、选择题1.在计算机中,算法是指(CA.查询方法B.加工方法C.对解题方案的准确而完整的描述D.排序方法2.在下列选项中,哪个一个不是算法应该具有的基本特征(CA.确定性B.可行性C.无穷性D.拥有足够的情报3.算法一般都可以用哪几种控制结构组合而成(DA.循环、分支、递归B.顺序、循环、嵌套C.循环、递归、选择D.顺序、选择、循环4.算法的时间复杂度是指(CA.执行算法程序所需要的时间B.算法程序的长度C.算法执行过程中所需要的基本运算次数D.算法程序中的指令条数5.算法的空间复杂度是指(DA.算法程序的长度B.算法程序中的指令条数

2、C.算法程序所占的存储空间D.算法执行过程中所需要的存储空间6.算法分析的目的是(D注:书中没有总结,但要牢记A.找出数据结构的合理性B.找出算法中输入和输出之间的关系C.分析算法的易懂性和可靠性D.分析算法的效率以求改进7.数据的存储结构是指(DA.存储在外存中的数据B.数据所占的存储空间C.数据在计算机中的顺序存储D.数据的逻辑结构在计算机中的表示8.数据结构中,与所使用的计算机无关的是数据的(CA.存储结构B.物理结构C.逻辑结构D.物理和存储结构9.下列叙述正确的是(CA.算法的执行效率与数据的存储结构无关B.算法的空间复杂度是指算法程序中指令(或语句的条数C.算法的有穷性是指算法必须

3、能在执行有限个步骤之后终止D.以上三种描述都不对10.以下数据结构中不属于线性结构的是(CA.队列B.线性表C.二叉树D.栈11.在下面关于线性表的叙述中,选出正确的一项(DA.线性表的每一个元素都有一个直接前驱和直接后继B.线性表中至少要有一个元素C.线性表中的元素必须按递增或递减的顺序排列D.除第一个元素和最后一个元素外,每个元素都有一个直接前驱和直接后继12.下列对线性链表描述正确的是(AA.存储空间不一定连续,且各元素的存储顺序是任意的B.存储空间不一定连续,且前件元素一定存储在后件元素的前面C.存储空间必须连续,且前件元素一定存储在后件元素的前面D.存储空间必须连续,且各元素的存储顺

4、序是任意的13.下列对线性表叙述中,正确的一项是(CA.采用链式存储的线性表,必须占用一片连续的存储单元B.采用顺序存储的线性表,便于进行插入和删除操作C.采用链式存储的线性表,不必占用一片连续的存储单元D.链式和顺序存储的线性表,都便于进行插入和删除操作14.线性表的顺序存储结构和线性表的链式存储结构分别是(BA.顺序存取的存储结构、顺序存取的存储结构B.随机存取的存储结构、顺序存取的存储结构C.随机存取的存储结构、随机存取的存储结构D.任意存取的存储结构、任意存取的存储结构15.链表不具有的特点是(BA.不必事先估计存储空间B.可随机访问任一元素C.插入删除不需要移动元素D.所需空间与线性

5、表长度成正比16.用链表表示线性表的优点是(A注:因为不需要移动元素A.便于插入和删除操作B.数据元素的物理顺序与逻辑顺序相同C.花费的存储空间较顺序存储少D.便于随机存取17.线性表若采用链式存储结构时,要求内存中可用存储单元的地址(DA.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以18.下列关于栈的描述正确的是(CA.在栈中只能插入元素而不能删除元素B.在栈中只能删除元素而不能插入元素C.栈是特殊的线性表,只能在一端插入或删除元素。D.栈是特殊的线性表,只能在一端插入元素,而不能在一端删除元素19.下列关于栈的描述中错误的是(BA.栈是先进后出的线性表B.栈只

6、能顺序存储C.栈具有记忆作用D.对栈的插入与删除操作中,不需要改变栈底指针20.栈底至栈顶依次存放元素ABCD,在第5个元素E入栈前,栈中元素可以出栈,则出栈序列可能是(DA.ABCEDB.DBCEAC.CDABED.DCBEA21.栈通常采用的两种存储结构是(AA.顺序存储结构和链式存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构22.下列关于队列的叙述中正确的是(CA.在队列中只能插入元素B.在队列中只能删除数据C.队列是先进先出的线性表D.队列是先进后出的线性表23.一个队列的入队序列是1,2,3,4,则队列的输出序列是(BA.4,3,2,1B.1,2

7、,3,4C.1,4,3,2D.3,2,4,124.栈和队列的共同点是(CA.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点25.树最适合用来表示(CA.有序数组元素B.无序数组元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据26.树是结点的集合,它的根结点数目是(CA.有且只有1B.1或多于1C.0或1D.至少227.一棵二叉树第5层的结点数最多为(BA.8B.16C.32D.1528.设一棵二叉树中有3个叶子结点,有8个度为1的结点,则该二叉树中总的结点数为(B A.12B.13C.14D.1529.某二叉树结点的前序序列为EACBDGF,中序序列为

8、ABCDEFG。该二叉树结点的后序序列为(AA.BDCAFGEB.DBCFAGEC.DCEGFABD.DEGACFB30.已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是(AA.cedbaB.acbedC.decabD.deabc31.设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数为(BA.349B.350C.255D.35132.具有3个结点的二叉树有(DA.2种形态B.4种形态C.7种形态D.5种形态33.对长度为n的线性表进行顺序查找,在最坏的情况下所需要的比较次数为(CA.Log2nB.n/2C.nD.n+134.下列数据结构中,能用二分法

9、进行查找的是(AA.顺序存储的有序线性表B.线性链表C.二叉链表D.有序线性链表35.二分法查找适合用于存储结构为(A且按关键字排好序的线性表A.顺序存储B.链式存储C.顺序和链式存储D.索引存储36.对于长度为n的线性表,在最坏的情况下,下列各排序法所对应的比较次数中正确的是(DA.冒泡排序为n/2B.冒泡排序为nC.快速排序为nD.快速排序为n(n-1/237.希尔排序法属于哪一种类型的排序法(BA.交换类排序法B.插入类排序法C.选择类排序法D.建堆排序法二、填空题1.问题处理方案的正确而完整的描述称为_。答:算法2.算法复杂度主要包括时间复杂度和_复杂度。答:空间3.数据结构包括数据的

10、_结构和数据的存储结构。答:逻辑4.数据的逻辑结构在计算机存储空间中的存放形式称为数据的_。答:存储结构#物理结构5.数据的逻辑结构有线性结构和_两大类。答:非线性结构6.数据结构分为逻辑结构与存储结 构，线性链表属于_。 答：存储结构 7.数据结构分为逻辑结构和存储结 构，循环队列属于_结构。 答：存储 8.顺序存储方法是把逻辑上相邻的结 点存储在物理位置_的存储单元 中。 答：相邻 9.长度为 n 的顺序存储线性表中，当 在任何位置上插入一个元素概率都相 等时，插入一个元素所需移动元素的 平均个数为_。 答：n/2 10.栈的基本运算有三种：入栈、退栈 和_。 答：读栈顶元素 11.二叉树的遍历可以分为三种：前序 遍历、_