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

题目	题型
设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( )。	单选
设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。	单选
设一棵三叉树中有 2 个度数为 1 的结点， 2 个度数为 2 的结点， 2 个度数为 3 的结点，则该三叉链权中有（）个度数为 0 的结点。	单选
设无向图G 中的边的集合 E={(a ， b) ， (a ， e) ， (a ， c) ， (b ， e) ， (e ， d) ， (d ， f) ， (f ， c)} ，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。	单选
队列是一种（）的线性表。	单选
如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（）	单选
设初始记录关键字基本有序，则快速排序算法的时间复杂度为 O(nlog2n) 。（）	单选
分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（）	单选
二维数组和多维数组均不是线性结构。（）	单选
向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（）	单选
如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（）	单选
非空的双向循环链表中任何结点的前驱指针均不为空。（）	单选
不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（）	单选
图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（）	单选
稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非 0 元素。（）	单选
设一组初始记录关键字序列为 (49 ， 38 ， 65 ， 97 ， 76 ， 13 ， 27 ， 50) ，则以 d=4 为增量的一趟希尔排序结束后的结果为 () 。	填空
下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。	填空
设指针变量 p 指向单链表中结点 A ，指针变量 s 指向被插入的结点 X ，则在结点 A 的后面插入结点 X 需要执行的语句序列： s->next=p->next; (); 。	填空
设指针变量 head 指向双向链表中的头结点，指针变量 p 指向双向链表中的第一个结点	填空
设某棵二叉树的中序遍历序列为 ABCD ，后序遍历序列为 BADC ，则其前序遍历序列为 () 。	填空

题目

题型

设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( )。

单选

设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。

单选

设一棵三叉树中有 2 个度数为 1 的结点， 2 个度数为 2 的结点， 2 个度数为 3 的结点，则该三叉链权中有（）个度数为 0 的结点。

单选

设无向图G 中的边的集合 E={(a ， b) ， (a ， e) ， (a ， c) ， (b ， e) ， (e ， d) ， (d ， f) ， (f ， c)} ，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。

单选

队列是一种（）的线性表。

单选