欢迎来到天天文库
浏览记录
ID:34932054
大小:319.00 KB
页数:39页
时间:2019-03-14
《数据结构习题集参考答案解析》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、习题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
4、,.....,n,n≥0}r={
5、i=1,2,…,n-1,n≥0}(2)基本操作①初始化操作函数:InitBookList(&BL)。初始条件:图书表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。⑥插入图书操作函数:insert
7、Book(&BL,i,b)。初始条件:图书表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
8、-1,时间复杂度为T(n)=O(n)。(3)【解】选取的基本语句为最内层的循环体语句“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循环选取的基本语句为“
9、if(b[i]
10、长率相同,都是线性增长的。13.【解】由题意,设计程序如下:#include#includestructstuInfo{intnum;charname[18];intscore;};voidinp
此文档下载收益归作者所有