全球新闻大学-全球新闻大学
浙江财经学院东方学院
2010
～
2011
学年第一学期
密
封
线
《数据
结构》课程期末考试试卷（
A
卷）
考核方式：闭卷
考试日期：
2010
年
月
日
适用专业、班级：东方电子商务专业
题
号
得
分
评卷人
一
二
三
（共六大题）
四
五
六
总分
专
业
、
班
级
：
学
号
：
姓
名
：
说明：
（
1
）
请考生将答案写在答题纸上；
（
2
）
考试时间
120
分钟；
一、单选题
（每题
1
分，共
15
分）
1
、对一个算法的评价，不包括如下（
）方面的内容。
A
．健壮性
B
．可读性
C
．正确性
D
．实用性
2
执行下面程序段时，
s
语句的执行次数为
< p>( 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
、
在一个长度为
的顺序存储的线性表中，删除第
i
个元素
( 1
≤
i
≤
n)
时，需要
< p>从前向后依次前移
( 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. =new Node(x,p) =new Node(x,p. next)
6
< p>
假定利用数组
a
顺序存储一个栈，用
top
表示栈顶指针，
top-= -1
表示栈空，
并已
知栈不为空，当退栈并返回栈顶元素时所执行的操作为
( B )
。
a[- -top];
a[top--];
C. rcturn a[++top];
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
，则判断队空的条件为< /p>
( 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 < /p>
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
一个算法的时间复杂度为
(n 3+n2log2n+14n)/n
，其数量级表示为
_____
。
5
任何集合框架都包含三大块内容：对外的接口、< /p>
_____
接口
的实现和对集合运
算的算法
。
6
设有
6
个结点的无 向图，该图至少应有
______
条边才能确保是一个连通图。
7 List
接口对
Collection
进行了简单的扩充，它的具体实现类常用的有
ArrayList
和< /p>
_____
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
算法和构造右图的最小生成树并写出构造过程
.
<
/p>
四、程序填空（每空格
2
分，共
20
分）
1
下面十进制转二进制的算法
.
请在空白处填入适当的内容。
public class binary {
public static void writeBinary(int n, String
s1){
if(n<0)
①
throw
new
IllegalArgumentException()
if(n<=1){
< p>第
3
页，共
7
页