数据结构习题解答

数据结构习题解答第1章绪论一、基本内容数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义；抽象数据类型的定义、表示和实现方法；描述算法的类C语言；算法设计的基本要求以及从时间和空间角度分析算法的方法。二、学习要点1．熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。2．了解抽象数据类型的定义、表示和实现方法。3．熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。4．理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）。5．掌握计算语句频度和估算算法时间复杂度的方法。三、基础知识题1.1简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。答：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示（又称映像）。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。1.2试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。程序设计语言中的数据类型是一个值的集合和定义在这个值集上的一组操作的总称。而抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。1.8设n为正整数，试确定下列各程序段中前置以记号@的语句的频度。（1）i=1;k=0;while(i=n-1){@k+=10*i;i++;}答：n-1（2）i=1;k=0;do{@k+=10*i;i++;}while(i=n-1);答：1111nnn（3）i=1;k=0;while(i=n-1){i++;@k+=10*i;}答：n-1（4）k=0;for(i=1;i=n;i++){for(j=i;j=n;j++)@k++;}答：21nn（5）for(i=1;i=n;i++){for(j=i;j=i;j++)for(k=1;k=j;k++)@x+=delta;}答：621nnn（6）i=1;j=0;while(i+j=n){@if(ij)j++;elsei++;}答：n（7）x=n;y=0;while(x=(y+1)*(y+1)){@y++;}答：n（8）x=91;y=100;while(y0){@if(x100){x-=100;y--;}elsex++;}答：1100四、算法设计题1.16试写一算法，自大至小依次输出顺序读入的三个整数X，Y，Z的值。答：voidprint_descending(intx,inty,intz)//按从大到小顺序输出三个数{scanf(%d,%d,%d,&x,&y,&z);if(xy){temp=x;x=y;y=temp;}if(yz){temp=z;z=y;if(x=temp)y=temp;else{y=x;x=temp;}}printf(%d%d%d,x,y,z);}//print_descending五、附加题5.1填空题1.数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。操作对象，关系2.数据结构被形式地定义为（D,R），其中D是的有限集合，R是D上的有限集合。数据元素，关系3.数据结构包括数据的、数据的和数据的这三个方面的内容。4.数据结构按逻辑结构可分为两大类，它们分别是和。线性结构，非线性结构5.线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。一对一，一对多，多对多6．数据的存储结构可用四种基本的存储方法表示，它们分别是。顺序存储结构，链式存储结构，索引存储结构，散列存储结构7.一个算法的效率可分为效率和效率。时间，空间5.2选择题（）1.线性结构是数据元素之间存在一种：DA．一对多关系B．多对多关系C．多对一关系D．一对一关系（）2.数据结构中，与所使用的计算机无关的是数据的结构。CA．存储B．物理C．逻辑D．物理和存储（）3.算法分析的目的是：CA．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性（）4.计算机算法指的是：CA．计算方法B．排序方法C．解决问题的有限运算序列D．调度方法（）5.计算机算法必须具备输入、输出和等5个特性。BA．可行性、可移植性和可扩充性B．可行性、确定性和有穷性C．确定性、有穷性和稳定性D．易读性、稳定性和安全性第2章线性表一、基本内容线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法；在线性表的两类存储结构（顺序的和链式的）上实现基本操作；稀疏多项式的抽象数据类型定义、表示和加法的实现。二、学习要点1．了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。2．熟练掌握这两类存储结构的描述方法，如一维数据中一个区域[i..j]的上、下界和长度之间的变换公式（L=j-i+1,i=j-L+1,j=i+L-1）,链表中指针P和结点*p的对应关系（结点*(p-next)是结点*p的后继等），链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。链表是本章的重点和难点。扎实的指针操作和内在动态分配的编程技术是学好本章的基本要求。3．熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。4．熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。了解静态链表，能够加深对链表本质的理解。5．能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。三、基础知识题2.1描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是当对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。这3个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。2.2填空题1.在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。答：表中一半，表长和该元素在表中的位置2.顺序表中逻辑上相邻的元素的物理位置相邻。单链表中逻辑上相邻的元素的物理位置相邻。答：必定，不一定3.在单链表中，除了首元结点外，任一结点的存储位置由指示。其前驱结点的链域的值4．在单链表中设置头结点的作用是。插入和删除首元素时不必进行特殊处理2.6已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.在P结点后插入S结点的语句序列是。4，1b.在P结点前插入S结点的语句序列是。7，11，8，4，1c.在表首插入S结点的语句序列是。5，12d.在表尾插入S结点的语句序列是。9，1，6（1）P-next=S;（2）P-next=P-next-next;（3）P-next=S-next;（4）S-next=P-next;（5）S-next=L;（6）S-next=NULL;（7）Q=P;（8）while(p-next!=Q)P=P-next;（9）while(P-next!=NULL)P=P-next;（10）P=Q;（11）P=L;（12）L=S;（13）L=p;2.7已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。a.删除P结点的直接后继结点的语句序列是。11，3，14b.删除P结点的直接前驱结点的语句序列是。10，12，8，11，3，14c.删除P结点的语句序列是。10，12，7，3，14d.删除首元结点的语句序列是。12，11，3，14e.删除尾元结点的语句序列是。9，11，3，14（1）P=P-next;（2）P-next=P;（3）P-next=P-next-next;（4）P=P-next-next;（5）while(P!=NULL)P=P-next;（6）while(Q-next!=NULL){P=Q;Q=Q-next;}（7）while(P-next!=Q)P=P-next;（8）while(p-next-next!=Q)P=P-next;（9）while(P-next-next!=NULL)P=P-next;（10）Q=P;（11）Q=P-next;（12）P=L;（13）L=L-next;（14）free(Q);2.8已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。a.在P结点后插入S结点的语句序列是。7，12，3，6b.在P结点前插入S结点的语句序列是。8，13，5，4c.删除P结点的直接后继结构的语句序列是。15，1，11，18d.删除P结点的直接前驱结点的语句序列是。16，2，10，18e.删除P结点的语句序列是。9，14，17（1）P-next=P-next-next;（2）P-priou=P-priou-priou;（3）P-next=S;（4）P-priou=S;（5）S-next=P;（6）S-priou=P;（7）S-next=P-next;（8）S-priou=P-priou;（9）P-priou-next=P-next;（10）P-priou-next=P;（11）P-next-priou=P;（12）P-next-priou=S;（13）P-priou-next=S;（14）P-next-priou=p-priou;（15）Q=P-next;（16）Q=P-priou;（17）free(P);（18）free(Q);2.7简述以下算法的功能。（1）StatusA(LinkedListL){//L是无表头结点的单链表if(L&&L-next){Q=L;L=L-next;P=L;While(P-next)P=P-next;P-next=Q;Q-next=NULL;}returnOK;}//A答：如果L的长度不小于2，则将首元结点删去并插入到表尾。（2）voidBB(LNode*s,LNode*q){p=s;while(p-next!=q)p=p-next;p-next=s;]//BBvoidAA(LNode*pa,LNode*pb){//pa和pb分别指向单循环链表中的两个结点BB(pa,pb);BB(pb,pa);}//AA答：将s至q之前的结点组成一个新的单循环链表，将q断开。四、算法设计题2.11设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。答：StatusInsert_SqList(SqList&va,intx)//把x插入递增有序表va中{if(va.length+1va.listsize)returnERROR;va