12.已知一组关键字为{25,48,36,72,79,82,23,40,16,35},其中每相邻两个为有序子序列。对这 些子序列进行一趟两两归并的结果是() A.{25,36,48,72,23,40,79,82,16,35} B{25,36,48,72,16,23,40,79,82,35} C.{25,36,48,72,16,23,35,40,79,82} D.{16,23,25,35,36,40,48,72,79,82} 13.设顺序存储的线性表共有123个元素,按分块査找的要求等分成3块。若对索引表采用顺序查找来确定 块,并在确定的块中进行顺序查找,则在查找概率相等的情况下,分块查找成功时的平均查找长度为() A.21B.23C.41D62 14索引非顺序文件的特点是() A.主文件无序,索引表有序B主文件有序,索引表无序 C.主文件有序,索引表有序D主文件无序,索引表无序 15倒排文件的主要优点是( A.便于进行插入和删除运算B便于进行文件的恢复 C便于进行多关键字查询D节省存储空间 第二部分非选择题(共70分) 、填空题(本大题共10小题,每小题2分,若有两个空格,每个空格1分,共20分)不写解答过程, 将正确的答案写在每小题的空格内。错填或不填均无分。 16抽象数据类型的特点是将 和 封装在一起,从而实现信息隐 17从顺序表中删除一个元素时,表中所有在被删元素之后的元素均需个位置。 18.在队列中,允许进行插入操作的一端称为 允许进行删除操作的一端称 为 19如图两个栈共享一个向量空间,topl和top2分别为指向两个栈顶元素的指针,则“栈满”的判定条件 top top2 栈2 20.设Sl=“good”,S2=“",S3=“book”,则Sl,S2和S3依次联接后的结果是 21假设三维数组A[098]按行优先顺序存储,若每个元素占3个存储单元,且首地址为100,则元素 A[9][8[的存储地址是 22已知在一棵含有n个结点的树中,只有度为k的分支结点和度为0的叶子结点,则该树中含有的叶子结 点的数目为 能够成功完成拓扑排序的图一定是一个 24如果在排序前,关键字序列已接近正序或逆序,则在堆排序和快速排序两者之中,选用 较为适当。 25假设哈希表的表长m,哈希函数为H(key),若用线性探查法解决冲突,则探查地址序列的形式表达 为 三、解答题(本大题共4小题,每小题5分,共20分) 26假设通信电文使用的字符集为{ab,cd,ef},各字符的在电文中出现的频度分别为:34,5,12,23,8, 18,试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右12.已知一组关键字为{25，48，36，72，79，82，23，40，16，35}，其中每相邻两个为有序子序列。对这 些子序列进行一趟两两归并的结果是（ ） A.{25，36，48，72，23，40，79，82，16，35} B.{25，36，48，72，16，23，40，79，82，35} C.{25，36，48，72，16，23，35，40，79，82} D.{16，23，25，35，36，40，48，72，79，82} 13.设顺序存储的线性表共有 123 个元素，按分块查找的要求等分成 3 块。若对索引表采用顺序查找来确定 块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为（ ） A.21 B.23 C.41 D.62 14.索引非顺序文件的特点是（ ） A.主文件无序，索引表有序 B.主文件有序，索引表无序 C.主文件有序，索引表有序 D.主文件无序，索引表无序 15.倒排文件的主要优点是（ ） A.便于进行插入和删除运算 B.便于进行文件的恢复 C.便于进行多关键字查询 D.节省存储空间 第二部分 非选择题（共 70 分） 二、填空题（本大题共 10 小题，每小题 2 分，若有两个空格，每个空格 1 分，共 20 分）不写解答过程， 将正确的答案写在每小题的空格内。错填或不填均无分。 16.抽象数据类型的特点是将 和 封装在一起，从而实现信息隐 藏。 17.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需 一个位置。 18. 在队列中，允许进行插入操作的一端称为 ，允许进行删除操作的一端称 为 。 19.如图两个栈共享一个向量空间，top1 和 top2 分别为指向两个栈顶元素的指针，则“栈满”的判定条件 是 。 20.设 S1=“good”，S2=“ ”，S3=“book”，则 S1，S2 和 S3 依次联接后的结果是 。 21.假设三维数组 A[10][9][8]按行优先顺序存储，若每个元素占 3 个存储单元，且首地址为 100，则元素 A[9][8][7]的存储地址是 。 22.已知在一棵含有 n 个结点的树中，只有度为 k 的分支结点和度为 0 的叶子结点，则该树中含有的叶子结 点的数目为 。 23.能够成功完成拓扑排序的图一定是一个 。 24.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用 较为适当。 25.假设哈希表的表长 m，哈希函数为 H(key)，若用线性探查法解决冲突，则探查地址序列的形式表达 为 。 三、解答题（本大题共 4 小题，每小题 5 分，共 20 分） 26.假设通信电文使用的字符集为{a,b,c,d,e,f}，各字符的在电文中出现的频度分别为：34，5，12，23，8， 18，试为这 6 个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树（要求树中左孩子结点的权值小于右