西安电子科技大学期末考试真题+解析

题目	题型
设有 n 个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为()，右孩子结点的编号为()。	填空
设一组初始记录关键字为 (72 ， 73 ， 71 ， 23 ， 94 ， 16 ， 5) ，则以记录关键字 72 为基准的一趟快速排序（升序）结果为 () 。	填空
设有向图G中有向边的集合E ={<1 ， 2> ， <2 ， 3> ， <1 ， 4> ， <4 ， 2> ， <4 ， 3>} ，则该图的一种拓扑序列为 () 。	填空
下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。	填空
下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。	填空
已知二叉树的前序遍历序列是 AEFBGCDHIKJ ，中序遍历序列是 EFAGBCHKIJD ，画出此二叉树，并画出它的后序线索二叉树。	问答
已知待散列的线性表为（ 36 ， 15 ， 40 ， 63 ， 22 ），散列用的一维地址空间为 [0..6] ，假定选用的散列函数是 H （ K ） = K mod 7 ，若发生冲突采用线性探查法处理	问答
已知序列（ 10 ， 18 ， 4 ， 3 ， 6 ， 12 ， 1 ， 9 ， 18 ， 8 ）请用快速排序写出每一趟排序的结果。	问答
设计在单链表中删除值相同的多余结点的算法。	问答
设计一个求结点 x 在二叉树中的双亲结点算法。	问答
设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。	单选
设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。	单选
设某无向图中有n个顶点e条边，则该无向图中所有顶点的度之和为（）。	单选
设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。	单选
在二叉排序树中插入一个结点的时间复杂度为（）。	单选
设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。	单选
设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。	单选
设用链表作为栈的存储结构则退栈操作（）。	单选
下列四种排序中（）的空间复杂度最大。	单选
设某二叉树中度数为0的结点数为N0 ，度数为1的结点数为Nl ，度数为2的结点数为N2 ，则下列等式成立的是（）。	单选

题目

题型

设有 n 个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为()，右孩子结点的编号为()。

填空

设一组初始记录关键字为 (72 ， 73 ， 71 ， 23 ， 94 ， 16 ， 5) ，则以记录关键字 72 为基准的一趟快速排序（升序）结果为 () 。

填空

设有向图G中有向边的集合E ={<1 ， 2> ， <2 ， 3> ， <1 ， 4> ， <4 ， 2> ， <4 ， 3>} ，则该图的一种拓扑序列为 () 。

填空

下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。

填空

下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。

填空