(完整word版)《数据结构》课程期末考试试卷(A卷)DAOAN-副本

题号一题号一二三四五六总分得分评卷人(共六大题)浙江财经学院东方学院2010〜2011学年第一学期《数据结构》课程期末考试试卷(A卷)考核方式：闭卷 考试日期：2010年月日适用专业、班级：东方电子商务专业说明：(1)请考生将答案写在答题纸上；(2)考试时间120分钟；一、单选题(每题1分，共15分)1、对一个算法的评价，不包括如下( )方面的内容。A.健壮性B.可读性C.正确性D.实用性2执行下面程序段时，s语句的执行次数为(D)。for(inti=l;i<=n;i++)For(intj=1;j<=i;j++)S;A.n2B.N2/2 C.n(n+1)D.n(n+1)/2面算法的时间复杂度为(B)intf(intn){if(n==0||n==l)return1.Elsereturnn*f(n-l);A.O(1)B.O(n)C.O(n2)DO(n!)4、在一个长度为n的顺序存储的线性表中，删除第i个元素(1&i&n)时，需要从前向后依次前移(A)个元素。A.n-iB.n-i+1C.n-i-lD.i5若一个结点的引用为p,在p结点后面插入一个值为x的新结点的操作为(D)。A.p=newNode(x,p)B.p=newNode(x,p.next)

C.p.next=newNode(x,p)D.p.next=newNode(x,p.next)假定利用数组a顺序存储一个栈，用top表示栈顶指针，top-=-1表示栈空,并已知栈不为空，当退栈并返回栈顶元素时所执行的操作为 （B）。A.returna[--top]; B.returna[top--];C.returna[++top];D.returna[top++];7若让元素1.2.3依次进栈.则出栈次序不可能出现（C）的情况。A3.2.1 B.2,1,3 C.3,1,2 D.1.3,28假定一个顺序队列的队首和队尾指针分别为 f和r,则判断队空的条件为（D ）。A.f+1==rB.r+l==fC.f-==0D.f==r9在一个顺序队列中，队首指针指向队首元素的（A）位置。A.前一个B.后一个C.当前D.前2个10树中所有结点的度等于所有结点数加（C）。A.0B.1C.-1D.211在一棵具有35个结点的完全二叉树中，该树的深度为（A）。A.6B.7C.5D.812在一棵具有n个结点的二叉树的第i层上，最多具有（C）个结点。A.2iB.2i+1C.2i-1D.2n13n个顶点的连通图至少包含有（A）条边。A.n-lB,nC.n+114为了实现图的广度优先搜索遍历.其广度优先搜索算法使用的一个辅助数据结构为（B）。A.栈B.队列二叉树D.树15在又tn个元素进行直接选择排序的过程中.需要进行 （C）趟选择和交换。n-ln/2n-ln/2浙江财经学院东方学院课程期末考试试卷浙江财经学院东方学院课程期末考试试卷第第页，共7页二、填空题（每空1分，共15分）1算法可用文字、高级程序设计语言或类同于高级程序设计语言的伪码 描述2.数据的物理存储结构分为顺序和―链式二种。3当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用 4一个算法的时间复杂度为（n3+n210g2n+14n）/n,其数量级表示为。5任何集合框架都包含三大块内容：对外的接口、 接口的实现和对集合运算的算法。6设有6个结点的无向图，该图至少应有 条边才能确保是一个连通图。7List接口对Collection进行了简单的扩充，它的具体实现类常用的有ArrayList和LinkedList8若一个过程直接地或间接地调用自己,则称这个过程是 递归的过程9若某完全二叉树的高度为h,则该完全二叉树中至少有个结点10对一棵二叉搜索树进行前序遍历时， 得到的结点序列是一个 序列。三、综合题（每小题6分，共30分）.已知一棵二叉树的前序遍历的结果序列是 ABDEGCF片序遍历的结果是DBGEACHF式画出这棵二叉树并写出这棵二叉树的后序遍历结果。 DGEBHFCA.请写出右图的邻接矩阵、邻接表和边集数组.设一个关键字序列为｛26,53,67,48,57,13,48,32,60,50｝分别写出直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、归并排序的前二趟的排序序列...分别用purim算法和构造右图的最小生成树并写出构造过程.四、程序填空（每空格2分，共20分）1下面十进制转二进制的算法.请在空白处填入适当的内容。publicclassbinary{publicstaticvoidwriteBinary(intn,Strings1){if(n<0)① thrownewIllegalArgumentException();if(n<=1){s1=1+s1;System.out.println(sl);}else{s1=② n%2+s1;③writeBinary(n/2,s1);}23下面是栈的类定义，请在空白处填入适当的内容publicclassStack{inttop=-1;intsize=0;Object口arr;publicStack(intcapacity){arr=new①Object[capacity];}publicvoidpush(Objecte){top++;arr[top]=②e;size++;}publicObjectpop(){Objectt=arr[top];top--；size--;returnt;}…}五、算法分析和设计题(共20分)1、指出下列算法的功能并求出其时间复杂度intCount(int[][]a,intk){intc=0;for(inti=0;i<a.length;i++)for(intj=0;j<a[i].length;j++)If(a[i][i]>=k)c++；returnc;}统计并返回二维数组a中大于等于k的元素的个数。时间复杂度为 O(mxn)，假定m和n分别表示二维数组a的行数和列数2指出下列算法的功能并写出运行结果publicclassTestPrime{publicstaticvoidmain(stringargs口) {inti,j;For(i=3;i<=30;i++){For(j=2;j<i;j++);{If(i%j==0){Bresk;}}If((j<i){Continue;

}System.out.print(i+"")}}}3编写一个函数，要求借助一个栈把一个数组中的元素逆置PublicstaticObject口ReverseArray(Object口array)PublicstaticObject口ReverseArray(Object口array){if(array==null||array.length==0)returnarray;Stackstack=newStack(array.length);for(inti=0;i<array.length;i++)stack.push(array[i]);for(inti=0;i<array.length;i++)array[i]=stack.pop();returnarray;)4从链接存储的线性表list中删除与obj相同的所有元素

publicstaticvoiddeleteAll(linkListlist,Objectobj){ // 从参数线性表list中删除与obj相同的所有元素Nodep=list.prior(),head=p;//listNodeq=p.next; //while(q!=head){ //if(q.element.equals(obj