[数据结构与算法]数据结构简答题目

13

1. 线性结构与非线性结构的差别：
   线性结构是最简单最常用的一种数据结构，线性结构的特点是，在数据元素的非空有限集合中，除第一个元素无直接前驱、最后一个元素无直接后继外，集合中其余每个数据元素均有唯一直接前驱和唯一的直接后继。
   而非线性结构中节点间的前驱、后继关系并不具有唯一性
   常见线性结构有：线性表，栈，队列，串，数组
   常见非线性结构有：树，图
2. 说明在图的遍历中，设置访问标志数组的作用
   用于防止某个节点被多次重复访问
   由于在图中各个节点间的联通关系是不确定的，有可能会出现某个节点和若干节点相连的情况，当这些相连节点被遍历到时，会出现多个访问该节点的情况，设置访问标志数组可以避免重复访问。
3. 简述数组和字符串属于线性表的原因
   数组和字符串都满足除第一个元素无直接前驱、最后一个元素无直接后继外，集合中其余每个数据元素均有唯一直接前驱和唯一的直接后继。
4. 算法特性与算法时间复杂度
   算法特性：输入，输出，有限性，确定性，可行性
   算法时间复杂度：为方便于比较解决同一问题的不同算法，通常以算法中执行基本操作重复执行的频度作为度量标准，用随着问题规模增加的函数来表征，以此作为时间度量
   记作T(n)=O(f(n))
   称作算法的渐进时间复杂度，简称时间复杂度
5. 数据类型和抽象数据类型
   数据类型：一组性质相同的值的集合以及定义在这个集合上的一组操作的总称
   抽象数据类型：包括数据对象、数据元素间的结构关系、操作三个部分
6. 简述稳定排序的含义，给出一种不稳定排序方法，并证明
   稳定排序：排序前与排序后，相同关键字的数据位置前后关系不会发生变化
   快速排序，2412*，d=2时，结果为12*24

14

1. 简述四类基本的数据逻辑关系，并用图表示
   集合结构：结构中元素除了同属于同一集合外无其他关系
   线性结构：元素间存在一对一线性关系
   树状结构：存在一对多的层次结构
   图状或网状结构：存在多对多的任意关系
2. 特殊矩阵的压缩原则有哪些
   元素分布有规律（三角矩阵，带状矩阵）的矩阵，只需找到对应规律的数学函数，便可实现二位矩阵到一位矩阵的压缩
   矩阵中大部分元素都是相同的元素时，可采用三元组或十字链表进行压缩存储
3. 什么是平衡二叉树？平衡因子的取值范围是什么
   平衡二叉树或者是一颗空树，或者具有以下性质，即任意节点的左右子树高度差不超过1，取值范围【-1，1】
4. 具有n个结点的k叉树，若采用k叉链表存储，则空链域有多少个（写出求解步骤）
   N+1，n个节点，则具有2n个链域，链表中存在n-1个链，则存在2n-n+1个空链域
5. 递归进层时需要做哪些事
   三件事
   保留本层参数与返回地址
   为被调用函数的局部变量分配存储区，给下层函数赋值
   将程序转移到被调函数入口