序为主序存储，元素A[8][5]的起始地址与当A按列序为主序存储时的元素_________的起始地址相同。（设每个字符占一个字节）（）
A.A[8][5] B.A[3][10] C.A[5][8] D.A[0][9] 4.下面说法不正确的是（）
A.广义表的表头总是一个广义表 B.广义表的表尾总是一个广义表 C.广义表难以用顺序存储结构 D.广义表可以是一个多层次的结构 5.算术表达式A+B*C-D/E转为前缀表达式后为（）
A.-A*C/DE B.-A+B*CD/E C.-+ABC/DE D.-+A*BC/DE 6.有n个叶子的哈夫曼树的结点总数为（）
A.不确定 B.2n C.2n+1 D.2n-1
7. 若X是中序线索二叉树中一个有左孩子的结点，且X不为根，则X的前驱为（ ） A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点
8.无向图G=（V，E），其中V={a，b，c，d，e，f}，E={{a，b}，{a，e}，{a，c}，{b，e}，{c，f}，{f，d}，{e，d}}，对该图进行广度优先遍历，得到的顶点序列正确的是（ ） A.a，b，e，c，d，f B.a，c，f，e，b，d
C.a，e，b，c，f，d D.a，e，d，f，c，b
9.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行_________探测。（ ）
A.k-1次 B.k次 C.k+1次 D.k（k+1）/2次
10.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是（ ）
A.直接插入排序 B.快速排序 C.直接选择排序 D.堆排序
二、填空题（5分，每题1分）
1.在有序表A[1..12]中，采用折半查找算法查等于A[12]的元素，所比较的元素下标依次为_____________________________。
2.求图的最小生成树有两种算法，________________ 算法适合于求稀疏图的最小生成树。 3.一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为_____________。 4.在单链表L中，指针p所指结点有后继结点的条件是________________________。
5.一个深度为k，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依次对结点编号，则编号是i的结点所在的层次号是_______________________（跟所在的层次号规定为1层）。
三、判断题（5分，每题1分）
1.链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 （ ）
2.对一棵二叉树进行层次遍历时，应借助于一个栈。 （ ） 3.将一棵树转成二叉树，跟节点没有左子树。 （ ） 4.一个有向图的邻接表和逆邻接表中结点的个数可能不等。 （ ） 5.在待排序数据有序的情况下，快速排序效果好。 （ ）
四、应用题（20分，每题5分）
1.用集合{46，88，45，39，70，58，101，10，66，34}建立一棵二叉排序树，画出该树，并求在等概率情况下的平均查找长度。
2008计算机科学与技术专业综合-7
5
2.设一组关键字{9，01，23，14，55，20，84，27}，采用哈希函数：H（key）=key mod 7和二次探测再散列法解决冲突，对该关键字序列构造表长为10的哈希表。
3.假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10，试为这8个数字设计哈夫曼编码。
4.用普里姆算法构造下图的一棵最小生成树，并给出选点顺序。（以①为起点）
1 18 23 12 15 20 2 6 7 5 5 4 7 25 6 8 4 3 10
五、算法设计题（10分）
编写一个算法来交换单链表中指针P所指接点与其后继结点，HEAD是该链表的头结点，P指向该链表中的某一结点。
2008计算机科学与技术专业综合-7
6