计算机学院3数据结构

1、计算机科学与技术学院 2011-2012 学年第二学期期末数据结构 试卷 A （数服 111-2）（答题时间：120 分钟，满分：100 分）一、判断题：（共 10 分，每题 1 分）1.2.3.4.5.6.()非空线性表中任意一个数据元素都有且仅有一个直接后继元素。)在 n 个结点的无向图中,若边数少于 n-1,则该图必是非连通图。)如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。)顺序表是一种随机存取结构，链表是一种顺序存取结构。)栈和队列在逻辑结构上属于线性表。)对任意图，从它的某个顶点出发，进行一次深度优先搜索或广度优先搜索，即可图的每个顶点。7.8.()在非空完全二叉树

2、中，若一个结点不存在右孩子，则该结点一定是叶子结点。) 在任何情况下，堆排序的时间复杂度为三、应用题：（共 30 分 ，每题 10 分）15对图 1 所示的图，若从顶点 A 出发，按深度优先搜索方法进行遍历，则可能得到的一种顶点序列是_。A. a,b,e,c,d,fB. a,e,d,f,c,bC. a,e,b,c,f,dD. a,c,f,e,b,d2、假设用于通讯的电文由字符集a,b,c,d,e中的字符为3,8,6,4,5，要求：(1)构造 Huffman 树。，各字符在电文出现的次数分别16具有 n 个结点的二叉树的深度是（约定根结点所在的层次为 1）。A、n-1B、nC、D、不能确定(2)

3、并计算其路径长度 WPL。17已知广义表 L=(a,b),(c,d),则 GetTail(GetHead(GetTail(L)的结果为。(3)为每个字符设计 Huffman 编码。A、 (d )B、 (c,d)C、 (c,d)D、 d18下面的序列中，是堆。A、（1,2,8,4,3,9,10,5）3、 已知某个图的对应的邻接表如下：B、（1,5,10,6,7,8,9,2）C、（9,8,7,6,4,8,2,1）D、（9,8,7,6,5,4,3,7）19对二叉排序树进行操作，输出结点序列是按关键字有序的。A、先序遍历B、中序遍历C、后序遍历D、按层次遍历20如图 2 所示的 AOE 网，则事件 v

4、4 的最早发生时间是。（1）画出该邻接表对应的图。（2）在该邻接表上执行利用栈实现的拓扑排序算法，输出的拓扑序列是什么？A. 11B. 12C. 13D. 14（1）在划线的地方填写适当的语句，完善算法。（2）r0在算法中的作用是什么？（3）分析算法的时间复杂度、空间复杂度、稳定性。四、算法题（共 20 分）1、 阅读下面的算法，回答问题。（10 分）void aa(Queue *Q)Stack S;InitStack(S);/Q 是队列d;/初始化栈 Swhile (!QueueEmpty(Q) DeQueue(Q,d);push(S,d);/ QueueEmpty(Q)判断队空/出队/入栈

5、while(!StackEmpty(S)/ StackEmpty(S)判断栈空pop(S,d);EnQueue(Q,d);/出栈/入队该算法的功能是什么？假设初始时，队列Q 中的数据为（1,2,3,4,5,6），请写出执行完算法 aa 后，队列Q 中的数据是什么？2、阅读下面的直接void InsertSort(排序算法 (由小到大排列)，完成所问题（10 分）。r ,n) /一组待排序关键字直接用数组 r存放,n 是元素个数。i,j;for(i=2; i=n; i+)r0=ri ; j=i-1;while( ) j- -;/循环比较待元素与子表中元素的大小;/rj后移一个位置 ;/元素答 题 纸 （请将所有写在答题纸上）2、（1）一、判断题（正确为，错误为 x）（10 分）二、选择题（40 分）三、应用题（30 分）1. （1）（2）（2）（3）字符Huffman 编码abcde题号12345678910题号11121314151617181920题号1