数据结构(C语言版)知识点复习资料

1、数据结构审查材料第一，填补空白问题1.数据结构是在研究非数字计算的编程问题上，研究计算机的操作对象和它们之间的关系和运算等的学科。2.数据结构以(D，R)格式定义。其中D是数据元素的有限集合，R是D的有限关系集。3.数据结构包括三个茄子方面：数据的逻辑结构、数据的存储结构和数据运算。4.数据结构可以根据逻辑结构分为线性结构和非线性结构两个茄子主要类别。5.线性结构中的元素之间存在一对一关系，树状结构中的元素之间存在一对多关系，图形结构中的元素之间存在多对多关系。6.线性结构中的第一个节点没有前一个节点，其他每个节点只有一个前一个节点。最后一个节点没有后续节点，其他每个节点只有一个后续节点。7.

2、在树状结构中，根节点没有前一个节点，其他每个节点只有一个前一个节点。叶节点没有后续节点，其馀每个节点的后续节点数可以任意多。8.在图形结构中，每个节点的前一个节点数和后续节点数可以任意多。9.数据的存储结构可以用四种茄子默认存储方法表示：顺序、链、索引和散列。10.数据操作的最常见类型是插入、删除、修改、查找和排序。11.算法的效率可以分为时间效率和空间效率。12.要在顺序表格中插入或删除元素，必须在表格中平均移动元素的一半。移动的元素数与表格中表格的长度和元素的位置相关。13.线性表格中的节点集合是有限的，节点之间的关系是一对一的。14.在n长度向量的I元素(1In 1)之前插入元素时，必须

3、向后移动n-i 1元素。15.从n长度的向量中移除I元素(1In)时，必须向前移动n-i元素。16.顺序表也称为随机访问的数据结构，因为访问顺序表中任何节点的时间复杂性为O(1)。17.顺序表中逻辑相邻元素的物理位置必须相邻。在单链表格中，逻辑相邻元素的物理位置不一定相邻。18.在单个链接表中，除第一个节点外的所有节点的存储位置都直接显示为前一个节点的链域值。19.要从n个节点的单个链接列表中删除已知节点*p，必须查找时间复杂性为O(n)的上一个节点的地址。20.矢量、堆栈和队列是线性结构，可以在矢量中的任意位置插入和删除元素。对于堆栈，只能在堆栈顶部插入和删除元素。对于队列，可以在队列末尾插

4、入元素，然后仅从队列顶部删除元素。21.堆叠是特殊的线性表格，插入和删除作业的一端称为堆叠顶部。不允许插入和删除的端点称为堆栈底部。22.队列是线性表，限制为仅在表的一端执行插入操作，在表的另一端执行删除操作。23.不包含字符(长度为零)的字符串称为空字符串。由一个或多个空格(仅空格字符)组成的字符串称为空字符串。24.子字符串的定位操作称为字符串的模式匹配。匹配的主字符串称为目标字符串，子字符串称为模式。25.假设有二维阵列A68牙齿，每个存储为相邻的6个字节，内存按字节寻址。已知A的起始存储位置(主地址)为1000，阵列A的卷(存储容量)为288B。结束元素A57的第一个字节地址为1282

5、。如果逐行保存，则元素A14的第一个字节地址为(8 4) 6 1000=1072。按列保存时，元素A47的第一个字节地址为(67 4) 6 1000)=1276。26.由三个节点组成的二叉树有5种茄子形式。27.深度为6的整个二叉树具有n1 n2=0 n2=n0-1=31个分支点和26-1=32个叶片。注意：整个二叉树没有度数为1的节点，因此分支节点数是2度节点数。28.一棵完整的二叉树，具有257个深度为9的节点。注：使用log2(n) 1=8.xx 1=929.一棵完全二叉树有700个节点，共350个叶点。a:最快的方法：叶数=n/2=35030.设置包含1000个节点的完整二进制树时，牙

6、齿完整的二进制树只有500个叶节点，499度2的节点，1个节点为左非空子树，0个节点为右非空子树。a:最快的方法：叶数=n/2=500，n2=n0-1=499。此外，最后一个节点的左侧为2i，右侧为空，有一个非空的左侧子树。完整的二叉树的特征决定了左右不能为空，因此右非空子树数=0。31.从不规则线性表中检索数据的最佳方法是顺序祖怀(线性祖怀)。32.定线顺序表格(a1、a2、a3、a256)按从小到大的顺序排列。对于给定值K，以二分法在表中搜索K等元素，如果查找失败，则最多需要搜索8次。安装100个节点以二分法查找时，最大比较次数为7。33.假设在排序的线性表a20中执行半次查找，则将一次查

7、找成功的节点数比较为1。成功比较两次的节点数为2。比较4个成功节点的数量是8。平均祖怀长度为3.7。解决方案：很明显，平均祖怀长度=O (Log2n) 5次(25次)。但是具体几次，按公式做就渡边杏。计算(即(21日志221)/20=4.6次不准确！)。因为这是假设n=2m-1时导出的公式。要用彻底的方法列出来。寻找所有元素的次数=(1 22 43 84 55)=74；Asl=74/20=3.7！34.半祖怀顺序表格(4、6、12、20、28、38、50、70、88、100)；如果在祖怀表格中找到元素20，则表格中的元素28、6、12、35.在各种祖怀方法中，平均祖怀长度与节点数N无关的祖怀方

8、法是散列查找。36.散列存储的基本想法是，关键字值决定数据的存储地址。第二，判断正确(在正确的陈述后检查，相反地打叉)()1。连接列表中的每个节点都恰好包含一个指针。答案：错了。连接列表中的节点可以包含多个指针字段，每个字段可以包含多个指针。例如，双向链接表中的节点可能包含两个指针字段，每个字段可能包含直接向前和直接指向下一个节点的指针。()2 .链接表的物理存储结构与链接表的顺序相同。错，链表的存储结构以无序为特征，链表的示意有序。()3 .链表的删除算法很简单。删除链中的一个节点是因为计算机自动向前移动后续设备。错误，关联列表中的节点不会移动，仅更改指针内容。()4。路线表中的每个节点可以

9、是简单类型，链接表中的每个节点可以是复杂类型。错了。混淆逻辑结构和物理结构，链路表也是线性表！而且，即使是顺序表也可以保存记录型数据。()5。顺序表格结构适用于顺序存取，连结表格适用于随机存取。错了，正好相反。顺序表适合随机访问，链表适合“藤条触角”。()6。顺序存储方法的优点是存储密度高，插入、删除操作效率高。错了，前一半是对的，但后一半是错的，这是连锁储存的好处。顺序存储插入，删除操作效率低下。在表格长度为N的顺序表格中插入和删除资料元素。必须平均移动表长度的一半的数据元素。()7。线性表在物理存储空间中也必须连续。错误，线性表以两种茄子方法存储：顺序存储和链存储。后者不要求连续存档。()

10、8。按顺序保存路线表时，逻辑相邻元素可能不与存储它们的物理位置顺序相邻。错了。定线表格以两种茄子方式储存。储存顺序时，逻辑相邻的元素也与储存的实体位置顺序相邻。()9 .顺序存储方法只能用于存储线性结构。错了。顺序存储方法不仅可以用于存储线性结构，还可以用于存储非线性结构。例如，完整的二叉树是非线性结构，但是最好的存储方法是顺序存储方法。(下一节中介绍)()10。线性表格的逻辑顺序永远与储存顺序相符。错误的原因等于7。链式存储不需要一致性。()11。路线表中的每个节点只能是简单类型，而链接表中的每个节点可以是复杂类型。错误的是，线性表是一个逻辑结构概念，无论元素数据类型如何，都可以按顺序存储或

11、以链式存储。()12。表结构中最常用的是线性表，堆栈和队列不太常用。错了，不一定是这样吧？通常用于调用子节目或函数，CPU也使用队列。()13。堆栈是线性表，它将所有插入和删除操作限制在表的一端，是后进先出结构。()14。每个用户的表结构可以是堆栈、队列或线性表。没错。都是线性逻辑结构。堆栈和队列实际上是特殊的线性表。运算的定义略有不同。()15。与堆栈关联的列表是两个茄子的不同数据结构。错，堆栈是逻辑结构的概念，是特殊的线性表，关联表是存储结构的概念，两者不是同一项目。()16。堆栈和队列是非线性数据结构。错，它们都是线性逻辑结构，堆栈和队列实际上是特殊的线性表，运算的定义略有不同。()17

12、。堆栈和队列以顺序和链接的方式存储。()18。当两个堆栈共享连续内存空间时，为了提高内存利用率并减少溢出机会，必须将两个堆栈的底部分别安装在牙齿内存空间的两端。()19。团队是线性表格，其插入和删除操作分别在表格的两端执行，是前后输出结构。错了，后半部分错了。()20。如果堆栈的输入序列为12345，则堆栈的输出序列不能为12345。错了。可以。()21。如果二进制树使用二进制链表作为存储结构，则N个节点的二叉树链表只有N-1个非空指针字段。()22。二进制树每个节点上的两个子树的高度差异为1。()23。二叉树的每个节点上的两个子树是有序的。()24。二叉树的每个节点都有两棵树非空或两棵树。(

13、)25。二进制树中每个节点的关键字值大于左侧非空子树(如果存在)中所有节点的关键字值，小于右侧非空子树(如果存在)中所有节点的关键字值。(必须是二进制排序树的特性)()26。二叉树中的所有节点数为2k-1-1。其中K是树的深度。(必须为2i-1)()27。二叉树中的所有节点，如果没有左非空子树，则没有右非空子树。()28。对于非空的二进制树，如果根节点用作第一层，则层I中最多可以有2i-1个节点。(必须为2i-1)()29。将包含n个节点的二进制树保存为二进制链接表(link-rlink)。节点的2n个指针区域中，n个为空指针。()30。具有12个节点的完整二进制树包含5度2的节点。三、选择题

14、1.非线性结构是存在于数据元素之间的。a)一对多关系b)多对多关系c)多对一关系d)一对一关系2.数据结构中使用的与计算机无关的是数据的结构。a)存储b)物理c)逻辑d)物理和存储算法分析的目的是：a)确定数据结构的合理性b)算法的输入与输出关系研究C) d)分析算法的有效性，以提高分析算法的理解和文档性算法分析的两个茄子主要方面如下：a)空间复杂性和时间复杂性b)准确性和简洁性c)可读性和文档d)数据复杂性和节目复杂性电脑算法意味着：a)计算方法b)排序方法c)解决问题的有限运算序列d)调度方法6.电脑算法必须具有输入、输出和其他5茄子特性。a)可行性、可移植性和可扩展性b)可行性、确定性和

15、贫穷c)确定性、贫穷、稳定性d)可读性、稳定性、安全性7.数据显示在电脑内存中时，物理地址与逻辑地址相同，是连续的，称为：(a)存储结构(b)逻辑结构(c)顺序存储结构(d)链存储结构8.向量中第一个元素的存储地址为100，每个元素的长度为2，第五个元素的地址为(A)110 (B)108 (C)100 (D)1209.在n节点顺序表中，算法的时间复杂性是O(1)的操作。(a)访问查找第I节点(1In)和第I节点的直接前驱体(2In)(b)在第一个节点后插入新节点(1In)(c)删除第I个节点(1In)(d)按从小到大的顺序排列n个节点10.在具有127个元素的顺序表格中插入新元素，并保持原始顺序不变，以移动平均一个元素(A)8 (B)63.5 (C)63 (D)711.连接的存储结构占用的存储空间：(a)分为两部分，一部分存储节点值，另一部分存储指示节点之间关系的指针(b)仅保存部分节点值。(c)只有存储指示节点之间关系的指针的部分。(D)分成两部分，一