| 填空题（共50题） |
| 题目 |
| 第1题. 算法的计算量的大小称为计算的_____。 |
| 第2题. 一个算法应具有_____，____，____，____和____这五个特性。 |
| 第3题. 数组的长度是____，线性表的长度是____。 |
| 第4题. 数据结构是研究数据的____和____以及他们之间的相互关系，并对这种结构定义相应的____,设计出相应的____,而确保经过这些运算后所得的新结构是____结构类型。 |
| 第5题. 在线性表的顺序存储中，元素之间的逻辑关系是通过____决定的；在线性表的链接存储中，元素之间的逻辑关系是通过____决定的。 |
| 第6题. 在双向链表中，每个结点包含两个指针域，一个指向____结点，另一个指向____结点。 |
| 第7题. 对于一个具有N个结点的单链表，在已知的结点*P后插入一个新结点的时间复杂度为____,在给定值为X的结点后插入一个新结点的时间复杂度为____. |
| 第8题. 在一个单链表中删除*p结点时，应执行下列操作：
q=p->next;
p->data=p->next->data;
p->next=____;
free(q); |
| 第9题. 设有一空?C，现有输入序列1,2,3,4,5,经push,push,pop,push,pop,push,push后，输出序列为____. |
| 第10题. 无论对于顺序存储还是链接存储的?C和队列来说，进行插入或删除运算的时间复杂度均相同为____. |
| 第11题. 一个字符串相等的充要条件是____和____. |
| 第12题. 一维数组的逻辑结构是____,存储结构是____;对于二维或多维数组，分为按____和____两种不同的存储方式。 |
| 第13题. 一个广义表为(a,(a,b),d,e,((i,j)k))，则该广义表的长度为____,深度为____. |
| 第14题. 数组A［1..10,-2..6,2..8］以行优先的顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A【5，0，7】的存储地址为____. |
| 第15题. 假定一棵树的广义表表示为A(B(E),C(F(H,I,J),G),D),则该树的度为____,深度为____,终端结点个数为____,单分支结点个数为____,C结点的双亲结点为____,其孩子结点为____和____结点。 |
| 第16题. 对于一棵具有n个结点的树，该树中所有结点的度数之和为____. |
| 第17题. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有____个。 |
| 第18题. 对于一棵含有40个结点的理想平衡树，它的高度为____. |
| 第19题. 在一个堆的顺序存储中，若一个结点的下标为i，则它的左子女结点的下标为____,右子女结点的下标为____. |
| 第20题. 在霍夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10外，还可以最多对____个字符编码。 |
| 第21题. 在一个最小堆中，堆顶结点的值是所有结点中的____,在一个最大堆中，堆顶结点的值是所有结点中的____. |
| 第22题. 对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为____个，其中____个用于指向子女结点，____个指针空闲着。 |
| 第23题. 以折半搜索方法从长度为12的有序表中搜索一个元素时，平均搜索长度为____. |
| 第24题. 以折半搜索方法搜索一个线性表时，此线性表必须是____存储的____表。 |
| 第25题. 从有序表（12，18，30，43，56，78，82，95）中依次折半搜索43和56元素时，其搜索长度分别为____和____. |
| 第26题. 对于折半搜索所对应的判定树，它既是一棵____,又是一棵____. |
| 第27题. 假定对长度n＝50的有序表进行折半搜索，则对应的判定树高度为____,判定树中前5层的结点数为____,最后一层的结点数为____. |
| 第28题. 在一个无向图中，所有顶点的度数之和等于所有边数的____倍。 |
| 第29题. 在一个具有n个顶点的无向完全图中，包含有____条边，在一个具有n个顶点的有向完全图中，包含有____条边。 |
| 第30题. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要____条边。 |
| 第31题. 表示图的三种存储结构为____,____,____. |
| 第32题. 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为____和____条。 |
| 第33题. 在有向图的邻接表和逆邻接表表示中，每个顶点的边链表中分别链接着该顶点的所有____和____结点。 |
| 第34题. 对于一个具有n个顶点和e条边的有向图和无向图，若采用邻接多重表表示，则存于顶点表中的边链表指针分别有____和____个，所有边结点有____个。 |
| 第35题. 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表和邻接多重表表示时，求任一顶点度数的时间复杂度依次为____、____、____. |
| 第36题. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为____和____. |
| 第37题. 在直接选择排序中，记录比较次数的时间复杂度为____,记录移动次数的时间复杂度为____. |
| 第38题. 假定一组记录的排序码为（46，79，56，38，40，80），对其进行快速排序的一次划分的结果为____. |
| 第39题. 在二路归并排序中，对n个记录进行归并的趟数为____. |
| 第40题. 对20个记录进行归并排序时，共需要进行____趟归并，在第三趟归并时是把长度为____的有序表两两归并为长度为____的有序表。 |
| 第41题. 假定一组记录的排序码为（46，79，56，38，40，80），对其进行归并排序的过程中，第二趟归并后的结果为____. |
| 第42题. 在索引表中，每个索引项至少包含有____域和____域这两项。 |
| 第43题. 在索引表中，若一个索引项对应数据对象表中的一个表项，则称此索引为____索引，若对应数据对象表中的若干表项，则称此索引为____索引。 |
| 第44题. 若对长度n＝10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为____,二级索引表的长度为____. |
| 第45题. 假定要对长度n＝100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m＝20的散列表，每个散列地址的同义词子表（单链表）的长度平均为____. |
| 第46题. 已知一棵3阶B_树中含有50个关键码，则该树的最小高度为____,最大高度为____. |
| 第47题. 在一棵B_树中，所有叶结点都处在____上，所有叶结点中空指针等于所有____总数加一。 |
| 第48题. 在对m阶B_树插入元素的过程中，每向一个结点插入一个关键码后，若该结点的关键码个数等于____个，则必须把它分裂为____个结点。 |
| 第49题. 向一棵B_树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度____. |
| 第50题. 从一棵B_树删除关键码的过程中，若最终引起树根结点的合并，则新树比原树的高度____. |
