A．n个度为0 B．2m个度为0
C．2m个度为1 D．2m个度为2
6.某n>0个结点的二叉树的先序序列正好相反，则该二叉树一定不是_________的二叉树。
A．任一结点无左孩子B．任一结点无右孩子
C．深度为n D．存在度为2的结点
7.二叉树用二叉链表表示，若要将其所有结点的左，右子树相互交换位置，则采用下列——遍
历的方法较为合适。
A．先序B．中序C．后序D．按层
8.对于二叉树的两个结点X和Y，应该选择_________两个序列来判断X是否Y 的祖先。
A．先序和后序B．先序和中序
C．中序和后序D．任意两个序列都行
9.最小生成树指的是连通图中_________.
A．边数最少的生成树B．顶点相对较少的生成树
C．极小连通子图D．所有生成树中权值之和最小的生成树
10.具有n个顶点的强连通图至少有_________条弧。
A．n-1 B．n
C．2n D．n（n-1）
11.对20 个有序记录进行折半查找，查找成功的平均查找长度为_________.
A．5 B．37/10
C．39/10 D．41/10
12.哈希表长度为m，哈希函数H（K）=K%P，一般来说P应取小于m的最大_________.
A．奇数B．偶数
C．素数D．合数
13.对动态查找有高效率的查找表组织结构是_________.
A．有序表B．分块有序表
C．循环链表 D B-树
14.当初始数据有序时，不应采用_________.
A．堆排序B．快速排序
C．基数排序D．希尔排序
15.在n个元素中找出两个最小的元素，当n很大时，采用_________方法比较次数较少。
A．树型选择排序B．简单选择排序
C．归并排序D．快速排序
二、填空题（每空1分，共15分）
1.一个算法的效率可分为效率和效率。
2.向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动
________个元素。
3.在具有n个单元的循环队列中，队满时共有个元素。
4.假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起
始存储位置（基地址）为1000，则数组A的体积（存储量）为；末尾元素A57的第一个字节地址为；若按行存储时，元素A14的第一个字节地址为；若按列存储时，元素A47的第一个字节地址为。
5.设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个
度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。
6.10、线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值k，用二分法
检索表中与k相等的元素，在查找不成功的情况下，最多需要检索次。设有100个结点，用二分法查找时，最大比较次数是。
7.散列法存储的基本思想是由决定数据的存储地址。
三、应用题(共40分)
1.假设一棵二叉树的层次遍历序列是ABCDEFGHIJ和中序遍历序列是DBGEHJACIF,请画出该
树。（5分）
2.已知一个图的顶点为A、B、C、D，其邻接矩阵的上三角元素全为0（包括主对角线元素），
其他元素均为1。请画出该图，并给出其邻接表。（5分）
3.给定权值{8，12，4，5，26，16，9}，构造一棵带权路径长度最短的二叉树，并计算其带
权路径长度。（6分）
4.使用Prim算法构造出如下图所示的的最小代价生成树，并将过程写出。（6分）
图G
5.判别序列（42 13 91 23 24 16 05 88）是否为堆，如果不是，则把它调整为堆。使之
按关键字递减次序排列。请写出排序过程中得到的初始堆和一趟排序后的序列状态。（6分）
6.设有一组关键字{19, 01, 23, 14, 55, 20, 84, 27, 68, 11, 10, 77}，采用哈希函数: ：H(key) = key
MOD 13，，采用开放地址法的二次探测再散列方法解决冲突，试在1～18的散列地址空间中对该关键字序列构造哈希表，并求该表的平均查找长度ASL。（6分）
7.用序列（46，88，45，39，70，58，101，10，66，34）建立一个排序二叉树，画出该树，并
求在等概率情况下查找成功的平均查找长度。（6分）
三、算法题（15分）
1．算法分析题（5分）
阅读下面算法：
(1)简要说明程序功能。（3分）
(2)假设二叉排序树*bst是有n个结点的满二叉树,给出算法的时间复杂度。（2分）
int Proc (BSTree *bst, KeyType K)
{ BSTree f, q, s;
s=(BSTree)malloc(sizeof(BSTNode));
s-> key = K; s-> lchild = NULL; s-> rchild = NULL;
if ( *bst == NULL ) { *bst = s; return 1; }
