《清华大学出社数据结构C第2课后习题含2.doc》由会员分享，可在线阅读，更多相关《清华大学出社数据结构C第2课后习题含2.doc（121页珍藏版）》请在金锄头文库上搜索。
1、清华大学第一版社数据结构C版第2版课后习题含答案最全整理精编版 最新资料介绍 第 1 章绪论课后习题解说1. 填空（ ）是数据的基本单位，在计算机程序中往常作为一个整体进行考虑和办理。【解答】数据元素（ ）是数据的最小单位，（ ）是议论数据结构时波及的最小数据单位。【解答】数据项，数据元素【剖析】数据结构指的是数据元素以及数据元素之间的关系。 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。【解答】会合，线性结构，树结构，图结构 数据的储存结构主要有 （ ）和（ ）两种基本方法， 不论哪一种储存结构，都要储存双方面的内容：（ ）和（ ）。【解答】次序储存结构，链接储存结构，数据
2、元素，数据元素之间的关系 算法拥有五个特征，分别是（ ）、（ ）、（ ）、（ ）、（ ）。【解答】有零个或多个输入，有一个或多个输出，有穷性，确立性，可行性1 / 最新资料介绍 算法的描绘方法往常有（ ）、（ ）、（ ）和（ ）四种，此中，（ ）被称为算法语言。【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 在一般状况下，一个算法的时间复杂度是（ ）的函数。【解答】问题规模设待办理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数目级的形式为（ ），若为n*log25n ，则表示成数目级的形式为（ ）。【解答】 (1)，(nlog2n)【剖析】用大 O记号表示算法的时间复杂度
3、，需要将低次幂去掉，将最高次幂的系数去掉。2.选择题次序储存结构中数据元素之间的逻辑关系是由 （ ）表示的，链接储存结构中的数据元素之间的逻辑关系是由（ ）表示的。A线性结构 B 非线性结构 C 储存地点 D 指针【解答】 C，D【剖析】次序储存结构就是用一维数组储存数据结构中的数据元素， 其逻辑关系由储存地点 （即元素在数组中的下标） 表示；链接储存结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 假定有以下遗产继承规则：丈夫和老婆能够互相继承遗产；儿女能够继承父亲或母亲的遗产； 儿女间不可以互相继承。则表示该遗产继承关系的最适合的2 最新资料介绍 数据结构应当
4、是（ ）。A树B图C线性表 D 会合【解答】 B【剖析】将丈夫、老婆和儿女分别作为数据元素，依据题意画出逻辑结构图。 算法指的是（ ）。A对特定问题求解步骤的一种描绘，是指令的有限序列。B计算机程序 C 解决问题的计算方法 D 数据办理【解答】 A【剖析】计算机程序是对算法的详细实现；简单地说，算法是解决问题的方法；数据办理是经过算法达成的。所以，只有 A 是算法的正确立义。 下边（ ）不是算法所一定具备的特征。A 有穷性 B 切实性 C 高效性 D 可行性【解答】 C【剖析】高效性是好算法应具备的特征。 算法剖析的目的是（ ），算法剖析的两个主要方面是（ ）。A 找出数据结构的合理性 B 研
5、究算法中输入和输出的关系C 剖析算法的效率以求改良D 剖析算法的易读性和文档性E 空间性能和时间性能 F 正确性和简洁性3 最新资料介绍 G 可读性和文档性 H 数据复杂性和程序复杂性【解答】 C，E3. 判断题 算法的时间复杂度都要经过算法中的基本语句的履行次数来确立。【解答】错。时间复杂度要经过算法中基本语句履行次数的数目级来确立。 每种数据结构都具备三个基本操作：插入、删除和查找。【解答】错。如数组就没有插入和删除操作。本题注意是每种数据结构。 所谓数据的逻辑结构指的是数据之间的逻辑关系。【解答】错。是数据之间的逻辑关系的整体。逻辑结构与数据元素自己的内容和形式没关。【解答】对。所以逻辑
6、结构是数据组织的主要方面。 鉴于某种逻辑结构之上的基本操作，其实现是独一的。【解答】错。基本操作的实现是鉴于某种储存结构设计的，因此不是独一的。4. 剖析以下各程序段，并用大 O记号表示其履行时间。【解答】 基本语句是 k=k+10*i ，共履行了 n-2 次，所以 T(n)=O(n) 。 基本语句是 k=k+10*i ，共履行了 n 次，所以 T(n)=O(n) 。4 最新资料介绍 剖析条件语句， 每循环一次， i+j 整体加 1，共循环n 次，所以 T(n)=O(n) 。设循环体共履行 T(n) 次，每循环一次，循环变量 y 加 1，最后T(n)=y ，即：(T(n)+1)2 n，所以 T
7、(n)=O(n1/2) 。 x+ 是基本语句，所以5设有数据结构（ D，R），此中 D=1, 2, 3, 4, 5, 6 ，R=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6) 。试画出其逻辑结构图并指出属于何种结构。【解答】其逻辑结构图如图1-3 所示，它是一种图结构。6.为整数定义一个抽象数据种类，包含整数的常有运算，每个运算对应一个基本操作，每个基本操作的接口需定义前置条件、输入、功能、输出和后置条件。【解答】整数的抽象数据种类定义以下：ADT integerData整数 a：能够是正整数 (1, 2, 3, )、负整数 (-1, -2, -
8、3, )和零OperationConstructor前置条件：整数 a 不存在输入：一个整数 b功能：结构一个与输入值相同的整数输出：无5 最新资料介绍 后置条件：整数 a 拥有输入的值Set前置条件：存在一个整数 a输入：一个整数 b功能：改正整数 a 的值，使之与输入的整数值相同输出：无后置条件：整数 a 的值发生改变Add前置条件：存在一个整数 a输入：一个整数 b功能：将整数 a 与输入的整数 b 相加输出：相加后的结果后置条件：整数 a 的值发生改变Sub前置条件：存在一个整数 a输入：一个整数 b功能：将整数 a 与输入的整数 b 相减输出：相减的结果后置条件：整数 a 的值发生改
9、变Multi前置条件：存在一个整数 a输入：一个整数 b6 最新资料介绍 功能：将整数 a 与输入的整数 b 相乘输出：相乘的结果后置条件：整数 a 的值发生改变Div前置条件：存在一个整数 a输入：一个整数 b功能：将整数 a 与输入的整数 b 相除输出：若整数 b为零，则抛出除零异样，不然输出相除的结果后置条件：整数 a 的值发生改变Mod前置条件：存在一个整数 a输入：一个整数 b功能：求目前整数与输入整数的模，即正的余数输出：若整数 b为零，则抛出除零异样，不然输出取模的结果后置条件：整数 a 的值发生改变Equal前置条件：存在一个整数 a输入：一个整数 b功能：判断整数 a 与输入
10、的整数 b 能否相等输出：若相等返回 1，不然返回 0后置条件：整数 a 的值不发生改变endADT7 最新资料介绍 7. 求多项式 A(x) 的算法可依据以下两个公式之一来设计： A(x)=anxn+an-1xn-1+ +a1x+a0 A(x)=( (anx+an-1)x+ +a1)x)+a0依据算法的时间复杂度剖析比较这两种算法的好坏。【解答】 第二种算法的时间性能要好些。 第一种算法需履行大批的乘法运算， 而第二种算法进行了优化，减少了不用要的乘法运算。8. 算法设计（要求：算法用伪代码和 C+ 描绘，并剖析最坏状况下的时间复杂度）对一个整型数组An设计一个排序算法。【解答】下边是简单项
11、选择择排序算法的伪代码描绘。下边是简单项选择择排序算法的 C+ 描绘。剖析算法，有两层嵌套的 for 循环，所以， 。 找出整型数组An 中元素的最大值和次最大值。【解答】算法的伪代码描绘以下：算法的 C+ 描绘以下：8 最新资料介绍 剖析算法，只有一层循环，共履行 n-2 次，所以， T(n)=O(n) 。学习自测及答案1次序储存结构的特色是（ ），链接储存结构的特色是（ ）。【解答】用元素在储存器中的相对地点来表示数据元素之间的逻辑关系， 用指示元素储存地点的指针表示数据元素之间的逻辑关系。2. 算法在发生非法操作时能够作出办理的特征称为（ ）。【解答】强健性3. 常有的算法时间复杂度用大
12、记号表示为：常数阶( )、对数阶( )、线性阶( )、平方阶( )和指数阶( ) 。【解答】 (1)， (log2n) ，(n) ， (n2)， (2n)4将以下函数按它们在 n时的无量大阶数，从小到大摆列。n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!, n2+log2n【解答】 log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2,(3/2)n, n!5试描绘数据结构和抽象数据种类的观点与程序设计语言中数据种类观点的差别。【解答】数据结构是指互相之间存在必定关系的数据元素的会合。 而抽象数据类型是指一个数据结构以及定义在该结构上的一组操作。 程序设计语言中的数据类9 最新资料介绍 型是一个值的会合和定义在这个值集上一组操作的总称。 抽象数据种类能够当作是对数据种类的一种抽象。6.对以下用二元组表示的数据结构 ,试分别画出对应的逻辑结构图，
