在一个具有n个顶点的无向图中，要连通全部顶点至少需要______条边。

二叉树的存储结构类型定义如下

typedef struct node{

int data;

struct node *lchild， *rchild;

} BinNode;

typedef BinNode *BinTree;

编写递归算法，求只有一个孩子结点的结点总数，并计算这些结点的数据值的和。函数的原型为：void f34(BinTree T, int *count, int *sum)*count和*sum的初值为0。

顺序表类型定义如下：

(1)给出该算法的功能;

(2)给出该算法的时间复杂度。

阅读下列算法，并回答问题：

(1)这是哪一种插入排序算法?该算法是否稳定?

(2)设置r[0]的作用是什么?

有向图的邻接矩阵类型定义如下：

#define MVN 100 ∥ 最大顶点数

typedef int EType; ∥ 边上权值类型

typedef struct{

EType edges[MVN][MVN]; ∥ 邻接矩阵，即边表

int n; ∥ 图的顶点数

｝MGraph; ∥ 图类型

例如，一个有向图的邻接矩阵如下所示：

阅读下列算法，并回答问题：

(1)step1到step2之间的二重循环语句的功能是什么?

(2)step2之后的二重循环语句的功能是什么?

一组记录关键字(55,76,44,32,64,82,20,16,43)，用散列函数H(key)=key%11将记录 散列到散列表HT[0..12]中去，用线性探测法解决冲突。(1)画出存入所有记录后的散列表。(2)求在等概率情况下，查找成功的平均查找长度。

顺序表类型定义如下：

# define ListSize 100

typedef struct {

int data[ListSize];

int length;}SeqList;

阅读下列算法，并回答问题：

(1)若L->data 中的数据为(22,4,63,0,15,29,34,42,3),则执行上述算法后L->data中的数据以及L->length的值各是什么?

(2)该算法的功能是什么?

假设Q是一个具有11个元素存储空间的循环队列(队尾指针指向队尾元素的下一个位置，队头指针指向队头元素)，初始状态Q.front=Q.rear=0;写出依次执行下列操作后头、尾指针的当前值。

a,b,c,d,e,f入队，a,b,c,d出队; (1) Q.front=______;Q.rear=______。

g,h,i,j,k,l入队，e,f,g,h出队; (2) Q.front=______;Q.rear=______。

M,n,o,P入队，i,j,k,l,m出队; (3) Q.front=______;Q.rear=______。

已知一个无向图如题27图所示，以①为起点，用普里姆(Prim)算法求其最小生成树，画出最小生成树的构造过程。

用归并排序法对序列 (98,36,-9,0,47,23,1,8)进行排序，问：

(1)一共需要几趟归并可完成排序。

(2)写出第一趟归并后数据的排列次序。

对于长度为81的表，若采用分块查找，每块的最佳长度为______。