kl800.com省心范文网

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


诚信是你一生的承诺??????????????? ????????????考试只是一时的测验,

????????????????????????装订线???????????????????????

嘉 兴 学 院 试 卷
2012— 2013 学 年 第 1 学 期 期 中 考 试 试 卷
课程名称:数据结构 使用班级:信息 11 级 考试形式:开卷 试卷代码:

班级: 题号 得分 评阅人 一 二 三

姓名: 四 五 六

学号: 七 八 总分

8.在顺序栈中,若栈顶指针 top 指向栈顶元素的下一个存储单元,且顺序栈的最大容量是 maxSize。则顺 序栈的判满的条件是( C ) 。 A.top = =0 B.top= =-1 C. top = =maxSize D.top = = maxSize-1 9.设线性表有 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 2.设有函数 T (n)=3n -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.若双向链表的结点类描述为: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 {

一、单项选择题(在每小题的四个备选答案中,选出一个正确答案,并将正确答案的序号填 在题干的括号内。每小题 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 ) 。 2 A. O(1) B. O(log2n) C. O(n) D. O(n ) 6.在循环顺序队列中,假设以设置一个计数变量 num 的方法来区分队列判满和判空的条件,front 和 rear 分别为队首和队尾指针,它们分别指向队首元素和队尾元素的下一个存储单元,队列的最大存储容量 为 maxSize,则下面不是队列判满或判空条件是( A ) 。 A.front==rear B. front= =rear && num==0 C. front= =rear && num>0 D. num= =maxSize 7.一个栈的入栈序列是 a, b, c, d, e, 则栈的不可能的出栈序列是 ( D ) 。 A.abcde B.decba C.edcba D.dceab

命题人或命题小组负责人签名:

所(室、教研部)负责人签名:

分院(部)领导签名:



1

页 (共

4页)

诚信是你一生的承诺??????????????? ????????????考试只是一时的测验,

????????????????????????装订线???????????????????????

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 ;栈顶元素的访问形式是 stackElem[top-1] 。

(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 分)

a0
a0

a1

??

ai-2
a2

ai-1


??

an-1

a1

an-1

^

三、判断题(共 10 分,2 分 1 题,对的打“√”,错的打“×”)
1. 线性表中数据元素的逻辑顺序与存储顺序总是一致的。 2.链式存储时,存储区域可以连续,也可以不连续。 3.删除顺序表中第 0 个数据元素 a0 的时间复杂度是 O(n)。 4.判断一个链栈为空的条件件是表达式 top= =null 的值为真。 5.双向循环链表中,任意一结点的后继指针均指向其逻辑后继。 ( ( ( ( (

× √ √ √ ×

) ) ) ) )

3.对线性表 A=(11, 22, 33, 44,55) ,画出下列存储结构的示意图: (共 6 分) (1)带表头结点的单链表; (2)不带表头结点的单向循环链表; (3)带表结点的双向循环链表。 head 11 head 11 22 33 44 55
^

22

33

44

55

^

四、应用与计算题(共 26 分)
1. 求下列程序段的时间复杂度。 (9 分) (1) for (i=0; i<n; i++) for (j=0; j<i; 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)

head

11

22

33

44

55

^

命题人或命题小组负责人签名:

所(室、教研部)负责人签名:

分院(部)领导签名:



2

页 (共

4页)

诚信是你一生的承诺??????????????? ????????????考试只是一时的测验,

????????????????????????装订线???????????????????????

4. 建立链栈的基本思想是从空栈开始依次将入栈元素结点插入到栈顶。 假设依次入栈的元素为 23、 17、 28、 69、11,请画出将各元素结点分别入栈后的链栈示意图。 (5 分) top 23 ^

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; }

top

17

23

^

top

28

17

23

^

top

69

28

17

23

^

top

11

69

28

17

23

^

五、 根据以下各题的要求,分别写出相应的算法(用 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=listElem[i]; listElem[i]=listElem[curLen-i-1]; listElem[curLen-i-1]=temp; } } 2. 编写一个单链表类的成员函数, 实现在非递减的有序单链表中插入一个整数值为 x 的数据元素, 并使单 链表仍保持有序的操作。 (8 分) 已知单链表中的结点类和单链表类分别描述如下: class Node { //链表中的结点类 private Object data; private Node next; public Node(Object data){ //构造函数:构造一个数据域值为 data 为结点

命题人或命题小组负责人签名:

所(室、教研部)负责人签名:

分院(部)领导签名:



3

页 (共

4页)

Return true;

rear.getNext().setNext(p.getNext());// return p.getData(); } }

诚信是你一生的承诺??????????????? ????????????考试只是一时的测验,

????????????????????????装订线???????????????????????

} 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

命题人或命题小组负责人签名:

所(室、教研部)负责人签名:

分院(部)领导签名:



4

页 (共

4页)


赞助商链接