数据结构与算法分析试卷

《数据结构与算法分析试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京工业大学计算机学院2004级2005─2006（第二学期）《数据结构与算法》期末考试卷考试形式：“A4一纸开卷”时间2006年6月16日8:00~9:35班级学号姓名卷面作业题号一二三四五总分总分上机分数101045152070%30%100注意：不能拆卷!卷面不整洁最多可以扣3分.一、单项选择题（10分）1．算法的渐进时间复杂度是指（）。A．算法程序执行的绝对时间B．算法中执行语句的总条数C．算法最深层循环语句中原操作重复执行的次数D．随着问题规模的增大，算法执行时间的增长趋势2．三个元素X、Y和Z顺序进栈，若进栈过程中允许退栈，不可能得到的退栈排列是（）。A

2、．XYZB．YZXC．ZXYD．ZYX3．利用折半查找在有序表(4，10，28，32，46，55，63，76，97)中查找28，55和97时，所需进行的关键字和给定值的比较次数分别为（）。A．3，3，4B．3，4，3C．4，3，3D．4，4，34．对任一棵二叉树进行遍历，如果只看叶子结点的输出序列，则叶子的先序序列和后序序列所对应的次序关系（）。A．不确定B．相同C．互为逆序D．不相同9-15．下列排序算法中，其时间复杂度和记录的初始排列无关的是（）。A．堆排序B．插入排序C．快速排序D．起泡排序二、填空题（10分）（不写解答过程，将答案直接填写在试题的空上）1．数

3、据结构在计算机中的表示被称为。2．包含t个非零元素、m行n列的稀疏矩阵，采用三元组表示法存储该矩阵，当t值很小或与m•n等数量级时，快速转置算法在这两种条件下的时间复杂度分别为。3．使用循环队列对n个结点的满二叉树进行按层次的横向遍历，所开设的队空间大小至少应为。4．假设哈希表的表长为m，哈希函数为H(key)，若用二次探测再散列解决冲突，则探查地址序列的形式表达为。5．在插入排序、起泡排序、快速排序、堆排序和归并排序等五个排序方法中，适合做“最低位优先”多关键字排序的有。三、解答题（本大题共5小题，共45分）1．森林转化为对应的二叉树后，对该二叉树进行先序遍历和中

4、序遍历，结果为：先序序列HDACBGFE中序序列ADCBHFEG请画出原来的森林。9-22.对于给定的关键字序列：Sun，Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec，Moon。（1）以字典序比较大小，画出该输入序列所创建的二叉排序树；（2）写出查找关键字Moon的比较过程；（3）画出按教科书的算法删除关键字Sun后的二叉排序树。9-33.利用堆排序方法对一组关键字序列（7，10，14，23，33，56，66，72，90）只进行前两趟的非递减序排序，按要求完成下列问题：（1）画出排序的“初始堆”，并统计建立初始堆所需

5、要进行的比较次数；（2）画出第一趟和的第二趟的堆排序结果。建初始化堆比较次数：第一趟结果第二趟结果9-44．已知一个图如下所示，其顶点按A、B、C、D、E、F、G顺序存放在邻接表的顶点表中，请画出该图的完整邻接表，使得按此邻接表进行深度优先遍历时得到的顶点序列为ACFGDEB，进行广度优先遍历时得到的顶点序列为ACBDFEG。5．已知一个电文中只含‘A’,’B’,’C’,’D’,’E’,’F’,’G’七种字符，且每个字母在电文中出现的频度依次为：0.15,0.05,0.20,0.28,0.12,0.11,0.09，按要求完成下列问题：（1）按HuffnamCodin

6、g算法和所给的存储空间图示，画出构造Huffman树的存储表示及Huffman编码（注意：为使编码无二义性，应保持左子树根的结点序号比．右子树根的结点序号小）。．HTweightparentlchildrchild123456789101112139-5（2）若电文中的字母总数为1000，估算经哈夫曼编码后得到的电文总长：四．算法阅读题（15分）一个AOV网G的邻接矩阵如下图所示，阅读所给的算法（算法中的Q是一个循环队列结构），并完成下面的两个问题。StatusgraphXP（GraphG）{FindInDegree(G,indegree);InitQueue(Q)

7、;for(i=0;i