6.已知完全二叉树有26个结点,则整棵二叉树有多少个度为1的结点?( A.1 0 C.2 不确定 7.已给下图,哪一项是该图的拓扑排序? A.1,2,3,4,5 B.1,3,2,4,5 C.1,2,4,3,5 D.1,2,3,5,4 8.在常用的哈希表处理冲突的方法中,哪一种方法容易产生“二次聚集”( A.开放定址法B.再哈希法C.链地址法E.都不会产生 9.直接插入排序的算法复杂性是多少? AO(n2) B O(nlogn) C O(n) D. O(ogn) 10串联文件的记录之间有何关系? A相继的两个物理记录的存储位置相邻 B.物理记录之间的次序由指针相联 C.两个逻辑相邻的记录物理上相邻 D.都不是 得分评卷人 三、简释名词(每小题3分,共15分) 1.线索二叉树 2.拓扑排序 3.关键路径 4.堆排序 直接存取文件 得分评卷人 四、简答题(每小题5分,共30分) 1.已给一个栈S,写出对S的所有操作。 2.以数据集{3,4,5,8,12,18}为叶结点的权值,构造一棵哈夫曼树 写出其邻接矩阵,并画出从顶点0"(2 3.已给右图 开始的最小生成树。 4.已给输入序列{17,60,29,38,42,50},按除留余数法,填写如下哈希表。其中除留余数 法的公式如下: H (key )=key %11 当出现冲突时,按H=(H(key)+1)MOD11的线性探测再散列的方法进行 地址|o123|45678910 5.已给有8个的无序序列:{49,38,65,97,76,13,27,49},画出建立初始堆的过程的示6．已知完全二叉树有 26 个结点，则整棵二叉树有多少个度为 1 的结点？ （ ） A．1 B．0 C．2 D．不确定 7．已给下图，哪一项是该图的拓扑排序？ （ ） A．1，2，3，4，5 B．1，3，2，4，5 C．1，2，4，3，5 D．1，2，3，5，4 8．在常用的哈希表处理冲突的方法中，哪一种方法容易产生“二次聚集” （ ） A．开放定址法 B．再哈希法 C．链地址法 E．都不会产生 9．直接插入排序的算法复杂性是多少？ （ ） A．O（n 2） B. O（nlogn） C. O(n) D. O(logn) 10.串联文件的记录之间有何关系? A 相继的两个物理记录的存储位置相邻 B．物理记录之间的次序由指针相联 C．两个逻辑相邻的记录物理上相邻 D．都不是 得分 评卷人 1． 线索二叉树 2． 拓扑排序 3． 关键路径 4． 堆排序 5． 直接存取文件 得分 评卷人 1． 已给一个栈 S，写出对 S 的所有操作。 2． 以数据集{3，4，5，8，12，18}为叶结点的权值，构造一棵哈夫曼树。 3． 已给右图 写出其邻接矩阵，并画出从顶点① 开始的最小生成树。 4． 已给输入序列{17，60，29，38，42，50}，按除留余数法，填写如下哈希表。其中除留余数 法的公式如下： H（key）=key % 11 当出现冲突时，按 Hi=（H（key）+1）MOD 11 的线性探测再散列的方法进行。 地址 0 1 2 3 4 5 6 7 8 9 10 关键字 5． 已给有 8 个的无序序列：{49，38，65，97，76，13，27，49}，画出建立初始堆的过程的示 三、简释名词（每小题 3 分，共 15 分） 四、简答题（每小题 5 分，共 30 分） 5 1 2 3 4 5 1 3 2 4 6 12 2 3 4 6 7 5