《数据结构2009~2010试卷A试题_Final啊》由会员分享，可在线阅读，更多相关《数据结构2009~2010试卷A试题_Final啊（7页珍藏版）》请在金锄头文库上搜索。
1、密 封 线专业、班级： 学号： 姓名：浙江财经学院20092010学年第一学期数据结构课程期末考试试卷（ A 卷）考核方式： 开卷 考试日期：2009 年1 月 15 日适用专业、班级：08电子商务1、2题 号一二三四五总分得 分评卷人（共 5 大题）一、 填空题（每空1分，共10分）1_字节是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。2数据的物理存储结构分为_顺序存储结构_和_链式存储结构_二种。3下面程序段的时间复杂度是O（n）_。int n=10,sum=0;for(int i=0;in;i+) sum+=n;4.栈和队列是操作受限的线性表，队列又称_先进先出_线性表
2、。5若某完全二叉树的高度为h，则该完全二叉树中至少有_个结点，最多有_个结点。6每次使两个相邻的有序表合并成一个有序表的排序方法叫做 归并 排序。7在线性表的散列存储中，处理冲突的常用方法有_开放地址法_和_链地址法_两种。二、 综合运算题（每小题5分，共25分）1有以下双端链表的图形，要求完成在最后一个结点插入一个新结点的语句，新插入结点为newEntry，其中newEntry中的数据元素值为“kate”。其中节点定义类型如下： class Entry Object data;Entry next;public Entry(Object data)this.data = data;heade
3、rlastdatanextdatanextdatanextdatanextnulldatanext2已知一棵二叉树的前序遍历结果为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分，共
4、25分）1、确定如下代码段的输出：import java.util.*;public class Exam1public static void main(Stringargs)ArrayList letters = new ArrayList();letters.add(“f”);letters.add(1,”i”);letters.add(”e”);letters.add(1,”r”);letters.add(”e”);letters.add(4,”z”);System.out.println(letters);letters.remove(”i”);int index=letters.i
5、ndexof(”e”);letters.remove(index);letters.add(2,”o”);System.out.println(letters);friezefroze2、对下面的方法传递参数5，则方法返回的值是多少？public long unKnow (int n) if (n 0) throw new IllegalArgumentException( ); if (n = 1) return 1; else return n * unKnow (n 1)1203、 已知Stack为java集合框架中的栈类，请给出下列的输出结果：public static void ma
6、in(String args) Stack s = new Stack(); s.push(new Integer(3); s.push(new Integer(4); int x=(Integer)s.pop().intValue()+2*(Integer)s.pop().intValue(); s.push(new Integer(x); int i,a5=2,5,8,22,15; for(i=0;i 1 ; out-) / outer loop (backward) for(in=0; in ain+1 ) temp=R in ; R in = Rin+1 ; R in+1 = temp
7、 ; / end bubbleSort()2、SortedList实现了有序单链表插入算法，阅读下来算法并补充所缺语句class Entry Object element;Entry next; public Entry(Object o) / constructor element=o; / end class Link/public class SortedList private Entry first; / ref to first item public SortedList() first = null; / constructor public boolean isEmpty() return (first= =null); / true if no links public void insert(Object key) / insert, in order Entry newEntry= new Entry(key); / make new link Entry previous = null; / start at first Entry current = frist ;
