超星 - 作业9 - 查题吧

填空题

n个顶点的有向图中，顶点的最大度数等于______。

填空题

对含有k个连通分量的无向图进行先深搜索时，主控函数中需要调用递归的搜索函数dfs_____次。

判断题

无向图G的连通分量是G的极大连通子图。

A. 对
B. 错

判断题

对于无向加权图而言，其最小生成树有可能不存在，但如果存在的话通常是不唯一的。

A. 对
B. 错

判断题

可以采用一维数组对无向图的邻接矩阵进行压缩存储。对于一个包含n个顶点的无向图而言，假设M是其邻接矩阵，A是对M（下三角）进行压缩存储的一维数组。那么M[i][j]=A[i*(i-1)/2+j]，其中0≤i
A. 对
B. 错
查看答案

判断题

通过对无向图进行先深搜索，一定可以判断该图是否是连通图，或找出图的连通分量及先深生成树。

A. 对
B. 错

简答题

在分块检索中，对256个元素的线性表分成多少块最好？每块的最佳长度是多少？若每块的长度为8，其平均检索的长度是多少？

简答题

含有9个叶子结点的3阶B-树中至少有多少个非叶子结点？含有10个叶子结点的3阶B-树中至少有多少个非叶子结点？

简答题

设散列表为T[0..12]，即表的大小m=13。现采用再哈希法（双散列法）解决冲突。散列函数和再散列函数分别为：H0(k)=k%13，Hi=(Hi-1+REV(k+1)%11+1)%13，i=1，2，…，m-1其中，函数REV(x)表示颠倒10进制数的各位，如REV(37)=73，REV(1)=1等。若插入的关键码序列为{2，8，31，20，19，18，53，27}。（1）试画出插入这8个关键码后的散列表。（2）计算检索成功的平均查找长度ASL。

单选题

设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为（）。

A. 21
B. 23
C. 41
D. 62

8