数据结构与算法分析试卷.pdf

《数据结构与算法分析试卷.pdf》由会员分享，可在线阅读，更多相关《数据结构与算法分析试卷.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 9-1北京工业大学北京工业大学 计算机学院计算机学院 2004 级级 20052006（第二学期）（第二学期）数据结构与算法期末考试卷数据结构与算法期末考试卷 考试形式：考试形式：“A4 一纸开卷一纸开卷”时间时间 2006 年年 6 月月 16 日日 8:009:35 班级班级 学号学号 姓名姓名 题号题号 一一 二二 三三 四四 五五 卷面卷面 总分总分 作业作业 上机上机 总分总分 分数分数 10 10 45 15 20 70%30%100 注意：不能拆卷注意：不能拆卷!卷面不整洁最多可以扣卷面不整洁最多可以扣 3 分分.一、单项选择题（一、单项选择题（10 分）分）1算法的渐进时间复

2、杂度是指（）。A算法程序执行的绝对时间 B算法中执行语句的总条数 C算法最深层循环语句中原操作重复执行的次数 D随着问题规模的增大，算法执行时间的增长趋势 2三个元素 X、Y 和 Z 顺序进栈，若进栈过程中允许退栈，不可能得到的退栈排列是（）。AXYZ BYZX CZXY DZYX 3利用折半查找在有序表(4，10，28，32，46，55，63，76，97)中查找 28，55 和 97 时，所需进行的关键字和给定值的比较次数分别为（）。A3，3，4 B3，4，3 C4，3，3 D4，4，3 4对任一棵二叉树进行遍历，如果只看叶子结点的输出序列，则叶子的先序序列和后序序列所对应的次序关系（）。A

3、不确定 B相同 C互为逆序 D不相同 9-25下列排序算法中，其时间复杂度和记录的初始排列无关的是（）。A堆排序 B插入排序 C快速排序 D起泡排序 二、填空题（二、填空题（10 分）分）（不写解答过程，将答案直接填写在试题的空上）1数据结构在计算机中的表示被称为 。2包含 t 个非零元素、m 行 n 列的稀疏矩阵，采用三元组表示法存储该矩阵，当 t值很小或与 mn 等数量级时，快速转置算法在这两种条件下的时间复杂度分别为 。3使用循环队列对 n 个结点的满二叉树进行按层次的横向遍历，所开设的队空间大小至少应为 。4假设哈希表的表长为 m，哈希函数为 H(key)，若用二次探测再散列解决冲突，

4、则探查地址序列的形式表达为 。5在插入排序、起泡排序、快速排序、堆排序和归并排序等五个排序方法中，适合做“最低位优先”多关键字排序的有 。三、解答题（本大题共三、解答题（本大题共 5 小题，共小题，共 45 分）分）1森林转化为对应的二叉树后，对该二叉树进行先序遍历和中序遍历，结果为：先序序列 HDACBGFE 中序序列 ADCBHFEG 请画出原来的森林。9-3 2.对于给定的关键字序列：Sun，Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec，Moon。（1）以字典序比较大小，画出该输入序列所创建的二叉排序树；（2）写出查找关键字 Moon 的

5、比较过程；（3）画出按教科书的算法删除关键字 Sun 后的二叉排序树。9-43.利用堆排序方法对一组关键字序列（7，10，14，23，33，56，66，72，90）只进行前两趟的非递减序排序，按要求完成下列问题：（1）画出排序的“初始堆”，并统计建立初始堆所需要进行的比较次数；（2）画出第一趟和的第二趟的堆排序结果。建初始化堆 比较次数：第一趟结果 第二趟结果 9-54已知一个图如下所示，其顶点按 A、B、C、D、E、F、G 顺序存放在邻接表的顶点表中，请画出该图的完整邻接表，使得按此邻接表进行深度优先遍历时得到的顶点序列为 A C F G D E B，进行广度优先遍历时得到的顶点序列为 A

6、C B D F E G。5已知一个电文中只含 A,B,C,D,E,F,G 七种字符，且每个字母在电文中出现的频度依次为：0.15,0.05,0.20,0.28,0.12,0.11,0.09，按要求完成下列问题：（1）按 HuffnamCoding 算法和所给的存储空间图示，画出构造 Huffman 树的存储表示及 Huffman 编码（注意：为使编码无二义性，应保持左子树根的结点序号比右子树根的结点序号小）。HT weight parent lchild rchild 1 2 3 4 5 6 7 8 9 10 11 12 13 9-6（2）若电文中的字母总数为 1000，估算经哈夫曼编码后得到

7、的电文总长：四算法阅读题（四算法阅读题（15 分）分）一个 AOV 网 G 的邻接矩阵如下图所示，阅读所给的算法（算法中的 Q 是一个循环队列结构），并完成下面的两个问题。Status graphXP（Graph G）FindInDegree(G,indegree);InitQueue(Q);for(i=0;iG.vexnum;+i)if(!indegreei)EnQueue(Q,i);count=0;while(!QueueEmpty(Q)DeQueue(Q,v);printf(v);+count;for(w=FirstAdj(v);w;w=NextAdj(G,v,w)-indegree(w

8、);if(!indegreew)EnQueue(Q,w);if(countG.vexnum)printf(“图中有回路”);return ERROR;else return OK;9-7（1）画出循环队列 Q0.8的动态变化情况并写出算法输出的结果：Q 队初态 front rear 输出的结果：（2）说明 graphXP 算法的功能：0 1 2 3 4 5 5 7 8 9-8五五.算法设计（本大题共算法设计（本大题共 2 小题，共小题，共 20 分）分）1.设计递归算法，求以“孩子兄弟链表”表示的树的度。请写明算法思想，语句加注释。树结构的类型定义如下：typedef struct CSNod

9、e Elem data;struct CSNode *firstchild,*nextsibling;CSNode,*CSTree;算法思想：递归算法：9-92在 Windows 的资源管理器中，包含有许多文件夹及文件。这些文件夹和文件之间的组织关系可以用类似广义表的形式表示。例如，对应的广义表模型如下（假设文件夹与文件均以合法的字符串命名，文件结点含有指向具体文件的指针 FILE*pf）：（d1（d2（d3（f1，f2），f3，f4），d4（f5，d5（），d6（），）设计资源管理应用的广义表类型定义，并编写算法删除由字符串命名的指定文件夹或文件（提示：如果删除的是文件夹，应该先将该文件夹中包含的子文件夹或文件一并删除掉）。