福建农林大学考试试卷(A)卷

1、 福建农林大学考试试卷 （A）卷20072008 学年第 二 学期课程名称： 数据结构 考试时间 120分钟 计算机科学技术 专业 2006 年级 班 学号 姓名 题号一二三四五六七八九总得分得分评卷人签字复核人签字得分一、单项选择题（本大题共10小题，每小题2分，共20分）1. 顺序栈中压入元素时，是（ ）。A)先存入元素后移动指针B)先移动指针后存入元素C)无所谓谁先谁后 D)同时进行2. 线性表的顺序存储结构是一种（ ）的存储结构。 A) 随机存取 B) 顺序存取 C) 索引存取 D) HASH存取3. 若一个栈的输入序列是1,2,3n，输出序列的第一个元素是n，则第i个输出元素是（ ）

2、。A)不确定B)n-iC)n-i+1D)i4. 在以下的叙述中，正确的是（ ）。 A) 线性表的线性存储结构优于链表存储结构 B) 二维数组是它的每个数据元素为一个线性表的线性表C) 栈的操作方式是先进先出 D) 队列的操作方式是先进后出5. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（ ）。 A) bdgcefha B) gdbecfha C) bdgaechf D) gdbehfca6. 树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二

3、叉树叫做这棵树对应的二叉树。结论（ ）是正确的。 A) 树的先根遍历序列与其对应的二叉树的后序遍历序列相同 B) 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C) 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D) 树的后根遍历序列与其对应的二叉树的中序遍历序列相同7. 时间复杂度均为O(nlog2n)且不稳定的排序方法是（ ）。 A)快速排序 B)选择排序 C)归并排序 D)冒泡排序 8. 用邻接表存储的图的深度优先遍历算法类似于二叉树的（ ）。A)先序遍历 B)中序遍历C)后序遍历D)层次遍历9. 堆排序的时间复杂度为 （ ）。A)O(n2) B)O(log2n)C)O(n)

4、 D)O(nlog2n)10已知Huffman树的总结点数为m，叶子数为n。则m与n 的关系是 （ ）。 A) m = 2n + 1 B) m = n + 1 C) m = 2n 1D) m = n - 1得分二、填空题（本大题共20个空，每空2分，共40分）1在一个长度为n的线性表中删除第i个元素 (1in)，需向前移动 个元素。2. 下面程序段的时间复杂度是 。long i=1 , s=0.0; while (sn) s=s+i; i+; 3. 广义表(a，(a，b)，d，e，(h,(i，j)，k),g)深度是 。4. 用折半查找方法从长度为11的有序表中查找一个元素时，平均查找长度为 。

5、5连通无向图中有n个顶点e条边，进行最小生成树的prim算法时间复杂度是 。6图的广度优先遍历算法利用队列来完成，图的深度优先遍历算法利 来完成。7 一棵二叉排序树上按 方式进行遍历，会得到一个已排序好的结点序列。8线性表长度为n，排序码位数为d，基数为b，进行基数排序时间复杂度是 。9对长度为n的线性表进行分块查找，其ASL的最小值是 。10线性表长度为n，对其进行归并排序时间复杂度是 。以下为算法填空11二叉树用以下静态二叉链表作为存储结构#define n0 100 /数组最大下标#define datatype charstruct node datatype data; int lc

6、h,rch; /lch指向左子树，rch指向右子树 treen0+l;int root; /根结点指针 下面是先序遍历二叉树的非递算法。一维数组s作为栈，t为栈顶指针。void preorder（） int sn0+l,t= ; int p=root; while(p | ) if( p ) printf(“%c”, ) s+t= treep.rch; p= treep. ; else p=s ;12. 以下mergeSort是归并排序算法，merge是将两个相邻有序表归并的算法，mergepass是一趟归并的算法，填空完成算法。void meger(Element R, Element S,

7、 int a, int b, int c) int i=a, j=b+1, k=a; while( i=b & j=c ) if( Ri.keyRj.key ) Sk+=Ri+; else Sk+=Rj+; while(i=b)Sk+=Ri+; while(j=c)Sk+=Rj+;void megerPass(Element R, Element S, int m) int i=1; while( ) meger(R, S, i, i+m-1, i+2*m-1 ); i += ; if(i+m-1n) meger(R, S, ); else while( i=n) Si= ;void mege

8、rSort() Element Sn0+1; int m=1; while(mn) megerPass(R,S,m); m*=2; m*=2; 得分三、综合分析题（本大题共5小题，每小题8分，共40分）1假设用于通信的电文仅由8个字母 a， b， c， d， e， f, g, h 组成，各字母的使用频率分别为 16， 3， 9， 8， 4， 10, 5, 6请画出本问题的哈夫曼树（左孩子权值小于右孩子），并为这8个字母设计哈夫曼编码。(只写结果，不画出构造过程)2对下图所给的带权有向图执行dijkstra算法，求顶点v1到其余顶点的最短路径，试写出算法执行过程中辅助数组dist和path的变化情况，并写出最短路径结果。1521849236761954315 带权有向图123456 1进入第1组3有8个数：18，19，3，8，25，35，26，6 写出第一趟快速排序的分组过程。4有10个数：29, 38, 17，15，8，39，3，32，