数据结构复习材料 1.填空题 数据结构是研究非数值计算的编程问题中计算机的操作对象及其之间关系的领域。 数据结构正式定义为(D,R)，其中D为数据元素有限集，R为关系有限集。 数据结构包括三个方面：数据的逻辑结构、数据的存储结构、数据的操作。 数据结构根据其逻辑结构可以分为两类。 它们是线性结构。 线性结构中的元素之间存在一对一的关系。 树结构中的元素之间存在一对多的关系。 图形结构中的元素之间存在多对多关系。 一对多关系。 在线性结构中，第一个节点没有前驱节点，其余每个节点都有且只有一个前驱节点； 最后一个节点没有后续节点，其余每个节点都有且只有一个后续节点。 。 在树结构中，根节点没有前驱节点，各个其他节点有且仅在图结构中，每个节点的前驱节点和后继节点的数量可以多达10个。最常用的操作有五种对数据进行操作，即插入、删除、修改、查找、排序。 11、算法的效率可以分为时间效率和空间效率。 12、在序列表中插入或删除一个元素，平均需要移动表中一半的元素。 具体移动的元素数量与表格的长度以及元素在表格中的位置有关。 13.线性表中的节点集合是有限的，节点之间的关系是一对一的关系 14.当在长度为n的向量的第i个元素（1in+1）之前插入元素时，需要向后移动 n -i+1 个元素。
15. 当从长度为n的向量中删除第i个元素（1in）时，需要向前移动ni个元素。 16、访问序列表中任意节点的时间复杂度都是O(1)。 因此，序列表也称为随机存取数据结构。 17. 序列表中逻辑相邻元素的物理位置必须相邻。 单链表中逻辑上相邻的元素不一定物理上相邻。 18、在单链表中，除第一个节点外，任何节点的存储位置都是由其直接前驱节点的link字段的值来指示的。 19、从19个节点的单向链表中删除已知节点*p，需要找到其前驱节点的地址，其时间复杂度为O(n)。 20、向量、栈和队列都是线性结构，向量的任意位置都可以插入和删除元素； 对于栈来说，只能在栈顶插入和删除元素； 对于队列来说，只能删除顶部的元素。 21. 栈是一种特殊的线性链表，允许插入和删除操作的一端称为 22. 队列是一种线性链表，仅限于链表一端只能进行插入操作，另一端只能进行删除操作列表。 23、不包含任何字符（长度为0）的字符串称为空字符串； 由一个或多个空格（仅空格字符）组成的字符串是空字符串。 24、子串的定位操作称为字符串模式匹配； 匹配到的主字符串称为目标字符串，称为模式。 25． 假设有一个二维数组A68，每个元素存储有6个相邻的字节，内存是字节寻址的。 已知A的起始存储位置（基址）为1000，则数组A的卷（存储量）为288B； 末尾元素A57的首字节地址为1282； 如果按行存储，元素A14的第一个字节地址一个字节地址为(8+4)6+1000=1072； 如果按列存储，则元素A47的首字节地址为(67+4)6+1000)=1276个节点。 二叉树有 5 种形式。
27． 深度为6的满二叉树有n1+n2=0+n2=n0-1=31个分支节点和26-1=32个叶子。 注：满二叉树中不存在度数为1的节点，因此分支节点数为度数为2的节点数。 28、一棵257个节点的完全二叉树，其深度为 注：用[log2(n)]+1=[8.xx]+1=９29。 假设完全二叉树有 700 个节点，则总共有 350 个叶节点。 答：最快的方法：使用叶子数=[n/2]=35030。假设一棵完全二叉树有1000个节点，那么完全二叉树有500个叶子节点和499个度为2的节点。节点只有非空右子树。 答：最快的方法：用叶子数=[n/2]=500，n2=n0-1=499。另外，最后一个节点2i属于左叶子，右叶子为空，所以有是一个非空的左子树。 完全二叉树的特性决定了不可能有空的左右子树，所以非空的右子树个数=0.31。 在数据不规则存储的线性表中搜索的最佳方法是顺序搜索（线性搜索）32。 线性有序列表(a1,a2,a3,...,a256)从小到大排列。 对于给定值k，使用二分法在表中查找等于k的元素。 如果搜索失败，此时需要的最大搜索数量为100个节点。 使用二分法查找时，最大比较次数为33次。假设对有序线性表a[20]进行二分查找，则比较一次查找成功的节点数。 是 1； 比较两次搜索成功的节点数； 平均搜索长度为 3.7。 解：显然，平均搜索长度=O(log2n)5乘以(25)。
但具体次数不应该按照公式ASL来计算（即（2）/20=4.6次是不正确的！）。 因为这是在n=2m-1的假设下推导出来的公式。 应详尽列出：所有元素的搜索次数=(1+22+43+84+55)=74； ASL=74/20=3.734。 在一半的有序列表中搜索 (4, 6, 12, 20, 28, 38, 50, 70, 88, 100)。 如果在表中查找元素 20，它将与表中的元素 28、6、12、20 进行比较。 。 35. 在各种搜索方法中，平均搜索长度与节点数n无关的搜索方法是哈希搜索。 36、散列法存储的基本思想是关键字的值决定数据的存储地址。 2、判断是真是假（勾选正确的说法，标出相反的说法）。 链表的每个节点恰好包含一个指针。 答：错了。 链表中的节点可以包含多个指针字段，分别存储多个指针。 例如，双向链表中的节点可以包含两个指针字段，分别存储指向其直接前驱节点和直接后继节点的指针。 链表的物理存储结构与链表的顺序相同。 错了，链表的存储结构特点是无序，而链表的示意图是有序的。 链表的删除算法非常简单，因为当链上的一个节点被删除时，计算机会自动将后续单元向前移动。 错了，链表的节点不会移动，只会改变指针内容。 线性表的每个节点只能是简单类型，而链表的每个节点可以是复杂类型。
逻辑结构和物理结构错误、混乱。 链表也是线性表！ 甚至顺序列表也可以存储记录数据。 序列表结构适合顺序访问，而链表结构适合随机访问。 错了，恰恰相反。 顺序表适合随机访问，而链表适合“遵循模式”的顺序存储方法。 顺序存储方式的优点是存储密度高，插入、删除操作效率高。 错了，前半部分是正确的，但后半部分是错误的。 这就是链式存储的优势。 顺序存储方式的插入和删除操作效率较低，并且在线线性表在物理存储空间上必须是连续的。 错了，线性表有两种存储方式，顺序存储和链式存储。 后者不需要连续存储。 当线性表顺序存储时，逻辑上相邻的元素在物理存储顺序上可能不相邻。 错误。 线性表有两种存储方法。 在顺序存储中，逻辑上相邻的元素在存储的物理位置的顺序上也是相邻的。 顺序存储只能用于存储线性结构。 错误。 顺序存储方法不仅可以用来存储线性结构，也可以用来存储非线性结构。 例如，完全二叉树是一种非线性结构，但它最好的存储方式是顺序存储。 （下一节介绍）（） 10、线性表的逻辑顺序和存储顺序总是一致的。 错了，原因和7一样。链式存储不需要一致。 () 11.线性表的每个节点只能是简单类型，而链表的每个节点可以是复杂类型。 错了，线性表是一个逻辑结构概念，可以顺序存储或者链式存储，与元素数据类型无关。
() 12、最常用的表结构是线性表，而栈和队列则不太常用。 错了，不一定吧？ 通常用于调用子程序或函数，队列也用于CPU中。 ()13． 堆栈是一种线性列表，其中所有插入和删除操作都仅限于列表的一端。 它是后进先出的结构。 () 14、对于不同的用户，表结构可以是栈、队列、线性表。 没错，它们都是线性逻辑结构。 堆栈和队列实际上是特殊的线性表，其操作定义略有不同。 () 15.栈和链表是两种不同的数据结构。 错了，栈是一种逻辑结构的概念，一种特殊的线性表，而链表是一种存储结构的概念，它们不是同一个东西。 ()16。 堆栈和队列是非线性数据结构。 错了，它们都是线性逻辑结构。 堆栈和队列实际上是特殊的线性表，其操作定义略有不同。 ()17。 栈和队列的存储方式可以是顺序的，也可以是链接的。 ） 18、当两个栈共用一块连续的内存空间时，为了提高内存利用率，减少溢出的机会，两个栈的底应该设置在内存空间的两端。 () 19、队列是一个线性表，插入和删除操作在表的两端进行。 它是先进后出的结构。 错了，后半句错了。 ( ) 20. 如果堆栈的输入顺序是 12345，则堆栈的输出顺序不可能是 12345。可能是错误的。 () 21、如果二叉树采用二叉链表作为存储结构，那么n个节点的二叉树链表中只有n-1个非空指针字段。
()22． 二叉树中每个节点的两个子树的高度差等于1。 () 23、二叉树中每个节点的两个子树是有序的。 () 24、二叉树中的每个节点都有两个非空子树或两个空子树。 () 25、二叉树中每个节点的键值均大于其左非空子树中所有节点的键值（如果存在），且小于其右非空子树中所有节点的键值空子树（如果存在）字值。 （应该是二叉排序树的特性）（）26． 二叉树中所有节点的数量为 2 k-1 -1，其中 k 是树的深度。 (应2 -1) () ２7． 对于二叉树中的所有节点，如果不存在非空左子树，则也不存在非空右子树。 () 28. 对于一棵非空二叉树，以根节点为第一层，第 i 层最多可以有 2 个节点。 （应为2i-1 () 29.用二叉链表方法（link-rlink）存储一棵包含n个节点的二叉树，该节点的2n个指针区域中，n+1个为空指针。（） 30.有 12 个节点的完全二叉树有 5 个度为 2 的节点。 3. 单选题的非线性结构是存在一种： A) 一对多关系 B) 多对多关系 C ) 多对一对一关系 D) 在一对一关系数据结构中，与所使用的计算机无关的是数据的结构；
