计算机二级数据结构与算法题库

1、数据结构与算法算法算法的复杂度主要包括时间复杂度和空间复杂度，算法的时间复杂度与空间复杂度没有直接尖系。算法的时间复杂度是指执行算法所需要的汁算工作量。循环队列是队列的顺序存储结构循环队列中的元素个数随队头指针与队尾指针变化而动态变化。线性表链式存储结构的存储空间可以是连续的，也可以是不连续的。6?有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构。在线性单链表中，可以从任何一个结点开始直接遍历到所有结点。循环队列是队列的顺序存储结构。在排序方法中，最坏情况下时间复杂度最小的是堆排序。为了对有序进行对分查找，则要求有序表只能顺序存储。X?带链的栈与队列是线性结构。 TOC o 1-

2、5 h z 算法的时间复杂度的度量方法是，执行算法所需要的基本运算次数：时间复杂度与所运用的计算工具无矢。在最坏情况下，希尔排序的时间复杂度比直接排序的时间复杂度要小。算法的空间复杂度的度疑方法是，执行算法所需要的存储空间：与算法所处理的数据存储空间有尖。有的非线性结构也可以采用顺序存储结构。算法的时间复杂度与算法所处理数据的存储结构有直接矢系：算法的空间复杂度与算法所处理数据的存储结构有直接矢系。具有两个根结点的数据结构一定是非线性结构。带链队列的存储空间可以不连续，但队头指针可以大于也可以小于队尾指针。?在链表中，如果有两个结点的同一指针域的值相等，泽该链表一泄是非线性结构。?在带链栈中，

3、队头指针和队尾指针都是在动态变化中；栈顶指针是在动态变化的，栈底指针是不变的。?链表结点中具有两个指针域的数据结构可以是线性结构的，也可以是非线性的。程序可以作为算法的一种描述方法。没有根结点或没有叶子结点的数据结构一泄是非线性结构。算法强调动态的执行过程，不同于静态的il?算公式：算法必须能衽有限个步骤之后终止：算法的优劣取决于算法复杂度，与程序的环境无尖：算法设计必须考虑算法的复杂度。线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有，插入与删除运算效率高。有序表可以用链接存储方式在不连续的存储空间内。带链的栈与顺序存储的栈相比，苴优点是，入栈操作是不会受栈存储空间的限制而发生溢

4、出。设序列长度为在最坏情况下比较次数低于O（n2）的排序方法是，希尔排序。29?设设序列长度为n,在最坏情况下，时间复杂度为O（log2n）的算法是，二分法查找。30?对长度为n的线性表排序，任最坏情况下，堆排序需要比较次数为0（nlog2n）0.在最坏情况下，二分查找法的时间复杂度为（Iog2n）?在线性表的链式存储结构中，其存储空间一般是不连续的，并且前件结点的存储序号可以小于也可以大于后件结点的存储序号。线性结构的存储结点也可以有多个指针。在线性表的顺序存储结构中，英存储空间连续，各个元素所占的字节数相同，元素的存储顺序与逻辑顺序一致。非空循环链表所表示的数据结构有根结点也有叶子结点。在

5、排序过程中，每一次数据元素的移动会产生新的逆序的排序方法是，快速排序。处理中与队列有尖的是，操作系统中的作业调度。38?二叉链表为非线性结构的数据结构。数据结构中的数据元素可以是另一数据结构；空数据结构可以是线性结构，也可以时非线性结构：非空数据结构可以没有根结点。为了降低算法的空间复杂度，要求算法尽量采用原地工作，所谓原地工作是指，执行算法时所使用的额外空间固压（即不随算法所处理的数据空间大小的变化而变化）。二分查找法只适用于顺序存储的有序线性表。42?设某二叉树的前序序列与中序序列均为ABCDEFGHRU该二叉树的后序序列为，HGFEDCBA.能从任意一个结点开始没有重复地扫描到所有结点的

6、数据结构是，循环链表。若某二叉树中的所有结点值均大于其左子树上的所有结点值，且小于右子树上的所有结点值，则该二叉树遍历序列中有序的是，中序序列。解决同一个问题的不同算法的时间复杂度一般是不同的。?在最坏的情况下，冒泡排序，快速排序，简单插入排序和简单选择排序需要比较的次数为n（n?l）2,希尔排序所需要的比较次数为（nl?5）.堆排序需要比较的次数为0（nlog2n）47有多个指针领域的链表有可能是线性结构。48?某二叉树的前历序列为ABCDE中序遍历序列为CBADE则后序遍历序列为CBEDA.算法的逻辑结构和存储结构都会影响算法的效率。某二叉树的中序遍历序列为CBADEf序遍历序列为CBED

7、A则前序遍历序列为，ABCD曰某二叉树的后序遍历序列与中序遍历序列相同，均为ABCDER1IJ遍历序列序列为FEDCBA遍历序列相同，则该二叉树的深度为（根结点在第1层），n.非线性结构可以为空。排序方法中，最坏情况下时间复杂度（即比较次数）最低的是，希尔排序。一个非空的数据结构满足以下条件：有且只有一个根结点每个结点最多有一个前件，也最多只有一个后件。则称该数据结构为线性结。5&最坏情况下，时间复杂度（即比较次数）低于O（n2）的是，堆排序。57.最坏情况下，时间复杂度最低的为，二分查找法。58?二分法只适用于顺序存储的线性有序表：有多个指针域的链表也有可能是线性结构：循环队列是队列的存储结

8、构。过程中是固左不变的：但顺序栈和带链栈的栈在操作过程中其栈顶指针军事动态变化的。排序二叉树的中序遍历序列是有序序列。多重链表可能是非线性结构也可能是线性结构。算法的时间复杂度与运算算法时特定的输入有矢。对于各种特建的输入，算法的时间复杂度是固定不变的。 TOC o 1-5 h z 在长度为n的顺序表中查找一个元素，假设需要查找的元素一泄在表中，并且元素出现在表中每个位宜上的可能性是相同的，则平均情况下需要比较的次数为（n+1）/2,64?设非空二叉树的所有子树中，其左子树的绩点值均小于根结点的值，而右子树的结点值均不小于根结点值，则称该二叉树为排序二叉树，对排序二叉树的遍历结果为有序序列的是

9、，中序序列。算法中均以比较作为基本运算，则平均情况与最坏情况下的时间复杂度相同的是，在顺序存储结构的线性表中寻找最大项。在具有2n个结点的完全二叉树中，叶子结点个数为n.在栈中，栈顶指针的动态变化决泄栈中元素的个数。在循环队列中，队头指针和队尾指针的动态变化决定队列的长度。69?顺序表的长度为最坏情况下比较次数等于n（n?l）/2的是，快速排序。最坏情况下比较次数小于n的是，二分查找法，寻找最大项。70?二叉链表是二叉树的存储结构；栈是线性结构：循环队列是队列的存储结构。.某二叉树的后序遍历序列与中序遍历序列相同均为ABCDEFM按层次输出（同一层从左到右）的序列为,FEDCBA?.某二叉树的

10、前序遍历序列与中序遍历序列相同均为ABCDEFM按层次输出（同一层从左到右）的序列为,ABCDEF?.对数据进行压缩存储会降低算法的空间复杂度。.每经过一次元素的交换会产生新的逆序的是，快速排序。.某完全二叉树按层次输出（同一层从左到右）的序列为ABCDEFGH完全二叉树的前序序列为，ABDHECFG.有的二叉树也能用顺序存储结构表示。.某二叉树的前序序列为ABDFHCEGf序序列为HFDBACEG二叉树按层次输出（同一层从左到右）的序列为，ABCDEFGH.某完全二叉树按层次输出（同一层从左到右）的序列为ABCDEFGH完全二叉树的中序序列为HDBEAFCG.解决一个问题可以有不同的算法，且

11、它们的时间复杂度可以是不同的。?设表的长度为在最坏情况下，比较次数最少的是，有序表的二分查找。?算法的时间复杂度与计算机系统无尖：其时间复杂度与空间复杂度没有必然的联系：算法的空间复杂度与算法运行输出结果的数据量无矢。82?设表的长度为20,则在最坏情况下，冒泡排序的比较次数为，1900若二叉树没有叶子结点，则为空二叉树。若带链队列中占有一个元素，则队头指针与队尾指针必泄相同。带链栈空的条件是，top二bottom二NULL.不能采用顺序存储结构的是，非完全二叉树。带链队列空的条件是，front=rear=NULL.循环队列是线性结构。具有两个以上叶子结点的数据结构一泄属于非线性结构；具有两个

12、根结点的数据结构一龙属于非线性结构；具有一个根结点且只有一个叶子结点的数据结构也可能是非线性结构。双向链表属于线性结构链式存储。91?循环链表中有一个表头结点，其表头指针与循环链表中最后一个结点的指针均指向表头结点；实现了空表与非空表运算的统一。92?二叉链表属于非线性结构。循环链表可以从表中任何一个结点位置出发就可以不重复地访问表中其他所有结点的链表。数组是长度固定的线性表。在快速排序法中，每经过一次数据交换（或移动）后，能消除多个逆序。95?线性表的长度为在最坏情况下，比较次数为n-1的算法是寻找最大项。96?向量是线性结构：非空线性结构中只有一个结点没有前件；非空线性结构中只有一个结点没

13、有后件。在希尔排序法中，每经过一次数据交换后，能消除多个逆序。所有的线性结构都可以采用顺序存储结构。设表的长度为最坏情况下时间复杂度最高的是，希尔排序。树是一种简单的非线性结构。设表的长度为最坏情况下时间复杂度最低的是，循环链表中寻找最大项。设二叉树的后序序列为DGHEBIJFCAf1序序列为DBGEHACIF则前序序歹U为ABDEGHCFIJ.算法的时间复杂是算法在执行过程中基本运算的次数。循环队列是对裂的一种顺序存储结构。 TOC o 1-5 h z 某完全二叉树有256个结点，则该二叉树的涉毒为9。?能顺序存储的数据结构可以是线性结构也可以是非线性结构。线性结构也能采用链式存储结构。线性

14、结构一定能采用顺序存储结构。107?链表可以是线性结构也可以是非线性结构。108-设二叉树有20个叶子结点，5个度为1的结点，则该二叉树中总的结点数为44.109?快速排序法适用于顺序存储结构的线性表。110?数二树的度为3,且有9个度为3的结点，5个度为2的结点，但没有度为2的结点。则该树总的结点数为33。在最坏情况下比较次数相同的是，冒泡排序与快速排序。设二叉树的中序序列为BCDA前序序列为ABCD则后序序列为DCBA树的度为3,且有9个度为3的结点，5个度为1的结点，但没有度为2的结点。则该树中的叶子结点数为，19.循环队列是队列的一种顺序存储结构，循环链表中至少有一个结点。M5.在下列

15、算法中最坏情况下，时间复杂度最低的是，有序表的对分查找。门6.树的度为3,且有9个度为3的结点，20个叶子结点，但没有度为1的结点。则该树总的结点数为30。设二叉树的中序序列为BCDA后序序列为DCBAJI用序序列为ABCD.线性链表可以有多个指针域。对长度为8的数进行快速排序，最多需要的比较次数为28.120?树的度为3,且有9个度为3的结点，20个叶子结点，但没有度为1的结点。则该数中度为2的结点树为1.设线性表的长度为12,最坏情况下冒泡排序需要的比较次数为66。树的度为3,共有29个结点，但没有度为1和2的结点，则该数中叶子结点树为，不可有这样的数。 TOC o 1-5 h z 数的度

16、为3,共有31个结点，但没有度为1和2的结点，则该树中度为3的结点数为10.某二叉树有49个度为2的结点，4个度为1的结点，30个叶子结点，则不可能有这样的二叉树。某二叉树有49个度为2的结点，4个度为1的结点则该二叉树共有203个结点。对长度为N的线性表排序，在最坏情况下，冒泡排序，快速排序，直接插入排序和简单选择排序需要比较的次数为n(n-l)/2,堆排序需要比较的次数O(nlog2n),希尔排序所需要的比较次数为。(nl.5).某二叉树的前序序列为ABDECFG中序序列为DBEAFCCRU后序序列为DEBFGCA在长度为n的顺序表中寻找最大项，需要比较的次数至少是n-1.二叉树都为非线性

17、结构。在循环队列中，当front=rear时，不能确泄是队列满还是队列空，那么元素个数即为空或者满。某二叉树的前序序列为DEBFGCA中序序列为DBEAFCG!U后序序列为ABDECFG.要在具有n个元素的有序顺序表中插入一个元素，插入后仍是有序顺序表，则在最坏情况下需要移动的元素个数是n.采用顺序存储的完全二叉树属于非线性结构。设某树的度为3,且度为3的结点数为4,度为1的结点数为9,没有度为2的结点。则该树中的叶子结点数为9?要在具有n个元素的有序顺序表中删除一个元素，删除后仍是有序顺序表，则在最坏情况下需要移动的元素个数为n-1设某树的度为3,且度为3的结点数为4,度为1的结点数为9,没有度为2的结点。则该树中总的结点数为22.某二叉树的前序序列为ABCDE用序序列为ABCDEF该二叉树的深度为(根结点为第1层)6-在长度为N的有序链表中进行查找，最坏情况下需要比较的次数为某二叉树的前序序列为ABCDE叩序序列为ABCDEF,U后序序列为FEDCBA设某树的度为3,且度为3的结点数为5,度为2的结点数为4,没有度为1的结点。则