数据结构章节练习(2020.06.06)

来源：考试资料网

1 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要平均比较的结点数是（）

2 在二维数组A[8][10]中，每一个数组元素A[i][j]占用3个存储空间，所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储空间是（）。

3.填空题用普里姆（Prim）算法求具有n个顶点e条边的图的最小生成树的时间复杂度为（）；用克鲁斯卡尔（Kruskal）算法的时间复杂度是（）。若要求一个稀疏图G的最小生成树，最好用（）算法来求解；若要求一个稠密图G的最小生成树，最好用（）算法来求解。

参考答案：O（n²）；O（elog₂e）；Kruskal；Prim

4.填空题假定一个顺序表的长度为50，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度（），在查找不成功情况下的平均查找长度（）

5 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）。

6.判断题栈不是一种线性结构。

7.判断题十字链表是图的一种存储结构，是由邻接表和逆邻接表构成的。

8.问答题简述在链接栈中插入一个元素的操作过程。

参考答案：链接栈的插入操作，先将待进栈结点的指针域指向原来的栈顶结点，然后将栈顶指针top修改指向该结点，使进栈元素结点成为新的栈...

9.问答题 已知有向图用邻接表为存储结构（如下），设计一算法计算有向图每一顶点的度的算法。

10 设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）