文档介绍：密封线
专业、班级：学号：姓名：
浙江财经学院2009～2010学年第一学期
《数据结构》课程期末考试试卷（ A 卷）
考核方式：开卷考试日期：2009 年1 月 15 日
适用专业、班级：08电子商务1、2
题号
一
二
三
四
五
总分
得分
评卷人
（共 5 大题）
填空题（每空1分，共10分）
1．_字节是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
2．数据的物理存储结构分为____顺序存储结构____和____链式存储结构______二种。
3．下面程序段的时间复杂度是O（n）_____。
int n=10,sum=0;
for(int i=0;i<n;i++)
sum+=n;
，队列又称_先进先出_______线性表。
5．若某完全二叉树的高度为h，则该完全二叉树中至少有______个结点，最多有______个结点。
6．每次使两个相邻的有序表合并成一个有序表的排序方法叫做归并排序。
7．在线性表的散列存储中，处理冲突的常用方法有__开放地址法_____________和_______链地址法_________两种。
综合运算题（每小题5分，共25分）
1．有以下双端链表的图形，要求完成在最后一个结点插入一个新结点的语句，新插入结点为newEntry，其中newEntry中的数据元素值为“kate”。其中节点定义类型如下：
class Entry
{
Object data;
Entry next;
public Entry(Object data)
{
= data;
}
}
header
last
data
next
data
next
data
next
data
next
null
data
next
2．已知一棵二叉树的前序遍历结果为ABDGEFCH，中序遍历的结果为GDBEAFHC，画出该二叉树，并给出后序遍历的结果。
3．将关键码6３，8８，7５，2７，9７，1９，9１，5５，3３依次插入到一棵初始为空的二叉搜索树中，画出对应的二叉搜索树。
4．举例说明clone方法的含义，并对浅克隆与深度克隆进行说明及图示？
5．设待排序文件的关键码为（42, 65,80,77,43,55, 2,87,44,60），第一个元素为分界元素（枢轴）进行快速排序（按关键码值递增顺序），请给出第一趟排序后的结果。
三、程序阅读题（每小题5分，共25分）
1、确定如下代码段的输出：
import ja