数据结构章习题课答案PPT学习教案

1、会计学1 数据结构章习题课答案数据结构章习题课答案 2 一、填空题一、填空题 1.数据的逻辑结构被分为数据的逻辑结构被分为 、 、 和和 4 种种. 2.数据的存储结构被分为数据的存储结构被分为 、 2种种. 3.在线性结构、树形结构和图形结构中，直接前驱和在线性结构、树形结构和图形结构中，直接前驱和 直接后继结点之间分别存在着直接后继结点之间分别存在着 、 和和 的联系。的联系。 4. 一个算法应具有一个算法应具有 、 、 输输 入和输出特性入和输出特性. 5. 一个算法的效率主要由一个算法的效率主要由 和和 来度量来度量 。 6. 抽象数据类型包括抽象数据类型包括_和和_。 第1页/共25

2、页 3 7.在顺序表中插入一个元素，需要平均移动在顺序表中插入一个元素，需要平均移动 元素，具体移动的元素个数与元素，具体移动的元素个数与 有关。有关。 8. 在顺序表中逻辑上相邻的元素的物理位置在顺序表中逻辑上相邻的元素的物理位置 紧邻紧邻 。 单链表中逻辑上相邻的元素的物理位置单链表中逻辑上相邻的元素的物理位置 紧邻。紧邻。 9. 在单链表中，除了首元结点外，任一结点的存储位在单链表中，除了首元结点外，任一结点的存储位 置由置由 指示。指示。 10. 在单链表中设置头结点的作用是在单链表中设置头结点的作用是 。 第2页/共25页 4 14. 从一维数组从一维数组An中顺序找出一个最大值元素

3、的时间复杂中顺序找出一个最大值元素的时间复杂 度度 为为 ,输出一个二维数组输出一个二维数组Bmn中所有元素值的时中所有元素值的时 间复杂度为间复杂度为 . 15. 在下面的程序中，在下面的程序中，s=s+p语句的执行次数为语句的执行次数为 , p*=j语句的执行次数为语句的执行次数为 , 该程序段的时间复杂度为该程序段的时间复杂度为 . int i=0; s=0; while(+i=n) int p=1; for(int j=1; j=i; j+ ) p*=j; s=s+p; 第3页/共25页 5 第4页/共25页 6 补充题补充题: 按增长率由小到大的顺序排列下列各函数：按增长率由小到大的

4、顺序排列下列各函数： 2100，(3/2)n，(2/3)n，(4/3)n，nn，n2/3， n1/2， ， n!，n，log2n，n/log2n，log22n，log2(log2n)， nlog2n，nlog2n 第5页/共25页 7 补充题答案补充题答案: 答答: :按增长率由小到大的顺序各函数为：按增长率由小到大的顺序各函数为： (2/3)n， 2100， log2(log2n) ， log2n， log22n， n1/2 ， n2/3， n/log2n， n，nlog2n, (4/3)n， (3/2)n， n!， nn nlog n 2 第6页/共25页 8 第7页/共25页 9 四、四

5、、设有一个设有一个10*10的对称矩阵的对称矩阵A1010，采取按行压缩存储的方式存放于一个一维数组，采取按行压缩存储的方式存放于一个一维数组B 中，则数组中，则数组B 的容量应有多大？若设的容量应有多大？若设A00为第一个元素，存放于为第一个元素，存放于B0，且数组，且数组A 的每一个数组元素在数组的每一个数组元素在数组B 中占一个数组元素位置，则中占一个数组元素位置，则A85在数组在数组B 中地址是多少？中地址是多少？ 答案：答案： 数组数组B应有应有55个元素，对于下三角矩阵，个元素，对于下三角矩阵， LOC(A85)=1+8+5=41 对于上三角矩阵，对于上三角矩阵， LOC(A85)

6、= LOC(A58)=10+9+8+7+6+(8-5)=43 第8页/共25页 10 五、五、（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, 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; 第10页

7、/共25页 12 (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); 第11页/共25页 13 数据结构数据结构: 所研究内容的着重点主要体现在三个方面：所研究内容的着重点主要体现在三个方面： 第一是数据间的逻辑关系，即数据元素之间的关系。第一是数据间的逻辑关系，即数据元素之间的关系。 第二是

8、数据的存储关系，即数据在计算机中的存储结构。第二是数据的存储关系，即数据在计算机中的存储结构。 第三是算法，即定义在逻辑关系上的一组操作。第三是算法，即定义在逻辑关系上的一组操作。 因此，简单说来，数据结构所研究的问题是如何将现实世界中的事物合理描述为计算机世界中所研究的对象，并根据研究对象的特点，分析对象之间的关系、存储结构和操作的学科。因此，简单说来，数据结构所研究的问题是如何将现实世界中的事物合理描述为计算机世界中所研究的对象，并根据研究对象的特点，分析对象之间的关系、存储结构和操作的学科。 1.试说明基本数据类型、数据结构和抽象数据类型的联系与差异。试说明基本数据类型、数据结构和抽象数

9、据类型的联系与差异。 基本数据类型（基本数据类型（Data Type）：）： 在程序设计高级语言中，数据类型用来说明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。高级语言中都有基本数据类型。例如在在程序设计高级语言中，数据类型用来说明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。高级语言中都有基本数据类型。例如在C、C+和和Java语言中，有基本类型语言中，有基本类型int（整型）、（整型）、float（浮点型）和（浮点型）和char（字符型），有构造类型数组、结构、联合、指针、枚举型和自定义等。（字符型），有构造类型数组、结

10、构、联合、指针、枚举型和自定义等。数据类型仅局限于计算机中定义并实现了的数据类型数据类型仅局限于计算机中定义并实现了的数据类型; 第12页/共25页 14 抽象数据类型：抽象数据类型： 是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于抽象数据类型的逻辑特性，与它在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要数学特性不变，都不影响抽象数据类型外部的使用。是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于抽象数据类型的逻辑特性，与它在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要数学特性不变，都不影响抽象数据类型外部的使用

11、。 抽象数据类型除了计算机中定义并实现了的数据类型；还包括用户在设计软件系统时自己定义的数据类型。抽象数据类型除了计算机中定义并实现了的数据类型；还包括用户在设计软件系统时自己定义的数据类型。 第13页/共25页 15 1-5 试说明数据的逻辑结构、存储结构和算法三者之间的关系试说明数据的逻辑结构、存储结构和算法三者之间的关系。 1个数据逻辑结构可有多种不同的存储结构；存储结构是对逻辑结构实现；算法是基于逻辑结构对操作的实现；函数是基于存储结构对算法的实现，是程序；个数据逻辑结构可有多种不同的存储结构；存储结构是对逻辑结构实现；算法是基于逻辑结构对操作的实现；函数是基于存储结构对算法的实现，是

12、程序； 答：数据的逻辑结构、存储结构和算法是数据结构所讨论的三个答：数据的逻辑结构、存储结构和算法是数据结构所讨论的三个 方面。方面。 第14页/共25页 16 1-6 请给出下列函数的大请给出下列函数的大O和和表示：表示： nnn nn nnnn nnnn 5log ,log ,2log ,2100 2 2 5 . 1 2 O(n1/2logn) O(n) O(n1.5) O(n1/2) 第15页/共25页 17 2-1描述以下三个概念的区别：头指针、头结点、描述以下三个概念的区别：头指针、头结点、 首结点（第一个元素结点）。在单链表中设置头结点首结点（第一个元素结点）。在单链表中设置头结点

13、 的作用是什么？的作用是什么？ 答：首结点就是存放数据元素的第一个元素结点，头答：首结点就是存放数据元素的第一个元素结点，头 结点是为了插入和删除的方便说增设的一个结点，头结点是为了插入和删除的方便说增设的一个结点，头 指针是指向链表中第一个结点的存储位置，在没有头指针是指向链表中第一个结点的存储位置，在没有头 结点的链表中，头指针指向链表中的首结点，在有头结点的链表中，头指针指向链表中的首结点，在有头 结点的链表中，头指针指向链表中的头结点。结点的链表中，头指针指向链表中的头结点。 习习 题题 2（p55） 第16页/共25页 18 2-4 已知二维数组已知二维数组Am,m采用按行优先顺序存

14、采用按行优先顺序存 放，每个元素占放，每个元素占K个存储单元，并且第一个元素的存储个存储单元，并且第一个元素的存储 地址为地址为Loc(a00)，请写出求，请写出求Loc(aij)的计算公式。如果采的计算公式。如果采 用列优先顺序存放呢？用列优先顺序存放呢？ 答：行优先顺序存放时答：行优先顺序存放时: Loc(aij)= Loc(a00) +(i*m+j)*K 列优先顺序存放时列优先顺序存放时: Loc(aij)= Loc(a00) +(j*m+i)*K 第17页/共25页 19 2-5 在链表类的实现中增加一个成员函数实现对表中元素置逆的操作（设原链表为在链表类的实现中增加一个成员函数实现对

15、表中元素置逆的操作（设原链表为 a0, a1, , an-2, an-1；则置逆后的序列为；则置逆后的序列为 an-1, an-2, ,a1, a0）。对于有）。对于有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; 第18页/共25页 20 2-10 设计一个算法，将数

16、组设计一个算法，将数组A(0.n-1)中的元素循环右中的元素循环右 移移k位，假设原数组序列为位，假设原数组序列为a0, a1, , an-2, an-1；移动后；移动后 的序列为的序列为 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; 第19页/共25页 21 补充题补充题 1. 数组置逆数组置逆 void i

17、nverse(DataType A , int n) for(i=0;in/2;i+) temp=Ai; Ai=An-1-i; An-1-i=temp; 第20页/共25页 22 2: 求鞍点求鞍点:二维数组中行最小二维数组中行最小,列最大的元素列最大的元素 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 else h+; if (tag) couti“ ”j“ ”rowendl; 第21页/共25页 23 练习题：练习题： 3. 设数组设数组An中有多个零元素，是写一函数，将中有多个零元素，是写一函数，将A中中 所有非零元素依次移动数组所有非零元素依次移动数组A的前端。的前端。 4. 设计一个算法，找单链表中值最大的结点。设计一个算法，找单链表中值最大的结点。 第22页/共25页 24 3：设数组：设数组An中有多个零元素，是写一函数，将中有多个零元素，是写一函数，将A 中所有非零元素依次移动数组中所有非零元素依次移动数组A的前端。的前端。 void compact(int A，int n) k=0; fo