《数据结构-C语言描述》习题及答案耿国华

第1章绪论习题一、问答题1.什么是数据结构?2.四类基本数据结构的名称与含义。3.算法的定义与特性。4.算法的时间复杂度。5.数据类型的概念。6.线性结构与非线性结构的差别。7.面向对象程序设计语言的特点。8.在面向对象程序设计中,类的作用是什么?9.参数传递的主要方式及特点。10.抽象数据类型的概念。二、判断题1.线性结构只能用顺序结构来存放,非线性结构只能用非顺序结构来存放。2.算法就是程序。3.在高级语言（如C、或PASCAL）中，指针类型是原子类型。三、计算下列程序段中XX1的语句频度fori1iltniforj1jltijfork1kltjkxx1提示：i1时：111X1/2112/2i2时：1212×2∕2222/2i3时：12313X3/2332/2…in时：123……n1n×n∕2nn2∕2fn123……n122232……n2/21nn/2nn12n1/6/2nn1n2/6n3/6n2/2n/3区分语句频度和算法复杂度：OfnOn3四、试编写算法求一元多项式Pnxa0a1xa2x2a3x3…anxn的值Pnx0,并确定算法中的每一语句的执行次数和整个算法的时间复杂度要求时间复杂度尽可能的小,规定算法中不能使用求幂函数。注意：本题中的输入aii01∙∙∙nX和n,输出为Pnx0.通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递;（2）通过全局变量隐式传递。试讨论这两种方法的优缺点,并在本题算法中以你认为较好的一种方式实现输入和输出。提示：floatPolyValuefloatafloatXintn核心语句:p1X的零次幂s0i从0到n循环SsaipPpX或:PXX的一次幂sa0i从1到n循环SsaipPpX实习题设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法,以及求有理数的分子、分母。第一章答案1.3计算下列程序中xx1的语句频度fori1iltniforj1jltijfork1kltjkxx1【解答】xx1的语句频度为：Tn112(123)……(12……n)nn1n2/61.4试编写算法,求pnxa0a1xa2x2 .anxn的值pnx0并确定算法中每一语句的执行次数和整个算法的时间复杂度,要求时间复杂度尽可能小,规定算法中不能使用求幂函数。注意:本题中的输入为@打01…n、X和n输出为Pnx0。算法的输入和输出采用下列方法(1)通过参数表中的参数显式传递(2)通过全局变量隐式传递。讨论两种方法的优缺点,并在算法中以你认为较好的一种实现输入输出。【解答】(1)通过参数表中的参数显式传递优点:当没有调用函数时,不占用内存,调用结束后形参被释放,实参维持,函数通用性强,移置性强。缺点:形参须与实参对应,且返回值数量有限。(2)通过全局变量隐式传递优点:减少实参与形参的个数,从而减少内存空间以及传递数据时的时间消耗缺点:函数通用性降低,移植性差算法如下:通过全局变量隐式传递参数POlyValUeintinfloatxapPrintf“nn”scanf“f”ampnprintf“nx”scanf“f”ampxfori0iltniscanf“f”ampai/执行次数:n次/pa0fori1iltnippaix/执行次数:n次/xxxPrintf“f”P算法的时间复杂度:TnOn通过参数表中的参数显式传递floatPolyValuefloatafloatxintnfloatpsintipxsa0fori1iltnissaip/执行次数:n次/ppxreturnp算法的时间复杂度:TnOn第2章线性表习题2.1描述以下三个概念的区别:头指针,头结点,首元素结点。2.2填空:(1)在顺序表中插入或删除一个元素,需要平均移动__一半__元素,具体移动的元素个数与__插入或删除的位置__有关。(2)在顺序表中,逻辑上相邻的元素,其物理位置 相邻。在单链表中,逻辑上相邻的元素,其物理位置 相邻。(3)在带头结点的非空单链表中,头结点的存储位置由 指示,首元素结点的存储位置由 指示,除首元素结点外,其它任一元素结点的存储位置由―其直接前趋的next域—指示。2.3已知1是无表头结点的单链表,且P结点既不是首元素结点,也不是尾元素结点。按要求从下列语句中选择合适的语句序列。a.在P结点后插入5结点的语句序列是:_(4)(1)_。、b.在P结点前插入5结点的语句序列是:、(7)(11)(8)(4)、、、(1)。c.在表首插入5结点的语句序列是：、(5)(12)。d.在表尾插入5结点的语句序列是:、、、。(11)(9)(1)(6)供选择的语句有：(1)P-gtnextS(2)P-gtnextP-gtnext-gtnext(3)P-gtnextS-gtnext(4)S-gtnextP-gtnext(5)S-gtnextL(6)S-gtnextNULL(7)QP(8)whileP-gtnextQPP-gtnext(9)whileP-gtnextNULLPP-gtnext(10)PQ(11)PL(12)LS(13)LP2.4已知线性表L递增有序。试写一算法,将X插入到L的适当位置上，以保持线性表L的有序性。提示:voidinsertSeqListLElemTypexlt方法1gt(1)找出应插入位置i,(2)移位，(3)……lt方法2gt参P.2292.5写一算法,从顺序表中删除自第i个元素开始的k个元素。提示:注意检查i和k的合法性。(集体搬迁,、“新房”“旧房”)lt方法1gt以待移动元素下标m(“旧房号”)为中心,计算应移入位置()“新房号”：formi-1kmltL-gtlastmL-gtelemm-kL-gtelemmlt方法2gt同时以待移动元素下标m和应移入位置j为中心：建方法3gt以应移入位置j为中心,计算待移动元素下标:2.6已知线性表中的元素(整数)以值递增有序排列,并以单链表作存储结构。试写一高效算法,删除表中所有大于mink且小于maxk的元素(若表中存在这样的元素)，分析你的算法的时间复杂度(注意:mink和maxk是给定的两个参变量,它们的。值为任意的整数)提示:注意检查mink和maxk的合法性:minkltmaxk不要一个一个的删除(多次修改next域)。(1)找到第一个应删结点的前驱prepreLpL-gtnextwhilepNULLampampp-gtdataltminkPreppp-gtnext(2)找到最后一个应删结点的后继s,边找边释放应删结点SpwhileSNULLampamps-gtdataltmaxktSss-gtnextfreet(3)pre-gtnexts2.7试分别以不同的存储结构实现线性表的就地逆置算法,即在原表的存储空间将线性表(a1a2...an)逆置为(anan-1...a1)。(1)以一维数组作存储结构,设线性表存于a1:arrsize的前elenum个分量中。(2)以单链表作存储结构。方法1:在原头结点后重新头插一遍方法2:可设三个同步移动的指针pqr,将q的后继r改为p2.8假设两个按元素值递增有序排列的线性表A和B,均以单链表作为存储结构,请编写算法,将A表和B表归并成一个按元素值递减有序的排列的线性表C,并要求利用原表(即A表和B表的)结点空间存放表C.提示:参P.28例2-1lt方法1gtvoidmergeLinkLiStALinkListBLinkListC paA-gtnextpbB-gtnextCAC-gtnextNULLwhilepaNULLampamppbNULLifpa-gtdataltpb-gtdataSmallerpapapa-gtnextSmaller-gtnextC-gtnext/头插法/C-gtnextSmallerelSeSmallerpbpbpb-gtnextSmaller-gtnextC-gtnextC-gtnextSmallerwhilepaNULLSmallerpapapa-gtnextSmaller-gtnextC-gtnextC-gtnextSmallerwhilepbNULLSmallerpbpbpb-gtnextSmaller-gtnextC-gtnextC-gtnextSmallerlt方法2gtLinkLiStmergeLinkLiStALinkLiStB……LinkLiStC;paA-gtnextpbB-gtnextCAC-gtnextNULL…………returnC2.9假设有一个循环链表的长度大于1,且表中既无头结点也无头指针。已知S为指向链表某个结点的指针,试编写算法在链表中删除指针S所指结点的前趋结点。提示:设指针p指向S结点的前趋的前趋,p与S有何关系?则2.10已知有单链表表示的线性表中含有三类字符的数据元素(如字母字符、数字字符和其它字符),试编写算法来构造三个以循环链表表示的线性表,使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。2.11设线性表Aa1a2…am,Bb1b2∙∙∙bn,试写一个按下列规则合并A、B为线性表C的算法,使得:Calbl…ambmbm1…bn当m≤n时；或者Ca1b1…anbnan1…am当mgtn时。线性表A、B、C均以单链表作为存储结构,且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。提示:voidmergeLinkListALinkListBLinkListC或：LinkListmergeLinkListALinkListB2.12将一个用循环链表表示的稀疏多项式分解成两个多项式,使这两个多项式中各自仅含奇次项或偶次项,并要求利用原链表中的结点空间来构成这两个链表。提示:注明用头指针还是尾指针。2.13建立一个带头结点的线性链表,用以存放输入的二进制数,链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算。提示:可将低位放在前面。2.14设多项式PX采用课本中所述链接方法存储。写一算法,对给定的X值,求PX的值。提示:floatPolyValuePolylistpfloatX……实习题1.将若干城市的信息存入一个带头结点的单链表,结点中的城市信息包括城市名、城市的位置坐标。要求:（1）给定一个城市名，返回其位置坐标；（2）给定一个位置坐标P和一个距离D,返回所有与P的距离小于等于D的城市。2.约瑟夫环问题。约瑟夫问题的一种描述是:编号为1,2,∙∙∙,n的n个人。一开始按顺时针方向围坐一圈,每人持有一个密码（正整数）任选一个整数作为报数上限值m从第一个人开始顺时针自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止。试设计一个程序,求出出列顺序。利用单向循环链表作为存储结构模拟此过程,按照出列顺序打印出各人的编号。例如m的初值为20;n7,7个人的密码依次是:3,1,7,2,4,8,4,出列的顺序为6,1,4,7,2,3,5。第二章答案约瑟夫环问题约瑟夫问题的一种描述为:编号12∙∙∙n的n个人按顺时针方向围坐一圈,每个人持有一个密码（正整数）。一开始任选一个报数上限值m从第一个人开始顺时针自1开始顺序报数,报到m时停止报数。报m的人出歹列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止。试设计一个程序,求出出列顺序。利用单向循环链表作为存储结构模拟此过程,按照出列顺序打印出各人的编号。例如m的初值为20;n7,个人的密码依次是：73172484出列顺序为6147235。【解答】算法如下：typedefstructNodeintpasswordintnumstructNodenextNodeLinklistvoidJosephusLinklistLNodeprqintmnCjLNodemallocsizeofNode/初始化单向循环链表/ifLNULLprintfquotn链表申请不到空间quotreturnL-gtnextNULLrLPrintfqUot请输入数据n的值ngt0:quotscanfquotdquotampnforj1jltnj/建立链表/pNodemallocsizeofNodeifpNULLPrintfqUot请输入第d个人的密码:quotjScanfqUotdqUotampCp-gtpaSSwordCp-gtnumjr-gtnextprpr-gtnextL-gtnextprintfquot请输入第一个报数上限值mmgt0:quotScanfqUotdqUotamPmPrintfqUotnqUotprintfquot出列的顺序为:nquotqLpL-gtnextWhilenI/计算出列的顺序/j1Whilejltm/计算当前出列的人选p/qp/q为当前结点P的前驱结点/pp-gtnextjprintfquotd-gtqUotP-gtnUmmP-gtPassword/获得新密码/n--q-gtnextP-gtnext/P出列/rPPP-gtnextfreerPrintfqUotdnqUotP-gtnUm2.7试分别以不同的存储结构实现单线表的就地逆置算法,即在原表的存储空间将线性表(a1a2∙∙∙an)逆置为anan-1∙∙∙a1。【解答】(1)用一维数组作为存储结构VoidinvertSeqListLintnUmintjElemTyPetmPforj0jltnUm-1/2jtmPLjLjLnUm-j-1Lnum-j-ltmP(2)用单链表作为存储结构VoidinvertLinkLiStLNodePqrifL-gtnextNULLretUrn/链表为空/PL-gtnextqP-gtnextP-gtnextNULL/摘下第一个结点,生成初始逆置表/whileqNULL/从第二个结点起依次头插入当前逆置表/rq-gtnextq-gtnextL-gtnextL-gtnextqqr2.11将线性表Aa1a2amBb1b2 bn合并成线性表C或Ca1b1 ambmbm1.bn当mltn时,Calbl anbnan1 am当mgtn时线性表A、B、C以单链表作为存储结构,且C表利用A表和B表中的结点空间构成。注意:单链表的长度值m和n均未显式存储。【解答】算法如下：LinkListmergeLinkListALinkListBLinkListCNodePaqapbqbPpaA-gtnext/pa表示A的当前结点/pbB-gtnextpA/利用P来指向新连接的表的表尾,初始值指向表A的头结点/whilePaNULLamPamPPbNULL/利用尾插法建立连接之后的链表/qaPa-gtnextqbqb-gtnextp-gtneXtPa/交替选择表A和表B中的结点连接到新链表中；/PPaP-gtnextPbPPbPaqaPbqbifPaNULLP-gtnextPa/A的长度大于B的长度/ifPbNULLP-gtneXtPb/B的长度大于A的长度/CAReturnC第3章限定性线性表—栈和队列习题1.按图3.1b所示铁道(两侧铁道均为单向行驶道)进行车厢调度，回答:⑴如进站的车厢序列为123,则可能得到的出站车厢序列是什么？123、213、132、231、321(312)⑵如进站的车厢序列为123456,能否得到435612和135426的出站序歹列,并说明原因。(即写出以“S”表示进栈、以“X”表示出栈的栈操作序列)。SXSSXSSXXXSX或S1X1S2S3X3S4S5X5X4X2S6X62.设队列中有A、B、C、D、E这5个元素,其中队首元素为A。如果对这个队列重复执行下列4步操作：(1)输出队首元素;(2)把队首元素值插入到队尾;(3)删除队首元素;(4)再次删除队首元素。直到队列成为空队列为止,则是否可能得到输出序列：(1)A、C、E、C、C(2)A、C、E(3)A、C、E、C、C、C(4)A、C、E、C提示:A、B、C、D、E（输出队首元素A）A、B、C、D、E、A（把队首元素A插入到队尾）B、C、D、E、A（删除队首元素A）C、D、E、A（再次删除队首元素B）