[理学]数据结构试卷.docVIP

《理学院数学系08级数据结构》试卷 题 号 一 二 三 四 五 总分 得 分 评卷人 选择题（从下列答案选项中选出一个正确答案，每小题2分，共18分) 长度为n的顺序存储的线性表,当在任何位置上插入一个元素的概率相等时，插入一个元素需要移动元素的平均次数为（ ）。 n+1 C. (n-1)/2 (n+1） C. D. 以下说法不正确的是（ ）。 在n个结点的无向图中,若边数多于n-1,则该图必是连通图。 对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目。出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。 任何一个无向连通图有一颗或多颗最小生成树。 强连通分量是有向图中的极大强连通子图 一组记录的关键字序列为{45，80，55，40，42，85}，则利用快速排序并以第一个记录关键字为基准得到一次划分的结果是（ ）q=p-next; p-next=q-next; free(q); p-next=p-next; free(p-next); p=p-next-next; free(p-next); 答案栏: 1、_____ 2、_____ 3、_____ 4、_____5、_____ 6、_____7、____ 8、_____9、_____ 填空题（每题2分，共20分） 1、若广义表A=(a,b,(c,d),(e,(f,g)))，则经过运算：head[tail[tail[A]]]的结果是______________________________。 2、、对于A[0]~A[7]有序表， 采用二分查找时，成功的平均查找长度ASL是______________________________。 3、下面程序的时间复杂度是______________________________。 void fun(int n) { int i=1,s=0; while(s=n*n*n) { s=s+i; i++; } } 4、设待排序的表有6个记录，其关键字分别为{46，89，56，48，40，84}，则利用堆排序（建立大根堆）的方法建立的初始堆为： ______________________________。 5、某二叉树的先序遍历序列是bcehdigf，中序遍历序列是ehcbidfg，则该二叉树的树形表示为： _______________________________。 6、图1为带权无向图，则从顶点4出发采用普里姆(Prim)算法生成的最小生成树为： _______________________________。 7、若将图2的二叉树转换为森林，则结果为： _________________________________________。 8、图3所示的二叉树的中序遍历序列是：_________________________________________。 9、若将函数f= 1+x1+x2+…+xn转化为递归函数，则递归函数表示如下： 10、设环形队列类型SqQueue中的成员data数组中元素个数最大不超过整数MaxSize；同时q-front为环形队首下标，q-rear为环形队尾下标；则利用MaxSize, q-front和q-rear计算当前环形队列中元素个数的公式为： ________________________________________。 计算题（每小题6分，共30分） 1. 已知8个字符的频数如下表： 字符 A B C D E F G H 频数 23 11 6 3 8 7 14 28 试画出哈夫曼树，并计算出带权路径长度WPL. 2. 按顺序读入关键字序列{33, 41, 20, 24, 30, 13, 01, 67}建立哈希表A[0..10]，其哈希函数为h(k)=(3k)%11，用线性探测法解决冲突。填充下面的哈希表，并在结点查找概率相等的情况下，计算出查找成功的平均查找长度ASLsucc和查找不成功的平均查找长度ASLunsucc。 0 1 2 3 4 5 6 7 8 9 10 3. 将整数序列{10，20，40，50，60，30，5，7}中的数依次插入到一棵空的平衡二叉树（AVL）中，用图形画出构造过程。并在结点查找概率相等的情况下，计算出查找成功的平均查找长度ASLsucc 4. 已知带权有向图G，试写出其邻接矩阵、邻接表。 并画出各强连通分量。 5. 设目标串为s= “abbababaab”，模式t= “ababaa”，计算模式t的next函数和nextval函数（填入表中），并写出KMP模式匹配过程（采