2、n的顺序表时，搜索成功的平均搜索长度为（ ）。 A、n B、n/２ C、(n-1)/2 D、(n+1)/24.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（） A、9 B、11 C、12 D、不确定5.有64个结点的完全二叉树的深度为（ ）（根的层次为1）。 A、8 B、7 C、6 D、56.在已知待排序文件已基本有序的前提下，效率最高的排序方法是（） A、直接插入排序B、直接选择排序C、快速排序D、归并排序7.在有n个叶子结点
3、的哈夫曼树中，其结点总数为（）。 Ａ、不确定Ｂ、2nＣ、2n+1Ｄ、2n-18.广义表((A,B,E,F,G))的表尾是()。 A、(B,E,F,G) B、() C、（A，B，E，F，G） D、不存在9.折半查找要求查找表中各元素的关键字值必须是（）排列。 Ａ、 递增或递减Ｂ、递增Ｃ、递减Ｄ、无序10.设有一个N*N的对称矩阵A，将其下三角部分以行为主序存入一个一维数组B中，A[0][0]存入B[0]中，那么第i行的对角元素A[i][i]存入于B中的（）处。 A、（i+3）*i/2B、(i+1)*
4、i/2C、(2N-i+1)*i/2D、(2N-i-1)*i/2一、判断题（每题2分，共20分）1.有回路的有向图不能完成拓扑排序。（）2.一棵树的度是指该树中所有结点的度的和。（）3.在完全二叉树中，一个结点若没有左孩子，则它一定没有右孩子。 （）4.满二叉树一定是完全二叉树，并且完全二叉树也一定是满二叉树。（）5.能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序表上相同。（）6.栈与队列都是限制存取点的表，只是它们的存取特征不一样。（）7.直接选择排序是一种不稳定的排序方法。（）8.双循环链表中，任
5、一结点的后继指针均指向其逻辑后继。（）9.对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。（）10.顺序存储的数组是一个随机存取结构。（）一、填空（每题2分，共20分）1.数据结构的抽象数据类型ADT可用三元组表示（D，S，P），其中D是数据对象，S是_____________，P是_____________。2.已知顺序存储的循环队列中，front，rear分别为队头、队尾指针，MAX为队列中存储单元的最大个数，若当队列中仅有一个空闲单元时视为队满，则队满条件为___
6、______；一般情况下，队列中元素个数可表示为_________________。3.已知一棵度为5的树中，2度、3度、4度、5度结点的个数依次为1，2，3，4个，则叶子个数为_____________。4.假设有一个顺序栈A，其中元素a1,a2,a3,a4,a5,a6依次进栈，如果已知六个元素出栈的顺序是a2,a3,a4,a6,a5,a1,则此栈容量至少应该为______________________。5.顺序表中逻辑上相邻的元素的物理位置________________紧邻。单链表中逻辑上相邻的元素的物
7、理位置________________紧邻。6.一个向量的第一个元素存储地址是100，每个元素的长度为2，则第五个元素的地址是________。7.在对于一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第七个记录60插入到有序表时，为寻找插入位置需比较______次。二、操作题（每题5分，共20分）1.请写出下面关键字序列的第一趟和第二趟快速排序(排序是从小到大)后的序列。49386597761327492.已知二叉树的先序、中序和后序序列分别如下，但其中有一些模糊不清，
8、请将其补完整。 先序序列 ＿BC＿EF＿＿ 中序序列 BDE＿AG＿H 后序序列 ＿DC＿GH＿A3.假设字符a,b,c,d,e,f的使用频度分别是0.07,0.09,0.12,0.22,0.23,0.27。 (1)画出这棵Huffman（哈夫曼）树。(2)写出a,b,c,d,e,f的Huffman（哈夫曼）编码。4.已知哈希函数为除余法（对7取余）,关键字序
