数据结构(本科)期末综合练习(算法设计题).DOC

1数据结构（本科）期末综合练习（算法设计题）1.设有一个线性表(e0,e1,…,en-2,en-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个元素内容置换为(en-1,en-2,…,e1,e0)。函数的原型为：templateclassTypevoidinverse(TypeA[],intn);2.试编写一个函数，在一个顺序表A中找出具有最大值和最小值的整数。函数的原型如下所示，原型的参数表中给出顺序表对象为A，通过算法执行，从参数表中的引用参数Max中得到表中的最大整数，Min中得到表中的最小整数。注意，函数中可使用顺序表的两个公有函数：Length()求表的长度；getData(intk)提取第k个元素的值。#include“SeqList.h”templateclassTvoidFindMaxMin(SeqListint&A,int&Max,int&Min);3.设有两个整数类型的顺序表A（有m个元素）和B（有n个元素），其元素均以升序排列。试编写一个函数，将这两个顺序表合并成一个顺序表C，要求C的元素也以升序排列（表中允许元素重复）。函数的原型如下所示。原型中的参数表给出参加运算的三个顺序表A、B与C。从C中得到执行结果。函数中用到顺序表的4个公有函数：Length()求表的当前长度；maxLength()求表的最大允许长度；getData(intk)提取第k个元素的值；setData(intk,intval)修改第k个元素的值为val。templateclassTvoidmerge(SeqListint&A,SeqListint&B,SeqListint&C);4.编写一个函数frequency，统计在一个输入字符串中各个不同字符出现的频度。函数返回两个数组：A[]记录字符串中有多少种不同的字符，C[]记录每一种字符的出现次数。此外，还要通过整数k返回不同字符数。函数的原型如下所示：#includeiostream.h#includestring.h2voidfrequency(char*s,charA[],intC[],int&k);5.根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。要求新生成的链表中不允许有重复元素，并要求返回新表的表头指针。填写程序中缺少的部分。ListNode*Merge(ListNode*L1,ListNode*L2){//根据两个有序单链表L1和L2,生成一个新的有序单链表ListNode*p1=L1-link,*p2=L2-link;ListNode*first=newListNode;ListNode*p=first;while(p1!=NULL&&p2!=NULL){//当两个链表都未检测完时}while(p1!=NULL){//继续处理p1链表中剩余的结点。p=p-link=newListNode;p-data=p1-data;p1=p1-link;}while(p2!=NULL){//继续处理p2链表中剩余的结点。p=p-link=newListNode;p-data=p2-data;p2=p2-link;}p-link=NULL;returnfirst-link;}6.假定在一个带表头结点的单链表L中所有结点的值按递增顺序排列，试补充下面函数，功能是删除表L中所有其值大于等于min，同时小于等于max的结点。voidrangeDelete(ListNode*L,ElemTypemin,ElemTypemax){ListNode*q=L,*p=L-link;3}7.已知一个带表头附加结点的单链表LA中包含有三类字符：数字字符；字母字符；其他字符。试编写一个while循环补充下面Separate函数，其功能是构造三个新的单链表，使LA,LB,LC单链表各自指向同一类字符。要求使用原表的结点空间。Separate函数将调用如下两个函数：boolisdigit(charch);//判断字符是否为数字，若是则返回“真”，否则返回“假”boolisalpha(charch);//判断字符是否为字母，若是则返回“真”，否则返回“假”voidSeparate(ListNode*&LA,ListNode*&LB,ListNode*&LC){//原来的单链表是LA,新的三个单链表是LA,LB,LC，它们均需要带表头附加结点ListNode*pa=LA;ListNode*pb=newListNode,*pc=newListNode;LB=pb;LC=pc;ListNode*p=LA-link;//p指向待处理的结点//添加的while循环位置pa-link=NULL;pb-link=NULL;pc-link=NULL;}//请把while循环内容写在此行下面8.已知first为单链表的表头指针,结点结构为(data,link），试根据下列每个函数声明和算法功能写出递归算法。intMax(LinkNode*f);//递归算法:求链表中的最大值，若链表为空则返回0intNum(LinkNode*f);//递归算法:求链表中结点个数49.请分别写出在循环队列上进行插入和删除操作的算法。循环队列定义如下：structCyclicQueue{ElemTypeelem[M];//M为已定义过的整型常量，表示队列长度intrear,front;//rear指向队尾元素后一个位置，front指向队头元素inttag;//当front=rear且tag=0时，队列空，当front=rear且tag=1时，队列满};boolEnCQueue(CyclicQueue&Q,ElemTypex){//Q是一个循环队列，最多可存储M个元素，若队列不满，//将x插入至队尾并返回true；否则返回false。}boolDelCQueue(CyclicQueue&Q,ElemType&x){//Q是一个循环队列，若队列不空，则删除队头元素并由x带回，//且返回true，否则返回false}10.Q是一个由其尾指针和队列长度标识的循环队列，请写出插入和删除一个元素的算法。structCyclicQueue//循环队列定义{ElemTypeelem[M];//M为已定义过的整型常量5intrear;//rear指向队尾元素的后一个位置intlength;//length指示队列中元素个数};boolEnCQueue(CyclicQueue&Q,ElemTypex){//Q是一个循环队列，若队列不满，则将x插入并返回true；否则返回false}boolDelCQueue(CyclicQueue&Q,ElemType&x){//Q是一个循环队列，若队列不空，则删除队头元素并由x带回，//且返回true；否则返回false}11.计算多项式Pn(x)=a0xn+a1xn-1+a2xn-2+……+an-1x+an通常使用的方法是一种递推的方法。它可以描述为如下的递推形式：pn(x)=x*pn-1(x)+an(n0)此处Pn-1(x)=a0xn-1+a1xn-2+……+an-2x+an-1P0=an这也是问题的递归形式。多项式的递归求解形式为：poly(x,0)=A[0]poly(x,n)=x*poly(x,n-1)+A[n],n0试编写一个递归函数，计算这样的多项式的值。floatpoly(floatx,floatA[],intn){6}12.从n个自然数1,2,3,…,n中任取k个数的所有组合数用C(n,k)表示。求C(n,k)的递归公式为0(n=0,nk)1(n0,k=0或k=n)n(n0,k=1)C(n-1,k)+C(n-1,k-1)(n1,0kn)试写出计算C(n,k)的递归函数：intcombine(intn,intk){}13.已知二叉树中的结点类型BinTreeNode定义为:structBinTreeNode{chardata;BinTreeNode*left,*right;};其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面函数声明编写出求一棵二叉树高度的算法，该高度由函数返回。假定树根的层次为0，参数BT初始指向这棵二叉树的根结点。intBTreeHeight(BinTreeNode*BT);14.已知二叉树中的结点类型BinTreeNode定义为:structBinTreeNode{chardata;BinTreeNode*left,*right;};其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。intBTreeCount(BinTreeNode*BT);15.已知二叉树中的结点类型BinTreeNode定义为:structBinTreeNode{chardata;BinTreeNode*left,*right;};7其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。intBTreeLeafCount(BinTreeNode*BT);16.已知二叉树中的结点类型BinTreeNode定义为:structBinTreeNode{chardata;BinTreeNode*left,*right;};其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出删除一棵二叉树中所有结点的算法，并使树根指针为空。假定引用参数BT初始指向这棵二叉树的根结点。voidClearBTree(BinTreeNode*&BT);17.已知二叉树中的结点类型BinTreeNode定义为:structBinTreeNode{chardata;BinTreeNode*left,*right;};其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出判断两棵二叉树是否相等的算法，若相等则返回1否则返回0。算法中参数T1和T2为分别指向这两棵二叉树根结点的指针。当两棵树的结构完全相同并且对应结点的值也相同时才被认为相等。intBTreeEqual(BinTreeNode*T1,BinTreeNode*T2);18.已知二叉树中的结点类型用BinTreeNode表示，被定义为:structBinTreeNode{chardata;BinTreeNode*left,*right;};其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出交换一棵二叉树中所有结点的左、右指针域值的算法，算法中参数BT初始指向这棵二叉树的根结点。voidBTreeSwop(BinTreeNode*BT)19.已知二叉树中的结点类型用BinTreeNode表示，被定义为:structBinTreeNode{chardata;BinTreeNode*left,*right;};其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出复制一棵二叉树的算法，并返回复制得到的二叉树的根结点指针。算法中参数BT初始指向待复制二叉树的根结点。BinTreeNode*BTreeCopy(BinTreeNode*BT);20.已知二叉树中的结点类型BinTreeNode定义为:structBinTreeNode{chardata;BinTreeNode*left,*right;};8其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出从一棵二叉树中求出结点值大