内容发布更新时间 : 2024/12/28 12:11:38星期一 下面是文章的全部内容请认真阅读。
《数据结构与算法设计》习题册 第一章 绪论
一、单项选择题
1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 ① 以及它们之间的 ② 和运
算等的学科。
①A. 数据元素 B. 计算方法 C. 逻辑存储 D. 数据映象 ②A. 结构 B. 关系 C. 运算 D. 算法
2. 数据结构被形式地定义为（K，R），其中K是 ① 的有限集，R是K上的 ② 有限集。 ①A. 算法 B. 数据元素 C. 逻辑结构 D. 数据操作 ②A. 操作 B. 存储 C. 映象 D. 关系
3. 在数据结构中，从逻辑上可以把数据结构分成 。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构
4. 数据结构在计算机内存中的表示是指 。 A. 数据的存储结构 B. 数据结构
C. 数据的逻辑结构 D. 数据元素之间的关系
5. 在数据结构中，与所使用的计算机无关的是数据的 结构。 A. 逻辑 B. 存储 C. 逻辑和存储 D. 物理
6. 算法分析的目的是 ① ，算法分析的两个主要方面是 ② 。 ①A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ②A. 空间复杂度和时间复杂度 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性
7. 计算机算法指的是 ① ，它必须具备输入、输出和 ② 等5个特性。 ①A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性
8. 在以下叙述中，正确的是 。
A. 线性表的线性存储结构优于链表存储结构 C. 栈的操作方式是先进先出
B. 二维数组是其数据元素为线性表的线性表 D. 队列的操作方式是先进后出
9. 在决定选取何种存储结构时，一般不考虑 。
A. 各结点的值如何 B. 结点个数的多少 C. 对数据有哪些运算 D. 所用编程语言实现这种结构是否方便
10. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 。
A. 数据的处理方法 C. 数据元素之间的关系
B. 数据元素的类型 D. 数据的存储方法
11. 下面说法错误的是 。
（1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估计算法执行时间的一个上界 （4）同一个算法，实现语句的级别越高，执行效率越低 A. （1） B. （1）、（2） C. （1）、（4） D. （3）
12. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 。 A. 数据元素具有同一特点
B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样
D. 数据元素所包含的数据项的个数要相等
13. 以下说法正确的是 。 A. 数据元素是数据的最小单位 B. 数据项是数据的基本单位
C. 数据结构是带结构的各数据项的集合
D. 一些表面上很不相同的数据可以有相同的逻辑结构
二、填空题
1. 一个数据结构在计算机中的 称为存储结构。
2. 数据逻辑结构包括 ① 、 ② 和 ③ 三种结构，树形结构和图形结构合称为 ④ 。
3. 在线性结构中，第一个结点 ① 前驱结点，其余每个结点有且只有 ② 个前驱结点；最后一
个结点 ③ 后继结点，其余每个结点有且只有 ④ 个前驱结点。
4. 在树形结构中，树根结点没有 ① 结点，其余每个结点有且只有 ② 个前驱结点；叶子结点
没有 ③ 结点，其余每个结点的后继结点可以有 ④ 个。
5. 在图形结构中，每个结点的前驱结点数和后继结点数都可以有 个。
6. 线性结构中元素之间存在 ① 关系，树形结构中元素之间存在 ② 关系，图形结构中元素之
间存在 ③ 关系。
7. 算法的五个重要特性是 、 、 、输入和输出。
8. 算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实现上就是程
序了。这个断言是 （正确的或错误的）。
三、简答题
1. 设有数据逻辑结构为：
B=(K,R) K={k1,k2,...,k9}
R={
画出这个逻辑结构的图示，并确定相对关系R，哪些结点是开始结点，哪些结点是终端结点。
2. 设有如图1所示的逻辑结构图示，给出它的逻辑结构。
k1 k2 k6 k8 k9 图1 k7 k3 k4 k5
3. 有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表示，并指出它们分别属于何种
结构。
（1）A=(K,R)，其中：K={a,b,c,d,e,f,g,h} R={r}
r={
（2）B=(K,R)，其中：K={a,b,c,d,e,f,g,h} R={r}
r={
r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)} 这里的圆括号对表示两结点是双向的。
（4）D=(K,R)，其中：K={48,25,64,57,82,36,75} R={r1,r2} r1={<25,36>,<36,48>,<48,57>,<57,64>,<64,75>,<75,82>} r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<82,75>}
4. 当你为解决某一问题而选择数据结构时，应从哪些方面考虑？
四、算法设计题
1. 下面程序段的时间复杂度是 。