课后自测-7_32

7.1 自测练习

一、判断题

1. 2. 3. 4. 5. 6. 7. 8.

程序的核心是算法。

算法就是程序，程序就是算法。

算法与程序不同，算法是问题求解规则的一种过程描述。 算法必须用程序设计语言来表示。 算法一定要用“伪代码”（一种介于自然语言和程序设计语言之间的文字和符号表达工具）来描述。 一个算法可以不满足能行性。

一个算法可以没有输出，但至少应有一个输入。

算法和数据结构之间存在密切关系，算法往往建立在数据结构的基础上，若数据结构不同，对应问题的求解算法也会有差异。

9. 评价一个算法的效率应从空间代价和时间代价两方面进行考虑。

10. 对于同一个问题可采用不同的算法去解决，但不同的算法通常具有相同的效率。 11. 一个完整的算法必须有输出。

12. 算法的效率包括空间效率和时间效率。

13. 一个算法必须有外部提供的输入，否则无法确定其初始条件。 14. 一个算法只要正确，即使没有输出也是可以的。 15. 数据的逻辑结构与数据的存储无关，于计算机。 16. 数据的存储结构可以分为顺序存储和链式存储两种。 17. 数据的逻辑结构可分为线性结构和非线性结构两类。

18. 线性表采用链式存储结构要求存储单元的地址必须是连续的。 19. 线性表的顺序结构比链式结构更利于元素的插入、删除。 20. 栈和队列逻辑上都是线性表。

21. 若让元素1,2,3依次进栈，则出栈顺序1,3,2是不可能出现的情况。

22. 队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进先出的结构。 23. 线性表中每个元素都有一个直接前驱和一个直接后继。

24. 二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。

25. 二叉树中不存在度大于2的结点。当某个结点只有一棵子树时，无所谓左、右子树。 26. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。 27. 如果无向图中每个顶点的度都大于等于2，则该图中必有回路。

28. 使用枚举法解决问题，在列举问题可能解的过程中，不能遗漏，但可以重复。 29. 贪心算法往往比较简单，但不能保证求得的最后解是最佳的，因此不具有价值。

30. 动态规划算法与分治法类似，其基本思想都是将待求解问题分解成若干个子问题，两者的区别是：分治

法中的各个子问题是的，而动态规划法允许子问题不。

二、填空题

1. 使用计算机求解问题的主要步骤是：先要理解和确定问题，然后寻找其解决方法并将其表示成 ，接着再进行编程、调试和运行。 2. 算法是对问题求解过程的一种描述，“算法中的操作都是可以具体执行的，即在计算机的能力范围之内，

且在有限时间内能够完成”，这句话所描述的性质被称为算法的 。

1

3. 为解决某一问题而设计的确定的有限的步骤称为 。

4. 算法应具备输入、输出、有穷性、 和 等特性。

5. 解决某一问题的算法也许有多种，但它们都必须满足确定性、有穷性、能行性、输入和输出等性质，其中

输出的个数n应大于等于 （填一个数字）。 6. 7. 8. 9.

算法可以使用 、 、N-S图、 和程序设计语言等工具进行描述。 对算法和 的设计是程序设计的主要内容。 程序= 结构+ 。

是数据组织形式，反映数据之间的关系，但不涉及数据的具体内容。

10. 衡量一个算法的优劣通常可以从它的 、 和易理解性等三个方面来考虑。 11. 算法的运行效率主要是指算法所耗费的 和占用的 。

12. 若求解某个问题的程序要反复多次执行，则在设计求解算法时，应重点从 代价上考虑。

13. 若有问题规模为n的算法，其主运算的时间代价表示为f(n)=n2+5n+c(c为常数)，则该算法的时间复杂性可

表示为O( )。

14. 研究数据结构就是研究数据的逻辑结构、 及其对数据的运算。 15. 数据的逻辑结构分为 和非线性结构两大类。

16. 线性结构中元素之间存在着 关系，树型结构中元素之间存在着 关系。 17. 数据的存储结构主要分为 和 两种。

18. 在线性表的顺序存储结构中，元素之间的逻辑关系是通过 决定的；而链式存储中，元素之间

的逻辑关系是通过 决定的。

19. 顺序表相对于链表的优点有 和 。

20. 在单链表中除首结点外，任意结点的存储位置都由直接前驱结点中的 指示。

21. 长为n的顺序存储的线性表，当在任何位置上删除元素的概率相等时，删除一个元素所需移动的元素

平均数为 。

22. 若一线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用 存储方式最节省时间。

23. 设输入元素的顺序为1,2,3,4,5，要使出栈序列为43521，则应进行的栈的基本操作为

PUSH(S,1),PUSH(S,2),PUSH(S,3),PUSH(S,4),POP(S), ,POP(S),POP(S),POP(2)。 24. 在求表达式值的算符优先算法中使用的主要数据结构是 。

25. 用一个大小为1000的数组来实现循环队列，当前rear和front的值分别为0和994，若要达到队满的条

件，还需要继续入队的元素个数是 。

26. 一棵完全二叉树，按层次遍历的序列是ABCDEFG，则在先序遍历中结点E的直接前驱是 ，

在后序遍历中结点B的直接后继是 。 27.

28. 递归算法是把问题转化为规模缩小了的同类问题的 ，然后递归调用函数（或过程）来表示问题

的解。

29. 回溯法是一种满足某些 的穷举搜索法。 30. 二分搜索法是 算法的应用。

三、选择题

1. 计算机算法指的是 。

A. 计算方法 B. 调度方法 C. 排序方法 D. 解决某一问题的有限步骤 2. 为解决某一问题而设计的确定的有限的步骤称为 。

A. 文件 B. 算法 C. 指令 D. 软件 3. 看下面的四段话，其中不是解决问题的算法的是 。

A. 从济南到北京旅游，先坐火车，再坐飞机抵达

2

4.

5.

6.

7. 8.

9.

10. 11.

12.

13.

B. 解一元一次方程的步骤是去分母、去括号、移项、合并同类项、系数化为1 C. 方程x2-1=0有两个实根

D. 求1+2+3+4+5的值，先算1+2=3，再算3+3=6，6+4=10，10+5=15，最终结果为15 用算法解决问题的一般过程为 。

A. 分析问题、设计算法、用计算机进行处理（编程及调试） B. 设计算法、分析问题、用计算机进行处理（编程及调试） C. 分析问题、用计算机进行处理（编程及调试）、设计算法 D. 输入、处理、输出

下列有关算法及其性质的叙述错误的是 。

A. 算法的设计一般采用由粗到细、由抽象到具体的逐步求精的方法 B. 算法必须具有确定性、有穷性和能行性等基本性质

C. 算法均必须有多个输入量，至少有一个输出量（包括参量状态的变化） D. 一个算法的好坏，需要考虑执行该算法所要占用的计算机资源 下列关于算法的叙述正确的是 。 A. 算法必须产生正确的结果 B. 算法可以没有输出 C. 算法必须具有确定性 D. 算法的表示必须使计算机能理解

算法的特征是：有穷性、 、能行性、有0个或多个输入和有一个或多个输出。 A. 稳定性 B. 确定性 C. 正常性 D. 快速性 算法的有穷性是指 。 A. 算法必须包含输出

B. 算法中每个操作步骤都是可执行的

C. 算法的步骤必有限或以在合理的时间范围内完成全部操作 D. 算法必须包含输入

一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现。这句话说明算法具有 特性。 A. 有穷性 B. 可行性 C. 确定性 D. 健壮性 下列性质中，不符合算法特征的是 。 A. 无二义性 B. 有穷性 C. 能行性性 D. 确定性

算法中的输入，是指算法在执行时需要从外界（如：键盘）取得数据信息，其目的是为算法的某些阶段建立初始状态，一个算法的输入可以0个，是因为： 。 A. 该算法的运算不涉及任何数据信息 B. 该算法不需要初始状态的数据信息

C. 建立初始状态所需要的数据信息已经包含在算法中 D. 以上说法都正确

算法中的输出是指算法在执行过程中或终止前，需要将解决问题的结果以一定方式反馈给用户，这种信息的反馈称为输出，关于算法中输出的描述以下正确的是： 。 A. 算法至少有1个输出，该输出可以出现在算法的结束部分 B. 算法可以有多个输出，所有输出必须出现在算法的结束部分 C. 算法可以没有输出，因为该算法运行结果为“无解” D. 以上说法都错误

关于算法的能行性特征，以下描述不符合能行性的是： 。 A. a← 4 ； b ← 20 ； Temp ←

(ab)

B. a← 4 ； b ← 20 ； Temp ← (ba)

3

C. a← 4 ； b ← 20 ； Temp ← D. a← 4 ； b ← 20 ； Temp ←

(|ab|)

(ab)*(ab)

14. 算法能正确地实现预定功能的特性称为算法的 。

A. 健壮性 B. 易读性 C. 正确性 D. 高效率

15. 用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中

的 。 A. 唯一性 B. 有穷性 C. 有输出 D. 有0个或多个输入 16. 下列有关算法和程序关系的叙述正确的是 。

A. 算法必须使用程序设计语言进行描述 B. 算法与程序是一一对应的 C. 算法是程序的简化 D. 程序是算法的具体实现 17. 下列叙述错误的是 。

A. 程序就是算法，算法就是程序 B. 程序是用某种计算机语言编写的语句的集合 C. 软件的主体是程序 D. 只要软件运行环境不变，它们功能和性能不会发生变化 18. 著名的计算机科学家尼·沃思提出了 。

A. 数据结构+算法=程序 B. 存储控制结构 C. 信息熵 D. 控制论

19. 下列有关程序、算法和数据结构的叙述错误的是 。

A. 程序是用程序设计语言对解题对象和解题步骤进行的一种描述 B. 算法和数据结构是设计与编写程序时首先要考虑的两个重要方面

C. 算法是问题求解规则的一种过程描述，它必须有输入，但可以没有输出

D. 数据结构主要是研究数据的逻辑结构、存储结构以及在这些数据上定义的运算 20. 下列有关算法和数据结构的叙述错误的是 。

A. 算法描述解决问题的步骤，数据结构描述求解问题的对象 B. 算法应具有确定性、有穷性和能行性

C. 数据结构研究的内容包括数据的逻辑结构和存储结构，与数据的运算无关 D. 精心选择和设计的数据结构可以提高算法的时间效率和空间效率 21. 算法的表示形式有： 。

A. 流程图 B. 算法描述语言 C. 判定表 D. 以上都是 22. 常用的算法描述方法是 。

A. 自然语言、机器语言、伪代码 B. 伪代码、流程图、机器语言 C. 流程图、自然语言、伪代码 D. 低级语言、自然语言、流程图 23. 流程图中的处理框，有 。

A. 一个入口和两个出口 B. 两个入口和一个出口 C. 一个入口和一个出口 D. 两个入口和两个出口 24. 流程图中的判断框，有一个入口和 个出口。

A. 1 B. 2 C. 3 D. 4

25. 关于流程图中的开始、结束符号，以下说法正确的是： 。

A. 一个算法可以有多个开始处，但只能有一个结束处 B. 一个算法只能有一个开始处，但可以有多个结束处 C. 一个算法可以有多个开始处，也可以有多个结束处 D. 一个算法不能有多个开始处，也不能有多个结束处 26. 以下描述算法的方法中，计算机可以执行的是 。

A. 流程图 B. 自然语言 C. 伪代码 D. 计算机程序代码

4

27. 从算法需要占用的计算机资源角度分析其优劣时，应考虑的两个主要方面是 。

A. 空间代价和时间代价 B. 可读性和开放性 C. 正确性和简明性 D. 数据复杂性和程序复杂性 28. 分析算法的好坏不必考虑 。

A. 正确性 B. 易理解 C. 需要占用的计算机资源 D. 编程人员的爱好

29. 在一个算法中所包含的简单操作的执行次数，称为算法的 。

A. 可实现性 B. 时间复杂度 C. 困难度 D. 计算有效性 30. 算法执行过程中所需要占用的计算机存储空间大小称为 。

A. 可行性 B. 高效性 C. 可实现性 D. 空间复杂度

31. 对一个数组A[n]进行特定要求的处理，设计了4种算法，其时间复杂性函数分别如下，其中 耗

时最少？ A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2)

32. 若对一个数组S[m]进行特定要求的处理，设计了4种算法，其空间复杂性函数如下，其中 空间开销最大？ A. O(log2m) B. O(m) C. O(mlog2m) D. O(m2) 33. 在数据结构中，与所使用的计算机无关的数据结构是 。

A. 逻辑结构 B. 存储结构 C. 物理结构 D. 逻辑和存储结构 34. 数据在计算机内存中的表示是指 。

A. 数据结构 B. 数据的存储结构 C. 数据的逻辑结构 D. 数据元素之间的关系

35. 数据的 包括集合、线性结构、树型结构和图状结构四种基本类型。

A. 算法描述 B. 基本运算 C. 逻辑结构 D. 存储结构 36. 在数据结构中，从逻辑上可以把数据结构分成 。

A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 37. 数据的存储结构包括顺序、 、索引和散列四种基本类型。

A. 向量 B. 数组 C. 集合 D. 链式

38. 数据结构是研究程序设计中计算机操作对象以及它们之间关系和运算的一个专门学科。下列数据结构

的叙述错误的是 。

A. 数据结构仅研究数据的逻辑结构和存储结构，不考虑在该结构上的数据运算 B. 数据的存储结构是其逻辑结构在计算机存储器上的实现

C. 数据的逻辑结构是数据间关系的描述，它只抽象的反映数据元素间的逻辑关系 D. 线性表和树是典型的数据逻辑结构，链接表是典型的数据存储结构

39. 数据的 用于抽象地反映数据元素之间的约束关系而不考虑其在计算机中的存储方式。

A. 存储结构 B. 层次结构 C. 逻+辑结构 D. 物理结构 40. 以下不属于“数据结构”研究内容的是 。

A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的获取 D. 在数据上定义的运算

41. 数据的 包括查找、插入、删除、更新、排序等操作类型。

A. 存储结构 B. 逻辑结构 C. 基本操作 D. 算法描述

42. 一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的存储地址是 。

A. 98 B. 100 C. 102 D. 106 43. 线性表是n个 的有限序列。

A. 表元素 B. 字符 C. 数据元素 D. 数据项

5

44. 在线性表的下列存储结构中，读取元素花费的时间最少的是 。

A. 单链表 B. 双链表 C. 循环链表 D. 顺序表 45. 对于线性表，以下 情况应采用链表表示。

A. 需要经常随机存取元素 B. 表中的元素个数不变 C. 需要经常插入和删除元素 D. 表中元素需要占用连续的存储空间 46. 栈和队列的共同点是 。

A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点

47. 一个栈的入栈序列为abcde，则栈的不可能的输出序列是 。

A. edcba B. decba C. dceab D. abcde

48. 某队列初始为空，若它的输入序列为abcd，则它的输出序列应为 。

A. abcd B. dcba C. acbd D. dacb 49. 二叉树的深度为k，则二叉树最多有 个结点。

A. 2k B. 2k-1 C. 2k-1 D. 2k-1

50. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是 。

A. a在b的右方 B. a在b的左方 C. a是d的祖先 D. a是b的子孙 51. 树的路径长度是树根到每个结点的路径长度的 。

A. 总和 B. 最小值 C. 最大值 D. 平均值 52. 为描述N个人之间的同学关系，可用 结构表示。

A. 线性表 B. 树 C. 图 D. 队列

53. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。

A. 1/2 B. 1 C. 2 D. 4

54. 采用盲目的搜索方法，在搜索结果的过程中，把各种可能的情况都考虑到，并对所得的结果逐一进行判

断，过滤掉那些不合要求的，保留那些合乎要求的结果，这种方法叫做 。 A. 递推法 B. 枚举法 C. 选择法 D. 解析法 55. 使用枚举法解决问题，在列举问题可能解的过程中， 。

A. 不能遗漏，但可以重复 B. 不能遗漏，也不应重复 C. 可以遗漏，但不应重复 D. 可以遗漏，也可以重复

56. 在算法设计的基本方法中， 是从初始条件出发，逐次推出所需求的结果。

A. 递推法 B. 递归法 C. 列举法 D. 归纳法

57. 给定一组长度为n的无序序列，将其存储在一维数组a[0…n-1]中。现采用如下方法找出其中的最大元素

和最小元素：比较a[0]和a[n-1]，若a[0]较大，则将二者的值进行交换；再比较a[1]和a[n-2]，若a[1]较大，则交换二者的值；然后依次比较a[2]和a[n-3]、a[3]和a[n-4]、…，使得每一对元素中的较小者被交换到低下标端。重复上述方法，在数组的前n/2个元素中查找最小元素中在后n/2个元素中查找最大元素，从而得到整个序列的最小元素和最大元素。上述方法采用的算法设计策略是 。 A. 动态规划法 B. 贪心法 C. 分治法 D. 回溯法 58. 以下的算法设计方法中， 以获取问题最优解为目标。

A. 回溯法 B. 分治法 C. 动态规划法 D. 递推法 59. 要在8×8的棋盘上摆放8个“皇后”，要求“皇后”之间不能发生冲突，即任何两个“皇后”不能在同

一行、同一列和相同的对角线上，则一般采用 来实现。 A. 分治法 B. 动态规划法 C. 贪心法 D. 回溯法

60. 设商店有10元、5元、2元和1元的零币，每种零币的数量充足。售货员给顾客找零钱时，零币的数量

越少越好。例如给顾客找零29元：先选2张10元，然后选择张5元，再选择两张2元。以上的找零钱方法采用了 策略。 A．分治 B．贪心 C．动态规划 D．回溯

6

7.2 参

一、判断题

1. √ 4. × 7. × 10. × 13. × 16. √ 19. × 22. √ 25. × 2. × 5. × 8. √ 11. √ 14. × 17. √ 20. √ 23. × 26. √ 3. √

6. ×

9. √

12. √

15. √

18. ×

21. ×

24. √

27. √

二、填空题

1. 算法 11. 时间，空间 21. （n-1）/2 2. 能行性 12. 时间 22. 链式

3. 算法

13. n2

23. POP(S),PUSH(S,5)4. 确定性，可行性 14. 存储结构 24. 栈 5. 1

15. 线性结构

25. 993 6. 自然语言，流程图，伪代码 16.

一对一，一对多

26. D,F 7. 数据结构 17. 顺序存储结构，链式存储结构

27.

8. 数据，算法 18. 物理存储位置，指针 28. 子问题 9. 数据结构

19. 随机访问，空间利用率高 29. 约束条件 10.

时间特性，空间特性

20. 指针

30.

分治

三、选择题

1. D 7. B 13. A 19. C 25. B 31. A 37. D 43. C 49. C 2. B 8. C 14. C 20. C 26. D 32. D 38. A 44. D 50. B 3. C 9. B 15. B 21. D 27. A 33. A 39. C 45. C 51. C 4. D 10. A 16. D 22. C 28. D 34. B 40. C 46. C 52. C 5. C 11. C 17. A 23. C 29. B 35. C 41. C 47. C 53. B 6. C

12.

A

18.

A

24.

B

30.

D

36.

C

42.

B

48.

A

54.

B

7

28. × 29. × 30. √

55. B 56. A 57. C 58. C 59. D 60.

B