《数据结构与算法分析(java版)》期中考试试卷

数据结构与算法分析（Java版）期中考试试题

一、填空题（每空2分，共10分）

1．数据的逻辑结构分为：

A.线性结构、图结构

B.顺序结构、链式存储结构

C.线性结构、树结构和图结构

D.顺序结构、树结构和图结构

2．哪种结构中，每个数据元素可有零个或若干个前驱数据元素和零个或若干个后继数据元素。

A.线性结构

B.顺序结构

C. 树结构

D.图结构

3．线性表删除第i个数据元素时：

A. 从第i个数据元素起以后的所有数据元素依次后移

B. 从第i个数据元素起以后的所有数据元素依次前移

C. 从第(i+1)个数据元素起以后的所有数据元素依次后移

D. 从第(i+1)个数据元素起以后的所有数据元素依次前移

4．堆栈的运算是按照（）的原则进行的。

A.LIFO

B.LILO

C.FIFO

D.都不正确

5．顺序循环队列会出现“假溢出”问题，在入队操作时，下列哪个运算可以解决这个问题。

A.rear=（rear+1）% maxsize

B. front=（front+1）% mixsize

C. rear=（front+1）% maxsize

D. front=（rear+1）% maxsize

二、填空题（每空2分，共20分）

1．数据结构是研究__________、__________以及__________的一门学科。

2. 数据的逻辑结构又称____________,数据的存储结构又称___________。

3．线性表按照存储结构的不同可分为_________和_________。

4．顺序循环队列的队空和队满问题的解决方法有三个，分别是：____________、____________和____________。

三、简答题（每题4分，共16分）

1.什么是算法？

2.什么是线性表？

3.什么是堆栈？

4.什么是队列？

四、分析下列程序，计算并用O()表示其时间复杂度(只分析基本语句的执行次

数即可) （第1和第3题各5分，第2题6分，共16分）

1. …

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

x=x+1;

…

2. …

for(i=0;i<n;i++)

for(j=0;j<n;j++)

{ c[i][j]=0;

for(k=0;k<n;k++)

c[i][j]=c[i][j]+a[i][j]*b[i][j];

}

…

3. …

i=0;k=0;n=100;

while(i<=n)

{ k=k+10*I;

i=i+1;

}

…

五、代码分析题，写出整段代码是哪个抽象数据类型的设计，并在黄颜色标号的

地方添加注释语句。（每个标号2分，共38分）

1． 1

public class SeqList implements List{

final int defaultSize = 10;

int maxSize; //数组的最大允许数据元素个数

int size; //数组的当前数据元素个数

Object[] listArray;

public SeqList(){ initiate(defaultSize);} 2

public SeqList(int size){ initiate(size);} 3

private void initiate(int sz){

maxSize = sz;

size = 0;

listArray = new Object[sz];

}

public void insert(int i,Object obj) throws Exception{ 4 if (size == maxSize){

throw new Exception("顺序表已满无法插入！");

}

if (i < 0 || i > size){

throw new Exception("参数错误！");

}

for(int j = size; j > i; j--){ 5

listArray[j] = listArray[j-1];

}

listArray[i] = obj;

size++;

}

public Object delete(int i) throws Exception{ 6 if(size == 0){

throw new Exception("顺序表已空无法删除！");

}

if (i < 0 || i > size-1){

throw new Exception("参数错误！");

}

Object it = listArray[i]; 7

for(int j = i; j < size-1; j++){ 8

listArray[j] = listArray[j+1];

}

size--;

return it;

}

public Object getData(int i) throws Exception{ 9 if(i < 0 || i >= size){

throw new Exception("参数错误！");

}

return listArray[i];

}

public int size(){ 10

return size;

}

public boolean isEmpty(){ 11 return size == 0;

}

}

2． 12

public class LinStack implements Stack{

Node head; //堆栈头

int size; //结点个数

public void LinStack(){ 13 head = null;

size = 0;

}

public void push(Object obj){ 14

head = new Node(obj, head); 15

size ++;

}

public Object pop() throws Exception{ 16 if(size == 0){

throw new Exception("堆栈已空！");

}

Object obj = head.element;

head = head.next; 17

size --;

return obj;

}

public boolean notEmpty(){ 18 return head != null;

}

public Object getTop(){ 19

return head.element;

}

}