数据库系统工程师：数据结构精选填空题训练
填空题（共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_树删除关键码的过程中，若最终引起树根结点的合并，则新树比原树的高度____.
答案
第1题. 复杂度
第2题. 有穷性，确定性，可行性，0或多个输入，1或多个输入。
第3题. 数组元素的个数，表中数据元素的个数
第4题. 物理结构，逻辑结构，运算，算法，原来的
第5题. 物理存储位置，链域的指针值
第6题. 前驱，后续
第7题. O(1),O(N)
第8题. q->next
第9题. 2,3
第10题. O(1)
第11题. 两个串的长度相等，对应位置的字符相等
第12题. 线性结构，顺序结构，以行为主序，以列为主序
第13题. 5,3
第14题. 913
第15题. 3，4，6，1，A,F,G
第16题. n-1
第17题. 6
第18题. 5
第19题. 2i+1,2i+2
第20题. 4
第21题. 最小值，最大值
第22题. 2n,n-1,n+1
第23题. 37/12
第24题. 顺序，有序
第25题. 1,3
第26题. 二叉搜索树，理想平衡树
第27题. 5,31,19
第28题. 2
第29题. n(n-1)/2,n(n-1)
第30题. n-1
第31题. 邻接矩阵，邻接表，邻接多重表
第32题. e,2e
第33题. 出边，入边
第34题. 2n,n,e
第35题. O(n),O(e/n),O(e)
第36题. n,n-1
第37题. O(n2),O(n)
第38题. (84,79,56,38,40,46)
第39题. 4，4
第40题. 5，4，8
第41题. [38 46 56 79][40 84]
第42题. 关键码值，子表地址域
第43题. 稠密，稀疏
第44题. 500,25
第45题. 5
第46题. 4,5
第47题. 同一层，关键码
第48题. m,2
第49题. 增1
第50题. 减一