A ）所谓算法就是计算方法
B ）程序可以作为算法的一种描述方法
C ）算法设计只需考虑得到计算结果
D ）算法设计可以忽略算法的运算时间
题目解析:算法是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程, 重在解题方案的设计，并且不等于计算方法，故A 和C 选项不正确，程序的编制不可能优于算法的设计，但算法的描述可以用程序、伪代码、流程图来描述，故B 选项正确。算法要求执行过程中所需要的基本运算次数和时间最少，即时间复杂度最低，所以C 选项不正确。正确答案为B 。
2. 下列各序列中不是堆的是（ ）。答案：C
A ）(91,85,53,36,47,30,24,12)
B ）(91,85,53,47,36,30,24,12)
C ）(47,91,53,85,30,12,24,36)
D ）(91,85,53,47,30,12,24,36)
题目解析:堆可以看成一棵完全二叉树：任一根节点>=左右孩子（或者
3. 深度为5的完全二叉树的结点数不可能是（ ）。答案：A
A ）15
B ）16
C ）17
D ）18
题目解析:对于满二叉树，叶子结点的数目等于2（n-1）,n 为深度，这里就是2的5-1=4次方，就是16。
4. 设二叉树如下：
则前序序列为（ ）。答案：A
A ）ABDEGCFH
B ）DBGEAFHC
C ）DGEBHFCA
D ）ABCDEFGH
题目解析:前序遍历首先访问根结点然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故正确选项选A ；B 选项为中序遍历。C 选项为后序遍历；D 选项不正确。
A ）循环队列是顺序存储结构
B ）循环队列是链式存储结构
C ）循环队列是非线性结构
D ）循环队列的插入运算不会发生溢出现象
题目解析:循环队列属于队列的特例和栈同属于线性结构，C 选项不正确。在顺序队列中, 由于数组空间不够而产生的溢出叫真溢出；顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出；假溢出是由于队尾rear 的值和队头front 的值不能由所定义数组下界值自动转为数组上界值而产生的，解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列，因此，顺序队列通常都采用顺序循环队列结构；栈的存储方式有顺序存储和链式存储，故正确选项为A ；B 选项不正确。循环队列虽然能解决由于假溢出，却不能解决在顺序队列中, 由于数组空间不够而产生的溢出的真溢出，故选项C 不正确。
6. 下列叙述中正确的是（ ）。答案：D
A ）所有数据结构必须有根结点
B ）所有数据结构必须有终端结点（即叶子结点）
C ）只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构
D ）没有根结点或没有叶子结点的数据结构一定是非线性结构
题目解析:只有一个空节点的结构也属数据结构，所以A 和B 选项不正确；有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件的数据结构才属于线性结构，其它的都属于非线性结构，故C 选项不正确，正确选项为D 。
7. 下列关于算法的描述中错误的是（ ）。答案：D
A ）算法强调动态的执行过程，不同于静态的计算公式
B ）算法必须能在有限个步骤之后终止
C ）算法设计必须考虑算法的复杂度
D ）算法的优劣取决于运行算法程序的环境
题目解析:算法的优劣取决自身的运行效率，时间和空间复杂度高低，并不取决于运行算法程序的环境，故D 选项错误。
8. 设二叉树如下：
则中序序列为（ ）。答案：B
A ）ABDEGCFH
B ）DBGEAFHC
C ）DGEBHFCA
D ）ABCDEFGH
题目解析:中序遍历（LDR ）是指首先遍历左子树，然后访问根结点，最后遍历右子树；故
正确答案为B 。
9. 线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有（ ）。答案：B
A ）节省存储空间
B ）插入与删除运算效率高
C ）便于查找
D ）排序时减少元素的比较次数
题目解析:顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（＝1），存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 优点：插入或删除元素时很方便效率高，使用灵活。缺点：存储密度小（
10. 深度为７的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为（ ）。答案：B
A ）62
B ）63
C ）64
D ）65
题目解析: 对于满二叉树，结点的数目等于2n-1，叶子结点数目为2n-1，n 为深度，这里就是2的7次方-1，就是127个结点，叶子结点是64个，然而题目中只有125个结点，说明少了两个结点，那么就少了一个叶子结点，即63个。
11. 下列叙述中正确的是（ ）。答案：C
A ）所谓有序表是指在顺序存储空间内连续存放的元素序列
B ）有序表只能顺序存储在连续的存储空间内
C ）有序表可以用链接存储方式存储在不连续的存储空间内
D ）任何存储方式的有序表均能采用二分法进行查找
题目解析:有序表可以用顺序存储空间内连续存放的元素序列来实现，也可以用链接存储方式存储在不连续的存储空间内，已达到逻辑上连续，存储空间上不一定连续的效果。二分法进行查找只适用于顺序存储的有序表。故选项C 正确。
12. 设二叉树如下：
则后序序列为（ ）。答案：C
A ）ABDEGCFH
B ）DBGEAFHC
C ）DGEBHFCA
D ）ABCDEFGH
题目解析:后序遍历（LRD ）首先遍历左子树，然后访问遍历右子树，最后访问根结点。故正确选项为C 。
13. 下列叙述中正确的是（ ）。答案：B
A ）结点中具有两个指针域的链表一定是二叉链表
B ）结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构
C ）二叉树只能采用链式存储结构
D ）循环链表是非线性结构
题目解析:结点中尽管有两个指针域但没有分别指向两个不同的结点就不是二叉链表，故A 选项不正确；二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序存储结构和链式存储结构，故C 选项不正确；循环链表是在单链表中，将终端结点的指针域NULL 改为指向表头结点或开始结点的线性结构，故D 选项不正确；当结点中两个指针分别指向前驱结点和后继结点是为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，故B 选项正确。
14. 设某二叉树中共有140个结点，其中有40个度为1的结点。则（ ）。答案：D
A ）该二叉树中有51个叶子结点
B ）该二叉树中有50个叶子结点
C ）该二叉树中有51个度为2的结点
D ）不可能有这样的二叉树
题目解析:140个结点除去40个度为1的结点，说明有100个度为2的结点，而根据二叉树性质，这个数值无法得出故本题答案选D 。
15. 带链的栈与顺序存储的栈相比，其优点是（ ）。答案：C
A ）入栈与退栈操作方便
B ）可以省略栈底指针
C ）入栈操作时不会受栈存储空间的限制而发生溢出
D ）以上都不对
题目解析:带链的栈与顺序存储的栈相比优点是不受连续存储空间大小的限制，即不需考虑栈满的问题，故C 选项正确。
16. 某二叉树的前序序列为ABCD ，中序序列为DCBA ，则后序序列为（ ）。答案：B
A ）BADC
B ）DCBA
C ）CDAB
D ）ABCD
题目解析:在二叉树前序遍历中ABCD 中A 是根节点，二在后序遍历中根结点位于最后，所以正确答案为B 。
17. 某系统结构图如下所示
该系统结构图的最大扇入数是（ ）。答案：A
A ）n
B ）1
C ）2
D ）3
题目解析:系统结构图中的最大扇入数为系统图中进入某一节点的最大节点数，本系统图中功能n.1节点输出节点为功能1到功能n, 所以系统结构图的最大扇入数为n, 故正确选项为A 。
18. 下列关于算法复杂度叙述正确的是（ ）。答案：B
A ）最坏情况下的时间复杂度一定高于平均情况的时间复杂度
B ）时间复杂度与所用的计算工具无关
C ）对同一个问题，采用不同的算法，则它们的时间复杂度是相同的
D ）时间复杂度与采用的算法描述语言有关
题目解析:准确把握算法复杂度的概念。
19. 设有栈S 和队列Q ，初始状态均为空。首先依次将A,B,C,D,E,F 入栈，然后从栈中退出三个元素依次入队，再将X,Y ,Z 入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为（ ）。答案：B
A ）DEFXYZABC
B ）FEDZYXCBA
C ）FEDXYZCBA
D ）DEFZYXABC
题目解析:栈是一种特殊的线性表栈中的数据时按照先进后出或者是后进先出的规则进行的，队列是同栈不太相同的线性结构，进出顺序为先进先出的规则，根据题意要求本题正确答案为B 选项。
20. 下列叙述中正确的是（ ）。答案：D
A ）有两个指针域的链表称为二叉链表
B ）循环链表是循环队列的链式存储结构
C ）带链的栈有栈顶指针和栈底指针，因此又称为双重链表
D ）结点中具有多个指针域的链表称为多重链表
题目解析:结点中尽管有两个指针域但没有分别指向两个不同的结点就不是二叉链表，故A 选项不正确；循环链表是在单链表中，将终端结点的指针域NULL 改为指向表头结点或开始结点的线性结构，故B 选项不正确；当结点中两个指针分别指向前驱结点和后继结点是为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，故B 选项正确。双重链表的结点有两个指针，一个指向前驱，一个指向后继，从一个结点既可以向前也可以向后才是双重链表，故C 选项不正确。D 选项正确。
21. 某二叉树共有845个结点，其中叶子结点有45个，则度为1的结点数为（ ）。答案：C
A ）400
B ）754
C ）756
D ）不确定
题目解析:二叉树中，度为0的结点（即叶子节点）比度为2的结点多1个，而度为0、1、2的结点相加等于总结点数845，所以度为1的结点数为845-45-（45-1）=756。
22. 深度为7的二叉树共有127个结点，则下列说法中错误的是（ ）。答案：A
A ）该二叉树有一个度为1的结点
B ）该二叉树是满二叉树
C ）该二叉树是完全二叉树
D ）该二叉树有64个叶子结点
题目解析:大家一定要记清楚这几个二叉树的性质。
23. 下列叙述中正确的是（ ）。答案：D
A ）非线性结构只能采用链式存储结构
B ）非线性结构只能用多重链表表示
C ）所有数据结构既可以采用顺序存储结构，也可以采用链式存储结构
D ）有的非线性结构也能采用顺序存储结构
题目解析:链式存储方式即可用于表示线性结构，也可用于表示非线性结构，非线性结构也可以用连续存储空间顺序存储。所以AB 选项不正确在所有的数据结构中并非所有的结构都能用顺序存储结构和采用链式存储结构表示，故选项C 不正确，D 选项正确。
24. 某二叉树的中序序列为BDCA ，后序序列为DCBA ，则前序序列为（ ）。答案：C
A ）DCBA
B ）BDCA
C ）ABCD
D ）BADC
题目解析:在二叉树后序遍历中DCBA 中A 是根节点，二在前序遍历中根结点位于首位，所以正确答案为B 。
25. 某系统结构图如下图所示
该系统结构图的最大扇出数是（ ）。答案：D
A ）1
B ）2
C ）3
D ）n
题目解析: 系统结构图中的最大扇出数为系统图中某一节点输出的最大节点数，本系统图中某系统输出节点为功能1到功能n, 所以系统结构图的最大扇入数为n, 故正确选项为D 。
26. 设有序线性表的长度为n ，则在有序线性表中进行二分查找，最坏情况下的比较次数为（ ）。答案：D
A ）n(n-1)/2
B ）n
C ）nlog2 n
D ）log2 n
题目解析:二分法查找只适用于顺序存储的有序表，对于长度为n 的有序线性表，最坏情况只需比较log2n 次，而顺序查找需要比较n 次。故正确选项为D 。
27. 某完全二叉树共有256个结点，则该完全二叉树的深度为（ ）。答案：C
A ）7
C ）9
D ）10
题目解析: 根据" 二叉树的第i 层至多有2^(i ? 1) 个结点；深度为k 的二叉树至多有2^k ? 1个结点（根结点的深度为1）". 这个性质：因为前九层的结点就有2^9-1=511个；而第九层的结点数是2^(9-1)=256。
28. 设序列长度为n, 在最坏情况下比较次数低于O （n2）的排序方法是（ ）。答案：D
A ）快速排序
B ）直接插入排序
C ）冒泡排序
D ）希尔排序
题目解析:大家一定要熟悉这几种排序方法的性质。
29. 某二叉树的前序序列为ABCD ，中序序列为BDCA ，则该二叉树的深度为（ ）。答案：A
A ）4
B ）3
C ）2
D ）不确定
题目解析:首先还原二叉树，然后再次进行排序。
30. 下列排序方法中，最坏情况下时间复杂度最低的是（ ）。答案：D
A ）冒泡排序
B ）快速排序
C ）希尔排序
D ）堆排序
题目解析:堆排序法，最坏情况需要O(nlog2n)次比较。 相比以上几种(除希尔排序法外) ，堆排序法的时间复杂度最小，故D 选项正确。
31. 设循环队列为Q(1:m)，初始状态为front=rear=m。现经一系列入队与退队操作后，front=rear=m-1，则（ ）。答案：D
A ）该循环队列已空
B ）该循环队列已满
C ）该循环队列中有1个元素
D ）该循环队列已空或已满
题目解析:循环队列m=0表示队列空；s=1且front=rear表示队列满。所以选项D 正确。
32. 设序列长度为n ，在最坏情况下，时间复杂度为O （log2n ）的算法是（ ）。答案：A
A ）二分法查找
B ）顺序查找
C ）分块查找
D ）哈希查找
题目解析:二分法查找只适用于顺序存储的有序表，对于长度为n 的有序线性表，最坏情况只需比较log2n 次，而顺序查找需要比较n 次。故正确选项为A 。
33. 某二叉树的深度为7，其中有64个叶子结点，则该二叉树中度为1的结点数为（ ）。答案：A
A ）0
B ）1
D ）63
题目解析:2的7-1次方已经是64了，所以度为1的结点一定是0。
34. 堆排序最坏情况下的时间复杂度为（ ）。答案：B
A ）O(n1.5)
B ）O(nlog2n)
C ）
D ）O(log2n)
题目解析:堆排序法，最坏情况需要O(nlog2n)次比较，堆排序法的时间复杂度最小，故B 选项正确。
35. 在线性表的链式存储结构中，其存储空间一般是不连续的，并且（ ）。答案：C
A ）前件结点的存储序号小于后件结点的存储序号
B ）前件结点的存储序号大于后件结点的存储序号
C ）前件结点的存储序号可以小于也可以大于后件结点的存储序号
D ）以上都不对
题目解析:链式存储结构使得节点在内存中不收位置的限制，结点存储号可以是任意的，并且能够保证逻辑上的线性关系。故C 选项正确。
36. 某二叉树中有15个度为1的结点，16个度为2的结点，则该二叉树中总的结点数为（ ）。答案：C
A ）32
B ）46
C ）48
D ）49
题目解析:二叉树有一个性质是：对任何二叉树，如果其终端结点数位n0，度为2的结点数为n2则n0=n2+1，所以度为0的一共有17个，总的结点数即时17+15+16=48个。
37. 某系统结构图如下图所示
该系统结构图中最大扇入是（ ）。答案：C
A ）0
B ）1
C ）2
D ）3
题目解析: 系统结构图中的最大扇入数为系统图中输入某一节点的最大节点数，本系统图中某系统输入节点为功能1到功能3n, 所以系统结构图的最大扇入数为3, 故正确选项为C 。
38. 下列叙述中正确的是（ ）。答案：D
A ）每一个结点有两个指针域的链表一定是非线性结构
B ）所有结点的指针域都为非空的链表一定是非线性结构
C ）循环链表是循环队列的链式存储结构
D ）线性结构的存储结点也可以有多个指针
题目解析:当结点中两个指针分别指向前驱结点和后继结点是为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，指针域为非空的链表也可以是线性结构，链式存储方式即可用于表示线性结构，也可用于表示非线性结构。故A 、B 、C 选项不完全正确。线性结构的存储结点可以由多个指针只有保证有且只有指向一个前驱结点和一个后继结点就是线性结构。故D 选项正确；。
39. 在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数（ ）。答案：A
A ）相同，元素的存储顺序与逻辑顺序一致
B ）相同，但其元素的存储顺序可以与逻辑顺序不一致
C ）不同，但元素的存储顺序与逻辑顺序一致
D ）不同，且其元素的存储顺序可以与逻辑顺序不一致
题目解析:线性表的顺序存储结构的两个特点（1）线性表中所有元素所占的存储空间是连续的；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。另在线性表中数据元素所占的字节数都是一致的，所以正确选项为A 。
40. 设循环队列为Q(1: m)，其初始状态为front=rear=m。经过一系列入队与退队运算后， front=30，rear=10。现要在该循环队列中作顺序查找，最坏情况下需要比较的次数为（ ）。答案：D
A ）19
B ）20
C ）m-19
D ）m-20
题目解析:二分法查找只适用于顺序存储的有序表，对于长度为n 的有序线性表，最坏情况只需比较log2n 次，而顺序查找需要比较n 次。已知循环队列为Q(1: m) ，其初始状态为front=rear=m，而节点个数为m-(front-rear),且顺序查找的比较次数与实际节点个数一致，故正确选项为D 。
41. 某二叉树中共有935个结点，其中叶子结点有435个，则该二叉树中度为2的结点个数为（ ）。答案：D
A ）64
B ）66
C ）436
D ）434
题目解析:大家记住一个公式，n0=n2+1，所以n2有434个。
42. 某系统结构图如下图所示
该系统结构图中最大扇出数是（ ）。答案：C
A ）1
B ）23
C ）3
D ）4
题目解析:系统结构图中的最大扇出数为系统图中某一节点输出的最大节点数，本系统图中某系统输出节点为功能1到功能3, 所以系统结构图的最大扇入数为3, 故正确选项为C 。
43. 算法的有穷性是指（ ）。答案：A
A ）算法程序的运行时间是有限的
B ）算法程序所处理的数据量是有限的
C ）算法程序的长度是有限的
D ）算法只能被有限的用户使用
题目解析:算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。有穷性是指算法程序的运行时间是有限的。
44. 对长度为n 的线性表排序，在最坏情况下，比较次数不是n(n－1)/2的排序方法是（ ）。答案：D
A ）快速排序
B ）冒泡排序
C ）直接插入排序
D ）堆排序
题目解析:在最坏的情况下，堆排序需要比较的次数为O(nlog2n) ，所以选择D.
45. 下列关于栈的叙述正确的是（ ）。答案：B
A ）栈按" 先进先出" 组织数据
B ）栈按" 先进后出" 组织数据
C ）只能在栈底插入数据
D ）不能删除数据
题目解析:栈是按照" 先进后出" 的原则组织数据的，只能在栈顶插入或删除数据，所以选择B 。
46. 一个栈的初始状态为空。现将元素1、2、3、4、5、A 、B 、C 、D 、E 依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。答案：B
A ）12345ABCDE
B ）EDCBA54321
C ）ABCDE12345
D ）54321EDCBA
题目解析:栈是先进后出的原则组织数据，所以入栈最早的最后出栈，所以选择B 。
47. 下列叙述中正确的是（ ）。答案：D
A ）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构
B ）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况
C ）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况
D ）循环队列中元素的个数是由队头指针和队尾指针共同决定
题目解析:循环队列有队头和队尾两个指针，但是循环队列仍是线性结构的，所以A ）错误；在循环队列中只需要队头指针与队尾两个指针来共同反映队列中元素的动态变化情况，所以B ）与
C ）错误。
48. 在长度为n 的有序线性表中进行二分查找，最坏情况下需要比较的次数是（ ）。答案：C
A ）O(n)
B ）
C ）
D ）
题目解析:当有序线性表为顺序存储时才能用二分法查找。可以证明的是对于长度为n 的有序线性表，在最坏情况下，二分法查找只需要比较O(nlog2n) 次，而顺序查找需要比较n 次。
49. 下列叙述中正确的是（ ）。答案：A
A ）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的
B ）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构
C ）顺序存储结构能存储有序表，链式存储结构不能存储有序表
D ）链式存储结构比顺序存储结构节省存储空间
题目解析:链式存储结构既可以针对线性结构也可以针对非线性结构，所以B ）与C ）错误。链式存储结构中每个结点都由数据域与指针域两部分组成，增加了存储空间，所以D ）错误。
50. 在数据管理技术发展的三个阶段中，数据共享最好的是（ ）。答案：C
A ）人工管理阶段
B ）文件系统阶段
C ）数据库系统阶段
D ）三个阶段相同
题目解析:据管理发展至今已经历了三个阶段：人工管理阶段、文件系统阶段和数据库系统阶段。其中最后一个阶段结构简单，使用方便逻辑性强物理性少，在各方面的表现都最好，一直占据数据库领域的主导地位，所以选择C ）。
51. 下列叙述中正确的是（ ）。答案：D
A ）栈是" 先进先出" 的线性表
B ）队列是" 先进后出" 的线性表
C ）循环队列是非线性结构
D ）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构
题目解析:栈是先进后出的线性表，所以A ）错误；队列是先进先出的线性表，所以B ）错误；循环队列是线性结构的线性表，所以C ）错误。
52. 支持子程序调用的数据结构是（ ）。答案：A
A ）栈
B ）树
C ）队列
D ）二叉树
题目解析:栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表，在主程序调用子函数时要首先保存主程序当前的状态，然后转去执行子程序，最终把子程序的执行结果返回到主程序中调用子程序的位置，继续向下执行，这种调用符合栈的特点，因此本题的答案为A ）。
53. 某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是（ ）。答案：C
A ）10
B ）8
C ）6
D ）4
题目解析:根据二叉树的基本性质3：在任意一棵二叉树中，度为0的叶子节点总是比度为2的节点多一个，所以本题中是5＋1＝6个。
54. 下列排序方法中，最坏情况下比较次数最少的是（ ）。答案：D
A ）冒泡排序
B ）简单选择排序
C ）直接插入排序
D ）堆排序
题目解析:冒泡排序与简单插入排序与简单选择排序法在最坏情况下均需要比较n(n－1)/2次，而堆排序在最坏情况下需要比较的次数是nlog 2n 。
55. 下列叙述中正确的是（ ）。答案：C
A ）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化
B ）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化
C ）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化
D ）在栈中，栈中元素不会随栈底指针与栈顶指针的变化而动态变化
题目解析:栈是先进后出的数据结构，在整个过程中，栈底指针不变，入栈与出栈操作均由栈顶指针的变化来操作，所以选择C) 。
56. 某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）（ ）。答案：D
A ）3
B ）4
C ）6
D ）7
题目解析:根据二叉树的基本性质3：在任意一棵二叉树中，度为0的叶子节点总比度为2的节点多一个，所以本题中度为2的节点为1－1＝0个，所以可以知道本题目中的二叉树的每一个节点都有一个分支，所以共7个节点共7层，即深度为7。
57. 下列叙述中正确的是（ ）。答案：D
A ）算法就是程序
B ）设计算法时只需要考虑数据结构的设计
C ）设计算法时只需要考虑结果的可靠性
D ）以上三种说法都不对
题目解析:算法是指解题方案的准确而完整的描述，算法不等于程序，也不等于计算方法，所以
A ）错误。设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构，所以B ）和C ）错误。
58. 下列数据结构中，属于非线性结构的是（ ）。答案：C
A ）循环队列
B ）带链队列
C ）二叉树
D ）带链栈
题目解析:树是简单的非线性结构，所以二叉树作为树的一种也是一种非线性结构。
59. 下列数据结构中，能够按照" 先进后出" 原则存取数据的是（ ）。答案：B
A ）循环队列
B ）栈
C ）队列
D ）二叉树
题目解析:栈是按先进后出的原则组织数据的。队列是先进先出的原则组织数据。因此，本题答案为B ）。
60. 对于循环队列，下列叙述中正确的是（ ）。答案：D
A ）队头指针是固定不变的
B ）队头指针一定大于队尾指针
C ）队头指针一定小于队尾指针
D ）队头指针可以大于队尾指针，也可以小于队尾指针
题目解析:循环队列的队头指针与队尾指针都不是固定的，随着入队与出队操作要进行变化。因为是循环利用的队列结构所以对头指针有时可能大于队尾指针有时也可能小于队尾指针。
61. 算法的空间复杂度是指（ ）。答案：A
A ）算法在执行过程中所需要的计算机存储空间
B ）算法所处理的数据量
C ）算法程序中的语句或指令条数
D ）算法在执行过程中所需要的临时工作单元数
题目解析:算法的空间复杂度是指算法在执行过程中所需要的内存空间。所以选择A ）。
62. 下列叙述中正确的是（ ）。答案：B
A ）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的
B ）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构
C ）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构
D ）线性表的链式存储结构所需要的存储空间与顺序存储结构没有任何关系
题目解析:线性链式存储结构中每个结点都由数据域与指针域两部分组成，增加了存储空间，所以一般要多于顺序存储结构。
63. 下列叙述中正确的是（ ）。答案：D
A ）栈是一种先进先出的线性表
B ）队列是一种后进先出的线性表
C ）栈与队列都是非线性结构
D ）栈与队列都是线性结构
题目解析:栈是一种先进后出的线性表，队列是一种先进先出的线性表，栈与队列都是线性结构。
64. 下列叙述中正确的是（ ）。答案：B
A ）有一个以上根结点的数据结构不一定是非线性结构
B ）只有一个根结点的数据结构不一定是线性结构
C ）循环链表是非线性结构
D ）双向链表是非线性结构
题目解析:线性结构应满足：有且只有一个根结点与每个结点最多有一个前件，也最多有一个后件，所以B ）正确。所以有一个以上根结点的数据结构一定是非线性结构，所以A ）错误。循环链表和双向链表都是线性结构的数据结构，所以C ）和D ）错误。
65. 下列关于二叉树的叙述中，正确的是（ ）。答案：B
A ）叶子结点总是比度为2的结点少一个
B ）叶子结点总是比度为2的结点多一个
C ）叶子结点数是度为2的结点数的两倍
D ）度为2的结点数是度为1的结点数的两倍
题目解析:根据二叉树的基本性质：在任意一棵二叉树中，度为0的叶子结点总是比度为2的结点多一个。所以选择B ）。
66. 某系统总体结构图如下图所示：
该系统总体结构图的深度是：（ ）。答案：C
A ）7
B ）6
C ）3
D ）2
题目解析:根据总体结构图可以看出该树的深度为3，比如：XY 系统——功能2——功能2.1，就是最深的度数的一个表现。
67. 下列叙述中正确的是（ ）。答案：B
A ）循环队列是队列的一种链式存储结构
B ）循环队列是队列的一种顺序存储结构
C ）循环队列是非线性结构
D ）循环队列是一种逻辑结构
题目解析:在实际应用中，队列的顺序存储结构一般采用循环队列的形式。
68. 下列关于线性链表的叙述中，正确的是（ ）。答案：C
A ）各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致
B ）各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续
C ）进行插入与删除时，不需要移动表中的元素
D ）各数据结点的存储顺序与逻辑顺序可以不一致，它们的存储空间也可以不一致
题目解析:一般来说，在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。线性链表中数据的插入和删除都不需要移动表中的元素，只需改变结点的指针域即可。
69. 一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为（ ）。答案：A
A ）16
B ）10
C ）6
D ）4
题目解析:根据二叉树的性质3：在任意一棵二叉树中，度为0的叶子结点总是比度为2的结点多一个，所以本题中度为2的结点是5-1＝4个，所以度为1的结点的个数是25-5-4＝16个。
70. 在满足实体完整性约束的条件下（ ）。答案：A
A ）一个关系中应该有一个或多个候选关键字
B ）一个关系中只能有一个候选关键字
C ）一个关系中必须有多个候选关键字
D ）一个关系中可以没有候选关键字
题目解析:实体完整性约束要求关系的主键中属性值不能为空值，所以选择A ）。
71. 下列链表中，其逻辑结构属于非线性结构的是（ ）。答案：A
A ）二叉链表
B ）循环链表
C ）双向链表
D ）带链的栈
题目解析:二叉链表是二叉树的链式存储结构，属于非线性结构，其余选项均属于线性结构，所以选择A ）。
72. 设循环队列的存储空间为Q(1: 35) ，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为（ ）。答案：D
A ）15
B ）16
C ）20
D ）0或35
题目解析:front=rear，说明队列为满或者为空，所以答案选择D ）。
73. 下列关于栈的叙述中，正确的是（ ）。答案：C
A ）栈底元素一定是最后入栈的元素
B ）栈顶元素一定是最先入栈的元素
C ）栈操作遵循先进后出的原则
D ）以上三种说法都不对
题目解析:栈操作遵循先进后出的原则，栈底元素一定是最先入栈的元素，栈顶元素一定是最后入栈的元素，所以选择C ）。
74. 下列叙述中正确的是（ ）。答案：A
A ）程序执行的效率与数据的存储结构密切相关
B ）程序执行的效率只取决于程序的控制结构
C ）程序执行的效率只取决于所处理的数据量
D ）以上三种说法都不对
题目解析:采用的存储结构不同，其数据处理的效率是不同的，程序执行的效率也就不同，因此选项A ）是正确的。程序执行的效率不仅与程序的控制结构有关，而且与所处理的数据量有关，因此选项 B）、C ）、D ）都不正确。
75. 下列与队列结构有关联的是（ ）。答案：D
A ）函数的递归调用
B ）数组元素的引用
C ）多重循环的执行
D ）先到先服务的作业调度
题目解析:队列是按照先进先出的原则组织数据的，可以看出以下四个选项中，与队列结构有关联的是D ）选项。
76.
（ ）。答案：C
A ）DYBEAFCZX
B ）YDEBFZXCA
C ）ABDYECFXZ
D ）ABCDEFXYZ
题目解析:前序遍历的过程是首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。根据图可以分析出，该二叉树的前序遍历结果为C ）。
77. 一个栈的初始状态为空。现将元素1,2,3,A,B,C 依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。答案：C
A ）1,2,3,A,B,C
B ）C,B,A,1,2,3
C ）C,B,A,3,2,1
D ）1,2,3,C,B,A
题目解析:栈是先进后出的原则组织数据，所以入栈最早的最后出栈，所以选择C) 。
78. 下列叙述中正确的是（ ）。答案：D
A ）一个算法的空间复杂度大，则其时间复杂度也必定大
B ）一个算法的空间复杂度大，则其时间复杂度必定小
C ）一个算法的时间复杂度大，则其空间复杂度必定小
D ）算法的时间复杂度与空间复杂度没有直接关系
题目解析:算法的时间复杂度是指之行算法所需要的计算工作量；算法的空间复杂度是指执行这个算法所需要的内存空间，两者之间没有直接关系。
79. 下列叙述中正确的是（ ）。答案：A
A ）循环队列中的元素个数随队头指针与队尾指针的变化而动态变化
B ）循环队列中的元素个数随队头指针的变化而动态变化
C ）循环队列中的元素个数随队尾指针的变化而动态变化
D ）以上说法都不对
题目解析:循环队列中的元素个数随队头指针与队尾指针的变化而动态变化，选A ）。
80. 一棵二叉树中共有80个叶子结点与70个度为1的结点，则该二叉树中的总结点数为（ ）。答案：B
A ）219
B ）229
C ）230
D ）231
题目解析:根据二叉树的性质，度为0的结点（即叶子结点）总是比度为2的结点多一个，叶子结点为80，度为2的结点为79，所以总结点数为：80+70+79=229，选B ）。
81. 对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为（ ）。答案：C
A ）9
B ）10
C ）45
D ）90
题目解析:在最坏情况下，冒泡排序的时间复杂度为n(n-1)/2，为45，答案选C ）。
82. 下列叙述中正确的是（ ）。答案：B
A ）算法的效率只与问题的规模有关，而与数据的存储结构无关
B ）算法的时间复杂度是指执行算法所需要的计算工作量
C ）数据的逻辑结构与存储结构是一一对应的
D ）算法的时间复杂度与空间复杂度一定相关
题目解析:算法的时间复杂度是指执行算法所需要的计算工作量，与数据的存储结构有关，与算法的空间复杂度没有关系。数据的逻辑结构与存储位置无关，即与存储结构无关，所以选择B ）。
83. 下列叙述中正确的是（ ）。答案：C
A ）线性表链式存储结构的存储空间一般要少于顺序存储结构
B ）线性表链式存储结构与顺序存储结构的存储空间都是连续的
C ）线性表链式存储结构的存储空间可以是连续的，也可以是不连续的
D ）以上说法都不对
题目解析:在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的，所以选择C ）。
84. 某二叉树共有12个结点，其中叶子结点只有1个。则该二叉树的深度为（根结点在第1层）（ ）。答案：D
A ）3
B ）6
C ）8
D ）12
题目解析:根据二叉树的性质，叶子结点比度为2的结点个数多一个，叶子结点只有1个，那么度为2的结点为0个，可以得出共有11个度为1的结点，那么该二叉树每一层上只能有一个结点，共12层，即深度为12。
85. 对长度为n 的线性表作快速排序，在最坏情况下，比较次数为（ ）。答案：D
A ）n
B ）n-1
C ）n(n-1)
D ）n(n-1)/2
题目解析:在最坏情况下，快速排序需要比较n(n-1)/2次。
86. 下列叙述中正确的是（ ）。答案：D
A ）有且只有一个根结点的数据结构一定是线性结构
B ）每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构
C ）有且只有一个根结点的数据结构一定是非线性结构
D ）有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构
题目解析:有且只有一个根结点的数据结构可以是线性结构，如队列，也可以是非线性结构，如二叉树，所以选项D ）正确。选项B ）中，如果有两个根结点，则不符合线性结构的条件，说法错误。本题答案选D ）。
87. 下列叙述中错误的是（ ）。答案：C
A ）在双向链表中，可以从任何一个结点开始直接遍历到所有结点
B ）在循环链表中，可以从任何一个结点开始直接遍历到所有结点
C ）在线性单链表中，可以从任何一个结点开始直接遍历到所有结点
D ）在二叉链表中，可以从根结点开始遍历到所有结点
题目解析:在线性单链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，但不能找到前件结点，选项C ）说法错误。
88. 某二叉树共有13个结点，其中有4个度为1的结点，则叶子结点数为（ ）。答案：A
A ）5
B ）4
C ）3
D ）2
题目解析:在线性单链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，但不能找到前件结点，选项C ）说法错误。
89. 设栈的顺序存储空间为S(1: 50), 初始状态为top=0。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（ ）。答案：C
A ）30
B ）29
C ）20
D ）19
题目解析:在栈中，top 位置直接反映栈中元素的个数，top=20，则说明当前栈中的元素个数为20。
90. 下列叙述中正确的是（ ）。答案：B
A ）栈与队列都只能顺序存储
B ）循环队列是队列的顺序存储结构
C ）循环链表是循环队列的链式存储结构
D ）以上说法都不对
题目解析:栈和队列都可以采用链式存储结构，选项A ）错误。队列的顺序存储结构一般采用循环队列的形式，所以循环队列是队列的顺序存储结构，选项B 正确，选项C ）错误。答案选B ）。
91. 设某二叉树的前序序列为ABC ，中序序列为CBA ，则该二叉树的后序序列为（ ）。答案：B
A ）BCA
B ）CBA
C ）ABC
D ）CAB
题目解析:前序序列为ABC ，中序序列为CBA ，说明根结点为A ，且B 和C 均在该A 的左子树上；结点B 和C 的前序序列为BC ，中序序列为CB ，则说明结点C 在结点B 的左子树上，根据以上分析，该二叉树的后序序列为CBA ，答案选B ）。
92. 下列排序方法中，最坏情况下时间复杂度最小的是（ ）。答案：C
A ）冒泡排序
B ）快速排序
C ）堆排序
D ）直接插入排序
题目解析:在最坏情况下，堆排序时间复杂度为O(nlog2n) ，其余选项均为O(n) ，所以答案选C ）。 2
93. 为了对有序表进行对分查找，则要求有序表（ ）。答案：A
A ）只能顺序存储
B ）只能链式存储
C ）可以顺序存储也可以链式存储
D ）任何存储方式
题目解析:对分查找必须满足用顺序存储结构，且线性表是有序表两个条件，答案选A ）。
94. 设某二叉树的后序序列为CBA ，中序序列为ABC ，则该二叉树的前序序列为（ ）。答案：C
A ）BCA
B ）CBA
C ）ABC
D ）CAB
题目解析:后序序列为CBA ，中序序列为ABC ，则说明，A 为根结点，并且B 和C 均在A 的右子树上；结点B 和C 中，后序序列为CB ，中序序列为BC ，则说明结点C 在结点B 的右子树上，根据分析可得，该二叉树的前序序列为ABC ，答案选C ）。
95. 下列叙述中正确的是（ ）。答案：D
A ）存储空间不连续的所有链表一定是非线性结构
B ）结点中有多个指针域的所有链表一定是非线性结构
C ）能顺序存储的数据结构一定是线性结构
D ）带链的栈与队列是线性结构
题目解析:判断一个非空的数据结构是否为线性结构必须满足以下两个条件：① 有且只有一个根结点；② 每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项A ）、
B ）和C ）都不能判定是否是线性结构，选项D ）正确，答案选D ）。
96. 算法时间复杂度的度量方法是（ ）。答案：B
A ）算法程序的长度
B ）执行算法所需要的基本运算次数
C ）执行算法所需要的所有运算次数
D ）执行算法所需要的时间
题目解析:算法的时间复杂度，是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运行次数来度量，答案选B ）。
97. 设循环队列为Q(1: m)，初始状态为front=rear=m。现经过一系列的入队与退队运算后，front=rear=1，则该循环队列中的元素个数为（ ）。答案：D
A ）1
B ）2
C ）m-1
D ）0或m
题目解析:在循环队列中，当front=rear时，有两种情况，一种是队列为空，另一种是队列为满，所以答案选D ）。
98. 在最坏情况下（ ）。答案：C
A ）快速排序的时间复杂度比冒泡排序的时间复杂度要小
B ）快速排序的时间复杂度比希尔排序的时间复杂度要小
C ）希尔排序的时间复杂度比直接插入排序的时间复杂度要小
D ）快速排序的时间复杂度与希尔排序的时间复杂度是一样的
题目解析:在最坏情况下，快速排序、冒泡排序和直接插入排序所需要的比较次数为O(n) ，希尔排序所需要的比较次数为O(n) ，所以答案选C ）。 1.52
99. 在深度为7的满二叉树中，度为2的结点个数为（ ）。答案：B
A ）64
B ）63
C ）32
D ）31
题目解析:根据满二叉树的性质，深度为7的满二叉树共有2-1=127个结点。根据二叉树的性质，该满二叉树在第7层上，共有2=64个结点，即共有64个叶子结点，那么度为2的结点个数为127-64=63个。 7-17
100. 设栈的顺序存储空间为S(1: m) ，初始状态为top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（ ）。答案：C
A ）30
B ）20
C ）m-19
D ）m-20
题目解析:初始状态为top=m+1，经过运算之后，top=20，则当前栈中元素个数为m+1-20=m-19个。
101. 算法空间复杂度的度量方法是（ ）。答案：D
A ）算法程序的长度
B ）算法所处理的数据量
C ）执行算法所需要的工作单元
D ）执行算法所需要的存储空间
题目解析:算法的空间复杂度，一般是指执行这个算法所需要的内存空间，答案选D ）。 102. 下面不属于软件开发阶段任务的是（ ）。答案：B
A ）测试
B ）可行性研究
C ）设计
D ）实现
题目解析:可行性研究是属于软件定义阶段的任务，所以答案选B ）。
103. 设循环队列为Q(1: m) ，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为（ ）。答案：A
A ）4
B ）6
C ）m-5
D ）m-6
题目解析:初始状态为front=rear=m，说明初始状态为空。经过一系列入队与退队运算后，front=15，rear=20，则当前共有5个元素，则在最坏情况下，需要比较的次数为4次，答案选
A ）。
104. 下列叙述中正确的是（ ）。答案：D
A ）循环队列属于队列的链式存储结构
B ）双向链表是二叉树的链式存储结构
C ）非线性结构只能采用链式存储结构
D ）有的非线性结构也可以采用顺序存储结构
题目解析:循环队列属于队列的顺序存储结构，选项A ）错误；二叉树的存储结构为二叉链表，选项B ）错误；非线性结构也可以采用顺序存储结构，因此选项C ）错误，选项D ）正确，答案为D ）。
105. 某二叉树中有n 个叶子结点，则该二叉树中度为2的结点数为（ ）。答案：B
A ）n+1
B ）n-1
C ）2n
D ）n/2
题目解析:根据二叉树的性质，叶子结点的个数比度为2的结点数多一个，因此答案为B) 。 106. 下列叙述中错误的是（ ）。答案：C
A ）算法的时间复杂度与算法所处理数据的存储结构有直接关系
B ）算法的空间复杂度与算法所处理数据的存储结构有直接关系
C ）算法的时间复杂度与空间复杂度有直接关系
D ）以上说法都不对
题目解析:算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，并且两者之间美欧直接关系，因此答案选C ）。
107. 设栈的顺序存储空间为S(0:49)，栈底指针bottom=49，栈顶指针top=30（指向栈顶元素）。则栈中的元素个数为（ ）。答案：C
A ）30
B ）29
C ）20
D ）19
题目解析:算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，并且两者之间美欧直接关系，因此答案选C ）。
108. 某二叉树的前序序列为ABCDEFG ，中序序列为DCBAEFG ，则该二叉树的深度（根结点在第1层）为（ ）。答案：C
A ）2
B ）3
C ）4
D ）5
题目解析:该二叉树的前序序列为ABCDEFG ，中序序列为DCBAEFG ，可知A 为根结点，结点B 、C 、D 位于根结点的左子树上，结点E 、F 、G 位于根结点的右子树上；并且结点B 、C 、D 在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点E 、F 、G 顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树深度为4，答案选C ）。
109. 下列叙述中正确的是（ ）。答案：D
A ）存储空间连续的数据结构一定是线性结构
B ）存储空间不连续的数据结构一定是非线性结构
C ）没有根结点的非空数据结构一定是线性结构
D ）具有两个根结点的数据结构一定是非线性结构
题目解析:判断一个非空的数据结构是否为线性结构必须满足以下两个条件：① 有且只有一个根结点；② 每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项A ）、
B ）和C ）都不能判定是否是线性结构，选项D ）正确，答案选D ）。
110. 下列叙述中正确的是（ ）。答案：C
A ）带链队列的存储空间可以不连续，但队头指针必须大于队尾指针
B ）带链队列的存储空间可以不连续，但队头指针必须小于队尾指针
C ）带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针
D ）以上说法都不对
题目解析:带链队列的存储空间可以不连续，且队头指针与队尾指针大小没有可比性，答案选C ）。 111. 设循环队列为Q(1:m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为（ ）。答案：D
A ）5
B ）6
C ）m-5
D ）m-6
题目解析:该循环队列的容量为m ，队列中共有15-20+m=m-5个元素，如果想找出其中的最小值，最坏情况下需要比较m-5-1=m-6次。
112. 某二叉树的前序序列为ABCDEFG ，中序序列为DCBAEFG ，则该二叉树的后序序列为（ ）。答案：D
A ）EFGDCBA
B ）DCBEFGA
C ）BCDGFEA
D ）DCBGFEA
题目解析:该二叉树的前序序列为ABCDEFG ，中序序列为DCBAEFG ，可知A 为根结点，结点B 、C 、D 位于根结点的左子树上，结点E 、F 、G 位于根结点的右子树上；并且结点B 、C 、D 在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点E 、F 、G 顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树的后序遍历序列为DCBGFEA ，答案选D ）。
113. 下列叙述中正确的是（ ）。答案：B
A ）在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构
B ）在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构
C ）在链表中，如果每个结点有两个指针域，则该链表一定是线性结构
D ）在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构
题目解析:判断一个非空的数据结构是否为线性结构必须满足以下两个条件：① 有且只有一个根结点；② 每一个结点最多有一个前件，也最多有一个后件。选项B ）中，如果有两个结点的同一个指针域的值相等，则说明至少有一个结点有两个前件，不符合线性结构的定义，所以答案选B ）。
114. 下列叙述中错误的是（ ）。答案：B
A ）在带链队列中，队头指针和队尾指针都是在动态变化的
B ）在带链栈中，栈顶指针和栈底指针都是在动态变化的
C ）在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的
D ）以上说法均不对
题目解析:在栈结构中，插入和删除操作都是在栈顶进行操作，相对应的在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的，所以选项B ）说法错误。
115. 设数据元素的集合D={ 1,2,3,4,5 }，则满足下列关系R 的数据结构中为线性结构的是（ ）。答案：B
A ）R={ (1,2), (3,4), (5,1) }
B ）R={ (1,3), (4,1), (3,2), (5,4) }
C ）R={ (1,2), (2,3), (4,5) }
D ）R={ (1,3), (2,4), (3,5) }
题目解析:关系R 中的每个结点由两个部分构成，分别是数据域和指针域。选项B ）中可以看出，元素序列为5→4→1→3→2，符合线性结构的条件。选项A ）、选项C ）和选项D ）中分别有两个根结点，不符合线性结构的条件。所以答案选B ）。
116. 下列叙述中正确的是（ ）。答案：A
A ）链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构
B ）线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个指针
C ）线性表的链式存储结构中，每个结点只能有一个指向后件的指针
D ）线性表的链式存储结构中，叶子结点的指针只能是空
题目解析:在链式存储方式中，每个结点由两部分组成：数据域和指针域，指针域用于指向该节点的前一个或后一个结点，所以选项B ）、C ）、D ）说法错误。选项A ）中，例如双向链表就具有两个指针，也属于线性结构，所以答案选A ）。
117. 一个栈的初始状态为空。现将元素A,B,C,D,E 依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队（原队列为空），最后将队列中的元素全部退出。则元素退队的顺序为（ ）。答案：C
A ）ABC
B ）CBA
C ）EDC
D ）CDE
题目解析:栈是根据先进后出的原则组织数据，所以退栈三次的元素依次为E 、D 、C ；队列是根据先进先出的原则组织数据的，所以退队的顺序依次为E 、D 、C ，答案选C ）。
118. 某二叉树的中序序列为DCBAEFG ，后序序列为DCBGFEA ，则该二叉树的深度（根结点在第1层）为（ ）。答案：B
A ）5
B ）4
C ）3
D ）2
题目解析:该二叉树的中序序列为DCBAEFG ，后序序列为DCBGFEA ，可知A 为根结点，结点B 、C 、D 位于根结点的左子树上，结点E 、F 、G 位于根结点的右子树上；并且结点B 、C 、D 在中序序列和后序序列中顺序未变，则说明这三个结点依次位于前一个结点的左子树上；结点E 、F 、G 顺序颠倒，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树的深度为4，答案选B ）。
A ）所谓算法就是计算方法
B ）程序可以作为算法的一种描述方法
C ）算法设计只需考虑得到计算结果
D ）算法设计可以忽略算法的运算时间
题目解析:算法是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程, 重在解题方案的设计，并且不等于计算方法，故A 和C 选项不正确，程序的编制不可能优于算法的设计，但算法的描述可以用程序、伪代码、流程图来描述，故B 选项正确。算法要求执行过程中所需要的基本运算次数和时间最少，即时间复杂度最低，所以C 选项不正确。正确答案为B 。
2. 下列各序列中不是堆的是（ ）。答案：C
A ）(91,85,53,36,47,30,24,12)
B ）(91,85,53,47,36,30,24,12)
C ）(47,91,53,85,30,12,24,36)
D ）(91,85,53,47,30,12,24,36)
题目解析:堆可以看成一棵完全二叉树：任一根节点>=左右孩子（或者
3. 深度为5的完全二叉树的结点数不可能是（ ）。答案：A
A ）15
B ）16
C ）17
D ）18
题目解析:对于满二叉树，叶子结点的数目等于2（n-1）,n 为深度，这里就是2的5-1=4次方，就是16。
4. 设二叉树如下：
则前序序列为（ ）。答案：A
A ）ABDEGCFH
B ）DBGEAFHC
C ）DGEBHFCA
D ）ABCDEFGH
题目解析:前序遍历首先访问根结点然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故正确选项选A ；B 选项为中序遍历。C 选项为后序遍历；D 选项不正确。
A ）循环队列是顺序存储结构
B ）循环队列是链式存储结构
C ）循环队列是非线性结构
D ）循环队列的插入运算不会发生溢出现象
题目解析:循环队列属于队列的特例和栈同属于线性结构，C 选项不正确。在顺序队列中, 由于数组空间不够而产生的溢出叫真溢出；顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出；假溢出是由于队尾rear 的值和队头front 的值不能由所定义数组下界值自动转为数组上界值而产生的，解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列，因此，顺序队列通常都采用顺序循环队列结构；栈的存储方式有顺序存储和链式存储，故正确选项为A ；B 选项不正确。循环队列虽然能解决由于假溢出，却不能解决在顺序队列中, 由于数组空间不够而产生的溢出的真溢出，故选项C 不正确。
6. 下列叙述中正确的是（ ）。答案：D
A ）所有数据结构必须有根结点
B ）所有数据结构必须有终端结点（即叶子结点）
C ）只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构
D ）没有根结点或没有叶子结点的数据结构一定是非线性结构
题目解析:只有一个空节点的结构也属数据结构，所以A 和B 选项不正确；有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件的数据结构才属于线性结构，其它的都属于非线性结构，故C 选项不正确，正确选项为D 。
7. 下列关于算法的描述中错误的是（ ）。答案：D
A ）算法强调动态的执行过程，不同于静态的计算公式
B ）算法必须能在有限个步骤之后终止
C ）算法设计必须考虑算法的复杂度
D ）算法的优劣取决于运行算法程序的环境
题目解析:算法的优劣取决自身的运行效率，时间和空间复杂度高低，并不取决于运行算法程序的环境，故D 选项错误。
8. 设二叉树如下：
则中序序列为（ ）。答案：B
A ）ABDEGCFH
B ）DBGEAFHC
C ）DGEBHFCA
D ）ABCDEFGH
题目解析:中序遍历（LDR ）是指首先遍历左子树，然后访问根结点，最后遍历右子树；故
正确答案为B 。
9. 线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有（ ）。答案：B
A ）节省存储空间
B ）插入与删除运算效率高
C ）便于查找
D ）排序时减少元素的比较次数
题目解析:顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（＝1），存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 优点：插入或删除元素时很方便效率高，使用灵活。缺点：存储密度小（
10. 深度为７的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为（ ）。答案：B
A ）62
B ）63
C ）64
D ）65
题目解析: 对于满二叉树，结点的数目等于2n-1，叶子结点数目为2n-1，n 为深度，这里就是2的7次方-1，就是127个结点，叶子结点是64个，然而题目中只有125个结点，说明少了两个结点，那么就少了一个叶子结点，即63个。
11. 下列叙述中正确的是（ ）。答案：C
A ）所谓有序表是指在顺序存储空间内连续存放的元素序列
B ）有序表只能顺序存储在连续的存储空间内
C ）有序表可以用链接存储方式存储在不连续的存储空间内
D ）任何存储方式的有序表均能采用二分法进行查找
题目解析:有序表可以用顺序存储空间内连续存放的元素序列来实现，也可以用链接存储方式存储在不连续的存储空间内，已达到逻辑上连续，存储空间上不一定连续的效果。二分法进行查找只适用于顺序存储的有序表。故选项C 正确。
12. 设二叉树如下：
则后序序列为（ ）。答案：C
A ）ABDEGCFH
B ）DBGEAFHC
C ）DGEBHFCA
D ）ABCDEFGH
题目解析:后序遍历（LRD ）首先遍历左子树，然后访问遍历右子树，最后访问根结点。故正确选项为C 。
13. 下列叙述中正确的是（ ）。答案：B
A ）结点中具有两个指针域的链表一定是二叉链表
B ）结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构
C ）二叉树只能采用链式存储结构
D ）循环链表是非线性结构
题目解析:结点中尽管有两个指针域但没有分别指向两个不同的结点就不是二叉链表，故A 选项不正确；二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序存储结构和链式存储结构，故C 选项不正确；循环链表是在单链表中，将终端结点的指针域NULL 改为指向表头结点或开始结点的线性结构，故D 选项不正确；当结点中两个指针分别指向前驱结点和后继结点是为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，故B 选项正确。
14. 设某二叉树中共有140个结点，其中有40个度为1的结点。则（ ）。答案：D
A ）该二叉树中有51个叶子结点
B ）该二叉树中有50个叶子结点
C ）该二叉树中有51个度为2的结点
D ）不可能有这样的二叉树
题目解析:140个结点除去40个度为1的结点，说明有100个度为2的结点，而根据二叉树性质，这个数值无法得出故本题答案选D 。
15. 带链的栈与顺序存储的栈相比，其优点是（ ）。答案：C
A ）入栈与退栈操作方便
B ）可以省略栈底指针
C ）入栈操作时不会受栈存储空间的限制而发生溢出
D ）以上都不对
题目解析:带链的栈与顺序存储的栈相比优点是不受连续存储空间大小的限制，即不需考虑栈满的问题，故C 选项正确。
16. 某二叉树的前序序列为ABCD ，中序序列为DCBA ，则后序序列为（ ）。答案：B
A ）BADC
B ）DCBA
C ）CDAB
D ）ABCD
题目解析:在二叉树前序遍历中ABCD 中A 是根节点，二在后序遍历中根结点位于最后，所以正确答案为B 。
17. 某系统结构图如下所示
该系统结构图的最大扇入数是（ ）。答案：A
A ）n
B ）1
C ）2
D ）3
题目解析:系统结构图中的最大扇入数为系统图中进入某一节点的最大节点数，本系统图中功能n.1节点输出节点为功能1到功能n, 所以系统结构图的最大扇入数为n, 故正确选项为A 。
18. 下列关于算法复杂度叙述正确的是（ ）。答案：B
A ）最坏情况下的时间复杂度一定高于平均情况的时间复杂度
B ）时间复杂度与所用的计算工具无关
C ）对同一个问题，采用不同的算法，则它们的时间复杂度是相同的
D ）时间复杂度与采用的算法描述语言有关
题目解析:准确把握算法复杂度的概念。
19. 设有栈S 和队列Q ，初始状态均为空。首先依次将A,B,C,D,E,F 入栈，然后从栈中退出三个元素依次入队，再将X,Y ,Z 入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为（ ）。答案：B
A ）DEFXYZABC
B ）FEDZYXCBA
C ）FEDXYZCBA
D ）DEFZYXABC
题目解析:栈是一种特殊的线性表栈中的数据时按照先进后出或者是后进先出的规则进行的，队列是同栈不太相同的线性结构，进出顺序为先进先出的规则，根据题意要求本题正确答案为B 选项。
20. 下列叙述中正确的是（ ）。答案：D
A ）有两个指针域的链表称为二叉链表
B ）循环链表是循环队列的链式存储结构
C ）带链的栈有栈顶指针和栈底指针，因此又称为双重链表
D ）结点中具有多个指针域的链表称为多重链表
题目解析:结点中尽管有两个指针域但没有分别指向两个不同的结点就不是二叉链表，故A 选项不正确；循环链表是在单链表中，将终端结点的指针域NULL 改为指向表头结点或开始结点的线性结构，故B 选项不正确；当结点中两个指针分别指向前驱结点和后继结点是为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，故B 选项正确。双重链表的结点有两个指针，一个指向前驱，一个指向后继，从一个结点既可以向前也可以向后才是双重链表，故C 选项不正确。D 选项正确。
21. 某二叉树共有845个结点，其中叶子结点有45个，则度为1的结点数为（ ）。答案：C
A ）400
B ）754
C ）756
D ）不确定
题目解析:二叉树中，度为0的结点（即叶子节点）比度为2的结点多1个，而度为0、1、2的结点相加等于总结点数845，所以度为1的结点数为845-45-（45-1）=756。
22. 深度为7的二叉树共有127个结点，则下列说法中错误的是（ ）。答案：A
A ）该二叉树有一个度为1的结点
B ）该二叉树是满二叉树
C ）该二叉树是完全二叉树
D ）该二叉树有64个叶子结点
题目解析:大家一定要记清楚这几个二叉树的性质。
23. 下列叙述中正确的是（ ）。答案：D
A ）非线性结构只能采用链式存储结构
B ）非线性结构只能用多重链表表示
C ）所有数据结构既可以采用顺序存储结构，也可以采用链式存储结构
D ）有的非线性结构也能采用顺序存储结构
题目解析:链式存储方式即可用于表示线性结构，也可用于表示非线性结构，非线性结构也可以用连续存储空间顺序存储。所以AB 选项不正确在所有的数据结构中并非所有的结构都能用顺序存储结构和采用链式存储结构表示，故选项C 不正确，D 选项正确。
24. 某二叉树的中序序列为BDCA ，后序序列为DCBA ，则前序序列为（ ）。答案：C
A ）DCBA
B ）BDCA
C ）ABCD
D ）BADC
题目解析:在二叉树后序遍历中DCBA 中A 是根节点，二在前序遍历中根结点位于首位，所以正确答案为B 。
25. 某系统结构图如下图所示
该系统结构图的最大扇出数是（ ）。答案：D
A ）1
B ）2
C ）3
D ）n
题目解析: 系统结构图中的最大扇出数为系统图中某一节点输出的最大节点数，本系统图中某系统输出节点为功能1到功能n, 所以系统结构图的最大扇入数为n, 故正确选项为D 。
26. 设有序线性表的长度为n ，则在有序线性表中进行二分查找，最坏情况下的比较次数为（ ）。答案：D
A ）n(n-1)/2
B ）n
C ）nlog2 n
D ）log2 n
题目解析:二分法查找只适用于顺序存储的有序表，对于长度为n 的有序线性表，最坏情况只需比较log2n 次，而顺序查找需要比较n 次。故正确选项为D 。
27. 某完全二叉树共有256个结点，则该完全二叉树的深度为（ ）。答案：C
A ）7
C ）9
D ）10
题目解析: 根据" 二叉树的第i 层至多有2^(i ? 1) 个结点；深度为k 的二叉树至多有2^k ? 1个结点（根结点的深度为1）". 这个性质：因为前九层的结点就有2^9-1=511个；而第九层的结点数是2^(9-1)=256。
28. 设序列长度为n, 在最坏情况下比较次数低于O （n2）的排序方法是（ ）。答案：D
A ）快速排序
B ）直接插入排序
C ）冒泡排序
D ）希尔排序
题目解析:大家一定要熟悉这几种排序方法的性质。
29. 某二叉树的前序序列为ABCD ，中序序列为BDCA ，则该二叉树的深度为（ ）。答案：A
A ）4
B ）3
C ）2
D ）不确定
题目解析:首先还原二叉树，然后再次进行排序。
30. 下列排序方法中，最坏情况下时间复杂度最低的是（ ）。答案：D
A ）冒泡排序
B ）快速排序
C ）希尔排序
D ）堆排序
题目解析:堆排序法，最坏情况需要O(nlog2n)次比较。 相比以上几种(除希尔排序法外) ，堆排序法的时间复杂度最小，故D 选项正确。
31. 设循环队列为Q(1:m)，初始状态为front=rear=m。现经一系列入队与退队操作后，front=rear=m-1，则（ ）。答案：D
A ）该循环队列已空
B ）该循环队列已满
C ）该循环队列中有1个元素
D ）该循环队列已空或已满
题目解析:循环队列m=0表示队列空；s=1且front=rear表示队列满。所以选项D 正确。
32. 设序列长度为n ，在最坏情况下，时间复杂度为O （log2n ）的算法是（ ）。答案：A
A ）二分法查找
B ）顺序查找
C ）分块查找
D ）哈希查找
题目解析:二分法查找只适用于顺序存储的有序表，对于长度为n 的有序线性表，最坏情况只需比较log2n 次，而顺序查找需要比较n 次。故正确选项为A 。
33. 某二叉树的深度为7，其中有64个叶子结点，则该二叉树中度为1的结点数为（ ）。答案：A
A ）0
B ）1
D ）63
题目解析:2的7-1次方已经是64了，所以度为1的结点一定是0。
34. 堆排序最坏情况下的时间复杂度为（ ）。答案：B
A ）O(n1.5)
B ）O(nlog2n)
C ）
D ）O(log2n)
题目解析:堆排序法，最坏情况需要O(nlog2n)次比较，堆排序法的时间复杂度最小，故B 选项正确。
35. 在线性表的链式存储结构中，其存储空间一般是不连续的，并且（ ）。答案：C
A ）前件结点的存储序号小于后件结点的存储序号
B ）前件结点的存储序号大于后件结点的存储序号
C ）前件结点的存储序号可以小于也可以大于后件结点的存储序号
D ）以上都不对
题目解析:链式存储结构使得节点在内存中不收位置的限制，结点存储号可以是任意的，并且能够保证逻辑上的线性关系。故C 选项正确。
36. 某二叉树中有15个度为1的结点，16个度为2的结点，则该二叉树中总的结点数为（ ）。答案：C
A ）32
B ）46
C ）48
D ）49
题目解析:二叉树有一个性质是：对任何二叉树，如果其终端结点数位n0，度为2的结点数为n2则n0=n2+1，所以度为0的一共有17个，总的结点数即时17+15+16=48个。
37. 某系统结构图如下图所示
该系统结构图中最大扇入是（ ）。答案：C
A ）0
B ）1
C ）2
D ）3
题目解析: 系统结构图中的最大扇入数为系统图中输入某一节点的最大节点数，本系统图中某系统输入节点为功能1到功能3n, 所以系统结构图的最大扇入数为3, 故正确选项为C 。
38. 下列叙述中正确的是（ ）。答案：D
A ）每一个结点有两个指针域的链表一定是非线性结构
B ）所有结点的指针域都为非空的链表一定是非线性结构
C ）循环链表是循环队列的链式存储结构
D ）线性结构的存储结点也可以有多个指针
题目解析:当结点中两个指针分别指向前驱结点和后继结点是为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，指针域为非空的链表也可以是线性结构，链式存储方式即可用于表示线性结构，也可用于表示非线性结构。故A 、B 、C 选项不完全正确。线性结构的存储结点可以由多个指针只有保证有且只有指向一个前驱结点和一个后继结点就是线性结构。故D 选项正确；。
39. 在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数（ ）。答案：A
A ）相同，元素的存储顺序与逻辑顺序一致
B ）相同，但其元素的存储顺序可以与逻辑顺序不一致
C ）不同，但元素的存储顺序与逻辑顺序一致
D ）不同，且其元素的存储顺序可以与逻辑顺序不一致
题目解析:线性表的顺序存储结构的两个特点（1）线性表中所有元素所占的存储空间是连续的；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。另在线性表中数据元素所占的字节数都是一致的，所以正确选项为A 。
40. 设循环队列为Q(1: m)，其初始状态为front=rear=m。经过一系列入队与退队运算后， front=30，rear=10。现要在该循环队列中作顺序查找，最坏情况下需要比较的次数为（ ）。答案：D
A ）19
B ）20
C ）m-19
D ）m-20
题目解析:二分法查找只适用于顺序存储的有序表，对于长度为n 的有序线性表，最坏情况只需比较log2n 次，而顺序查找需要比较n 次。已知循环队列为Q(1: m) ，其初始状态为front=rear=m，而节点个数为m-(front-rear),且顺序查找的比较次数与实际节点个数一致，故正确选项为D 。
41. 某二叉树中共有935个结点，其中叶子结点有435个，则该二叉树中度为2的结点个数为（ ）。答案：D
A ）64
B ）66
C ）436
D ）434
题目解析:大家记住一个公式，n0=n2+1，所以n2有434个。
42. 某系统结构图如下图所示
该系统结构图中最大扇出数是（ ）。答案：C
A ）1
B ）23
C ）3
D ）4
题目解析:系统结构图中的最大扇出数为系统图中某一节点输出的最大节点数，本系统图中某系统输出节点为功能1到功能3, 所以系统结构图的最大扇入数为3, 故正确选项为C 。
43. 算法的有穷性是指（ ）。答案：A
A ）算法程序的运行时间是有限的
B ）算法程序所处理的数据量是有限的
C ）算法程序的长度是有限的
D ）算法只能被有限的用户使用
题目解析:算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。有穷性是指算法程序的运行时间是有限的。
44. 对长度为n 的线性表排序，在最坏情况下，比较次数不是n(n－1)/2的排序方法是（ ）。答案：D
A ）快速排序
B ）冒泡排序
C ）直接插入排序
D ）堆排序
题目解析:在最坏的情况下，堆排序需要比较的次数为O(nlog2n) ，所以选择D.
45. 下列关于栈的叙述正确的是（ ）。答案：B
A ）栈按" 先进先出" 组织数据
B ）栈按" 先进后出" 组织数据
C ）只能在栈底插入数据
D ）不能删除数据
题目解析:栈是按照" 先进后出" 的原则组织数据的，只能在栈顶插入或删除数据，所以选择B 。
46. 一个栈的初始状态为空。现将元素1、2、3、4、5、A 、B 、C 、D 、E 依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。答案：B
A ）12345ABCDE
B ）EDCBA54321
C ）ABCDE12345
D ）54321EDCBA
题目解析:栈是先进后出的原则组织数据，所以入栈最早的最后出栈，所以选择B 。
47. 下列叙述中正确的是（ ）。答案：D
A ）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构
B ）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况
C ）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况
D ）循环队列中元素的个数是由队头指针和队尾指针共同决定
题目解析:循环队列有队头和队尾两个指针，但是循环队列仍是线性结构的，所以A ）错误；在循环队列中只需要队头指针与队尾两个指针来共同反映队列中元素的动态变化情况，所以B ）与
C ）错误。
48. 在长度为n 的有序线性表中进行二分查找，最坏情况下需要比较的次数是（ ）。答案：C
A ）O(n)
B ）
C ）
D ）
题目解析:当有序线性表为顺序存储时才能用二分法查找。可以证明的是对于长度为n 的有序线性表，在最坏情况下，二分法查找只需要比较O(nlog2n) 次，而顺序查找需要比较n 次。
49. 下列叙述中正确的是（ ）。答案：A
A ）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的
B ）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构
C ）顺序存储结构能存储有序表，链式存储结构不能存储有序表
D ）链式存储结构比顺序存储结构节省存储空间
题目解析:链式存储结构既可以针对线性结构也可以针对非线性结构，所以B ）与C ）错误。链式存储结构中每个结点都由数据域与指针域两部分组成，增加了存储空间，所以D ）错误。
50. 在数据管理技术发展的三个阶段中，数据共享最好的是（ ）。答案：C
A ）人工管理阶段
B ）文件系统阶段
C ）数据库系统阶段
D ）三个阶段相同
题目解析:据管理发展至今已经历了三个阶段：人工管理阶段、文件系统阶段和数据库系统阶段。其中最后一个阶段结构简单，使用方便逻辑性强物理性少，在各方面的表现都最好，一直占据数据库领域的主导地位，所以选择C ）。
51. 下列叙述中正确的是（ ）。答案：D
A ）栈是" 先进先出" 的线性表
B ）队列是" 先进后出" 的线性表
C ）循环队列是非线性结构
D ）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构
题目解析:栈是先进后出的线性表，所以A ）错误；队列是先进先出的线性表，所以B ）错误；循环队列是线性结构的线性表，所以C ）错误。
52. 支持子程序调用的数据结构是（ ）。答案：A
A ）栈
B ）树
C ）队列
D ）二叉树
题目解析:栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表，在主程序调用子函数时要首先保存主程序当前的状态，然后转去执行子程序，最终把子程序的执行结果返回到主程序中调用子程序的位置，继续向下执行，这种调用符合栈的特点，因此本题的答案为A ）。
53. 某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是（ ）。答案：C
A ）10
B ）8
C ）6
D ）4
题目解析:根据二叉树的基本性质3：在任意一棵二叉树中，度为0的叶子节点总是比度为2的节点多一个，所以本题中是5＋1＝6个。
54. 下列排序方法中，最坏情况下比较次数最少的是（ ）。答案：D
A ）冒泡排序
B ）简单选择排序
C ）直接插入排序
D ）堆排序
题目解析:冒泡排序与简单插入排序与简单选择排序法在最坏情况下均需要比较n(n－1)/2次，而堆排序在最坏情况下需要比较的次数是nlog 2n 。
55. 下列叙述中正确的是（ ）。答案：C
A ）在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化
B ）在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化
C ）在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化
D ）在栈中，栈中元素不会随栈底指针与栈顶指针的变化而动态变化
题目解析:栈是先进后出的数据结构，在整个过程中，栈底指针不变，入栈与出栈操作均由栈顶指针的变化来操作，所以选择C) 。
56. 某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根结点在第1层）（ ）。答案：D
A ）3
B ）4
C ）6
D ）7
题目解析:根据二叉树的基本性质3：在任意一棵二叉树中，度为0的叶子节点总比度为2的节点多一个，所以本题中度为2的节点为1－1＝0个，所以可以知道本题目中的二叉树的每一个节点都有一个分支，所以共7个节点共7层，即深度为7。
57. 下列叙述中正确的是（ ）。答案：D
A ）算法就是程序
B ）设计算法时只需要考虑数据结构的设计
C ）设计算法时只需要考虑结果的可靠性
D ）以上三种说法都不对
题目解析:算法是指解题方案的准确而完整的描述，算法不等于程序，也不等于计算方法，所以
A ）错误。设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构，所以B ）和C ）错误。
58. 下列数据结构中，属于非线性结构的是（ ）。答案：C
A ）循环队列
B ）带链队列
C ）二叉树
D ）带链栈
题目解析:树是简单的非线性结构，所以二叉树作为树的一种也是一种非线性结构。
59. 下列数据结构中，能够按照" 先进后出" 原则存取数据的是（ ）。答案：B
A ）循环队列
B ）栈
C ）队列
D ）二叉树
题目解析:栈是按先进后出的原则组织数据的。队列是先进先出的原则组织数据。因此，本题答案为B ）。
60. 对于循环队列，下列叙述中正确的是（ ）。答案：D
A ）队头指针是固定不变的
B ）队头指针一定大于队尾指针
C ）队头指针一定小于队尾指针
D ）队头指针可以大于队尾指针，也可以小于队尾指针
题目解析:循环队列的队头指针与队尾指针都不是固定的，随着入队与出队操作要进行变化。因为是循环利用的队列结构所以对头指针有时可能大于队尾指针有时也可能小于队尾指针。
61. 算法的空间复杂度是指（ ）。答案：A
A ）算法在执行过程中所需要的计算机存储空间
B ）算法所处理的数据量
C ）算法程序中的语句或指令条数
D ）算法在执行过程中所需要的临时工作单元数
题目解析:算法的空间复杂度是指算法在执行过程中所需要的内存空间。所以选择A ）。
62. 下列叙述中正确的是（ ）。答案：B
A ）线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的
B ）线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构
C ）线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构
D ）线性表的链式存储结构所需要的存储空间与顺序存储结构没有任何关系
题目解析:线性链式存储结构中每个结点都由数据域与指针域两部分组成，增加了存储空间，所以一般要多于顺序存储结构。
63. 下列叙述中正确的是（ ）。答案：D
A ）栈是一种先进先出的线性表
B ）队列是一种后进先出的线性表
C ）栈与队列都是非线性结构
D ）栈与队列都是线性结构
题目解析:栈是一种先进后出的线性表，队列是一种先进先出的线性表，栈与队列都是线性结构。
64. 下列叙述中正确的是（ ）。答案：B
A ）有一个以上根结点的数据结构不一定是非线性结构
B ）只有一个根结点的数据结构不一定是线性结构
C ）循环链表是非线性结构
D ）双向链表是非线性结构
题目解析:线性结构应满足：有且只有一个根结点与每个结点最多有一个前件，也最多有一个后件，所以B ）正确。所以有一个以上根结点的数据结构一定是非线性结构，所以A ）错误。循环链表和双向链表都是线性结构的数据结构，所以C ）和D ）错误。
65. 下列关于二叉树的叙述中，正确的是（ ）。答案：B
A ）叶子结点总是比度为2的结点少一个
B ）叶子结点总是比度为2的结点多一个
C ）叶子结点数是度为2的结点数的两倍
D ）度为2的结点数是度为1的结点数的两倍
题目解析:根据二叉树的基本性质：在任意一棵二叉树中，度为0的叶子结点总是比度为2的结点多一个。所以选择B ）。
66. 某系统总体结构图如下图所示：
该系统总体结构图的深度是：（ ）。答案：C
A ）7
B ）6
C ）3
D ）2
题目解析:根据总体结构图可以看出该树的深度为3，比如：XY 系统——功能2——功能2.1，就是最深的度数的一个表现。
67. 下列叙述中正确的是（ ）。答案：B
A ）循环队列是队列的一种链式存储结构
B ）循环队列是队列的一种顺序存储结构
C ）循环队列是非线性结构
D ）循环队列是一种逻辑结构
题目解析:在实际应用中，队列的顺序存储结构一般采用循环队列的形式。
68. 下列关于线性链表的叙述中，正确的是（ ）。答案：C
A ）各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致
B ）各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续
C ）进行插入与删除时，不需要移动表中的元素
D ）各数据结点的存储顺序与逻辑顺序可以不一致，它们的存储空间也可以不一致
题目解析:一般来说，在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。线性链表中数据的插入和删除都不需要移动表中的元素，只需改变结点的指针域即可。
69. 一棵二叉树共有25个结点，其中5个是叶子结点，则度为1的结点数为（ ）。答案：A
A ）16
B ）10
C ）6
D ）4
题目解析:根据二叉树的性质3：在任意一棵二叉树中，度为0的叶子结点总是比度为2的结点多一个，所以本题中度为2的结点是5-1＝4个，所以度为1的结点的个数是25-5-4＝16个。
70. 在满足实体完整性约束的条件下（ ）。答案：A
A ）一个关系中应该有一个或多个候选关键字
B ）一个关系中只能有一个候选关键字
C ）一个关系中必须有多个候选关键字
D ）一个关系中可以没有候选关键字
题目解析:实体完整性约束要求关系的主键中属性值不能为空值，所以选择A ）。
71. 下列链表中，其逻辑结构属于非线性结构的是（ ）。答案：A
A ）二叉链表
B ）循环链表
C ）双向链表
D ）带链的栈
题目解析:二叉链表是二叉树的链式存储结构，属于非线性结构，其余选项均属于线性结构，所以选择A ）。
72. 设循环队列的存储空间为Q(1: 35) ，初始状态为front=rear=35。现经过一系列入队与退队运算后，front=15，rear=15，则循环队列中的元素个数为（ ）。答案：D
A ）15
B ）16
C ）20
D ）0或35
题目解析:front=rear，说明队列为满或者为空，所以答案选择D ）。
73. 下列关于栈的叙述中，正确的是（ ）。答案：C
A ）栈底元素一定是最后入栈的元素
B ）栈顶元素一定是最先入栈的元素
C ）栈操作遵循先进后出的原则
D ）以上三种说法都不对
题目解析:栈操作遵循先进后出的原则，栈底元素一定是最先入栈的元素，栈顶元素一定是最后入栈的元素，所以选择C ）。
74. 下列叙述中正确的是（ ）。答案：A
A ）程序执行的效率与数据的存储结构密切相关
B ）程序执行的效率只取决于程序的控制结构
C ）程序执行的效率只取决于所处理的数据量
D ）以上三种说法都不对
题目解析:采用的存储结构不同，其数据处理的效率是不同的，程序执行的效率也就不同，因此选项A ）是正确的。程序执行的效率不仅与程序的控制结构有关，而且与所处理的数据量有关，因此选项 B）、C ）、D ）都不正确。
75. 下列与队列结构有关联的是（ ）。答案：D
A ）函数的递归调用
B ）数组元素的引用
C ）多重循环的执行
D ）先到先服务的作业调度
题目解析:队列是按照先进先出的原则组织数据的，可以看出以下四个选项中，与队列结构有关联的是D ）选项。
76.
（ ）。答案：C
A ）DYBEAFCZX
B ）YDEBFZXCA
C ）ABDYECFXZ
D ）ABCDEFXYZ
题目解析:前序遍历的过程是首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。根据图可以分析出，该二叉树的前序遍历结果为C ）。
77. 一个栈的初始状态为空。现将元素1,2,3,A,B,C 依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。答案：C
A ）1,2,3,A,B,C
B ）C,B,A,1,2,3
C ）C,B,A,3,2,1
D ）1,2,3,C,B,A
题目解析:栈是先进后出的原则组织数据，所以入栈最早的最后出栈，所以选择C) 。
78. 下列叙述中正确的是（ ）。答案：D
A ）一个算法的空间复杂度大，则其时间复杂度也必定大
B ）一个算法的空间复杂度大，则其时间复杂度必定小
C ）一个算法的时间复杂度大，则其空间复杂度必定小
D ）算法的时间复杂度与空间复杂度没有直接关系
题目解析:算法的时间复杂度是指之行算法所需要的计算工作量；算法的空间复杂度是指执行这个算法所需要的内存空间，两者之间没有直接关系。
79. 下列叙述中正确的是（ ）。答案：A
A ）循环队列中的元素个数随队头指针与队尾指针的变化而动态变化
B ）循环队列中的元素个数随队头指针的变化而动态变化
C ）循环队列中的元素个数随队尾指针的变化而动态变化
D ）以上说法都不对
题目解析:循环队列中的元素个数随队头指针与队尾指针的变化而动态变化，选A ）。
80. 一棵二叉树中共有80个叶子结点与70个度为1的结点，则该二叉树中的总结点数为（ ）。答案：B
A ）219
B ）229
C ）230
D ）231
题目解析:根据二叉树的性质，度为0的结点（即叶子结点）总是比度为2的结点多一个，叶子结点为80，度为2的结点为79，所以总结点数为：80+70+79=229，选B ）。
81. 对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为（ ）。答案：C
A ）9
B ）10
C ）45
D ）90
题目解析:在最坏情况下，冒泡排序的时间复杂度为n(n-1)/2，为45，答案选C ）。
82. 下列叙述中正确的是（ ）。答案：B
A ）算法的效率只与问题的规模有关，而与数据的存储结构无关
B ）算法的时间复杂度是指执行算法所需要的计算工作量
C ）数据的逻辑结构与存储结构是一一对应的
D ）算法的时间复杂度与空间复杂度一定相关
题目解析:算法的时间复杂度是指执行算法所需要的计算工作量，与数据的存储结构有关，与算法的空间复杂度没有关系。数据的逻辑结构与存储位置无关，即与存储结构无关，所以选择B ）。
83. 下列叙述中正确的是（ ）。答案：C
A ）线性表链式存储结构的存储空间一般要少于顺序存储结构
B ）线性表链式存储结构与顺序存储结构的存储空间都是连续的
C ）线性表链式存储结构的存储空间可以是连续的，也可以是不连续的
D ）以上说法都不对
题目解析:在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的，所以选择C ）。
84. 某二叉树共有12个结点，其中叶子结点只有1个。则该二叉树的深度为（根结点在第1层）（ ）。答案：D
A ）3
B ）6
C ）8
D ）12
题目解析:根据二叉树的性质，叶子结点比度为2的结点个数多一个，叶子结点只有1个，那么度为2的结点为0个，可以得出共有11个度为1的结点，那么该二叉树每一层上只能有一个结点，共12层，即深度为12。
85. 对长度为n 的线性表作快速排序，在最坏情况下，比较次数为（ ）。答案：D
A ）n
B ）n-1
C ）n(n-1)
D ）n(n-1)/2
题目解析:在最坏情况下，快速排序需要比较n(n-1)/2次。
86. 下列叙述中正确的是（ ）。答案：D
A ）有且只有一个根结点的数据结构一定是线性结构
B ）每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构
C ）有且只有一个根结点的数据结构一定是非线性结构
D ）有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构
题目解析:有且只有一个根结点的数据结构可以是线性结构，如队列，也可以是非线性结构，如二叉树，所以选项D ）正确。选项B ）中，如果有两个根结点，则不符合线性结构的条件，说法错误。本题答案选D ）。
87. 下列叙述中错误的是（ ）。答案：C
A ）在双向链表中，可以从任何一个结点开始直接遍历到所有结点
B ）在循环链表中，可以从任何一个结点开始直接遍历到所有结点
C ）在线性单链表中，可以从任何一个结点开始直接遍历到所有结点
D ）在二叉链表中，可以从根结点开始遍历到所有结点
题目解析:在线性单链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，但不能找到前件结点，选项C ）说法错误。
88. 某二叉树共有13个结点，其中有4个度为1的结点，则叶子结点数为（ ）。答案：A
A ）5
B ）4
C ）3
D ）2
题目解析:在线性单链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，但不能找到前件结点，选项C ）说法错误。
89. 设栈的顺序存储空间为S(1: 50), 初始状态为top=0。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（ ）。答案：C
A ）30
B ）29
C ）20
D ）19
题目解析:在栈中，top 位置直接反映栈中元素的个数，top=20，则说明当前栈中的元素个数为20。
90. 下列叙述中正确的是（ ）。答案：B
A ）栈与队列都只能顺序存储
B ）循环队列是队列的顺序存储结构
C ）循环链表是循环队列的链式存储结构
D ）以上说法都不对
题目解析:栈和队列都可以采用链式存储结构，选项A ）错误。队列的顺序存储结构一般采用循环队列的形式，所以循环队列是队列的顺序存储结构，选项B 正确，选项C ）错误。答案选B ）。
91. 设某二叉树的前序序列为ABC ，中序序列为CBA ，则该二叉树的后序序列为（ ）。答案：B
A ）BCA
B ）CBA
C ）ABC
D ）CAB
题目解析:前序序列为ABC ，中序序列为CBA ，说明根结点为A ，且B 和C 均在该A 的左子树上；结点B 和C 的前序序列为BC ，中序序列为CB ，则说明结点C 在结点B 的左子树上，根据以上分析，该二叉树的后序序列为CBA ，答案选B ）。
92. 下列排序方法中，最坏情况下时间复杂度最小的是（ ）。答案：C
A ）冒泡排序
B ）快速排序
C ）堆排序
D ）直接插入排序
题目解析:在最坏情况下，堆排序时间复杂度为O(nlog2n) ，其余选项均为O(n) ，所以答案选C ）。 2
93. 为了对有序表进行对分查找，则要求有序表（ ）。答案：A
A ）只能顺序存储
B ）只能链式存储
C ）可以顺序存储也可以链式存储
D ）任何存储方式
题目解析:对分查找必须满足用顺序存储结构，且线性表是有序表两个条件，答案选A ）。
94. 设某二叉树的后序序列为CBA ，中序序列为ABC ，则该二叉树的前序序列为（ ）。答案：C
A ）BCA
B ）CBA
C ）ABC
D ）CAB
题目解析:后序序列为CBA ，中序序列为ABC ，则说明，A 为根结点，并且B 和C 均在A 的右子树上；结点B 和C 中，后序序列为CB ，中序序列为BC ，则说明结点C 在结点B 的右子树上，根据分析可得，该二叉树的前序序列为ABC ，答案选C ）。
95. 下列叙述中正确的是（ ）。答案：D
A ）存储空间不连续的所有链表一定是非线性结构
B ）结点中有多个指针域的所有链表一定是非线性结构
C ）能顺序存储的数据结构一定是线性结构
D ）带链的栈与队列是线性结构
题目解析:判断一个非空的数据结构是否为线性结构必须满足以下两个条件：① 有且只有一个根结点；② 每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项A ）、
B ）和C ）都不能判定是否是线性结构，选项D ）正确，答案选D ）。
96. 算法时间复杂度的度量方法是（ ）。答案：B
A ）算法程序的长度
B ）执行算法所需要的基本运算次数
C ）执行算法所需要的所有运算次数
D ）执行算法所需要的时间
题目解析:算法的时间复杂度，是指执行算法所需要的计算工作量，算法的工作量用算法所执行的基本运行次数来度量，答案选B ）。
97. 设循环队列为Q(1: m)，初始状态为front=rear=m。现经过一系列的入队与退队运算后，front=rear=1，则该循环队列中的元素个数为（ ）。答案：D
A ）1
B ）2
C ）m-1
D ）0或m
题目解析:在循环队列中，当front=rear时，有两种情况，一种是队列为空，另一种是队列为满，所以答案选D ）。
98. 在最坏情况下（ ）。答案：C
A ）快速排序的时间复杂度比冒泡排序的时间复杂度要小
B ）快速排序的时间复杂度比希尔排序的时间复杂度要小
C ）希尔排序的时间复杂度比直接插入排序的时间复杂度要小
D ）快速排序的时间复杂度与希尔排序的时间复杂度是一样的
题目解析:在最坏情况下，快速排序、冒泡排序和直接插入排序所需要的比较次数为O(n) ，希尔排序所需要的比较次数为O(n) ，所以答案选C ）。 1.52
99. 在深度为7的满二叉树中，度为2的结点个数为（ ）。答案：B
A ）64
B ）63
C ）32
D ）31
题目解析:根据满二叉树的性质，深度为7的满二叉树共有2-1=127个结点。根据二叉树的性质，该满二叉树在第7层上，共有2=64个结点，即共有64个叶子结点，那么度为2的结点个数为127-64=63个。 7-17
100. 设栈的顺序存储空间为S(1: m) ，初始状态为top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为（ ）。答案：C
A ）30
B ）20
C ）m-19
D ）m-20
题目解析:初始状态为top=m+1，经过运算之后，top=20，则当前栈中元素个数为m+1-20=m-19个。
101. 算法空间复杂度的度量方法是（ ）。答案：D
A ）算法程序的长度
B ）算法所处理的数据量
C ）执行算法所需要的工作单元
D ）执行算法所需要的存储空间
题目解析:算法的空间复杂度，一般是指执行这个算法所需要的内存空间，答案选D ）。 102. 下面不属于软件开发阶段任务的是（ ）。答案：B
A ）测试
B ）可行性研究
C ）设计
D ）实现
题目解析:可行性研究是属于软件定义阶段的任务，所以答案选B ）。
103. 设循环队列为Q(1: m) ，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为（ ）。答案：A
A ）4
B ）6
C ）m-5
D ）m-6
题目解析:初始状态为front=rear=m，说明初始状态为空。经过一系列入队与退队运算后，front=15，rear=20，则当前共有5个元素，则在最坏情况下，需要比较的次数为4次，答案选
A ）。
104. 下列叙述中正确的是（ ）。答案：D
A ）循环队列属于队列的链式存储结构
B ）双向链表是二叉树的链式存储结构
C ）非线性结构只能采用链式存储结构
D ）有的非线性结构也可以采用顺序存储结构
题目解析:循环队列属于队列的顺序存储结构，选项A ）错误；二叉树的存储结构为二叉链表，选项B ）错误；非线性结构也可以采用顺序存储结构，因此选项C ）错误，选项D ）正确，答案为D ）。
105. 某二叉树中有n 个叶子结点，则该二叉树中度为2的结点数为（ ）。答案：B
A ）n+1
B ）n-1
C ）2n
D ）n/2
题目解析:根据二叉树的性质，叶子结点的个数比度为2的结点数多一个，因此答案为B) 。 106. 下列叙述中错误的是（ ）。答案：C
A ）算法的时间复杂度与算法所处理数据的存储结构有直接关系
B ）算法的空间复杂度与算法所处理数据的存储结构有直接关系
C ）算法的时间复杂度与空间复杂度有直接关系
D ）以上说法都不对
题目解析:算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，并且两者之间美欧直接关系，因此答案选C ）。
107. 设栈的顺序存储空间为S(0:49)，栈底指针bottom=49，栈顶指针top=30（指向栈顶元素）。则栈中的元素个数为（ ）。答案：C
A ）30
B ）29
C ）20
D ）19
题目解析:算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，并且两者之间美欧直接关系，因此答案选C ）。
108. 某二叉树的前序序列为ABCDEFG ，中序序列为DCBAEFG ，则该二叉树的深度（根结点在第1层）为（ ）。答案：C
A ）2
B ）3
C ）4
D ）5
题目解析:该二叉树的前序序列为ABCDEFG ，中序序列为DCBAEFG ，可知A 为根结点，结点B 、C 、D 位于根结点的左子树上，结点E 、F 、G 位于根结点的右子树上；并且结点B 、C 、D 在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点E 、F 、G 顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树深度为4，答案选C ）。
109. 下列叙述中正确的是（ ）。答案：D
A ）存储空间连续的数据结构一定是线性结构
B ）存储空间不连续的数据结构一定是非线性结构
C ）没有根结点的非空数据结构一定是线性结构
D ）具有两个根结点的数据结构一定是非线性结构
题目解析:判断一个非空的数据结构是否为线性结构必须满足以下两个条件：① 有且只有一个根结点；② 每一个结点最多有一个前件，也最多有一个后件。根据这两个条件，可知选项A ）、
B ）和C ）都不能判定是否是线性结构，选项D ）正确，答案选D ）。
110. 下列叙述中正确的是（ ）。答案：C
A ）带链队列的存储空间可以不连续，但队头指针必须大于队尾指针
B ）带链队列的存储空间可以不连续，但队头指针必须小于队尾指针
C ）带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针
D ）以上说法都不对
题目解析:带链队列的存储空间可以不连续，且队头指针与队尾指针大小没有可比性，答案选C ）。 111. 设循环队列为Q(1:m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=20，rear=15。现要在该循环队列中寻找最小值的元素，最坏情况下需要比较的次数为（ ）。答案：D
A ）5
B ）6
C ）m-5
D ）m-6
题目解析:该循环队列的容量为m ，队列中共有15-20+m=m-5个元素，如果想找出其中的最小值，最坏情况下需要比较m-5-1=m-6次。
112. 某二叉树的前序序列为ABCDEFG ，中序序列为DCBAEFG ，则该二叉树的后序序列为（ ）。答案：D
A ）EFGDCBA
B ）DCBEFGA
C ）BCDGFEA
D ）DCBGFEA
题目解析:该二叉树的前序序列为ABCDEFG ，中序序列为DCBAEFG ，可知A 为根结点，结点B 、C 、D 位于根结点的左子树上，结点E 、F 、G 位于根结点的右子树上；并且结点B 、C 、D 在前序序列和中序序列中顺序颠倒，则说明这三个结点依次位于前一个结点的左子树上；结点E 、F 、G 顺序未变，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树的后序遍历序列为DCBGFEA ，答案选D ）。
113. 下列叙述中正确的是（ ）。答案：B
A ）在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构
B ）在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构
C ）在链表中，如果每个结点有两个指针域，则该链表一定是线性结构
D ）在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构
题目解析:判断一个非空的数据结构是否为线性结构必须满足以下两个条件：① 有且只有一个根结点；② 每一个结点最多有一个前件，也最多有一个后件。选项B ）中，如果有两个结点的同一个指针域的值相等，则说明至少有一个结点有两个前件，不符合线性结构的定义，所以答案选B ）。
114. 下列叙述中错误的是（ ）。答案：B
A ）在带链队列中，队头指针和队尾指针都是在动态变化的
B ）在带链栈中，栈顶指针和栈底指针都是在动态变化的
C ）在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的
D ）以上说法均不对
题目解析:在栈结构中，插入和删除操作都是在栈顶进行操作，相对应的在带链栈中，栈顶指针是在动态变化的，但栈底指针是不变的，所以选项B ）说法错误。
115. 设数据元素的集合D={ 1,2,3,4,5 }，则满足下列关系R 的数据结构中为线性结构的是（ ）。答案：B
A ）R={ (1,2), (3,4), (5,1) }
B ）R={ (1,3), (4,1), (3,2), (5,4) }
C ）R={ (1,2), (2,3), (4,5) }
D ）R={ (1,3), (2,4), (3,5) }
题目解析:关系R 中的每个结点由两个部分构成，分别是数据域和指针域。选项B ）中可以看出，元素序列为5→4→1→3→2，符合线性结构的条件。选项A ）、选项C ）和选项D ）中分别有两个根结点，不符合线性结构的条件。所以答案选B ）。
116. 下列叙述中正确的是（ ）。答案：A
A ）链表结点中具有两个指针域的数据结构可以是线性结构，也可以是非线性结构
B ）线性表的链式存储结构中，每个结点必须有指向前件和指向后件的两个指针
C ）线性表的链式存储结构中，每个结点只能有一个指向后件的指针
D ）线性表的链式存储结构中，叶子结点的指针只能是空
题目解析:在链式存储方式中，每个结点由两部分组成：数据域和指针域，指针域用于指向该节点的前一个或后一个结点，所以选项B ）、C ）、D ）说法错误。选项A ）中，例如双向链表就具有两个指针，也属于线性结构，所以答案选A ）。
117. 一个栈的初始状态为空。现将元素A,B,C,D,E 依次入栈，然后依次退栈三次，并将退栈的三个元素依次入队（原队列为空），最后将队列中的元素全部退出。则元素退队的顺序为（ ）。答案：C
A ）ABC
B ）CBA
C ）EDC
D ）CDE
题目解析:栈是根据先进后出的原则组织数据，所以退栈三次的元素依次为E 、D 、C ；队列是根据先进先出的原则组织数据的，所以退队的顺序依次为E 、D 、C ，答案选C ）。
118. 某二叉树的中序序列为DCBAEFG ，后序序列为DCBGFEA ，则该二叉树的深度（根结点在第1层）为（ ）。答案：B
A ）5
B ）4
C ）3
D ）2
题目解析:该二叉树的中序序列为DCBAEFG ，后序序列为DCBGFEA ，可知A 为根结点，结点B 、C 、D 位于根结点的左子树上，结点E 、F 、G 位于根结点的右子树上；并且结点B 、C 、D 在中序序列和后序序列中顺序未变，则说明这三个结点依次位于前一个结点的左子树上；结点E 、F 、G 顺序颠倒，则说明这三个结点依次位于前一个结点的右子树上。根据以上分析，该二叉树的深度为4，答案选B ）。