数据结构习题参考答案解析

《数据结构习题参考答案解析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、WORD格式可编辑习题1参考答案1至8题答案略。9.（1）【解】该逻辑结构为线性结构，其图形表示如下：SunMonTueWedThuFriSat（2）【解】该逻辑结构为树型结构，其图形表示如下：bcdefghjika（3）【解】该逻辑结构为图型结构，其图形表示如下：bcdea（4）【解】该逻辑结构为线性结构，其图形表示如下：c1c2c3cn……10.【解】该图书库存管理系统所要处理的数据对象为图书，所以该问题中涉及的数据元素为图书，设数据元素类型为bookType类型。每个数据元素应包含的数据项有图书编号、书名、作者、出版社、出版日期等。可用一个表格（

2、如下表）的形式表示图书间的逻辑关系，即该问题数学模型可采用简单的线性结构来表示。图书信息表编号书名作者出版社出版日期1数据结构顾泽元北京航空航天大学出版社2011年6月2高等数学李四北京航空航天大学出版社2009年1月3计算方法张五清华大学出版社2008年12月根据问题需求功能目标，此模型的所需的主要处理操作有插入、删除、查找和修改等基本操作。所以，现用抽象数据类型bookList表示问题模型，其逻辑结构与基本操作的定义如下：（1）逻辑结构bookList=(D,{r})D={bi

3、bi为bookType类型的元素，i=1,2,3,.....,n，n≥

4、0}r={

5、i=1,2,…,n-1,n≥0}（2）基本操作①初始化操作函数：InitBookList(&BL)。专业技术资料分享WORD格式可编辑初始条件：图书表BL不存在。操作结果：构造一个空的图书表BL。②求图书表长度操作函数：bookListLength(BL)。初始条件：图书表BL已存在。操作结果：返回图书表BL中所包含的数据元素（图书）的个数。③取图书表中元素操作函数：getBook(BL,i,&b)。初始条件：图书表BL已存在，且1≤i≤bookListLength(BL)。操作结果：用b返回图书表BL中的第i个数据元素

6、的值。④按编号查找操作函数：locateById(BL,id)。初始条件：图书表BL已存在，id是给定的一个图书编号。操作结果：返回图书表BL中图书编号为id的数据元素的位序，若这样的数据元素不存在，则返回0。⑤按编号查找操作函数：locateByName(BL,i,name)。初始条件：图书表BL已存在，且1≤i≤bookListLength(BL)，name是给定的一个图书名。操作结果：从图书表BL中第i个元素开始，查找图书名与给定name相等的第一个元素，若找到则返回其位序，否则返回0。⑥插入图书操作函数：insertBook(&BL,i,b)。

7、初始条件：图书表BL已存在，且1≤i≤bookListLength(BL)+1。操作结果：在图书表BL的第i个位置上插入一个值为b的新元素，使线性表的长度增1。⑦删除操作操作函数：deleteBook(&BL,i,&b)。初始条件：线性表L已存在，1≤i≤listLength(L)。操作结果：删除图书表BL的第i个数据元素，并用b返回其值，使线性表的长度减1。11.（1）【解】函数体内为简单语句，时间复杂度为T(n)=O(1)（2）【解】选取的基本语句为“if(a[i]>a[k])k=i;”其执行频度为n-1，时间复杂度为T(n)=O(n)。（3）【解

8、】选取的基本语句为最内层的循环体语句“total+=a[i][j];”，其执行频度为n(n+1)/2，时间复杂度为T(n)=O(n2)。（4）【解】选取的基本语句为最内层的循环体语句“c[i][j]+=a[i][k]*b[k][j];”，其执行频度为n3，时间复杂度为T(n)=O(n3)。（5）【解】函数有两个并列的循环，其问题规模分别为n和m，对于第一个for循环选取的基本语句为“if(a[i]>a[max])max=i;”，其执行频度为n-1；对于第二个for循环选取的基本语句为“if(b[i]

9、以该函数的时间复杂度为T(n,m)=O(n+m)。（6）【解】选取的基本语句为while的循环体，其执行频度为max{}，时间复杂度为T(n)=O()。12.专业技术资料分享WORD格式可编辑【解】算法（1）中有两个并列的循环，每个循环的循环体语句执行次数均为n，故该函数的语句频度为2n。算法（2）只用了一个循环，其循环体语句执行次数为n，即该函数的语句频度为n。所以算法（1）与算法（2）相比较，算法（1）的时间效率更好。但它们的时间复杂度都为O（n），这说明：随着n值的增大，这两个函数执行时间的增长率相同，都是线性增长的。13.【解】由题意，设计程序

10、如下：#include#includestructstu