实用数据结构基础（第四版）课后习题

一、判断题

（第一章 绪论）

1.数据元素是数据的最小单元。 答案：错误

2. 一个数据结构是由一个逻辑结构和这个逻辑结构上的基本运算集构成的整体。 答案：错误

3. 数据的存储结构是数据元素之间的逻辑关系和逻辑结构在计算机存储器内的映像。 答案：正确

4. 数据的逻辑结构是描述元素之间的逻辑关系，它是依赖于计算机的。 答案：错误

5.用语句频度来表示算法的时间复杂度的最大好处是可以独立于计算机的软硬件，分析算 法的时间 答案：正确

（第二章 线性表）

6.取顺序存储线性表的第i个元素的时间同i的大小有关。 答案：错误

7.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。 答案：正确

8.线性链表的每一个节点都恰好包含一个指针域。 答案：错误

9.顺序存储方式的优点的存储密度大，插入和删除效率不如练市存储方式好。 答案：正确

10.插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。 答案：错误 （第三章 栈）

11.栈是一种对进栈和出栈作了限制的线性表。 答案：错误

12.在C（或C++）语言中设顺序栈的长度为MAXLEN，则top=MAXLEN表示栈满。 答案：错误

13.链栈与顺序栈相比，其特点之一是通常不会出现满栈的情况。 答案：正确

14.空栈就是所有元素都为0上的栈。 答案：错误

15.将十进制数转换为二进制数是栈的典型应用之一。 答案：正确 （第四章 队列）

16.队列式限制在两端进行操作的线性表。 答案：正确

17.判断顺序队列为空的标准是头指针和尾指针都指向同一结点。 答案：错误

18.在循环链列队中无溢出现像。 答案：错误

19.在循环队列中，若尾指针rear大于头指针front，则元素个数为rear-front。 答案：正确

20.顺序队列和循环队列关于队满和队空的判断条件是一样的。 答案：错误 （第五章 串）

21.串是n个字母的有限序列。 答案：错误

22.串的堆分配存储是一种动态存储结构。 答案：正确

23.串的长度是指串中不同字符的个数。 答案：错误

24.如贵一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。 答案：错误

25.在链串中为了提高存储密度，应该增大结点的大小。 答案：正确

（第六章 对维数组和广义表）

26. n维的多维数组可以视为n-1维数组元素组成的线性结构。 答案：正确

27.上三角矩阵对主角线以上（不包括对主角线中的元素），均为常数C。 答案：错误

28.数组的三元组表存储时对稀疏矩阵的压缩存储。 答案：正确

29.广义表Ls=（a0，a1，......an-1），则an-1是其表尾。 答案：错误 30.广义表（（a,b），a,b）的表头和表尾是相等的。 答案：错误

（第七章 树和二叉树）

31.在完全二叉树中，若一个结点没有左孩子，则它必然是叶子节点。 答案：正确

32.含多于两棵树的森林转换到二叉树，其根节点一定无右子树。 答案：错误

33.二叉树的前序遍历中，任意一个节点均处于其子女节点的前面。 答案：正确

34.在中序线索二叉树中，右线索若不为空，则一定指向其双亲。 答案：错误

35.在哈夫曼编码中，当两个字符出现的频率相同的，其他编码也相同，对于这种情况应该做特殊处理。 答案：错误 （第八章 图） 36.在无相图中，（v1,v2）与（v2,v1）是两条不同的边。 答案：错误

37.图可以没有边，但不能没有顶点。 答案：正确

38.若一个无向图以顶点v1为起点，进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。 答案：错误

39.用邻接矩阵法存储一个图时，所占用的存储空间大小与图中的顶点个数无关，而只与图的边数有关。 答案：错误

40.存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。 答案：正确 （第九章 查找）

41.在有序的顺序表和有序的链表上，均可以采用二分查找法来提高查找速度。 答案：错误

42.在二叉排序树中，根节点的这都小于孩子节点的值。 答案：错误

43.选择好的哈希函数就可以避免冲突的发生。 答案：错误

44.散列存储法的基本思想是由关键字的值决定数据存储地址。 答案：正确

45.在二叉排序树上删除一个节点时，不必移动其他节点，只要将该节点的父节点的相应指针域置空即可。 答案：错误 （第十章 排序）

46.如果某种排序算法不稳定，则该排序方法就没有使用价值。 答案：错误

47.希尔排序是不稳定的排序。 答案：正确

48.对排序所需的时间与待排序的记录个数无关。 答案：错误

49.快速排序在任何情况下都比其他排序方法速度快。 答案：错误

50.采用归并排序可以实现外排序。 答案：错误

二、填空题

（第一章 绪论）

1. 数据结果是一门研究非数值计算的程序设计问题中计算机的___数据元素___，以及它们之间关系和运算的学科。

2. 数据有逻辑结构和 __存储结构__两种结构。

3. 数据逻辑结构除了集合以外的还包括线性结构，树形结构和__图形结构__。 4. 数据结构按逻辑结构可分为两大类，分别是线性结构和__非线性结构__。 5. 图形结构和__树形结构__合称为非线性结构。

6. 在树形结构中，除了树根节点以外，其余每个节点都只有__1__个前驱结点。 7. 在图形结构中，每一个节点的前驱节点上数和后继节点数可以__互换__。 8. 数据的存储结构，又叫做数据的__物理结构__。

9. 数据的存储结构形式，包括顺序存储，链式存储索引存储和__散列存储__。 10. 树形结构中的元素之间存在__1对多__的关系。 11. 图形结构的元素之间存在__多对多__的关系。

12. 数据结构主要研究数据的逻辑结构，存储结构和__算法__三方面的内容。

13. 数据结构被定义为(D,R),D是数据的有限集合，R是D上的__逻辑关系__的有限集合 14. 算法是对特定问题__解决步骤__的描述。

15. 算法效率的度量可以分为事先估算和__事后统计__。 16. 一个算法的时间复杂度是算法__数据规模__的函数。 17. 算法的空间复杂度是指该算法所耗费的__存储空间__，他是该算法求解问题规模n的函数。

18. 若一个算法中，还有10万条基本语句，但有问题的规模无关，则该算法的时间复杂度为__O(1)__。

19. 若一个算法中的语句频度之和为T(n)=6n+3nlog2n，则算法的时间复杂度为__O(n)__。 20. 若一个算法中的语句频度之和为T(n)=3n+nlog2n+n2，则算法的时间复杂度为__O(n^2)__。 （第二章 线性表）

1.在线性表中，数据的长度定义为__表长__。

2.顺序表中逻辑上相邻的元素在物理位置上__一定__相邻。 3.顺序表相对于链表的优点是__密度大__和随机存取。 4.某线性表采用顺序存储结构，每个元素占据4个存储单元，首地址为100则下标为11的(第12个元素)存储地址为__144__。

5.当线性表中的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取现象表中的元素时，应采用__顺序__存储结构。

6.顺序表中访问任意一个结点的时间复杂度均为__O …… 此处隐藏：3447字，全部文档内容请下载后查看。喜欢就下载吧 ……