南邮陈慧南版数据结构课后习题答案
- 格式:ppt
- 大小:190.00 KB
- 文档页数:33
第1 章绪论1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案:数据:是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数,文本编辑所用到的字符串,多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素:是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。
在有些情况下,数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象,如一个学生记录,树中棋盘的一个格局(状态)、图中的一个顶点等。
数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。
例如,学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象:是性质相同的数据元素的集合,是数据的一个子集。
例如:整数数据对象是集合N={0,±1,±2,… },字母字符数据对象是集合C={‘A’,‘B’,… ,‘Z’,‘a’,‘b’,…,‘z’},学生基本信息表也可是一个数据对象。
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。
逻辑结构:从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。
因此,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构:数据对象在计算机中的存储表示,也称为物理结构。
抽象数据类型:由用户定义的,表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称。
具体包括三部分:数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
2.试举一个数据结构的例子,叙述其逻辑结构和存储结构两方面的含义和相互关系。
答案:例如有一张学生基本信息表,包括学生的学号、姓名、性别、籍贯、专业等。
每个学生基本信息记录对应一个数据元素,学生记录按顺序号排列,形成了学生基本信息记录的线性序列。
第1 章绪论一、基础题1. A2. C3. C4. A5. C二、扩展题1.数据是计算机加工处理的对象;数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理;数据项是组成数据元素的、不可分割的最小单位。
2.数据结构是按某种逻辑关系组织起来的数据元素的集合,使用计算机语言描述并按一定的存储方式存储在计算机中,并在其上定义了一组运算。
3.集合结构、线性结构、树形结构和图形结构。
集合结构中,元素之间没有关系;线性结构中,元素之间存在一对一的关系;树形结构中,元素之间存在一对多的关系,其中最多只有一个元素没有前驱元素,这个元素就是根;图形结构中,元素之间存在多对多的关系。
4.顺序存储、链式存储、索引存储和散列存储。
5.一个算法是对特定问题的求解步骤的一种描述,是指令的有限序列。
其特征包括:➢输入:算法有零个或多个输入➢输出:算法至少产生一个输出➢确定性:算法的每一条指令都有确切的定义,没有二义性。
➢能行性/可行性:可以通过已经实现的基本运算执行有限次来实现➢有穷性:算法必须总能在执行有限步之后终止6.联系:程序是计算机指令的有序集合,是算法用某种程序设计语言的表述,是算法在计算机上的具体实现。
区别:在语言描述上不同,程序必须是用规定的程序设计语言来写,而算法的描述形式包括自然语言、伪代码、流程图和程序语言等;算法所描述的步骤一定是有限的,而程序可以无限地执行下去,比如一个死循环可以称为程序,但不能称为算法。
7.正确性:算法的执行结果应当满足功能需求,无语法错误,无逻辑错误简明性:思路清晰、层次分明、易读易懂,有利于调试维护健壮性:当输入不合法数据时,应能做适当处理,不至于引起严重后果效率:有效使用存储空间和有高的时间效率最优性:解决同一个问题可能有多种算法,应进行比较,选择最佳算法可使用性:用户友好性8(1)执行次数为n-1(n>=2),n=1时执行1次;时间复杂度为O(n)。
(2)执行次数为⌈log3n⌉;时间复杂度为O(logn)(3) 执行次数为n2;时间复杂度为O(n2)(4)执行次数为⌊√n⌋ + 1;时间复杂度为O(√n)第2 章线性表1.A2.D3.B4.C5.B6.D7.D8.C9.A10.D1.编写程序实现对顺序表逆置。
第1章绪论1 •简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案:数据:是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数,文本编辑所用到的字符串,多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素:是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。
在有些情况下,数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象,如一个学生记录,树中棋盘的一个格局(状态)、图中的一个顶点等。
数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。
例如,学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象:是性质相同的数据元素的集合,是数据的一个子集。
例如:整数数据对象是集合N={0,士1,士2,…},字母字符数据对象是集合C={ ‘ A', ‘ B…,‘ Z,‘ a'b ',…,‘ z ' },学生基本信息表也可是一个数据对象。
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。
逻辑结构:从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。
因此,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构:数据对象在计算机中的存储表示,也称为物理结构。
抽象数据类型:由用户定义的,表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称。
具体包括三部分:数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
2 •试举一个数据结构的例子,叙述其逻辑结构和存储结构两方面的含义和相互关系。
答案:例如有一张学生基本信息表,包括学生的学号、姓名、性别、籍贯、专业等。
每个学生基本信息记录对应一个数据元素,学生记录按顺序号排列,形成了学生基本信息记录的线性序列。
数据结构课后习题标准答案————————————————————————————————作者:————————————————————————————————日期:7_1对于图题7.1(P235)的无向图,给出:(1)表示该图的邻接矩阵。
(2)表示该图的邻接表。
(3)图中每个顶点的度。
解:(1)邻接矩阵:0111000100110010010101110111010100100110010001110(2)邻接表:1:2----3----4----NULL;2: 1----4----5----NULL;3: 1----4----6----NULL;4: 1----2----3----5----6----7----NULL;5: 2----4----7----NULL;6: 3----4----7----NULL;7: 4----5----6----NULL;(3)图中每个顶点的度分别为:3,3,3,6,3,3,3。
7_2对于图题7.1的无向图,给出:(1)从顶点1出发,按深度优先搜索法遍历图时所得到的顶点序(2)从顶点1出发,按广度优先法搜索法遍历图时所得到的顶点序列。
(1)DFS法:存储结构:本题采用邻接表作为图的存储结构,邻接表中的各个链表的结点形式由类型L_NODE规定,而各个链表的头指针存放在数组head中。
数组e中的元素e[0],e[1],…..,e[m-1]给出图中的m条边,e中结点形式由类型E_NODE规定。
visit[i]数组用来表示顶点i是否被访问过。
遍历前置visit各元素为0,若顶点i被访问过,则置visit[i]为1.算法分析:首先访问出发顶点v.接着,选择一个与v相邻接且未被访问过的的顶点w访问之,再从w 开始进行深度优先搜索。
每当到达一个其所有相邻接的顶点都被访问过的顶点,就从最后访问的顶点开始,依次退回到尚有邻接顶点未曾访问过的顶点u,并从u开始进行深度优先搜索。
这个过程进行到所有顶点都被访问过,或从任何一个已访问过的顶点出发,再也无法到达未曾访问过的顶点,则搜索过程就结束。
《数据结构》教材课后习题+答案数据结构第一章介绍数据结构是计算机科学中重要的概念,它涉及到组织和存储数据的方法和技术。
数据结构的选择对于算法的效率有着重要的影响。
本教材为读者提供了丰富的课后习题,以帮助读者巩固所学知识并提高解决问题的能力。
下面是一些选定的习题及其答案,供读者参考。
第二章线性表习题一:给定一个顺序表L,编写一个算法,实现将其中元素逆置的功能。
答案一:算法思路:1. 初始化两个指针i和j,分别指向线性表L的首尾两个元素2. 对于L中的每一个元素,通过交换i和j所指向的元素,将元素逆置3. 当i>=j时,停止逆置算法实现:```pythondef reverse_list(L):i, j = 0, len(L)-1while i < j:L[i], L[j] = L[j], L[i]i += 1j -= 1```习题二:给定两个线性表A和B,编写一个算法,将线性表B中的元素按顺序插入到线性表A中。
答案二:算法思路:1. 遍历线性表B中的每一个元素2. 将B中的元素依次插入到A的末尾算法实现:```pythondef merge_lists(A, B):for element in B:A.append(element)```第三章栈和队列习题一:编写一个算法,判断一个表达式中的括号是否匹配。
表达式中的括号包括小括号"()"、中括号"[]"和大括号"{}"。
答案一:算法思路:1. 遍历表达式中的每一个字符2. 当遇到左括号时,将其推入栈中3. 当遇到右括号时,判断栈顶元素是否与其匹配4. 当遇到其他字符时,继续遍历下一个字符5. 最后判断栈是否为空,若为空则表示括号匹配算法实现:```pythondef is_matching(expression):stack = []for char in expression:if char in "([{":stack.append(char)elif char in ")]}":if not stack:return Falseelif (char == ")" and stack[-1] == "(") or (char == "]" and stack[-1] == "[") or (char == "}" and stack[-1] == "{"):stack.pop()else:return Falsereturn not stack```习题二:利用两个栈实现一个队列。
第一章绪论1.(第14页,第(18)题)确定划线语句的执行次数,计算它们的渐近时间复杂度。
(1) i=1; k=0;do {k=k+10*i; i++;} while(i<=n-1)划线语句的执行次数为 n-1(n>=2),n=1时执行1次。
(2)i=1; x=0;do{x++; i=2*i;} while (i<n);划线语句的执行次数为⎡log2n⎤。
(3) for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)for (int k=1;k<=j;k++)x++;划线语句的执行次数为n(n+1)(n+2)/6。
(4)x=n;y=0;while(x>=(y+1)*(y+1)) y++;划线语句的执行次数为⎣√n ⎦。
第二章两种基本的数据结构2-4.Loc(A[i][j][k])=134+(i*n*p+j*p+k)*22-9.第34页习题(2).9void Invert(T elements[], int length){//length数组长度 // elements[]为需要逆序的数组 T e;for (int i=1;i<=length/2;i++){e=elements[i-1];elements[i-1]=elements[length-i];elements[length-i]=e;}}2-12.第34页习题(12)void pInvert(Node* first){Node *p=first,*q;first=NULL;while (p){q=p->Link; p->Link=first;first=p; p=q;}}第三章栈与队列1.第54页习题(1)设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈),问能否得到下列序列。
若能得到,则给出相应的push和pop序列;若不能,则说明理由。
第1章绪论一、基础知识题1.1 简述下列概念数据,数据元素,数据类型,数据结构,逻辑结构,存储结构,算法。
【解答】数据是信息的载体,是描述客观事物的数、字符,以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
数据元素是数据的基本单位。
在不同的条件下,数据元素又可称为元素、结点、顶点、记录等。
数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一种总体描述。
每一种计算机程序设计语言都定义有自己的数据类型。
“数据结构”这一术语有两种含义,一是作为一门课程的名称;二是作为一个科学的概念。
作为科学概念,目前尚无公认定义,一般认为,讨论数据结构要包括三个方面,一是数据的逻辑结构,二是数据的存储结构,三是对数据进行的操作(运算)。
而数据类型是值的集合和操作的集合,可以看作是已实现了的数据结构,后者是前者的一种简化情况。
数据的逻辑结构反映数据元素之间的逻辑关系(即数据元素之间的关联方式或“邻接关系”),数据的存储结构是数据结构在计算机中的表示,包括数据元素的表示及其关系的表示。
数据的运算是对数据定义的一组操作,运算是定义在逻辑结构上的,和存储结构无关,而运算的实现则依赖于存储结构。
数据结构在计算机中的表示称为物理结构,又称存储结构。
是逻辑结构在存储器中的映像,包括数据元素的表示和关系的表示。
逻辑结构与计算机无关。
算法是对特定问题求解步骤的一种描述,是指令的有限序列。
其中每一条指令表示一个或多个操作。
一个算法应该具有下列特性:有穷性、确定性、可行性、输入和输出。
1.2数据的逻辑结构分哪几种,为什么说逻辑结构是数据组织的主要方面?【解答】数据的逻辑结构分为线性结构和非线性结构。
(也可以分为集合、线性结构、树形结构和图形即网状结构)。
逻辑结构是数据组织的某种“本质性”的东西:(1)逻辑结构与数据元素本身的形式、内容无关。
(2)逻辑结构与数据元素的相对位置无关。
(3)逻辑结构与所含数据元素的个数无关。
第1章绪论习题1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
2.试举一个数据结构的例子,叙述其逻辑结构和存储结构两方面的含义和相互关系。
3.简述逻辑结构的四种基本关系并画出它们的关系图。
4.存储结构由哪两种基本的存储方法实现?5.选择题(1)在数据结构中,从逻辑上可以把数据结构分成()。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构(2)与数据元素本身的形式、内容、相对位置、个数无关的是数据的()。
A.存储结构B.存储实现C.逻辑结构D.运算实现(3)通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着()。
A.数据具有同一特点B.不仅数据元素所包含的数据项的个数要相同,而且对应数据项的类型要一致C.每个数据元素都一样D.数据元素所包含的数据项的个数要相等(4)以下说法正确的是()。
A.数据元素是数据的最小单位B.数据项是数据的基本单位C.数据结构是带有结构的各数据项的集合D.一些表面上很不相同的数据可以有相同的逻辑结构(5)以下与数据的存储结构无关的术语是()。
A.顺序队列 B. 链表 C. 有序表 D. 链栈(6)以下数据结构中,()是非线性数据结构A.树B.字符串C.队D.栈6.试分析下面各程序段的时间复杂度。
(1)x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;(2)for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;(3)s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;(4)i=1;while(i<=n)i=i*3;(5)x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;(6)x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;(1)O(1)(2)O(m*n)(3)O(n2)(4)O(log3n)(5)因为x++共执行了n-1+n-2+……+1= n(n-1)/2,所以执行时间为O(n2)(6)O(n)第2章线性表1.选择题(1)一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是()。
单元练习1一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳)(√)(1)数据的逻辑结构与数据元素本身的内容和形式无关。
(√)(2)一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。
(ㄨ)(3)数据元素是数据的最小单位。
(ㄨ)(4)数据的逻辑结构和数据的存储结构是相同的。
(ㄨ)(5)程序和算法原则上没有区别,所以在讨论数据结构时可以通用。
(√)(6)从逻辑关系上讲,数据结构主要分为线性结构和非线性结构两类。
(√)(7)数据的存储结构是数据的逻辑结构的存储映像。
(√)(8)数据的物理结构是指数据在计算机内实际的存储形式。
(ㄨ)(9)数据的逻辑结构是依赖于计算机的。
(√)(10)算法是对解题方法和步骤的描述。
二.填空题(1)数据有逻辑结构和存储结构两种结构。
(2)数据逻辑结构除了集合以外,还包括:线性结构、树形结构和图形结构。
(3)数据结构按逻辑结构可分为两大类,它们是线性结构和非线性结构。
(4)树形结构和图形结构合称为非线性结构。
(5)在树形结构中,除了树根结点以外,其余每个结点只有 1 个前趋结点。
(6)在图形结构中,每个结点的前趋结点数和后续结点数可以任意多个。
(7)数据的存储结构又叫物理结构。
(8)数据的存储结构形式包括:顺序存储、链式存储、索引存储和散列存储。
(9)线性结构中的元素之间存在一对一的关系。
(10)树形结构结构中的元素之间存在一对多的关系,(11)图形结构的元素之间存在多对多的关系。
(12)数据结构主要研究数据的逻辑结构、存储结构和算法(或运算)三个方面的内容。
(13)数据结构被定义为(D,R),其中D是数据的有限集合,R是D上的关系的有限集合。
(14)算法是一个有穷指令的集合。
(15)算法效率的度量可以分为事先估算法和事后统计法。
(16)一个算法的时间复杂性是算法输入规模的函数。
(17)算法的空间复杂度是指该算法所耗费的存储空间,它是该算法求解问题规模n的函数。