数据结构课后部分习题答案.doc

《数据结构课后部分习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章绪论1.填空⑴数据元素⑵数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。⑶集合，线性结构，树结构，图结构⑷顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹自然语言，程序设计语言，流程图，伪代码，伪代码⑺问题规模⑻Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。2.选择题⑴C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个

2、结点，元素之间的逻辑关系由结点中的指针表示。⑵B【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。（6）A【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。（7）C【分析】高效性是好算法应具备的特性。（8）C，E3.判断题⑴错。时间复杂度要通过算法中基本语句执行次数的数量级来确定。⑵错。如数组就没有插入和删除操作。此题注意是每种数据结构。⑶错。是数据之间的逻辑关系的整体。⑷对。因此逻辑结构是数据组织的主要方面。⑸错。基本操作的实现是基于某种存储结构设计的，因而不是唯一的。4.⑴基本语句是k

3、=k+10*i，共执行了n-2次，所以T(n)=O(n)。⑵基本语句是k=k+10*i，共执行了n次，所以T(n)=O(n)。⑶分析条件语句，每循环一次，i+j整体加1，共循环n次，所以T(n)=O(n)。⑷设循环体共执行T(n)次，每循环一次，循环变量y加1，最终T(n)=y，即：(T(n)+1)2≤n，所以T(n)=O(n1/2)。⑸x++是基本语句，所以5．（1）其逻辑结构图如图1-3所示，它是一种图结构。（2）整数的抽象数据类型定义如下：ADTintegerData整数a：可以是正整数(1,2,3,…)、负整数(-1,-2,-3,…)和零OperationConstruct

4、or前置条件：整数a不存在输入：一个整数b功能：构造一个与输入值相同的整数输出：无后置条件：整数a具有输入的值Set前置条件：存在一个整数a输入：一个整数b功能：修改整数a的值，使之与输入的整数值相同输出：无后置条件：整数a的值发生改变Add前置条件：存在一个整数a输入：一个整数b功能：将整数a与输入的整数b相加输出：相加后的结果后置条件：整数a的值发生改变Sub前置条件：存在一个整数a输入：一个整数b功能：将整数a与输入的整数b相减输出：相减的结果后置条件：整数a的值发生改变Multi前置条件：存在一个整数a输入：一个整数b功能：将整数a与输入的整数b相乘输出：相乘的结果后置条件

5、：整数a的值发生改变Div前置条件：存在一个整数a输入：一个整数b功能：将整数a与输入的整数b相除输出：若整数b为零，则抛出除零异常，否则输出相除的结果后置条件：整数a的值发生改变Mod前置条件：存在一个整数a输入：一个整数b功能：求当前整数与输入整数的模，即正的余数输出：若整数b为零，则抛出除零异常，否则输出取模的结果后置条件：整数a的值发生改变Equal前置条件：存在一个整数a输入：一个整数b功能：判断整数a与输入的整数b是否相等输出：若相等返回1，否则返回0后置条件：整数a的值不发生改变endADT（3）第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法

6、进行了优化，减少了不必要的乘法运算。6、⑴【解答】下面是简单选择排序算法的伪代码描述。下面是简单选择排序算法的C++描述。分析算法，有两层嵌套的for循环，所以，。⑵算法的伪代码描述如下：算法的C++描述如下：分析算法，只有一层循环，共执行n-2次，所以，T(n)=O(n)。第2章线性表填空1.⑴表长的一半，表长，该元素在表中的位置⑵108第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108⑶p->next=(p->next)->next⑷为了运算方便例如在插入和删除操作时不必对表头的情况进行特殊处理。⑸p->next=head如图2-8所示。⑹s->next=rea

7、r->next;rear->next=s;rear=s;q=rear->next->next;rear->next->next=q->next;deleteq;操作示意图如图2-9所示：⑺Ο(1)，Ο(n)在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。⑻循环链表，循环双链表，双链表2.选择题⑴【解答】A，B【分析】参见2.2.1。⑵【解答】D【分析】线性表的链接