数据结构作业.pdf
数据结构习题数据结构习题第一章第一章 绪论绪论1.6 在程序设计中，常用以下三种不同的出错处理方式：1)用 exit 语句终止执行并报告错误；2)以函数的返回值区别正确返回或错误返回；3)设置一个整形变量的函数参数以区别正确返回或某种错误返回。试讨论这三种方法各自的优缺点。1.7 在程序设计中，可采用以下三种方法实现输出和输入：1)通过 scanf 和 printf 语句；2)通过函数的参数显示传递；3)通过全局变量隐式传递。试讨论这三种方法的优缺点。1.8 设 n 为正整数。试确定以下各程序段中前置以记号的语句的频度：5)for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=(y+1)*(y+1)y+;答案：n向下取整8)x=91;y=100;while(y 0)if(x 100)x-=10;y-;else x+;答案：if 执行次数为 1100，if 判断内部执行为 100 次1.19 试编写算法，计算 i!2ii=0,1,n-1的值并分别存入数组 aarrsize的各个分量中。假设计算机中允许的整数最大值为MAXINT，那么当 n arrsize 或对某个 k 0 k n-1使 k!2k MAXINT 时，应按出错处理。注意选择你认为较好的出错处理方法。1.20 试编写算法求一元多项式Pn(x)a xii 0ni的值 Pn(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。此题的输入为 aii=0,1,n、x0和 n，输出为 Pn(x0)。第二章第二章 线性表线性表2.11 设顺序表 va 中的数据元素非递减有序。试写一算法，将 x 插入到顺序表的适当位置上，以保持该表的有序性。2.12 设 Aa1，am和 Bb1，bn均为顺序表，A和 B分别为 A 和 B 中除去最大共同前缀后的子表例如，Ax，y，y，z，x，z，Bx，y，y，z，y，x，x，z，那么两者中最大的共同前缀为x，y，y，z，在两表中除去最大共同前缀后的子表分别为 Ax，z和 By，x，x，z 。假设 AB空表，那么 AB；假设 A空表，而B空表，或者两者均不为空，且A的首元小于 B的首元，那么A B。试写一个比拟 A、B 大小的算法请注意：在算法中，不要破坏原表A 和B，并且也不一定先求得A和 B才进行比拟。2.19 线性表中的元素以值非递减有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有值大于 mink 且小于 maxk 的元素 假设表中存在这样的元素 同时释放被删节点空间，并分析你的算法的时间复杂度注意：mink 和 maxk 是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同。2.22 试写一算法，对单链表实现就地原地逆置。2.38 设有一双向循环链表，每个结点中除有 prior，data 和 next 三个域外，还增设了一个访问频度域 freq。在链表被起用之前，频度域freq 的置均初始化为零，而每当对链表进行一次 LOCATEL，x的操作后，被访问的结点即元素值等于x 的结点中的频度域 freq的值便增 1,同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的LOCATE 操作的算法。2.41 试以循环链表作稀疏多项式的存储结构，编写求其导函数的算法，要求利用原多项式中的结点空间存放其导函数多项式，同时释放所有无用被删的结点。第三章第三章 栈和队列栈和队列3.17 试写一算法，识别依次读入的一个以为结束符的字符序列是否为形如序列 1&序列2模式的字符序列。其中序列1 和序列 2 中都不包含字符&，且序列 2 是序列 1 的逆序列。例如a+b&b+a是属于该模式的字符序列，而1+3&3-1那么不是。3.21 假设表达式由单字母变量和双目四那么运算符构成。试写一算法，将一个通常书写形式且书写正确的表达式转换成逆波兰式。3.22 如题 3.21 的假设条件，试写一算法，对以逆波兰式表示的表达式求值。3.30 假设将循环队列定义为：以域变量rear 和 length 分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法在出队列的算法中要返回对头元素。3.31 假设称正读和反读都相同的字符序列为“回文，例如，abba和abcba是回文，abcde和ababab那么不是回文。试写一算法判别读入的一个以 为结束符的字符序列是否是回文。3.32 试利用循环队列编写求k 阶斐波那契序列中前n+1 项f0,f1,，fn的算法，要求满足：fnmax 而 fn+1max，其中 max 为某个约定的常数。注意：此题所用循环队列的容量仅为 k，那么在算法执行结束时，留在循环队列中的元素应是所求k 阶斐波那契序列中的最后k 项 fn-k+1,，fn。第四章第四章 串串4.17 编写算法，实现串的根本操作Replace(&S,T,V)。4.23 假设以块链结构作串的存储结构。试编写判别给定串是否具有对称性的算法，并要求算法的时间复杂度为 O(StrLength(S)。4.28 假设以结点大小为 1带头结点的链表结构表示串，那么在利用next 函数值进行串匹配时，在每个结点中需设三个域：数据域 chdata、指针域 succ 和指针域 next。其中 chdata域存放一个字符；succ 域存放指向同一链表中后继结点的指针；next 域在主串中存放指向同一链表中前驱结点的指针，但在模式串中存放指向当该结点的字符与主串中的字符不等时，模式串中下一个应进行比拟的字符结点即与该结点字符的next 函数值相对应的字符结点的指针，假设该结点字符的 next 函数值为零，那么其next 域的值应指向头结点。试按上述定义的结构改写求模式串的next 函数值的算法。注：根据同学们的要求，将作业量从六道题减少到三道题，希望同学们能及时完成。第五章第五章 数组和广义表数组和广义表5.21 假设稀疏矩阵 A 和 B 均以三元组顺序表作为存储结构。试写出矩阵相加的算法，另设三元组 C 存放结果矩阵。5.26 试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。5.33 试编写递归算法，输出广义表中所有原子项及其所在的层次。第六章第六章 树和二叉树树和二叉树6.45 编写递归算法：对于二叉树中每一个元素值为x 的结点，删去以它为根的子树，并释放相应的空间。6.46 编写复制一棵二叉树的非递归算法。6.59 编写算法完成以下操作：无重复地输出以孩子兄弟链表存储的树T 中所有的边这里的边是指树 T 本身的分支，而不是孩子兄弟链表所形成的二叉树的分支。输出的形式为 k1,k2,.,(ki,kj),.,其中，ki 和 kj 为树结点中的结点标识。第七章第七章 图图7.22 试基于图的深度优先搜索策略编写一算法，判别以邻接表方式存储的有向图中是否存在从顶点 vi到顶点 vj的路径(ij)。注意：算法中涉及的图的根本操作必须在此存储结构上实现。7.24 利用栈的根本操作编写，按深度优先搜索策略遍历一个强连通图的非递归算法。算法中不规定具体的存储结构，而将图Graph 看成是一个抽象的数据类型。7.31 试完成求有向图的强连通分量的算法，并分析算法的时间复杂度。7.42 以邻接表作为存储结构实现求从源点到其余各顶点的最短路径的Dijkstra 算法。第八章第八章 动态存储管理动态存储管理10的块的伙伴的二进制地址是什么？假设块大小为(16)10时又如何？第九章第九章 查找查找9.11 试推导含 12 个结点的平衡二叉树的最大深度，并画出一棵这样的树。9.25 假设顺序表关键字自大而小有序，修改教科书 9.1.1 节中的顺序查找算法，将哨兵设在高低标端。然后画出此查找过程的判定树，分别求出等概率情况下查找成功和不成功时的平均查找长度。9.45 假设哈希表长为 m，哈希函数为H(x)，用链地址法处理冲突。试编写输入一组关键字并建造哈希表的算法。第十章 排序10.23 试以 L.rk+1作为监视哨改写直接插入排序算法。其中，L.r1.k为待排记录且kMAXSIZE。10.32 荷兰国旗问题：设有一个仅由红、白、蓝三种颜色的条块组成的条块序列。请编写一个时间复杂度为 O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。第十二章 文件12.10 假设某个有 3000 张床位的旅店需建立一个便于管理的文件,每个记录是一个旅客的身份和投宿情况。其中旅客身份证号(15 位十进制数字)可作为主关键字，此外还需建立按姓名、投宿日期、从哪来等次关键字项索引。请为此文件确定一种组织方式(如:主文件如何组织,各次关键字项索引如何建立等
