《南理工04级至07级数据结构课程期末考试试卷及答案.pdf》由会员分享，可在线阅读，更多相关《南理工04级至07级数据结构课程期末考试试卷及答案.pdf（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、南京理工大学课程考试试卷（学生考试用）课程名称：数据结构 学分：3 大 纲 编 号062204试卷编号：考试方式：闭卷 满分分值：100 考试时间：120 分钟组卷口期：2006年5月1 8日 组卷教师（签字）补 宏 审定人（签字）树 林学生班级：计算机学院04级 学生学号：学生姓名：一、选 择 题(1.5*2 0=3 0 分)1 .若以4,5,6,3,8 作为叶子结点的权值构造哈夫曼树，则带权路径长度是一A)55 B)6 8 C)5 9 D)2 82 l o l 1 1 G (V E),.比 中.V (a b c d e f)E=(a,b),(a,e),(a,c t(b：e),(c,f)：(
2、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,b3 .对关键字码集合1 ne xt;p-ne xt=p-ne xt-ne xtB)fr e e (p-ne xt)(C 语言格式)或 d e l e t e p-n e x t (C+语言格式)C)p=p-n e x t-n e x t;D)p-n e x t=p-n e x t-n e x t8 .数组A的每个元素需要4个字节存放，数组有8行 1 0 歹 ij,若数组以行为主顺序存放在内存S A 开始的存储区中，则
3、A中 8 行 5 列的元素的位置是一A)S A+74 B)S A+2 9 2 O S A+2 9 6 D)S A+3 0 09-1 0.在一棵7 阶 B 树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有(1)个关键字:若在某结点中删去一个关键字而导致结点合并，则该结点中原有的关键字的个数是(2)。(1)A)6 B)5 C)4 D)3(2)A)4 B)3 C)2 D)11 1 .已知四个元素a,b,c,d 依次进栈，进栈过程中可出栈，下面那一种出栈顺序是不正确的A)a,d,c,b B)b,c,d,a C)c,a,d,b D)c,d,b,a1 2 .队列操作的原则是 oA)先进先
4、出 B)后进先出 0 只 能 进 行 插 入 D)只能进行删除1 3 .在有n个结点的二叉链表中，值为空链域的个数为A)n-1 B)2 n-1 C)n+1 D)2 n+11 4 .具 有 1 0 8 0 个结点的完全二叉树的深度为A)1 2 B)1 0 O il D)1 31 5 .若已知一个栈的入栈序列是元素1,2,3.n,其输出序列为P b P 2,P 3,P”,若出是n,则 8是()A)i B)n-i C)n-i+1 D)不确定1 6 .对 于 个 具 有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是A)n B)(n-1)C)n-1 D)n第 2 页 共 3 页1 7.对线性
5、表进行二分查找时，要求线性表必须A)以顺序方式存储 B)以链接方式存储C)以顺序方式存储，且数据有序 D)以链接方式存储，且数据有序1 8 .若用起泡排序对序列 1 4,2 6,2 9,4 1,5 2,5 从小到大排序,需要 次比较A)1 5 B)2 8 C)3 D)2 11 9 .有一个有序表为 1,3,9,1 2,3 2,4 1,4 5,6 2,70,77,8 2,9 5,1 0 0 ,当二分查找值 6 2的数据时要 次比较成功。A)1 B)2 C)4 D)32 0 .设双向循环链表中结点的结构为(d a t a,p r e,n e x t),若在指针p 所指结点之后插入结点s,则应执行下
6、列 操作A)p-n e x t=s;s-p r e=p;p-n e x t-p r e=s;s-n e x t=p-n e x t;B)p-n e x t=s;p-n e x t-p r e=s;s-p r e=p;s-n e x t=p-n e x t;C)s-p r e=p;s-n e x t=p-n e x t;p-n e x t=s;p-n e x t-p r e=s;D)s-p r e=p;s-n e x t =p-n e x t;p-n e x t-p r e=s;p-n e x t=s;二、填 空 题(1 9 分，其余每空1 分)1 .已知h是无表头结点的单链表，且 p结点既不是
7、首元结点，亦不是尾元结点，试 从 F列提供答案中选择合适的语句序列(给出序号)：a.在 p结点后插入s 结点的语句序列是(1)b.在 p结点前插入s 结 点 的 语 句 序 列 是(2)C.在表首插入S 结 点 的 语 句 序 列 是 d.在表尾插入S 结 点 的 语 句 序 列 是(1)p-n e x t=s;(2)p-n e x t=p-n e x t-n e x t;(3)p-n e x t=s-n e x t;(4)h=s;(5)p=h;(6)s-n e x t=N U L L;(7)q=p;(8)w h il e(p-n e x t!=N U L L)p=p-n e x t;(9)w
8、 h il e(p-n e x t!=q )p=p-n e x t;(1 0)p=q;(1 1)p=h;s-n e x t=h;(1 2)h=p;(1 3)s-n e x t=p-n e x t;2 .图的遍历分为 和 。3 .假设一棵二叉树的中序序列为DC B GEA HFIJK 和后序序列为DC EGB FHK JIA,则先序序列为：_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ Q)_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。4 .深度为k 的完全二叉树至少有3 个结点；至多有(9)结点。5 .在一棵二叉树中，度 为 1 的结点有4 0 个，总的结点数
9、为9 9,则二叉树中叶子结点数共有一(1 0)Q6 .在一棵m阶 B-树中，若在某结点中插入一个新关键字而引起该结点分裂时，则左边结点有(1 1)个关键字:右边结点的关键字数是(1 2)。7 .求图的最小生成树有两种算法，(1 3)算法适合于求稀疏图的最小生成树。8 .一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向右)用自然数依此对结点编号，则编号最小的叶子的序号是(1 4)；编号是i 的结点所在的层次号是(1 5)(根所在的层次号规定为1 层)。三、简 答 题(3 5 分)1.已知有向图的带权矩阵为：00120015800000013000000COco0000000060
10、025000050000005002000002007001）（3 分）画出该有向图。2）（3分）按 D i j k s t r a 算法，给出从顶点1（顶点标号从1 计）到其余顶点的最短路径长度以及经过的中间点。3）（3分）画出该图邻接表存储结构示意图。4）（3分）画出对应无向图的最小生成树，给出生成树边权之和。（如果去掉方向后,一对顶点之间有两条以上的边,只保留权值最小的边）2.已知关键字的集合5 6,8,1 5,8 0,1 0,2 2,2 8,5 0,6 0,4 0,90（1）（3分）试按给出的序列构造一棵平衡二叉树。（2）（3分）试构造3阶电树。（3）（3分）写出依次删除关键字6 0,
11、4 0 后的B _ 树。（4）（3分）按以上数据，用链地址法处理冲突（Ha s h 函数H（k ey）-k ey%1 3）,画出示意图（不要写算法）3.（3分）已知三棵树的森林如下，试把它转化为二叉树A G N/I /B C H I K 0 P/I /I D E F L M R S T4.（4分）按大顶堆将序列5 6,8,1 5,8 0,1 0,2 2,2 8,5 0,6 0,4 0,90 调整为堆,写出最后的数据序列5.（4分）给出拓扑排序算法描述（不用写C/C+算法）四、算法设计（用类-C/类-C+描述）（1 6 分）1.（8分）完成一个二叉树左右子树交换的递归算法。2.（8分）设在一个带
12、头结点的双向链表中，所有结点的数据元素按值递增顺序排列，写一算法，删除表中所有大于m i n,小于m a x 的 元 素（若存在）。双链表的定义如下：t y p ed ef s t r u c t D L n o d ei n t d a t a;D L n o d e*p r e,*n ex t;D L n o d e;第4页 共3页南 京 理 工 大 学 课 程 考 试 试 卷 (学生考试用)课程名称：数据结构 学分：3 大 纲 编 号 0 6 2 2 0 4试卷编号：考试方式：闭卷 满分分值：1 0 0 考试时间：1 2 0 分钟组卷日期：2 0 0 6 年 5月 1 8 日 组卷教师(
13、签 字)秘宏 审定人(签 字)上树林学生班级：计算机学院0 4 级 学生学号：学生姓名：一、单项选择题(1.5*2 0=3 0 分)1、对于序列(1 2,1 3,1 1,1 8,6 0,1 5,7,1 8,2 5,1 0 0),用筛选法建堆，必须从值为的数据开始建初始堆。A)1 0 0 B)1 2 C)6 0 D)1 52、若一棵二叉树具有1 0 个度为2的结点，则该二叉树的度为0的结点个数是一A)9 B)1 1 C)1 2 D)不确定3、对某二叉树进行前序遍历的结果为A B D EFC,中序遍历的结果为D B FEA C,则后序遍历的结果为A)D B FEA C B)D FEB C A C)
14、B D FEC A D)B D EFA C4、5 阶 B 树中，每个结点最多有 个关键字。A)2 B)3 C)4 D)55、设有一个二维数组a m n,假设a 0 0 存放位置在6 4 4,a 2 2 存放位置在6 7 6,每个元素占一个空间，则 a 4 5 在 位置(数组元素以行为主存储)A)6 9 2 B)6 2 6 C)7 0 9 D)7 2 46、一棵完全二叉树按顺序方式存储在一维数组c h a r s =A ,B ,C ,D ,E ,F,G,H ,I J J )中，则结点E 在二叉树的第 层。(注：根所在的层为 1 层)A)1 B)2 C)3 D)47、下面说法不正确的是A)循环链表
15、从任何个结点出发，都能访问到所有结点B)一般树和二叉树的结点的孩子数都可以为0C)在拓扑排序序列中，若 V i 在匕之前，则必定存在从到V 的路径D)图(网)的最小代价生成树不是唯一的8、下面说法不正确的说法有 个1)队列逻辑上是一个表头和表尾都能插入又能删除的线性表2)有 n个顶点的无向图G 的最小生成树T就是由G 中具有最小权值n-1 条边所构造出来的G的子图。3)在 1 0 万个随机排列的数据中，要选出5 个最小的数，采用快速排序比采用S h e ll排序、堆排序及直接排序法都快。4)哈希表查找无需进行关键字的比较。A)1 B)2 C)3 D)49、一个堆通常采用 存储结构来存储A)顺序
16、 B)链 接 C)索引 D)哈希(散列)1 0、长度为n的线性表中，都有一个直接前驱元素。A)任意元素B)除第n/2 个元素 C)除第一个元素D)除最后一个元素1 1、在由he a d 所指的非空线性链表中删除由p指的链结点的下一个链结点的过程是依次执行q=p-n e x t;d e l e t e q;A.)p-n e x t=q B)q-n e x t=p C)q-n e x t=p-n e x t D)p-n e x t=q-n e x t1 2、稀疏矩阵采用三元组方法进行压缩存储的原因是A)0元素分布有规律B)非 0元素分布有规律 C)0元素多 D)非 0元素多1 3、已知一个有向图的
17、弧集合为,va,d,vb,d,，则由该图产生的一种可能的拓扑序列为A)a,b,c,d,e B)a,c,d,e,b C)a,c,b,e,d D)a,c,d,b,e1 4、对于一个数据序列，按照给定的次序建立一个二叉排序树，该二叉排序树的形状取决于_A）该序列的存储结构 B）序列中的数据元素的取值范围C）数据元素的输入次序 D）使用的计算机的软、硬件条件1 5、一组数据为（2 5,4 8,1 6,35,7 9,8 4 2 3,4 0,36,7 2）,现在用某种排序算法进行一趟后的结果如下：1 6 4 82 5 35 7 9 8 2 2 3 4 0 36 7 2,则采用的是 排序A）选择 B）快 速
18、 C）S he l l （希尔）D）直接插入1 6、链 表 不 具 有 的 特 点 是.A）可随机访问任一元素 B）插入删除不需要移动元素C）不必事先估计存储空间 D）所需空间与线性表长度成正比1 7、在有n个叶子的哈夫曼树中，其结点总数为 oA）不确定 B）2 n C）2 n+l D）2 n-l1 8、任何一个无向带权连通图的最小生成树 oA）只 有 一 棵 B）有一棵或多棵C）一定有多棵D）可能不存在1 9、将一棵有1 0 0 个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1,则编号为4 9 的 结 点 的 左 孩 子 编 号 为。A）9 8 B）9
19、9 C）5 0 D）4 82 0、下面说法正确的是1）二叉树的前序遍历序列中，任意一个结点均处于其子孙结点的前面2）一棵树的先序遍历序列同它对应的转换后的二叉树的中序遍历序列相同3）二叉线索树中每个结点都有指向前驱和后继的指针A）1 B）2 C）1）和 3）D）1）和 2）二、填 空 题（1*1 6=1 6 分）1、已知一有个链表表示的栈，栈顶指针为t o p,退栈后，对 t o p 的 操 作 是（1）（用 C/C+语句描述，每个结点的两个域为值域da t a 和指针域n ex t）2、若由3,6,8,1 2,1 0 构成一棵哈夫曼树，则该树的高度是（2）,带权路径长度为（3）；3、求从指定
20、源点到其余各顶点的最短路径长度的算法中，弧上权须为正的原因是（4）；4 .图 的（5）遍历是一种递归的算法,图的（6）遍历算法需要使用队列。5 .写出两个排序算法的名字,其平均排序时间为0（n l o g2n）:_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _（7）_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。6 .有 2 0 4 9 个结点的二叉树至少高（8）个结点;最大高度可达（9）。7 .在一棵二叉树中，度 为 1 的结点有3 1 个，总的结点数为5 0,则二叉树中叶子结点数共有一（1 0）Q8 .在一棵1 1 阶 B-树中，若在某结点中插入一个新
21、关键字而引起该结点分裂时，则左边结点有（1 1）个关键字:右边结点的关键字数是（1 2）o9.快速排序在（1 3）情况下效率最坏;此时，时间复杂度达到（1 4）1 0.一个深度为k 的，具有最少结点数的完全二叉树按层次，（同层次从左向右）用自然数依此对结点编号，则编号最小的叶子的序号是（1 序；编号是i 的结点所在的层次号是（1 6）（根所在的层次号规定为1 层）。三、简 答 题（4 0 分）2.已知有向图G有 6 个 顶 点（顶点号从1 计），弧集E如下：（其中弧后面冒号后数表示弧上的权）E=:1 2,:1 5,:8,:1 3,:6,:2 5,:5,:5,:2 0,:2,:7 完成问题1）至
22、 4）1）（3 分）画出该有向图。2）（3分）按 D ij ks t r a 算法,给出从顶点1 （顶点标号从1 计）到其余顶点的最短路径长度以及经过的中间点。3）（3分）画出该图邻接表存储结构示意图。4）（3分）上图去除弧上方向（去方向后，若两个顶点有两条边，去权值大的边），画出对应无向图的最小生成树，给出生成树边权之和。第6页 共3页2.已知关键字的集合 5 6,8,1 5,8 0,1 0,2 2,2 8,5 0,6 0,4 0,9 0（1）（4分）试按给出的序列构造一棵平衡二叉树。（2）（4分）试构造3 阶上树。（3）（4分）写出依次删除关键字5 6,9 0 后的B _ 树。（4分）按以
23、上数据,用链地址法处理冲突（H a s h函数H （key）-key%1 3）,画出示意图（不要写算法）3.（4 分）已知三棵树的森林如下，试把它转化为二叉树AGN/1 /B CH I K0 P/1 /1 D E FL MR S T4.（4分）按大顶堆将序列 5 6,8,15,8 0,10,22,28,5 0,6 0,4 0,90 调整为堆,写出最后的数据序列5.（4分）给出求最小生成树的K r u s ka l算法描述（不用写C/C+算法）四、算法设计（用类-C/类-C+描述）（14 分）1.（7 分）完成一个求二叉树叶子的递归算法tr e e le a f （p）。（p 为二叉树根）2.（
24、7 分）有 n个顶点的有向图用邻接表a d j 表 示，写算法f in d d e gr e e 求出所有顶点的出度,结果放在数组o u td e gr e e i 中（O W i W n）。（o u td e gr e e i 表示顶点i+1的出度，图的顶点号从1计）南 京 理 工 大 学 课 程 考 试 试 卷 （学生考试用）课程名称：数据结构 学分：3 大 纲 编 号 06 2204试卷编号：考试方式：闭卷 满分分值：100 考试时间：120 分钟组卷日期：2007 年 6月 4日 组卷教师（签字）祢宏 审 定 人（签字）工相检学生班级：计算机学院05 级二、选 择 题（2*20=4 0
25、分）1.不是算法的基本特征A）可行性 B）长度有限C）在有限时间内完成 D）确定性2.某算法的时间复杂度为0（r），表明该算法的A）问题规模是n,B）执行时间等于n,C）执行时间与祐成正比D）问题规模与r?成正比3.设 n个元素进栈序列是P 1,P 2,P 3,P n,其输出序列是1,2,3,n,若 p 3=3,则 P l的值为_A）可能是2 B）一定是24.链表不具备的特点是_A）可随机访问任一结点0不必事先估计存储空间C）不可能是1 D）一定是1B）插入、删除不需要移动元素D）所需空间与其长度成正比5 .最 不 合 适 用 作 链 队 的 链 表 是=A）只带队首指针的非循环单链表B）只带
26、队首指针的循环双链表C）只带队尾指针的循环双链表 D）只带队尾指针的循环单链表6 .设二维数组A6 10,每个数组元素占用4个字节，若按行优先顺序存放时，数组元素A3 5 的存储地址为1000,则 A0 0 的存储地址是一A）8 7 2 B）8 6 0 C）8 6 8 D）8 6 47 .以 下 不 是 堆 的 序 列 是。A）100,8 5,98,7 7,8 0,6 0,8 2,4 0,20,10,6 6B）100,98,8 5,8 2,8 0,7 7,6 6,6 0,4 0,20,10O10,20,4 0,6 0,6 6,7 7,8 0,82,85,98,100D）100,8 5,4 0,
27、7 7,8 0,6 0,6 6,98,8 2,10,208 .一棵完全二叉树上有1001个结点，其中叶子结点的个数是A）25 0 B）5 00 05 05 D）5 019.无向图的邻接矩阵是一个 矩阵。A）对称 B）零 C）上三角 D）对角10.对于含有n个结点的带权连通图，它 的 最 小 生 成 树 是 指 图 中 任 意 一 个。A）有 n-1条权值最小的边构成的子图B）有 n-1条权值之和最小的边构成的子图0有 n-1条权值最小的边构成的连通子图D）有 一 n个顶点构成的边的权值之和最小的连通子图11.有 n 个结点的线索二叉树上含有的线索数为一A）2n B）n-1 C）n+1 D）n1
28、2.若个有向图中的顶点不能排成一个拓扑序列，则 可 断 定 该 有 向 图。A）是个有根有向图 B）含有多个入度为0的顶点O 是个强连通图 D）含有顶点数目大于1 的强连通分量13.关键路径是指A 0 E 网络中A）从源点到汇点的最长路径 B）从源点到汇点的最短路径C）最长的回路 D）最短的回路14 .对 有 18 个元素的有序表R 0 至 R 17,则二分查找R 2的比较序列的下标为.A）0、1、2 B）8、4、1、2 C）8、4、2 D）8、3、1、215.有 k个相同的数据，若用线性探测法把这k个数据存入哈希表，至少要进行 次探查A）k-1 B）k C）k+1 D）k（k+l）/2第8页
29、 共3页16 .在一棵二叉排序树上查找值为35的数据，以下比较的数据序列正确的为A）28、36、18、4 6、35 B）18、36、28、4 6、35C）4 6、28、18、36、35 D）4 6、36、18、28、3517 .快速排序在 情况下最不利于发挥其长处A）要排序的数据量太大 B）要排序的数据中含有多个相同的值。要排序的数据已基本有序 D）要排序的数据个数是奇数18 .稀 疏 矩 阵 采 用 压 缩 存储的目的主要是为了A）表达变得简单 B）对矩阵元素的存取变得简单0 去掉矩阵中的多余元素 D）减少不必要的存储空间的开销19 .哈希函数构造的原则是：它的函数值应 概率的取其值域的每一
30、个值。A）最大 B）最小 C）同等 D）平均20 .树的遍历策略可分为先序遍历和后序遍历（也有称为中序遍历的）；二叉树的基本遍历有三种，即先序、中序和后序。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论：“树的序遍历序列与其对应的二叉树的序遍历序列相同”是正确的A）先 先B）后（中）后 C）先 中D）先 后二、填 空 题（20 分，其余每空2 分）1.下面是对无向图的一种操作，其 中 g 是无向图的邻接矩阵，n是图的顶点数，顶点标号为1 到 n,v i 是一个全程变量的一维数组，初值为全0,下面的类C/C+算 法 t t 对图做什么操 作（1）。v o i d t r （g n,
31、v 0）/v 0 是图的顶点号，值范围为1 到 n 之间的整数（v i s i t（v O）;v i s i t 是一个函数，完成对给定图顶点的访问v i v 0-l=l;f o r（i=0;i n;i+）i f（!v i i&g v O-l i）t r（g,i）;v o i d t t（g n,n）（f o r（i=0;i n;i+）v i i=0;f o r（i=0;i n;i+）i f（!v i i ）t r（g,i+1）;2 .求最短路径的D i j k s t r a 算法若用邻接矩阵表示图，在 有 1 0 0 个顶点时如果时间是t,则在4 0 0个顶点时，时 间 去 约 是（2）。
32、3 .已知一棵完全二叉树共有8 9 2 个结点，则该二叉树的高度是（3）,叶 子 数 是（4）,度为 1的 结 点 数 是（5）,最后一个非叶结点的序号是（6）。（注：二叉树结点按自然数顺序从1 开始从上到下，同一层从左到右编号）4 .原始数据为（3 4、9 0,3 0,5 0,2 3,1 1,1 0,1 0 0,4 6 ）按快速排序算法一趟划分后，数据的排列是（7）。5 .求 最 小 生 成 树 有（8）和（9）两个算法。6 .在一棵5阶上树中，高度是5（叶子层不算），则这棵B树至少有（1 0）个结点三、简 答 题（2 6 分）1.（6 分）按 1 3、2 4、3 7、9 0、5 3 的次序
33、，a）画出建立平衡二叉树的过程并注明平衡类型（3分）b）画出建立3阶 也 树（又称2-3 树）的 过 程（3分）2.（1 3 分）有一个A OE 网如下:（1）画出该A OE 网的邻接表示意图（3分）（2）求出所有事件的最早发生时间与最迟发生时间（4分）（3）列出所有关键活动（3分）（4）把上图看成无向图（忽略弧的方向），求出棵最小生成树，生成树边权之和为多少？（生成树不需要画出，3 分）3.（4分）有数据1 3、2 4、3 7、9 0、5 3,试 建 立 一 棵 H u f f m a n 树并计算W P L。（4分）4.（3分）简述分块查找的数据组织方式，查找过程。（3分）四、算法设计（用
34、类-C/类-C+描述）（1 4 分）1.（7 分）完成一个二叉树拷贝的递归算法t r e e c o p y（d,s）。其中s 是源二叉树，d 是目的二叉树。2.（7分）设在n个数据存在一维数组r中，试写一个算法将数据按原始顺序构造一个带有头结点的双向循环链表。函数名为：Co n v e r t （r,l a,n）,其 中 r为存有n个数据的一维数组，l a 为链表头指针。双向链表的三个域为：数据域d a t a,前向指针p r i o r,后向指针n e x t,数组下标从0计。第1 0页 共3页南 京 理 工 大 学 课 程 考 试 试 卷 (学生考试用)课程名称：数据结构 学分：3 大
35、纲 编 号 062204试卷编号：考试方式：闭卷 满分分值：100 考试时间：120 分钟组卷日期：2007年 6 月 4 日 组 卷 教 师(签 字)祢宏 审 定 人(签 字)3 相 检学生班级：计算机学院05级三、选 择 题(2*20=40分)1.对于链队，在进行删除操作时，A)仅修改头指针 B)仅 修 改 尾 指 针 C)头、尾指针都修改 D)头、尾指针都可能修改2.二维数组A中，每个元素的长度为3 个字节，行下标从0 到 9,列下标从0 到 1 1,则连续存放该数组至少需要一字节A)100 B)240 0 360 D)3403.一棵有124个叶子的完全二叉树，最多有 个结点A)247
36、B)248 C)249 D)2504.利用3,6,8,12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权利路径长度为一B)55 B)29 C)58 D)395.一个堆是一棵 二叉树A)普通 B)排序 C)满D)完全6.在一个有向图的邻接表中，每个顶点链表中结点的个数等于该定点的A)入度 B)出 度。度 D)度数减17.下 面 程 序 段 的 时 间 复 杂 度 是。for(i=l;im;i+)for(j=0;j n e x ta rc）if（!vi p-a d jve x-l ）tr（a d j,p-a d jve x）;vo id tri(a d j,n)(f o r(i=0;i n
37、;i+)visite d i=0;f o r(i=0;i n;i+)if(!visite d i)tr(a d j,i+1);)2.假 定对数据序列（7,3,5,9,1,1 2,8,1 5）进行快速排序，则进行第一次划分后,在7的左边数据 依 次 是（2）,7的右边数据依次是（3）。-0 1 03 .从邻接矩阵A=1 0 1可以看出，该 图 有（4）个顶点。如果是有向图，该图有（5）0 1 0条弧，若是无向图，该 图 有（6）条边。m4 .有向图如图-1 所示：写出一个拓扑序列（7）,添加孤（8）后,则仅可能/有唯一的拓扑序列。5 .由一棵二叉树的先序序列和（9）可唯一的确定这棵二叉树。（3、
38、（2 ）6 .已知完全二叉树的第8 层有8个 结 点（根为第1 层），则叶子数 V/为（1 0）。/7 .D i ik stra 算法可以求从指定源点到其它各顶点的（1 1）路径,/路 径 长 度 按（1 2）序产生，若采用邻接矩阵存储有向图，对于有 厂 Xn 个顶点的图而言，算法的时间复杂度是（1 3）。,三、简 答 题（2 0 分）a）简单叙述哈希查找的思想，链地址法是如何解决冲突的？（2+3 分）图Tb）引入平衡二叉树的目的是什么？在图-2 中的平衡二叉树中加入7 0 后需要做什么类型的平衡，画出平衡后的二叉树。（2+2+2 分）第1 2页 共3页（1）求出所有事件的最早发生时间与最迟发
39、生时间（3 分）（2）列出所有关键活动（3分）（3）画出该A O E 网的逆邻接表（3分）四、算法设计（用类-C/类-C+描述）（1 4 分）L（7 分）完成一-个在根为tre e 的二叉排序树中插入数据x的算法i nse rt（tre e,x）。（二叉排序树结点的三个域为：左、右孩子I ch i l d与 rch i l d,数据域dada）2.（7分）有 n 个结点的有向图（图的顶点号为1 至 n）用邻接表表示，试完成从图中删去弧 u,v 的算法D e l A rc（adj,u,v）。（注：（1）为简便，假定弧 u,v 是存在的（2）adj 为邻接表表头数组，数组下标从0计（3）结点的数据
40、域名称可自己命名）南 京 理 工 大 学 课 程 考 试 试 卷 (学生考试用)课程名称：数据结构 学分：3 大 纲 编 号 0 62 2 0 4试卷编号：考试方式：闭卷 满分分值：1 0 0 考试时间：1 2 0 分钟组卷日期：2 0 0 8 年 4月 2 8 日 组 卷教师(签字)秘宏 审 定 人(签 字)上树梅学生班级：计算机学院0 6级四、选 择 题(2*2 0=4 0 分)1、以下不属于算法特性的是A)可行性 B)有输入 C)确定性 D)健壮性2、下面关于算法的说法正确的是A)算法最终必须由计算机程序实现B)算法的有穷性是对于任意的一组输入值必须在有穷步骤后结束0算法的可行性是指指令
41、不能有二义性D)以上几个都是错误的3、线性表采用链表存储时，其地址A)必须是连续的 B)一定是不连续的 C)部分地址必须是连续的 D)连续与否均可以4、一个栈的进栈序列是a,b,c,d,e,则栈的不可能输出序列是C)e dcba B)de cba C)dce ab D)abcde5、对于链队，在进行删除操作时，oA)仅修改头指针 B)仅修改尾指针C)头、尾指针都要修改 D)头、尾指针可能都要修改6、设 二 维 数 组 A m n ,每 个 数 组 元 素 占 用 k 个字节，第一个数组元素的存储地址是L o c(a0 0),求按行优先顺序存放的数组元素ai j (O W i W n r l,O
42、 W j W n-1)的存储地址为A)L o c(a0 O )+(i-l)*n-l)*k B)L o c(a0 O )+(i*n+j)*kC)L o c(a0 O )+(j*m+i)*k D)L o c(a0 O )+(j-l)*m+i-l)*k7、如果二叉树T 2是由树T 1 转换而来的二叉树，那么T 1 中结点的先序就是T 2 中 结 点 的。A)先序 B)中序 C)后序 D)无对应关系8、一个具有1 025个结点的二叉树的高h为A)1 1 B)1 0 C)H 到 1 025 D)1 2 到 1 0249、一棵二叉树的后序遍历序列为E F H I G J K,中序遍历序列为HFIEJKG,
43、则该二叉树根结点 的 右 孩 子 为。A)E B)F C)G D)H1 0、n 个 结 点 的 线 索 二 叉 树 上 含 有 的 线 索 数 为。G)2n B)n-1 C)n+1 D)nIE堆是一A)完全二叉树 B)线性表 C)二叉排序树 D)平衡二叉树1 2、假定在一棵二叉树中，度 为 2 的结点数为1 5,度 为 1 的结点数为30,则叶子结点数为 oA)1 5 B)1 6 C)1 7 D)1 81 3、由带权为9、2、5、7 的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为A)23 B)37 C)46 D)441 4、下面的叙述中，不正确的是A)关键活动不按期完成就会影响整个工程完
44、成时间B)任何一个关键活动提前完成，将使整个工程提前完成0所有关键活动提前完成，则整个工程提前完成D)某些关键活动若提前完成，将可能使整个工程提前完成1 5、设哈希表长为1 4,哈希函数为h(k ey)=k ey%l l。表中现有数据1 5、38、61 和 8 4,其余位置为空，如果用二次探测再散列处理冲突，则 49 的位置是A)8 B)3 C)5 D)9第 1 4页 共 3 页1 6、在一棵二叉排序树上查找值为35的数据，以下比较的数据序列正确的为A）28、36、1 8、46、35 B）1 8、36、28、46、35C）46、28、1 8、36、35 D）46、36、1 8、28、351 7
45、、下面排序算法中，算法可能会出现下面情况：初始数据有序时，花费的时间反而最多A）堆排序 B）冒泡排序 C）快速排序 D）希 尔（Sh el l）排序1 8、任何一棵二叉树的叶子结点在先序、中 序 和 后 序 遍 历 中 的 相 对 次 序。0不发生改变 B）发生改变 0不能确定 D）以上都不对1 9、如果从无向图的任一顶点出发进行一次图遍历即可访问所有顶点，则 该 图 一 定 是。A）完全图 B）连通图 C）有回路 D）一棵树20、对 有 1 8个元素的有序表r 0.1 7,进行二分查找，则查找r 3 的比较序列下标为A）0、1、2 B）8、4、1、2 0 8、4、2 D）8、3、1、2五、填
46、 空 题（24分，每空3 分）a）下面程序段的时间复杂度为（1）os=0;fo r（i=l;i n;i+）fo r（j=l;j i;j+）s+=i*j；2、已知完全二叉树T的第5 层只有7个结点，则该树共有（2）个叶子结点3、始数据为（3 5、9 7,3 0,5 0,2 3,1 1,1 0 1,1 0 0,4 6 ）按快速排序算法一趟划分后，数据的排列是（3）。4、n 个顶点的连通图用邻接矩阵表示时，该矩阵至少有（4）非零元素。5、评价哈希函数好坏的标准是（5）。6、对于关键字序列：1 2、1 3、1 1、1 8、6 0、1 5、7、2 0、2 5、1 0 0,用筛选法建堆，必 须 从 值 为
47、（6）的关键字开始。7、D i jk s t r a 最短路径算法按9 J 衣次产生路径，在 边（弧）上 权 有（8）值时不能正确工作。三、简 答 题（2 5 分）1、（4 分）有 0（1）,0（l og 2n）,0（n）,0（n l og2n）,0（n2）,0（n3）,0（nk）,0（2）,试用W把它们从左向右连接起来。2、（9分）已知3 阶 B.树如图所示。（1）画出将关键字8 8 插入之后的B-树；（2）画出将关键字4 7和 6 6 依次插入之后的B-树。题 2 9 图3、（4分）简述哈希查找中链地址法解决冲突的方法。4、（8分）有一个A O E 网如下:（4）求出所有事件的最早发生时间
48、与最迟发生时间（4分）（5）列出所有关键活动（4分）四、算法设计（用类-C/类-C+描述）（1 1 分）1、（5 分）写一个递归的二分查找算法b in a s（d,x,1,h）o其中：d 为一维数组，x为待查数据，1、h 为查找的范围（l,h给出的是下标范围，下标从0 计算）2、（6分）在邻接表表示的无向图中加入一条 边（u,v）,完成算法：A ddE dge（a dj,u,v）其中：a dj为邻接表表头数组，u、v是顶点号，为方便，u、v假定是合法的，且邻接表中没有边（u,v）（顶点号从1 计，数组下标从0 计，图的顶点数为n）。第1 6页 共3页南 京 理 工 大 学 课 程 考 试 试
49、卷 (学生考试用)07年六、选 择 题(2*2 0=4 0 分)1、一个算法必须保证执行有限步之后结束，这是算法的性A)有穷 B)确定 C)可行 D)输出2、A算法的时间复杂度为0 (n 3),B 算法的时间复杂度为0 (2 n)，则说明E)对于任何数据量，A算法的时间开销都比B算法小F)随着问题规模n的增大，A算法比B算法有效G)随着问题规模n的增大，B算法比A算法有效H)对于任何数据量，B算法的时间开销都比A算法小3、对线性表，在 情况下应当采用链表表示A)经常需要随机地存取元素 B)经常需要进行插入和删除运算C)表中元素需要占据一片连续的存储空间 D)表中元素的个数不变4、对线性表进行二
50、分查找，其前提条件是D)顺序表 B)有序的顺序表 C)链表 D)有序的链表5、对于链队，在进行删除操作时，。A)仅修改头指针 B)仅修改尾指针C)头、尾指针都要修改 D)头、尾指针可能都要修改6、设 二 维 数 组 A m n ,每 个 数 组 元 素 占 用 k 个字节，第一个数组元素的存储地址是L o c(a 0 0 ),求按行优先顺序存放的数组元素a i j (0 W i m-l,0 W j W n-l)的存储地址为A)L o c(a 0 0 )+(i-l)*n-l)*k B)L o c(a 0 O )+(i*n+j)*kC)L o c(a 0 0 )+(j*m+i)*k D)L o c