嘉兴学院试卷
2011—2012 学年第1 学期期中考试试卷课程名称：数据结构使用班级：信息11级考试形式：开卷试卷代码：
班级：姓名：学号：
一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题1分，共10分)
1．数据的逻辑结构从形式上可用二元组（D，R）表示，其中R是的有限集。
A．算法B．数据元素C．数据操作D．数据关系
2．数据结构课程研究的内容涉及到三个方面的内容，它们分别是数据的逻辑结构、数据的和数据的操作。
A．数据元素B．逻辑结构C．存储结构D．计算方法
3．线性结构的顺序存储结构是一种随机存取的存储结构，而链式存储结构是一种的存储结构。 A．顺序存取 B．随机存取 C．索引存取 D．散列存取
4．线性表L在情况下，最适合采用链式存储结构来实现算法。
A．不需经常对L进行修改 B．需经常对L进行删除和插入操作
C．需经常修改L中结点值 D．L中结点结构复杂
5．在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是。
A.O(1)
B. O(log2n)
C. O(n)
D. O(n2)
6．在循环顺序队列中，假设以设置一个计数变量num的方法来区分队列判满和判空的条件，front和rear 分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则下面不是队列判满或判空条件是（）。
A．front==rear B. front= =rear && num==0
C. front= =rear && num>0
D. num= =maxSize
7．一个栈的入栈序列是a, b, c, d, e, 则栈的不可能的出栈序列是。
A．abcde B．decba C．edcba D．dceab 8．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是。
A．top = =0 B.top= =-1 C. top = =maxSize D.top = = maxSize-1
9．设线性表有n个元素，严格说来，以下操作中，（）在顺序表上实现比链表上实现比链表上实现效率更高。
Ⅰ输出第i个（0≤i≤n-1）数据元素的值
Ⅱ交换第3个数据元素与第4个数据元素的值
Ⅲ顺序输出这n个数据元素的值
A．Ⅰ B．Ⅰ、Ⅱ C．Ⅰ、Ⅲ D．Ⅱ、Ⅲ
10. 在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为s,则修改链的Java语句序列
是（）。
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 ( )。
3．要将一个顺序表{a0,a1,……,a n-1}中第i个数据元素a i(0≤i≤n-1)删除，会引起个数据元素的移动。
4．队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为，允许删除的一端称为。队列具有的特点。
5．在一个单链表中删除p所指结点时，可执行如下操作：
q=p.getNext(); p.setData(q.getData());p.setNext( );
6．设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出栈的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是。
7．若双向链表的结点类描述为：public class DuLNode {
pvivate Object data;
private DuLNode piror;
private DuLNode next;
……
}
则在带头结点的双向链表中的p结点之前插入一个新结点s，其修改指针的java语句序列是：
1）
2）
3）
4）
8．在不带表头结点的链栈中，栈顶指针top直接指向栈顶元素，如果链栈中结点的类描述为：
class Node {
命题人或命题小组负责人签名：所（室、教研部）负责人签名：分院（部）领导签名：
private Object data;
private Node next:
…… }
则将一个新结点p入栈时修改链的两个对应语句是：
1）
2）
9．如果循环顺序队列类的描述如下：
class CircleSqQueeu {
pvivate Object[ ] queueElem; //队列的存储空间
pvivate int front;
pvivate int rear;
……}
假设以少用一个存储单元的方法来区分队列判满和判空的条件，其中front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是。
10．在顺序存储、链式存储、索引存储和散列存储这4种存储方式中，最基本、最常用的两种存储结构是
和。
11．按数据元素的逻辑关系来系，数据结构可分为四种：线性表、集合、树和图。其中图型结构中的数据元素之间存在“”的关系。
12. 栈元素存储在数组stackElem中，假设栈顶指针top是指向栈顶元素的下一个存储单元，则顺序栈判
空的条件是；栈顶元素的访问形式是。
三、判断题（共10分，2分1题，对的打“√”，错的打“×”）
1. 线性表中数据元素的逻辑顺序与存储顺序总是一致的。（）
2．链式存储时，存储区域可以连续，也可以不连续。（）
3．删除顺序表中第0个数据元素a0的时间复杂度是O(n)。（）
4．判断一个链栈为空的条件件是表达式top= =null的值为真。（）
5．双向循环链表中，任意一结点的后继指针均指向其逻辑后继。（）
四、应用与计算题（共26分）
1．求下列程序段的时间复杂度。（9分）
（1）for (i=0; ifor (j=0; jA[i][j]=0;
时间复杂度是：
（2）a=0;b=1;
for (i=0;i<=n; i++)
{ s=a+b;
b=a;
a=s;
}
时间复杂度是：
（3）a=1; m=1;
while(a{
m+=a; a*=3;
}
时间复杂度是：
2.设有数据的逻辑结构的二元组定义形式为B=(D,R)，其中D={a0,a1,…,a n-1}，R={| i=0,1,…，n-2}，
请画出此逻辑结构对应的顺序存储结构和链式存储结构的示意图。(共6分)
3．对线性表A=（11, 22, 33, 44,55），画出下列存储结构的示意图：（共6分）
（1）带表头结点的单链表；
（2）不带表头结点的单向循环链表；
（3）带表结点的双向循环链表。
4. 建立链栈的基本思想是从空栈开始依次将入栈元素结点插入到栈顶。假设依次入栈的元素为23、17、28、
69、11，请画出将各元素结点分别入栈后的链栈示意图。（5分）
命题人或命题小组负责人签名：所（室、教研部）负责人签名：分院（部）领导签名：
