计算机二级公共基础知识题库及答案分析

全国计算机等级考试二级公共基础知识考题库第一章 数据结构一、选择题（1）下列数据结构中，能用二分法进行查找的是A）顺序存储的有序线性表 B）线性链表C）二叉链表 D）有序线性链表【答案】A【解析】二分查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列（即从小到大.但允许相邻元素值相等）的。选项A正确。（2）下列关于栈的描述正确的是A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素【答案】C【解析】栈是一种特殊的线性表，其插入与删除运算都只在线性表的一端进行。由此可见，选项A、选项B和选项D错误，正确答案是选项Co（3）下列叙述中正确的是A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率【答案】D【解析】一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。由此可见，选项D的说法正确。（4）算法执行过程中所需要的存储空间称为算法的A）时间复杂度B）计算工作量C）空间复杂度D）工作空间【答案】C【解析】算法执行时所需要的存储空间，包括算法程序所占的空间、输入的初始数据 所占的存储空间以及算法执行过程中所需要的额外空间，其中额外空间还包括算法程序执行过程的工作单元以及某种数据结构所需要的附加存储空间。这些存储空间共称为算法的空间复杂度。（5）下列关于队列的叙述中正确的是A）在队列中只能插入数据B）在队列中只能删除数据C）队列是先进先出的线性表D）队列是先进后出的线性表【答案】C【解析】对队列可以进行插入和删除数据的操作，只是插入数据只能在队尾，删除数据只能在队头。所以队列是先进先出的线性表。（6）设有下列二叉树:对此二叉树后序遍历的结果为A)ABCDEFB)BDAECFC)ABDCEFD)DBEFCA【答案】D【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求后序遍历。其遍历顺序应该为：后序遍历左子树一》后序遍历右子树一》访问根结点。按照定义，后序通历序列是DBEFCA,故答案为Do（7）下列叙述中正确的是（）A）程序执行的效率与数据的存储结构密切相关B）程序执行的效率只取决于程序的控制结构0程序执行的效率只取决于所处理的数据量D）以上三种说法都不对【答案】A【解析】本题考查程序效率。程序效率是指程序运行速度和程序占用的存储空间。影响程序效率的因素是多方面的，包括程序的设计、使用的算法、数据的存储结构等。在确定数据逻辑结构的基础上，选择一种合适的存储结构，可以使得数据操作所花费的时间少，占用的存储空间少，即提高程序的效率。因此，本题选项A的说法是正确的。（8）下列叙述中正确的是（）A）数据的逻辑结构与存储结构必定是一一对应的B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构。程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线线结构D）以上三种说法都不对【答案】D【解析】本题考查数据结构的基本知识。数据之间的相互关系称为逻辑结构。通常分为四类基本逻辑结构，即集合、线性结构、树型结构、图状结构或网状结构。存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。存储结构在计算机中有两种，即顺序存储结构和卷式存储结构。顺序存储结构是把数据元素存储在一块连续地址空间的内存中；钱式存储结构是使用指针把相互直接关联的节点链接起来。因此，这两种存储结构都是线性的。可见，逻辑结构和存储结构不是一一对应的。因此，选项A和选项B的说法都是错误的。无论数据的逻辑结构是线性的还是非线性的，只能选择顺序存储结构或链式存储结构来实现存储。程序设计语言中，数组是内存中一段连续的地址空间，可看作是顺序存储结构。可以用数组来实现树型逻辑结构的存储，比如二叉树。因此，选项c的说法是错误的（9）冒泡排序在最坏情况下的比较次数是（）A)n(n+l)/2B)n1ogznC)n(n-l)/2D)n/2【答案】C【解析】冒泡排序的基本思想是：将相邻的两个元素进行比较，如果反序，则交换；对于一个待排序的序列，经一趟排序后，最大值的元素移动到最后的位置，其他值较大的元素也向最终位置移动，此过程称为一趟冒泡。对于有n个数据的序列，共需n-1趟排序，第i趟对从I到n-i个数据进行比较、交换。冒泡排序的最坏情况是待排序序列逆序，第I趟比较n-1次，第2趟比较n-2次。依此类推，最后趟比较1次，一共进行n-l趟排序。因此，冒泡排序在最坏情况下的比较次数是(n-1)+(n-2)+…+I,结果为n(n-1)/2o本题的正确答案是选项Co(10)一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为()A)219 B)221 C)229 D)231【答案】A【解析】本题考查数据结构中二叉树的性质。二叉树满足如下一条性质，即：对任意一棵二叉树，若终端结点(即叶子结点)数为no,而其度数为2的结点数为n2,则n0=n2+lo根据这条性质可知，若二叉树中有70个叶子结点，则其度为2的结点数为70-1，即69个。二叉树的总结点数是度为2、度为1和叶子结点的总和，因此，题目中的二叉树总结点数为69+80+70,即219。因此，本题的正确答案是选项A。(11)下列叙述中正确的是()A)算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需耍的计算工作量0数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关【答案】B【解析】本题考查数据结构中有关算法的基本知识和概念。数据的结构，直接影响算法的选择和效率。而数据结构包括两方面，即数据的逻辑结构和数据的存储结构。因此，数据的逻辑结构和存储结构都影响算法的效率。选项A的说法是错误的。算法的时间复杂度是指算法在计算机内执行时所需时间的度曜；与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。因此，选项B的说法是正确的。数据之间的相互关系称为逻辑结构。通常分为四类基本逻辑结构，即集合、线性结构、树型结构、图状结构或网状结构。存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。存储结构在计算机中有两种，即顺序存储结构和链式存储结构。可见，逻辑结构和存储结构不是一一对应的。因此，选项c的说法是错误的。有时人们为了提高算法的时间复杂度，而以牺牲空间复杂度为代价。但是，这两者之间没有必然的联系。因此，选项D的说法是错误的。（12）卜.列关于算法的时间复杂度陈述正确的是A）算法的时间复杂度是指执行算法程序所需要的时间B）算法的时间复杂度是指算法程序的长度C）算法的时间复杂度是指算法执行过程中所需要的基本运算次数D）算法的时间复杂度是指算法程序中的指令条数【答案】C【解析】算法的时间复杂度是指执行算法所需要的计算工作=，也就是算法在执行过程中所执行的基本运算的次数，而不是指程序运行需要的时间或是程序的长度。（13）下列关于栈的叙述中正确的是A）在栈中只能插入数据B）在栈中只能删除数据C）栈是先进先出的线性表D）栈是先进后出的线性表【答案】D【解析】对栈可进行插入和删除数据的操作，但必须牢记插入和删除数据都只能是在栈顶，是一种特殊的线性表。所以栈是先进后出的线性表。（14）设有下列二叉树：FFF对此二叉树中序遍历的结果为A)ABCDEFB)DAECFC)BDAECFD)DBEFCA【答案】C【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求中序遍历，其遍历顺序应该为：中序遍历左子树，访问根结点，中序遍历右子树。按照定义，中序通历序列是BDAECF,故答案为Bo(15)按照“后进先出”原则组织数据的数据结构是A)队列 B)栈C)双向链表 D)二叉树【答案】B【解析】“后进先出”表示最后被插入的元素最先能被删除。选项A中，队列是指允许在一端进行插入、而在另一端进行删除的线性表，在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除，队列又称为“先进先出”的线性表，它体现了“先来先服务”的原则：选项B中，栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素，栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。队列和栈都属于线性表，它们具有顺序存储的特点，所以才有“先进先出”和“后进先出”的数据组织方式。双向链表使用链式存储方式.二叉树也通常采用链式存储方式，它们的存储数据的空间可以是不连续的，各个数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。所以选项C和选项D错。(16)下列叙述中正确的是A)线性链表是线性表的链式存储结构B)栈与队列是非线性结构C)双向链表是非线性结构D)只有根结点的二叉树是线性结构【答案】A【解析】一个非空的数据结构如果满足下列两个条件：(1)有且只有一个根结点;(2)每一个结点最多有一个前件，也最多有一个后件。则称为线性结构。线性链表是线性表的链式存储结构，选项A的说法是正确的。栈与队列是特殊的线性表，它们也是线性结构，选项B的说法是错误的；双向链表是线性表的链式存储结构，其对应的逻辑结构也是线性结构，而不是非线性结构，选项c的说法是错误的；二叉树是非线性结构，而不是线性结构，选项D的说法是错误的。因此，本题的正确答案为A(17)对如下二叉树进行后序遍历的结果为A)ABCDEF B)DBEAFCC)ABDECF D)DEBFCA【答案】D【解析】二叉树后序遍历的简单描述如下：若二叉树为空，则结束返回。否则(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。也就是说，后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先通历左子树，然后遍历右子树，最后访问根结点。根据后序遍历的算法，后序遍历的结果为DEBFCAo(18)下列对队列的叙述正确的是()A)队列属于非线性表B)队列按“先进后出”原则组织数据C)队列在队尾删除数据D)队列按“先进先出”原则组织数据【答案】D【解析】本题考查数据结构中队列的基本知识。队列是一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出的特性。在队列中，允许插入元素的一端叫做队尾，允许删除的一端则称为队头。这与日常生活中的排队是一致的，最早进入队列的人最早离开，新来的人总是加入到队尾。因此，本题中只有选项D的说法是正确的。(19)对下列二叉树进行前序遍历的结果为()A)DYBEAFCZXB)YDEBFZXCAC)ABDYECFXZD)ABCDEFXYZ【答案】C【解析】本题考查数据结构中二叉树的遢历。根据对二叉树根的访问先后顺序不同，分别称为前序遍历、中序遍历和后序遍历。这三种遍历都是递归定义的，即在其子树中也按照同样的规律进行遢历。下面就是前序遍历方法的递归定义。当二叉树的根不为空时，依次执行如下3个操作：(1)访问根结点(2)按先序遍历左子树(3)按先序遍历右子树根据如上前序遍历规则，来遍历本题中的二叉树。首先访问根结点，即A,然后遍历A的左子树。遍历左子树同样按照相同的规则首先访问根结点B,然后遍历B的左子树。遍历B的左子树，首先访问D,然后访问D的左子树，D的左子树为空，接下来访问D的右子树，即丫。遍历完B的左子树后，再遍历B的右子树，即E。到此遍历完A的左子树，接下来遍历A的右子树。按照同样的规则，首先访问C,然后遍历c的左子树。即F。c的左子树遍历完，接着遍历c的右子树。首先访问右子树的根结点X,然后访问X的左子树，X的左子树，即Z,接下来访问X的右子树，右子树为空。到此，把题目的二叉树进行了一次前序遍历。遍历的结果为ABDYECFXZ,故本题的正确答案为选项Co(20)某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为()A)n+1n-12nD)n/2A)n+1n-12nD)n/2【答案】A【解析】本题考查数据结构中二叉树的性质。二叉树满足如下一条性质，即：对任意一棵二叉树，若终端结点(即叶子结点)数为n0,而其度数为2的结点数为n2,则n0=n2+lo根据这条性质可知，若二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为n+L因此，本题的正确答案是选项Ao(21)在深度为7的满二叉树中，叶子结点的个数为A)32B)31C)64 D)63【答案】C【解析】在二叉树的第k层上，最多有2皿(心1)个结点。对于满二叉树来说，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2。个结点。因此，在深度为7的满二叉树中，所有叶子结点在第7层上,即其结点数为21=27-1=64因此.本题的正确答案为Co(22)下列叙述中正确的是一个算法的空间复杂度大，则其时间复杂度也必定大一个算法的空间复杂度大，则期时间复杂度必定小一个算法的时间复杂度大，则其空间复杂度必定小D)上述三种说法都不对【答案】D【解析】时间复杂度是指一个算法执行时间的相对度量；空间复杂度是指算法在运行过程中临时占用所需存储空间大小的度量。人们都希望选择一个既省存储空间、又省执行时间的算法。然而，有时为了加快算法的运行速度，不得不增加空间开销；有时为了能有效地存储算法和数据，又不得不牺牲运行时间。时间和空间的效率往往是一对矛盾，很难做到两全。但是，这不通用于所有的情况，也就是说时间复杂度和空间复杂度之间虽然经常矛盾。但是二者不存在必然的联系。因此，选项A、B、c的说法都是错误(23)在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为A>63B)64C)6D)7【答案】B【解析】在长度为64的有序线性表中，其中的64个数据元素是按照从大到小或从小到大的顺序排列有序的。在这样的线性表中进行顺序查找，最坏的情况就是查找的数据元素不在线性表中或位于线性表的最后。按照线性表的顺序查找算法，首先用被查找的数据和线性表的第一个数据元素进行比较。若相等，则查找成功，否则，继续进行比较，即和线性表的第二个数据元素进行比较。同样，若相等，则查找成功，否则，继续进行比较。依次类推，直到在线性表中查找到该数据或查找到线性表的最后一个元素，算法才结束。因此，在长度为64的有序线性表中进行顺序查找，最坏的情况下需要比较64次。因此，本题的正确答案为Bo(24)对下列二叉树进行中序遍历的结果是A)ACBDFEG B)ACBDFGEC)ABDCGEF D)FCADBEG【答案】A【解析】二叉树的中序遍历递归算法为：如果根不空，贝1(1)按中序次序访问左子树；(2)访问根结点：(3)按中序次序访问右子树。否则返回。本题中，根据中序遍历算法.应首先按照中序次序访问以c为根结点的左子树，然后再访问根结点F,最后才访问以E为根结点的右子树。遍历以c为根结点的左子树同样要遵循中序遍历算法，因此中序遍历结果为ACBD；然后遍历根结点F；遍历以E为根结点的右子树，同样要遵循中序遍历算法，因此中序遍历结果为EGo最后把这三部分的遍历结果按顺序连接起来，中序遍历结果为ACBDFEG。因此，本题的正确答案是A。(25)数据的存储结构是指.A)存储在外存中的数据 B)数据所占的存储空间量C)数据在计算机中的顺序存储方式D)数据的逻辑结构在计算机中的表示【答案】D【解析】数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，也称数据的物理结构。所以选项D正确。(26)下列关于栈的描述中错误的是oA)栈是先进后出的线性表B)栈只能顺序存储C)栈具有记忆作用D)对栈的插入与删除操作中，不需要改变栈底指针【答案】B【解析】本题考核栈的基本概念，我们可以通过排除法来确定本题的答案。栈是限定在一端进行插入与删除的线性表，栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素,即栈是按照“先进后出”或“后进先出”的原则组织数据的，这便是栈的记忆作用，所以选项A和选项C正确。对栈进行插入和删除操作时，栈顶位置是动态变化的，栈底指针不变，选项D正确。由此可见，选项B的描述偌误。(27)对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是.A)冒泡排序为n/2 B)冒泡排序为nC)快速排序为n D)快速排序为n(nT)/2【答案】D【解析】假设线性表的长度为n,在最坏情况下，冒泡排序和快速排序需要的比较次数为n(n-1)/2。由此可见，选项D正确。(28)对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为,A)log2"B)n/2 C)n D)n+1【答案】C【解析】在长度为n的线性表中进行顺序查找，最坏情况下需要比较n次。选项C正确。（29）下列对于线性链表的描述中正确的是.A）存储空间不一定是连续，且各元素的存储顺序是任意的B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的【答案】A【解析】在链式存储结构中，存储数据的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，数据元素之间的逻辑关系，是由指针域来确定的。由此可见，选项A的描述正确。（30）某二叉树中度为2的结点有18个，则该二叉树中有个叶子结点。【答案】19【解析】二叉树具有如下性质：在任意一棵二叉树中，度为O的结点（即叶子结点）总是比度为2的结点多一个。根据题意，度为2的节点为18个，那么，叶子结点就应当是19个。（1）线性表若采用链式存储结构时，要求内存中可用存储单元的地址A）必须是连续的B）部分地址必须是连续的一定是不连续的D）连续不连续都可以解析：在链式存储结构中，存储数据结构的存储空间可以是连续的，也可以是不连续的，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。故本题答案应该为选项D）（2）在待排序的元素序列基本有序的前提下，效率最高的排序方法是A）冒泡排序B）选择排序C）快速排序D）归并排序解析：从平均时间性能而言，快速排序最佳，其所需时间最少，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。当序列中的记录基本有序或元素个数较少时，冒泡排序和筒单选择排序为最佳排序方法，故本题答案应该为选项A）o（3）下列叙述中，错误的是A）数据的存储结构与数据处理的效率密切相关B）数据的存储结构与数据处理的效率无关C）数据的存储结构在计算机中所占的空间不一定是连续的一种数据的逻辑结构可以有多种存储结构解析：一般来说，一种数据结构根据需要可以表示成多种存储结构。常用的存储结构有顺序、链接、索引等，而采用不同的存储结构，其数据处理的效率是不同的；一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系是有可能不同的。故本题答案应该为选项B）o（4）希尔排序属于A）交换排序B）归并排序C）选择排序D）插入排序解析：希尔排序的基本思想是把记录按下标的一定增■分组，对每组记录使用插入排序，随增■的逐渐减小，所分成的组包含的记录越来越多，到增♦的值减小到1时，整个数据合成一组，构成一组有序记录，故其属于插入排序方法。故本题答案应该为选项D）。（1）栈和队列的共同特点是A）都是先进先出B）都是先进后出C）只允许在端点处插入和删除元素D）没有共同点解析：栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种“后进先出”的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种“先进先出”的线性表。故本题答案应该为选项C）O（2）已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是acbeddecabdeabccedba解析：依据后序遍历序列可确定根结点为c;再依据中序遍历序列可知其左子树由deba构成，右子树为空；又由左子树的后序遍历序列可知其根结点为e,由中序遍历序列可知其左子树为d,右子树由ba构成，如下图所示。求得该二叉树的前序遍历序列为选项D）。（3）链表不具有的特点是A）不必事先估计存储空间B）可随机访问任一元素C）插入删除不需要移动元素D）所需空间与线性表长度成正比解析：链表采用的是隹式存储结构，它克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。但是隹式存储结构也有不足之处：①每个结点中的指针域需额外占用存储空间；②健式存储结构是一种非81机存储结构。故本题答案应该为选项D）。（6）算法的时间复杂度是指A）执行算法程序所需要的时间B）算法程序的长度C）算法执行过程中所需要的基本运算次数D）算法程序中的指令条数解析：算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度。所谓算法的时间复杂度是指执行算法所需要的计算工作・；算法的空间复杂度一般是指执行这个算法所需要的内存空间。故本题答案应

该为选项A)。(1)已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为GEDHFBCADGEBHFCAABCDEFGHACBFEDHG解析：利用前序和中序遍历的方法可以确定二叉树的结构，具体步骤如下：①前序遍历的第一个结点A为树的根结点；②中序遍历中A的左边的结点为A的左子树，A右边的结点为A的右子树；③再分别对A的左右子树进行上述两步处理，直到每个结点都找到正确的位置。故本题答案应该为选项B)。(2)树是结点的集合，它的根结点数目是A)有且只有11或多于10或1D)至少2解析：树是一个或多个结点组成的有限集合，其中一个特定的结点称为根，其余结点分为若干个不相交的集合。每个集合同时又是一棵树。树有且只有1个根结点。故本题答案应该为选项A)o(3)如果进栈序列为el,e2,e3,e4,则可能的出栈序列是e3,el,e4,e2e2,e4,e3,ele3,e4,el,e2D)任意顺序①・1.・2入栈⑦・2出栈.入栈③.4出栈④。3出栈⑤出栈解析：由栈"后进先出"的特点可知：A)中e1不可能比e2先出，C)中e3不可能比e4①・1.・2入栈⑦・2出栈.入栈③.4出栈④。3出栈⑤出栈故本题答案应该为选项B)。（4）在设计程序时，应采纳的原则之一是A）不限制goto语句的使用B）减少或取消注解行C）程序越短越好D）程序结构应有助于读者理解解析：溢用goto语句将使程序流程无规律，可读性差，因此A）不选；注解行有利于对程序的理解，不应减少或取消，B）也不选；程序的长短要依照实际情况而论，而不是越短越好，C）也不选。故本题答案应该为选项D）。（5）程序设计语言的基本成分是数据成分、运算成分、控制成分和A）对象成分B）变量成分C）语句成分D）传输成分解析：程序设计语言是用于书写计算机程序的语言，其基本成分有以下4种，数据成分：用来描述程序中的数据。运算成分：描述程序中所需的运算。控制成分：用来构造程序的逻辑控制结构。传输成分：定义数据传输成分，如输入输出语言。故本题答案应该为选项D）。（1）循环链表的主要优点是A）不再需要头指针了B）从表中任一结点出发都能访问到整个链表C）在进行插入、删除运算时，能更好的保证链表不断开D）一知某个结点的位置后，能够容易的找到它的直接前件解析：循环链表就是将单向链表中最后一个结点的指针指向头结点，使整个链表构成一个环形，这样的结构使得从表中的任一结点出发都能访问到整个链表。故本题答案应该为选项B）o（2）栈底至栈顶依次存放元素A、B、C、D,在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是ABCEDDCBEADBCEAD)CDABE解析：栈操作原则上“后进先出”，栈底至栈顶依次存放元素A、B、C、D,则表明这4个元素中D是最后进栈，B、C处于中间，A最早进栈。所以出栈时一定是先出D,再出C,最后出Ao故本题答案应该为选项B）。（3）对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为。N+1N（N+D/2N/2解析：［答案］B,很简单，我们的二级程序设计语言书中都有此算法，另外还要掌握二分法查找，这也是我们二级中常考的。那么二分法最坏的情况为多少次呢？Iog2n的最小整数值。比如n为4,最坏的情况要比较3次；n为18,最坏的情况要比较5次。（1）下列叙述中正确的是A）线性表是线性结构B）栈与队列是非线性结构C）线性链表是非线性结构D）二叉树是线性结构解析：线性表是一种线性结构，数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的；栈、队列、线性性表实际上也是线性表，故也是线性结构；树是一种简单的非绫性结构。故本题答案应该为选项A）o（2）非空的循环单链表head的尾结点（由p所指向），满足p->next==NULLp==NULLp->next=headp=head解析：循环链表就是将链表的最后一个结点指向链表头结点（或第一个结点），即p->next=heado故本（3）已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是A）堆排序B）直接插入排序C）快速排序D）直接选择排序解析：当数据表A中每个元素距其最终位置不远，说明数据表A按关键字值基本有序，在待排序序列基本有序的情况下，采用插入排序所用时间最少，故答案为选项B））,（1）假设线性表的长度为n,则在最坏情况下，冒泡排序需耍的比较次数为log2°n20（nl.5）n（n-1）/2解析：假设线性表的长度为n,则在最坏情况下，冒泡排序要经过n/2通的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n（n-1）120故本题答案应该为选项D）。（2）算法分析的目的是A）找出数据结构的合理性B）找出算法中输入和输出之间的关系C）分析算法的易懂性和可靠性D）分析算法的效率以求改进解析：算法分析是指对一个算法的运行时间和占用空间做定■的分析，一般计算出相应的数■级，常用时间复杂度和空间复杂度表示。分析算法的目的就是要降低算法的时间复杂度和空间复杂度，提高算法的执行效率。故本题答案应该为选项D）。（3）线性表L=（al,a2,a3,…ai,…an）,下列说法正确的是A）每个元素都有一个直接前件和直接后件B）线性表中至少要有一个元素C）表中诸元素的排列顺序必须是由小到大或由大到小D）除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件解析：线性表可以为空表；第一个元素没有直接前件，最后一个元素没有直接后件；线性表的定义中，（4）在单链表中，增加头结点的目的是A）方便运算的实现B）使单链表至少有一个结点C）标识表结点中首结点的位置D）说明单链表是线性表的链式存储实现解析：头结点不仅标识了表中首结点的位置，而且根据单链表（包含头结点）的结构，只要掌握了表头，就能够访问整个链表，因此增加头结点目的是为了便于运算的实现。故本题答案应该为选项A）。（1）算法的空间复杂度是指A）算法程序的长度B）算法程序中的指令条数C）算法程序所占的存储空间D）执行过程中所需要的存储空间解析：算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度。所谓算法的时间复杂度是指执行算法所需要的计算工作■；算法的空间复杂度一般是指执行这个算法所需要的内存空间。故本题答案应该为选项D）。（2）用链表表示线性表的优点是A）便于随机存取B）花费的存储空间较顺序存储少C）便于插入和删除操作D）数据元素的物理顺序与逻辑顺序相同解析：链式存储结构克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。故链式存储结构下的线性表便于插入和删除操作。故本题答案应该为选项C）O（3）数据结构中，与所使用的计算机无关的是数据的A）存储结构B）物理结构C）逻辑结构D）物理和存储结构解析：数据结构概念一般包括3个方面的内容，数据的逻辑结构、存储结构及数据上的运算集合。数据的逻辑结构只抽象的反映数据元素之间的逻辑关系，而不管它在计算机中的存储表示形式。故本题答案应该为选项C）。（1）由两个栈共享一个存储空间的好处是A）减少存取时间，降低下溢发生的机率B）节省存储空间，降低上溢发生的机率C）减少存取时间，降低上溢发生的机率D）节省存储空间，降低卜溢发生的机率解析：常常一个程序中要用到多个栈，为了不发生上溢错误，就必须给每个栈分配一个足够大的存储空间。但实际中，很难准确地估计，若每个栈都分配过大的存储空间，势必造成系统空间紧张；若让多个栈共用一个足够大的连续存储空间，则可利用栈的动态特性使他们的存储空间互补。故本题答案应该为选项B）。（2）设有两个串p和q,求q在P中首次出现位置的运算称作A）连接B）模式匹配C）求子串D）求串长解析：子串的定位操作通常称作串的模式匹配，是各种串处理系统中最重要的操作之一，算法的基本思想是：从主串的开始字符起和模式的第一个字符比较，若相等则继续比较后续字符，否则从主串的下一个字符起再重新和模式的字符比较，依次类推，直至模式中的每一个字符依次和主串中的一个连续的字符序列相等，称匹配成功，否则称匹配不成功。（3）下列关于队列的叙述中正确的是A.在队列中只能插入数据B.在队列中只能删除数据C.队列是先进先出的线性表D.队列是先进后出的线性表解析：C队列是先进先出的，栈是先进后出的，2者的区别一定要搞清楚。(1)算法的空间复杂度是指A)算法程序的长度B)算法程序中的指令条数C)执行算法程序所占的存储空间D)算法执行过程中所需要的存储空间【答案】D【解析】算法的空间复杂度一般是指这个算法执行时所需要的内存空间，其中包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，其中额外空间还包括算法程序执行过程的工作单元以及某种数据结构所需要的附加存储空间。(2)线性表的链式存储结构是一种A)随机结构B)顺序结构C)索引结构D)散列结构【答案】B【解析】线性表的链式存储结构中的每一个存储结点不仅含有一个数据元素，还包括指针，每一个指针指向一个与本结点有逻辑关系的结点。此类存储方式属于顺序存储。(3)设有下列二叉树：对此二叉树先序遍历的结果是A)ABCDEFB)DBEAFCOABDECFD)DEBFCA【答案】C【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求先序遍历；遍历顺序应该为：访问根结点->先序遍历左子树->先序遍历右子树。按照定义，先序遍历序列是ABDECF。（1）算法分析的目的是.A）找出数据结构的合理性B）找出算法中输入和输出之间的关系C）分析算法的易懂性和可靠性D）分析算法的效率以求改进答案：D评析：算法分析是指对一个算法的运行时间和占用空间做定量的分析，一般计算出相应的数量级，常用时间复杂度和空间复杂度表示。分析算法的目的就是要降低算法的时间复杂度和空间复杂度，提高算法的执行效率。（3）已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是。A）堆排序 B）直接插入排序C）快速排序 D）直接选择排序答案：B评析：当数据表A中每个元素距其最终位置不远，说明数据表A按关键字值基本有序，在待排序序列基本有序的情况下，采用插入排序所用时间最少，故答案为选项B.（4）用链表表示线性表的优点是。A）便于插入和删除操作B）数据元素的物理顺序与逻辑顺序相同C）花费的存储空间较顺序存储少D）便于随机存取答案：A评析：钱式存储结构克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。故链式存储结构下的线性表便于插入和删除操作。1.以下数据结构中不属于线性数据结构的是.A、队列B、线性表C、二叉树D、栈解析:线性表、栈和队列等数据结构所表达和处理的数据以线性结构为组织形式。栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作，允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。所以栈又称后进先出表(LastInFirstOut);队列可看作是插入在一端进行，删除在另一端进行的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。在队列中，只能删除队头元素，队列的最后一个元素一定是最新入队的元素。因此队列又称先进先出表(FirstInFirstOut)。本题答案为Co5.下列关于栈的叙述中正确的是。A、在栈中只能插入数据B、在栈中只能删除数据C、栈是先进先出的线性表D、栈是先进后出的线性表解析:栈是限定在一端进行插入与删除的线性表。栈是按照"先进后出"的或后进先出的原则组织数据的，因此，栈也被称为"先进后出"表或"后进先出"表。本题答案是Do7.对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为.A、N+1B、NC、(N+D/2D、N/2解析:在进行顺序查找过程中，如果线性表中被查的元素是线性表中的最后一个，或者被查元素根本不在线性表中，则为了查找这个元素需要与线性表中所有元素进行比较，这是顺序查找最坏的情况。本题答案为Bo1.在一棵二叉树上第5层的结点数最多是.A、8B、16C、32D、15解析:根据二叉树的性质：二叉树第i(住1)层上至多有2i-1个结点。得到第5层的结点数最多是16o本题答案为Bo3.下列叙述中正确的是.A、线性表是线性结构B、栈与队列是非线性结构C、线性链表是非线性结构D、二叉树是线性结构解析:根据数据结构中各数据元素之间前后间关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，又称线性表。所以线性表、栈与队列、线性链表都是线性结构，而二叉树是非线性结构。本题答案是A。7.在下列选项中，哪个不是一个算法一般应该具有的基本特征 ,A、确定性B、可行性C、无穷性D、拥有足够的情报解析:作为一个算法，一般应具有以下几个基本特征。1）可行性2）确定性3）有穷性4）拥有足够的情报本题答案为Co5.在计算机中，算法是指oA、查询方法B、加工方法C、解题方案的准确而完整的描述D、排序方法解析:计算机算法是指解题方案的准确而完整的描述，它有以下几个基本特征：可行性、确定性、有穷性和拥有足够的情报。本题答案为Co7.在单链表中，增加头结点的目的是.A、方便运算的实现B、使单链表至少有一个结点C、标识表结点中首结点的位置D、说明单链表是线性表的链式存储实现解析:头结点不仅标识了表中首结点的位置，而且根据单链表（包含头结点）的结构，只要掌握了表头，就能够访问整个性表，因此增加头结点目的是为了便于运算的实现。本题答案为Ao.数据的存储结构是指.A、存储在外存中的数据B、数据所占的存储空间量C、数据在计算机中的顺序存储方式D、数据的逻辑结构在计算机中的表示解析:本题考查的是数据结构的基本概念。数据的逻辑结构在计算机存储空间中的存放形式形式称为数据的存储结构（也称数据的物理结构）。故本题答案为Do.下列关于栈的描述中错误的是oA、栈是先进后出的线性表B、栈只能顺序存储C、栈具有记忆作用D、对栈的插入与删除操作中，不需要改变栈底指针解析:本题考查的是栈和队列。栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作，允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。所以栈又称先进后出表（FILO-FirstInLastOut）。线性表可以顺序存储，也可以链式存储，而栈是一种线性表，也可以采用链式存储结构。故本题答案为Bo.对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是oA、冒泡排序为n/2B、冒泡排序为nC、快速排序为nD、快速排序为n(n-l)/2解析:本题考查的是基本排序算法。假设线性表的长度为n,则在最坏情况下，冒泡排序需要经过n/2遍的从前往后扫描和n/2遍的从后往前扫描，需要比较次数为n(n-1)/2o快速排序法的最坏情况比较次数也是n(n-1)/2。故本题答案为Do.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为oA、log2nB、n/2C、nD、n+1解析:本题考查的是顺序查找。在进行顺序查找过程中，如果线性表中的第一个元素就是被查找元素，则只需做一次比较就查找成功，查找效率最高；但如果被查找的元素是线性表中的最后一个元素，或者被查找的元素根本就不在线性表中，则为了查找这个元素需要与线性表中所有的元素进行比较，这是顺序查找的最坏情况。所以对长度为n的线性表进行顺序查找，在最坏情况下需要比较n次。故本题答案为Co.下列对于线性链表的描述中正确的是。A、存储空间不一定是连续，且各元素的存储顺序是任意的B、存储空间不一定是连续，且前件元素一定存储在后件元素的前面C、存储空间必须连续，且前件元素一定存储在后件元素的前面D、存储空间必须连续，且各元素的存储顺序是任意的解析:本题考查的是线性单链表、双向链表与循环链表的结构及其基本运算。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。故本题答案为Ao.算法的时间复杂度是指 oA、执行算法程序所需要的时间B、算法程序的长度C、算法执行过程中所需要的基本运算次数D、算法程序中的指令条数解析:所谓算法的时间复杂度，是指执行算法所需要的计算工作为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作・时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度■算法的工作量。本题答案是Co.下列叙述中正确的是.A、线性表是线性结构B、栈与队列是非线性结构C、线性链表是非线性结构D、二叉树是线性结构解析:根据数据结构中各数据元素之间前后间关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，又称线性表。所以线性表、栈与队列、线性链表都是线性结构，而二叉树是非线性结构。本题答案是Ao.设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为oA、349B、350C、255D、351解析:所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其父结点数为int(n/2),而叶子结点数等于总结点数减去父结点数。本题n=699,故父结点数等于int(699/2)=349,叶子结点数等于699-349=350。本题答案是Bo.算法的空间复杂度是指»A、算法程序的长度B、算法程序中的指令条数C、算法程序所占的存储空间D、算法执行过程中所需要的存储空间解析:一个算法的空间复杂度，一般是指执行这个算法所需的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。本题答案是D。.下列关于栈的叙述中正确的是oA、在栈中只能插入数据B、在栈中只能删除数据C、栈是先进先出的线性表D、栈是先进后出的线性表解析:栈是限定在一端进行插入与删除的线性表。栈是按照"先进后出"的或后进先出的原则组蛆数据的，因此，栈也被称为"先进后出"表或"后进先出"表。本题答案是D。.在深度为5的满二叉树中，叶子结点的个数为.A、32B、31C、16D、15解析:所谓满二叉树是指这样的一种二叉树：除最后一层外，每层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第K层上有2。个结点，且深度为m的满二叉树有2m个结点。在满二叉树中，最后一层的结点个数就是叶子结点的个数，本题中深度为5,故叶子结点数为25-1=24=16O本题答案是Co.算法一般都可以用哪几种控制结构组合而成.A、循环、分支、递归B、顺序、循环、嵌套C、循环、递归、选择D、顺序、选择、循环解析:算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。本题答案为Do.数据的存储结构是指。A、数据所占的存储空间量B、数据的逻辑结构在计算机中的表示C、数据在计算机中的顺序存储方式D、存储在外存中的数据解析:数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。本题答案为Bo3.设有下列二叉树:对此二叉树中序遍历的结果为—ABCDEFDBEAFCABDECFDEBFCA解析:所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。本题答案为Bo.在计算机中，算法是指 。A、查询方法B、加工方法C、解题方案的准确而完整的描述D、排序方法解析:计算机算法是指解题方案的准确而完整的描述，它有以下几个基本特征：可行性、确定性、有穷性和拥有足够的情报。本题答案为Co.栈和队列的共同点是«A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点解析:栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种"后进先出"的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种“先进先出"的线性表。本题答案为Co.已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是。cedbaacbeddecabdeabc解析:依据后序遍历序列可确定根结点为c;再依据中序遍历序列可知其左子树由deba构成，右子树为空；又由左子树的后序遍历序列可知其根结点为e,由中序遍历序列可知其左子树为d,右子树由ba构成。求得该二叉树的前序遍历序列为选项A。本题答案为Ao4.在下列几种排序方法中，要求内存量最大的是.A、插入排序B、选择排序C、快速排序D、归并排序解析:快速排序的基本思想是，通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录继续进行排序，以达到整个序列有序；插入排序的基本操作是指将无序序列中的各元素依次插入到已经有序的线性表中，从而得到一个新的序列；选择排序的基本思想是：扫描按个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）,然后对剩下的子表采用同样的方法，直到表空为止；归并排序是将两个或两个以上的有序表组合成一个新的有序表。本题答案为D。.数据结构中，与所使用的计算机无关的是数据的。A、存储结构B、物理结构C、逻辑结构D、物理和存储结构解析:数据结构概念一般包括3个方面的内容，数据的逻辑结构、存储结构及数据上的运算集合。数据的逻辑结构只抽象的反映数据元素之间的逻辑关系，而不管它在计算机中的存储表示形式。本题答案为Co.栈底至栈顶依次存放元素A、B、C、D,在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是。ABCEDDBCEACDABEDCBEA解析：栈操作原则是“后进先出"，栈底至栈顶依次存放元素A、B、C、D,则表明这4个元素中D是最后进栈，B、C处于中间，A最早进栈。所以出栈时一定是先出D,再出C,最后出A。本题答案为D。.线性表的顺序存储结构和线性表的链式存储结构分别是.A、顺序存取的存储结构、顺序存取的存储结构B、随机存取的存储结构、顺序存取的存储结构C、随机存取的存储结构、随机存取的存储结构D、任意存取的存储结构、任意存取的存储结构解析:顺序存储结构中，数据元素存放在一组地址连续的存储单元中，每个数据元素地址可通过公式L0C(ai)=L0C(a1)+(i-1)L计算得到，从而实现了随机存取。对于桂式存储结构，要对某结点进行存取，都得从性的头指针指向的结点开始，这是一种顺序存取的存储结构。本题答案为Bo.在单链表中，增加头结点的目的是,A、方便运算的实现B、使单链表至少有一个结点C、标识表结点中首结点的位置D、说明单链表是线性表的链式存储实现解析:头结点不仅标识了表中首结点的位置，而且根据单链表(包含头结点)的结构，只要掌握了表头，就能够访问整个链表，因此增加头结点目的是为了便于运算的实现。本题答案为Ao.下面叙述正确的是。A、算法的执行效率与数据的存储结构无关B、算法的空间复杂度是指算法程序中指令(或语句)的条数C、算法的有穷性是指算法必须能在执行有限个步骤之后终止D、以上三种描述都不对解析:算法的设计可以避开具体的计算机程序设计语言，但算法的实现必须借助程序设计语言中提供的数据类型及其算法。数据结构和算法是计算机科学的两个重要支柱。它们是一个不可分割的整体。算法在运行过程中需辅助存储空间的大小称为算法的空间复杂度。算法的有穷性是指一个算法必须在执行有限的步骤以后结束。本题答案为Co.设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为oA、349B、350C、255D、351解析:所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其父结点数为int(n/2),而叶子结点数等于总结点数减去父结点数。本题n=699,故父结点数等于int(699/2)=349,叶子结点数等于699-349=350。本题答案是Bo9.已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是。A、堆排序B、直接插入排序C、快速排序D、直接选择排序解析:当数据表A中每个元素距其最终位置不远，说明数据表A按关键字值基本有序，在待排序序列基本有序的情况下，采用插入排序所用时间最少。本题答案为Bo二、填空题(1)问题处理方案的正确而完整的描述称为0【答案】算法或程序或流程图【解析】算法是问题处理方案正确而完整的描述(2)对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为o【答案】45【解析】在冒泡排序中，最坏情况下，需要比较的次数为n(n-l/2),也就是：10*(10-1)/2=45(3)算法夏杂度主要包括时间复杂度和复杂度。【答案】空间【解析】算法的复杂度主要包括时间复杂度和空间复杂度。所谓算法的时间复杂度，是指执行算法所需要的计算工作一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。(4)一棵二叉树第六层(根结点为第一层)的结点数最多为个。【答案】32【解析】二叉树的一个性质是，在二叉树的第k层上，最多有2k-i(Q1)个结点。此，等于32。所以答案为32。(5)数据结构分为逻辑结构和存储结构，循环队列属于结构。【答案】存储或物理或存储结构或物理结构【解析】数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。所调循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。可知，循环队列应当是物理结构。(6)下列软件系统结构图的宽度为。【解析】题目中的图形是倒置的树状结构，这是用层次图表示的软件结构。结构图中同一层模块的最大模块个数称为结构的宽度，它表示控制的总分布。根据上述结构图宽度的定义，从图中可以看出，第二层的模块个数最多，即为3O因此，这个系统结构图的宽度就为3O(7)按“先进后出”原则组织数据的数据结构是。【答案】栈或Stack【解析】栈和队列是两种特殊的线性表，其特殊性在于对它们的操作只能在表的端点进行。栈中的数据按照后进先出的原则进行组织，而队列中的数据是按照先进先出的原则进行蛆织。因此，本题的正确答案是栈(Stack)。(8)数据结构分为线性结构和非线性结构，带链的队列属于0【答案】线性结构【解析】数据结构分为线性结构和非线性结构，其中队列是属于线性结构。队列有两种存储结构，一种是顺序存储结构，称为顺序队列；另一种是链式存储结构，称为链队列。题目中所说的带链的队列就是指链队列。无论队列采取哪种存储结构，其本质还是队列，还属于一种线性结构。因此，本题的正确答案是线性结构。(9)在深度为7的满二叉树中，度为2的结点个数为o【答案】63或26-1【解析】本题考查数据结构中满二叉树的性质。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。深度为k的满二叉树，一共有2y个结点，其中包括度为2的结点。因此，深度为7的满二叉树，一共有27-1个结点，即127个结点。根据二叉树的另一条性质，对任意一棵二叉树,若终端结点(即叶子结点)数为no,而其度数为2的结点数为&则即=m+1。设尝试为7的满二叉树中，度为2的结点个数为x,则改树中中子结点的个数为x+1。则应满足x+(x+1)=127,解该方程得到，x的值为63O结果上述分析可知，在深度为7的满二叉树中，度为2的结点个数为63»(10)线性表的存储结构主耍分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的存储结构。【答案】顺序【解析】本题考查数据结构的队列。队列是一种特殊的线性表，即限定在表的一端进行删除，在表的另一端进行插入操作的线性表。允许删除的一端叫做队头，允许插入的一端叫做队尾。线性表的存储结构主要分为顺序存储结构和链式存储结构。当队列用链式存储结构实现时，就称为链队列；当队列用顺序存储结构实现时，就称为循环表。因此，本题划线处应填入“顺序”。(11)对下列二叉树进行中序遍历的结果为[b| |H||P|【答案】ACBDFEHGP【解析】本题考查数据结构中二叉树的遍历。根据对二叉树根的访问先后顺序不同，分别称为前序遍历、中序遍历和后序遍历。这三种遍历都是递归定义的，即在其子树中也按照同样的规律进行遢历。下面就是中序遍历方法的递归定义。当二叉树的根不为空时，依次执行如下3个操作：(1)按中序遍历左子树。(2)访问根结点。(3)按中序遍历右子树。根据如上前序遍历规则，来遍历本题中的二叉树。首先遍历F的左子树，同样按中序遍历。先遍历C的左子树，即结点A,然后访问c,接着访问c的右子树，同样按中序遍历c的右子树，先访问结点B,然后访问结点D,因为结点D没有右子树，因此遍历完C的右子树，以上就遍历完根结点F的左子树。然后访问根结点F,接下来遍历F的右子树.同样按中序遍历。首先访问E的左子树，E的左子树为空，则访问结点E,然后访问结点E的右子树，同样按中序遍历。首先访问G的左子树，即H,然后访问结点G,最后访问G的右子树Po以上就把整个二叉树遍历一遍，中序遍历的结果为ACBDFEHGPo因此.划线处应填入"ACBDFEHGP%(11)用链表表示线性表的突出优点是.答案：插入和删除操作方便，不必移动数据元素，执行效率高解析：为了克服顺序表中插入和删除时需要移动大量数据元素的缺点，引入了链式存储结构。链表表示线性表的突出优点是插入和删除操作方便，不必移动数据元素，执行效率高。(12)在长度为n的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为.答案：log2n解析：对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。(11)数据结构分为逻辑结构与存储结构，线性链表属于。答案：存储结构解析：数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构；数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。(11)冒泡排序算法在最好的情况下的元素交换次数为。答案：0解析：根据冒泡排序算法思想可知，若待排序的初始序列为“正序”序列，则只需进行一趟排序，在排序过程中进行n-1次关键字间的比较，且不移动和交换记录，这种情况是冒泡排序的最好情况，故冒泡排序算法在最好的情况下的元素交换次数为Oo(13)若串s="MathTypes”,则其子串的数目是。答案：46解析：串S中共有9个字符，由于串中字符各不相同，则其子串中有0个字符的1个(空串)，1个字符的9个，2个字符的8个，3个字符的7个，4个字符的6个，5个字符的5个，6个字符的4个，7个字符的3个，8个字符的2个，9个字符的1个，共有1+2+3+4+5+6+7+8+9+1=46。(11)在算法正确的前提下，评价一个算法的两个标准是o答案：时间复杂度和空间复杂度X+短(12)将代数式；转换成程序设计中的表达式为o答案:(x+y*y)/(a+b)(11)数据的逻辑结构有线性结构和两大类。答案：非线性结构解析：数据的逻辑结构有线性结构和非线性结构两大类。(12)顺序存储方法是把逻辑上相邻的结点存储在物理位置的存储单元中。答案：也相邻解析：常用的存储表示方法有4种，顺序存储、链式存储、索引存储、散列存储。其中，顺序存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中。(11)当线性表采用顺序存储结构实现存储时，其主要特点是»答案：逻辑结构中相邻的结点在存储结构中仍相邻解析：顺序存储结构的主要特点是数据元素按线性表的逻辑次序，依次存放在一组地址连续的存储单元中。在存储单元中各元素的物理位置和逻辑结构中各结点间的相邻关系是一致的。52.设一棵完全二叉树共有500个结点，则在该二叉树中有个叶子结点。解析:所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其父结点数为int(n/2),而叶子结点数等于总结点数减去父结点数。本题n=500,故父结点数等于int(500/2)=250,叶子结点数等于500-250=250。标准答案为：250.算法的基本特征是可行性、确定性、和拥有足够的情报。解析:算法是指解题方案的准确而完整的描述。它有4个基本特征，分别是可行性、确定性、有穷性和拥有足够的情报。标准答案为：有穷性.顺序存储方法是把逻辑上相邻的结点存储在物理位置的存储单元中。解析:常用的存储表示方法有4种，顺序存储、链式存储、索引存储、散列存储。其中，顺序存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中。标准答案为：相邻(1)算法的复杂度主要包括空间复杂度和【1】复杂度。【答案】空间【解析】算法的复杂度主要指时间复杂度和空间复杂度。(2)在线性结构中，队列的操作顺序是先进先出，而栈的操作顺序是【2】o【答案】先进后出【解析】队列和栈都是线性结构，但是不同之处在于队列的操作顺序是先进先出，而栈的操作顺序是先进后出。(2)在最坏情况下，堆排序需要比较的次数为【2】«答案：O(nlog2n)评析：在最坏情况下，冒泡排序所需要的比较次数为n(n-1)/2;简单插入排序所需要的比较次数为n(n-1)/2;希尔排序所需要的比较次数为。(a5)；堆排序所需要的比较次数为OSIog?。。(3)若串s="Program”,则其子串的数目是【3】。答案：29评析：串s中共有7个字符，由于串中字符各不相同，则其子串中有0个字符的1个(空串),1个字符的7个，2个字符的6个，3个字符的5个，4个字符的4个，5个字符的3个，6个字符的2个，7个字符的1个，共有1+2+3+4+5+6+7+1=29。.实现算法所需的存储单元多少和算法的工作量大小分别称为算法的o解析:算法的复杂性是指对一个在有限步舞内终止算法和所需存储空间大小的估计。算法所需存储空间大小是算法的空间复杂性，算法的计算・是算法的时间复杂性。标准答案为：空间复杂度和时间复杂度.数据结构包括数据的逻辑结构、数据的以及对数据的操作运算。解析:数据结构包括3个方面，即数据的逻辑结构、数据的存储结构及对数据的操作运算。标准答案为：存储结构53在最坏情况下，冒泡排序的时间爱杂度为 。解析:冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n,则在最坏的情况下，胃泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2o标准答案为:n(n-1)/2或n*(n-1)/2或O(n(n-1)/2)或0(n*(n-1)/2)54.顺序存储方法是把逻辑上相邻的结点存储在物理位置 的存储单元中。解析:常用的存储表示方法有4种，顺序存储、链式存储、索引存储、散列存储。其中，顺序存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中。标准答案为：相邻52.在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、遍历和后序遍历。标准答案为：中序解析：在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历和后序遍历。前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。中序遍历指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。后序遍历指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历右子树，然后访问根结点，最后遍历左子树；并且遍历左、右子树时，仍然先遍历右子树，然后访问根结点，最后遍历左子树。.数据结构包括数据的逻辑结构、数据的以及对数据的操作运算。标准答案为：存储结构解析：数据结构包括3个方面，即数据的逻辑结构、数据的存储结构及对数据的操作运算。.算法具有五个特性，以下选项中不属于算法特性的是«A、有穷性B、简洁性C、可行性D、确定性解析:本题考查的是算法的特性。有穷性、确定性、有零个或多个输入、有一个或多个输出、有效性是算法的五大特性。故本题答案为Bo.某二叉树中度为2的结点有18个，则该二叉树中有个叶子结点。标准答案为：19解析:本题考查的是二叉树的定义及其存储结构。二叉树的性质3:在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。本题中度为2的结点数为18,故叶子结点数为18+1=19个。55.问题处理方案的正确而完整的描述称为。标准答案为：算法 本题考查的是算法的基本概念。解析:所谓算法是指解题方案的准确而完整的描述。.设一棵完全二叉树共有500个结点，则在该二叉树中有个叶子结点。标准答案为：250解析:所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其父结点数为int(n/2),而叶子结点数等于总结点数减去父结点数。本题n=500,故父结点数等于int(500⑵=250,叶子结点数等于500-250=250。.在最坏情况下，冒泡排序的时间复杂度为.标准答案为:n(n-1)/2或n*(n-1)/2或O(n(n-1)/2)或O(n*(n-1)/2)解析:冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n,则在最坏的情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)/2o.数据结构包括数据的结构和数据的存储结构。标准答案为：逻辑解析:数据结构是指带有结构的数据元素的集合。它包括数据的逻辑结构和数据的存储结构。数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的存储结构是指在计算机存储空间中的存放形式。第二章程序设计基础一、选择题（1）下列叙述中正确的是A）程序设计就是编制程序B）程序的测试必须由程序员自己去完成C）程序经调试改错后还应进行再测试D）程序经调试改错后不必进行再测试【答案】C【解析】软件测试仍然是保证软件可靠性的主要手段，测试的目的是要尽■发现程序中的错误，调试主要是推断错误的原因，从而进一步改正错误。测试和调试是软件测试阶段的两个密切相关的过程，通常是交替进行的。选项C正确。（2）下面描述中，不符合结构化程序设计风格的是A）使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑B）注重提高程序的可读性D）使用goto语句【答案】D【解析】在结构化程序设计中，应严格控制使用GOTO语句，必要时才可以使用，故答案为D。（3）在面向对象设计中，对象有很多基本特点，其中“从外面看只能看到对象的外部特性，而对象的内部对外是不可见的”这一性质指的是对象的A）分类性B）标识惟一性C）多态性D）封装性【答案】D【解析】从外面看只能看到对象的外部特性，而对象的内部，即处理能力的实行和内部状态，指的是对象的封装性。（4）结构化程序设计的一种基本方法是A）筛选法B）递归法C）归纳法D）逐步求精法【答案】D【解析】在结构化程序设计中通常采取自上而下、逐步求精的方法，其总的思想是先全局后局部、先整体后细节、先抽象后具体。而筛选法、递归法和归纳法指的都是程序的某种具体算法。（5）函数重载是指A）两个或两个以上的函数取相同的函数名，但形参的个数或类型不同B）两个以上的函数取相同的名字和具有相同的参数个数，但形参的类型可以不同C）两个以上的函数名字不同，但形参的个数或类型相同D）两个以上的函数取相同的函数名，并且函数的返回类型相同【答案】A【解析】函数重载指的是两个或两个以上的函数具有相同的函数名，但形参的个数或类型不同。程序中通过判断主调函数传过来的参数的个数和类型，来决定选择调用哪个具体的函数。（6）下列选项中不符合良好程序设计风格的是A）源程序要文档化B）数据说明的次序要规范化C）避免滥用goto语D）模块设计要保证高耦合、高内聚【答案】D【解析】编程风格是在不影响性能的前提下，有效地编排和组织程序，以提高可读性和可维护性。更直接的说，风格就是意味着要按照规则进行编程。这些规则包括：程序文档化。就是程序文档包含恰当的标识符.适当的注解和程序的视觉组织等。（2）数据说明。出于阅读理解和维护的需要，最好使模块前的说明语句次序规范化。此外，为方便查找，在每个说明语句的说明符后，数据名应按照字典顺序排列。（3）功能模块化。即把源程序代码按照功能划分为低相合、高内聚的模块。（4）注意goto语句的使用。合理使用goto语句可以提高代码的运行效率.但goto语句的使用会破坏程序的结构特性。因此，除非确实需要，否则最好不使用goto语，因此，本题的正确答案是D。（7）在结构化程序设计中，模块划分的原则是（）A）各模块应包括尽量多的功能B）各模块的规模应尽量大0各模块之间的联系应尽量紧密D）模块内具有高内聚度、模块间具有低耦合度【答案】D【解析】本题考查软件工程中软件设计的概念和原理。人们在开发计算机软件的长期实践中积累了丰富的经验，总结这些经验得到如下的启发式规则：.改进软件结构，提高模块独立性。通过模块的分解或合并，力求降低耨合提高内聚。低相合也就是降低不同模块间相互依赖的紧密程度，高内聚是提高一个模块内各元素彼此结合的紧密程度。.模块的规模应适中。一个模块的规模不应过大，过大的模块往往是由于分解不够充分；过小的模块开销大于有益操作，而且模块过多将使系统接口复杂。因此过小的模块有时不值得单独存在。.模块的功能应该可以预测，但也要防止模块功能过分局限。如果模块包含的功能太多，则不能体现模块化设计的特点；如果模块的功能过分的局限，使用范围就过分狭窄。经过上述分析，本题的正确答案是选项D。（8）下面选项中不属于面向对象程序设计特征的是（）A）继承性B）多态性C）类比性D）封装性【答案】C【解析】通常认为，面向对象方法具有封装性、继承性、多态性几大特点。就是这几大特点，为软件开发提供了一种新的方法学。封装性：所谓封装就是将相关的信息、操作与处理融合在一个内含的部件中（对象中）。简单地说，封装就是隐藏信息。这是面向对象方法的中心，是面向对象程序设计的基础。继承性：子类具有派生它的类的全部H性（数据）和方法，而根据某一类建立的对象也都具有该类的全部，这就是继承性。继承件自动在类与子类间共享功能与数据，当某个类作了某项修改，其子类会自动改变，子类会继承其父类所有特性与行为模式，继承有利于提高软件开发效率，容易达到一致性。多态性：多态性就是多种形式。不同的对象在接收到相同的消息时，采用不同的动作。例如，一个应用程序包括许多对象，这些对象也