广东工业大学数据结构试卷.doc

7．散列表的地址区间为0-17，散列函数为H(K)=K mod 17，采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（ ）。 [A] 8 [B] 9 [C] 10 [D] 11 8．ISAM文件和VASM文件属于（ ）。 [A] 索引非顺序文件 [B] 顺序文件 [C] 索引顺序文件 [D] 散列文件 二．填空题（共12分，每空1分） 1．线性表L=（a1,a2,…,an）采用顺序存储表示，假定删除表中任一元素的概率相同，则删除一个元素需要移动元素的平均次数是___________。 2．在栈结构中，允许插入和删除的一端称为___________，另一端称为___________。 3．模式串P=’ababc’的next函数值序列为___________。 4．深度为6的完全二叉树的结点数至少有___________个。 5．线索二叉树的左线索指向其___________，右线索指向其___________。 6．已知无向图G =（V, E），其中V={a, b, c, d, e}，E={(a,b),(a,d),(a,c),(d,c),(b,e)}，若从顶点a开始遍历图，得到的序列为a,b,e,c,d，则采用的是___________遍历方法。 7．动态查找表和静态查找表的重要区别在于前者包含有___________和___________运算，而后者不包含这两种运算。 8．简单选择排序的平均时间复杂度是___________，堆排序的平均时间复杂度是___________。 三．解答题（共40分） 1．（6分）假设电文中仅由a到e共5个字母组成，字母在电文中出现的频率依次为 0.2，0.15，0.32，0.28，0.05 请画出由此构造的哈夫曼树（要求树中所有结点的左右孩子必须是左大右小），并计算该哈曼夫树的带权路径长度WPL。 2．（8分）设对称矩阵A= （1）若将A中包括主对角线的下三角元素按行的顺序压缩到数组S中，即S为 1 0 3 0 0 0 2 0 5 0 下标： 1 2 3 4 5 6 7 8 9 10 请求出A中任一元素的行列下标[i,j](1=i,j=4)与S中元素的下标K之间的关系； （2）若将A[i,j]（1=i, j=4）视为稀疏矩阵，画出其三元组表。 3．（10分）若带权无向图G的邻接矩阵如右图所示，顶点集是{V1, V2, V3, V4, V5}， （1）画出图G的邻接表，要求每个顶点的表结点序号都是按照从 小到大的次序链接； （2）画出图G的最小生成树。 4．（8分）从空树开始构造一棵平衡二叉排序树，依次插入的关键字为（11, 13, 15, 17, 19, 20），请按下图要求画出该树的部分生成过程。 插入11,13,15后 插入17后 插入19后 插入20后 5．（8分）对序列（3, 87, 12, 61, 70, 97, 26, 45）执行升序排序。试根据堆排序原理，填写完整下列各步骤结果。 建立大顶堆结构：________________________ 交换与调整： （1）87, 70, 26, 61, 45, 12, 3, 97； （2）________________________； （3）61, 45, 26, 3, 12, 70, 87, 97； （4）45, 12, 26, 3, 61, 70, 87, 97； （5）26, 12, 3, 45, 61, 70, 87, 97； （6）________________________； （7）3, 12, 26, 45, 61, 70, 87, 97； 四．算法阅读题（共24分） 1．（6分）阅读算法f1，并回答问题。 （1）设线性表L=(2, 3, 6, 5, 4)，并采用带头结点的单链表储存，写出执行算法f1(L)后的L； （2）简述算法f1(L)对线性表L的操作意义。 void f1(LinkList L) { LinkList p, s; p = L-next; L-next = NULL; while (p!= NULL) { s=p-next; p-next=L-next; L-next =p; p=s; } } 2．（6分）假设以带头结点的循环链表表示队列，并且只设一个指针rear指向队尾元素（注意不设头指针），算法f2实现相应的出队列操作。