《数据结构》课程期末考试试卷（A卷）DAOAN- 副本 - 图文

浙江财经学院东方学院课程期末考试试卷

浙江财经学院东方学院2010～2011学年第一学期

密 封 线 《数据结构》课程期末考试试卷（A卷）

考核方式：闭卷 考试日期：2010年 月 日 适用专业、班级：东方电子商务专业

题 号 得 分 评卷人 一 二 三 （共六大题） 四 五 六 总分 专业、班级： 学号： 姓名： 说明：

（1） 请考生将答案写在答题纸上； （2） 考试时间120分钟；

一、单选题 （每题1分，共15分）

1、对一个算法的评价，不包括如下（ ）方面的内容。

A．健壮性 B．可读性 C．正确性 D．实用性 2执行下面程序段时，s语句的执行次数为( D )。 for (int i=l; i<=n;i++) For(int j=1; j<=i; j++)S;

A．n2 B．N2／2 C．n(n+1) D.n(n+1)/2 3..下面算法的时间复杂度为(B) intf (int n){

if (n==0 || n==l) return 1. Else return n*f(n-l);

A．O(1) B．O(n) C．O(n2) D O(n!)

4、

在一个长度为n的顺序存储的线性表中，删除第i个元素(1≤i≤n)时，需要从前向后依次前移( A )个元素。

A. n-i B.n-i+1 C.n-i-l D.i

5

若一个结点的引用为p，在p结点后面插入一个值为x的新结点的操作为( D )。 A. p=new Node(x,p) B.p=new Node(x,p. next)

第1页，共7页

浙江财经学院东方学院课程期末考试试卷

C. p.next=new Node(x,p) D.p.next=new Node(x,p. next) 6

假定利用数组a顺序存储一个栈，用top表示栈顶指针，top-= -1表示栈空，并已知栈不为空，当退栈并返回栈顶元素时所执行的操作为( B )。

A.return a[- -top]; B.return a[top--]; C. rcturn a[++top]; D.return a[top++]; 7

若让元素1．2.3依次进栈．则出栈次序不可能出现( C )的情况。 A 3.2.1 B.2,1,3 C.3,1,2 D.1.3,2 8

假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为( D )。

A．f+1 ==r B．r+l==f C．f-==0 D．f==r 9

在一个顺序队列中，队首指针指向队首元素的( A )位置。 A．前一个 B．后一个 C．当前 D．前2个 10

树中所有结点的度等于所有结点数加( C )。 A．0 B．1 C．-1 D．2

11在一棵具有35个结点的完全二叉树中，该树的深度为( A )。 A．6 B．7 C．5 D．8

12在一棵具有n个结点的二叉树的第i层上，最多具有( C )个结点。

A．2i B．2i+1 C．2i-1 D．2n 13 n个顶点的连通图至少包含有( A )条边。 A．n-l B．n C．n+1

14 为了实现图的广度优先搜索遍历．其广度优先搜索算法使用的一个辅助数据结构为( B )。

A．栈 B．队列 二叉树 D．树

15在对n个元素进行直接选择排序的过程中．需要进行( C )趟选择和交换。 A n B．n+l C．n-l D．n/2

第2页，共7页

浙江财经学院东方学院课程期末考试试卷

二、填空题 （每空1分，共15分）

1算法可用文字、高级程序设计语言或类同于高级程序设计语言的伪码______描述

2．数据的物理存储结构分为顺序和____链式_______二种。

3当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_______________排序

4一个算法的时间复杂度为(n3+n2log2n+14n)/n，其数量级表示为_____。 5任何集合框架都包含三大块内容：对外的接口、_____接口的实现和对集合运算的算法。

6设有6个结点的无向图，该图至少应有______条边才能确保是一个连通图。 7 List接口对Collection进行了简单的扩充，它的具体实现类常用的有ArrayList和_____LinkedList

8若一个过程直接地或间接地调用自己, 则称这个过程是_____递归的过程 9若某完全二叉树的高度为h，则该完全二叉树中至少有______个结点

10对一棵二叉搜索树进行前序遍历时，得到的结点序列是一个__________序列。

三、综合题（每小题6分，共30分）

1. 已知一棵二叉树的前序遍历的结果序列是ABDEGCFH，中序遍历的结果是DBGEACHF，试画出这棵二叉树并写出这棵二叉树的后序遍历结果。DGEBHFCA 2. 请写出右图的邻接矩阵、邻接表和边集数组

3. 设一个关键字序列为｛26 , 53 , 67 , 48 , 57 , 13 , 48 , 32 , 60 , 50｝分别写出直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、归并排序的前二趟的排序序列.．

4. 分别用purim算法和构造右图的最小生成树并写出构造过程.

四、程序填空（每空格2分，共20分）

1下面十进制转二进制的算法. 请在空白处填入适当的内容。

public class binary {

public static void writeBinary(int n, String s1){

if(n<0)

① throw

new

IllegalArgumentException() ;

if(n<=1){

第3页，共7页

浙江财经学院东方学院课程期末考试试卷

s1=1+s1;

System.out.println(s1); } else {

s1= ② n%2+s1; ③ writeBinary(n/2,s1); } 2

3下面是栈的类定义, 请在空白处填入适当的内容 public class Stack {

int top=-1; int size =0; Object[] arr;

public Stack(int capacity) { }

public void push(Object e) {

top++;

arr[top]= ② e;

arr = new ① Object[capacity];

③ size++; }

public Object pop() {

Object t = arr[top];

第4页，共7页

浙江财经学院东方学院课程期末考试试卷

} … }

top--; size--;

④ return t;

五、算法分析和设计题（共20分）

1、指出下列算法的功能并求出其时间复杂度。 int Count(int[][]a,int k) { int c=0;

for(int i=0;i

for(int j=0;j=k) c++; return c; }

统计并返回二维数组a中大于等于k的元素的个数。时间复杂度为O(m×n)，假定m和n

分别表示二维数组a的行数和列数

2 指出下列算法的功能并写出运行结果 public class TestPrime{

public static void main(string args[]) { int i,j;

For (i=3;i<=30;i++){ For(j=2;j

Bresk;

} } If((j

第5页，共7页

浙江财经学院东方学院课程期末考试试卷

}

System.out.print(i+\} } }

3编写一个函数，要求借助一个栈把一个数组中的元素逆置。

Public static Object [] ReverseArray (Object [] array)

Public static Object [] ReverseArray (Object [] array) {

if (array == null || array.length == 0) return array ;

Stack stack = new Stack (array.length) ;

for (int i = 0 ; i < array.length ; i ++) stack.push (array [i]) ;

for (int i = 0 ; i < array.length ; i ++) array [i] = stack.pop () ;

return array ; }

4 从链接存储的线性表list中删除与obj相同的所有元素。

第6页，共7页

浙江财经学院东方学院课程期末考试试卷

public static void deleteAll(linkList list, Object obj) { //从参数线性表list中删除与obj相同的所有元素

Node p=list.prior(),head=p; //list的表头指针赋给p，并保存到head Node q=p.next; //使q指向第1个元素结点, p为q的前驱 while(q!=head) { //从头到尾依次扫描每个结点 if(q.element.equals(obj)) {

p.next=q.next; q=q.next; //删除q结点,q指向下一个结点 list.setSize(list.size()-1); //长度减1 }

else {p=q; q=q.next;} //使p和q顺序指向下一个结点 } }

第7页，共7页

本文来源：https://www.bwwdw.com/article/uerr.html