公共基础习题解析.docVIP

数据结构和算法 一、选择题 1、B（p1） 解析：算法的基本特征：确定性、有穷性、可行性、拥有足够的情报 2、C（p2） 解析：算法的时间复杂度指的是：算法执行过程中所需要的基本运算次数。 3、D（p3） 解析：算法的空间复杂度指的是：算法在执行过程中所需要的存储单位。包括三个部分：1、输入数据多占的存储空间。 2、程序本身占有的存储空间。 3、算法执行过程中所需要的额外的空间。 4、D 解析：时间复杂度和空间复杂度之间没有的关系。 5、A（P5） 解析：数据的存储结构指的是数据在计算机中的存放方式。面向计算机的，即是外存中的数据。 6、B（P5） 解析：采用不同的存储结构，其数据处理的效率是不同的。 7、D（p4-p5） 解析：一个逻辑数据结构可以有多种存储结构：链式、顺序、索引等存储，A答案错误。B答案数据的存储结构也可以是线性结构，如数组。C答案一个数据的逻辑结构可以有多种存储结构是正确的，但是采用不同的存储结构，其数据处理的效率是不同的。 8、C（P11） 解析：栈是线性的。栈既可以插入元素，也可以删除元素。但是只能在栈的一端插入和删除元素。D答案中说的是队列，队列是在一端插入数据，在另外一端删除数据。 9、B（P11）（9---13题所在页数为11） 解析：栈的特点：栈是一种先进后出合或者是后进先出的线性表。具有记忆功能。由于栈只能在一端插入和删除数据，所以在插入和删除操作中，不需要改变栈底的指针。栈也可以随机存储。 10、D 11、B 12、B 13、C 14、C（P12） 解析：队列是一种特殊的线性表，只能在一端插入元素，在另外一端删除元素。既可以插入数据，也可以删除数据。是一种先进先出的线性表。或者说是后进后出的线性表。 15、A 解析：由于栈是先进后出的线性表，队列是先进先出的线性表，所以根据它们陈虎队列的顺序，可以得知栈的容量为3.它们进入栈的顺序为a,紧接着是b,移走b,c 进入，d进入，移走d,移走d,e进入，f进入，移走f,移走e,移走a。 16、A（P8） 解析：链表存储数据结构的存储空间可以是不连续的，也可以是连续的，并且数据结点的存储顺序与数据元素之间的逻辑关系可以是不一致的。 17、D 解析：同16题 18、A 解析：栈和队列都是线性结构的，树不是线性结构的是非线性结构的，线性链表是线性结构的。（记住：出现线性的地方就是线性结构的） 19、C（p15） 解析：在满的二叉树中叶子结点的个数为：2k-1个，即：24=16个。 20、A 解析：做这个题目的时候先画出度为4的结点。接着画出度为3的结点，画出度为2的结点和度为1的结点最后来数叶子结点的个数即可。 21、B （P15） 解析：叶子结点即为度为0的结点，度为0的结点比度为2的结点多一个，所以度为2的结点的个数为2个，度为1的结点的个数为8，所以总的结点的个数为：3+8+2=13个。 22、A 解析：栈和队列都是线性的，所以B答案是错的，树都是非线性的，D答案出错。线性链表是线性表的链式存储结构，正确的。C答案：双向链表是线性的，C答案出错。 23、D 解析：出现线性的地方都是线性的，栈和队列都是线性的。二叉链表是非线性的。 24、C 解析：同19题 25、B（P17） 解析：前序遍历的顺序是：中 左 右 所以这根树的根节点A应该出现在第一个位置，所以A、C两个答案排除。所以遍历的结果为：ATBZXCYP答案为B 26、A（P17） 解析：中序遍历的顺序是：左 中 右 遍历这棵树的时候根节点不能出现在第一个位置，所以D答案是错误的。遍历的结果为： ACBDFEG ，答案为A。 27、D（P17） 解析：后序遍历的顺序是：右 中 左 后序遍历的时候最后遍历的是这根树的根节点，所以这棵树的最后的一个元素应该是A。所以答案为D 28、C（p19） 解析：顺序查找在最坏的情况下比较的次数为n次，平均比较次数为：（n+1）/2 29、A（p19） 解析：用二分法查找的必须满足的是顺序存储的有序线性表。非顺序的不可以。 30、A（p20） 解析：用二分法查找数据时，最坏的情况下，需要比较的次数为：log2n次。 31、B（p19） 解析：在有序的线性表中查找数据的时候，最坏的情况下，需要比较的次数为n次。所以该题为64. 32、D 解析：在最坏的情况下，冒泡法排序的时间复杂度是：n（n-1）/2,插入排序的时间复杂度为：n（n-1）/2。堆排序的时间复杂度为：nlog2n ,快速排序法的时间复杂度为n（n-1）/2.所以答案为D 33、D 解析：同上 34、A（p1） 解析：算法的有穷性是指：算法在经过有穷的步骤后结束。即在时间上是有限的。 35、D 解析：堆排序的时间复杂度是：：nlog2n 36、B（P11）