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页)


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

数据结构期中试卷信息11)2015-1-21 16.12.11 - 诚信是你一生

数据结构期中试卷答案信计11.doc

嘉兴学院试卷 2012 2013 学年第 2 学期期中考试试卷 课程名称:数据结构 使用班级:信计 11 级 考试形式:闭卷 姓名:___学号:___ 9.从数据结构来看,串是...

数据结构期中试卷及答案.doc

数据结构期中试卷及答案_英语_高中教育_教育专区。一...不分顺序 11. 栈和队列的共同点是( C )。 A....没有共同点 12.在个链队列中,假定 front 和 ...

《数据结构》期中试卷-2015-2016学年第一学期(1).doc

数据结构期中试卷-2015-2016学年第一学期(1)_...6. 11. 2. 7. 12. 3. 8. 13. 4. 9. ...循环链表 11、下面关于串的的叙述中,哪一个是不...

数据结构期中试题及参考答案.doc

1 四 学期 数据结构期中试卷 ( 闭卷) 五六七八...一 二 一、单项选择题(本大题共 12 小题,每小...D.11 11.若非连通无向图 G 含有 21 条边,则 ...

数据结构期中考试答案.pdf

数据结构期中考试答案_电子/电路_工程科技_专业资料。《数据结构》期中考试试卷...11. 串的链式存储结构包括 链。 (17) 单字符结点链 和 (18) 块 12. ...

《数据结构》期中试题(有答案).doc

数据结构期中试题 试卷类别:闭卷 专业: 题号 ...1 2 3 4 5 6 7 8 9 10 11 12 13 14 15...(共 9 页第- 3 -页) 答:30、24、16、10、2...

数据结构期中试卷.pdf

数据结构期中试卷_工学_高等教育_教育专区。针对复旦...21},选择第个元素 28 进行划分,写出其 快速排序...=r[j+1]; r[j+1]=t; } i++; } } 11 ...

数据结构期中试卷及答案_201104.pdf

数据结构期中试卷及答案_201104_理学_高等教育_教育...21},选择第个元素 28 进行划分,写出其 快速排序...=r[j+1]; r[j+1]=t; } i++; } } 11 ...

《数据结构》期中试卷-2014-2015学年第二学期.pdf

数据结构期中试卷-2014-2015学年第二学期_数学_初中教育_教育专区。此处不...循环链表 11、下面关于串的的叙述中,哪一个是不正确的?() A.串是字符的...

数据结构期中试卷(信息技术学院).doc

数据结构期中试卷(信息技术学院)_工学_高等教育_教育专区。浙江中医药大学信息...(共 7 页) 7 8 9 10 11 12 13 14 15 5、线性表存储在带头结点的...

《数据结构》期中试卷.doc

数据结构期中试卷 班级 姓名 学号 成绩 一、选择题(每个空只有一个正确答案,将其找出来,打上√)[每题 1 分,共 20 分] 1数据结构门研究非数值...

数据结构(本)期末综合练习(2015年11月).pdf

数据结构(本)期末综合练习 201511 月综合练习一一、单项选择题 1.

《算法与数据结构》-期中试卷.doc

5 A 6 A 7 A 8 C 9 A 10 C 11 D 12 A 13 B 14 B 15 C 1. ...2014-2015 下 计算机学院《算法与数据结构期中试卷 第 4 页,共 17 页 2)...

数据结构试题2011答案.pdf

120? 分钟 数据结构试题题号 分数 1.考试形式:闭...21 15. 对组数据(2,12,16,88,5,10)进行...? ? ? ? 11? 12 27? 53? 2? 31? 19? 20...

北京师范大学12-13-数据结构试卷-A+答案.doc

数据结构考试时长: 120 分钟 专业: 学号: 任课教师姓名: 刘玉铭 考试类别:闭...1 0.16 D 101 B 11 weight 0.10 0.34 0.08 0.16 0.20 0.12 0....

数据结构期中试卷.doc

数据结构期中试卷_理学_高等教育_教育专区。孝感学院...11 12 13 14 15 16 17 18 19 20 1 2 3 1...10. 11. 12. 13. 如某线性表最常用的操作是...

数据结构(本)期末综合练习(2015年11月).doc

数据结构(本)期末综合练习 201511 月综合练习一一、单项选择题 1.

2015年11月期中化学试卷(附答案).doc

201511期中化学试卷(附答案)_理化生_高中教育_...非选择题[第 16 题~第 21 题,共 80 分]两...可能用到的相对原子质量:H-1 C-12 O-16 Na-23...

2014-2015-1福建师范大学软件学院数据结构试卷A卷.doc

2014-2015-1福建师范大学软件学院数据结构试卷A卷_工学_高等教育_教育专区。...11} 6.二叉树中第 5 层上的结点个数最多为( ) A.8 B.15 C.16 D....