数据结构期中试卷信息11)2015-1-21161211

命题人或命题小组负责人签名：所（室、教研部）负责人签名：分院（部）领导签名：第1页（共4页）………………………………考试只是一时的测验，诚信是你一生的承诺………………………………………………………………………………………………………装订线……………………………………………………………嘉兴学院试卷2012—2013学年第1学期期中考试试卷课程名称：数据结构使用班级：信息11级考试形式：开卷试卷代码：班级：姓名：学号：题号一二三四五六七八总分得分评阅人一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题1分，共10分)1．数据的逻辑结构从形式上可用二元组（D，R）表示，其中R是（D）的有限集。A．算法B．数据元素C．数据操作D．数据关系2．数据结构课程研究的内容涉及到三个方面的内容，它们分别是数据的逻辑结构、数据的（C）和数据的操作。A．数据元素B．逻辑结构C．存储结构D．计算方法3．线性结构的顺序存储结构是一种随机存取的存储结构，而链式存储结构是一种（A）的存储结构。A．顺序存取B．随机存取C．索引存取D．散列存取4．线性表L在（B）情况下，最适合采用链式存储结构来实现算法。A．不需经常对L进行修改B．需经常对L进行删除和插入操作C．需经常修改L中结点值D．L中结点结构复杂5．在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（C）。A.O(1)B.O(log2n)C.O(n)D.O(n2)6．在循环顺序队列中，假设以设置一个计数变量num的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则下面不是队列判满或判空条件是（A）。A．front==rearB.front==rear&&num==0C.front==rear&&num0D.num==maxSize7．一个栈的入栈序列是a,b,c,d,e,则栈的不可能的出栈序列是（D）。A．abcdeB．decbaC．edcbaD．dceab8．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（C）。A．top==0B.top==-1C.top==maxSizeD.top==maxSize-19．设线性表有n个元素，严格说来，以下操作中，（B）在顺序表上实现比链表上实现比链表上实现效率更高。Ⅰ输出第i个（0≤i≤n-1）数据元素的值Ⅱ交换第3个数据元素与第4个数据元素的值Ⅲ顺序输出这n个数据元素的值A．ⅠB．Ⅰ、ⅡC．Ⅰ、ⅢD．Ⅱ、Ⅲ10.在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为s,则修改链的Java语句序列是（D）。A．s.setNext(p);q.setNext(s);B.p.setNext(s.getNext());s.setNext(p);C.q.setNext(s.getNext());s.setNext(p);D.p.setNext(s);s.setNext(q);二、填空题（20分，每空1分）1．算法的复杂度通常体现为时间复杂度和空间复杂度两个指标。2．设有函数T(n)=3n2-n+4，T(n)=O(n²)。3．要将一个顺序表{a0,a1,……,an-1}中第i个数据元素ai(0≤i≤n-1)删除，会引起n-1-i个数据元素的移动。4．队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为队尾，允许删除的一端称为队首。队列具有先进先出的特点。5．在一个单链表中删除p所指结点时，可执行如下操作：q=p.getNext();p.setData(q.getData());p.setNext(q.getNext());6．设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出栈的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是3。7．若双向链表的结点类描述为：publicclassDuLNode{pvivateObjectdata;privateDuLNodepiror;privateDuLNodenext;……}则在带头结点的双向链表中的p结点之前插入一个新结点s，其修改指针的java语句序列是：1）p.getPiror().setNext(s);2）s.setPiror(p.gettPiror());3）s.setNext(p);4）p.setPiror(s);8．在不带表头结点的链栈中，栈顶指针top直接指向栈顶元素，如果链栈中结点的类描述为：classNode{命题人或命题小组负责人签名：所（室、教研部）负责人签名：分院（部）领导签名：第2页（共4页）………………………………考试只是一时的测验，诚信是你一生的承诺………………………………………………………………………………………………………装订线……………………………………………………………privateObjectdata;privateNodenext:……}则将一个新结点p入栈时修改链的两个对应语句是：1）p.setNext(top);2）top=p;9．如果循环顺序队列类的描述如下：classCircleSqQueeu{pvivateObject[]queueElem;//队列的存储空间pvivateintfront;pvivateintrear;……}假设以少用一个存储单元的方法来区分队列判满和判空的条件，其中front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是(rear-front+queueElem.length)%queueElem.length。10．在顺序存储、链式存储、索引存储和散列存储这4种存储方式中，最基本、最常用的两种存储结构是顺序存储和链式存储。11．按数据元素的逻辑关系来系，数据结构可分为四种：线性表、集合、树和图。其中图型结构中的数据元素之间存在“多对多”的关系。12.栈元素存储在数组stackElem中，假设栈顶指针top是指向栈顶元素的下一个存储单元，则顺序栈判空的条件是top==0；栈顶元素的访问形式是stackElem[top-1]。三、判断题（共10分，2分1题，对的打“√”，错的打“×”）1.线性表中数据元素的逻辑顺序与存储顺序总是一致的。（×）2．链式存储时，存储区域可以连续，也可以不连续。（√）3．删除顺序表中第0个数据元素a0的时间复杂度是O(n)。（√）4．判断一个链栈为空的条件件是表达式top==null的值为真。（√）5．双向循环链表中，任意一结点的后继指针均指向其逻辑后继。（×）四、应用与计算题（共26分）1．求下列程序段的时间复杂度。（9分）（1）for(i=0;in;i++)for(j=0;ji;j++)A[i][j]=0;时间复杂度是：O(n²)（2）a=0;b=1;for(i=0;i=n;i++){s=a+b;b=a;a=s;}时间复杂度是：O(n)（3）a=1;m=1;while(an){m+=a;a*=3;}时间复杂度是：O(log3n)2.设有数据的逻辑结构的二元组定义形式为B=(D,R)，其中D={a0,a1,…,an-1}，R={ai,ai+1|i=0,1,…，n-2}，请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。(共6分)a0a1……ai-2ai-1……an-13．对线性表A=（11,22,33,44,55），画出下列存储结构的示意图：（共6分）（1）带表头结点的单链表；（2）不带表头结点的单向循环链表；（3）带表结点的双向循环链表。a1a0a2an-1^…112255^3344head112255^3344head22334455^11head命题人或命题小组负责人签名：所（室、教研部）负责人签名：分院（部）领导签名：第3页（共4页）………………………………考试只是一时的测验，诚信是你一生的承诺………………………………………………………………………………………………………装订线……………………………………………………………4.建立链栈的基本思想是从空栈开始依次将入栈元素结点插入到栈顶。假设依次入栈的元素为23、17、28、69、11，请画出将各元素结点分别入栈后的链栈示意图。（5分）五、根据以下各题的要求，分别写出相应的算法（用Java语言描述）。（共34分）1．编写一个顺序表类的成员函数，实现对顺序表就地逆置的操作。（8分）已知顺序表类的描述为：classSqList{privateObject[]listElem;privatintcurLen;……}[参考答案]：（方法不唯一）publicvoidnizhi(SqListL){Objecttemp;for(inti=0;icurLen/2;i++){temp=listElem[i];listElem[i]=listElem[curLen-i-1];listElem[curLen-i-1]=temp;}}2．编写一个单链表类的成员函数，实现在非递减的有序单链表中插入一个整数值为x的数据元素，并使单链表仍保持有序的操作。（8分）已知单链表中的结点类和单链表类分别描述如下：classNode{//链表中的结点类privateObjectdata;privateNodenext;publicNode(Objectdata){//构造函数：构造一个数据域值为data为结点this.data=data;this.next=null;}……}clsssLinkList(){//单链表类privateNodehead;……}[参考答案]：（方法不唯一）publicvoidcharu(intx){Nodep=head.getNext();Nodeq=head;inttemp;while(p!=null){temp=((Integer)p.getData()).intValue();if(tempx){q=p;p=p.getNext();}elsebreak;}Nodes=newNode(x);s.setNext(p);q.setNext(s);}3．编写一个函数判断一个字符序列是否为回文序列，所谓回文序列就是正读与反读都相同的字符序列，例、如：abba和abdba均是回文序列。要求只借助栈来实现。[参考答案]：（方法不唯一）publicBooleanisPalindSeq(Stringstr){LinkStacks=newLinkStack;for(inti=0;istr.length();i++)s.push(str.charAt(i));for(inti=0;istr.length();i++){charc=((Character)S.pop()).charValue();if(c!=str.charAt(i))returnfalse;}23^1169281723^1723^281723^69281723^toptoptoptoptop命题人或命题小组负责人签名：所（室、教研部）负责人签名：分院（部）领导签名：第4页（共4页）………………………………考试只是一时的测验，诚信是你一生的承诺………………………………………………………………………………………………………装订线……………………………………………………………Returntrue;}4.假设采用带头结点的循环链表来表示队列，并且只设一个指向队尾元素的指针（不设队首指针），试编写相应的队列置空、队列判空、入队和出队操作的成员函数。（10分）已知用队尾指针标识的循环链队列的类描述如下:classCircleLinkQueue{privateNoderear;