[南理工04级至07级数据结构课程期末考试试卷及答案.docVIP

南京理工大学课程考试试卷 （学生考试用） 课程名称： 数据结构 学分： 3 大纲编号 062204 试卷编号： 考试方式： 闭卷 满分分值： 100 考试时间： 120 分钟 组卷日期： 2006年5月18日 组卷教师（签字） 张宏 审定人（签字） 王树梅 学生班级： 计算机学院 04级 学生学号： 学生姓名： 选择题（1.5*20=30分） 1.若以{4，5，6，3，8}作为叶子结点的权值构造哈夫曼树，则带权路径长度是 A) 55 B)68 C)59 D)28 2. 无向图G=（V，E），其中：V={ a,b,c,d,e,f} , E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行广度优先遍历，得到的顶点序列正确的是 A) a,b,e,c,d,f B) a,c,f,e,b,d C) a,e,b,c,f,d D) a,e,d,f,c,b 3. 对关键字码集合K={53，30，37，12，45，24，96}，从空二叉树出发建立与集合K对应的二叉排序树，若希望得到树的高度最小，应选择下列哪个输入序列 。 A)45，24，53，12，37，96，30 B)12，24，30，37，45，53，96 C)37，24，12，30，53，45，96 D)30，24，12，37，45，96，53 4. 已知一组数{20，8，6，2，30，1}的排序过程为： （1）20，8，6，2，30，1 （2）1，8，6，2，30，20 （3）1，2，6，8，30，20 （4）1，2，6，8，20，30 问它是下面那一种排序： A)快速排序 B) 直接插入排序 C) 起泡排序 D) 选择排序 5．计算机算法必须具备输入、输出和 等五个特征。 A) 可行性、可移植性和可扩充性 B)可行性、确定性和有穷性 确定性、有穷性和稳定性 D)易读性、稳定性和安全性 6．设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为26的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是 A) 8 B) 3 C)2 D)9 7．在一个单链表中，若要删除p所指结点的后继结点，则执行 。 A) p=p-next; p-next=p-next-next B) free(p-next) (C语言格式) 或 delete p-next (C++语言格式) C) p=p-next-next; D) p-next=p-next-next 8. 数组A的每个元素需要4个字节存放，数组有8行 10列，若数组以行为主顺序存放在内存SA开始的存储区中，则A中8行5列的元素的位置是 A) SA+74 B)SA+292 C)SA+296 D)SA+300 9-10．在一棵7阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有 (1) 个关键字；若在某结点中删去一个关键字而导致结点合并，则该结点中原有的关键字的个数是 (2) 。 (1) A)6 B)5 C)4 D)3 (2) A)4 B)3 C)2 D)1 11．已知四个元素a,b,c,d依次进栈，进栈过程中可出栈，下面那一种出栈顺序是不正确的 A)a,d,c,b B)b,c,d,a C)c,a,d,b D)c,d,b,a 12．队列操作的原则是 。 A) 先进先出 B) 后进先出 C) 只能进行插入 D)只能进行删除 13．在有n 个结点的二叉链表中,值为空链域的个数为 A)n-1 B)2n-1 C)n+1 D)2n+1 14．具有1080个结点的完全二叉树的深度为 A) 12 B)10 C)11 D)13 15．若已知一个栈的入栈序列是元素1，2，3，....，n，其输出序列为p1,p2,p3,…pn,若p1是n，则pi是( ) A) i B)n-i C)n-i+1 D)不确定 16．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是 A) n B)(n-1)2 C)n-