《数据结构1-2章习题课答案.ppt》由会员分享，可在线阅读，更多相关《数据结构1-2章习题课答案.ppt（25页珍藏版）》请在金锄头文库上搜索。
1、习习 题题 课课（12章）章）1一、填空题一、填空题1.数据的逻辑结构被分为数据的逻辑结构被分为 、 、 和和 4种种.2.数据的存储结构被分为数据的存储结构被分为 、 2种种.3.在线性结构、树形结构和图形结构中，直接前驱和在线性结构、树形结构和图形结构中，直接前驱和4. 直接后继结点之间分别存在着直接后继结点之间分别存在着 、 和和 5. 的联系。的联系。 6.4. 一个算法应具有一个算法应具有 、 、 输输7. 入和输出特性入和输出特性. 5. 一个算法的效率主要由一个算法的效率主要由 和和 来度量。来度量。6. 抽象数据类型包括抽象数据类型包括_和和_。 27.在顺序表中插入一个元素，
2、需要平均移动在顺序表中插入一个元素，需要平均移动 8. 元素，具体移动的元素个数与元素，具体移动的元素个数与 有关。有关。8. 在顺序表中逻辑上相邻的元素的物理位置在顺序表中逻辑上相邻的元素的物理位置 紧邻。紧邻。 单链表中逻辑上相邻的元素的物理位置单链表中逻辑上相邻的元素的物理位置 紧邻。紧邻。9. 在单链表中，除了首元结点外，任一结点的存储位在单链表中，除了首元结点外，任一结点的存储位 置由置由 指示。指示。10. 在单链表中设置头结点的作用是在单链表中设置头结点的作用是 。 314.从一维从一维数组数组An中中顺序找出一个最大值元素的时间复杂度顺序找出一个最大值元素的时间复杂度15. 为
3、为 ,输出一个二维数组输出一个二维数组Bmn中所有元素值中所有元素值的时的时16. 间复杂度为间复杂度为 . 15. 在下面的程序中，在下面的程序中，s=s+p语句的执行次数为语句的执行次数为 , p*=j语句的执行次数为语句的执行次数为 , 该程序段的时间复杂度为该程序段的时间复杂度为 . int i=0; s=0; while(+i=n) int p=1; for(int j=1; jnext=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
4、; (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;8四、四、设有一个设有一个10*10的对称矩阵的对称矩阵A1010，采取按行压缩存采取按行压缩存储的方式存放于一个一维数组储的方式存放于一个一维数组B 中，则数组中，则数组B 的容量应有的容量应有多大？若设多大？若设A00为第一个元素，存放于为第一个元素，存放于B0，且数组且数组A 的每一个数组元素在数组的每一个数组元素在数组B 中占一个数组元素位置，则中占一个数组元素位置，则A85在数组
5、在数组B 中地址是多少？中地址是多少？答案：答案： 数组数组B应有应有55个元素，对于下三角矩阵，个元素，对于下三角矩阵， LOC(A85)=1+8+5=41 对于上三角矩阵，对于上三角矩阵， LOC(A85)= LOC(A58)=10+9+8+7+6+(8-5)=439五、五、（1）画出执行下列各行语句后各指针及链表的示意图。）画出执行下列各行语句后各指针及链表的示意图。 Node *L=new Node( ); P=L; for(i=1; inext=Q; P=P-next; P-data=2*i-1; P-next=NULL; for(i=4; i=1; i-) Insert(2*i,
6、i+1); for(i=1; inext) Q=L; L=L-next; P=L; while(P-next) P=P-next; P-next=Q; Q-next=NULL; 11(2) void BB(ListNode *s; ListNode *q) p=s; while(p-next!=q) p-p-next; p-next=s; void AA (ListNode *pa; ListNode *pb) BB(pa,pb); /pa和和pb分别指向单循环链表中的两个结点。分别指向单循环链表中的两个结点。 BB(pb,pa); 12数据结构数据结构: 所研究内容的着重点主要体现在三个方面
7、：所研究内容的着重点主要体现在三个方面：第一是数据间的逻辑关系，即数据元素之间的关系。第一是数据间的逻辑关系，即数据元素之间的关系。第二是数据的存储关系，即数据在计算机中的存储结构。第二是数据的存储关系，即数据在计算机中的存储结构。第三是算法，即定义在逻辑关系上的一组操作。第三是算法，即定义在逻辑关系上的一组操作。因此，简单说来，数据结构所研究的问题是如何将现实世界中的事因此，简单说来，数据结构所研究的问题是如何将现实世界中的事物合理描述为计算机世界中所研究的对象，并根据研究对象的特点，物合理描述为计算机世界中所研究的对象，并根据研究对象的特点，分析对象之间的关系、存储结构和操作的学科。分析对
8、象之间的关系、存储结构和操作的学科。1.试说明基本数据类型、数据结构和抽象数据类型的联系与差异。试说明基本数据类型、数据结构和抽象数据类型的联系与差异。基本数据类型（基本数据类型（Data Type）：）： 在程序设计高级语言中，数据类型用来说明一个数据在数据在程序设计高级语言中，数据类型用来说明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。高级语言中都有基本数据类型。例如在变化范围。高级语言中都有基本数据类型。例如在C、C+和和Java语言中，有基本类型语言中，有基本类型int（整型）、（整型）、flo
9、at（浮点型）和（浮点型）和char（字符型），有构造类型数组、结构、联合、指针、枚举型和自（字符型），有构造类型数组、结构、联合、指针、枚举型和自定义等。定义等。数据类型仅局限于计算机中定义并实现了的数据类型数据类型仅局限于计算机中定义并实现了的数据类型;13抽象数据类型：抽象数据类型： 是指一个数学模型以及定义在该模型上的一组操作。抽象数是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于抽象数据类型的逻辑特性，与它在计算机据类型的定义仅取决于抽象数据类型的逻辑特性，与它在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要数内部如何表示和实现无关。即不论其内部
10、结构如何变化，只要数学特性不变，都不影响抽象数据类型外部的使用。学特性不变，都不影响抽象数据类型外部的使用。抽象数据类型除了计算机中定义并实现了的数据类型；还包括用抽象数据类型除了计算机中定义并实现了的数据类型；还包括用户在设计软件系统时自己定义的数据类型。户在设计软件系统时自己定义的数据类型。141-5 试说明数据的逻辑结构、存储结构和算法三者之间的关系试说明数据的逻辑结构、存储结构和算法三者之间的关系。 1个数据逻辑结构可有多种不同的存储结构；存储结构是对个数据逻辑结构可有多种不同的存储结构；存储结构是对逻辑结构实现；算法是基于逻辑结构对操作的实现；函数是逻辑结构实现；算法是基于逻辑结构对
11、操作的实现；函数是基于存储结构对算法的实现，是程序；基于存储结构对算法的实现，是程序；答：数据的逻辑结构、存储结构和算法是数据结构所讨论的三个答：数据的逻辑结构、存储结构和算法是数据结构所讨论的三个 方面。方面。151-6 请给出下列函数的大请给出下列函数的大O和和表示：表示：O(n1/2logn)O(n) O(n1.5)O(n1/2)162-1描述以下三个概念的区别：头指针、头结点、首描述以下三个概念的区别：头指针、头结点、首结点（第一个元素结点）。在单链表中设置头结点的结点（第一个元素结点）。在单链表中设置头结点的作用是什么？作用是什么？答：首结点就是存放数据元素的第一个元素结点，头答：首
12、结点就是存放数据元素的第一个元素结点，头结点是为了插入和删除的方便说增设的一个结点，头结点是为了插入和删除的方便说增设的一个结点，头指针是指向链表中第一个结点的存储位置，在没有头指针是指向链表中第一个结点的存储位置，在没有头结点的链表中，头指针指向链表中的首结点，在有头结点的链表中，头指针指向链表中的首结点，在有头结点的链表中，头指针指向链表中的头结点。结点的链表中，头指针指向链表中的头结点。习习 题题 2（p55）172-4 已知二维数组已知二维数组Am,m采用按行优先顺序存放，采用按行优先顺序存放，每个元素占每个元素占K个存储单元，并且第一个元素的存储地址个存储单元，并且第一个元素的存储地
13、址为为Loc(a00)，请写出求，请写出求Loc(aij)的计算公式。如果采用列的计算公式。如果采用列优先顺序存放呢？优先顺序存放呢？ 答：行优先顺序存放时答：行优先顺序存放时: Loc(aij)= Loc(a00) +(i*m+j)*K 列优先顺序存放时列优先顺序存放时: Loc(aij)= Loc(a00) +(j*m+i)*K182-5 在链表类的实现中增加一个成员函数实现对表中元素置逆在链表类的实现中增加一个成员函数实现对表中元素置逆的操作（设原链表为的操作（设原链表为 a0, a1, , an-2, an-1；则置逆后的序列为；则置逆后的序列为 an-1, an-2, ,a1, a0
14、）。对于有）。对于有n个元素的线性表，你的算法的个元素的线性表，你的算法的运行时间应为运行时间应为O(n)。 void LinkList: Inverse( ) if (head-next=NULL) return; p=head-next; head-next=NULL; while(p!=NULL) q=p-next; p-next=head-next; head-next=p; p=q; 192-10 设计一个算法，将数组设计一个算法，将数组A(0.n-1)中的元素循环右中的元素循环右移移k位，假设原数组序列为位，假设原数组序列为a0, a1, , an-2, an-1；移动；移动后的序
15、列为后的序列为 an-k, an-k+1, , a0, a1, , an-k-1。要求只。要求只用一个元素大小的附加存储，元素移动或交换次数为用一个元素大小的附加存储，元素移动或交换次数为O(n)。 void youyi (int a,int n,int k) int b; for(int i=0;i=0;j-) aj+1=aj; a0=b; 20补充题补充题1. 数组置逆数组置逆 void inverse(DataType A , int n) for(i=0;in/2;i+) temp=Ai; Ai=An-1-i; An-1-i=temp; 212: 求鞍点求鞍点:二维数组中行最小二维数组
16、中行最小,列最大的元素列最大的元素 void minmax(int A , int m, int n) for(i=0; im; i+) row=Ai0; k=0; for(j=1; jn; j+) if(Aijrow) k=j; row=Aij; tag=1; h=0; while(tag & hrow) tag=0; else h+; if (tag) couti“ ”j“ ”rowendl; 22练习题：练习题：3. 设数组设数组An中有多个零元素，是写一函数，将中有多个零元素，是写一函数，将A中中 所有非零元素依次移动数组所有非零元素依次移动数组A的前端。的前端。 4. 设计一个算法，
17、找单链表中值最大的结点。设计一个算法，找单链表中值最大的结点。233：设数组：设数组An中有多个零元素，是写一函数，将中有多个零元素，是写一函数，将A中中所有非零元素依次移动数组所有非零元素依次移动数组A的前端。的前端。 void compact(int A，int n) k=0; for(i=0; in; i+) if (Ai!=0) if(i!=k) Ak= Ai; k+; for(i=k; in; i+) Ai=0; 24 int Max(List head ) if(!head-next) return -1; maxvalue=-9999; p=head-next; while(p) if(p-datamaxvalue) maxvalue=p-data; p=p-next; return maxvalue; 4. 设计一个算法，找单链表中值最大的结点。设计一个算法，找单链表中值最大的结点。25
