北邮数据结构期末试题与答案.pdf

试卷四 试卷四 . 22 1 . 22 1 一 填空题 （ 分，每空 分） 一 填空题 （ 分，每空 分） 1 n 1 n ．设待处理的问题规模为 ，若一个算法的时间复杂度为一个常数，则表示为（ ）， ．设待处理的问题规模为 ，若一个算法的时间复杂度为一个常数，则表示为（ ）， n*log 若一个算法的执行次数为 n*log 若一个算法的执行次数为 5n 5n，则时间复杂度表示为 （ ）。 2 ，则时间复杂度表示为 （ ）。 2 2 2．数据的逻辑结构主要分为 （ ）、（ ）、（ ）和 （ ）四种。 ．数据的逻辑结构主要分为 （ ）、（ ）、（ ）和 （ ）四种。 3 3  1  5  2  8  3  12  3．一棵度为 3 的树，若度为 1 的结点有 5 个，度为 2 的结点有 8 个，度为 3 的结点有 12  ．一棵度为 的树，若度为 的结点有 个，度为 的结点有 个，度为 的结点有 个，则该树有 （ ）叶子结点。 个，则该树有 （ ）叶子结点。 4 1000H 1 2 3 4 5 push push 4 1000H 1 2 3 4 5 push push ．设一个空栈，栈顶指针为 ，若有输入序列为 、 、 、 、 ，经过 、 、 ．设一个空栈，栈顶指针为 ，若有输入序列为 、 、 、 、 ，经过 、 、 pop push pop push push  4  pop push pop push push  4  、 、 、 、 后，输出序列是 （ ），若输入的每个数占 个 、 、 、 、 后，输出序列是 （ ），若输入的每个数占 个 H H 字节的空间，则栈顶指针为 （ ） 。 字节的空间，则栈顶指针为 （ ） 。 5 5．按照 （ ）遍历二叉排序树得到的序列是一个有序序列。 ．按照 （ ）遍历二叉排序树得到的序列是一个有序序列。 6 n  6．若哈夫曼树一共有 n 个叶子结点，则该哈夫曼树总结点数为 （