安
徽
工
业
大
学
工
商
学
院
试
题
纸（二）
二、填空题（每空1分，共12分）
1通常是以算法执行所耗费的和所占用的来判断一个算法的优劣。2．已知二维数组A1020采用行序优先方式存储，每个元素占2个存储单元。并且A00的存储地址是1024则A618的地址是3．用带头结点的循环链表表示的队列若只设尾指针rear则队空的条件是4．向一个有
个元素的有序表中插入一个新元素并保持原来顺序不变，平均要移动。个元素。
5．10000个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到________________。6．高度为h的完全二叉树最少有个结点。
7．对某二叉树进行前序遍历的结果为EBADCFHGIKJ，中序遍历的结果为ABCDEFGHIJK则后序遍历的结果为________________。8．线性结构中元素之间存在________关系，树形结构中元素之间存在________关系，图形结构中元素之间存在________关系。9．在一棵二叉树中，假定双分支结点数为10个，单分支结点数为11个，则叶子结点数为个。
三、判断题（每题1分，共10分）
（（（（（（（（）1在单链表中，头结点是必不可少的。）2在一个大根堆中，最小元素不一定在最后。）3顺序存储结构只能存线性结构，链式存储结构只能存非线性结构。）4在有向图中，所有顶点的入度之和等于所有顶点的出度之和。）5内部排序是指排序过程在内存中进行的排序。）6拓扑排序是指结点的值是有序排列。）7AOE网所示工程至少所需时间等于从源点到汇点最长路径长度。）8二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值大于其右孩子的值。（（）9分块查找的特点是块内可无序，块间要有序。）10快速排序的枢轴元素可以任意选定。
四、应用题（每题8分，共40分）
1．设哈希函数H（K）（K的第一字母在字母表中的序号）11，哈希表长度为11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。2．假设用于通信的电文由10个字母组成，字母A，B，C，D，E，F，G，H，I，J的使用频率分别为5，12，4，7，9，12，10，8，13，20试为这10个字符设计哈夫曼编码，并计算带权路径长度。3．给定一组关键码18，31，16，22，51，30，24，10，请建大根堆。4．已知带权的无向图的邻接矩阵如下，画出该图及其最小生r