一.选择题(每题1分，共20分)
1.组成数据的基本单位是( ).
(A)数据项 (B)数据类型 (C)数据元素 (D)数据变量
2.设有一个又10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一个元素,其存储地址为1,每元素占1个地址空间,则a85的地址为( ).
(A)13 (B)33 (C)18 (D)40
3.线索化二叉树中某结点D,没有左孩子的主要条件是( )
(A)D->Lchild=Null (B)D->ltag=1
(C )D->Rchild=Null (D)D->ltag=0
4.下面的序列中,( )是堆.
(A)1,2,8,4,3,9,10,5 (B)1,5,10,6,7,8,9,2
(C )9,8,7,6,4,8,2,1 (D)9,8,7,6,5,4,3,7
5.数据结构是研究数据的( )以及它们之间的相互关系.
(A)理想结构,物理结构 (B)理想结构,抽象结构
(C )物理结构,逻辑结构 (D)抽象结构,逻辑结构
6.若给定的关键字集合为{20,15,14,18,21,36,40,10},一趟快速排序结束时,键值的排列为( )
(A)10,15,14,18,20,36,40,21 (B)10,15,14,18,20,40,36,21
(C )10,15,14,20,18,40,36,21 (D)15,10,14,18,20,36,40,21
7.设有100个元素,用二分法查找时,最大比较次数是( ).
(A) 25 (B)7 (C )10 (D)1
8.线性表的链接实现有利于( )运算
(A)插入 (B)读表元素 (C )查找 (D)定位
9.若线性表最常用的操作是存取第i个元素及其前趋的值,则采用( )存储方式节省时间.
(A)单链表 (B)双链表 (C)单循环链表 (D)顺序表
10.下列排序算法中,某一趟结束后未必能选出一个元素放在其最终位置上的是( ).
(A)堆排序 (B)冒泡排序 (C )直接插入排序 (D)快速排序
11.二叉树在线索化后,仍不能有效求解的问题是( )
(A)先序线索二叉树中求先序后继 (B)中序线索二叉树中求中序后继
(C)中序线索二叉树中求中序前驱 (D)后序线索二叉树中求后序后继
12.在用邻接表表示图的情况下,建立图的算法的时间复杂度为( ).
(A)O(n+e) (B)O(n2) (C )O(n×e) (D)O(n3)
13．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动（ ）个元素。
（A）n-i (B)n-i+1 (C )n-i-1 (D)i
14.对一个具有n个元素的线性表，建立其有序单链表的时间复杂度为（ ）
（A）O(n) (B)O(1 ) (C )O(n2) (D)O(nlog2n)
15．已知广义表((a,b,c),(d,e,f)),从A中取出原子e的运算是（ ）
(A)tail(head(A)) (B)head(tail(A))
(C )head(tail(tail(head(A)))) (D)head(head(tail(tail(A))))
16．一棵二叉排序树用中序遍历输出的信息是（ ）
（A）有序序列 （B）递减序列 （C ）无序序列 （D）递增序列
17．若有一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n,则第i个输出元素是（ ）
（A）n-i (B)n-i-1 (C )n-i+1 (D)不确定
18．下列哪种排序需要的附加存储开销最大( ).
(A)快速排序 (B)堆排序 (C )归并排序 (D)插入 排序
19．二叉树第i(i≥1)层上至多有( )结点.
( A)2i (B)2i (C)2i-1 (D)2i-1
20．串的逻辑结构与( )的逻辑结构不同.
(A)线性表 (B)栈 (C)队列 (D)树
二．填空题(每空2分，共20分)
1．对于一个以顺序实现的循环队列Q[0…m-1],队头指针分别为f,r,其判空的条件是 ，判满的条件是 。
2．循环链表的主要优点是
3．前序序列和中序序列相同的二叉树为
4．在散列表(hash)查找中，评判一个散列函数优劣的两个主要条件是：和 。
5．有向图G用邻接矩阵A{1…n,1…n}存储，其第i列的所有元素等于顶点i的 。
6．采用堆排序、快速排序、冒泡排序，对初态为有序的表，最省时间的是 。
7．在左右子树均不空的先序线索二叉树（有n个结点）中，空链域的数目是 。
8.如果含n个顶点的图是一个环，则它有 棵生成树。
三．判断题（正确的标记T,错误的标记F,每题2分，共20分）
1．对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。（ ）
2.已知一颗树的先序序列和后序序列，一定能构造出该树。（ ）
3．任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。（ ）
4．一颗满二叉树同时又是一颗平衡树。（ ）
5．表中的每一个元素都有一个前驱和后继元素。（ ）
6．向二叉排序树中插入一个新结点，需要比较的次数可能大于此二叉树的高度h。 （ 　）
7．如果有向图G＝（V，E）的拓扑序列不唯一，则图中必有两条弧<Vi,Vj>和<Vj,Vi>. ( )
8．若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是该子树的先序遍历中的最后一个结点。( )
9．用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点的个数有关，而与图的边数无关。（ ）
10.在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零。（ ）
四.应用题（写出求解步骤）
1.对关键字序列{72，73,71,23,94,16,05,68},按照堆排序（直接插入排序 ）的方法进行排序。（8分）
2．如下图所示的AOE网（1表示工程开始，8 表示工程结束），求关键路径（9分）。

3．设有一组关键字（19，01，23，14，55，20，84，27，68），采用散列函数：H(key)=key %13，采用开放地址的线性探测再散列方法解决冲突，试在0～15的散列地址空间中对该关键字序列构造散列表。（8分）
五．算法设计题
1．算法填空（5分）
队列的入队操作
status EnQueue(LinkQueue &Q, QElemType e)
{ P=(QueuePtr)malloc(sizeof(Qnode));
　if (!P) exit(OVERFLOW);
　P->data=e;
　P->next=_________（1） ;
　Q.rear->next=________ （2） ;
　Q.rear=_________ （3） ;
　Return OK;
}
二叉树的中序遍历
void InorderTraverse(BiTree T)
{ if (T)
{ 　 _________（4）
　　printf(T->data);
　　_________（5） }
}
2. 编写一个算法将一个无向图的邻接矩阵转换成邻接表。（10分）