一．选择题（每小题1.5分，共18分）
1. 串的逻辑结构与 的逻辑结构不同。
A.线性表 B. 栈 C. 队列 D. 树
2. 下列叙述中属于顺序存储结构的优点的是 。
A.存储密度大 B.插入运算方便
C.删除运算方便 D.可以方便地用于各种逻辑结构的存储表示
3.一算法的执行时间函数为10n4-12n+1，则其时间复杂度是 。
A. O(1) B. O(n) C. O(n4) D. O(log2n)
4.一顺序存储结构线性表有n个数据元素，若要删除的第i个元素，则需要移动_________个数据元素。
A． i－1 B. n－i C． n－i＋1 D. i
5. 若表R在排序前已按键值递增顺序（正序）排列，则 算法的比较次数最少。
A. 直接插入排序 B. 快速排序 C. 归并排序 D. 选择排序
6. p是单链表某结点的指针，假定p及其后继均非空，则删除p的后继结点的操作是 。
A. p=p->next B. p=p->next->next
C. p->next=p->next->next D. p->next=NULL
7. 设栈S已经存在，则在对S进行出栈操作的过程中，首先要判断栈是否为 。
8．队列操作的原则是 。
A. 先进先出 B. 后进先出 C. 只能进行插入 D.只能进行删除
9. 一个栈的输入序列为 a b c d e，则下列序列中不可能是栈的输出序列的是 。
A. b c d a e B．e d a c b C. b c a d e D．a e d c b
10. 在具有n个单元的顺序存储的循环队列中，假设front和rear分别为队头指针和队尾指针，则判断队列满的条件为 。
A. rear % n==front B. front % n+1==rear
C. rear % n-1==front D.(rear+1) % n==front
11. 具有64个结点的完全二叉树的深度为 （根的层次为1）。
A. 8 B. 7 C. 6 D. 5
12. 一个有8个顶点的有向图，所有顶点的入度之和与所有顶点的出度之和的差是 。
A．0 B．2 C．4 D．16
二．判断题（每小题1分，共10分）
1．（ ）已知指针P指向链表L中的某结点，执行语句P=P-〉next不会删除该链表中的结点。
2．（ ）若线性表的主要操作是查找且很少做插入删除操作时，采用顺序存储结构为宜。
3.（ ）算法的重要特性只有三种：有穷性.确定性和输入/输出。
4．（ ）所谓的空白串就是指不包含任何字符的串，其串长度为零。
5.（ ）一棵二叉树的中序遍历序列与该二叉树转换成森林的后序遍历序列相同。
6.（ ）一棵二叉树的后序遍历序列与该二叉树转换成森林后的后序遍历序列相同。
7.（ ）一个完全二叉树的叶子结点只可能在最下面两层出现。
8.（ ）栈顶指针top指向栈顶元素，在顺序存储结构的栈中，必须在修改top的值之后才能做插入和删除操作。
9.（ ）用拓扑排序法可以判断一个有向图是否存在环路。
10.（ ）折半查找算法的前提之一是线性表有序。
三．填空题（每小题1.5分，共15分）
1.所有叶子结点的带权路径长度之和最小的二叉树称为 树。
2.中序遍历一棵二叉排序树所得到的遍历序列的特点是 。
3．在有序表A[1 ．．18]中，采用二分查找算法查找元素值等于A[7]的元素，所比较过的元素的下标依次为 。
4．可以采用折半查找法进行查找的数据文件一般应满足的条件
为 和 。
5．设单链表中指针p指着结点A，若要删除A之后的一个结点（假设存在），则需要修改指针的操作
为____ ____。
6. 线性结构的特点是除了第一个元素和最后一个元素之外，其余元素均只有一个直接前驱和一个 。
7．队列是 的线性表。
8．具有n个顶点的连通图无向图至少有 条边。
9. 设栈S已经存在，则在对S进行出栈操作的过程中，首先要判断栈是否为 。
四．简答题（每小题5分，共25分）
1．已知一带权有向图的邻接矩阵表示如下，请画出其逻辑图。
0 10 15 ∞ ∞ ∞
3 0 ∞ ∞ 10 30
∞ 4 0 ∞ ∞ 10
∞ 15 ∞ 0 ∞ 4
∞ ∞ 10 15 0 ∞
5 ∞ ∞ ∞ 10 0
2．已知一棵树的双亲表示存储映像图如下所示，请画出该树的逻辑示意图。
下标 1 2 3 4 5 6 7 8 9 10 11 12
DatA A B C D E F G H I J K L
PArent 5 1 6 1 0 8 5 5 8 3 8 4
3．将右图所示的树转换成二叉树。
4．在一棵空的二叉查找树中依次插入关键字序列为20、30、8、12、34、5、60、6、1、26，请画出所得到的二叉查找树。
5.设一棵二叉树结点的先序序列为A B D E C F G H ，中序序列为D E B A F C H G ，试画出该二叉树，并写出其后序序列。
五．算法阅读题（共12分）
1．（6分）阅读下列算法，并回答问题。
typedef struct { ElemType *elem；
int length；
int size；
} SeqList；
int xyz(SeqList &L, int i, ElemType &e) { //操作成功返回1，否则返回0
if ((i<1) || (i>L.length)) return 0；
e=L.elem[i-1]；
S1: for ( k=i； K<=L.length-1； ++k ) L.elem[k-1]=L.elem[k]；
L.length- -；
return 1；
}
（1） 语句S1在做什么？
（2）算法的功能是什么？
2. (6分) 以下算法为二分法查找算法，在空格处填上合适语句或表达式完成该算法。
int BinSearch(SqList R, KeyType K)
{ // 参数R为线性表，元素从0到n，R具有字段key为关键字，参数K为待查关键字。
int i=0, j=n； //查找区间初始化
int m；
while (i<j)
{ m=(i+j)/2；
if (R[m].key==K)
return m； //找到该元素
if (R[m].key>K)
；//将查找区间定为左半边
else
；//将查找区间定为右半边
}
Return -1`；//找不到该元素
}
六．编程题（共10分）
试写一算法实现二叉树的叶子结点总数的统计。二叉树类型定义如下：
typedef struct node { datatype data ；
struct node *lchild ；
struct node *rchild} *BTREE；
int leaves(BTREE T) {
} //leaves
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
计算机理论与工程 → 『 理论计算机科学 』 → 求求各位高手帮帮我，星期一就补考了！B卷
(订阅本版)
2008/1/26 18:29:00
新浪微博
求求各位高手帮帮我，星期一就补考了！B卷
