南理工计算机系数据结构2004数据结构B.doc

南京理工大学课程考试试卷 （学生考试用）课程名称： 数据结构 学分： 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）152、若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是 A）9 B）11 C）12 D）不确定3、对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为 A）DBFEAC B）DFEBCA C）BDFECA D）BDEFAC4、5阶B树中，每个结点最多有 个关键字。 A）2 B）3 C）4 D）55、设有一个二维数组amn，假设a00存放位置在644，a22存放位置在676，每个元素占一个空间，则a45在 位置 (数组元素以行为主存储) ）692）626 ）709）7246、一棵完全二叉树按顺序方式存储在一维数组char s=A,B,C,D,E,F,G,H,I,J中，则结点E在二叉树的第 层。(注：根所在的层为1层) A）1 B）2 C）3 D）47、下面说法不正确的是 A）循环链表从任何一个结点出发，都能访问到所有结点 B）一般树和二叉树的结点的孩子数都可以为0 C）在拓扑排序序列中，若Vi在Vj之前，则必定存在从Vi到Vj的路径 D）图（网）的最小代价生成树不是唯一的8、下面说法不正确的说法有 个 1）队列逻辑上是一个表头和表尾都能插入又能删除的线性表 2) 有n个顶点的无向图G的最小生成树T就是由G中具有最小权值n-1条边所构造出来的G的子图。 3）在10万个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及直接排序法都快。4) 哈希表查找无需进行关键字的比较。A) 1 B)2 C) 3 D)49、一个堆通常采用 存储结构来存储A）顺序 B）链接 C）索引 D）哈希(散列)10、长度为n的线性表中，_都有一个直接前驱元素。 A）任意元素 B）除第n/2个元素 C）除第一个元素 D）除最后一个元素11、在由head所指的非空线性链表中删除由p指的链结点的下一个链结点的过程是依次执行 q=p-next ; _; delete q ;A.) p-next=q B) q-next=p C) q-next=p-next D)p-next=q-next12、稀疏矩阵采用三元组方法进行压缩存储的原因是 A）0元素分布有规律 B）非0元素分布有规律 C）0元素多 D）非0元素多13、已知一个有向图的弧集合为,则由该图产生的一种可能的拓扑序列为_ A）a,b,c,d,e B）a,c,d,e,b C）a,c,b,e,d D）a,c,d,b,e14、对于一个数据序列，按照给定的次序建立一个二叉排序树，该二叉排序树的形状取决于 A）该序列的存储结构 B）序列中的数据元素的取值范围C）数据元素的输入次序 D）使用的计算机的软、硬件条件15、一组数据为(25,48,16,35,79,82,23,40,36,72),现在用某种排序算法进行一趟后的结果如下：16 48 25 35 79 82 23 40 36 72，则采用的是 排序 A）选择 B）快速 C）Shell(希尔) D）直接插入16、链表不具有的特点是_.A）可随机访问任一元素 B）插入删除不需要移动元素C）不必事先估计存储空间 D）所需空间与线性表长度成正比17、 在有n个叶子的哈夫曼树中，其结点总数为_。A)不确定 B）2n C）2n+1 D）2n-118、任何一个无向带权连通图的最小生成树_。A)只有一棵 B）有一棵或多棵 C）一定有多棵 D）可能不存在19、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为_。A）98 B）99 C）50 D）4820、下面说法正确的是 1）二叉树的前序遍历序列中，任意一个结点均处于其子孙结点的前面 2) 一棵树的先序遍历序列同它对应的转换后的二叉树的中序遍历序列相同 3) 二叉线索树中每个结点都有指向前驱和后继的指针 A）1 B）2 C）1)和3） D） 1）和2)二、 填空题（1*16=16分）1、已知一有个链表表示的栈，栈顶指针为top, 退栈后，对top的操作是 (1) （用C/C+语句描述，每个结点的两个域为值域data和指针域next）2、若由3，6，8，12，10构成一棵哈夫曼树，则该树的高度是 (2) ，带权路径长度为 (3) ；3、求从指定源点到其余各顶点的最短路径长度的算法中，弧上权须为正的原因是 （4） ；4图的 (5) 遍历是一种递归的算法，图的 (6) 遍历算法需要使用队列。5写出两个排序算法的名字,其平均排序时间为O(nlog2n): (7) 。6有2049个结点的二叉树至少高 (8) 个结点；最大高度可达 (9) 。7在一棵二叉树中，度为1的结点有31个，总的结点数为50，则二叉树中叶子结点数共有 (10) 。8在一棵11阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂时，则左边结点有 (11) 个关键字；右边结点的关键字数是 (12) 。9.快速排序在 (13) 情况下效率最坏；此时，时间复杂度达到 （14） 10一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向右)用自然数依此对结点编号，则编号最小的叶子的序号是 (15) ；编号是i的结点所在的层次号是 (16) （根所在的层次号规定为1层）。三、简答题（40分）1 已知有向图G有6个顶点（顶点号从1计），弧集E如下：(其中弧后面冒号后数表示弧上的权) E=:12，:15,:8,:13,:6,:25,:5,:5,:20,:2,:7完成问题1）至 4）1)（3分）画出该有向图。2) (3分) 按Dijkstra算法,给出从顶点1(顶点标号从1计)到其余顶点的最短路径长度以及经过的中间点。 3）（3分）画出该图邻接表存储结构示意图。4）（3分）上图去除弧上方向（去方向后，若两个顶点有两条边，去权值大的边），画出对应无向图的最小生成树，给出生成树边权之和。2已知关键字的集合56，8，15，80，10，22，28，50，60,40,90（1）（4分）试按给出的序列构造一棵平衡二叉树。（2）（4分）试构造3阶B_树。（3）（4分）写出依次删除关键字56,90后的B_树。（4）（4分）按以上数据, 用链地址法处理冲突(Hash函数H（key）=key % 13)，画出示意图(不要写算法) 3（4分）已知三棵树的森林如下，试把它转化为二叉树 A G N / / | / B C H I K O P / | / / | D E F L M R S T4（4分）按大顶堆将序列56，8，15，80，10，22，28，50，60,40,90调整为堆，写出最后的数据序列5（4分）给出求最小生成树的Kruskal算法描述（不用写C/C+算法）四、算法设计（用类-C/类-C+描述）