《南理工04级至07级数据结构课程期末考试试卷及答案》由会员分享，可在线阅读，更多相关《南理工04级至07级数据结构课程期末考试试卷及答案（38页珍藏版）》请在金锄头文库上搜索。
1、南京理工大学课程考试试卷 （学生考试用）课程名称： 数据结构 学分： 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)282. 无向图G=（V，E），其中：V= a,b,c,d,e,f , E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,
2、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,b3. 对关键字码集合K=53，30，37，12，45，24，96，从空二叉树出发建立与集合K对应的二叉排序树，若希望得到树的高度最小，应选择下列哪个输入序列 。A)45，24，53，12，37，96，30 B)12，24，30，37，45，53，96C)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
3、，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)可行性、确定性和有穷性C) 确定性、有穷性和稳定性 D)易读性、稳定性和安全性6设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为26的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是 A) 8 B) 3 C)2 D)97在一个单链表中，若
4、要删除p所指结点的后继结点，则执行 。A) p=p-next; p-next=p-next-nextB) free(p-next) (C语言格式) 或 delete p-next (C+语言格式)C) p=p-next-next;D) p-next=p-next-next8. 数组A的每个元素需要4个字节存放，数组有8行 10列，若数组以行为主顺序存放在内存SA开始的存储区中，则A中8行5列的元素的位置是 A) SA+74 B)SA+292 C)SA+296 D)SA+3009-10在一棵7阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有 (1) 个关键字；若在某结点中删
5、去一个关键字而导致结点合并，则该结点中原有的关键字的个数是 (2) 。(1) A)6 B)5 C)4 D)3 (2) A)4 B)3 C)2 D)111已知四个元素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+114具有1080个结点的完全二叉树的深度为 A) 12 B)10 C)11 D)1315若
6、已知一个栈的入栈序列是元素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-1 D)n217对线性表进行二分查找时，要求线性表必须 A)以顺序方式存储 B)以链接方式存储C)以顺序方式存储，且数据有序 D)以链接方式存储，且数据有序18若用起泡排序对序列14,26,29,41,52,5从小到大排序,需要 次比较A)15 B) 28 C)3 D)2119有一个有序表为1，3，9，12，32，41，45，62，7
7、0，77，82，95，100，当二分查找值62的数据时要 次比较成功。A)1 B) 2 C) 4 D) 320设双向循环链表中结点的结构为（data,pre,next）。若在指针p所指结点之后插入结点s，则应执行下列 操作A)p-next=s; s-pre=p; p-next-pre=s; s-next=p-next;B)p-next=s; p-next-pre=s; s-pre=p; s-next=p-next;C)s-pre=p; s-next=p-next; p-next=s; p-next-pre=s; D)s-pre=p; s-next =p-next; p-next-pre=s;
8、p-next=s;二、填空题（19分,其余每空1分）1已知h是无表头结点的单链表，且p结点既不是首元结点，亦不是尾元结点，试从下列提供答案中选择合适的语句序列(给出序号)：a.在p结点后插入s结点的语句序列是 (1) ；b. 在p结点前插入s结点的语句序列是 (2) ；c.在表首插入s结点的语句序列是 (3) ；d. 在表尾插入s结点的语句序列是 (4) ；(1) p-next=s;(2) p-next=p-next-next;(3) p-next=s-next;(4) h=s;(5) p=h;(6) s-next=NULL;(7) q=p;(8) while(p-next!=NULL)p=p
9、-next; (9) while(p-next!=q )p=p-next;(10) p=q;(11) p=h; s-next=h;(12) h=p; (13) s-next=p-next;2图的遍历分为 (5) 和 (6) 。3假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA，则先序序列为： (7) 。4深度为k的完全二叉树至少有 (8) 个结点；至多有 (9) 结点。5在一棵二叉树中，度为1的结点有40个，总的结点数为99，则二叉树中叶子结点数共有 (10) 。6在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂时，则左边结点有 (11) 个关
10、键字；右边结点的关键字数是 (12) 。7.求图的最小生成树有两种算法， (13) 算法适合于求稀疏图的最小生成树。8一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向右)用自然数依此对结点编号，则编号最小的叶子的序号是 (14) ；编号是i的结点所在的层次号是 (15) （根所在的层次号规定为1层）。三、简答题（35分）1 已知有向图的带权矩阵为：1)（3分）画出该有向图。2) (3分) 按Dijkstra算法,给出从顶点1(顶点标号从1计)到其余顶点的最短路径长度以及经过的中间点。 3）（3分）画出该图邻接表存储结构示意图。4）（3分）画出对应无向图的最小生成树，给出生成树边
11、权之和。(如果去掉方向后,一对顶点之间有两条以上的边,只保留权值最小的边)2已知关键字的集合56，8，15，80，10，22，28，50，60,40,90（1）（3分）试按给出的序列构造一棵平衡二叉树。（2）（3分）试构造3阶B_树。（3）（3分）写出依次删除关键字60,40后的B_树。（4）（3分）按以上数据, 用链地址法处理冲突(Hash函数H（key）=key % 13)，画出示意图(不要写算法) 3（3分）已知三棵树的森林如下，试把它转化为二叉树 A G N / / | / B C H I K O P / | / / | D E F L M R S T4（4分）按大顶堆将序列56，8，
12、15，80，10，22，28，50，60,40,90调整为堆，写出最后的数据序列5（4分）给出拓扑排序算法描述（不用写C/C+算法）四、算法设计（用类-C/类-C+描述）（16分）1(8分)完成一个二叉树左右子树交换的递归算法。2(8分)设在一个带头结点的双向链表中，所有结点的数据元素按值递增顺序排列，写一算法，删除表中所有大于min，小于max的元素（若存在）。双链表的定义如下： typedef struct DLnode int data; DLnode *pre, *next; DLnode; 南京理工大学课程考试试卷 （学生考试用）课程名称： 数据结构 学分： 3 大纲编号 062204 试卷编号： 考试方式： 闭卷 满分分值： 100 考试时间： 120 分钟组卷日期： 2006年5月18日 组卷教师（签字） 张宏 审定人（签字） 王树梅 学生班级： 计算机学院 04级 学生学号： 学生姓名： 一、 单项选择题(1.5*20=30分)1、 对于序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从值为_的数据开始建初始堆。A）100 B）12 C）60 D）1
