存在这样的二叉树，对它采用任何次序的遍历，结果相同。

(1)【◆题库问题◆】：[判断题] 存在这样的二叉树，对它采用任何次序的遍历，结果相同。
A．正确
B．错误

【◆参考答案◆】：正确

(2)【◆题库问题◆】：[单选] 排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置，这是（）排序的基本思想。
A．堆排序
B．直接插入排序
C．快速排序
D．冒泡排序

【◆参考答案◆】：D

(3)【◆题库问题◆】：[名词解释] 分块查找（索引查找）

【◆参考答案◆】：
分块查找以前两个为基础，将待查记录分成若干块，每块的关键字无序，但每块的关键字的最大值有序，查找时，先查找到待查记录所在的块，再在块内进行顺序查找。找块时，即可以用折半查找，也可用顺序查找。

(4)【◆题库问题◆】：[单选] 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B．在第i个结点后插入一个新结点（1≤i≤n）
C．删除第i个结点（1≤i≤n）
D．将n个结点从小到大排序

【◆参考答案◆】：A

(5)【◆题库问题◆】：[单选] 对线性表进行折半搜索时，要求线性表必须（）
A．以链接方式存储且结点按关键码有序排列
B．以数组方式存储
C．以数组方式存储且结点按关键码有序排列
D．以链接方式存储

【◆参考答案◆】：C

(6)【◆题库问题◆】：[问答题] 已知图G的邻接矩阵如下所示：（1）求从顶点1出发的广度优先搜索序列；（2）根据prim算法，求图G从顶点1出发的最小生成树，要求表示出其每一步生成过程。（用图或者表的方式均可）。

【◆参考答案◆】：(1)广度优先遍历序列：1; 2, 3, 4; 5; 6(2)最小生成树（prim算法）

(7)【◆题库问题◆】：[问答题] 阅读下列算法，并回答下列问题：该算法采用何种策略进行排序？

【◆参考答案◆】：
直接插入排序。

(8)【◆题库问题◆】：[单选] 下列关于队列的叙述中正确的是（）
A．在队列中只能插入数据
B．在队列中只能删除数据
C．队列是先进先出的线性表
D．队列是先进后出的线性表

【◆参考答案◆】：C

(9)【◆题库问题◆】：[问答题] 什么是队列的上溢现象？一般有几种解决方法，试简述之。

【◆参考答案◆】：
在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量（即存储的空间大小）为maxnum。当有元素要加入队列（即入队）时，若rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种"假溢出"现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。
一般地，要解决队列的上溢现象可有以下几种方法：
（1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。
（2）要避免出现"假溢出"现象可用以下方法解决：
第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。
第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。
第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循"先进先出"的原则。

(10)【◆题库问题◆】：[填空题] 由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为（）。

【◆参考答案◆】：55