2009~2010学年秋季学期期末考试试题(A)
试题 班级 姓名 学号 第 1 页
题目 分数 评卷人 一 二 三 四 五 六 七 八 总分数
一、选择题（在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题号后面的括号内。每题2分，共20分）
1. ( )下面程序段的时间复杂度为 1、 void binary(int n){ 2、 while(n>0){
3、 System.out.print(n+”,”); 4、 n/=2; 5、 } } A.O(1) B.O(log2n) C.O(n) D.O(n2)
2. ( )算法必须具备五个特性：输入，输出以及
A.可行性、可移植性、可扩充性 B.可行性、确定性、有穷性 C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性 3. ( )以下与数据的存储结构无关的术语是
A.循环队列 B.循环链表 C.链式栈 D.栈 4. ( )下列说法中正确的是 A.数据元素是数据的最小单位。
B.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 C.数据的存储结构是指数据在计算机内的实际存储形式。 D.链表中的头结点仅起到标识的作用。
5. ( )在需要经常查找结点的前驱与后继的情况下，使用下列哪种结构比较合适。
A.单链表 B.双链表 C.顺序表 D.循环链表.
6. ( )按二叉树的定义，具有三个结点的二叉树共有( )种形态。 A.3 B.4 C.5 D.6
7. ( )高度为5的完全二叉树中含有的结点数至少为( ) A.16 B.17 C.31 D.32
8. ( )对线性表进行折半查找时，要求线性表必须
A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序
9. ( )设栈的输入序列是1，2，3，4,则不可能出现的出栈序列是 A.1，2，4，3 B.2，1，3，4 C.1，4，3，2 D.4，3，1，2
1
数据结构(A) 10. ( )已知变量p和q分别引用某单链表中第一个结点和最后一个结点。假设变量s引用另一个单链表中某个结点，则在s所引用的结点之后插入上述链表应执行的语句为
A.q.next=s.next；s.next=p； B.s.next=p；q.next=s.next； C.p.next=s.next；s.next=q； D.s.next=q；p.next=s.next；
二、填空题（每题2分，共20分）
1.在一个长度为1000的顺序表中删除第50个元素（序号为49）时，需移动__________个元素。
2.带头结点的单链表，头指针为head，则判定该表为空表的条件是____________________________________
3. 在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为 。
4.已知一个顺序循环队列最多能容纳60个元素，当front=47,rear=12时，该队列有_____________个元素。
5.若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是______________的。
6.对于下面的带权图，若从顶点v0出发，则按照普里姆（Prim）算法生成的最小生
成树中，得到第二条边为_________________。 7.顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__ __次。
8.队列的队尾位置通常是随着______________操作而变化的。
9.对n个元素的序列进行冒泡排序时，最少的比较次数为_______________。 10. 归并排序的空间复杂度为_____________。 三、简答题（共36分）
1.（7分）已知一棵二叉树的中序序列是IGJEKBFCDA，先序序列是EIJGBKACFD， (1)请画出这棵二叉树
(2)请画出该二叉树的中序线索化树。
2
试题 班级 姓名 学号 第 2 页 2. （6分）输入一组关键字{10,5,7,14,3,1,18,12,15,16} (1)请画出由此生成的二叉排序树。
(2)如果对每一关键字的查找概率相等，求其平均查找长度ASL。
3. （7分）已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示， （1） 请画出该无向图
（2） 请写出从顶点V0出发，进行深度优先遍历，所
得到的遍历序列。
（3） 请写出从顶点V0出发，进行广度优先遍历，所
得到的遍历序列。
数据结构(A) 3
4. （6分）采用堆排序法对序列{48，37，63，96，22，31，50，55，11}进行升序排序，写出构建的初始(大根)堆及前两趟调整堆之后的序列状态。 初始堆：
第1趟：
第2趟：
5. （10分）请阅读如下算法，回答以下问题 （1）请写出输出结果。
（2）请解释下划线处所示方法的功能。
import dataStructure.linearList.SeqStack;
public class Test {
public static void main(String args[]){ int a[]={78,63,45,30,91,34}; SeqStack S=new SeqStack(a.length); ① for(int i=0;iS.push(new Integer(a[i])); ② while(!S.isEmpty()) ③System.out.print(S.pop().toString()+\" \"); ④ } }
输出结果：___________________________________ ①___________________________________________ ②___________________________________________ ③___________________________________________ ④___________________________________________ 四、算法填空题（6分）
顺序表类中包含以下属性，remove方法删除index位置的对象，若操作成功，则返回被删除对象，否则返回null，请在程序的空白处填入合适内容。 public class SeqList implements LList { private Object[] table; private int n; ……public E remove(int index){
if(this.n!=0&&index>=0&&indexE old=(E)this.table[index];for(int j=index;jthis.table[this.n-1]=null;4
试题 班级 姓名 学号 第 3 页 }
}
② //表长减一
③ //若操作成功，返回删除对象 }
return null;
五、算法设计题（每题6分，共18分）
1.不带头结点的单链表声明如下，方法略。
public class SinglyLinkedList implements LList { protected Node head; }在SinglyLinkedList类中增加下列构造方法 public boolean replace(Object obj, E element)
其功能为将元素值为obj的结点值替换为element，若替换成功返回true，否则返回false。
5
数据结构(A) 2.二叉树类声明如下，方法略。
public class BinaryTree {protected BinaryNode root; }请在该类中增加方法countLeaf，计算二叉树叶子结点的数量。
3. 请编写算法，对整型数组t进行直接插入排序。
6
