数据结构作业(更新到排序).doc

数据结构作业数据结构作业第一章绪论1.1 有下列几种用二元组表示的数据结构，画出它们分别对应的图形表示，并指出它们分别 属于何种结构 （1）A = (K,R)，其中： K = {a,b,c,d,e,f,g,h} R = {r} r = {,,,,,,} （2）B = (K,R),其中： K = {a,b,c,d,e,f,g,h} R = {r} r = {,,,,,,} （3）C = (K,R),其中： K = {1,2,3,4,5,6} R = {r} r = {(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)} 这里的圆括号对表示两结点是双向的 （4）D = (K,R),其中： K = {48,25,64,57,82,36,75} R = {r1,r2} r1 = {,,,,,} r2 = {,,,,,} 1.2 指出下列各算法的功能并求出其时间复杂度1）int Prime(int n) { int i = 2;int x=(int)sqrt(n);while(ix) return 1;else return 0; }（2）int sum1(int n) {int p=1,s=0; for(int i=1; i2，试求下列算法的时间复杂度及变量 count 的值（以 n 的函数形式表示） 。

int Time(int n){count=0; x=2;while(xa.length) return INFEASIBLE; //参数不合法else {for( count=1;count=i+1; j--) a.elem[j-1]=a.elem[j];a.length--;} } Return OK; } 2.2 设顺序表 va 中的数据元素递增有序试写一算法，将 x 插入到顺序表的适当位置上， 以保持该表的有序性 2.3 试写一算法在带头结点的单链表结构上实现线性表操作 Length（L） 2.4 已知线性表中的元素以值递增有序排列，并以单链表作存储结构试写一个高效的算 法，删除表中所有值大于 mink 且小于 maxk 的元素（若表中存在这样的元素）同时释放被 删结点空间，并分析你的算法的时间复杂度（注意：mink 和 maxk 是给定的两个参变量， 它们的值可以和表中的元素相同，也可以不同） 2.5 假设有两个按元素值递增有序排列的线性表 A 和 B，均以单链表作存储结构，请编写 算法将Ａ表和Ｂ表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的 元素）排列的线性表Ｃ，并要求利用原表（即Ａ表或Ｂ表）的结点空间构造Ｃ表。

第三章栈和队列3.1 若按照教科书 3.1.1 节中图 3.1（b）所示铁道进行车厢调度（注意：两侧铁道均为单向 行驶道） ，则请回答： （1）如果进站的车厢序列为 123，则可能得到的出站车厢序列是什么？ （2）如果进站的车厢序列为 123456，则能否得到 435612 和 135426 的车站序列，并请说 明为什么不能得到或者如何得到（即写出以‘S’表示进栈和以‘X’表示出栈的栈操作序 列） 3.2 如果希望循环队列中的元素都能得到利用，则需要设置一个标志域 tag，并以 tag 的值 为 0 或 1 来区别尾指针和头指针相同时的队列的状态是“空”还是“满” 试编写与此结构 相应得入队列和出队列的算法 提示：标志位 tag 的初值置“0” 一旦元素入队列使 rear==front 时，需置 tag 为“1” ；反 之，一旦元素出队列使 rear==front 时，需置 tag 为“0” ，以便使下一次进行入队列或出队 列操作时（此时 rear==front） ，可由标志位 tag 的值来区别队列当时的状态时“空”还是 “满” 第五章 数组与广义表5.1 设矩阵 A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图）按行存放在一 维数组 B[1，n(n-1)/2]中，对下三角部分中任一元素 ai,j(i≥j)，在一维数组 B 中下标 k 的值 为多少？给出计算过程。

12212212Annnna aaaaa   L L5.2 设稀疏矩阵如下图所示： 300060 0000160 2500000A0066000 0000088 000000        要求给出该稀疏矩阵的三元组顺序表表示法的图示第六章 树和二叉树6.1 三个结点的树和二叉树的基本形态有何区别？ 6.2 已知一棵树的边的集合表示为：{(L,N),(G,K),(G,L),(G,M),(B,E),(B,F),(D,G),(D,H),(D,I), (D,J),(A,B),(A,C),(A,D)}请画出这棵树，并回答以下问题： （1）树的根结点是哪个？哪些是叶子结点？哪些是分支结点？ （2）树的度是多少？各个结点的度是多少？ （3）树的深度是多少？各个结点的层数是多少？ （4）对于 G 结点，它的双亲结点、祖先结点、子女结点、子孙结点、兄弟和堂兄弟分别 是哪些？ 6.3 已知完全二叉树的第 7 层有 10 个叶子结点，则整个二叉树的结点数最多是多少？给出 计算过程 6.4 设某二叉树的前序遍历序列为：ABCDEFGIH，中序遍历序列为：BCAEDGHFI。

（1）试画出该二叉树 （2）画出该二叉树的中序线索树 6.5 假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成它们在电文中出现的频率分 别为{0.31, 0.16, 0.1, 0.08, 0.11, 0.2, 0.04} （1）为这 7 个字母设计赫夫曼编码画出赫夫曼树 （2）为这 7 个字母进行等长编码，至少需要几位二进制数？赫夫曼编码比等长编码使电文 总长压缩多少？第七章第七章 图图7.1 从占用的存储空间来看，对于稠密图和稀疏图，采用邻接矩阵和邻接表哪个更好些？ 7.2 给出图 7.1 所示的无向图 G1 的邻接矩阵和邻接表两种存储结构并在给定的邻接表基 础上，指出从顶点 1 出发的深度优先遍历和广度优先遍历序列12435图 7.1 无向图 G123456图 7.2 无向图 G2651 5352 6647.3 使用普利姆算法和克鲁斯卡尔算法构造如图 7.2 所示的图 G2 的一棵最小生成树 7.4 如图 7.3 所示的 AOE 网，求：123457689105a16a23a36a43a534a71a84a95a104a122a132a11a6图 7.3 一个 AOE 网（1）每项活动 ai 的最早开始时间 e(ai)和最迟开始时间 l(ai)。

（2）完成此工程最少需要多少天（设弧上权值为天数）？ （3）哪些是关键活动？ （4）是否存在某项活动，当其提高速度后能使整个工程缩短工期？第第 9 章章 查找查找9.1 画出对长度为 10 的有序表进行折半查找的一棵判定树，并求其等概率时查找成功的平 均查找长度 9.2 设数据集合 d={1,12,5,8,3,10,7,13,9},试完成下列各题：（1）依次取 d 中各数据，构造一棵二叉排序树 bt;（2）如何依据此二叉树 bt 得到 d 的一个有序序列；（3）画出在二叉树 bt 中删除“12”后的树结构4）对原二叉排序树，求成功和不成功时的平均查找长度 9.3 设有一组关键字{19,1,23,14,55,20,84,27,68,11,10,77}，采用散列函数：H（key）= key % 131采用开放地址法的线性探测再散列方法解决冲突，试在 0~18 的散列地址空间中对该关 键字序列构造散列表 第第 10 章章10.1 设待排序的记录共 7 个，排序码分别是 8,3,2,5,9,1,6，要求按递减顺序排序1）用直接插入排序试以排序码序列的变化描述形式说明排序全过程（动态过程） 2）用直接选择排序。

试以排序码序列的变化描述形式说明排序全过程（动态过程） 3）直接插入排序算法和直接选择排序算法的稳定性如何？ 10.2 请简单叙述希尔排序的基本思想设有一组关键字序列为{98,36，-9,0,47,23,1,8,10,7} 进行希尔排序，给出的步长（也称增量序列）依次是 4,2,1，则排序需多少趟？写出第一趟 结束后，关键字的排列次序 10.3 请回答下列关于堆的问题：（1）堆的存储表示是顺序的，还是链式的？（2）设有一个小顶堆，其最大值元素可能在什么位置？ 10.4 已知待排序的序列为（503,87,512,61,908,170,897,275,653,462） ，试完成下列各题：（1）根据以上序列建立一个堆（画出第一步和最后堆的结果图） ，希望先输出最小值2）输出最小值后，如何得到次小值？画出相应的结果图。