1．串的长度是 。
A. 串中不同字母的个数 B. 串中不同字符的个数 C. 串中所含字符的个数，且大于0 D. 串中所含字符的个数
2．若线性表最常用的操作是存取第i个元素及其前趋元素的值，则采用___ ___存储方式最节省时间。
A．单链表 B.双向链表 C．单循环链表 D.顺序表
3. 一算法的执行时间函数为10n4-12n+1，则其时间复杂度是 。
A. O(1) B. O(n) C. O(n4) D. O(log2n)
4. p是单链表某结点的指针，假定p及其后继均非空，则删除p的后继结点的操作是 。
A. p=p->next B. p=p->next->next
C. p->next=p->next->next D. p->next=NULL
5. 一个栈的输入序列为 1 2 3 4 5，则下列序列中不可能是栈的输出序列的是 。
A. 2 3 4 1 5 B．5 4 1 3 2 C. 2 3 1 4 5 D．1 5 4 3 2
6．数组A[1..5，1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5] 的地址为 。
A． 1140 B． 1145 C． 1120 D． 1125
7．在有n个结点的二叉链表中，值为非空的链域的个数为 。
A. n－1 B. 2n－l C. n＋1 D. 2n＋l
8． 某二叉树的中序序列和后序序列正好相反，则该二叉树一定是 的二叉树。
A．空或只有一个结点 B. 高度等于其结点数
C．任一结点无左孩子 D. 任一结点无右孩子
9. 带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中 。
A. 第i行非∞的元素之和 B. 第i列非∞的元素个数之和
C. 第i行非∞且非0的元素个数 D. 第i列非∞且非0的元素个数
10. 一个有8个顶点的有向图，所有顶点的入度之和与所有顶点的出度之和的差是 。
A．0 B．2 C．4 D．16
11.若表R在排序前已按键值递增顺序（正序）排列，则 算法的比较次数最少。
A. 直接插入排序 B. 快速排序 C. 归并排序 D. 选择排序
12. 对含有n个互不相同数据元素的集合，同时找最大元和最小元至少需进行 次比较。
A． n－1 B. n C． 2n－3 D. n/2
二．判断题（每小题1分，共10分）
1．（ ）线性表的唯一存储形式就是链表。
2．（ ）线性结构中的所有数据元素都只有一个前驱元素和后继元素。
3.（ ）所有元素在存储位置上相邻的表是用顺序存储结构建立的表。
4.（ ）折半查找算法的前提之一是线性表有序。
5.（ ）对相同关键字集合，以不同次序插入初始为空的树中，一定得到不同的二叉排序树。
6.（ ）两个字符串相等的充要条件是其长度相等且每个对应位置上的字符相同。
7.（ ）一棵二叉树的中序遍历序列与该二叉树转换成森林的后序遍历序列相同。
8.（ ）若二叉树的根结点在第1层，则该二叉树第i层上最多有2i-1个结点。
9.（ ）在单循环链表中设置尾指针比设置头指针更好。
10.（ ）用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中边的数目无关。
三．填空题（每小题1.5分，共15分）
1．设单链表中指针p指着结点A，若要删除A之后的一个结点（假设存在），则需要修改指针的操作为____ _ ___。
2. 线性结构的特点是除了第一个元素和最后一个元素之外，其余元素均只有一个直接前驱和一个 。
3. 中序遍历一棵二叉排序树所得到的遍历序列的特点是 。
4．对于一个以顺序实现的循环队列Q[0..m-1]，队头、队尾指针分别为f、r，则队列判空的条件是 。
5. 设栈S已经存在，则在对S进行出栈操作的过程中，首先要判断栈是否为 。
6. 队列是一种特殊的线性表，它的特殊性在于 。
7．具有n个顶点的连通图无向图至少有 条边。
8．在有序表A[1 ．．18]中，采用二分查找算法查找元素值等于A[7]的元素，所比较过的元素的下标依次为 。
9．可以采用折半查找法进行查找的数据文件一般应满足的条件
为 和 。
四．简答题（每小题5分，共25分）
1．已知一带权无向图如右所示，请写出该网的邻接矩阵表示。
2． 设多项式P(x)＝5x6＋3x4－4x3＋x－12，请用两种不同线性存储结构表示该多项式，画出它们存储映像图。
3. 设一棵二叉树结点的先序序列为A B D E C F G H ，中序序列为D E B A F C H G ，试画出该二叉树，并写出其后序序列。
4. 判断（5， 80， 40， 10， 66， 77， 85, 100， 82， 60，95）是否为堆，若不是，则把它调整为堆。
5．在一棵空的二叉查找树中依次插入关键字序列为20、30、8、12、34、5、60、6、1、26，请画出所得到的二叉查找树。
五．算法阅读题（共12分）
1．（6分）以下为直接插入排序算法，请在空格处填上合适语句或表达式，完成以下算法。
void InsertSort(SeqList &L) {
for(i=2； i <= L.length； i++){
L.r[0] = L.r[i]；
for(j=i-1； L.r[0].key < L.r[j].key； j-- )
；
；
} //for
}// InsertSort
2. (6分)以下算法完成将不带头结点的单链表首元素放到表尾，请在空格处填上合适语句或表达式，完成以下算法。
void mynote( LinkList &L) //L是不带头结点的单链表的头指针
{ LinkList p, q； // LinkList为链表指针类型
if （L !=NULL &&（L->next!=NULL)） //当L为空或L为单个结点，则不必执行该程序
{ q=L； L=L－>next； p=L；
while ( ) p=p－>next；
p－>next=q；
q－>next= ；
}
}
六．编程题（共10分）
写出函数用于删除元素递增排列的带头结点单链表L中所有值相同的元素，并给出其时间复杂度。链表类型定义如下：
typedef struct node { char data ；
struct node * next } *LinkList ；
void DeleteSameE(LinkList L) {
}
} // DeleteSameE
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 理论计算机科学 』 → 求求各位高手帮帮我，星期一就补考了！A卷
(订阅本版)
2008/1/26 18:25:00
新浪微博
求求各位高手帮帮我，星期一就补考了！A卷
