数据结构(C++版)王红梅-版课后答案.doc
《数据结构(C++版)王红梅-版课后答案.doc》由会员分享,可在线阅读,更多相关《数据结构(C++版)王红梅-版课后答案.doc(77页珍藏版)》请在咨信网上搜索。
1、第 1 章 绪 论课后习题讲解1. 填空( )是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素( )是数据的最小单位,( )是讨论数据结构时涉及的最小数据单位。【解答】数据项,数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。 从逻辑关系上讲,数据结构主要分为( )、( )、( )和( )。【解答】集合,线性结构,树结构,图结构 数据的存储结构主要有( )和( )两种基本方法,不论哪种存储结构,都要存储两方面的内容:( ) 和( )。【解答】顺序存储结构,链接存储结构,数据元素,数据元素之间的关系 算法具有五个特性,分别是( )、( )、( )、(
2、)、( )。【解答】有零个或多个输入,有一个或多个输出,有穷性,确定性,可行性 算法的描述方法通常有( )、( )、( )和( )四种,其中,( )被称为算法语言。【解答】自然语言,程序设计语言,流程图,伪代码,伪代码 在一般情况下,一个算法的时间复杂度是( )的函数。【解答】问题规模 设待处理问题的规模为 n,若一个算法的时间复杂度为一个常数,则表示成数量级的形式为( ),若 为 n*log25n,则表示成数量级的形式为( )。【解答】(1),(nlog2n)【分析】用大 O 记号表示算法的时间复杂度,需要将低次幂去掉,将最高次幂的系数去掉。2. 选择题 顺序存储结构中数据元素之间的逻辑关系
3、是由( )表示的,链接存储结构中的数据元素之间的逻辑关 系是由( )表示的。A 线性结构 B 非线性结构 C 存储位置 D 指针【解答】C,D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素,其逻辑关系由存储位置(即元素在数 组中的下标)表示;链接存储结构中一个数据元素对应链表中的一个结点,元素之间的逻辑关系由结点中 的指针表示。 假设有如下遗产继承规则:丈夫和妻子可以相互继承遗产;子女可以继承父亲或母亲的遗产;子女间不 能相互继承。则表示该遗产继承关系的最合适的数据结构应该是( )。A 树 B 图 C 线性表 D 集合【解答】B【分析】将丈夫、妻子和子女分别作为数据元素,根据题意画
4、出逻辑结构图。 算法指的是( )。A 对特定问题求解步骤的一种描述,是指令的有限序列。B 计算机程序 C 解决问题的计算方法 D 数据处理【解答】A【分析】计算机程序是对算法的具体实现;简单地说,算法是解决问题的方法;数据处理是通过算法完成 的。所以,只有 A 是算法的准确定义。 下面( )不是算法所必须具备的特性。A 有穷性 B 确切性 C 高效性 D 可行性【解答】C【分析】高效性是好算法应具备的特性。 算法分析的目的是( ),算法分析的两个主要方面是( )。A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时
5、间性能 F 正确性和简明性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)。 分析条件语句,每循环一次,i+j 整体加 1,共循环 n 次,所以 T(n)=O(n)。 设循环体共执行 T(n)次,每循环一次,循环变量 y 加 1,最终 T(n)=y,即:(T(n)+1)2n,所以 T(n)=O(n 1/2)。 x+是基本语句,所以 5设有数据结构(D,R),其中 D=1, 2, 3, 4, 5, 6,R=(1,2),(2
7、,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)。试画出其逻辑结构图并指出属于何种结构。【解答】其逻辑结构图如图 1-3 所示,它是一种图结构。6. 为整数定义一个抽象数据类型,包含整数的常见运算,每个运算对应一个基本操作,每个基本操作的接 口需定义前置条件、输入、功能、输出和后置条件。【解答】整数的抽象数据类型定义如下:ADT integerData整数 a:可以是正整数(1, 2, 3, )、负整数(-1, -2, -3, )和零OperationConstructor 前置条件:整数 a 不存在 输入:一个整数 b 功能:构造一个与输入值相同的整数输出:无后
8、置条件:整数 a 具有输入的值Set 前置条件:存在一个整数 a 输入:一个整数 b功能:修改整数 a 的值,使之与输入的整数值相同 输出:无后置条件:整数 a 的值发生改变Add 前置条件:存在一个整数 a 输入:一个整数 b功能:将整数 a 与输入的整数 b 相加 输出:相加后的结果后置条件:整数 a 的值发生改变Sub 前置条件:存在一个整数 a 输入:一个整数 b功能:将整数 a 与输入的整数 b 相减 输出:相减的结果后置条件:整数 a 的值发生改变Multi 前置条件:存在一个整数 a 输入:一个整数 b功能:将整数 a 与输入的整数 b 相乘 输出:相乘的结果后置条件:整数 a
9、的值发生改变Div 前置条件:存在一个整数 a 输入:一个整数 b功能:将整数 a 与输入的整数 b 相除输出:若整数 b 为零,则抛出除零异常,否则输出相除的结果 后置条件:整数 a 的值发生改变Mod 前置条件:存在一个整数 a 输入:一个整数 b功能:求当前整数与输入整数的模,即正的余数输出:若整数 b 为零,则抛出除零异常,否则输出取模的结果 后置条件:整数 a 的值发生改变Equal 前置条件:存在一个整数 a 输入:一个整数 b功能:判断整数 a 与输入的整数 b 是否相等 输出:若相等返回 1,否则返回 0后置条件:整数 a 的值不发生改变endADT7. 求多项式 A(x)的算
10、法可根据下列两个公式之一来设计: A(x)=anxn+an-1xn-1+a1x+a0 A(x)=(anx+an-1)x+a1)x)+a0根据算法的时间复杂度分析比较这两种算法的优劣。【解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算,而第二种算法进行了优化, 减少了不必要的乘法运算。8. 算法设计(要求:算法用伪代码和 C+描述,并分析最坏情况下的时间复杂度) 对一个整型数组 An设计一个排序算法。【解答】下面是简单选择排序算法的伪代码描述。下面是简单选择排序算法的 C+描述。分析算法,有两层嵌套的 for 循环,所以, 。 找出整型数组 An中元素的最大值和次最大值。【解答】
11、算法的伪代码描述如下:算法的 C+描述如下:分析算法,只有一层循环,共执行 n-2 次,所以,T(n)=O(n)。学习自测及答案1顺序存储结构的特点是( ),链接存储结构的特点是( )。【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系,用指示元素存储地址的指针表示 数据元素之间的逻辑关系。2. 算法在发生非法操作时可以作出处理的特性称为( )。【解答】健壮性3. 常见的算法时间复杂度用大记号表示为:常数阶( )、对数阶( )、线性阶 ( )、平方阶( )和指数阶( )。【解答】(1),(log2n),(n),(n2),(2n)4将下列函数按它们在 n 时的无穷大阶数,从小到大排列
12、。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试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。【解答】数据结构是指相互之间存在一定关系的数据元素的集合。而抽象数据类型是指一个数据结构以及 定义在该结构上的一组操作。程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的 总称。抽象数据类型可以看成是对数据类型的一种抽象。6
13、. 对下列用二元组表示的数据结构,试分别画出对应的逻辑结构图,并指出属于何种结构。 A=(D,R), 其中 D=a1, a2, a3, a4,R= B=(D,R), 其中 D=a, b, c, d, e, f,R=, C=( D,R),其中 D=a,b,c,d,e,f,R=, D=(D,R), 其中 D=1, 2, 3, 4, 5, 6,R=(1, 2),(1, 4),(2, 3),(2, 4),(3, 4),(3, 5),(3, 6),(4, 6)【解答】 属于集合,其逻辑结构图如图 1-4(a)所示; 属于线性结构,其逻辑结构图如图 1-4(b)所示; 属于树结构,其逻辑结构图如图 1-4
14、(c)所示; 属于图结构,其逻辑结构图如图 1-4(d)所示。7. 求下列算法的时间复杂度。count=0; x=1; while (x x*=2; count+;return count;【解答】(log2n)第 2 章 线性表课后习题讲解1. 填空 在顺序表中,等概率情况下,插入和删除一个元素平均需移动( )个元素,具体移动元素的个数与( ) 和( )有关。【解答】表长的一半,表长,该元素在表中的位置 顺序表中第一个元素的存储地址是 100,每个元素的长度为 2,则第 5 个元素的存储地址是( )。【解答】108【分析】第 5 个元素的存储地址=第 1 个元素的存储地址(51)2=108
15、设单链表中指针 p 指向结点 A,若要删除 A 的后继结点(假设 A 存在后继结点),则需修改指针的操 作为( )。【解答】p-next=(p-next)-next 单链表中设置头结点的作用是( )。【解答】为了运算方便【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。 非空的单循环链表由头指针 head 指示,则其尾结点(由指针 p 所指)满足( )。【解答】p-next=head【分析】如图 2-8 所示。 在由尾指针 rear 指示的单循环链表中,在表尾插入一个结点 s 的操作序列是( );删除开始结点的操作序列为( )。【解答】s-next =rear-next; rear-
16、next =s; rear =s;q=rear-next-next; rear-next-next=q-next; delete q;【分析】操作示意图如图 2-9 所示: 一个具有 n 个结点的单链表,在指针 p 所指结点后插入一个新结点的时间复杂度为( );在给定值为x 的结点后插入一个新结点的时间复杂度为( )。【解答】(1),(n)【分析】在 p 所指结点后插入一个新结点只需修改指针,所以时间复杂度为 (1);而在给定值为 x 的结点 后插入一个新结点需要先查找值为 x 的结点,所以时间复杂度为 (n)。 可由一个尾指针唯一确定的链表有( )、( )、( )。【解答】循环链表,循环双链
17、表,双链表2. 选择题 线性表的顺序存储结构是一种( )的存储结构,线性表的链接存储结构是一种( )的存储结构。A 随机存取 B 顺序存取 C 索引存取 D 散列存取【解答】A,B【分析】参见 2.2.1。 线性表采用链接存储时,其地址( )。A 必须是连续的 B 部分地址必须是连续的C 一定是不连续的 D 连续与否均可以【解答】D【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以连续,也 可以不连续,甚至可以零散分布在内存中任意位置。 单循环链表的主要优点是( )。A 不再需要头指针了B 从表中任一结点出发都能扫描到整个链表;C 已知某个结点的位置后,能够容
18、易找到它的直接前趋;D 在进行插入、删除操作时,能更好地保证链表不断开。【解答】B 链表不具有的特点是( )。A 可随机访问任一元素 B 插入、删除不需要移动元素C 不必事先估计存储空间 D 所需空间与线性表长度成正比【解答】A 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋,则采用( )存储方法最节省时间。A 顺序表 B 单链表 C 双链表 D 单循环链表【解答】A【分析】线性表中最常用的操作是取第 i 个元素,所以,应选择随机存取结构即顺序表,同时在顺序表中 查找第 i 个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取,查找第 i 个元素的前趋也不方 便,双链
19、表虽然能快速查找第 i 个元素的前趋,但不能实现随机存取。 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点,则采用( )存储方法 最节省时间。A 单链表 B 带头指针的单循环链表 C 双链表 D 带尾指针的单循环链表【解答】D【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址,所以,单链表、带头指针 的单循环链表、双链表都不合适,考虑在带尾指针的单循环链表中删除第一个结点,其时间性能是 O(1), 所以,答案是 D 。 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点,则采用( )存储方 法最节省运算时间。A 单链表 B 循环双链表
20、 C 单循环链表 D 带尾指针的单循环链表【解答】B【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址,所以,单链表、单循环链 表都不合适,删除最后一个结点需要知道终端结点的前驱结点的地址,所以,带尾指针的单循环链表不合 适,而循环双链表满足条件。 在具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。A O(1) B O(n) C O(n2) D O(nlog2n)【解答】B【分析】首先应顺序查找新结点在单链表中的位置。 对于 n 个元素组成的线性表,建立一个有序单链表的时间复杂度是( )。A O(1) B O(n) C O(n2) D O(nlog
21、2n)【解答】C【分析】该算法需要将 n 个元素依次插入到有序单链表中,而插入每个元素需 O(n)。 使用双链表存储线性表,其优点是可以( )。A 提高查找速度 B 更方便数据的插入和删除C 节约存储空间 D 很快回收存储空间【解答】B【分析】在链表中一般只能进行顺序查找,所以,双链表并不能提高查找速度,因为双链表中有两个指针 域,显然不能节约存储空间,对于动态存储分配,回收存储空间的速度是一样的。由于双链表具有对称性, 所以,其插入和删除操作更加方便。 在一个单链表中,已知 q 所指结点是 p 所指结点的直接前驱,若在 q 和 p 之间插入 s 所指结点,则执 行( )操作。A s-next
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 C+ 红梅 课后 答案
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。