《数据结构》课程期末考试试卷（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)

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

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

二、填空题 （每空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];