复习题
填空题
1、数据的逻辑结构被分为四种：_______、_______、_______和_______。
2、一个算法必须具备以下几个方面的基本特征：_______、_______、_______和_______。
3、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的_______
和_______等的学科。
4、抽象数据类型的特点是将_______和_______封装在一起，从而现实信息隐藏。
5、算法分析的目的是分析算法的效率以求改进，主要是指_______复杂度和_______复杂度。
6、_______是具有独立意义的最小数据单位，是对数据元素属性的描述。
7、一个广义表中的元素分为_______元素和_______元素两类。
8、一个广义表为(a,(b,c),d)，则该广义表的长度为_______，深度为_______。
9、一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为_______，深度为_______。
10、若一个图的顶点集为{a, b, c, d, e, f)，边集为{(a, b), (a, c) , (b, c) , (d, e)} ，则该图含有_______
个连通分量。
11、在队列中，允许进行插入操作的一端称为_______，允许进行删除操作的一端称为_______。
12、在 n 个结点的线索二叉链表中，有_______个线索指针。
13、串 S=″I am a teacher″的长度是_______。
14、以二分查找法查找一个线性表时，此线性表必须是_______存储的_______表。
15、在一个具有 n 个顶点的无向图中，要连通所有顶点则至少需要_______条边。
16、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这
种方式主要适合于_______。
17、稀疏矩阵一般采用_______方法压缩存储。
18、在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的______、_____和_____三项。
19、对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为_______。
20、在线性表的散列存储中，处理冲突有_______和_______两种方法。
21、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。
在这种存储结构中，n 个结点的二叉树共有_______个指针域，其中有_______个指针域是存
放了地址，有_______个指针是空指针。
22、一棵含有 n 个结点的 k 叉树，_______形态达到最大深度，_______形态达到最小深度。
23、散列函数的构造方法有：直接定址法、_______、_______、_______和_______。
24、处理散列函数冲突的方法：_______、_______和建立一个公共溢出区。
25、在一个小顶堆中，堆顶结点的值是所有结点中的_______，在一个大顶堆中，堆顶结点的值
是所有结点中的_______。
26、二叉树的深度优先遍历需要借助_______的存储结构，层次搜索需要借助_______的存储结构。
27、深度为 h 的满 m 叉树的第 k 层有_______个结点(1=<k=<h)。
28、从有序表（12，18，30，43，56，78，82，95）中分别折半查找 43 和 56 元素时，其比较次
数分别为_______和_______。
29、若一个图的顶点集为{a, b, c, d, e)，边集为{(a, b), (a, c) , (b, c) , (d, e)} ，则该图含有_______
个连通分量。
30、对于顺序存储的线性表，访问结点的时间复杂度是_______，增删结点的时间复杂度分别为
_______。
31、对于一个有 n 个结点的二叉树，当它为一棵_______二叉树时具有最小高度，即为_______，
当它为一棵单支树具有_______高度，即为_______。
32、数据结构是_______。
33、为查找某一特定单词在文本中出现的位置，可应用的串运算是_______。
