数据结构习题集.doc

数据结构习题集第一章 绪论16 试写一算法，自大至小依次输出顺序读入的三个整数x，y和z的值。 17 已知k阶裴波那契序列的定义为f0=0， f1=0， ， fk-2=0，fk-1=1；fn=fn-1 + fn-2 + + fn-k， n=k，k+1， 试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。 18 假设有a，b，c，d，e五个高等院校进行田径对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。项目名称性 别校 名成 绩得 分 19 试编写算法，计算i！2i的值并存入数组a 0.arrsize-1的第i-1个分量中（i=1，2，n）。假设计算机中允许的最大值为maxint，则当narrsize或对某个k（1kn）使k！2kmaxint时，应按出错处理。注意选择你认为较好的出错处理方法。20 试编写算法求一元多项式的值pn（x）=aixi的值pn（x0），并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为ai（i=0，1，n），x0和n，输出为pn（x0）。第二章 线性表 本章算法设计题涉及的顺序表和线性链表的类型定义如下：#define list_init_size 100#define listincrement 10typedef structelemttpe *elem; / 存储空间地址int length; /当前长度int listsize; /当前分配的存储容sqlist; /顺序表类型typedef struct lnodeelemtype data;struct lnode *next；lnode,*linklist; /线性链表类型2.10 指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。status deletek(sqlist&a,int i,int k) /本过程从顺序结构的线性表a中删除第i个元素起的k个元素if (i1ka .length)return infeasible; /参数不合法else for(count=1;count=i+1;j-) a.elemj-1=a.elemj;a. length-;return ok;/deletek 2。11 设顺序表va中的数据元素递增有序.试写一算法，将x插入到顺序表的 适当位置上，以保持该表的有序性。 2。12 设a=（a1,am）和b=（b1,bn）均为顺序表,a/和b/分别为a和b中除去最大共同前缀后的子表（例如，a=（x，y，y，z，x，z），b=（x，y，y，z，y，x，x，z），则两者中最大的共同前缀为（x，y，y，z），在两表中除去最大共同前缀后的子表分别为a/=（x，z）和b/=（y，x，x，z）。若a/=b/=空表，则a =b；若a/=空表，而b/空表，或者两者均不为空表，且a/的首元小于b/的首元，则a b；否则a b。试写一个比较a，b大小的算法（请注意：在算法中，不要破坏表a和b，并且，也不一定先求得a/和b才进行比较）。 2。13 试写一算法在带头结点得单链表结构上实现线性表操作locate(l,x). 2。14 试写一算法在带头结点得单链表结构上实现线性表操作length(l). 2。15 已知指针ha和hb分别指向两个单链表得有结点，并且已知两个链表得长度分别为m和n。试写一算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。 2。16 已知指针la和lb分别指向两个无头接点单链表中的首元接点，下列算法是从表la中删除自第i个偶，将元素起共len个元素后，将它们插入到表lb中第i个元素之前。试问此算法是否真确？若有错，则请改正之。staus deleteandinsertsub (linkedlist la, linkedlist lb,int i,int j,int len)if(i0j0len0) return infeasible;p=la;k=l;while(knext;k+;q=p;while (knext;k+;s=lb;k=1;while(knext;k+;s-next=p; q-next=s-next;return ok;/deleteandinsertsub217 试写一算法，在无头结点的动态单链表上实现线性表操作insert(l，i，b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。218 同2.17题要求。试写一算法，实现线性表操作delete(l，i)。219 已知线性表中的元素以递增有序排列，并以单链表作存储结构。试写以高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。 220 同2.19题条件，试写一高效的算法，删除表中相同的多值元素（使得操作后得线性表中得所有元素得值均不相同），同时释放被删结点空间，并分析你得算法得时间复杂度。2.21试写一算法，实现顺序表的就地拟置，即利用原表的存储空间将线性表（a1,a2,an）逆置为（an,an-1,a1）.2.22 试写一算法，对单链表实现就地逆置。2.23 设线性表a=（a1,a2,am）,b=(b1,b2,bn),试写一个按下列规则合并a,b为线性表c的算法，即使得 c=（a1,b1,am,bm,bm+1,，bn） 当mn时 ;或者 c=（a1,b1,an,bn,an+1,，bm） 当mn时.线性表a,b和c均以单链表作存储结构，且c表利用表a和表b中的结点空间构成，注意：单链表的长度值m和n均未显示存储。2.24 假设有两个按元素值递增有序排列的线性表a和b，均以单链表作存储结构，请编写算法将a表和b表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表c，并要求利用原表（即a表和b表）的结点空间构造c表.2.25 假设以两个元素依值递增有序排列的线性表a和b分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表c,其元素为a和b中元素的交集，且c中的元素也依值递增有序排列，试对顺序表编写求c的算法。2.26 要求同2.25题，是对单链表编写求c的算法。2.27 对2.25题的条件作以下两点修改，对顺序表重新编写求得表c的算法。 假设在同一表（a或b）中可能存在值相同的元素，但要求新生成的表c中的元素值各不相同; 利用表a的空间存放表c.2.28 对2.25题的条件作以下两点修改, 对顺序表重新编写求得表c的算法.假设在同一表（a或b）中可能存在值相同的元素，但要求新生成的表c中的元素值各不相同; 利用原表(a表或b表)中的结点构造c,并释放a表中的无用结点。2.29 已知a,b和c为三个递增有序的线性表，现要求对a表作如下操作：删去那些既在b表中出现又在c表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。2.30 要求同2.29题，试写对单链表的编写算法，请释放a表中的无用结点。2.31 假设某个单向链表的长度大于1，且表中既无结点也无头指针。已知s为指向链表中的某个节点的指针，试编写算法在链表中删除指针s所指接点的前驱结点。2.32 已知有一个单项循环链表，其每个结点中含三个域：pre,data,和next,其中data为数据域，next为指向后继结点的指针域，pre业为指针域，但它的值为空（null）.是编写算法将此单项循环链表改为双向循环链表，即使pre成为指向前驱结点的指针域。2.33 已知有一个线性链表表示的线性表中含有三类字符的数据元素，（如字母字符，数据字符和其他字符），试编写算法将该线性表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。 在2.34至2.36题中，“异或指针双向链表”类型xorlinkedlist和指针异或函数xorp定义为： typedef struct xornode char data ; struct nornode lrptr； xornode,*xorpointer; typedef struct /无头结点的异或指针双向链表 xorpointer left, right; /分别指向链表的左端和右端 xorlinkedlist； xorpointer xorp(xorpointer p, xorpointer q); /指针异或函数xorp返回指针p和q的异或（xor）值2.34 假设在算法描述语言中引入指针的二元运算“异或”（用“”表示），若a和b为指针，则ab的运算结果仍为原指针类型，且 a(ab)=(aa)b=b (ab)b=a(bb)=a 则可利用一个指针域来实现双向链表l。链表中的每个结点只含两个域：data域和lrptr域，其中lrptr域存放该结点的左邻和右邻的结点指针(不存放在null)的异或。若设指针l.left指向链表中的最左结点，l.right指向链表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法，按任一方向依次输出链表中的各元素值。2.35 采用2.34题所述的存储结构，写出在第i个结点的算法。2.36 采用2.34题所述的存储结构，写出删除第i个结点的算法。2.37 设一带结点的双向循环链表表示的线性表l=(a1,a2,an).试写一个时间复杂度为o（n）的算法，将l改造为（a1,a3,an,a4,a2）。2.38 设有一个双向循环列表，每个结点中除了有pre,data,next三个域外，还增设了一个访问频度freq。在链表被启用之前，频度域freq的值均初始化为零，而每当用链表进行一次locate(l,x)的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增一，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合以上要求的locate操作算法。 在2.39至2.40题中，稀疏多项式采用的顺序存储结构sqpoly定义为 typedef struct int coef; int exp polyterm; typedef struct polyterm *data; int last; sqpoly;2.39 已知多项式pn(x)=c1xe1+c2xe2+cmxem,其中n=emem-1e10,ci0(i=1,2,m),m1.试采用存储量同多项式项数m成正比的顺序存储结构，编写求pn(x0)的算法（x0为给定值），并分析你的算法的时间复杂度。2.40 采用2.39题给定的条件和存储结构，编写求p(x)=pn1(x)-pn2(x)的算法，将结果多项式存放在新辟的空间中，并分析你的算法的时间复杂度。 在2.41至2.42题中，稀疏多项式采用的循环链表存储结构linkedpoly定义为 typedef struct polynode polyterm data; struct polynode *next; polynode,* polylink;typedef polylink linkedpoly;2.41 试以循环链表作稀疏多项式的存储结构，编写求其导函数的算法 ，要求利用原多项式中的结点空间存放其导函数(多项式)，同时释放所有的无用（被删）结点。2.42 试编写算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间构成这两个链表。第三章 栈和队列3.15 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别为设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或者1，用以分别指示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设为参变）或函数设计这些操作算法各有什么优缺点。3.16 假设如题3.1所述火车调度站的入口处有n节硬席或软席车厢（分别以h和s表示）等待调度，试编写算法，输出对这n节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都被调整到硬席车厢之前。3.17 试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形如序列1&序列2模式的字符序列。其中序列1和序列2中都不含字符&，且序列2是序列1的逆序列。例如，a+b&b+a是属该模式的字符序列，而13&3-1则不是。3.18 试写一个判别表达式中开、闭括号是否配对出现的算法。3.19 假设一个算术表达式中可以包含三种括号：圆括号“（”和“）”、方括号“”和“”和花括号“”和“”，且这三种括号可按任意的次序嵌套使用（如：()）。编写判别给定表达式中所含括号是否正确配对出现的算法（已知表达式已存入数据元素为字符的顺序表中）。3.20 假设以二维数组g(1.m,1.n)表示一个图像区域，gi,j表示该区域中点（i,j）所具颜色，其值为从0到k的整数。试编写算法置换点(i0,j0)所在区域的颜色。约定和(i0,j0)同色的上下左右的邻结点为同色区域的点。3.21假设表达式为单字母变量和双目四则运算符构成。试写一算法，降一个通常书写形式且书写正确地表达式转换为逆波兰式。3.22如题3.21的假设条件，试写一算法，对以逆波兰式表示的表达式求值。3.23如题3.21的假设条件，试写一算法，判断给定的非空后缀表达式是否为正确的逆波兰式（即后缀表达式）。如果是，则将它转化为波兰式（即前缀表达式）。3.24 试编写如下定义的 递归算法，并根据算法画出求g(5,2)时栈的变化过程。 3.25 试写出求递归函数 f（n）的递归算法，并消除递归：3.26 求解平方根 a的迭代函数定义如下：其中，p是a的近似平方根，e是结果允许误差。试写出相应的递归算法，并消除递归。3.27 以知aackerman函数的定义如下：（1） 写出递归算法；（2） 写出非递归算法；（3） 根据非递归算法，画出求akm（2，1）时栈的变化过程。3.28 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。3.29 如果希望循环队列的元素都能得到利用，则需设置一个标域tag，并以tag的值为0或1来区分，尾指针和头指针相同时的队列状态是“空”的还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。330 假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。331 假设称正读和反读都相同的字符序列为“回文”，例如，abba和abcba是回文，abcde和ababab则不是回文。试写一个算法判别读入的一个以为结束符的字符序列是否是“回文”。332 试利用循环队列编写求k阶斐波那契序列中前n+1项（f0,f1,fn）的算法，要求满足：fnmax而fn+1max，其中max为某个约定的常数。（注意：本题所用循环队列的容量仅为k，则在算法结束时，留在循环队列中的元素应是所求k阶斐波那契序列中的最后k项fn-k+1,fn）。 333 在顺序存储结构上实现输出受限的双端循环队列的入列和出列（只允许队头出列）算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。 334 假设在如教科书341节中图39所示的铁道转轨图的输入端有n节车厢：硬座、硬卧和软卧（分别以 p,h和s表示）等待调度，要求这三种车厢在输出端铁道上的排列次序为：硬座在前，软卧在中，硬卧在后。试利用输出受限的双端队列对这n节车厢进行调度，编写算法输出调度的操作序列：分别以字符e 和d表示对双端队列的头端进行入队列和出队列是操作；以字符a表示对双端队列的尾端进行入队列的操作。 第四章 串在编写410至414题的算法时，请采用stringtype数据类型：stringtype 是串的一个抽象数据类型，它包含以下五种基本操作：void strassign(stringtype&t, stringtype s)/将s的值赋给t。s的实际参量可以是串变量或者串常量（如：abcd）。int strcompare(stringtype s,stringtype t)/比较s 和t。若st，返回值0；若s=t ，返回值=0；若st，返回值lsti，则第i个顶点无后继顶点。试编写判别该有向图中是否存在回路的算法。7.26 试证明，对有向图中顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全零的充要条件是：该有想图不含回路。然后写一算法对无环有向图的顶点重新编号，使其邻接矩阵变为下三角形，并输出新旧编号对照表。 7.27 采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。7.29 试写一个算法，在以邻接矩阵方式存储的有向图g中求顶点i到顶点j的不含回路的、长度为k的路径数。7.30 试写一个求有向图g中所有简单回路的算法。7.31 试完成求有向图的强连通分量的算法，并分析算法的时间复杂度。7.32 试修改普里姆算法，使之能在邻接表存储结构上实现求图的最小生成森林，并分析其时间复杂度（森林的存储结构为孩子-兄弟链表）。 7.33 已知无向图的边集存放在某个类型为edgesettype的数据结构edgeset中（没有端点相重的环边），并在此结构上已定义两种基本运算： 函数getminedge(edgeset,u,v):若edgeset非空，则必存在最小边，变参u和v分别含最小边上两顶点，并返回true；否则返回false； 过程delminedge(edgeset,u,v)：从edgeset中删除依附于顶点u和v的最小边。试在上述结构上实现求最小生成树（以孩子-兄弟链表表示）的克鲁斯卡尔算法。7.34 试编写一个算法，给有向无环图g中每个顶点赋以一个整数序号，并满足以下条件：若从顶点i至顶点j有一条弧。则应ij。7.35 若在dag图中存在一个顶点r，在r 和图中所有其他顶点之间均存在由r出发的有向路径，则称该dag图有根。试编写求dag图的根的算法。 7.36 在图的邻接表存储结构中，为每个顶点增加一个mpl域。试写一算法，求有向无环图g的每个顶点出发的最长路径的长度，并存入其mpl域。请给出算法的时间复杂度。7.37 试设计一个求有向无环图中最长路径的算法，并估计其时间复杂度。 7.38 一个四则运算算术表达式以有向无环图的邻接表方式存储，每个操作数原子都由单个字母表示。写一个算法输出其逆波兰表达式。7.39 把存储结构改为二叉链表，重做7.38题。7.40 若7.38题的运算符和操作数原子分别由字符和整数表示，请设计邻接表结点类型，并且写一个表达式求值的算法。7.41 试编写利用深度优先遍历有向图实现求关键路径的算法。 7.42 以邻接表作存储结构实现求从源点到其余各顶点的最短路径的dijkstra算法。 第九章 查找 9.25 假设顺序表按关键字自大至小有序，试改写教科书9.1.1节中顺序查找算法，将监视哨设在高下标端。然后画出描述此查找过程的判别树，分别求出等概率情况下查找成功和不成功时的平均查找长度。9.26 试将折半查找的算法改写成递归算法。9.27 试改写教科书9.1.2节中折半查找的算法，当ri.keykri+1.key(i=1,2,n-1)时，返回i；当kr1.key时，返回0；当krn.key时，返回n。 9.28 试编写利用折半查找确定记录所在块的分块查找算法。并讨论在块中进行顺序查找时使用“监视哨”的优缺点，以及必要时如何在分块查找的算法中实现设置“监视哨”的技巧。9.29 已知一非空有序表，表中记录按关键字递增排列，以不带头结点的单循环链表作存储结构，外设两个指针h和t，其中h始终指向关键字最小的结点，t则在表中浮动，其初始位置和h相同，在每次查找之后指向刚查到的结点。查找算法的策略是：首先将给定值k和t-key进行比较，若相等，则查找成功；否则因k小于或大于t-key而从h所指结点或t所指结点的后继结点起进行查找。 按上述查找过程编写查找算法。 画出描述此查找过程的判定树，并分析在等概率查找时查找成功的平均查找长度（假设表长为n，待查关键码k等于每个结点关键码的概率为1/n，每次查找都是成功的，因此在查找时，t指向每个结点的概率也为1/n）。9.30 将9.28题的存储结构改为双向循环链表，且外设一个指针sp，其初始位置指向关键字最小的结点，在每次查找之后指向刚查到的结点。查找算法的策略是：首先将给定值k和sp-key进行比较，若相等，则查找成功；否则依k小于或大于sp-key继续从* sp的前驱或后继结点起进行查找。编写查找算法并分析等概率查找时查找成功的平均查找长度。 9.31 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表为存储结构。且树中结点的关键字均不同。9.32 已知一棵二叉排序树上所有关键字中的最小值为-max,最大值为max，又-maxxmax。编写递归算法，求该二叉排序树上的小于x且最靠近x的值a和大于x且最靠近x的值b。 9.33 编写递归算法，从大到小输出给定二叉排序树中所有关键字不小于x的数据元素。要求你的算法的时间复杂度为o(log2n+m