《数据结构与算法练习题.doc》由会员分享，可在线阅读，更多相关《数据结构与算法练习题.doc（9页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法练习题三、写一个算法归并两个已排序的线性表。（用两种方法：数组表示的线性表（次序表）和指针表示的线性表（链表）要求：1、定义线性表节点的构造，并定义节点的型和地点的型。2、定义线性表的基本操作3、在1，2的基础上，达成此题。4、在main函数中进行测试：先建立两个有序的线性表，而后归并这两个线性表。四、已知一个单向链表，试给出复制该链表的算法。要求：1、定义线性表的节点的构造以及节点的型和地点的型。2、定义线性表的基本操作3、在1，2的基础上，达成此题。4、在main函数中进行测试：先建立一个线性表，并定义一个空线性表，而后进行复制。五、写出从一个带表头的单链表中删除其值等于给定
2、值x的结点的算法函数：intdelete(LIST&L,intx);假如x在该链表中，则删除对应结点，并返回其在链表中的地点（逻辑地点，第一个结点的逻辑地点为1），不然返回-1。要求：1、定义线性表的节点的构造以及节点的型和地点的型。2、定义线性表的基本操作3、在1，2的基础上，达成此题。4、在main函数中进行测试：先建立一个线性表，而后调用函数删除值等于给定值的节点。六、写出一个将两个静态链表（属于同一个储存池）归并的算法函数：voidMerge(cursorM,cursorN);归并的方法是将N链表中的全部结点增添到M链表的后边，并将N链表的表头结点增添到安闲结点链表中。要求：1、定义静
3、态链表的结点的构造以及结点的型SPACE以及地点（position）和游标（cursor）的型。2、定义静态链表的基本操作：voidInitialize();初始化，将全部储存池中的结点设置为安闲；cursorGetNode();从安闲链中获取一个结点；voidFreeNode(cursorq);将结点q加入到安闲链；voidInsert(elementtypex,positionp,cursorM);在链表M中的地点为p的元素后边增添一个值为x的结点；voidDelete(cursorM,positionp);在链表M中删除地点为p的元素的后一个元素。3、在1、2的基础上达成此题。4、在ma
4、in函数中进行测试：先建立一个储存池，而后在该储存池中创立两个静态表，最后将这两个静态表归并。七、利用指针表示的线性表(链表)表示一个多项式，并实现两个多项式的相加和相乘运算。假定多项式形式为：A(x)amtemam1xem1.a1xe1此中，系数ai0，指数ei知足emem-1e2e1=0。要求：1、定义多项式每一项的构造。2、定义两个多项式的相加和相乘运算函数。3、在main函数中，建立两个多项式，并测试相加和相乘运算。八、试编写一个整数进制变换的通用函数convert(intnum,STACKS,intn)，要求将整数换为n进制数，n进制数的各位挨次寄存在栈S中。并在主函数中进行测试。要
5、求：1、定义栈以及栈的型。m转2、定义栈的各样操作。3、实现函数convert。4、在main函数中，经过调用函数中，并经过出栈的方法输出该n进制数convert将num的n进制数寄存到一个栈九、设有一个循环行列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的计数器count，试写出相应的判断行列空、判断行列满、出队算法和入队算法。要求：1、定义相应的循环行列的型（只有头指针，没有尾指针，但有一个元素个数的计数器）；2、定义该行列的四个算法：判断行列空、判断行列满、出队算法和入队算法；3、在main函数考证算法的正确性。十、设主串T=“abcaabbabcabaacbacb
6、a“，模式为p=“abcabaa”。1、计算模式p的nextval函数值2、不写算法，只画出利用KMP算法进行模式般配时，每一趟的般配过程。要求：1、写出模式p的nextval值；2、画出KMP算法的每一趟般配过程（可参照教材P61从第8行开始的内容）；3、不需要编写程序。十一、假定表达式中同意包括三种括号：圆括号、方括号和大括号。设计一个算法采纳次序栈（用数组表示的栈）判断表达式中的括号能否正确配对。要求：1、定义栈以及栈的型，栈中所寄存元素的种类为字符型，定义列举种类此中两个元素分别为TRUE和FALSE。2、定义栈的各样操作。Boolean，3、定义函数Booleancheck(char
7、*s);判断s中的括号能否正确配对，假如正确配对，返回TRUE，不然返回FALSE。4、在主函数中考证所编写函数的正确性。十二、设有一个带头结点的双向链表h，设计一个算法用于查找第一个元素之为x的结点，并将其与其前驱结点进行互换。要求：1、定义带头结点的双向链表的型DLIST。2、定义双向链表DLIST的基本操作。3、定义函数果在链表中存在元素值为intswap(elementtypex,DLIST&h)，查找第一个元素之为x的结点，如x的结点，并其与其前驱结点进行互换，并返回1，不然返回0。4、在主函数中测试所编写函数的正确性。十三、试编写一个求三元组次序表示的稀少矩阵对角线元素之和的算法十
8、四、当拥有同样行值和列值的稀少矩阵A和B均以三元组次序表方式储存时，试写出矩阵相加的算法，其结果寄存在以行逻辑链接次序表方式储存的矩阵C中。十五、设有一个稀少矩阵：0400000000300180000000005000070002000060001、写出三元组次序表储存表示2、写出十字链表储存的次序表示十六、画出广义表LS=(),(e),(a,(b,c,d)的头尾链表储存构造要求：依据教材中的案例画出相应的图形，不需要编程。此中第一个节点以下：(近似于教材P70图。t十七、试编写求广义表中原子元素个数的算法。要求：1、定义广义表的节点的型；2、定义广义表的基本操作；3、定义此题要求的函数in
9、telements(listpointerL)；函数返回值为广义表中原子的个数。比如，广义表(a,b,c,d)原子的个数为4，而广义表(a,(a,b),d,e,(i,j),k)中院子的个数为3。提示：先利用基本操作Cal(L)获取表头，判断表头能否是原子，再利用基本操作Cdr(L)获取除第一个元素外的其余元素所形成的表L1，利用递归的方法求L1中原子的个数。要求：1、上述作业要求在独自达成；2、达成后，于规按限期内提交到ftp服务器的相应目录中中，注意，在提交时将所编写的程序一致拷贝到一个Word文件中，文件名格式为“学号+姓名”三（数组表示）#includeusingnamespacestd
10、;#definemaxlength100typedefintposition;typedefintElementtype;structLISTElementtypeelementsmaxlength;intlast;positionEnd(LISTL)ext=j+1;ext=-1;available=0;ext=-1)p=-1;elsep=SPACEavailable.next;SPACEavailable.next=SPACEp.next;returnp;voidFreeNode(cursorq)ext=available;available=q;voidInsert(Elementtype
11、x,positionp,cursorM)lement=x;SPACEq.next=SPACEp.next;SPACEp.next=q;voidDelete(cursorM,positionp)ext!=-1)if(SPACESPACEp.next.next!=-1)q=SPACEp.next;SPACEp.next=SPACEq.next;FreeNode(q);elseq=SPACEp.next;FreeNode(q);/*归并:将N链表中的全部结点增添到M链表的后边，并将N链表的表头结点增添到安闲结点链表中。*/voidMerge(cursorM,cursorN)positionp=M;p
12、ositionq=N;while(SPACEp.next!=-1)p=SPACEp.next;SPACEp.next=SPACEq.next;positionr=available;SPACEN.next=r;available=N;voidInput(cursorM)ext;elseSPACEp.element=-1;p=-1;break;voidOutput(cursorM)positionp;p=M;while(p!=-1)coutSPACEp.elementt;p=SPACEp.next;coutendl;intmain()lement=2;SPACE0.next=6;SPACE1.element=4;SPACE1.next=3;SPACE2.next=4;SPACE3.element=8;SPACE3.next=-1;SPACE4.element=10;SPACE4.next=7;SPACE5.next=0;SPACE6.
