数据结构基础、程序设计基础、软件工程基础、数据库基础知识带解析题库

第一章 数据结构一、选择题（1）下列数据结构中，能用二分法进行查找的是A）顺序存储的有序线性表 B ）线性链表C）二叉链表 D ）有序线性链表【答案】A【解析】二分查找只适用于顺序存储的有序表。 在此所说的有序表是指线性表中的元素按值非递减排列 (即从小到大．但允许相邻元素值相等 )的。选项 A正确。（2）下列关于栈的描述正确的是A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D【答案】C【解析】栈是一种特殊的线性表，其插入与删除运算都只在线性表的一端进行。由此可见，选项 A、选项B和选项D错误，正确答案是选项 C。（3）下列叙述中正确的是）一个逻辑数据结构只能有一种存储结构）数据的逻辑结构属于线性结构，存储结构属于非线性结构）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率【答案】D【解析】一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。由此可见，选项 D的说法正确。算法执行过程中所需要的存储空间称为算法的A）时间复杂度 B）计算工作量 C）空间复杂度 D）工作空间【答案】c【解析】算法执行时所需要的存储空间，包括算法程序所占的空间、输入的初始数据 所占的存储空间以及算法执行过程中所需要的额外空间，其中额外空间还包括算法程序执行过程的工作单元以及某种数据结构所需要的附加存储空间。这些存储空间共称为算法的空间复杂度。下列关于队列的叙述中正确的是A）在队列中只能插入数据 B）在队列中只能删除数据C）队列是先进先出的线性表 D）队列是先进后出的线性表【答案】c【解析】对队列可以进行插入和删除数据的操作，只是插入数据只能在队尾，删除数据只能在队头。 所以队列是先进先出的线性表。设有下列二叉树：AB CD E F对此二叉树后序遍历的结果为A）ABCDEFB）BDAECF C）ABDCEFD）DBEFCA【答案】D【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求后序遍历。其遍历顺序应该为：后序遍历左子树一 >后序遍历右子树一 >访问根结点。按照定义，后序遍历序列是 DBEFCA，故答案为 D。下列叙述中正确的是()程序执行的效率与数据的存储结构密切相关程序执行的效率只取决于程序的控制结构C)程序执行的效率只取决于所处理的数据量D)以上三种说法都不对【答案】A【解析】本题考查程序效率。程序效率是指程序运行速度和程序占用的存储空间。影响程序效率的因素是多方面的，包括程序的设计、使用的算法、数据的存储结构等。在确定数据逻辑结构的基础上，选择一种合适的存储结构，可以使得数据操作所花费的时间少，占用的存储空间少，即提高程序的效率。因此，本题选项A的说法是正确的。下列叙述中正确的是()数据的逻辑结构与存储结构必定是一一对应的由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C)程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线线结构D)以上三种说法都不对【答案】D【解析】本题考查数据结构的基本知识。数据之间的相互关系称为逻辑结构。通常分为四类基本逻辑结构，即集合、线性结构、树型结构、图状结构或网状结构。存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。存储结构在计算机中有两种，即顺序存储结构和链式存储结构。 顺序存储结构是把数据元素存储在一块连续地址空间的内存中；链式存储结构是使用指针把相互直接关联的节点链接起来。 因此，这两种存储结构都是线性的。可见，逻辑结构和存储结构不是一一对应的。因此，选项 A和选项B的说法都是错误的。无论数据的逻辑结构是线性的还是非线性的，只能选择顺序存储结构或链式存储结构来实现存储。 程序设计语言中，数组是内存中一段连续的地址空间，可看作是顺序存储结构。可以用数组来实现树型逻辑结构的存储，比如二叉树。 因此，选项 c的说法是错误的冒泡排序在最坏情况下的比较次数是()A)n(n+1)/2

B)nlog

2n

C)n(n-1)/2

D)n/2【答案】C【解析】冒泡排序的基本思想是：将相邻的两个元素进行比较，如果反序，则交换；对于一个待排序的序列，经一趟排序后，最大值的元素移动到最后的位置，其他值较大的元素也向最终位置移动，此过程称为一趟冒泡。对于有

n个数据的序列，共需

n-1

趟排序，第

i趟对从

l到

n-i

个数据进行比较、交换。冒泡排序的最坏情况是待排序序列逆序，

第

l

趟比较

n-1

次，第2趟比较

n-2

次。依此类推，最后趟比较

1次，一共进行

n-l

趟排序。因此，冒泡排序在最坏情况下的比较次数是

(n-1)+(n-2)+

⋯+l，结果为

n(n-1)/2

。本题的正确答案是选项

c。(10) 一棵二叉树中共有

70个叶子结点与

80个度为

1的结点，则该二叉树中的总结点数为

()A)219

B)221

C)229

D)231【答案】A【解析】本题考查数据结构中二叉树的性质。二叉树满足如下一条性质，即：对任意一棵二叉树，若终端结点(即叶子结点)数为n0，而其度数为 2的结点数为 n2，则n0=n2+l。根据这条性质可知，若二叉树中有

70个叶子结点，则其度为

2的结点数为

70-1，即

69个。二叉树的总结点数是度为

2、度为

1和叶子结点的总和，因此，题目中的二叉树总结点数为

69+80+70，即

219。因此，本题的正确答案是选项

A。下列叙述中正确的是()算法的效率只与问题的规模有关，而与数据的存储结构无关算法的时间复杂度是指执行算法所需要的计算工作量C)数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关【答案】B【解析】本题考查数据结构中有关算法的基本知识和概念。数据的结构，直接影响算法的选择和效率。而数据结构包括两方面， 即数据的逻辑结构和数据的存储结构 。因此，数据的逻辑结构和存储结构都影响算法的效率。选项 A的说法是错误的。 算法的时间复杂度是指算法在计算机内执行时所需时间的度量；与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。 因此，选项 B的说法是正确的。数据之间的相互关系称为逻辑结构。通常分为四类基本逻辑结构，即集合、线性结构、树型结构、图状结构或网状结构。存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。存储结构在计算机中有两种， 即顺序存储结构和链式存储结构 。可见，逻辑结构和存储结构不是一一对应的。 因此，选项c的说法是错误的。有时人们为了提高算法的时间复杂度，而以牺牲空间复杂度为代价。但是，这两者之间没有必然的联系。因此，选项D的说法是错误的。下列关于算法的时间复杂度陈述正确的是A）算法的时间复杂度是指执行算法程序所需要的时间B）算法的时间复杂度是指算法程序的长度C）算法的时间复杂度是指算法执行过程中所需要的基本运算次数D）算法的时间复杂度是指算法程序中的指令条数【答案】C【解析】算法的时间复杂度是指执行算法所需要的计算工作量，也就是算法在执行过程中所执行的基本运算的次数，而不是指程序运行需要的时间或是程序的长度。下列关于栈的叙述中正确的是A）在栈中只能插入数据 B ）在栈中只能删除数据C）栈是先进先出的线性表 D ）栈是先进后出的线性表【答案】D【解析】对栈可进行插入和删除数据的操作，但必须牢记插入和删除数据都只能是在栈顶，是一种特殊的线性表。所以栈是先进后出的线性表。设有下列二叉树：AB CFF D E F对此二叉树中序遍历的结果为A）ABCDEF B）DAECF C）BDAECF D）DBEFCA【答案】C【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求中序遍历，其遍历顺序应该为：中序遍历左子树 ->访问根结点->中序遍历右子树。按照定义，中序遍历序列是 BDAECF，故答案为 B。按照“后进先出”原则组织数据的数据结构是A）队列 B）栈C）双向链表 D）二叉树【答案】B【解析】“后进先出”表示最后被插入的元素最先能被删除 。选项 A中，队列是指允许在一端进行插入、而在另一端进行删除的线性表，在队列这种数据结构中，最先插入的元素将最先能够被删除，反之，最后插入的元素将最后才能被删除，队列又称为“先进先出”的线性表，它体现了“先来先服务”的原则：选项B中，栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素，栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。队列和栈都属于线性表，它们具有顺序存储的特点，所以才有“先进先出”和“后进先出”的数据组织方式。双向链表使用链式存储方式．二叉树也通常采用链式存储方式，它们的存储数据的空间可以是不连续的，各个数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。 所以选项c和选项D错。下列叙述中正确的是A）线性链表是线性表的链式存储结构B）栈与队列是非线性结构C）双向链表是非线性结构D）只有根结点的二叉树是线性结构【答案】A【解析】一个非空的数据结构如果满足下列两个条件： (1)有且只有一个根结点 ;(2)每一个结点最多有一个前件，也最多有一个后件。则称为线性结构。线性链表是线性表的链式存储结构，选项 A的说法是正确的。栈与队列是特殊的线性表，它们也是线性结构 ，选项B的说法是错误的； 双向链表是线性表的链式存储结构，其对应的逻辑结构也是线性结构

，而不是非线性结构，选项

c的说法是错误的； 二叉树是非线性结构，而不是线性结构

，选项

D的说法是错误的。因此，本题的正确答案为

A(17)对如下二叉树AB

CD

E

F进行后序遍历的结果为A）ABCDEF

B）DBEAFCC）ABDECF

D）DEBFCA【答案】

D【解析】二叉树后序遍历的简单描述如下：若二叉树为空，则结束返回。否则（ 1)后序遍历左子树； (2)后序遍历右子树； (3)访问根结点。也就是说，后序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。根据后序遍历的算法，后序遍历的结果为 DEBFCA。下列对队列的叙述正确的是()队列属于非线性表队列按“先进后出”原则组织数据C)队列在队尾删除数据D)队列按“先进先出”原则组织数据【答案】D【解析】本题考查数据结构中队列的基本知识。队列是一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出的特性。在队列中，允许插入元素的一端叫做队尾，允许删除的一端则称为队头。这与日常生活中的排队是一致的，最早进入队列的人最早离开，新来的人总是加入到队尾。因此，本题中只有选项 D的说法是正确的。对下列二叉树进行前序遍历的结果为()A)DYBEAFCZX B)YDEBFZXCA C)ABDYECFXZ D)ABCDEFXYZ【答案】C【解析】本题考查数据结构中二叉树的遍历。根据对二叉树根的访问先后顺序不同，分别称为前序遍历、中序遍历和后序遍历。这三种遍历都是递归定义的，即在其子树中也按照同样的规律进行遍历。下面就是前序遍历方法的递归定义。当二叉树的根不为空时，依次执行如下 3个操作：访问根结点按先序遍历左子树按先序遍历右子树根据如上前序遍历规则，来遍历本题中的二叉树。首先访问根结点，即 A，然后遍历 A的左子树。遍历左子树同样按照相同的规则首先访问根结点 B，然后遍历 B的左子树。遍历 B的左子树，首先访问 D，然后访问D的左子树，D的左子树为空,接下来访问 D的右子树，即 Y。遍历完 B的左子树后，再遍历 B的右子树，即 E。到此遍历完 A的左子树，接下来遍历 A的右子树。按照同样的规则，首先访问 C，然后遍历c的左子树。即

F。c

的左子树遍历完，接着遍历

c的右子树。首先访问右子树的根结点

X，然后访问

X的左子树，

X的左子树，即

Z，接下来访问

X的右子树，右子树为空。到此，把题目的二叉树进行了一次前序遍历。遍历的结果为

ABDYECFXZ，故本题的正确答案为选项

C。(20) 某二叉树中有

n个度为

2的结点，则该二叉树中的叶子结点数为

( )A)n+1

B)n-1

C)2n

D)n/2【答案】

A【解析】本题考查数据结构中二叉树的性质。 二叉树满足如下一条性质，即：对任意一棵二叉树，若终端结点

(即叶子结点

)数为

no，而其度数为

2的结点数为

n2，则

n0=n2+l

。根据这条性质可知，若二叉树中有

n个度为

2的结点，则该二叉树中的叶子结点数为

n+l。因此，本题的正确答案是选项

A。(22) 下列叙述中正确的是A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则期时间复杂度必定小C）一个算法的时间复杂度大，则其空间复杂度必定小D）上述三种说法都不对【答案】D【解析】时间复杂度是指一个算法执行时间的相对度量；空间复杂度是指算法在运行过程中临时占用所需存储空间大小的度量。 人们都希望选择一个既省存储空间、又省执行时间的算法。然而，有时为了加快算法的运行速度，不得不增加空间开销；有时为了能有效地存储算法和数据，又不得不牺牲运行时间。时间和空间的效率往往是一对矛盾，很难做到两全。但是，这不适用于所有的情况，也就是说时间复杂度和空间复杂度之间虽然经常矛盾。但是二者不存在必然的联系。因此，选项 A、B、c的说法都是错误的。故本题的正确答案是 D。在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为A）63 B）64 C）6 D）7【答案】B【解析】在长度为 64的有序线性表中，其中的 64个数据元素是按照从大到小或从小到大的顺序排列有序的。在这样的线性表中进行顺序查找， 最坏的情况就是查找的数据元素不在线性表中或位于线性表的最后。按照线性表的顺序查找算法，首先用被查找的数据和线性表的第一个数据元素进行比较。若相等，则查找成功，否则，继续进行比较，即和线性表的第二个数据元素进行比较。同样，若相等，则查找成功，否则，继续进行比较。依次类推，直到在线性表中查找到该数据或查找到线性表的最后一个元素，算法才结束。因此，在长度为 64的有序线性表中进行顺序查找，最坏的情况下需要比较 64次。因此，本题的正确答案为B。对下列二叉树进行中序遍历的结果是A）ACBDFEG

B）ACBDFGEC）ABDCGEF

D）FCADBEGFC

EA

D

GB【答案】

A【解析】二叉树的中序遍历递归算法为：

如果根不空，则(1)

按中序次序访问左子树；

(2)访问根结点：

(3)按中序次序访问右子树。否则返回。本题中，根据中序遍历算法．应首先按照中序次序访问以

c为根结点的左子树，然后再访问根结点

F，最后才访问以

E为根结点的右子树。遍历以

c为根结点的左子树同样要遵循中序遍历算法，因此中序遍历结果为

ACBD；然后遍历根结点

F；遍历以

E为根结点的右子树，同样要遵循中序遍历算法，因此中序遍历结果为

EG。最后把这三部分的遍历结果按顺序连接起来，中序遍历结果为ACBDFEG。因此，本题的正确答案是 A。（25）数据的存储结构是指 ______。A）存储在外存中的数据 B）数据所占的存储空间量C）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示【答案】D【解析】数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，也称数据的物理结构。所以选项D正确。26）下列关于栈的描述中错误的是______。A）栈是先进后出的线性表B）栈只能顺序存储C）栈具有记忆作用D）对栈的插入与删除操作中，不需要改变栈底指针【答案】B【解析】本题考核栈的基本概念，我们可以通过排除法来确定本题的答案。栈是限定在一端进行插入与删除的线性表，栈顶元素总是最后被插入的元素，从而也是最先能被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素，即栈是按照“先进后出”或“后进先出”的原则组织数据的，这便是栈的记忆作用，所以选项 A和选项C正确。对栈进行插入和删除操作时，栈顶位置是动态变化的，栈底指针不变，选项 D正确。由此可见，选项 B的描述错误。（29）下列对于线性链表的描述中正确的是 ______。A）存储空间不一定是连续，且各元素的存储顺序是任意的B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的【答案】A【解析】在链式存储结构中，存储数据的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，数据元素之间的逻辑关系，是由指针域来确定的 。由此可见，选项 A的描述正确。（1）线性表若采用链式存储结构时，要求内存中可用存储单元的地址A）必须是连续的B）部分地址必须是连续的C）一定是不连续的D）连续不连续都可以解析： 在链式存储结构中，存储数据结构的存储空间可以是连续的，也可以是不连续的，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。故本题答案应该为选项 D）（2）在待排序的元素序列基本有序的前提下，效率最高的排序方法是A）冒泡排序B）选择排序C）快速排序D）归并排序解析： 从平均时间性能而言，快速排序最佳，其所需时间最少，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。 当序列中的记录基本有序或元素个数较少时，冒泡排序和简单选择排序为最佳排序方法，故本题答案应该为选项 A）。（3）下列叙述中，错误的是A）数据的存储结构与数据处理的效率密切相关B）数据的存储结构与数据处理的效率无关C）数据的存储结构在计算机中所占的空间不一定是连续的D）一种数据的逻辑结构可以有多种存储结构解析： 一般来说，一种数据结构根据需要可以表示成多种存储结构。常用的存储结构有顺序、链接、索引等，而采用不同的存储结构，其数据处理的效率是不同的； 一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系是有可能不同的。 故本题答案应该为选项 B）。（4）希尔排序属于A）交换排序B）归并排序C）选择排序D）插入排序解析： 希尔排序的基本思想是把记录按下标的一定增量分组，对每组记录使用插入排序，随增量的逐渐减小，所分成的组包含的记录越来越多，到增量的值减小到 1时，整个数据合成一组，构成一组有序记录，故其属于 插入排序方法 。故本题答案应该为选项 D）。（1）栈和队列的共同特点是A）都是先进先出B）都是先进后出C）只允许在端点处插入和删除元素D）没有共同点解析：栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。 二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种“后进先出”的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种“先进先出”的线性表。故本题答案应该为选项 C）。（2）已知二叉树后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是A）acbedB）decabC）deabcD）cedba解析： 依据后序遍历序列可确定根结点为 c；再依据中序遍历序列可知其左子树由空；又由左子树的后序遍历序列可知其根结点为 e，由中序遍历序列可知其左子树为如下图所示。求得该二叉树的前序遍历序列为选项 D）。

deba构成，右子树为d，右子树由 ba构成，（3）链表不具有的特点是A）不必事先估计存储空间B）可随机访问任一元素C）插入删除不需要移动元素D）所需空间与线性表长度成正比解析： 链表采用的是链式存储结构，它克服了顺序存储结构的缺点 ：它的结点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。但是链式存储结构也有不足之处：① 每个结点中的指针域需额外占用存储空间；② 链式存储结构是一种非随机存储结构。故本题答案应该为选项 D）。（6）算法的时间复杂度是指A）执行算法程序所需要的时间B）算法程序的长度C）算法执行过程中所需要的基本运算次数D）算法程序中的指令条数解析： 算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度。所谓算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度一般是指执行这个算法所需要的内存空间。故本题答案应该为选项 A）。（2）树是结点的集合，它的根结点数目是A）有且只有 1B）1或多于1C）0或1D）至少2解析： 树是一个或多个结点组成的有限集合，其中一个特定的结点称为根，其余结点分为若干个不相交的集合。每个集合同时又是一棵树。树有且只有 1个根结点。故本题答案应该为选项 A）。（3）如果进栈序列为 e1,e2,e3,e4 ，则可能的出栈序列是A）e3,e1,e4,e2B）e2,e4,e3,e1C）e3,e4,e1,e2D）任意顺序解析： 由栈"后进先出"的特点可知：A）中e1不可能比 e2先出，C）中e3不可能比 e4能比e2先出，D）中栈是先进后出的，所以不可能是任意顺序。 B）中出栈过程如图所示：

先出，且

e1不可故本题答案应该为选项 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）。（3）对长度为 N的线性表进行顺序查找，在最坏情况下所需要的比较次数为 ______。N+1N(N+1)/2N/2解析：[答案]B，很简单，我们的二级程序设计语言书中都有此算法，另外还要掌握二分法查找，这也是我们二级中常考的。那么二分法最坏的情况为多少次呢？

log2

n的最小整数值。比如

n为

4，最坏的情况要比较

3次；n为

18，最坏的情况要比较

5次。（1）下列叙述中正确的是A）线性表是线性结构B）栈与队列是非线性结构C）线性链表是非线性结构D）二叉树是线性结构解析： 线性表是一种线性结构，数据元素在线性表中的位置只取决于它们自己的序号，即数据元素之间的相对位置是线性的；栈、队列、线性链表实际上也是线性表，故也是线性结构； 树是一种简单的非线性结构。故本题答案应该为选项 A）。（3）已知数据表 A中每个元素距其最终位置不远，为节省时间，应采用的算法是A）堆排序B）直接插入排序C）快速排序D）直接选择排序解析： 当数据表 A中每个元素距其最终位置不远，说明数据表 A按关键字值基本有序，在待排序序列基本有序的情况下，采用插入排序所用时间最少，故答案为选项 B）。（2）算法分析的目的是A）找出数据结构的合理性B）找出算法中输入和输出之间的关系C）分析算法的易懂性和可靠性D）分析算法的效率以求改进解析： 算法分析是指对一个算法的运行时间和占用空间做定量的分析，一般计算出相应的数量级，常用时间复杂度和空间复杂度表示。分析算法的目的就是要降低算法的时间复杂度和空间复杂度，提高算法的执行效率。故本题答案应该为选项 D）。（1）算法的空间复杂度是指A）算法程序的长度B）算法程序中的指令条数C）算法程序所占的存储空间D）执行过程中所需要的存储空间解析： 算法的复杂度主要包括算法的时间复杂度和算法的空间复杂度。所谓算法的时间复杂度是指执行算法所需要的计算工作量；算法的空间复杂度一般是指执行这个算法所需要的内存空间。故本题答案应该为选项D）。（3）数据结构中，与所使用的计算机无关的是数据的A）存储结构B）物理结构C）逻辑结构D）物理和存储结构解析： 数据结构概念一般包括 3个方面的内容，数据的逻辑结构、存储结构及数据上的运算集合。数据的逻辑结构只抽象的反映数据元素之间的逻辑关系，而不管它在计算机中的存储表示形式。故本题答案应该为选项 C）。（2）设有两个串 p和q，求q在p中首次出现位置的运算称作A）连接B）模式匹配C）求子串D）求串长解析： 子串的定位操作通常称作串的模式匹配，是各种串处理系统中最重要的操作之一，算法的基本思想是：从主串的开始字符起和模式的第一个字符比较，若相等则继续比较后续字符，否则从主串的下一个字符起再重新和模式的字符比较，依次类推，直至模式中的每一个字符依次和主串中的一个连续的字符序列相等，称匹配成功，否则称匹配不成功。（3）下列关于队列的叙述中正确的是 ______。在队列中只能插入数据在队列中只能删除数据队列是先进先出的线性表队列是先进后出的线性表解析：C队列是先进先出的，栈是先进后出的， 2者的区别一定要搞清楚。算法的空间复杂度是指算法程序的长度算法程序中的指令条数C)执行算法程序所占的存储空间D)算法执行过程中所需要的存储空间【答案】D【解析】算法的空间复杂度一般是指这个算法执行时所需要的内存空间，其中包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，其中额外空间还包括算法程序执行过程的工作单元以及某种数据结构所需要的附加存储空间。（2）线性表的链式存储结构是一种随机结构顺序结构C)索引结构D)散列结构【答案】B【解析】线性表的链式存储结构中的每一个存储结点不仅含有一个数据元素，还包括指针，每一个指针指向一个与本结点有逻辑关系的结点。此类存储方式属于顺序存储。（3）设有下列二叉树：对此二叉树先序遍历的结果是A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA【答案】C【解析】二叉树的遍历分为先序、中序、后序三种不同方式。本题要求先序遍历；遍历顺序应该为：访问根结点

-＞先序遍历左子树

-＞先序遍历右子树。按照定义，先序遍历序列是

ABDECF。（3）已知数据表

A中每个元素距其最终位置不远，为节省时间，应采用的算法是

______。A）堆排序

B）直接插入排序C）快速排序

D）直接选择排序答案：

B评析：当数据表

A中每个元素距其最终位置不远，说明数据表

A按关键字值基本有序，在待排序序列基本有序的情况下，采用插入排序所用时间最少，故答案为选项

B。（4）用链表表示线性表的优点是

______。A）便于插入和删除操作 B）数据元素的物理顺序与逻辑顺序相同C）花费的存储空间较顺序存储少 D）便于随机存取答案：A评析：链式存储结构克服了顺序存储结构的缺点：它的结点空间可以动态申请和释放；它的数据元素的逻辑次序靠结点的指针来指示，不需要移动数据元素。故链式存储结构下的线性表便于插入和删除操作。5. 下列关于栈的叙述中正确的是 ______。A、在栈中只能插入数据B、在栈中只能删除数据C、栈是先进先出的线性表D、栈是先进后出的线性表解析:栈是限定在一端进行插入与删除的线性表。栈是按照

"先进后出

"的或后进先出的原则组织数据的，因此，栈也被称为

"先进后出

"表或"后进先出

"表。本题答案是 D。7. 对长度为 N的线性表进行顺序查找，在最坏情况下所需要的比较次数为A、N+1

______。B、NC、(N+1)/2D、N/2解析:在进行顺序查找过程中，如果线性表中被查的元素是线性表中的最后一个，或者被查元素根本不在线性表中，则为了查找这个元素需要与线性表中所有元素进行比较，这是顺序查找最坏的情况。本题答案为 B。在一棵二叉树上第5层的结点数最多是______。A、8B、16C、32D、15解析:根据二叉树的性质：二叉树第i（i≥1）层上至多有2i-1个结点。得到第5层的结点数最多是16。本题答案为B。7.在下列选项中，哪个不是一个算法一般应该具有的基本特征______。A、确定性B、可行性C、无穷性D、拥有足够的情报解析:作为一个算法，一般应具有以下几个基本特征。1)可行性2)确定性3)有穷性4)拥有足够的情报本题答案为C。在计算机中，算法是指______。A、查询方法B、加工方法C、解题方案的准确而完整的描述D、排序方法解析:计算机算法是指解题方案的准确而完整的描述，它有以下几个基本特征：可行性、确定性、有穷性和拥有足够的情报。本题答案为 C。在单链表中，增加头结点的目的是______。A、方便运算的实现B、使单链表至少有一个结点C、标识表结点中首结点的位置D、说明单链表是线性表的链式存储实现解析:头结点不仅标识了表中首结点的位置，而且根据单链表（包含头结点）的结构，只要掌握了表头，就能够访问整个链表，因此增加头结点目的是为了便于运算的实现。本题答案为 A。数据的存储结构是指______。A、存储在外存中的数据B、数据所占的存储空间量C、数据在计算机中的顺序存储方式D、数据的逻辑结构在计算机中的表示解析:本题考查的是数据结构的基本概念。数据的逻辑结构在计算机存储空间中的存放形式形式称为数据的存储结构（也称数据的物理结构）。故本题答案为 D。下列关于栈的描述中错误的是______。A、栈是先进后出的线性表B、栈只能顺序存储C、栈具有记忆作用D、对栈的插入与删除操作中，不需要改变栈底指针解析:本题考查的是栈和队列。栈是一种特殊的线性表，这种线性表只能在固定的一端进行插入和删除操作，允许插入和删除的一端称为栈顶，另一端称为栈底。一个新元素只能从栈顶一端进入，删除时，只能删除栈顶的元素，即刚刚被插入的元素。所以栈又称先进后出表（ FILO-FirstInLastOut ）。线性表可以顺序存储，也可以链式存储，而栈是一种线性表，也可以采用链式存储结构。故本题答案为 B。3. 对于长度为 n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是 ______。A、冒泡排序为

n/2B、冒泡排序为

nC、快速排序为

nD、快速排序为

n(n-1)/2解析:本题考查的是基本排序算法。假设线性表的长度为 n，则在最坏情况下，冒泡排序需要经过

n/2

遍的从前往后扫描和

n/2

遍的从后往前扫描，需要比较次数为 n(n-1)/2 。快速排序法的最坏情况比较次数也是故本题答案为 D。4. 对长度为 n的线性表进行顺序查找，在最坏情况下所需要的比较次数为

n(n-1)/2______。

。A、log2nB、n/2C、nD、n+1解析:本题考查的是顺序查找。在进行顺序查找过程中， 如果线性表中的第一个元素就是被查找元素， 则只需做一次比较就查找成功，查找效率最高；但如果被查找的元素是线性表中的最后一个元素， 或者被查找的元素根本就不在线性表中，则为了查找这个元素需要与线性表中所有的元素进行比较，这是顺序查找的最坏情况。所以对长度为 n的线性表进行顺序查找，在最坏情况下需要比较 n次。故本题答案为 C。5. 下列对于线性链表的描述中正确的是

______。A、存储空间不一定是连续，且各元素的存储顺序是任意的B、存储空间不一定是连续，且前件元素一定存储在后件元素的前面C、存储空间必须连续，且前件元素一定存储在后件元素的前面D、存储空间必须连续，且各元素的存储顺序是任意的解析:本题考查的是线性单链表、双向链表与循环链表的结构及其基本运算。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。故本题答案为 A。下列叙述中正确的是______。A、线性表是线性结构B、栈与队列是非线性结构C、线性链表是非线性结构D、二叉树是线性结构解析:根据数据结构中各数据元素之间前后间关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，又称线性表。所以线性表、栈与队列、线性链表都是线性结构，而二叉树是非线性结构。本题答案是 A。3. 设一棵完全二叉树共有 699个结点，则在该二叉树中的叶子结点数为 ______。A、349B、350C、255D、351解析:所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，

其父结点数为

int(n/2)

，而叶子结点数等于总结点数减去父结点数。

本题n=699，故父结点数等于

int(699/2)=349

，叶子结点数等于

699-349=350。本题答案是

B。下列关于栈的叙述中正确的是______。A、在栈中只能插入数据B、在栈中只能删除数据C、栈是先进先出的线性表D、栈是先进后出的线性表解析:栈是限定在一端进行插入与删除的线性表。栈是按照"先进后出"的或后进先出的原则组织数据的，因此，栈也被称为 "先进后出"表或"后进先出"表。本题答案是 D。3. 在深度为 5的满二叉树中，叶子结点的个数为 ______。A、32B、31C、16D、15解析:所谓满二叉树是指这样的一种二叉树：除最后一层外，每层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第K层上有2K-1个结点，且深度为m的满二叉树有2m个结点。在满二叉树中，最后一层的结点个数就是叶子结点的个数，本题中深度为5，故叶子结点数为25-1=24=16。本题答案是C。数据的存储结构是指______。A、数据所占的存储空间量B、数据的逻辑结构在计算机中的表示C、数据在计算机中的顺序存储方式D、存储在外存中的数据解析:数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构。本题答案为 B。设有下列二叉树：AB CD E F对此二叉树中序遍历的结果为 ______。A、ABCDEFB、DBEAFCC、ABDECFD、DEBFCA解析:所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。本题答案为 B。在计算机中，算法是指______。A、查询方法B、加工方法C、解题方案的准确而完整的描述D、排序方法解析:计算机算法是指解题方案的准确而完整的描述，它有以下几个基本特征：可行性、确定性、有穷性和拥有足够的情报。本题答案为 C。栈和队列的共同点是______。A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点解析:栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种 "后进先出"的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种 "先进先出"的线性表。本题答案为 C。已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是______。A、cedbaB、acbedC、decabD、deabc解析:依据后序遍历序列可确定根结点为 c；再依据中序遍历序列可知其左子树由 deba构成，右子树为空；又由左子树的后序遍历序列可知其根结点为 e，由中序遍历序列可知其左子树为 d，右子树由 ba构成。求得该二叉树的前序遍历序列为选项 A。本题答案为 A。1. 数据结构中，与所使用的计算机无关的是数据的 ______。A、存储结构B、物理结构C、逻辑结构D、物理和存储结构解析:数据结构概念一般包括3个方面的内容，数据的逻辑结构、存储结构及数据上的运算集合。数据的逻辑结构只抽象的反映数据元素之间的逻辑关系，而不管它在计算机中的存储表示形式。本题答案为 C。栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是______。A、ABCEDB、DBCEAC、CDABED、DCBEA解析: 栈操作原则是

"后进先出"，栈底至栈顶依次存放元素

A、B、C、D，则表明这

4个元素中

D是最后进栈，B、C处于中间，

A最早进栈。所以出栈时一定是先出

D，再出C，最后出A。本题答案为D。1.下面叙述正确的是

______。A、算法的执行效率与数据的存储结构无关B、算法的空间复杂度是指算法程序中指令（或语句）的条数C、算法的有穷性是指算法必须能在执行有限个步骤之后终止D、以上三种描述都不对解析:算法的设计可以避开具体的计算机程序设计语言，但算法的实现必须借助程序设计语言中提供的数据类型及其算法。数据结构和算法是计算机科学的两个重要支柱。它们是一个不可分割的整体。算法在运行过程中需辅助存储空间的大小称为算法的空间复杂度。算法的有穷性是指一个算法必须在执行有限的步骤以后结束。本题答案为 C。2. 设一棵完全二叉树共有 699个结点，则在该二叉树中的叶子结点数为 ______。A、349B、350C、255D、351解析:所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，

其父结点数为

int(n/2)

，而叶子结点数等于总结点数减去父结点数。

本题n=699，故父结点数等于本题答案是 B。

int(699/2)=349

，叶子结点数等于

699-349=350。9. 已知数据表

A中每个元素距其最终位置不远，为节省时间，应采用的算法是

______。A、堆排序B、直接插入排序C、快速排序D、直接选择排序解析:当数据表

A中每个元素距其最终位置不远，说明数据表

A按关键字值基本有序，在待排序序列基本有序的情况下，采用插入排序所用时间最少。本题答案为B。二、填空题（1）问题处理方案的正确而完整的描述称为_____。【答案】算法或程序或流程图【解析】算法是问题处理方案正确而完整的描述(2)对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为____。【答案】45【解析】在冒泡排序中，最坏情况下，需要比较的次数为n(n-1／2)，也就是：10*（lO-1)／2=45（3）算法复杂度主要包括时间复杂度和____【答案】空间【解析】算法的复杂度主要包括时间复杂度和空间复杂度。所谓算法的时间复杂度，是指执行算法所需要的计算工作量。一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。（4）一棵二叉树第六层（根结点为第一层）的结点数最多为_______【答案】32【解析】二叉树的一个性质是，在二叉树的第k-16-1k层上，最多有2(k≥1)个结点。此，2等于32。所以答案为32。（5）数据结构分为逻辑结构和存储结构，循环队列属于______结构。【答案】存储或物理或存储结构或物理结构【解析】数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。可知，循环队列应当是物理结构。(6)下列软件系统结构图的宽度为____。ABCDEF【答案】3【解析】题目中的图形是倒置的树状结构，这是用层次图表示的软件结构。结构图中同一层模块的最大模块个数称为结构的宽度，它表示控制的总分布。根据上述结构图宽度的定义，从图中可以看出，第二层的模块个数最多，即为

3。因此，这个系统结构图的宽度就为

3。(7)按“先进后出”原则组织数据的数据结构是

____

。【答案】栈或

Stack【解析】栈和队列是两种特殊的线性表，其特殊性在于对它们的操作只能在表的端点进行。栈中的数据按照后进先出的原则进行组织，而队列中的数据是按照先进先出的原则进行组织。因此，本题的正确答案是栈(Stack)。(8)数据结构分为线性结构和非线性结构，带链的队列属于 线性结构___ 。【答案】【解析】数据结构分为线性结构和非线性结构，其中队列是属于线性结构。队列有两种存储结构，一种是顺序存储结构，称为顺序队列；另一种是链式存储结构，称为链队列。题目中所说的带链的队列就是指链队列。无论队列采取哪种存储结构，其本质还是队列，还属于一种线性结构。因此，本题的正确答案是线性结构。(9) 在深度为 7的满二叉树中，度为 2的结点个数为_______。【答案】63或26-1【解析】本题考查数据结构中满二叉树的性质。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。深度为

k的满二叉树，一共有

2k-1

个结点，其中包括度为

2的结点。因此，深度为

7的满二叉树，一共有

27-1

个结点，即

127个结点。根据二叉树的另一条性质，对任意一棵二叉树，若终端结点（即叶子结点）数为

n0,

而其度数为

2的结点数为

n2则

n0=n2+1。设尝试为

7的满二叉树中，度为

2的结点个数为

x,则改树中中子结点的个数为

x+1。则应满足

x+(x+1)=127,

解该方程得到，

x的值为

63。结果上述分析可知，在深度为

7的满二叉树中，度为

2的结点个数为

63。线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的_____存储结构。【答案】顺序【解析】本题考查数据结构的队列。队列是一种特殊的线性表，即限定在表的一端进行删除，在表的另一端进行插入操作的线性表。允许删除的一端叫做队头，允许插入的一端叫做队尾。线性表的存储结构主要分为顺序存储结构和链式存储结构。当队列用链式存储结构实现时，就称为链队列；当队列用顺序存储结构实现时，就称为循环表。因此，本题划线处应填入“顺序”。对下列二叉树进行中序遍历的结果为____。【答案】ACBDFEHGP【解析】本题考查数据结构中二叉树的遍历。根据对二叉树根的访问先后顺序不同，分别称为前序遍历、中序遍历和后序遍历。这三种遍历都是递归定义的，即在其子树中也按照同样的规律进行遍历。下面就是中序遍历方法的递归定义。当二叉树的根不为空时，依次执行如下 3个操作：按中序遍历左子树。访问根结点。按中序遍历右子树。根据如上前序遍历规则，来遍历本题中的二叉树。首先遍历

F的左子树，同样按中序遍历。先遍历

C的左子树，即结点

A，然后访问

c，接着访问

c的右子树，同样按中序遍历

c的右子树，先访问结点

B，然后访问结点

D，因为结点

D没有右子树，因此遍历完

C的右子树，以上就遍历完根结点

F的左子树。然后访问根结点

F，接下来遍历

F的右子树．同样按中序遍历。首先访问

E的左子树，

E的左子树为空，则访问结点E，然后访问结点E的右子树，同样按中序遍历。首先访问G的左子树，即H，然后访问结点G，最后访问G的右子树P。以上就把整个二叉树遍历一遍，中序遍历的结果为ACBDFEHGP。因此．划线处应填入“ACBDFEHGP”。（11）用链表表示线性表的突出优点是。答案：插入和删除操作方便，不必移动数据元素，执行效率高解析：为了克服顺序表中插入和删除时需要移动大量数据元素的缺点，引入了链式存储结构。链表表示线性表的突出优点是插入和删除操作方便，不必移动数据元素，执行效率高。（11）算法的基本特征是可行性、确定性、和拥有足够的情报。答案：有穷性解析：算法是指解题方案的准确而完整的描述。它有4个基本特征，分别是可行性、确定性、有穷性和拥有足够的情报。（12）在长度为n的有序线性表中进行二分查找。最坏的情况下，需要的比较次数为。答案：log2n解析：对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。（11）数据结构分为逻辑结构与存储结构，线性链表属于存储结构。答案：解析：数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构；数据的存储结构是指数据的逻辑结构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。（11）冒泡排序算法在最好的情况下的元素交换次数为0。答案：0解析：根据冒泡排序算法思想可知，若待排序的初始序列为“正序”序列，则只需进行一趟排序，在排序过程中进行n-1次关键字间的比较，且不移动和交换记录，这种情况是冒泡排序的最好情况，故冒泡排序算法在最好的情况下的元素交换次数为 0。（12）在最坏情况下，堆排序需要比较的次数为 。n（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）在算法正确的前提下，评价一个算法的两个标准是 。答案：时间复杂度和空间复杂度（12）将代数式 转换成程序设计中的表达式为 。答案：(x+y*y)/(a+b)（11）数据的逻辑结构有线性结构和 两大类。答案：非线性结构解析： 数据的逻辑结构有线性结构和非线性结构两大类。（11）当线性表采用顺序存储结构实现存储时，其主要特点是 。答案：逻辑结构中相邻的结点在存储结构中仍相邻解析： 顺序存储结构的主要特点是数据元素按线性表的逻辑次序，依次存放在一组地址连续的存储单元中。在存储单元中各元素的物理位置和逻辑结构中各结点间的相邻关系是一致的。52. 设一棵完全二叉树共有 500个结点，则在该二叉树中有 ______个叶子结点。解析:所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其父结点数为题n=500，故父结点数等于 int(500/2)=250标准答案为： 250

int(n/2) ，而叶子结点数等于总结点数减去父结点数。本，叶子结点数等于 500-250=250。算法的基本特征是可行性、确定性、______和拥有足够的情报。解析:算法是指解题方案的准确而完整的描述。它有 4个基本特征，分别是可行性、确定性、有穷性和拥有足够的情报。标准答案为：有穷性52. 顺序存储方法是把逻辑上相邻的结点存储在物理位置 ______的存储单元中。解析:常用的存储表示方法有4种，顺序存储、链式存储、索引存储、散列存储。其中，顺序存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中。标准答案为：相邻（1）算法的复杂度主要包括空间复杂度和【时间 1】复杂度。【答案】时间【解析】算法的复杂度主要指时间复杂度和空间复杂度。（2）在线性结构中，队列的操作顺序是先进先出，而栈的操作顺序是【 2】。【答案】先进后出【解析】队列和栈都是线性结构，但是不同之处在于队列的操作顺序是先进先出，而栈的操作顺序是先进后出。（2）在最坏情况下，堆排序需要比较的次数为【2】。n答案：O(nlog2)评析：在最坏情况下，冒泡排序所需要的比较次数为n(n-1)/2；简单插入排序所需要的比较次数为n(n-1)/2；希尔排序所需要的比较次数为O（n1.5）；堆排序所需要的比较次数为O(nlogn2)。（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。51.实现算法所需的存储单元多少和算法的工作量大小分别称为算法的______。解析:算法的复杂性是指对一个在有限步骤内终止算法和所需存储空间大小的估计。算法所需存储空间大小是算法的空间复杂性，算法的计算量是算法的时间复杂性。标准答案为：空间复杂度和时间复杂度52. 数据结构包括数据的逻辑结构、数据的 ______以及对数据的操作运算。解析:数据结构包括 3个方面，即数据的逻辑结构、数据的存储结构及对数据的操作运算。标准答案为：存储结构53在最坏情况下，冒泡排序的时间复杂度为 ______。解析:冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为 n，则在最坏的情况下，冒泡排序需要经过 n/2遍的从前往后的扫描和从后往前的扫描，需要的比较次数为 n(n-1)/2 。

n/2

遍的标准答案为： n(n-1)/2 或n*(n-1)/2 或O(n(n-1)/2)54. 顺序存储方法是把逻辑上相邻的结点存储在物理位置

或O(n*(n-1)/2)______的存储单元中。解析:常用的存储表示方法有 4种，顺序存储、链式存储、索引存储、散列存储。其中，顺序存储方法是把逻辑上相邻的结点存储在物理位置也相邻的存储单元中。标准答案为：相邻52. 在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、 ______遍历和后序遍历。标准答案为：中序解析: 在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历和后序遍历。前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。中序遍历指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。后序遍历指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历右子树，然后访问根结点，最后遍历左子树；并且遍历左、右子树时，仍然先遍历右子树，然后访问根结点，最后遍历左子树。55. 数据结构包括数据的逻辑结构、数据的 ______以及对数据的操作运算。标准答案为：存储结构解析: 数据结构包括 3个方面，即数据的逻辑结构、数据的存储结构及对数据的操作运算。51. 某二叉树中度为

2的结点有

18个，则该二叉树中有

个叶子结点。标准答案为： 19解析:本题考查的是二叉树的定义及其存储结构。二叉树的性质 3：在任意一棵二叉树中，度为 0的结点（即叶子结点）总是比度为中度为2的结点数为 18，故叶子结点数为 18+1=19个。55. 问题处理方案的正确而完整的描述称为 。

2的结点多一个。本题标准答案为：算法 本题考查的是算法的基本概念。解析:所谓算法是指解题方案的准确而完整的描述。51. 在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、

______遍历和后序遍历。标准答案为：中序解析:在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历和后序遍历。前序遍历是指在访问根结点、 遍历左子树与遍历右子树这三者中， 首先访问根结点， 然后遍历左子树，最后遍历右子树；并且遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。中序遍历指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。后序遍历指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历右子树，然后访问根结点，最后遍历左子树；并且遍历左、右子树时，仍然先遍历右子树，然后访问根结点，最后遍历左子树。51. 设一棵完全二叉树共有 500个结点，则在该二叉树中有 ______个叶子结点。标准答案为： 250解析:所谓完全二叉树是指除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其父结点数为

int(n/2)

，而叶子结点数等于总结点数减去父结点数。本题n=500，故父结点数等于

int(500/2)=250

，叶子结点数等于

500-250=250。52. 在最坏情况下，冒泡排序的时间复杂度为

______。标准答案为： n(n-1)/2 或n*(n-1)/2 或O(n(n-1)/2) 或O(n*(n-1)/2)解析:冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为 n，则在最坏的情况下，冒泡排序需要经过 n/2遍的从前往后的扫描和从后往前的扫描，需要的比较次数为 n(n-1)/2 。

n/2

遍的第二章 程序设计基础一、选择题（1）下列叙述中正确的是A）程序设计就是编制程序 B）程序的测试必须由程序员自己去完成C）程序经调试改错后还应进行再测试 D）程序经调试改错后不必进行再测试【答案】C【解析】软件测试仍然是保证软件可靠性的主要手段，测试的目的是要尽量发现程序中的错误，调试主要是推断错误的原因，从而进一步改正错误。测试和调试是软件测试阶段的两个密切相关的过程，通常是交替进行的。选项 C正确。下面描述中，不符合结构化程序设计风格的是A）使用顺序、选择和重复（循环）三种基本控制结构表示程序的控制逻辑B）注重提高程序的可读性D）使用goto语句【答案】 D【解析】在结构化程序设计中，应严格控制使用 GOTO语句，必要时才可以使用，故答案为 D。在面向对象设计中，对象有很多基本特点，其中“从外面看只能看到对象的外部特性，而对象的内部对外是不可见的”这一性质指的是对象的A）分类性 B）标识惟一性 C）多态性 D）封装性【答案】D【解析】从外面看只能看到对象的外部特性，而对象的内部，即处理能力的实行和内部状态，指的是对象的封装性。结构化程序设计的一种基本方法是A）筛选法 B）递归法 C）归纳法 D）逐步求精法【答案】D【解析】在结构化程序设计中通常采取自上而下、逐步求精的方法，其总的思想是先全局后局部、先整体后细节、先抽象后具体。而筛选法、递归法和归纳法指的都是程序的某种具体算法。函数重载是指A）两个或两个以上的函数取相同的函数名，但形参的个数或类型不同B）两个以上的函数取相同的名字和具有相同的参数个数，但形参的类型可以不同C）两个以上的函数名字不同，但形参的个数或类型相同D）两个以上的函数取相同的函数名，并且函数的返回类型相同【答案】A【解析】函数重载指的是两个或两个以上的函数具有相同的函数名，但形参的个数或类型不同。程序中通过判断主调函数传过来的参数的个数和类型，来决定选择调用哪个具体的函数。下列选项中不符合良好程序设计风格的是A）源程序要文档化B）数据说明的次序要规范化C）避免滥用 goto 语D）模块设计要保证高耦合、高内聚【答案】D【解析】编程风格是在不影响性能的前提下，有效地编排和组织程序，以提高可读性和可维护性。更直接的说，风格就是意味着要按照规则进行编程。这些规则包括：程序文档化。就是程序文档包含恰当的标识符．适当的注解和程序的视觉组织等。 （2）数据说明。出于阅读理解和维护的需要，最好使模块前的说明语句次序规范化。此外，为方便查找，在每个说明语句的说明符后，数据名应按照字典顺序排列。

(3)功能模块化。即把源程序代码按照功能划分为低耦合、高内聚的模块。

(4)注意

goto

语句的使用。合理使用goto

语句可以提高代码的运行效率．但

goto

语句的使用会破坏程序的结构特性。因此，除非确实需要，否则最好不使用 goto语，因此，本题的正确答案是 D。(7) 在结构化程序设计中，模块划分的原则是 ( )各模块应包括尽量多的功能各模块的规模应尽量大C)各模块之间的联系应尽量紧密D)模块内具有高内聚度、模块间具有低耦合度【答案】D【解析】本题考查软件工程中软件设计的概念和原理。人们在开发计算机软件的长期实践中积累了丰富的经验，总结这些经验得到如下的启发式规则：改进软件结构，提高模块独立性。通过模块的分解或合并，力求降低耦合提高内聚。低耦合也就是降低不同模块间相互依赖的紧密程度，高内聚是提高一个模块内各元素彼此结合的紧密程度。模块的规模应适中。一个模块的规模不应过大，过大的模块往往是由于分解不够充分；过小的模块开销大于有益操作，而且模块过多将使系统接口复杂。因此过小的模块有时不值得单独存在。模块的功能应该可以预测，但也要防止模块功能过分局限。如果模块包含的功能太多，则不能体现模块化设计的特点；如果模块的功能过分的局限，使用范围就过分狭窄。经过上述分析，本题的正确答案是选项 D。(8) 下面选项中不属于面向对象程序设计特征的是 ( )A)继承性 B)多态性 C)类比性 D)封装性【答案】C【解析】通常认为，面向对象方法具有封装性、继承性、多态性几大特点。就是这几大特点，为软件开发提供了一种新的方法学。封装性：所谓封装就是将相关的信息、操作与处理融合在一个内含的部件中(对象中)。简单地说，封装就是隐藏信息。这是面向对象方法的中心，是面向对象程序设计的基础。继承性：子类具有派生它的类的全部属性(数据)和方法，而根据某一类建立的对象也都具有该类的全部，这就是继承性。继承件自动在类与子类间共享功能与数据，当某个类作了某项修改，其子类会自动改变，子类会继承其父类所有特性与行为模式，继承有利于提高软件开发效率，容易达到一致性。多态性：多态性就是多种形式。不同的对象在接收到相同的消息时，采用不同的动作。例如，一个应用程序包括许多对象，这些对象也许具有同一类型的工作，但是却以不同的做法来实现。不必为每个对象的过程取一过程名，造成复杂化，可以使过程名复用。同一类型的工作有相同的过程名，这种技术称为多态性。经过上述分析可知，选项 C的说法是错误的。在面向对象方法中，实现信息隐蔽是依靠()A)对象的继承 B) 对象的多态C)对象的封装 D) 对象的分类【答案】c【解析】通常认为，面向对象方法具有封装性、继承性、多态性几大特点。就是这几大特点，为软件开发提供了一种新的方法学。封装性：所谓封装就是将相关的信息、操作与处理融合在一个内含的部件中（对象中 )。简单地说，封装就是隐藏信息。这是面向对象方法的中心，也是面向对象程序设计的基础。继承性：子类具有派生它的类的全部属性 (数据)和方法，而根据某一类建立的对象也都具有该类的全部，这就是继承性。继承性自动在类与子类间共享功能与数据，当某个类作了某项修改，其子类会自动改变，子类会继承其父类所有特性与行为模式。继承有利于提高软件开发效率，容易达到一致性。多态性；多态性就是多种形式。不同的对象在接收到相同的消息时，采用不同的动作。例如，一个应用程序包括许多对象，这些对象也许具有同一类型的工作．但是却以不同的做法来实现。不必为每个对象的过程取一过程名，造成复杂化，可以使过程名复用。同一类型的工作有相同的过程名，这种技术称为多态性。经过上述分析可知，在面向对象方法中，实现信息隐蔽是依靠对象的封装。正确答案是选项 c。下列叙述中，不符合良好程序设计风格的是()A)程序的效率第一，清晰第二B)程序的可读性好C)程序中有必要的注释 D) 输入数据前要有提示信息【答案】A【解析】本题考查软件工程的程序设计风格。软件在编码阶段，力求程序语句简单、直接，不能只为了追求效率而使语句复杂化。除非对效率有特殊的要求，程序编写要做到清晰第一、效率第二。人们在软件生存期要经常阅读程序，特别是在软件测试和维护阶段，编写程序的人和参与测试、维护的人都要阅读程序，因此要求程序的可读性要好。正确的注释能够帮助读者理解程序，可为后续阶段进行测试和维护提供明确的指导。所以注释不是可有可无的，而是必须的，它对于理解程序具有重要的作用。I/O信息是与用户的使用直接相关的， 因此它的格式应当尽可能方便用户的使用。 在以交互式进行输入／输出时，要在屏幕上使用提示符明确提示输入的请求，指明可使用选项的种类和取值范围。经过上述分析可知，选项 A是不符合良好程序设计风格要求的。（11）结构化程序设计的 3种结构是A）顺序结构、选择结构、转移结构B）分支结构、等价结构、循环结构C）多分支结构、赋值结构、等价结构D）顺序结构、选择结构、循环结构解析： 顺序结构、选择结构和循环结构（或重复结构）是结构化程序设计的 3种基本结构。故本题答案应该为选项 D）。12）在结构化程序设计思想提出之前，在程序设计中曾强调程序的效率，现在，与程序的效率相比，人们更重视程序的A）安全性B）一致性C）可理解性D）合理性答案：C（13）对建立良好的程序设计风格，下面描述正确的是A）程序应简单、清晰、可读性好B）符号名的命名只要符合语法C）充分考虑程序的执行效率D）程序的注释可有可无解析： 程序设计应该简单易懂，语句构造应该简单直接，不应该为提高效率而把语句复杂化。故本题答案应该为选项 A）。（14）结构化程序设计主要强调的是A）程序的规模B）程序的效率C）程序设计语言的先进性D）程序易读性解析： 结构化程序设计方法的主要原则可以概括为自顶向下、逐步求精、模块化及限制使用 goto语句，总的来说可使程序结构良好、易读、易理解、易维护。故本题答案应该为选项 D）。（15）对象实现了数据和操作的结合，是指对数据和数据的操作进行A）结合B）隐藏C）封装D）抽象解析： 对象是由数据及可以对这些数据施加的操作组成的统一体。对象的内部，即处理能力的实行和内部状态，对外是看不见的，这一特性称做对象的封装。故本题答案应该为选项 C）。4）编制一个好的程序，首先要保证它的正确性和可靠性，还应强调良好的编程风格，在书写功能性注释时应考虑仅为整个程序作注释仅为每个模块作注释C)为程序段作注释D)为每个语句作注释【答案】C【解析】功能性注释是嵌在源程序体中的，用以描述其后的语句或程序段是在做什么工作，或者执行了下面的语句会怎么样。所以它描述的是一段程序，是为程序段做注释，而不是每条语句。（5）下列哪个是面向对象程序设计不同于其他语言的主要特点？继承性消息传递C)多态性D)静态联编【答案】A【解析】继承是一个子类直接使用父类的所有属性和方法。它可以减少相似的类的重复说明，从而体现出一般性与特殊性的原则，这使得面向对象程序设计语言有了良好的重用性，也是其不同于其他语言的主要特点。结构化程序设计主要强调的是______。A、程序的规模B、程序的易读性C、程序的执行效率D、程序的可移植性解析:结构化程序设计主要强调的是结构化程序清晰易读，可理解性好，程序员能够进行逐步求精、程序证明和测试，以保证程序的正确性。本题答案为 B。2. 下面概念中，不属于面向对象方法的是 ______。A、对象B、继承C、类D、过程调用解析:面向对象方法是一种运用对象、类、封装、继承、多态