数据结构与算法总复习题ppt课件

《数据结构与算法总复习题ppt课件》由会员分享，可在线阅读，更多相关《数据结构与算法总复习题ppt课件（176页珍藏版）》请在金锄头文库上搜索。

1、在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么数据结构第一章在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。3. 数据结构包括数据的 逻辑结构 、数据的 存储结构

2、 、和数据的 运算 这三个方面的内容。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。5. 线性结构中元素之间存在 一对一 关系，树形结构中元素之间存在 一对多 关系，图形结构中元素之间存在多对多 关系。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么6 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有1个后续结点。在日常生活中

3、，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以 任意多个 。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。9数据的存储结构可用四种基本的存储方法表示，它们分别是 顺序 、 链式 、 索引 和 散列 。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这

4、一点点算不了什么10. 数据的运算最常用的有5种，它们分别是 插入 、 删除、修改、 查找 、排序 。11. 一个算法的效率可分为 时间 效率和 空间 效率。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么二、单项选择题（ B ）1. 非线性结构是数据元素之间存在一种： A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系（ C ）2. 数据结构中，与所使用的计算机无关的是数据的 结构； A) 存储 B) 物理 C) 逻辑 D) 物理和存储在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一

5、点点算不了什么（ C ）3. 算法分析的目的是： A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ A ）4. 算法分析的两个主要方面是：A) 空间复杂性和时间复杂性 B) 正确性和简明性C) 可读性和文档性 D) 数据复杂性和程序复杂性在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ C ）5. 计算机算法指的是：A) 计算方法 B) 排序方法 C) 解决

6、问题的有限运算序列 D) 调度方法在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ B ）6. 计算机算法必须具备输入、输出和 等5个特性。A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么三、简答题1.数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一

7、组操作。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2. 简述线性结构与非线性结构的不同点。答：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么3. 算法的定义和特性。算法是解决特定问题的有限指令序列。特性：有限性、确定性、可行性、有0个或多个输入数据、有1个或多个输出结果。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么4.数据结构的逻辑结

8、构有哪四类？集合结构、线性结构、树形结构、图形结构线性结构的前驱与后继之间为一对一关系，非线性结构的前驱与后继之间通常为一对多或多对多关系。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么第二章 线性表习题1 顺序表中逻辑上相邻的元素的物理位置 相邻。单链表中逻辑上相邻的元素的物理位置 相邻。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么一定不一定在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2 在单链表中，除了首元结点外，

9、任一结点的存储位置由其直接前驱结点的链域的值指示。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么3. 线性表中结点间的关系是线性表中结点间的关系是 一对一一对一 的。的。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么判断题（ ）1. 链表的每个结点中都恰好包含一个指针。 答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费

10、，也许你认为浪费这一点点算不了什么（ ）2. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。错，链表的结点不会移动，只是指针内容改变。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）3. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）4. 顺序表结构适宜于进行顺序存取，而链表适

11、宜于进行随机存取。 错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）5. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序

12、上相邻。错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么单项选择题（ ）1数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么C在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）2.一个向量第一个元素的

13、存储地址是100，每个元素的长度为2，则第5个元素的地址是 （A）110 （B）108 （C）100 （D）120在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么B在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）5. 链接存储的存储结构所占存储空间：A 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B 只有一部分，存放结点值C 只有一部分，存储表示结点间关系的指针D 分两部分，一部分存放结点值，另一部分存放结点所占单元数 在日常生活中，随处都可以看到浪费粮食的现象

14、。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么A在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）6. 链表是一种采用 存储结构存储的线性表；（A）顺序 （B）链式 （C）星式 （D）网状在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么B在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（A）必须是连续的 （B）部分地址必须是连续的（C）一定

15、是不连续的 （D）连续或不连续都可以在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么D在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）8 线性表在 情况下适用于使用链式结构实现。（）需经常修改线性表中的结点值 （）需不断对线性表进行删除插入 （）线性表中含有大量的结点 （）线性表中结点结构复杂在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么B在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为

16、浪费这一点点算不了什么（ ）10 设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）循环链表 （）单链表 （）双向循环链表 （）双向链表在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么B在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么简答题1. 【严题集2.3】试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么答：答： 顺序存

17、储时，相邻数据元素的存放地顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。用存储单元的地址必须是连续的。优点：存储空间利用率高。优点：存储空间利用率高。缺点：插入或删除元素时不方便。缺点：插入或删除元素时不方便。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么链式存储时，相邻数据元素可随意存链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间存放结点值，另一部分存放

18、表示结点间关系的指针关系的指针优点：插入或删除元素时很方便，使用优点：插入或删除元素时很方便，使用灵活。灵活。缺点：存储空间利用率低。缺点：存储空间利用率低。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么顺序表适宜于做顺序表适宜于做查找查找这样的静态操作；这样的静态操作；链表宜于做链表宜于做插入、删除插入、删除这样的动态操作。这样的动态操作。若线性表的长度变化不大，且其主要操若线性表的长度变化不大，且其主要操作是作是查找查找，则采用顺序表；，则采用顺序表；若线性表的长度变化较大，且其主要操若线性表的长度变化较大，且其主要操作是作是插入、

19、删除插入、删除操作，则采用链表。操作，则采用链表。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么第三章第三章在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么1. 向量向量(线性表线性表)、栈和队列都是、栈和队列都是 结构，可以在向量的结构，可以在向量的 位置插入和位置插入和删除元素；对于栈只能在删除元素；对于栈只能在 插入和插入和删除元素；对于队列只能在删除元素；对于队列只能在 插插入和入和 删除元素。删除元素。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费

20、，也许你认为浪费这一点点算不了什么1、向量、栈和队列都是、向量、栈和队列都是 线性线性 结构，结构，可以在向量的可以在向量的 任何任何 位置插入和删位置插入和删除元素；对于栈只能在除元素；对于栈只能在 栈顶栈顶 插入和插入和删除元素；对于队列只能在删除元素；对于队列只能在 队尾队尾 插入和插入和 队首队首 删除元素。删除元素。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2. 栈是一种特殊的线性表，允许插入和栈是一种特殊的线性表，允许插入和删除运算的一端称为删除运算的一端称为 。不允许。不允许插入和删除运算的一端称为插入和删除运算的一端

21、称为 。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶栈顶 。不允许插入和删除运算的一端称为 栈底栈底 。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么3. 是被限定为只能在表的一端进是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运行插入运算，在表的另一端进行删除运算的线性表。算的线性表。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么3. 队列队列

22、是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么二、判断正误（判断下列概念的正确性，二、判断正误（判断下列概念的正确性，并作出简要的说明。）并作出简要的说明。）（ ）1. 线性表的每个结点只能是一线性表的每个结点只能是一个简单类型，而链表的每个结点可以是个简单类型，而链表的每个结点可以是一个复杂类型。一个复杂类型。 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么二、判断正误（判断下列概念的正确性，二、判断正误（

23、判断下列概念的正确性，并作出简要的说明。）并作出简要的说明。）（ ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）2. 在表结构中最常用的是线性在表结构中最常用的是线性表，栈和队列不太常用。表，栈和队列不太常用。 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）2. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一

24、定吧？调用子程序或函数常用，CPU中也用队列。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）3. 栈是一种对所有插入、删除栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是操作限于在表的一端进行的线性表，是一种后进先出型结构。一种后进先出型结构。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这

25、一点点算不了什么（ ）6. 栈和队列是一种非线性数据栈和队列是一种非线性数据结构。结构。 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）6. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）7. 栈和队列的存储方式既可是栈和队列的存储方式既可是顺序方式，也可是链接方式。顺序方式，也可是链接方式。 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己

26、在浪费，也许你认为浪费这一点点算不了什么（ ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）8. 队是一种插入与删除操作分队是一种插入与删除操作分别在表的两端进行的线性表，是一种先别在表的两端进行的线性表，是一种先进后出型结构。进后出型结构。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）8. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。在日常生活中，随处都可以看到浪

27、费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）9. 一个栈的输入序列是一个栈的输入序列是12345，则栈的输出序列不可能是，则栈的输出序列不可能是12345。 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）9. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么三、单项选择题三、单项选择题（ ）1. 栈中元素的进出原则是栈中元素的进出原则是 先进先出先进先出 后进先出

28、后进先出 栈空则进栈空则进 栈满则出栈满则出在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么三、单项选择题三、单项选择题（ B ）1. 栈中元素的进出原则是 先进先出 后进先出 栈空则进 栈满则出在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么6. 【初程P71】 从供选择的答案中，选出应填入下面叙述 内的最确切的解答，把相应编号写在答卷的对应栏内。设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。

29、假设栈或队的初始状态都是空。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A ，第二次出栈得到的元素是 B 是；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C ，第二次出队得到的元素是 D 。经操作后，最后在栈中或队中的元素还有 E 个。供选择的答案：AD：a1 a2 a3 a4E： 1 2 3 0在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为

30、浪费这一点点算不了什么答：ABCDE2, 4, 1, 2, 2在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么第五章1. 假设有二维数组假设有二维数组A68，每个元素用相邻的，每个元素用相邻的6个字节存储，存储器按字节编址。已知个字节存储，存储器按字节编址。已知A的的起始存储位置（基地址）为起始存储位置（基地址）为1000，则数组，则数组A的体积（存储量）为的体积（存储量）为 ；末尾元素；末尾元素A57的第一个字节地址为的第一个字节地址为 ；若按行存；若按行存储时，元素储时，元素A14的第一个字节地址为的第一个字节地址为 ；若按列存储时，

31、元素；若按列存储时，元素A47的第一个字节地址的第一个字节地址为为 。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么1. 假设有二维数组A68，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 B ；末尾元素A57的第一个字节地址为 1282 ；若按行存储时，元素A14的第一个字节地址为 (8+4)6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为 (674)61000）1276 。(注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57

32、可知，是从0行0列开始！)在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2. 三元素组表中的每个结点对应于稀疏三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数矩阵的一个非零元素，它包含有三个数据项，分别表示该元素据项，分别表示该元素的的 、 和和 。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么2. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。在日常生活中，随处都可以看到浪费粮食的现

33、象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么5. 用三元组表表示下列稀疏矩阵：用三元组表表示下列稀疏矩阵：在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么解：三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。588521325843667570266405-2149325543在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么6 下列各三元组表分别表示一个稀疏矩下列各三元组表分别表示一个稀疏矩

34、阵，试写出它们的稀疏矩阵。阵，试写出它们的稀疏矩阵。455001139218246327在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么6 答：为45矩阵，非零元素有5个1 0 0 0 00 0 0 9 00 8 0 0 60 0 7 0 0在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么第六章第六章 一、下面是有关二叉树的叙述，请判断一、下面是有关二叉树的叙述，请判断正误正误（ ）1. 若二叉树用二叉链表作存贮若二叉树用二叉链表作存贮结构，则在结构，则在n个结点的二叉树链表中只有个

35、结点的二叉树链表中只有n1个非空指针域。个非空指针域。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）1. 若二叉树用二叉链表作存贮结若二叉树用二叉链表作存贮结构，则在构，则在n个结点的二叉树链表中只有个结点的二叉树链表中只有n1个非空指针域。个非空指针域。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）2.二叉树中每个结点的两棵子树二叉树中每个结点的两棵子树的高度差等于的高度差等于1。 （ ）3.二叉树中每个结点的两棵子树二叉树中每个结点的两棵子树是有序的。是有序的。在

36、日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）2.二叉树中每个结点的两棵子树二叉树中每个结点的两棵子树的高度差等于的高度差等于1。 （ ）3.二叉树中每个结点的两棵子树二叉树中每个结点的两棵子树是有序的。是有序的。 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）4.二叉树中每个结点的关键字值二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树结点的关键字值，且小于其右非空子树（若存在的话）所有结

37、点的关键字值。（若存在的话）所有结点的关键字值。 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）4.二叉树中每个结点的关键字值二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（若存在的话）所有结点的关键字值。 （没有这个要求）在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）5.对于一棵非空二叉树，它的根对于一棵非空二叉树，它

38、的根结点作为第一层，则它的第结点作为第一层，则它的第i层上最多能层上最多能有有 个结点。个结点。 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）5.对于一棵非空二叉树，它的根对于一棵非空二叉树，它的根结点作为第一层，则它的第结点作为第一层，则它的第i层上最多能层上最多能有有2i 1个结点。个结点。（应 ）在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）6.用二叉链表法（用二叉链表法（link-rlink）存）存储包含储包含n个结点的二叉树，结点的个结点的二叉树，结点的2

39、n个个指针区域中有指针区域中有n+1个为空指针。个为空指针。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）6.用二叉链表法（用二叉链表法（link-rlink）存）存储包含储包含n个结点的二叉树，结点的个结点的二叉树，结点的2n个个指针区域中有指针区域中有n+1个为空指针。个为空指针。（正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。在日常生活中，随处都可以看

40、到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么二、填空二、填空1 由个结点所构成的二叉树有由个结点所构成的二叉树有 种形态。种形态。 2. 一棵深度为一棵深度为6的满二叉树有的满二叉树有 个分支结点和个分支结点和 个叶子。个叶子。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么1 由个结点所构成的二叉树有由个结点所构成的二叉树有 5 种形态。种形态。 2. 【计算机研】【计算机研】 一棵深度为一棵深度为6的满二的满二叉树有叉树有 n1+n2=0+ n2= n0-1=31 个个分支结点和分支结点和 26-1

41、=32 个叶子。个叶子。注：满二叉树没有度为注：满二叉树没有度为1的结点，所以分的结点，所以分支结点数就是二度结点数。支结点数就是二度结点数。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么3.二叉树的基本组成部分是：根（二叉树的基本组成部分是：根（N）、左子）、左子树（树（L）和右子树（）和右子树（R）。因而二叉树的遍历）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即次序有六种。最常用的是三种：前序法（即按按N L R次序），后序法（即按次序），后序法（即按 次序）和中序法（也称对称序法，即按次序）和中序法（也称对称序法，即按

42、L N R次序）。这三种方法相互之间有关联。次序）。这三种方法相互之间有关联。 若已知一棵二叉树的前序序列是若已知一棵二叉树的前序序列是BEFCGDH，中序序列是，中序序列是FEBGCHD，则它的后序序列，则它的后序序列必是必是 。 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么3. 二叉树的基本组成部分是：根（二叉树的基本组成部分是：根（N）、左子树（）、左子树（L）和右子树（和右子树（R）。因而二叉树的遍历次序有六种。最常）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按用的是三种：前序法（即按N L R次序），后序法（即

43、次序），后序法（即按按 L R N 次序）和中序法（也称对称序法，即次序）和中序法（也称对称序法，即按按L N R次序）。这三种方法相互之间有关联。若已知次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是一棵二叉树的前序序列是BEFCGDH，中序序列是，中序序列是FEBGCHD，则它的后序序列必是，则它的后序序列必是 F E G H D C B 。 解：法解：法1：先由已知条件画图，再后序遍历得到结果；：先由已知条件画图，再后序遍历得到结果；法法2：不画图也能快速得出后序序列，只要找到根的位置特征。由前序先确定root，由中序先确定左子树。例如，前序遍历BEFCGDH中，根结点在最

44、前面，是中，根结点在最前面，是B；则；则后序遍历中后序遍历中B一定在最后面。一定在最后面。法法3：递归计算。如：递归计算。如B在前序序列中第一，中序中在中间在前序序列中第一，中序中在中间（可知左右子树上有哪些元素），则在后序中必为最后。（可知左右子树上有哪些元素），则在后序中必为最后。如法对如法对B的左右子树同样处理，则问题得解。的左右子树同样处理，则问题得解。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么4. 用用5个权值个权值3,

45、 2, 4, 5, 1构造的哈构造的哈夫曼（夫曼（Huffman）树的带权路径长度是）树的带权路径长度是 。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么4. 【计算机研】【计算机研】 用5个权值3, 2, 4, 5, 1构造的哈夫曼（Huffman）树的带权路径长度是 33 。解：先构造哈夫曼树，得到各叶子的路解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出径长度之后便可求出WPL（453）2（12）3=33在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么三、选择题三、选择题

46、( )1. 3个结点可构成个结点可构成 个不同个不同形态的二叉树。形态的二叉树。A.2 B.3 C.4 D.5在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么( D )1. 3个结点可构成个结点可构成 个不个不同形态的二叉树。同形态的二叉树。A.2 B.3 C.4 D.5在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）2二叉树是非线性数据结构，二叉树是非线性数据结构，所以所以 。（）它不能用顺序存储结构存储（）它不能用顺序存储结构存储; （）它不能用链式存储结构存储（）它不能用

47、链式存储结构存储; （）顺序存储结构和链式存储结构都能（）顺序存储结构和链式存储结构都能存储存储; （）顺序存储结构和链式存储结构都不（）顺序存储结构和链式存储结构都不能使用能使用 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ C ）2二叉树是非线性数据结构，所以二叉树是非线性数据结构，所以 。（）它不能用顺序存储结构存储（）它不能用顺序存储结构存储; （）它不能用链式存储结构存储（）它不能用链式存储结构存储; （）顺序存储结构和链式存储结构都能存储（）顺序存储结构和链式存储结构都能存储; （）顺序存储结构和链式存储结构都不能使（）

48、顺序存储结构和链式存储结构都不能使用用 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）3把一棵树转换为二叉树后，把一棵树转换为二叉树后，这棵二叉树的形态是这棵二叉树的形态是 。（）唯一的（）唯一的 （）有多种（）有多种（）有多种，但根结点都没有左孩子（）有多种，但根结点都没有左孩子 （）有多种，但根结点都没有右孩子（）有多种，但根结点都没有右孩子在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ A ）3把一棵树转换为二叉树后，把一棵树转换为二叉树后，这棵二叉树的形态是这棵二

49、叉树的形态是 。（）唯一的（）唯一的 （）有多种（）有多种（）有多种，但根结点都没有左孩子（）有多种，但根结点都没有左孩子 （）有多种，但根结点都没有右孩子（）有多种，但根结点都没有右孩子在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么( )4.将一棵有50个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为30的结点的右孩子编号为 。A.30 B.60 C.61 D.62 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么( C )4.将一

50、棵有50个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为30的结点的右孩子编号为 。A.30 B.60 C.61 D.62 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么( )5. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是 。A.M1 B.M1+M2 C.M3 D.M2+M3在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么( D )5. 设森林F中有三棵

51、树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是 。A.M1 B.M1+M2 C.M3 D.M2+M3在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么6. 二叉树二叉树 A 。在完全的二叉树中，若一个结点没有。在完全的二叉树中，若一个结点没有 B ，则它必定是叶结点。每棵树都能惟一地转换成与它，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点对应的二叉树。由树转换成的二叉树里，一个结点N的左的左子女是子女是N在原树里对应结点的在原树里对应结点

52、的 C ，而，而N的右子女是它的右子女是它在原树里对应结点的在原树里对应结点的 D 。供选择的答案供选择的答案A： 是特殊的树是特殊的树 不是树的特殊形式不是树的特殊形式 是两棵树是两棵树的总称的总称 有是只有二个根结点的树形结构有是只有二个根结点的树形结构 B: 左子结点左子结点 右子结点右子结点 左子结点或者没有左子结点或者没有右子结点右子结点 兄弟兄弟CD： 最左子结点最左子结点 最右子结点最右子结点 最最邻近的右兄弟邻近的右兄弟 最邻近的左兄弟最邻近的左兄弟 最左的兄弟最左的兄弟 最右的兄弟最右的兄弟答案：答案：A= B= C= D 在日常生活中，随处都可以看到浪费粮食的现象。也许你并

53、未意识到自己在浪费，也许你认为浪费这一点点算不了什么6. 二叉树二叉树 A 。在完全的二叉树中，若一个结点没有。在完全的二叉树中，若一个结点没有 B ，则它必定是叶结点。每棵树都能惟一地转换成与它对，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点应的二叉树。由树转换成的二叉树里，一个结点N的左的左子女是子女是N在原树里对应结点的在原树里对应结点的 C ，而，而N的右子女是它的右子女是它在原树里对应结点的在原树里对应结点的 D 。供选择的答案供选择的答案A： 是特殊的树是特殊的树 不是树的特殊形式不是树的特殊形式 是两棵树是两棵树的总称的总称 有是只有二

54、个根结点的树形结构有是只有二个根结点的树形结构 B: 左子结点左子结点 右子结点右子结点 左子结点或者没有左子结点或者没有右子结点右子结点 兄弟兄弟CD： 最左子结点最左子结点 最右子结点最右子结点 最邻近的右兄弟最邻近的右兄弟 最邻近的左兄弟最邻近的左兄弟 最左的兄弟最左的兄弟 最右的兄弟最右的兄弟答案：答案：A= B= C= D 答案：ABCDE2，1，1，3在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么四、简答题四、简答题1 一棵度为一棵度为2的树与一棵二叉树有何区别的树与一棵二叉树有何区别？在日常生活中，随处都可以看到浪费粮食的

55、现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么四、简答题四、简答题1 一棵度为一棵度为2的树与一棵二叉树有何区别的树与一棵二叉树有何区别？答：度为答：度为2的树从形式上看与二叉树很相的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之在二叉树中即使是一个孩子也有左右之分。分。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点

56、点算不了什么2 给定二叉树的两种遍历序列，分别是：给定二叉树的两种遍历序列，分别是：前序遍历序列：前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树试画出二叉树B 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么4. 试写出如图所示的二叉树分别按先序、试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。中序、后序遍历时得到的结点序列。在日常生活中

57、，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么4. 试写出如图所示的二叉树分别按先序、试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。中序、后序遍历时得到的结点序列。答：DLR：A B D F J G K C E H I L M LDR: B F J D G K A C H E L I M LRD：J F K G D B H L M I E C A在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么6.【严题集【严题集6.21】画出和下列二叉树】画出和下列二叉树相应的森林。相应的

58、森林。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么6 答：注意根右边的子树肯定是森林，而孩子结点的右子树均为兄弟。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么第七章在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么一、单选题一、单选题（ ）1. 在一个图中，所有顶点的度数之在一个图中，所有顶点的度数之和等于图的边数的和等于图的边数的 倍。倍。 A1/2 B. 1 C. 2 D. 4 （ ）2. 在一个有向图中，所有顶点的入

59、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的度之和等于所有顶点的出度之和的 倍。倍。 A1/2 B. 1 C. 2 D. 4 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ C ）1. 在一个图中，所有顶点的度数之在一个图中，所有顶点的度数之和等于图的边数的和等于图的边数的 倍。倍。 A1/2 B. 1 C. 2 D. 4 （ B ）2. 在一个有向图中，所有顶点的入在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的度之和等于所有顶点的出度之和的 倍。倍。 A1/2 B. 1 C. 2 D. 4 在日常生活中，随

60、处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）3. 有有8个结点的无向图最多有个结点的无向图最多有 条边。条边。 A14 B. 28 C. 56 D. 112 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ B ）3. 有有8个结点的无向图最多有个结点的无向图最多有 条边。条边。 A14 B. 28 C. 56 D. 112 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）4. 有有8个结点的有向完全图有个结点的有向完全图有

61、条边。条边。 A14 B. 28 C. 56 D. 112 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ C ）4. 有有8个结点的有向完全图个结点的有向完全图有有 条边。条边。 A14 B. 28 C. 56 D. 112 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么二、填空题二、填空题1. 图有图有 、 等存储结等存储结构，遍历图有构，遍历图有 、 等方法。等方法。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么1

62、. 图有图有 邻接矩阵邻接矩阵 、 邻接表邻接表 等存储等存储结构，遍历图有结构，遍历图有 深度优先遍历深度优先遍历 、 广广度优先遍历度优先遍历 等方法。等方法。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么三、简答题三、简答题1. 【严题集【严题集7.1】已知如图所示的有向图，】已知如图所示的有向图，请给出该图的请给出该图的:(1)每个顶点的入每个顶点的入/出度；出度；(2)邻接矩阵；邻接矩阵；(3)邻接表；邻接表；(4)逆邻接表。逆邻接表。 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一

63、点点算不了什么在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么4.已知一个图的顶点为A、B、C、D，其邻接矩阵的上三角元素（包括

64、主对角线元素）全为0，其他元素均为1(如下表所示)。请问：（1）该图是有向图还是无向图? （2）请画出该图形。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么 该图是一个有向图 图形如下: 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么5已知某网的邻接（出度）表，请画出该网络。节点的结构表示如下:在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪

65、费这一点点算不了什么第八章在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么一、填空题一、填空题1. 在数据的存放无规律而言的线性表中在数据的存放无规律而言的线性表中进行检索的最佳方法是进行检索的最佳方法是 。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么一、填空题一、填空题1. 在数据的存放无规律而言的线性表中在数据的存放无规律而言的线性表中进行检索的最佳方法是进行检索的最佳方法是 顺序查找（线顺序查找（线性查找）性查找） 。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意

66、识到自己在浪费，也许你认为浪费这一点点算不了什么3. 假设在有序线性表假设在有序线性表a20上进行折半上进行折半查找，则比较一次查找成功的结点数为查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较两次查找成功的结点数为 ；比较四次查找成功的结点数为；比较四次查找成功的结点数为 。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么3. 假设在有序线性表假设在有序线性表a20上进行折半查上进行折半查找，则比较一次查找成功的结点数为找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为比较两次查找成功的结点数为 2 ；

67、比；比较四次查找成功的结点数为较四次查找成功的结点数为 8 。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么5. 在各种查找方法中，平均查找长度与在各种查找方法中，平均查找长度与结点个数结点个数n无关的查找方法是无关的查找方法是 。6. 哈希法存储的基本思想是由哈希法存储的基本思想是由 决定数据的存储地址。决定数据的存储地址。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么5. 在各种查找方法中，平均查找长度与在各种查找方法中，平均查找长度与结点个数结点个数n无关的查找方法是无关的

68、查找方法是 哈希查找哈希查找 。6. 哈希法存储的基本思想是由哈希法存储的基本思想是由 关键字关键字的值的值 决定数据的存储地址。决定数据的存储地址。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）2 折半查找有序表（折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找）。若查找表中元素表中元素58，则它将依次与表中，则它将依次与表中 比比较大小，查找结果是失败。较大小，查找结果是失败。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50在日常生活中，随处都可以看到浪费粮

69、食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ A ）2折半查找有序表（折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素）。若查找表中元素58，则它将依，则它将依次与表中次与表中 比较大小，查找结果比较大小，查找结果是失败。是失败。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）4. 链表适用于链表适用于 查找查找A顺序顺序 B二分法二分法 C顺序，也能二分法顺序，也能二分法 D随机

70、随机在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ A ）4. 链表适用于链表适用于 查找查找A顺序顺序 B二分法二分法 C顺序，也能二分法顺序，也能二分法 D随机随机在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么6 要进行线性查找，则线性表要进行线性查找，则线性表 A ；要进行；要进行二分查找，则线性表二分查找，则线性表 B ；要进行散列查找，；要进行散列查找，则线性表则线性表 C 。供选择的答案：供选择的答案：AC： 必须以顺序方式存储必须以顺序方式存储 必须以链必须以链表

71、方式存储表方式存储 必须以散列方式存储必须以散列方式存储 既可以以顺序方式，也可以以链表方式存储既可以以顺序方式，也可以以链表方式存储 必须以顺序方式存储且数据元素已按值递增必须以顺序方式存储且数据元素已按值递增或递减的次序排好或递减的次序排好 必须以链表方式存储且数据元素已按值递增必须以链表方式存储且数据元素已按值递增或递减的次序排好或递减的次序排好 答案：答案： A= B= C= 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么6要进行线性查找，则线性表要进行线性查找，则线性表 A ；要进；要进行二分查找，则线性表行二分查找，则线性表

72、 B ；要进行散列查找，；要进行散列查找，则线性表则线性表 C 。供选择的答案：供选择的答案：AC： 必须以顺序方式存储必须以顺序方式存储 必须以链表方式存储必须以链表方式存储 必须以散列方式存储必须以散列方式存储 既可以以顺序方式，也可以以链表方式存储既可以以顺序方式，也可以以链表方式存储 必须以顺序方式存储且数据元素已按值递增或必须以顺序方式存储且数据元素已按值递增或递减的次序排好递减的次序排好 必须以链表方式存储且数据元素已按值递增或必须以链表方式存储且数据元素已按值递增或递减的次序排好递减的次序排好答案：答案： A= B= C= 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意

73、识到自己在浪费，也许你认为浪费这一点点算不了什么7. 数据结构反映了数据元素之间的结构关系。链表数据结构反映了数据元素之间的结构关系。链表是一种是一种 A ，它对于数据元素的插入和删除，它对于数据元素的插入和删除 B 。通常查。通常查找线性表数据元素的方法有找线性表数据元素的方法有 C 和和 D 两种方法，其中两种方法，其中 C 是一种只适合于顺序存储结构但是一种只适合于顺序存储结构但 E 的方法；而的方法；而 D 是一种对顺序和链式存储结构均适用的方法。是一种对顺序和链式存储结构均适用的方法。 A：顺序存储线性表顺序存储线性表 非顺序存储非线性表非顺序存储非线性表 顺序存储非线性表顺序存储非

74、线性表 非顺序存储线性表非顺序存储线性表B： 不需要移动结点，不需改变结点指针不需要移动结点，不需改变结点指针 不需要移动结点，只需改变结点指针不需要移动结点，只需改变结点指针 只需移动结点，不需改变结点指针只需移动结点，不需改变结点指针 既需移动结点，又需改变结点指针既需移动结点，又需改变结点指针C： 顺序查找顺序查找 循环查找循环查找 条件查找条件查找 二分法查找二分法查找D： 顺序查找顺序查找 随机查找随机查找 二分法查找二分法查找分块查找分块查找E： 效率较低的线性查找效率较低的线性查找 效率较低的非线性查找效率较低的非线性查找 效率较高的非线性查找效率较高的非线性查找 效率较高的线性

75、查找效率较高的线性查找答案：答案：A B C D E 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么7. 数据结构反映了数据元素之间的结构关系。链表数据结构反映了数据元素之间的结构关系。链表是一种是一种 A ，它对于数据元素的插入和删除，它对于数据元素的插入和删除 B 。通常查。通常查找线性表数据元素的方法有找线性表数据元素的方法有 C 和和 D 两种方法，其中两种方法，其中 C 是一种只适合于顺序存储结构但是一种只适合于顺序存储结构但 E 的方法；而的方法；而 D 是一种对顺序和链式存储结构均适用的方法。是一种对顺序和链式存储结构均适

76、用的方法。 A：顺序存储线性表顺序存储线性表 非顺序存储非线性表非顺序存储非线性表 顺序存储非线性表顺序存储非线性表 非顺序存储线性表非顺序存储线性表B： 不需要移动结点，不需改变结点指针不需要移动结点，不需改变结点指针 不需要移动结点，只需改变结点指针不需要移动结点，只需改变结点指针 只需移动结点，不需改变结点指针只需移动结点，不需改变结点指针 既需移动结点，又需改变结点指针既需移动结点，又需改变结点指针C： 顺序查找顺序查找 循环查找循环查找 条件查找条件查找 二分法查找二分法查找D： 顺序查找顺序查找 随机查找随机查找 二分法查找二分法查找分块查找分块查找E： 效率较低的线性查找效率较低

77、的线性查找 效率较低的非线性查找效率较低的非线性查找 效率较高的非线性查找效率较高的非线性查找 效率较高的线性查找效率较高的线性查找答案：答案： A B C D E 在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么三、简答题三、简答题1. 对分（折半）查找适不适合链表结构对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法度必然比线性查找的速度快，这种说法对吗？对吗？在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点

78、点算不了什么1 对分（折半）查找适不适合链表结构的序列，对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？找的速度快，这种说法对吗？答：不适合！虽然有序的单链表的结点是按从答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。逐步搜索，故不能进行折半查找。二分查找的速度在一般情况下是快些，但在特二分查找的速度在一般情况下是快些

79、，但在特殊情况下未必快。例如所查数据位于首位时，殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。则线性查找快；而二分查找则慢得多。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么4.使用折半查找的两个前提条件是什么？（1）采用顺序存储结构；（2）按关键字大小有序排列。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么4.使用折半查找的两个前提条件是什么？在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么4.

80、 设哈希（设哈希（Hash）表的地址范围为）表的地址范围为017，哈希函，哈希函数为：数为：H（K）K MOD 16。K为关键字，用线性探测法再散列法处理冲突，输入关为关键字，用线性探测法再散列法处理冲突，输入关键字序列：键字序列：（10，24，32，17，31，30，46，47，40，63，49）造出造出Hash表，试回答下列问题：表，试回答下列问题：画出哈希表的示意图；画出哈希表的示意图；若查找关键字若查找关键字63，需要依次与哪些关键字进行比较？，需要依次与哪些关键字进行比较？若查找关键字若查找关键字60，需要依次与哪些关键字比较？，需要依次与哪些关键字比较？假定每个关键字的查找概率相等

81、，求查找成功时的平均假定每个关键字的查找概率相等，求查找成功时的平均查找长度。查找长度。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么解：解： （1）画表如下：）画表如下：在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（2） 查找查找63,首先要与首先要与H(63)=63%16=15号单号单元内容比较，即元内容比较，即63 vs 31 ,no;然后顺移，与然后顺移，与46,47,32,17,63相比，一共比较相比，一共比较了了6次！次！（3）查找60,首先要与H(60)=60%1

82、6=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。（4） 对于黑色数据元素，各比较1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（6233）17/11=1.54545454541.55在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么4. 选取散列函数选取散列函数H（key）=（3*key）%11，用线性探测，用线性探测法处理冲突，对下列关键码序列构造一法处理冲突，对下列关键码序列构造一

83、个散列地址空间为个散列地址空间为010，表长为，表长为11的的散列表，散列表，22，41，53，08，46，30，01，31，66。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么解：由题意知，解：由题意知，m=11(刚好为素数刚好为素数)则则(22*3)%11=60 (41*3)%11=112(53*3)%11=145(08*3)%11=22(46*3)%11=126(30*3)%11=82(01*3)%11=03(31*3)%11=85(66*3)%11=90在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许

84、你认为浪费这一点点算不了什么第9章在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么一、填空题一、填空题1. 大多数排序算法都有两个基本的操作：大多数排序算法都有两个基本的操作： 和和 。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么1. 大多数排序算法都有两个基本的操作：大多数排序算法都有两个基本的操作： 比较比较 和和 移动移动 。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么4. 设要将序列（设要将序列（Q, H, C,

85、 Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重）中的关键码按字母序的升序重新排列，则：新排列，则：初始步长为初始步长为4的希尔（的希尔（shell）排序一趟的结）排序一趟的结果是果是 ；二路归并排序一趟扫描的结果是二路归并排序一趟扫描的结果是 ；堆排序初始建堆的结果是堆排序初始建堆的结果是 。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么4. 设要将序列（设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重）中的关键码按字母序的升序重新排列，则：新

86、排列，则：初始步长为初始步长为4的希尔（的希尔（shell）排序一趟的结果）排序一趟的结果是是 P A C S Q H F X R D M Y ；二路归并排序一趟扫描的结果是二路归并排序一趟扫描的结果是 H Q C Y A P M S D R F X；堆排序初始建堆的结果是堆排序初始建堆的结果是 A D C R F Q M S Y P H X 。在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）1 排序方法中，从未排序序排序方法中，从未排序序列中依次取出元素与已排序序列（初始列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，

87、将其放入时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为已排序序列的正确位置上的方法，称为. 希尔排序希尔排序 . 冒泡排序冒泡排序 . 插入排序插入排序 . 选择排序选择排序在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ C ）1 排序方法中，从未排序序排序方法中，从未排序序列中依次取出元素与已排序序列（初始列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为已排序序列的正确位置上的方法，称为. 希尔排序希尔排序 . 冒泡排序冒泡

88、排序 . 插入排序插入排序 . 选择排序选择排序在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）2快速排序在下列哪种情况下最易发快速排序在下列哪种情况下最易发挥其长处。挥其长处。. 被排序的数据中含有多个相同排序码被排序的数据中含有多个相同排序码 . 被排序的数据已基本有序被排序的数据已基本有序. 被排序的数据完全无序被排序的数据完全无序 . 被排序的数据中的最大值和最小值相差悬被排序的数据中的最大值和最小值相差悬殊殊在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ C ）2

89、快速排序在下列哪种情况下最易发快速排序在下列哪种情况下最易发挥其长处。挥其长处。. 被排序的数据中含有多个相同排序码被排序的数据中含有多个相同排序码 . 被排序的数据已基本有序被排序的数据已基本有序. 被排序的数据完全无序被排序的数据完全无序 . 被排序的数据中的最大值和最小值相差悬被排序的数据中的最大值和最小值相差悬殊殊在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么( )8排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？ A. 堆排序 B.直接插入排序 C.快速排序 D.冒泡排序在

90、日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么( D )8排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？ A. 堆排序 B.直接插入排序 C.快速排序 D.冒泡排序在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）5下列关键字序列中，下列关键字序列中， 是是堆。堆。. 16, 72, 31, 23, 94, 53 . 94, 23, 31, 72, 16, 53 . 16, 53, 23, 94，31, 72 . 16, 2

91、3, 53, 31, 94, 72在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ D ）5下列关键字序列中，下列关键字序列中， 是堆。是堆。. 16, 72, 31, 23, 94, 53 . 94, 23, 31, 72, 16, 53 . 16, 53, 23, 94，31, 72 . 16, 23, 53, 31, 94, 72在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ ）6堆的形状是一棵堆的形状是一棵 . 二叉排序树二叉排序树 .满二叉树满二叉树 . 完全二叉树完

92、全二叉树 . 平衡二叉树平衡二叉树在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么（ C ）6堆的形状是一棵堆的形状是一棵 . 二叉排序树二叉排序树 .满二叉树满二叉树 . 完全二叉树完全二叉树 . 平衡二叉树平衡二叉树在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么1设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？在日常生活中，随处都可以看到浪费粮食的现象。也许你并未意识到自己在浪费，也许你认为浪费这一点点算不了什么堆排序。因为一趟堆排序排定一个元素，只需进行前5趟堆排序就可以了。其它排序方法均需进行完全排序。