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

浙江财经学院东方学院课程期末考试试卷第2页，共6页专业、班级：学号：姓名：密封线浙江财经学院东方学院2010～2011学年第一学期专业、班级：学号：姓名：密封线《数据结构》课程期末考试试卷（A卷）考核方式：闭卷考试日期：2010年月日适用专业、班级：东方电子商务专业题号一二三四五六总分得分评卷人（共六大题）说明：请考生将答案写在答题纸上；考试时间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／2C．n(n+1)D.n(n+1)/23..下面算法的时间复杂度为(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)6假定利用数组a顺序存储一个栈，用top表示栈顶指针，top-=-1表示栈空，并已知栈不为空，当退栈并返回栈顶元素时所执行的操作为(B)。A.returna[--top];B.returna[top--];C.rcturna[++top];D.returna[top++];7若让元素1．2.3依次进栈．则出栈次序不可能出现(C)的情况。A3.2.1B.2,1,3C.3,1,2D.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在对n个元素进行直接选择排序的过程中．需要进行(C)趟选择和交换。AnB．n+lC．n-lD．n/2二、填空题（每空1分，共15分）1算法可用文字、高级程序设计语言或类同于高级程序设计语言的伪码______描述2．数据的物理存储结构分为顺序和____链式_______二种。3当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_______________排序4一个算法的时间复杂度为(n3+n2log2n+14n)/n，其数量级表示为_____。5任何集合框架都包含三大块内容：对外的接口、_____接口的实现和对集合运算的算法。6设有6个结点的无向图，该图至少应有______条边才能确保是一个连通图。7List接口对Collection进行了简单的扩充，它的具体实现类常用的有ArrayList和_____LinkedList8若一个过程直接地或间接地调用自己,则称这个过程是_____递归的过程9若某完全二叉树的高度为h，则该完全二叉树中至少有______个结点10对一棵二叉搜索树进行前序遍历时，得到的结点序列是一个__________序列。三、综合题（每小题6分，共30分）已知一棵二叉树的前序遍历的结果序列是ABDEGCFH，中序遍历的结果是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(s1); } 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(m×n)，假定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;//list的表头指针赋给p，并保存到headNodeq=p.next;//使q指向第1个元素结点,p为q的前驱while(q!=head){//从头到尾依次扫描每个结点