杭州师范大学国际服务工程学院2008-2009学年第二学期期末考试《数据结构与算法分析》试卷（A ）注意：请将答案填写在答题纸上。

一、选择（共30分,每小题3分,把最恰当的答案题号填到答题卷上）1. 对于具有n 个顶点的连通图（连通的无向图）, 其最少的边数目为 ( ). A. n B. n ( n – 1) / 2 C. n + 1 D. n – 12. 给定某二叉树的先序遍历序列为 ABDCEFHG ，中序遍历序列为 BDAFHEGC , 则该二叉树的后序遍历序列为 ( ).A. DBAHFGCEB. BDHFGECAC. DBHFGECAD. DBCFHEGA3. 给定某整数序列为 {1,2,3,4,5,9,8,6,7}. 现要对其递增排序，则最快的排序算法为( ), 附助存储空间要求最多的排序算法为 ( ).A. 直接插入排序B. 堆排序C. 归并排序D. 起泡排序 4. 将m 个元素存储在具有s 个单元的哈希表中，则其装填因子为 ( ). A. s + m B. m / s C. m * s D. m – s 5. 图的广度优先搜索与二叉树的 ( )相类似.A. 先序遍历B. 中序遍历C. 后序遍历D.层次遍历6. 在下列三种二叉树中， 对( )中的元素进行中序遍历结果得到的序列是有顺序的。

. A. 堆（heap ） B. 二叉搜索树（binary search tree ） C.完全二叉树 7．下列各整数序列中( )不是堆.A. {100, 85, 98, 77, 80, 60, 82, 40, 20, 10, 66}B. {100, 98, 85, 82, 80, 77, 66, 60, 40, 20, 10}C. {10, 20, 40, 60, 66, 77, 80, 82, 85, 98, 100}D. {100, 85, 40, 77, 80, 60, 66, 98, 82, 10, 20}8. 如果一个栈中的进栈次序为1,2,3,4,…,n ,第一个输出的元素为n ，则第i 个输出的元素为( ).A. n – i + 1B. n – iC. iD. 无法确定 9．一个深度为k 的二叉树的最多的元素个数为( ).A. 2k + 1 – 1B. 2k - 1C. 2k -1 – 1D. 2k +1 10. 下列( )方法不是哈希表中用于处理冲突的方法. A. 线性探测 B. 链地址法 C. 折半查找 D. 二次探测二、问答题（共10分,请将答案填到答题卷上）1. 给定某英文文本为“this_is_an_ideal_string ”, 采用等长编码时的总编码长度为________位, 采用哈夫曼编码方法时的总编码长度为________位.(6 分)2. 给定某整数序列为25, 84, 21, 47, 15, 27, 68, 35, 20, 步长为3的第一轮希尔排序后得到的三、问答题（共38分,请将答案填到答题卷上）1. 对于给定的某有向图（如右图所示）,要求： ① 写出每个顶点的入度和出度(2 分)② 画出其邻接矩阵表示的示意图; (3 分) ③ 画出其邻接表表示的示意图; (3 分) ④ 画出其十字链表表示的示意图; (3 分) ⑤ 画出其强连通分量; (3 分)⑥ 给出从顶点“1”出发的DFS （深度优先搜索）结果; (2 分) ⑦ 给出从顶点“2”出发的BFS （广度优先搜索）结果. (2 分)2.给定一整数序列为{40, 30, 20, 50, 60, 45, 25, 55, 35, 38}.将其依次插入到初始为空的二叉搜索树（BST：Binary Search Tree）中. 请画出每个元素插入后的BST示意图. (10 分)3. 将关键字序列11,5, 29, 20, 0, 27 ,18依次插入表长为9的初始为空的哈希表中，其哈希函数为hash(k) = k % 9，处理冲突的方法为开放定址法中的线性探测(即d i = i).请画出该哈希表, 并计算查找成功时的平均查找长度(ASL: Average Search Time).(10 分)三、完善程序(共8分,每空格2分, 将答案填写在答题卷的相应位置)请完成下列图的深度优先搜索算法，在空白处填写正确的语句。

#define MAX_VERTEX_NUM 20typedef struct ArcNode{int adjvex; //该弧所指向的顶点的位置struct ArcNode *nextarc; //指向下一条弧的指针}ArcNode;typedef struct VNode{VertexType data; //顶点信息ArcNode *firstarc; //指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedef struct {AdjList vertices; //图的当前顶点数和弧数int vexnum,arcnum; //图的种类标志int kind;}ALGraph;void DFSTraverse(ALGraph G){//对图G作深度优先遍历for (v = 0;v < G.vexnum;++v)visited[v] = _____A_______; //访问标志数组初始化for (v = 0;v < G .vexnum;++v)void DFS(Graph G ,int v){ visited[v] = TRUE;printf("V%d->",G .vertices[v].data);for (w = FirstAdjVex(G ,v);w;w=NextAdjVex(G ,v,w))if (!visited[w]) _____B_______; //对v 的尚未访问的邻接顶点w 递归调用DFS }int NextAdjVex(ALGraph G ,int v,int w) {ArcNode *p;p = G.vertices[v].firstarc;while (_____C_______) p = p->nextarc; if (!(p->nextarc)) return -1; else return p->nextarc->adjvex; }int FirstAdjVex(ALGraph G ,int v) {if (!G.vertices[v].firstarc) return -1;else return _____D_______; }五、编程(14分)假设某大型网站年终时要产生年度十佳运动员，结果由网民投票产生。

假设有n 个候选运动员(n > 10)，有m 个网民参加投票，每人一张选票，每张选票选一个且只选一人，每个运动员用两位十进制数的号码表示。

请编写选年度十佳运动员（得票最多者）的程序，并按运动员的得票顺序输出结果。

该程序的输入是两个文本文件，其一为保存有n 个整数的文本文件“athlete.txt ”，该文件表示n 个候选运动员;另一为保存有m 个整数的文本文件“input.txt ”，该文件表示m 张选票。

杭州师范大学国际服务工程学院2008-2009学年第二学期期末考试《数据结构与算法分析》答题卷（A ）题号 Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ 总分 得分一、选择(共30分，每小题3分)1. D2. C3. A C4. B5. D6. A7. D8. A9. B10. C二、填空(10 分) (1) ____ ___位; (2 分) _____79____位. (4 分)(2) 3-sort 后的整数序列为: ___25,15,20,47,35,21,68,84,27_________. (4 分)三、问答(38 分) (1) ①- 0 1 2 3 4 out-degree 13 1 2 1 In-degree2132②③ ④0010010101010000010110000 ⎡⎤⎢⎥ ⎢⎥⎢⎥ ⎢⎥ ⎢⎥⎢⎥ ⎣⎦得分得分得分班级： 学号： 姓名： 装 订 线⑤⑥ 1 0 2 4 ⑦ 2 1 0 4(2)(3).0 1 2 3 4 5 6 7 8ASL = (1 + 2 + 1 + 2 + 3 + 1 + 7) / 7 = 17 / 7 四、完善程序 (8 分)A.__FALSE _______B. __DFS(G ,w)___C. __p->adjvex != w ___D. _G .vertices[v].firstarc->adjvex _五、编程 (14 分)#include "stdio.h" #include "stdlib.h"#define MAX_NUMBER 100 typedef struct node *pointer_node; typedef struct node{ pointer_node llink; int no; int vote;pointer_node rlink; };void selectbestsportsman(int n,int m);void selectbestsportsman(int n,int m) {pointer_node head = NULL,pre,current; int i,j,votenumber;//用双向链表作为存储结构//建立双向链表的头结点，各运动员的编号从1开始pre = (pointer_node) malloc(sizeof(node));pre->llink = NULL;pre->rlink = NULL;pre->no = 0;pre->vote = MAX_NUMBER;head = pre;//分别为每个运动员建立结点for (i = 1 ; i <= n;i++){current = (pointer_node) malloc(sizeof(node));current->no = i;current->vote = 0;current->llink = pre;current->rlink = NULL;pre->rlink = current;pre = current;}pre = head->rlink;//统计各运动员的得票数，并按运动员的得票数从高到低进行调整printf("请输入%d张选票\n",m);printf("请输入各选票号码！(1<=i<=%d)\n",n);for (i = 1; i <= m;i++){printf("第%d张选票: ",i);scanf("%d",&votenumber);//判断选票是否有效while ((votenumber < 1) || (votenumber > n)){printf("该选票无效！请重新输入第%d张选票: ",i);scanf("%d",&votenumber);}//找到该运动员的结点pre = head->rlink;while ((pre) && (pre->no != votenumber)) pre = pre->rlink;pre->vote++;//按各运动员的所得票数从高到你进行调整current = pre;pre = current->llink;while ((pre != head)&&(pre->vote < current->vote)) pre = pre->llink; if (pre->rlink != current){//删除current结点current->rlink->llink = current->llink;current->llink->rlink = current->rlink;//把current结点插入到pre结点后current->rlink = pre->rlink;current->llink = pre;current->rlink->llink = current;pre->rlink = current;}}//输出每个运动员的编号与得票数pre = head->rlink;while (pre){printf("no = %d,vote number = %d\n",pre->no,pre->vote);pre = pre->rlink;}}void main(){selectbestsportsman(10,10);}。