搜索
第1页共3页南京理工大学课程考试试卷（学生考试用）课程名称：数据结构学分：3大纲编号062204试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟组卷日期：2006年5月18日组卷教师（签字）张宏审定人（签字）王树梅学生班级：计算机学院04级学生学号：学生姓名：一、选择题（1.5*20=30分）1.若以{4，5，6，3，8}作为叶子结点的权值构造哈夫曼树，则带权路径长度是A)55B)68C)59D)282.无向图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,fB)a,c,f,e,b,dC)a,e,b,c,f,dD)a,e,d,f,c,b3.对关键字码集合K={53，30，37，12，45，24，96}，从空二叉树出发建立与集合K对应的二叉排序树，若希望得到树的高度最小，应选择下列哪个输入序列。A)45，24，53，12，37，96，30B)12，24，30，37，45，53，96C)37，24，12，30，53，45，96D)30，24，12，37，45，96，534.已知一组数{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)可行性、确定性和有穷性C)确定性、有穷性和稳定性D)易读性、稳定性和安全性6．设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为26的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是A)8B)3C)2D)97．在一个单链表中，若要删除p所指结点的后继结点，则执行。A)p=p-next;p-next=p-next-nextB)free(p-next)(C语言格式)或deletep-next(C++语言格式)C)p=p-next-next;D)p-next=p-next-next8.数组A的每个元素需要4个字节存放，数组有8行10列，若数组以行为主顺序存放在内存SA开始的存储区中，则A中8行5列的元素的位置是A)SA+74B)SA+292C)SA+296D)SA+3009-10．在一棵7阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有(1)个关键字；若在某结点中删去一个关键字而导致结点合并，则该结点中原有的关键字的个数是(2)。(1)A)6B)5C)4D)3(2)A)4B)3C)2D)111．已知四个元素a,b,c,d依次进栈，进栈过程中可出栈，下面那一种出栈顺序是不正确的A)a,d,c,bB)b,c,d,aC)c,a,d,bD)c,d,b,a12．队列操作的原则是。A)先进先出B)后进先出C)只能进行插入D)只能进行删除13．在有n个结点的二叉链表中,值为空链域的个数为第2页共3页A)n-1B)2n-1C)n+1D)2n+114．具有1080个结点的完全二叉树的深度为A)12B)10C)11D)1315．若已知一个栈的入栈序列是元素1，2，3，....，n，其输出序列为p1,p2,p3,…pn,若p1是n，则pi是()A)iB)n-iC)n-i+1D)不确定16．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是A)nB)(n-1)2C)n-1D)n217．对线性表进行二分查找时，要求线性表必须A)以顺序方式存储B)以链接方式存储C)以顺序方式存储，且数据有序D)以链接方式存储，且数据有序18．若用起泡排序对序列{14,26,29,41,52,5}从小到大排序,需要次比较A)15B)28C)3D)2119．有一个有序表为{1，3，9，12，32，41，45，62，70，77，82，95，100}，当二分查找值62的数据时要次比较成功。A)1B)2C)4D)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;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-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)个关键字；右边结点的关键字数是(12)。第3页共3页7.求图的最小生成树有两种算法，(13)算法适合于求稀疏图的最小生成树。8．一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向右)用自然数依此对结点编号，则编号最小的叶子的序号是(14)；编号是i的结点所在的层次号是(15)（根所在的层次号规定为1层）。三、简答题（35分）1．已知有向图的带权矩阵为：72205525613815121)（3分）画出该有向图。2)(3分)按Dijkstra算法,给出从顶点1(顶点标号从1计)到其余顶点的最短路径长度以及经过的中间点。3）（3分）画出该图邻接表存储结构示意图。4）（3分）画出对应无向图的最小生成树，给出生成树边权之和。(如果去掉方向后,一对顶点之间有两条以上的边,只保留权值最小的边)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分）已知三棵树的森林如下，试把它转化为二叉树AGN/\/|\/\BCHIKOP/|\/\/|\DEFLMRST4．（4分）按大顶堆将序列{56，8，15，80，10，22，28，50，60,40,90}调整为堆，写出最后的数据序列5．（4分）给出拓扑排序算法描述（不用写C/C++算法）四、算法设计（用类-C/类-C++描述）（16分）1．(8分)完成一个二叉树左右子树交换的递归算法。2．(8分)设在一个带头结点的双向链表中，所有结点的数据元素按值递增顺序排列，写一算法，删除表中所有大于min，小于max的元素（若存在）。双链表的定义如下：typedefstructDLnode{intdata;DLnode*pre,*next;}DLnode;第4页共3页南京理工大学课程考试试卷（学生考试用）课程名称：数据结构学分：3大纲编号062204试卷编号：考试方式：闭卷满分分值：100考试时间：120分钟组卷日期：2006年5月18日组卷教师（签字）张宏审定人（签字）王树梅学生班级：计算机学院04级学生学号：学生姓名：第5页共3页一、单项选择题(1.5*20=30分)1、对于序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从值为________的数据开始建初始堆。A）100B）12C）60D）152、若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是A）9B）11C）12D）不确定3、对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为A）DBFEACB）DFEBCAC）BDFECAD）BDEFAC4、5阶B树中，每个结点最多有个关键字。A）2B）3C）4D）55、设有一个二维数组a［m］［n］，假设a［0］［0］存放位置在644，a［2］［2］存放位置在676，每个元素占一个空间，则a［4］［5］在位置(数组元素以行为主存储)Ａ）692Ｂ）626Ｃ）709Ｄ）7246、一棵完全二叉树按顺序方式存储在一维数组chars[]={‘A’,’B’,’C’,’D’,’E’,’F’,’G’,’H’,’I’,’J’}中，则结点E在二叉树的第层。(注：根所在的层为1层)A）1B）2C）3D）47、下面说法不正确的是A）循环链表从任何一个结点出发，都能访问到所有结点B）一般树和二叉树的结点的孩子数都可以为0C）在拓扑排序序列中，若Vi在Vj之前，则必定存在从Vi到Vj的路径D）图（网）的最小代价生成树不是唯一的8、下面说法不正确的说法有个1）队列逻辑上是一个表头和表尾都能插入又能删除的线性表2)有n个顶点的无向图G的最小生成树T就是由G中具有最小权值n-1条边所构造出来的G的子图。3）在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及直接排序法都快。4)哈希表查找无需进行关键字的比较。A)1B)2C)3D)49、一个堆通常采用存储结构来存储A）顺序B）链接C）索引D）哈希(散列)10、长度为n的线性表中，_______都有一个直接前驱元素。A）任意元素B）除第n/2个元素C）除第一个元素D）除最后一个元素11、在由head所指的非空线性链表中删除由p指的链结点的下一个链结点的过程是依次执行q=p-next;_______;deleteq;A.)p-next=qB)q-next=pC)q-next=p-nextD)p-next=q-next12、稀疏矩阵采用三元组方法进行压缩存储的原因是A）0元素分布有规律B）非0元素分布有规律C）0元素多D）非0元素多13、已知一个有向图的弧集合为{a,b,a,c,a,d,b,d,b,e,d,e},则由该图产生的一种可能的拓扑序列为_____A）a,b,c,d,eB）a,c,d,e,bC）a,c,b,e,dD）a,c,d,b,e14、对于一个数据序列，按照给定的次序建立一个二叉排序树，该二叉排序树的形状取决于A）该序列的存储结构B）序列中的数据元素的取值范围C）数据元素的输入次序D）使用的计算机的软、硬件条件15、一组数据为(25,48,16,35,79,82,23,40,36,72),现在用某种排序算法进行一趟后的结果如下：16482535798223403672，则采用的是排序A）选择B）快速C）Shell(希尔)D）直接插