杭师A-试卷-数据结构期末试卷答案.doc

班级： 学号： 姓名： 装 订 线 杭州师范大学国际服务工程学院2008-2009学年第二学期期末考试数据结构与算法分析试卷（A）题号一二三四五总分得分 注意：请将答案填写在答题纸上。得分一、选择（共30分,每小题3分,把最恰当的答案题号填到答题卷上）1. 对于具有n个顶点的连通图（连通的无向图）, 其最少的边数目为 ( ).A. n B. n ( n 1) / 2 C. n + 1 D. n 1 2. 给定某二叉树的先序遍历序列为 ABDCEFHG，中序遍历序列为 BDAFHEGC, 则该二叉树的后序遍历序列为 ( ).A. DBAHFGCE B. BDHFGECA C. DBHFGECA D. 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 s5. 图的广度优先搜索与二叉树的 ( )相类似.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, 10C. 10, 20, 40, 60, 66, 77, 80, 82, 85, 98, 100 D. 100, 85, 40, 77, 80, 60, 66, 98, 82, 10, 208. 如果一个栈中的进栈次序为1,2,3,4,n,第一个输出的元素为n，则第i个输出的元素为( ).A. n i + 1 B. n i C. i D. 无法确定9一个深度为k的二叉树的最多的元素个数为( ).A. 2k + 1 1 B. 2k - 1 C. 2k-1 1 D. 2k +110. 下列( )方法不是哈希表中用于处理冲突的方法.A. 线性探测 B. 链地址法 C. 折半查找 D. 二次探测得分二、问答题（共10分,请将答案填到答题卷上）1. 给定某英文文本为“this_is_an_ideal_string”, 采用等长编码时的总编码长度为_位, 采用哈夫曼编码方法时的总编码长度为_位.(6 分)2. 给定某整数序列为25, 84, 21, 47, 15, 27, 68, 35, 20, 步长为3的第一轮希尔排序后得到的序列为( 3-sort): 数据结构与算法分析试题（第1页 共3页）_.(4 分)得分三、问答题（共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，处理冲突的方法为开放定址法中的线性探测(即di = i).请画出该哈希表, 并计算查找成功时的平均查找长度(ASL: Average Search Time).(10 分)三、完善程序 (共8分,每空格2分, 将答案填写在答题卷的相应位置)请完成下列图的深度优先搜索算法，在空白处填写正确的语句。#define MAX_VERTEX_NUM 20typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc; /指向下一条弧的指针ArcNode;typedef struct VNodeVertexType data; /顶点信息ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; /图的当前顶点数和弧数 int vexnum,arcnum; /图的种类标志 int kind;ALGraph;void DFSTraverse(ALGraph G) /对图G作深度优先遍历 for (v = 0;v G.vexnum;+v) visitedv = _A_; /访问标志数组初始化 for (v = 0;v ,G.verticesv.data); for (w = FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w) if (!visitedw) _B_; /对v的尚未访问的邻接顶点w递归调用DFSint NextAdjVex(ALGraph G,int v,int w) ArcNode *p; p = G.verticesv.firstarc; while (_C_) p = p-nextarc; if (!(p-nextarc) return -1; else return p-nextarc-adjvex;int FirstAdjVex(ALGraph G,int v)if (!G.verticesv.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) -01234out-degree13121In-degree21302 1 0 2 4 2 1 0 4(2) (3). 0 1 2 3 4 5 6 7 8keys027112920518ST1212317ASL = (1 + 2 + 1 + 2 + 3 + 1 + 7) / 7 = 17 / 7得分四、完善程序 (8 分) A._FALSE_ B. _DFS(G,w)_C. _p-adjvex != w_ D. _G.verticesv.firstarc-adjvex _得分五、编程 (14 分)#include stdio.h#include stdlib.h#define MAX_NUMBER 100typedef 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 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 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 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-l