中级软件设计师数据结构章节练习(2018.11.18)

来源：考试资料网

1 在KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下（其中，j为模式串字符的序号）。对于模式串"abaabaca"，其next函数值序列为（）

2 对于线性表（由n个同类元素构成的线性序列），采用单向循环链表存储的特定之一是（）

3 无向图中一个顶点的度是指图中与该顶点相邻接的顶点数。若无向图G中的顶点数为n，边数为e，则所有顶点的度数之和为（）

4 一棵满二叉树，其每一层节点个数都达到最大值，对其中的节点从1开始顺序编号，即根节点编号为1，其左、右孩子节点编号分别为2和3，再下一层从左到右的编号为4、5、6、7，依次类推，每一层都从左到右依次编号，直到最后的叶子节点层为止，则用（）可判定编号为m和n的两个节点是否在同一层。

点击查看答案&解析

5.问答题问题1：根据以上说明和C代码，填充C代码中的空（1）～（5）。问题2：根据以上C代码，函数heapMaximum，heapExtractMax和maxHeapInsert的时间复杂度的紧致上界分别为（6）、（7）和（8）（用O符号表示）。问题3：若将元素10插入到堆A=（15，13，9，5，12，8，7，4，0，6，2，1）中，调用maxHeapInsert函数进行操作，则新插入的元素在堆A中第（9）个位置（从1开始）。

参考答案：问题1（1）A->int_array［0］（2）A->int_array［0］=A->int_array［A->arra...

点击查看完整答案&解析

进入题库练习

6 （）是由权值集合{8，5，6，2}构造的哈夫曼树（最优二叉树）。

点击查看答案&解析