北京航空航天大学考研真题

题目	题型
则由此可以断定所采用的遍历方法是（）。	单选
已知某无回路的有向图G的邻接表如图一6所示，下列四个顶点序列中，不属于G的拓扑序列的是（）。	单选
若具有n个顶点的连通图采用邻接矩阵表示，则该邻接矩阵中非零元素的个数至少是（）。	单选
在长度为n且元素按值有序排列的顺序表中进行折半查找，查找每个元素所进行的元素之间的比较次数（）对应的“判定树”的深度（设深度≥2）。	单选
若散列表的长度为m，待散列的元素的个数为n，装填因子为α，则散列表的平均查找长度为（）。	单选
该排序过程采用的排序方法是（）。	单选
若要以复杂度为O(1)的时间代价将两个单链表链接成一个单链表，则这两个单链表分别应该为（）。	问答
若某满二叉树的结点总数为20至40之间的一个素数，则满足该二叉树中叶结点的数目为（）。	问答
某二叉树的中序遍历序列为（d，b，a，e，c，f），按层次遍历序列为（a，b，c，d，e，f），则该二叉树的后序遍历序列为（）。	问答
一个具有36条边的非连通无向图中至少有（）个顶点。	问答
除了拓扑排序方法外，判断一个有向图是否存在回路的方法还有（）。	问答
在顺序表（6，15，30，37，65，68，70，72，89，99）中采用折半查找法查找元素37的过程中与表中进行过比较的元素依次为（）。	问答
由经验得知，为了降低发生散列冲突的可能性，在采用除留余数发构造的散列函数H(k)=k MOD p中，p的取值最好是（）。（k为关键字）	问答
这种排序方法是（）。	问答
请用大O符号形式写出下列函数的时间复杂度。	问答
则请画出转换之前的树。	问答
证明：若无向图G中每个顶点的度至少为2，则G必然存在回路。	问答
折半查找法适用于什么线性表？为什么不能在按值大小有序链接的线性链表（单链表）中采用折半查找法查找链结点?	问答
每一个链结点的数据域中存放一个数据，但头结点数据域中不存放任何信息。	问答
在C语言中，对于下列存储类别，只有在使用时才为该类型的变量分配内存空间的是（）。	单选

题目

题型

则由此可以断定所采用的遍历方法是（）。

单选

已知某无回路的有向图G的邻接表如图一6所示，下列四个顶点序列中，不属于G的拓扑序列的是（）。

单选

若具有n个顶点的连通图采用邻接矩阵表示，则该邻接矩阵中非零元素的个数至少是（）。

单选

在长度为n且元素按值有序排列的顺序表中进行折半查找，查找每个元素所进行的元素之间的比较次数（）对应的“判定树”的深度（设深度≥2）。

单选

若散列表的长度为m，待散列的元素的个数为n，装填因子为α，则散列表的平均查找长度为（）。

单选