杭州师范大学国际服务工程学院20082009学年第二学期期末考试
《数据结构与算法分析》试卷（A）
题号得分注意：请将答案填写在答题纸上。一二三四五总分
一、选择（共30分每小题3分把最恰当的答案题号填到答题卷上）得分1对于具有
个顶点的连通图（连通的无向图）其最少的边数目为A
B
12C
1D
12给定某二叉树的先序遍历序列为ABDCEFHG，中序遍历序列为BDAFHEGC则该二叉树的后序遍历序列为ADBAHFGCEBBDHFGECACDBHFGECADDBCFHEGA3给定某整数序列为123459867现要对其递增排序，则最快的排序算法为附助存储空间要求最多的排序算法为A直接插入排序B堆排序C归并排序D起泡排序4将m个元素存储在具有s个单元的哈希表中，则其装填因子为AsmBmsCmsDms5图的广度优先搜索与二叉树的相类似A先序遍历B中序遍历C后序遍历D层次遍历6在下列三种二叉树中，对中的元素进行中序遍历结果得到的序列是有顺序的。A堆（heap）B二叉搜索树（bi
arysearchtree）C完全二叉树7．下列各整数序列中不是堆A10085987780608240201066B10098858280776660402010C10204060667780828598100D100854077806066988210208如果一个栈中的进栈次序为1234…
第一个输出的元素为
，则第i个输出的元素为A
i1B
iCiD无法确定9．一个深度为k的二叉树的最多的元素个数为A2k11B2k1C2k11D2k110下列方法不是哈希表中用于处理冲突的方法A线性探测B链地址法C折半查找D二次探测二、问答题（共10分请将答案填到答题卷上）得分1给定某英文文本为“this_is_a
_ideal_stri
g”采用等长编码时的总编码长度为________位采用哈夫曼编码方法时的总编码长度为________位6分2给定某整数序列为258421471527683520步长为3的第一轮希尔排序后得到的序列为3sort__________________________________________________4分
班级：
学号：
装
订
姓名：线
《数据结构与算法分析》试题（第1页
共3页）
f三、问答题（共38分请将答案填到答题卷上）1对于给定的某有向图（如右图所示）要求：①写出每个顶点的入度和出度2分②画出其邻接矩阵表示的示意图3分③画出其邻接表表示的示意图3分④画出其十字链表表示的示意图3分⑤画出其强连通分量3分⑥给出从顶点“1”出发的DFS（深度优先搜索）结果2分⑦r