数据结构基础教程习题及解答.docx
《数据结构基础教程习题及解答.docx》由会员分享,可在线阅读,更多相关《数据结构基础教程习题及解答.docx(21页珍藏版)》请在咨信网上搜索。
1、第1章习题解答一、填空1数据是指所有能够输入到计算机中被计算机加工、处理的 符号 的集合。2可以把计算机处理的数据,笼统地分成 数值 型和 非数值 型两大类。3数据的逻辑结构就是指数据间的 邻接关系 。4数据是由一个个 数据元素 集合而成的。5数据项是数据元素中 不可再分割 的最小标识单位,通常不具备完整、确定的实际意义,只是反映数据元素某一方面的属性。6数据是以 数据元素 为单位存放在内存的,分配给它的内存区域称为 存储结点 。7每个数据元素都具有 完整 、 确定 的实际意义,是数据加工处理的对象。8如果两个数据结点之间有着逻辑上的某种关系,那么就称这两个结点是 邻接 的。9在一个存储结点里
2、,除了要有数据本身的内容外,还要有体现 数据间邻接关系 的内容。10从整体上看,数据在存储器内有两种存放的方式:一是集中存放 在一个连续的 内存存储区中;一是利用存储器中的零星区域, 分散地存放在 内存的各个地方。11在有些书里,数据的“存储结构”也称为数据的“ 物理结构 ”。12“基本操作”是指算法中那种所需时间与操作数的具体取值 无关 的操作。二、选择1在常见的数据处理中, B 是最基本的处理。A删除B查找C读取D插入2下面给出的名称中, A 不是数据元素的同义词。A字段B结点C顶点D记录3 D 是图状关系的特例。A只有线性关系B只有树型关系C线性关系和树型关系都不D线性关系和树型关系都4
3、链式存储结构中,每个数据的存储结点里 D指向邻接存储结点的指针,用以反映数据间的逻辑关系。A只能有1个B只能有2个C只能有3个D可以有多个5本书将采用 C 来描述算法。A自然语言B流程图(即框图)C类C语言DC语言6有下面的算法段:for (i=0; in; i+) k+;其时间复杂度为 B 。AO(1)BO(n)CO(log2n)DO(n2)三、问答1中国百家姓中的赵、钱、孙、李、周、吴、郑、王等姓氏数据之间,是一种什么样的邻接关系,为什么?答:是一种线性关系,因为这些姓氏之间符合关系的“有头有尾,顺序排列”的特点。2什么是数据结点?什么是存储结点?它们间有什么关系?答:数据结点即是数据集合
4、中的一个数据元素,存储结点是存放数据结点的内存单位。在存储结点里,不仅要存放数据结点的内容,还要(显式或隐式地)存放数据结点间的逻辑关系。3为什么说链式存储既提高了存储的利用率,又降低了存储的利用率?答:由于链式存储是通过指针来体现数据元素之间的逻辑关系的,因此,存储结点可以不占用存储器的连续存储区。从这个意义上说,链式存储能够充分利用存储器中小的存储区,因此提高了存储器的利用率。另一方面,链式存储中的存储结点不仅要存放数据元素,还要占用适当的存储区来存放指针,这是一种额外的存储开销。从这个意义上说,链式存储降低了存储器的利用率。4列举几个数据之间具有树型结构的实际例子。答:学校各级管理之间,
5、是一种分支层次结构;一本书的书目,是一种分支层次结构。5判断如下除法过程是否是一个算法,为什么:(1)开始;(2)给变量m赋初值5,给变量n赋初值0;(3)m=m/n;(4)输出m;(5)结束。答:因为0不能为除数,本题第(3)步不具有有效性,所以它不是一个算法。但如果n的初值不为0,则是一个正确的算法。四、应用1用类C语言中的do-while语句,描述输出整数1、2、3、9、10的过程。答:算法编写如下。void num () i=1; do printf (“i = %dn”, i ); i = i +1; while (i=0) printf (“输入的是正数”); else print
6、f (“输入的是负数”);3分析算法段中标有记号“#1”和“#2”的基本操作的执行次数:for ( i=0; in; i+) for (j=0; jn; j+) #1 y=1; for (k=0; kn; k+) #2 y=y+1;答:标有记号“#1”的基本操作的执行次数是:n2;标有记号“#2”的基本操作的执行次数是:n3。4给出下面3个算法段的时间复杂度:(1)x+;(2)for (j=1; jn; j+) x+;(3)for (j=1; j=n; j+) printf (“j=%”, j); for (k=j; kPrior-Next = ptr-Next; ptr-Next-Prior
7、 = ptr-Prior; 。7设tail是指向非空、带表头结点的循环单链表的表尾指针。那么,该链表起始结点的存储位置应该表示成 tail-Next-Next 。8在一个不带表头结点的非空单链表中,若要在指针qtr所指结点的后面插入一个值为x的结点,则需要执行下列操作:ptr = malloc (size);ptr-Data = x ;ptr-Next = qtr-Next ;qtr-Next = ptr ;9顺序表Sq = (a1,a2,a3,an)(n1)中,每个数据元素需要占用w个存储单元。若m为元素a1的起始地址,那么元素an的存储地址是m+(n-1)*w。10当线性表的数据元素个数基
8、本稳定、很少进行插入和删除操作,但却要求以最快的速度存取表中的元素时,我们应该对该表采用 顺序 存储结构。二、选择1下面,对非空线性表特点的论述, C 是正确的。A所有结点有且只有一个直接前驱B所有结点有且只有一个直接后继C每个结点至多只有一个直接前驱,至多只有一个直接后继D结点间是按照1对多的邻接关系来维系其逻辑关系的2一般单链表Lk_h为空的判定条件是 A 。ALk_h = NULLBLk_h-Next = NULLCLk_h-Next = Lk_hDLk_h != NULL3带表头结点的单链表Lk_h为空的判定条件是 B 。ALk_h = NULLBLk_h-Next = NULLCLk
9、_h-Next = Lk_hDLk_h != NULL4往一个顺序表的任一结点前插入一个新数据结点时,平均而言,需要移动 B个结点。AnBn/2Cn+1D(n+1)/25在一个单链表中,已知qtr所指结点是ptr所指结点的直接前驱。现要在qtr所指结点和ptr所指结点之间插入一个rtr所指的结点,要执行的操作应该是 C 。Artr-Next = ptr-Next;ptr-Next = rtr;Bptr-Next = rtr-Next;Cqtr-Next = rtr;rtr-Next = ptr;Dptr-Next = rtr;rtr-Next = qtr-Next;6在一个单链表中,若现在要删
10、除ptr指针所指结点的直接后继结点,则需要执行的操作是 A 。Aptr-Next = ptr-Next-Next ;Bptr = ptr-Next; ptr-Next = ptr-Next-Next ;Cptr = ptr-Next-Next ;Dptr-Next ptr ; 7在长度为n的顺序表中,往其第i个元素(1in)之前插入一个新的元素时,需要往后移动 B 个元素。An-iBn-i+1Cn-i-1Di8在长度为n的顺序表中,删除第i个元素(1in)时,需要往前移动 A 个元素。An-iBn-i+1Cn-i-1Di9设tail是指向一个非空带表头结点的循环单链表的尾指针。那么,删除链表起
11、始结点的操作应该是 D 。Aptr = tail ;Btail = tail-Next ; tail = tail-Next ; free (tail) ; free (ptr);Ctail = tail-Next-Next ;Dptr = tail-Next-Next ; Free (tail); tail-Next-Next = ptr-Next ;Free (ptr); free (ptr);10在单链表中,如果指针ptr所指结点不是链表的尾结点,那么在ptr之后插入由指针qtr所指结点的操作应该是 B 。Aqtr-Next = ptr ;Bqtr-Next = ptr-Next ; p
12、tr-Next = qtr ; ptr-Next = qtr ;Cqtr-Next = ptr-Next ;Dptr-Next = qtr ; ptr = qtr ; qtr-Next = ptr ;三、问答1试问,如下的线性表:L = (29,25,21,17,13,11,7,5,3,1)是有序线性表还是无序线性表?答:L是一个有序线性表。2线性表L第i个存储结点ai的起始地址LOC(ai)可以通过下面的公式计算得到:LOC(ai)= LOC(ai-1)+k其中k表示存储结点的长度。这个公式对吗?为什么?答:这个公式是对的,因为第i个存储结点ai的起始地址LOC(ai),实际上就是等于第i-
13、1个存储结点ai-1的起始地址LOC(ai-1)加上一个存储结点的长度k得到。3试说明创建顺序表算法Create_Sq ()中,Sq_max和Sq_num的不同之处。答:Sq_max代表的是顺序表的最大长度,也就是它最多可以容纳下多少个数据元素,顺序表创建后,Sq_max是一个保持不变的常量;Sq_num代表的是顺序表内当前拥有的数据元素个数,在顺序表创建后,随着对数据元素进行的插入、删除操作,Sq_num将会不断地发生变化。4如何判断一个顺序表是否为空?答:只需判定Sq_num的当前值是多少,如果Sq_num为0,则表示顺序表Sq为空,否则表示该顺序表里有数据元素存在。5在算法2-3里,操作
14、“Sq_num=Sq_num -1”的作用是什么?没有它行吗?答:该操作是非常重要的,因为顺序表里当前拥有的元素个数是通过Sq_num来记录的,删除了一个元素,Sq_num必须减1,这样才能正确反映出删除后表中元素的个数。所以,没有这个操作是不行的。6在算法2-9里,如果现在是把一个结点插入到单链表尾结点的后面。按照算法的描述,能够保证插入后最后一个结点的Next域为“”吗?答:能够。因为原来ptr-Next里是“”,做了第1步操作:qtr-Next = ptr-Next ;后,就是把插入结点的Next域置为“”。7在一个单链表中,为了删除指针ptr所指的结点,有人编写了下面的操作序列。读懂并
15、加以理解。试问,编写者能够达到目的吗?其思想是什么?x = ptr-Data ;qtr = ptr-Next ;ptr-Data = ptr-Next-Data ;ptr-Next = ptr-Next-Next ;free (qtr);答:能够达到删除指针ptr所指结点的目的。编写者的思想是不去直接删除ptr所指的结点,而是在把ptr直接后继的Data域内容写入ptr所指结点的Data域之后,把它的直接后继删除。对于单链表来说,得到一个结点的直接后继容易,得到它的直接前驱难,所以这样的设计是有其可取之处的。8在一个单链表中,为了在指针ptr所指结点之前插入一个由指针qtr所指的结点,有人编写
16、了下面的操作序列,其中temp是一个临时工作单元。读懂并加以理解。试问,编写者能够达到目的吗?其思想是什么?qtr-Next = ptr-Next ;ptr-Next = qtr ;temp = ptr-Data ;p-Data = qtr-Data ;qtr-Data = temp ;答:能够达到在指针ptr所指结点之前插入一个由指针qtr所指结点的目的。编写者的思想是考虑到在单链表中得到一个结点的前驱信息较为困难,因此在这里先把qtr所指结点插入到ptr所指结点的后面,暂时成为它的直接后继。然后通过临时工作单元temp,将ptr及qtr所指结点的Data域内容进行交换,从而达到插入的目的。
17、9打算形成一个有表头结点的循环双链表,初始时除了每个结点的Next域已经链接好外,它们的Prior域还都是空的。有人编写了下面的算法,试图完成Prior域的链接:Com_Cd (Cd_h) ptr = Cd_h-Next ; qtr = Cd_h ; while (ptr != Cd_h) ptr -Prior = qtr ; qtr = ptr ; ptr = ptr-Next ;Cd_h-Prior = qtr ;读懂并理解它,解释为什么能够完成各结点的Prior域的链接?答:算法中用两个指针ptr和qtr配合,从头到尾扫描这个循环双链表,以达到让每个结点的Prior域指向其直接前驱的目的
18、。四、应用1设计一个计算表头指针为Lk_h的单链表长度(即结点个数)的算法。答:算法设计如下:Length_Lk (Lk_h)n = 0 ; ptr = Lk_h ;/* ptr指向起始结点 */ while (ptr != NULL) ptr = ptr-Next ; n=n+1 ;/* n为结点计数单元 */return (n) ;2用总是在表的头部插入整数结点的方法建立一个单链表,当输入为0时,建表过程结束。答:算法设计如下:Clink() Lk_h = NULL; scanf (%d, &x); while (x != “0”) ptr = malloc (size);ptr-Data
19、 = x;ptr-Next = Lk_h;Lk_h = ptr;scanf (%d, &x);return Lk_h;3一个不带表头结点的循环双链表Ck的表头指针为Ck_h,要在指针ptr指向处前插入一个rtr所指结点。模仿图2-21,对一般插入位置标示出下面4个操作步骤:rtr-Next = ptr ;rtr-Prior = ptr-Prior ;ptr-Prior-Next = rtr ;ptr-Prior = rtr ;答:4个操作步骤的具体功能体现如下图所示。4试设计一个算法copy (Ck_h1, Ck_h2),将一个带表头结点的、以Ck_h1为表头指针的单链表Ck1的内容,复制到一
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 基础教程 习题 解答
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。