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

《福建农林大学考试试卷 (a)卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、福建农林大学考试试卷（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

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

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

4、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(s

5、。6．图的广度优先遍历算法利用队列来完成，图的深度优先遍历算法利来完成。7．一棵二叉排序树上按方式进行遍历，会得到一个已排序好的结点序列。8．线性表长度为n，排序码位数为d，基数为b，进行基数排序时间复杂度是。9．对长度为n的线性表进行分块查找，其ASL的最小值是。10．线性表长度为n，对其进行归并排序时间复杂度是。以下为算法填空11．二叉树用以下静态二叉链表作为存储结构#definen0100//数组最大下标#definedatatypecharstructnode试题第8页(共8页){datatypedata;intlch,rch;//lch指向左子树，rch指向右子树}

6、tree[n0+l];introot;//根结点指针下面是先序遍历二叉树的非递算法。一维数组s作为栈，t为栈顶指针。voidpreorder（）{ints[n0+l],t=; intp=root;while(p

7、

8、)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,

9、j=b+1,k=a;while(i<=b&&j<=c)if(R[i].key