杭州师范大学国际服务工程学院2008-2009学年第二学期期末考试。
数据结构与算法分析》试卷（a）
注意：请将答案填写在答题纸上。
一、选择（共30分，每小题3分，把最恰当的答案题号填到答题卷上）
1. 对于具有n个顶点的连通图（连通的无向图）, 其最少的边数目为。
a. nb. n ( n – 1) /2 c. n + 1d. n – 1
2. 给定某二叉树的先序遍历序列为 abdcefhg，中序遍历序列为 bdafhegc, 则该二叉树的后序遍历序列为。
a. dbahfgce b. bdhfgeca c. dbhfgeca d. dbcfhega
3. 给定某整数序列为 . 现要对其递增排序，则最快的排序算法为附助存储空间要求最多的排序算法为。
a. 直接插入排序 b. 堆排序 c. 归并排序 d. 起泡排序。
4. 将m个元素存储在具有s个单元的哈希表中，则其装填因子为。
a. s + m b. m / sc. m * sd. m – s
5. 图的广度优先搜索与二叉树的相类似。
a. 先序遍历 b. 中序遍历 c. 后序遍历 d.层次遍历。
6. 在下列三种二叉树中， 对( )中的元素进行中序遍历结果得到的序列是有顺序的。.
a. 堆（heap） b. 二叉搜索树（binary search tree） c.完全二叉树
7．下列各整数序列中( )不是堆。
a. b.
c. d.
8. 如果一个栈中的进栈次序为1,2,3,4,…,n,第一个输出的元素为n，则第i个输出的元素为。
a. n – i + 1 b. n – ic. id. 无法确定。
9．一个深度为k的二叉树的最多的元素个数为。
a. 2k + 1 – 1 b. 2k - 1c. 2k-1 – 1 d. 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的第一轮希尔排序后得到的序列为( 3-sort4 分)
三、问答题（共38分，请将答案填到答题卷上）
1. 对于给定的某有向图（如右图所示）,要求：
写出每个顶点的入度和出度(2 分)
画出其邻接矩阵表示的示意图； (3 分)
画出其邻接表表示的示意图； (3 分)
画出其十字链表表示的示意图； (3 分)
画出其强连通分量； (3 分)
给出从顶点“1”出发的dfs（深度优先搜索）结果； (2 分)
给出从顶点“2”出发的bfs（广度优先搜索）结果。 (2 分)
2.给定一整数序列为。将其依次插入到初始为空的二叉搜索树（bst： binary search tree）中。 请画出每个元素插入后的bst示意图。 (10 分)
3. 将关键字序列11,5, 29, 20, 0, 27 ,18依次插入表长为9的初始为空的哈希表中，其哈希函数为hash(k) =k % 9，处理冲突的方法为开放定址法中的线性探测(即di = i).请画出该哈希表， 并计算查找成功时的平均查找长度(asl:
**erage search time).(10 分)
三、完善程序 (共8分，每空格2分， 将答案填写在答题卷的相应位置)
请完成下列图的深度优先搜索算法，在空白处填写正确的语句。
#define max_vertex_num 20
typedef 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 dfstr**erse(algraph g){
//对图g作深度优先遍历。
for (v = 0;v <
visited[v] =a访问标志数组初始化。
for (v = 0;v <
if (!visited[v]) dfs(g,v对尚未访问的顶点调用dfs
void dfs(graph g,int v){
visited[v] =true;
printf("v%d->"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 = while (_c___p = p->nextarc;
if (!p->nextarc)) return -1;
else return p->nextarc->adjvex;
int firstadjvex(algraph g,int v)
if (!return -1;
else return __d___
五、编程(14分)
假设某大型**年终时要产生年度十佳运动员，结果由网民投票产生。假设有n个候选运动员(n > 10)，有m个网民参加投票，每人一张选票，每张选票选一个且只选一人，每个运动员用两位十进制数的号码表示。请编写选年度十佳运动员（得票最多者）的程序，并按运动员的得票顺序输出结果。
该程序的输入是两个文本文件，其一为保存有n个整数的文本文件“该文件表示n个候选运动员；另一为保存有m个整数的文本文件“该文件表示m张选票。
杭州师范大学国际服务工程学院2008-2009学年第二学期期末考试。
数据结构与算法分析》答题卷（a）
一、选择(共30分，每小题3分)
2019《数据结构》期末试卷B答案
pop s2,x return ok else 栈s1和s2都为空。return error 二 本题15分 用孩子兄弟链表作为树的存储结构，设计算法求出树的深度。解 算法思路 一棵树的深度可以递归定义为 若树为空，则深度为0，否则树的深度为根结点的所有子树深度的最大值加1。数据结构为 typede...
数据结构A期末试卷 A卷
试卷编号拟题教研室 或教师 签名乐晓波教研室主任签名。长沙理工大学考试试卷 a卷 课程名称 含档次 数据结构a 课程代号 0812002615 课程编号 002131 专业计算机相关专业层次 本 专 本科考试方式 开 闭卷 闭卷 一 应用题 2小题，共8分 设有一个栈，元素进栈的次序为 a，b，c，...
本科生期末试卷数据结构答案
六 解 为了压缩指令字的长度，必须设法把一个微指令周期中的互斥性微命令信号组合在一个小组中，进行分组译码。经分析，e f h 和 b,i,j 可分别组成两个小组或两个字段，然后进行译码，可得六个微命令信号，剩下的a,c,d,g 四个微命令信号可进行直接控制，其整个控制字段组成如下 01e 01b 直...