文档介绍：学习必备 欢迎下载
学习必备 欢迎下载
学习必备 欢迎下载
课程测试试题（卷）
----------------------以下为教师填写--------------------
I、命题院（部）： 数，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。
6.        广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。
7.        二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结点的度的总和是_____________。
8.        对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。
9.        对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_____________个，其中_______________个用于指向孩子，_________________
学习必备 欢迎下载
学习必备 欢迎下载
学习必备 欢迎下载
个指针是空闲的。
10.    若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为________,右孩子元素为_______________，双亲元素为____________。
11.    在线性表的散列存储中，处理冲突的常用方法有________________________和_____________________________两种。
12.    当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_______________排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用________________________排序。
 
三、                   运算题（每题6分，共24分）
1.        已知一个6´5稀疏矩阵如下所示，
 
 
 
 
 
 
试：
（1）        写出它的三元组线性表；
（2）        给出三元组线性表的顺序存储表示。
2.        设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个数据而生成的二叉搜索树。
3.        对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：
(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树；
(2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树；
4.        已知一个图的顶点集V和边集E分别为：
学习必备 欢迎下载
学习必备 欢迎下载
学习必备 欢迎下载
图6
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.                     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)     指出该算法的功能；
(2)     该算法的时间复杂度是多少？
2.                     写出下述算法的功能：
void AJ(adjlist GL, int i, int n)
{
Queue Q;
InitQueue(Q);
cout<<i<<' ';
visited[i]=true;
QInsert(Q,i)