数据结构期中试卷信息11)2015-1-21-16.12.11(4页).doc

-数据结构期中试卷信息11)2015-1-21-16.12.11-第 4 页嘉兴学院试卷 20122013 学年第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中结点值 DL中结点结构复杂5在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ C ） 。A. O(1) B. O(log2n) C. O(n) D. O(n2)6在循环顺序队列中，假设以设置一个计数变量num的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则下面不是队列判满或判空条件是（ A ）。 Afront=rear B. front= =rear && num=0C. front= =rear && num>0 D. num= =maxSize7一个栈的入栈序列是a, b, c, d, e, 则栈的不可能的出栈序列是 （ D ）。 Aabcde Bdecba Cedcba Ddceab8在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ C ）。 Atop = =0 B.top= =-1 C. top = =maxSize D.top = = maxSize-19设线性表有n个元素，严格说来，以下操作中，（ B ）在顺序表上实现比链表上实现比链表上实现效率更高。 输出第i个（0in-1）数据元素的值 交换第3个数据元素与第4个数据元素的值 顺序输出这n个数据元素的值A B、 C、 D、10. 在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为s,则修改链的Java语句序列是（ D ）。As.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(0in-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若双向链表的结点类描述为：public class DuLNode pvivate Object data; private DuLNode piror; private DuLNode next;则在带头结点的双向链表中的p结点之前插入一个新结点s，其修改指针的java语句序列是： 1） p.getPiror().setNext(s); 2） s.setPiror(p.gettPiror(); 3） s.setNext(p); 4） p.setPiror(s); 8在不带表头结点的链栈中，栈顶指针top直接指向栈顶元素，如果链栈中结点的类描述为： class Node private Object data; private Node next:则将一个新结点p入栈时修改链的两个对应语句是： 1） p.setNext(top); 2） top=p; 9如果循环顺序队列类的描述如下： class CircleSqQueeu pvivate Object queueElem; /队列的存储空间 pvivate int front; pvivate int rear; 假设以少用一个存储单元的方法来区分队列判满和判空的条件，其中front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是 (rear-front+queueElem.length)%queueElem.length 。10在顺序存储、链式存储、索引存储和散列存储这4种存储方式中，最基本、最常用的两种存储结构是顺序存储 和 链式存储 。11按数据元素的逻辑关系来系，数据结构可分为四种：线性表、集合、树和图。其中图型结构中的数据元素之间存在“ 多对多 ”的关系 。 12. 栈元素存储在数组stackElem中，假设栈顶指针top是指向栈顶元素的下一个存储单元，则顺序栈判空的条件是 top= =0 ；栈顶元素的访问形式是 stackElemtop-1 。三、判断题（共10分，2分1题，对的打“”，错的打“×”）1. 线性表中数据元素的逻辑顺序与存储顺序总是一致的。 （ × ）2链式存储时，存储区域可以连续，也可以不连续。 （ ）3删除顺序表中第0个数据元素a0的时间复杂度是O(n)。 （ ）4判断一个链栈为空的条件件是表达式 top= =null的值为真。 （ ）5双向循环链表中，任意一结点的后继指针均指向其逻辑后继。 （ × ）四、应用与计算题（共26分）1 求下列程序段的时间复杂度。（9分）（1） for (i=0; i<n; i+) for (j=0; j<i; j+) Aij=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(a<n) 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分)a0a1ai-2ai-1an-1a1a0a2an-1 3对线性表A=（11, 22, 33, 44,55），画出下列存储结构的示意图： （共6分）（1）带表头结点的单链表；（2）不带表头结点的单向循环链表；（3）带表结点的双向循环链表。112255 3344head112255 3344head 22 33 44 55 11head4. 建立链栈的基本思想是从空栈开始依次将入栈元素结点插入到栈顶。假设依次入栈的元素为23、17、28、69、11，请画出将各元素结点分别入栈后的链栈示意图。（5分）top23 top1723 top281723 top69281723 top23 11692817五、 根据以下各题的要求，分别写出相应的算法（用Java语言描述）。（共34分）1 编写一个顺序表类的成员函数，实现对顺序表就地逆置的操作。（8分） 已知顺序表类的描述为：class SqList private Object listElem; privat int curLen;参考答案：（方法不唯一）public void nizhi(SqList L) Object temp; for(int i=0;i<curLen/2;i+) temp=listElemi; listElemi=listElemcurLen-i-1; listElemcurLen-i-1=temp;2编写一个单链表类的成员函数，实现在非递减的有序单链表中插入一个整数值为x的数据元素，并使单链表仍保持有序的操作。（8分）已知单链表中的结点类和单链表类分别描述如下：class Node /链表中的结点类 private Object data; private Node next;public Node(Object data) /构造函数：构造一个数据域值为data为结点 this.data=data; this.next=null; clsss LinkList() /单链表类 private Node head;参考答案：（方法不唯一） public void charu(int x) Node p=head.getNext(); Node q=head; int temp; while(p!=null) temp=(Integer)p.getData().intValue(); if(temp<x) q=p; p=p.getNext(); else break; Node s=new Node(x); s.setNext(p); q.setNext(s);3编写一个函数判断一个字符序列是否为回文序列，所谓回文序列就是正读与反读都相同的字符序列，例、如：abba和abdba均是回文序列。要求只借助栈来实现。参考答案：（方法不唯一）public Boolean isPalindSeq(String str) LinkStack s=new LinkStack; for(int i=0;i<str.length();i+) s.push(str.charAt(i); for(int i=0;i<str.length();i+) char c=(Character)S.pop().charValue(); if(c!=str.charAt(i) return false; Return true;4. 假设采用带头结点的循环链表来表示队列，并且只设一个指向队尾元素的指针（不设队首指针），试编写相应的队列置空、队列判空、入队和出队操作的成员函数。（10分）已知用队尾指针标识的循环链队列的类描述如下:class CircleLinkQueue private Node rear;/ 循环链队列的尾指针参考答案：（方法不唯一）队列置空： public void clear() rear.setNext(rear);队列判空：public Boolean isEmpty() return rear=rear.getNext();入队操作： void offer ( Object x) Node p= new Node(x); p.setNext(rear.getNext(); rear.setNext(p); rear=p;出队操作：Object poll() if (rear.getNext()=rear) return null; else Node p = rear.getNext().getNext(); if (p=rear) rear=rear.getNext(); rear.setNext(rear); else rear.getNext().setNext(p.getNext();/ return p.getData();