数据结构课后习题答案

第1章绪论一、基础知识题1.1简述下列概念数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，算法。【解答】数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种总体描述。每一种计算机程序设计语言都定义有自己的数据类型。“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。数据结构在计算机中的表示称为物理结构，又称存储结构。是逻辑结构在存储器中的映像，包括数据元素的表示和关系的表示。逻辑结构与计算机无关。算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。一个算法应该具有下列特性：有穷性、确定性、可行性、输入和输出。1.2数据的逻辑结构分哪几种，为什么说逻辑结构是数据组织的主要方面？【解答】数据的逻辑结构分为线性结构和非线性结构。（也可以分为集合、线性结构、树形结构和图形即网状结构）。逻辑结构是数据组织的某种“本质性”的东西：（1）逻辑结构与数据元素本身的形式、内容无关。（2）逻辑结构与数据元素的相对位置无关。（3）逻辑结构与所含数据元素的个数无关。1.3试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算三方面的内容。【解答】学生成绩表，逻辑结构是线性结构，可以顺序存储（也可以链式存储），运算可以有插入、删除、查询，等等。1.4简述算法的五个特性，对算法设计的要求。【解答】算法的五个特性是：有穷性、确定性、可行性、零至多个输入和一至多个输出。对算法设计的要求：正确性，易读性，健壮性，和高的时空间效率（运算速度快，存储空间小）。1.5设n是正整数，求下列程序段中带@记号的语句的执行次数。(1)i=1;k=0;(2)i=1;j=0;while(in)while(i+j=n){k=k+50*i;i++;@{if(ij)j++;@}elsei++;}@(3)x=y=0;(4)x=91;y=100;for(i=0;in;i++)@while(y0)for(j=0;jn;j++)@if(x100){x++;@{x=x-10;y--;@for(k=0;kn;k++)@}y++;@elsex++;@}【解答】(1)n-1(2)i=n/2，j=n/2(3)n+1,n(n+1),n2,(n+1)n2,n3(4)100,10001.6有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。【解答】对算法A1和A2的时间复杂度T1和T2取对数，得nlog2和2logn。显然，当n4时，算法A1好于A2；当n=4时，两个算法时间复杂度相同；当n4时，算法A2好于A1。1.7选择题：算法分析的目的是（）A、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的效率以求改进D、分析算法的易懂性和文档特点【解答】C二、算法设计题1.8已知输入x，y，z三个不相等的整数，设计一个“高效”算法，使得这三个数按从小到大输出。“高效”的含义是用最少的元素比较次数、元素移动次数和输出次数。【算法1.8】voidBest(){//按序输出三个整数的优化算法inta,b,c,t;scanf(“%d%d%d”,&a,&b,&c);if(ab){t=a;a=b;b=t:}//a和b已正序if(bc){t=c;c=b;//c已到位if(at){b=a;a=t;}//a和b已正序elseb=t;}printf(“%d,%d,%d\n”,a,b,c);//最佳2次比较，无移动；最差3次比较，7个赋值}1.9在数组A[n]中查找值为k的元素，若找到则输出其位置i(1≤i≤n)，否则输出0作为标志。设计算法求解此问题，并分析在最坏情况下的时间复杂度。【题目分析】从后向前查找，若找到与k值相同的元素则返回其位置，否则返回0。【算法1.9】intSearch(ElemTypeA[n+1],ElemTypek){i=n;while(i=1)&&(A[i]!=k))i--;if(i=1)returni;elsereturn0;}当查找不成功时，总的比较次数为n+1次，所以最坏情况下时间复杂度为O(n)。在学过第9章“查找”后，可优化以上算法:设“监视哨”。算法如下：intSearch(ElemTypeA[n+1],ElemTypek){i=n;A[0]=k;while(A[i]!=k)i--;returni;}研究表明，当n=1000时，算法效率提高50%。第2章线性表一、基础知识题2.1试述头指针、头结点、元素结点、首元结点的区别，说明头指针和头结点的作【解答】指向链表第一个结点（或为头结点或为首元结点）的指针称为头指针。“头指针”具有标识一个链表的作用，所以经常用头指针代表链表的名字，如链表L既是指链表的名字是L，也是指链表的第一个结点的地址存储在指针变量L中，头指针为“NULL”则表示指针变量L没指向任何链表。有时，我们在整个线性链表的第一个元素结点之前加入一个结点，称为头结点，它的数据域可以不存储任何信息（当然，作为“副产品”，头结点的数据域也可能做监视哨或存放线性表的长度等附加信息），指针域中存放的是第一个数据结点的地址，空表时为空。“头结点”的加入，使插入和删除等操作方便、统一。元素结点即是数据结点，至少包括元素自身信息和其后继元素的地址两个域。首元结点是指链表中第一个数据元素的结点；为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。2.2分析顺序存储结构和链式存储结构的优缺点，说明何时应该利用何种结构。【解答】①从空间上来看，当线性表的长度变化较大，难以估计其规模时，选用动态的链表作为存储结构比较合适。由于链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变化不大，易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。②从时间上看，顺序表具有按元素序号随机访问的特点，在顺序表中按序号访问数据元素的时间复杂度为O(1)；而链表中按序号访问的时间复杂度为O(n)。所以如果经常按序号访问数据元素，使用顺序表优于链表。在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此n较大时顺序表的插入和删除效率低。在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作。从这个角度考虑显然链表优于顺序表。总之，两种存储结构各有长短，选择那一种存储结构，由实际问题中的主要因素决定。2.3分析在顺序存储结构下插入和删除结点时平均需要移动多少个结点。【解答】平均移动表中大约一半的结点。插入操作平均移动2n个结点，删除操作平均移动2)1(n个结点。具体移动的次数取决于表长和插入、删除的结点的位置。2.4为什么在单循环链表中常使用尾指针，若只设头指针，插入元素的时间复杂度如何？【解答】单循环链表中无论设置尾指针还是头指针都可以遍历到表中任一个结点。设置尾指针时，若在表尾进行插入元素或删除第一元素，操作可在O(1)时间内完成；若只设置头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为O(n)。2.5在单链表、双链表、单循环链表中，若知道指针p指向某结点，能否删除该结点，时间复杂度如何？【解答：】以上三种链表中，若知道指针p指向某结点，都能删除该结点。双链表删除p所指向的结点的时间复杂度为O(1)，而单链表和单循环链表上删除p所指向的结点的时间复杂度均为O(n)。2.6下面算法的功能是什么？LinkedListUnknown(LinkedListla){LNode*q，*p;if(la&&la-next){q=la;la=la-next;p=la;while(p-next)p=p-next;p-next=q;q-next=null;}returnla;}【解答】将首元结点删除并插入到表尾（设链表长度大于1）。2.7选择题：在循环双链表的*p结点之后插入*s结点的操作是（）A、p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;B、p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;C、s-prior=p;s-next=p-next;p-next:=s;p-next-prior=s;D、s-prior=p;snext=pnext;pnext-prior=s;p-next=s;【解答】D2.8选择题：若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表【解答】A二、算法设计题2.9设ha和hb分别是两个带头结点的非递减有序单链表的头指针，试设计算法，将这两个有序链表合并成一个非递增有序的单链表。要求使用原链表空间，表中无重复数据。【题目分析】因为两链表已按元素值非递减次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针，若遇值相同的元素，则删除之。该问题要求结果链表按元素值非递增次序排列，故在合并的同时，将链表结点逆置。【算法2.9】LinkedListUnion(LinkedListha,hb)∥ha,hb分别是带头结点的两个单链表的头指针，链表中的元素值按非递减有序∥本算法将两链表合并成一个按元素值非递增有序的单链表,并删除重复元素{pa=ha-next;∥pa是链表ha的工作指针pb=hb-next;∥pb是链表hb的工作指针ha-next=null;∥ha作结果链表的头指针，先将结果链表初始化为空while(pa!=null&&pb!=null)∥当两链表均不为空时作{while(pa-next&&pa-data==pa-next-data){u=pa-next;pa-next=u-next;free(u)}∥删除pa链表中的重复元素while(pb-next&&pb-data==pb-next-data){u=pb-next;pb-next=u-next;free(u)}∥删除pb链表中的重复元素if(pa-datapb-data){r=pa-next;∥将pa的后继结点暂存于rpa-next=ha-next;∥将pa结点链于结果表中，同时逆置ha-next=pa;pa=r;∥恢复pa为当前待比较结点}elseif(pb-datapa-data){r=pb-next;∥将pb的后继结点暂存于rpb-next=ha-next;∥将pb结点链于结果表中，同时逆置ha-next=pb;pb=r;∥恢复pb为当前待比较结点}else{u=pb;pb=pb-next;free(u)}∥删除链表pb和pa中的重复元素}//while(pa!=null&&pb!=null)if(pa)pb=pa;∥避免再对pa写下面的while语句while(pb!=null)∥将尚未到尾的表逆置到结果表中{r=pb-next;pb-next=ha-next;ha-next=pb;pb=r;}r