福建农林大学考试试卷 (A)卷(2)

福建农林大学考试试卷 (A)卷

9. 堆排序的时间复杂度为 （ ）。

A)O(n2) B)O(log2n) C)O(n) D)O(nlog2n) 10．已知Huffman树的总结点数为m，叶子数为n。则m与n 的关系是 （ ）。 A) m = 2n + 1 B) m = n + 1 C) m = 2n – 1 D) m = n - 1

二、填空题（本大题共20个空，每空2分，共40分）

1．在一个长度为n的线性表中删除第i个元素 (1≤i≤n)，需向前移动 个元素。 2. 下面程序段的时间复杂度是 。

long i=1 , s=0.0; while (s<n) { s=s+i; i++;}

3. 广义表(a，(a，b)，d，e，(h,((i，j)，k),g))深度是 。

4. 用折半查找方法从长度为11的有序表中查找一个元素时，平均查找长度为 。

5．连通无向图中有n个顶点e条边，进行最小生成树的prim算法时间复杂度是 。

6．图的广度优先遍历算法利用队列来完成，图的深度优先遍历算法利 来完成。 7． 一棵二叉排序树上按 方式进行遍历，会得到一个已排序好的结点序列。 8．线性表长度为n，排序码位数为d，基数为b，进行基数排序时间复杂度是 。 9．对长度为n的线性表进行分块查找，其ASL的最小值是 。 10．线性表长度为n，对其进行归并排序时间复杂度是 。

以下为算法填空

11．二叉树用以下静态二叉链表作为存储结构 #define n0 100 //数组最大下标 #define datatype char struct node

{ datatype data;