3. 3. 当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0___(要超出才为满)_______________。
5. 5. 设W为一个二维数组，其每个数据元素占用4个字节，行下标i排序题从0到7 ，列下标j从0到3 ，则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。
6. 6. 广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为___________
_。
7. 7. 二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结点的度的总和是_____________。
8. 8. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。
9. 9. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_____________个，其中_______________个用于指向孩子，_________________个指针是空闲的。
10. 10. 若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为________,右孩子元素为_______________，双亲元素为____________。
11. 11. 在线性表的散列存储中，处理冲突的常用方法有________________________和_
____________________________两种。
12. 12. 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_______________排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用________________________排序。
一、 三、 运算题（每题6分，共24分）
1. 1. 已知一个6⨯5稀疏矩阵如下所示，
试：
（1） （1） 写出它的三元组线性表；
（2） （2） 给出三元组线性表的顺序存储表示。
2. 2. 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。
3. 3. 对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：
(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树；
(2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树；
4. 4. 已知一个图的顶点集V和边集E分别为：
V={1,2,3,4,5,6,7};
E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};
若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。
二、 四、 阅读算法（每题7分，共14分）
1. 1. int Prime(int n)
{
int i=1;
int x=(int) sqrt(n);
while (++i<=x)
if (n%i==0) break;
if (i>x) return 1;
else return 0;
}
(1) (1) 指出该算法的功能；
(2) (2) 该算法的时间复杂度是多少？
2. 2. 写出下述算法的功能：
void AJ(adjlist GL, int i, int n)
{
Queue Q;
InitQueue(Q);
cout<<i<<' ';
visited[i]=true;
QInsert(Q,i);
while(!QueueEmpty(Q)) {
int k=QDelete(Q);
edgenode* p=GL[k];
while(p!=NULL)
{
int j=p->adjvex;
if(!visited[j])
{
cout<<j<<' ';
visited[j]=true;
QInsert(Q,j);
}
p=p->next;
}
}
}
三、 五、 算法填空（共8分）
如下为二分查的非递归算法，试将其填写完整。
Int Binsch(ElemType A[ ],int n,KeyType K)
{
int low=0;
int high=n-1;
while (low<=high)
{
int mid=_______________________________；
if (K==A[mid].key) return mid; //查成功，返回元素的下标
else if (K<[mid].key)
______________________________________; //在左子表上继续查
else __________________________________; //在右子表上继续查
}
return -1; //查失败，返回-1
}
四、 六、 编写算法（共8分）
HL是单链表的头指针，试写出删除头结点的算法。
ElemType DeleFront(LNode * & HL)
参考答案
一、 一、 单选题（每题2分，共20分）
1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C
二、 二、 填空题（每空1分，共26分）
1. 1. 联系 图（或图结构）
2. 2. 尾 首
3. 3. top==0
4. 4. O（1） O（n）
5. 5. 128 44 108
6. 6. 3 3
7. 7. 有序 n-1
8. 8. 有序序列 后缀表达式（或逆波兰式）
9. 9. 2n n-1 n+1
10. 10. 2i+1 2i+2 (i-1)/2
11. 11. 开放定址法 链接法
12. 12. 快速 归并
三、 三、 运算题（每题6分，共24分）
1. 1. （1） ((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (3分)
（2） 三元组线性表的顺序存储表示如图7示。
2. 2. 如图8所示。
3. 3. DFS：①②③④⑤
BFS：②③④⑤①
4. 4. 拓朴排序为： 4 3 6 5 7 2 1
四、 四、 阅读算法（每题7分，共14分）
1. 1. (1) 判断n是否是素数（或质数）
（2）O（）
2. 2. 功能为：从初始点vi出发广度优先搜索由邻接表GL所表示的图。
五、 五、 算法填空（8 分）
(low+high)/2 high=mid-1 low=mid+1
六、 六、 编写算法（8分）
ElemType DeleFront(LNode * & HL)
{
if (HL==NULL){
cerr<<"空表"<<endl;
exit(1);
}
LNode* p=HL;
HL=HL->next;
ElemType temp=p->data;
delete p;
return temp;
}
一、 一、 单选题（每题 2 分，共20分）
1. 1. 栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
2. 2. 用链接方式存储的队列，在进行插入运算时( ).
A. 仅修改头指针 B. 头、尾指针都要修改
发布评论