南开大学20秋《数据结构》在线作业-2(参考答案)

《数据结构》课后习题答案(第2版)数据结构课后习题答案（第2版）第一章：基本概念1. 什么是数据结构？数据结构是指数据元素之间的关系，以及相应的操作。

它研究如何组织、存储和管理数据，以及如何进行高效的数据操作。

2. 数据结构的分类有哪些？数据结构可以分为线性结构和非线性结构。

线性结构包括数组、链表、栈和队列；非线性结构包括树和图。

3. 什么是算法？算法是解决特定问题的一系列有序步骤。

它描述了如何输入数据、处理数据，并产生期望的输出结果。

4. 算法的特性有哪些？算法具有确定性、有限性、输入、输出和可行性这五个特性。

5. 数据结构和算法之间的关系是什么？数据结构是算法的基础，算法操作的对象是数据结构。

第二章：线性表1. 顺序表的两种实现方式是什么？顺序表可以通过静态分配或动态分配的方式实现。

静态分配使用数组，动态分配使用指针和动态内存分配。

2. 单链表的特点是什么？单链表由节点组成，每个节点包含数据和一个指向下一个节点的指针。

它的插入和删除操作效率高，但是查找效率较低。

3. 循环链表和双向链表分别是什么？循环链表是一种特殊的单链表，在尾节点的指针指向头节点。

双向链表每个节点都有一个指向前一个节点和后一个节点的指针。

4. 链表和顺序表的区别是什么？链表的插入和删除操作效率更高，但是查找操作效率较低；顺序表的插入和删除操作效率较低，但是查找操作效率较高。

第三章：栈和队列1. 栈是什么？栈是一种特殊的线性表，只能在表的一端进行插入和删除操作。

后进先出（LIFO）是栈的特点。

2. 队列是什么？队列是一种特殊的线性表，只能在表的一端进行插入操作，在另一端进行删除操作。

先进先出（FIFO）是队列的特点。

3. 栈和队列的应用有哪些？栈和队列在计算机科学中有广泛的应用，例如浏览器的前进后退功能使用了栈，操作系统的进程调度使用了队列。

4. 栈和队列有哪些实现方式？栈和队列可以使用数组或链表来实现，还有更为复杂的如双端队列和优先队列。

数据结构习题二答案问题一：链表的基本操作链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。

链表的基本操作包括：1. 创建节点：定义一个节点类，包含数据域和指向下一个节点的指针域。

2. 插入操作：在链表的指定位置插入一个新的节点。

3. 删除操作：删除链表中的指定节点。

4. 遍历操作：从头节点开始，依次访问链表中的每个节点。

问题二：二叉树的遍历二叉树是一种特殊的树形数据结构，其中每个节点最多有两个子节点。

二叉树的遍历方式有：1. 前序遍历：首先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。

2. 中序遍历：首先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。

3. 后序遍历：首先递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。

问题三：图的表示图是一种复杂的非线性数据结构，由顶点和边组成。

图的表示方法有：1. 邻接矩阵：使用一个二维数组来表示图，其中矩阵的元素表示两个顶点之间的边是否存在。

2. 邻接表：使用链表来表示每个顶点的邻接顶点。

问题四：排序算法排序算法是将一组数据按照特定顺序重新排列的过程。

常见的排序算法包括：1. 冒泡排序：通过重复遍历待排序的数列，比较每对相邻元素的大小，并在必要时交换它们的位置。

2. 选择排序：从未排序序列中找到最小（或最大）的元素，存放到排序序列的起始位置，然后从剩余未排序元素中继续寻找最小（或最大）元素，以此类推。

3. 快速排序：选择一个元素作为“基准”，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再递归地对这两部分数据分别进行快速排序。

总结数据结构习题二涵盖了链表、二叉树、图和排序算法等基本概念和操作。

掌握这些基础知识对于深入理解计算机科学和进行高效的程序设计至关重要。

希望以上答案能够帮助你更好地理解和应用这些概念。

请注意，这只是一个示例答案，具体的习题答案需要根据实际的习题内容来编写。

数据结构第2章习题参考答案1. 简答题1.1 什么是数据结构？数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，它包括数据的逻辑结构和物理结构。

1.2 数据结构的分类有哪些？数据结构可以分为线性结构和非线性结构。

线性结构包括线性表、栈、队列和串；非线性结构包括树和图。

1.3 数据结构的逻辑结构有哪些？数据结构的逻辑结构包括线性结构、树形结构和图形结构。

1.4 数据结构的物理结构有哪些？数据结构的物理结构包括顺序存储结构和链式存储结构。

1.5 什么是算法？算法是指求解问题的具体步骤和方法。

1.6 算法的特性有哪些？算法应具有有穷性、确定性、可行性和输入输出性。

2. 选择题2.1 在栈的顺序存储结构中，栈的存储位置是：A. 自顶向下递增B. 自底向上递增C. 自底向上递减D. 自顶向下递减答案：D2.2 下列哪个数据结构不适合表示有父子关系的数据？A. 二叉树B. 图C. 链表D. 堆答案：D2.3 对于一棵完全二叉树，叶子节点的个数为n，则树中节点的总数为：A. 2nB. 2n + 1C. nD. n + 1答案：A2.4 假设有一个长度为10的栈，初始时栈为空，若对该栈连续执行5次入栈操作，然后执行4次出栈操作，最后执行1次入栈操作，则栈中剩余的元素个数为：A. 0B. 1C. 4D. 6答案：D3. 编程题3.1 实现一个栈数据结构的基本操作，包括入栈、出栈、获取栈顶元素和判断栈是否为空。

```Pythonclass Stack:def __init__(self):self.items = []def is_empty(self):return len(self.items) == 0def push(self, item):self.items.append(item)def pop(self):if self.is_empty():return Nonereturn self.items.pop()def peek(self):if self.is_empty():return Nonereturn self.items[-1]```3.2 实现一个队列数据结构的基本操作，包括入队、出队、获取队首元素和判断队列是否为空。

1.在关于报表数据源设置的叙述中，以下正确的是()。

A.可以是任意对象B.只能是表对象C.只能是查询对象D.可以是表对象或查询对象答案：D2.以下变量名中合法的是()。

A.avg_sumB.y+2C.100abcdD.print答案：A3.在Access中表与数据库的关系是()。

A.一个数据库可以包含多个表B.一个表只能包含两个数据库C.一个表可以包含多个数据库D.数据库就是数据表答案：A4.工资表结构：工资(职工号C，基本工资N，工龄工资N，实发工资N)。

现将所有职工的基本工资提高10%; 工龄工资提高5%，按照有关工资的变动，重新计算实发工资字段值，下面命令正确的是()。

A.Update 工资 set 实发工资=基本工资*1.1+工龄工资*1.05B.Update 工资 set 实发工资=基本工资+工龄工资，基本工资=基本工资*1.1，工龄工资=工龄工资*1.05C.Update 工资 set 基本工资=基本工资*1.1，工龄工资=工龄工资*1.05，实发工资=基本工资*1.1+工龄工资*1.05D.Update 工资 set 基本工资=基本工资*1.1，工龄工资=工龄工资*1.05，实发工资=基本工资+工龄工资答案：C5.SelectCase语句中，表达式是下面四种形式，不正确的是()。

A.表达式，例如“a”B.一组用逗号分隔的枚举值，例如“a”，“b”C.表达式1 to 表达式2，例如1 to 10D.关系运算符表达式，例如=60答案：D6.执行以下两条命令后，输出结果是()。

BOOKS=“南开大学图书管理系统” LEN(MID(BOOKS，5))A.16B.6C.12D.语法错误答案：B7.VBA代码调试过程中，能够动态了解变量和表达式变化情况的是()。

A.监视窗口B.本地窗口C.立即窗口D.快速监视窗口答案：A8.SQL查询语句中，用来实现数据列选取的短语是()。

A.WhereB.FromC.SelectD.GroupBy答案：C9.以下SQL语句和其他三条执行结果不一样的是()。

1.在Excel中“∑”按钮的意思是()。

A.自动求和B.自动求差C.自动求积D.自动求商答案：A2.密码学中，将明文转换成密文的过程是()。

A.加密B.解密C.还原D.破解答案：A3.程序和进程的说法正确的是()。

A.程序是动态的，进程是静态的B.程序是运行着的进程C.程序运行时会产生相应的进程，因此进程是动态的D.一个程序只能对应一个进程答案：C4.假设学生表中有一个出生日期字段，SQL查询1995年出生的学生的条件是()。

A.Between #1995-01-01# And #1995-12-31#B.Between “1995-01-01” And “1995-12-31”C.Between “1995.01.01” And “1995.12.31”D.#1995-01-01# And #1995-12-31#答案：A5.关于在Word中设置文字的项目符号与编号，以下描述正确的是()。

A.项目符号与编号以字为单位添加B.项目符号与编号以行为单位添加C.项目符号与编号以段落单位添加D.项目符号与编号的设置，只能先录入文字后再添加答案：C6.自动化生产过程属于计算机的哪种应用?()A.数据处理B.过程控制C.辅助系统D.科学计算答案：B7.在计算机中，正在执行的程序的指令主要存放在()中。

A.CPUB.磁盘C.内存D.键盘答案：A8.Excel中，当前工作表是指()。

A.有数据的工作表B.有公式计算的工作表C.被选中激活的工作表D.有图表的工作表答案：C9.要存放10个16×16点阵的汉字字模，需要()存储空间。

A.72BB.320BC.720BD.72KB答案：B10.OSI开放系统互联参考模型把整个网络划分为()个层次。

A.4B.5C.6D.7答案：D11.Access中的文本字段默认大小是()个字符。

A.24B.32C.64D.255答案：D12.若要将计算机与局域网连接，至少需要具有的硬件是()。

第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

存储结构：数据对象在计算机中的存储表示，也称为物理结构。

抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。

具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。

每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。

单元练习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 的函数。

1.Linux支持48位最大寻址空间是()[答案：D]A.32TBB.64TBC.128TBD.256TB2.在关于逆向工程(reverse engineering)的描述中，正确的是： ( )[答案：A]A.从已经安装的软件中提取设计规范，用以进行软件开发B.按照“输出→处理→输入”的顺序设计软件C.用硬件来实现软件的功能D.根据软件处理的对象来选择开发语言和开发工具3.IDA分析数据时，数据类型可以在()之间转换。

[答案：B]A.db、dw、dfB.db、dw、ddC.db、dd、dfD.dw、dd、df4.基址重定位数据采用类似按页分割的方法组织，是由许多重定位块串接成的，每个块中存放()KB的重定位信息[答案：C]A.1B.2C.4D.85.计算机体系结构中，()层是由十六进制形式的操作码组成，用于告诉处理器你想它干什么。

[答案：B]B.机器码C.低级语言D.高级语言6.在大端字节序中0.127.1.0，对应的正整数16进制表示为() [答案：D]A.0x7F000001B.0x01000007FC.0x000017F00D.0x007F01007.终止一个正在运行的进程的命令对应的快捷键是()。

[答案：D]A.F7B.F4C.Ctrl+F7D.Ctrl+F28.以下先执行语句块，再进行表达式判断的循环语句是()。

[答案：A]A.do循环B.while循环C.for循环D.都不是9.以下动态链接库中哪个是通用控件()[答案：B]A.Advapi32.dllctl32.dlldlg32.dllD.Shell32.dll10.ascii码是一种()A.字符编码B.压缩编码C.传输码D.校验码11.用于判断指定文件的属性的Windows API函数是()[答案：C]A.GetLogicalDriveStrings()B.GetLogicalDrives()C.GetFileAttributes()D.CreateFileA12.紧跟资源目录结构的就是资源目录入口(Resource Dir Entries)结构，此结构长度为()字节，包含2个字段。