清华大学环境学院2015年秋实验室安全考核研究生题库答案.docx

1、数据结构（ C语言版）（第 2版）课后习题答案李冬梅 2015.3目 录第 1章 绪论 . 1第 2章 线性表 . 5第 3章 栈和队列 . 13第 4章 串、数组和广义表 . 26第 5章 树和二叉树 . 33第 6章 图 . 43第 7章 查找 . 54第 8章 排序 . 65II第 1章 绪论1简述下列概念： 数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形 、图像、声音、动画等通过特殊编码定义后的

2、数据。数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、 等。数据元素用 整 述一个对象，如一个学 ，树中 的一个 、图中的一个 点等。数据项：是组 数据元素的、有 义的、 的 单位。 如，学 基本表中的学号、 、性 等 是数据项。数据对象：是性的数据元素的，是数据的一个。 如：整数数据对象是currency1“， 1 ， ， fi，字fl字符数据对象是 currency1， ， ， ，fi，学 基本 表也 是一个数据对象。数据结构：是”存在一多特定 的数据元素的。 ，数据结构是结构的数据元素的，结构是指数据元素”存在的 。逻辑结构：

3、逻辑 述数据，数据的存储 ，是 计算机的。，数据的逻辑结构 作是 体 抽象 的数学 型。存储结构：数据对象在计算机中的存储表示，也称为物理结构。抽象数据类型： 用 定义的，表示 用 的数学 型， 定义在 个 型 的一组 作的总称。 体 ：数据对象、数据对象 的和对数据对象的基本作的。 一个数据结构的 ，述 逻辑结构和存储结构 的 义和 。答案：如有一学 基本 表， 学 的学号、 、性 、 等。 个学 基本 对 一个数据元素，学 序号排列，形 学 基本 的线性序列。对 整个表 ，有一个 结点 的 和一个 结点 的后 ， 的结点有一个也有一个 和 后 。学 ”的 确定 学 表的逻辑结构，即线性结构

4、。些学 在计算机中的存储表示是存储结构。如果用连续的存储单元 如用数组表示 存放 些 ，称为 序存储结构；如果存储单元 连续，而是随机存放个 ，然后用指针进行链 ，称为链式存储结构。即的逻辑结构， 对 的存储结构。3简述逻辑结构的四基本 并画 们的 图。1答案：1 结构数据元素”除 属 一的 外， 。 如，确定一 学 是否为班级 员，需将班级做一个结构。 线性结构数据元素”存在一对一的 。 如，将学 数据 照 入学报到的时先后 序进行排列，将组 一个线性结构。3 树结构数据元素”存在一对多的 。 如，在班级的管理体中，班长管理多个组长， 位组长管理多 组员，而构 树形结构。4 图结构网 结构数

5、据元素”存在多对多的 。 如，多位学”的朋友 ，任何 位学 是朋友，而构 图形结构网 结构。中树结构和图结构 属 非线性结构。4存储结构 哪 基本的存储 法实现？答案：1 序存储结构序存储结构是借助元素在存储器中的对位置 表示数据元素”的逻辑 ，通常借助程序设计语言的数组类型 述。 链式存储结构序存储结构要求所有的元素依次存放在一片连续的存储空中，而链式存储结构， 需占用一整块存储空。但为 表示结点”的 ，需要给 个结点附加指针字段，用 存放后 元素的存储 址。所链式存储结构通常借助 程序设计语言的指针类型 述。5选择 1 在数据结构中，逻辑 把数据结构 。动 结构和静 结构 紧凑结构和非紧凑

6、结构四类基本逻辑结构 图2线性结构和非线性结构 D内 结构和外 结构答案： 数据元素本身的形式、内容、对位置、个数 的是数据的 。存储结构 存储实现逻辑结构 D运算实现答案： 3 通常要求一逻辑结构中的所有数据元素 有的特性， 意味着 。数据 有一特点 仅数据元素所 的数据项的个数要，而且对 数据项的类型要一致 个数据元素 一样D数据元素所 的数据项的个数要等答案：4 下法正确的是 。数据元素是数据的 单位数据项是数据的基本单位数据结构是有结构的数据项的D一些表 很 的数据 有的逻辑结构答案：D解释：数据元素是数据的基本单位，数据项是数据的 单位，数据结构是有结构的数据元素的。5 算法的时复杂

7、度取决 。 的规 待处理数据的初 计算机的配置 D和答案：D解释：算法的时复杂度 仅 的规 有 ，还 的 素有 。如某些排序的算法， 执行时待排序 的初 有 。为，有时会对算法有 好、 坏 平均时复杂度的评价。6 下数据结构中， 是非线性数据结构树 字符串 队列 D栈答案：6 析下 程序段的时复杂度。1 xcurrency19“; ycurrency11“; while y“ if x1“ xcurrency1x-1“;y-;fielse x+;答案：O 1 解释：程序的执行次数为常数阶。3 for icurrency1“; i1ycurrency1“;while x y+1 y+1 y+;答

8、案：O n 解释：语y+;的执行次数为 n 。4第 2章 线性表1选择 1 序表中第一个元素的存储 址是 100 ， 个元素的长度为 2 ，第5 个元素的 址是 。A110 B 108 C 100 D 120答案： B解释： 序表中的数据连续存储，所第 5 个元素的 址为：100+2*4=108。2 在n个结点的 序表中，算法的时复杂度是O(1)的 作是 。A 第 i 个结点 1in 和求第 i 个结点的 2in B在第 i 个结点后 入一个 结点 1in C 除第 i 个结点 1in D将n个结点 到 排序答案： A解释：在 序表中 入一个结点的时复杂度 是 O(n2) ，排序的时复杂度为O

9、(n2) O(nlog2n)。 序表是一随机存取结构， 第 i 个结点和求第 i 个结点的 通过数组的下 定位，时复杂度是O(1)。3 一个有 127个元素的 序表中 入一个 元素并 序 ，平均要动 的元素个数为 。A8 B 63.5 C 63 D7答案： B解释：平均要 动的元素个数为： n/2 。4 链 存储的存储结构所占存储空 。A ，一 存放结点 ， 一 存放表示结点 的指针B有一 ，存放结点 C有一 ，存储表示结点 的指针D ，一 存放结点 ， 一 存放结点所占单元数答案： A5 线性表 用链式存储结构时，要求内存中 用存储单元的 址 。A 是连续的 B 址 是连续的C一定是 连续的

10、 D连续 连续 答案： D6 线性表 在 情况下 用 用链式结构实现。A需常 中的结点 需 对 进行 除 入 C 中 有 的结点 中结点结构复杂5答案： B解释：链表 的currency1点在 入和 除时 需要 动数据， 指针即 。7 单链表的存储度 。A 1 B等 1 C 1 D 能确定答案： C解释：存储度是指一个结点数据本身所占的存储空和整个结点所占的存储空”“，设单链表一个结点本身所占的空为 D，指针所占的空为 N，存储度为： D/(D+N)，一定 1。8 将 个有n个元素的有序表并 一个有序表， fi的“fl次数是 。An B 2n-1 C 2n D n-1答案： A解释： 第一个有

11、序表中所有的元素 第二个表中的元素，需要用第二个表中的第一个元素依次第一个表的元素“fl，总计“fl n次。9 在一个长度为 n的 序表中，在第 i 个元素 1in+1 ” 入一个 元素时后 动 个元素。A n-i B n-i+1 C n-i-1 D I答案： B(10) 线性表 L=(a1 ，a2,an)，下列法正确的是 。A 个元素 有一个 和一个 后 B线性表中fi有一个元素C表中元素的排列 是 到 到 D除第一个和 后一个元素外， 个元素 有一个且仅有一个 和 后 。答案： D(11) 一个 n个结点的有序单链表的时复杂度是 。AO(1) B O(n) C O(n2) D O(nlog

12、2n)答案： C解释：单链表 的时复杂度是 O(n)，而要 一个有序的单链表， 一个 结点时需要和有的结点进行“fl，确定 的 入位置，所时复杂度是O(n2)。(12) 下法的是 。A求表长、定位 运算在 用 序存储结构时实现的” “ 用链式存储结构时实现的”B 序存储的线性表 随机存取C 序存储要求连续的存储，所在存储管理 D线性表的链式存储结构currency1 序存储结构答案： D解释：链式存储结构和 序存储结构有currency1 点，有 的 用。6(13) 在单链表中，要将 s所指结点 入到p所指结点”后， 语 为 。A s-next=p+1; p-next=s;B (*p).nex

13、t=s; (*s).next=(*p).next;C s-next=p-next; p-next=s-next;D s-next=p-next; p-next=s; 答案： D(14) 在 链表存储结构中， 除p所指的结点时 指针 。Ap-next-prior=p-prior; p-prior-next=p-next;Bp-next=p-next-next; p-next-prior=p;Cp-prior-next=p; p-prior=p-prior-prior;Dp-prior=p-next-next; p-next=p-prior-prior;答案： A(15) 在 链表中，在 p指针所

14、指的结点后 入 q所指 的 结点， 指针的作是 。A p-next=q; q-prior=p; p-next-prior=q; q-next=q;Bp-next=q; p-next-prior=q; q-prior=p; q-next=p-next;Cq-prior=p; q-next=p-next; p-next-prior=q; p-next=q;Dq-prior=p; q-next=p-next; p-next=q; p-next-prior=q;答案： C算法设计 1 将 个的有序链表并为一个的有序链表。要求结果链表 用 个链表的存储空 外占用 的存储空。表中 有复的数据。析 并后的

15、表 用指针 指 ，和 是链表和的 作指针 初 为 链表的第一个结点，第一个结点 进行“fl， 个链表 和均为到 表 结点时，依次 取 中fl 链 在 表的 后。如果 个表中的元素等， 取 表中的元素， 除表中的元素， 样确 并后表中 复的元素。 一个表到 表 结点，为空时，将非空表的 元素 链 在表的 后。算法 述 oi er eis i is i is i is 并链表和，并后的 表 用指针指 currency1- ex ; currency1- ex ; 和 是链表和的 作指针初 为 链表的第一个结点currency1currency1; 用的结点作为的结点while if - - ex

16、currency1;currency1;currency1- ex ;fi取fl 中的元素，将链 在的后 ，指针后 else if - - - ex currency1; currency1; currency1- ex ;fi7取fl 中的元素，将链 在的后 ，指针后 else 等时取中的元素， 除中的元素- ex currency1;currency1;currency1- ex ;currency1- ex ; ele e ; currency1 ;fifi- ex currency1 ; 入 段ele e ; 释放的结点fi 2 将 个非的有序链表并为一个非的有序链表。要求结果链表 用

17、 个链表的存储空 外占用 的存储空。表中 有复的数据。析 并后的 表 用指针 指 ，和 是链表和的 作指针 初 为 链表的第一个结点，第一个结点 进行“fl， 个链表 和均为到 表 结点时，依次 取 中fl 链 在 表的表结点”后，如果 个表中的元素等， 取 表中的元素， 表中的元素。 一个表到 表 结点，为空时，将非空表的 元素依次 取，链 在表的表结点”后。算法 述 oi er eis i is i is i is 并链表和，并后的 表 用指针指 currency1- ex ; currency1- ex ; 和 是链表和的 作指针初 为 链表的第一个结点currency1currency

18、1; 用的结点作为的结点 - ex currency1;while 要存在一个非空表，用 指 待 取的元素if currency1; currency1- ex ;fi表为空，用 指 ，指针后 else if currency1; currency1- ex ;fi 表为空，用 指 ，指针后 else if - currency1; currency1- ex ;fi取fl 等 中的元素，用 指 ，指针后 else currency1; currency1- ex ;fi取fl 中的元素，用 指 ，指针后 - ex currency1 - ex ; - ex currency1 ; 将 指 的结点 在 表的表结点”后fiele e ; 释放的结点8