①
for ( int i = 0; i < n; i++ ) ;
t. ConstructTree( T, n, 0, ptr ); //以数组建立一棵二叉树
②
;
return in; }
template
ConstructTree ( Type T[ ], int n, int i, BinTreeNode
//将用T[n]顺序存储的完全二叉树, 以i为根的子树转换成为用二叉链表表示的
③
//以ptr为根的完全二叉树。利用引用型参数ptr将形参的值带回实参。
if ( i >= n ) ;
else {
ptr = new BinTreeNode
⑤
④
ConstructTree ( T, n, 2*i+1, );
ConstructTree ( T, n, , ptr->rightChild );
} }
缺失的语句为：①②③④⑤
第七章
1、在有n个顶点的有向图中，每个顶点的度最大可达 2（n-1） 。
2、有向图g用邻接矩阵a［１…m,1…m］来存储，其第i行的所有元素之和等于顶点i的3．关键路径是指途中从原点到会点的路径长度最长的路径。 4一个具有n个结点的无向图，至多有n(n-1)/2条边。
5．具有n个顶点的有向图最多有__________条边。
6．若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个________矩阵。 下面给出的算法是建立AOV网络并对其进行拓扑排序的算法，其中有多个语句缺失。 void Graph::TopologicalSort ( ) { Edge * p, q; int i, j, k; for ( i = 0; i < n; i++ ) {
。 出度 NodeTable[i].adj = NULL;
? ;
}
cin >> j >> k; //输入有向边
p = new Edge (k); //建立边结点, dest域赋为k
p→link = NodeTable[j].adj; //链入顶点j的边链表的前端
cin >> j >> k; }
int top = -1;
for ( i = 0; i < n; i++ ) //建立入度为零顶点的链栈 if ( count[i] == 0 ) { count[i] = top; ? }
for ( i = 0; i < n; i++ ) if ( top == -1 )
{ cout << \return; } else {
j = top;
ˉ ;
cout << NodeTable[j].data << endl; q = NodeTable[j].adj;
while ( q ) { k = q→dest; if ( -- count[k] == 0 ) { count[k] = top; top = k; }
° }
}
}
(1) 请将缺失的语句补上： （10分） ? ? ˉ
;
count[k]++; //顶点k入度加一
;
;
(2) 请给出对于下面AOV网络，使用上述算法进行拓扑排序的结果，以及在count数组中建立的链式栈的变化。（top是栈顶指针） （10分）
top→ A B C D E F
初始 第九章
1．设有100个数据元素，采用折半搜索时，最大比较次数为__________。
2．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是___________。
3．将5个不同数据进行排序，至少需要比较4次，至多需要比较10次。 4．二分查找的平均查找长度为[(n+1)/n]log2(n+1)-1。 log2(n+1)-1
5常用的构造哈希函数的方法有 、 、 、折叠法、随机数法和数字分析法。 6、直接选择排序算法在最好情况下所作的交换元素的次数为0。
7、有n个球队参加的足球联赛按主客场制进行比赛，共需进行 n(n-1) 场比赛。８、8、8、在含有n个元素的顺序表中，用顺序查找方法，查找不成功的查找长度为 n+1 。
9． 在程序设计中那三种情况下，常常要用到递归：定义是递归的、_______、_______. 10． 将函数F=1+1/2+1/3+.....+1/n用递归运算，其递归体是______。
三、判断题
1、数据元素是数据的最小单位。（ × ）
2、顺序表用一维数组作为存储结构，因此顺序表是一维数组。（）
3、算法的运行时间涉及加、减、乘、除、转移、存、取等基本运算。要想准确地计算总运算时间是不可行的。（） 4、数据结构、数据元素、数据项在计算机中映像（或表示）分别称为存储结构、结点、数据域。（Y ） 5、在单链表中，要取得某个元素，只要知道该元素指针即可，因此单链表是随机存储结构（ N ）。 1、栈的特点是后进先出。（ √ ）
2、使用三元组表示稀疏矩的元素，有时并不能节省空间。（ √ ）
3、栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。
4、在使用后缀表示实现计算器类时用到一个栈的实例，其作用是暂存运算对象。
4、已知二叉数的前序遍历和后序遍历并不能唯一的确定这棵树，因为并不知道树的根结点是哪一个。（ × ） 5、栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。 使用三元组表示稀疏矩的元素，有时并不能节省空间。（ Y ） 串的联接不满足交换律，满足结合律。（ Y ）
6、二维数组是数组元素为一维数组的线性表，因此它是线性结构。
7、磁盘上读写一块信息所需的时间有查询时间、延迟时间和等待时间。（ × ） 8、顺序表用一维数组作为存储结构，因此顺序表是一维数组。
1、已知一棵树的先序序列和后序序列，一定能构造出该树。 （ √ ）
2、设由一棵树T转化的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。 （ × ） 3、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（ × ）
4．已知二叉数的前序遍历和后序遍历并不能唯一的确定这棵树，因为并不知道树的根结点是哪一个。（n）
5．（ ） 有n个结点的不同的二叉树有n！棵。1、对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。 （ × ）
6、具有n个结点的完全二叉树的高度为 ?log2 n? +1。（n ? 0, 根在第0层）
7、 在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有 n0 = nk + 1。
8、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。
9、用相邻矩阵法存储一个图时，再不考虑压缩存储的情况下，所占存储空间的大小只于图中结点的个数有关，而与图的边数无关。（Y ）
1、图G的最小生成树的代价一定小于其它生成树的代价。 （ × ）
2、任一AOV网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。 （ √ ） 3、连通分量是无向图中的极小连通子图。
1、在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。 （ √ ）
2、只有在初始数据为逆序，冒泡排序所执行的比较次数最多。 （ × ） 3、快速排序是排序算法中最快的一种。 （ × ）
4、闭散列法通常比开散列法时间效率更高。
5、一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。
6．对于不同关键字可能得到同一哈希地址,即key1≠key2，而f(key1)= f(key2)，这中现象称为冲突。 7．（ ） 折半搜索适用于有序的顺序表，不适用于有序的链表。
哈西表的查找效率主要决于哈西表造表时选取的哈西函数和处理冲突的方法。（Y） 8、直接选择排序是一种不稳定的排序方法。
9、在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。 10、当3阶B 树中有255个关键码时，其最大高度（包括失败结点层）不超过8。 11、一棵3阶B 树是平衡的3路搜索树，反之，一棵平衡的3路搜索树是3阶B 树。
12、在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。在设计再散列函数时，要求计算出的值与表的大小m互质。
四、应用题
1、若一棵二叉树终端结点数为m，度为2的结点数为n，试证明m=n+1。(8’)
2、某乡有a,b,c,d,e五个村庄，地理位置分布如下图所示，弧上的数值表示两村之间的距离，若要在乡内建立一所医院，则设在哪个村庄才能使各村离医院的距离最近，为什么？(10’)
2 4
1 2 3
1 5
3、已知一关键字序列为（40，11，16，31，23，55，13，45，50），试生成一棵平衡的二叉排序树,再从生成的平衡的二叉排序树中删除关键字45。（12’）
4、已知一组元素为（ 45，62，25，78，81，36，47，25，79 ），画出按元素排列顺序输入生成的一棵二叉排序树。 有9个带权结点 a、b、c、d、e、f、g、h、I，分别带权 4，2，7，12，6，10，5，9，3，试以他们为叶子结点构造一棵哈夫曼树（请按照左子树根结点的权小于等于右子树根结点的权的次序构造）。 如下图1，求v1到其它各顶点最短路径以及运算过程。（用表格画出来）
6
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构试题汇总(2)在线全文阅读。
相关推荐：