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

试题第1页(共8页)福建农林大学考试试卷（A）卷2007——2008学年第二学期课程名称：数据结构考试时间120分钟计算机科学技术专业2006年级班学号姓名题号一二三四五六七八九总得分得分评卷人签字复核人签字得分一、单项选择题（本大题共10小题，每小题2分，共20分）1.顺序栈中压入元素时，是（）。A)先存入元素后移动指针B)先移动指针后存入元素C)无所谓谁先谁后D)同时进行2.线性表的顺序存储结构是一种（）的存储结构。A)随机存取B)顺序存取C)索引存取D)HASH存取3.若一个栈的输入序列是1,2,3…n，输出序列的第一个元素是n，则第i个输出元素是（）。A)不确定B)n-iC)n-i+1D)i4.在以下的叙述中，正确的是（）。A)线性表的线性存储结构优于链表存储结构B)二维数组是它的每个数据元素为一个线性表的线性表C)栈的操作方式是先进先出D)队列的操作方式是先进后出5.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（）。A)bdgcefhaB)gdbecfhaC)bdgaechfD)gdbehfca6.树的基本遍历策略可分为先根遍历和后根遍历;二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论（）是正确的。A)树的先根遍历序列与其对应的二叉树的后序遍历序列相同B)树的后根遍历序列与其对应的二叉树的后序遍历序列相同C)树的先根遍历序列与其对应的二叉树的中序遍历序列相同D)树的后根遍历序列与其对应的二叉树的中序遍历序列相同7.时间复杂度均为O(nlog2n)且不稳定的排序方法是（）。A)快速排序B)选择排序C)归并排序D)冒泡排序8.用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。A)先序遍历B)中序遍历C)后序遍历D)层次遍历试题第2页(共8页)9.堆排序的时间复杂度为（）。A)O(n2)B)O(log2n)C)O(n)D)O(nlog2n)10．已知Huffman树的总结点数为m，叶子数为n。则m与n的关系是（）。A)m=2n+1B)m=n+1C)m=2n–1D)m=n-1得分二、填空题（本大题共20个空，每空2分，共40分）1．在一个长度为n的线性表中删除第i个元素(1≤i≤n)，需向前移动个元素。2.下面程序段的时间复杂度是。longi=1,s=0.0;while(sn){s=s+i;i++;}3.广义表(a，(a，b)，d，e，(h,((i，j)，k),g))深度是。4.用折半查找方法从长度为11的有序表中查找一个元素时，平均查找长度为。5．连通无向图中有n个顶点e条边，进行最小生成树的prim算法时间复杂度是。6．图的广度优先遍历算法利用队列来完成，图的深度优先遍历算法利来完成。7．一棵二叉排序树上按方式进行遍历，会得到一个已排序好的结点序列。8．线性表长度为n，排序码位数为d，基数为b，进行基数排序时间复杂度是。9．对长度为n的线性表进行分块查找，其ASL的最小值是。10．线性表长度为n，对其进行归并排序时间复杂度是。以下为算法填空11．二叉树用以下静态二叉链表作为存储结构#definen0100//数组最大下标#definedatatypecharstructnode{datatypedata;试题第3页(共8页)intlch,rch;//lch指向左子树，rch指向右子树}tree[n0+l];introot;//根结点指针下面是先序遍历二叉树的非递算法。一维数组s作为栈，t为栈顶指针。voidpreorder（）{ints[n0+l],t=;intp=root;while(p||)if(p){printf(“%c”,)s[++t]=tree[p].rch;p=tree[p].;}elsep=s[];}12.以下mergeSort是归并排序算法，merge是将两个相邻有序表归并的算法，mergepass是一趟归并的算法，填空完成算法。voidmeger(ElementR[],ElementS[],inta,intb,intc){inti=a,j=b+1,k=a;while(i=b&&j=c)if(R[i].keyR[j].key)S[k++]=R[i++];elseS[k++]=R[j++];while(i=b)S[k++]=R[i++];while(j=c)S[k++]=R[j++];}voidmegerPass(ElementR[],ElementS[],intm){inti=1;while(){meger(R,S,i,i+m-1,i+2*m-1);i+=;}if(i+m-1n)meger(R,S,);elsewhile(i=n)S[i]=;}voidmegerSort(){ElementS[n0+1];intm=1;while(mn){megerPass(R,S,m);m*=2;m*=2;}}试题第4页(共8页)得分三、综合分析题（本大题共5小题，每小题8分，共40分）1．假设用于通信的电文仅由8个字母a，b，c，d，e，f,g,h组成，各字母的使用频率分别为16，3，9，8，4，10,5,6请画出本问题的哈夫曼树（左孩子权值小于右孩子），并为这8个字母设计哈夫曼编码。(只写结果，不画出构造过程)试题第5页(共8页)2．对下图所给的带权有向图执行dijkstra算法，求顶点v1到其余顶点的最短路径，试写出算法执行过程中辅助数组dist和path的变化情况，并写出最短路径结果。带权有向图1234561进入第1组1584923761915152346试题第6页(共8页)3．有8个数：18，19，3，8，25，35，26，6写出第一趟快速排序的分组过程。试题第7页(共8页)4．有10个数：29,38,17，15，8，39，3，32，33，36初始化堆（要求成为大根堆），并写出前2趟堆排序的过程。试题第8页(共8页)5．将11个结点的关键字1，12，13，6，10，4,8,3,14,11，7顺序依次插入到一个平衡二叉排序树中，画出这一平衡二叉排序树的构造过程，并求出ASL。（原二叉树是一空树）