算法设计

第一章
数据结构（本科）期末综合练习五（算法设计题）

1. 设有一个线性表 (e0, e1, …, en-2, en-1) 存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个元素内容置换为 (en-1, en-2, …, e1, e0)。
函数的原型为：
template
void inverse ( Type A[ ], int n );


2. 试编写一个函数，在一个顺序表A中找出具有最大值和最小值的整数。
函数的原型如下所示，原型的参数表中给出顺序表对象为A，通过算法执行，从参数表中的引用参数Max中得到表中的最大整数，Min中得到表中的最小整数。
注意，函数中可使用顺序表的两个公有函数：
Length( ) 求表的长度；
getData(int k) 提取第k个元素的值。

#include “SeqList.h”
template void FindMaxMin ( SeqList& A, int& Max, int& Min );


3. 设有两个整数类型的顺序表A（有 m个元素）和B（有n个元素），其元素均以升序排列。试编写一个函数，将这两个顺序表合并成一个顺序表C，要求C的元素也以升序排列（表中允许元素重复）。
函数的原型如下所示。原型中的参数表给出参加运算的三个顺序表A、B与C。从C中得到执行结果。函数中用到顺序表的4个公有函数：
Length( ) 求表的当前长度；
maxLength( ) 求表的最大允许长度；
getData(int k) 提取第k个元素的值；
setData(int k, int val) 修改第k个元素的值为val。

template
void merge(SeqList& A, SeqList& B, SeqList& C);


4. 编写一个函数frequency，统计在一个输入字符串中各个不同字符出现的频度。函数返回两个数组：A[ ]记录字符串中有多少种不同的字符，C[ ]记录每一种字符的出现次数。此外，还要通过整数k返回不同字符数。
函数的原型如下所示：
#include
#include
void frequency( char* s, char A[ ], int C[ ], int &k );


5. 根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。要求新生成的链表中不允许有重复元素，并要求返回新表的表头指针。填写程序中缺少的部分。
ListNode * Merge ( ListNode *L1, ListNode *L2 ) {
//根据两个有序单链表L1和L2, 生成一个新的有序单链表
ListNode *p1 = L1->link, *p2 = L2->link;
ListNode *first=new ListNode;
ListNode *p=first;
while ( p1 != NULL && p2 != NULL ) { //当两个链表都未检测完时










}
while ( p1 != NULL ) { //继续处理p1链表中剩余的结点。
p=p->link = new ListNode; p->data = p1->data; p1 = p1->link;
}
while ( p2 != NULL ) { //继续处理p2链表中剩余的结点。
p=p->link = new ListNode; p->data = p2->data; p2 = p2->link;
}
p->link

= NULL;
return first->link;
}


6. 假定在一个带表头结点的单链表L中所有结点的值按递增顺序排列，试补充下面函数，功能是删除表L中所有其值大于等于min，同时小于等于max的结点。
void rangeDelete ( ListNode * L, ElemType min, ElemType max )
{
ListNode *q = L, *p = L->link;







}


7. 已知一个带表头附加结点的单链表LA中包含有三类字符：数字字符；字母字符；其他字符。试编写一个while循环补充下面Separate函数，其功能是构造三个新的单链表，使LA,LB,LC单链表各自指向同一类字符。要求使用原表的结点空间。Separate函数将调用如下两个函数：
bool isdigit(char ch); //判断字符是否为数字，若是则返回“真”，否则返回“假”
bool isalpha(char ch); //判断字符是否为字母，若是则返回“真”，否则返回“假”

void Separate ( ListNode *& LA, ListNode *& LB, ListNode *& LC )
{ //原来的单链表是LA, 新的三个单链表是LA,LB,LC，它们均需要带表头附加结点
ListNode *pa=LA;
ListNode *pb=new ListNode, *pc=new ListNode;
LB=pb; LC=pc;
ListNode *p=LA->link; //p指向待处理的结点

//添加的while循环位置

pa->link = NULL; pb->link = NULL; pc->link = NULL;
}

//请把while循环内容写在此行下面


8. 已知first为单链表的表头指针, 结点结构为(data,link），试根据下列每个函数声明和算法功能写出递归算法。
int Max(LinkNode *f); //递归算法: 求链表中的最大值，若链表为空则返回0







int Num(LinkNode *f); //递归算法: 求链表中结点个数






9. 请分别写出在循环队列上进行插入和删除操作的算法。
循环队列定义如下：
struct CyclicQueue {
ElemType elem[M]; //M为已定义过的整型常量，表示队列长度
int rear,front ; // rear指向队尾元素后一个位置，front 指向队头元素
int tag ;
// 当 front=rear且tag=0时，队列空，当front=rear且tag=1时，队列满
};

bool EnCQueue( CyclicQueue& Q, ElemType x )
{
// Q 是一个循环队列，最多可存储M个元素，若队列不满，
//将x插入至队尾并返回 true；否则返回 false。







}

bool DelCQueue( CyclicQueue& Q, ElemType& x )
{
// Q 是一个循环队列，若队列不空，则删除队头元素并由 x 带回，
//且返回 true，否则返回 false







}


10. Q 是一个由其尾指针和队列长度标识的循环队列，请写出插入和删除一个元素的算法。
struct CyclicQueue // 循环队列定义
{
ElemType elem[M]; //M为已定义过的整型常量
int rear; // rear指向队尾元素的后

一个位置
int length; // length 指示队列中元素个数
};

bool EnCQueue( CyclicQueue& Q, ElemType x )
{
//Q是一个循环队列，若队列不满，则将x插入并返回true；否则返回false






}

bool DelCQueue( CyclicQueue& Q, ElemType& x )
{
//Q 是一个循环队列，若队列不空，则删除队头元素并由x带回，
//且返回true；否则返回false






}


11. 计算多项式 Pn (x) = a0 xn + a1 xn-1 + a2 xn-2 + …… + an-1 x + an 通常使用的方法是一种递推的方法。它可以描述为如下的递推形式：
pn (x) = x * pn-1 (x) + an (n>0)
此处
Pn-1 (x) = a0 xn-1 + a1 xn-2 + …… + an-2 x + an-1
P0=an
这也是问题的递归形式。多项式的递归求解形式为：
poly(x, 0) = A[0]
poly(x, n) = x * poly(x, n-1) + A[n], n > 0

试编写一个递归函数，计算这样的多项式的值。
float poly ( float x, float A[], int n ) {





}


12. 从n个自然数1, 2, 3, …, n中任取k个数的所有组合数用C(n, k) 表示。求C(n, k)的递归公式为
0 (n<=0, n1 (n>0, k=0或k=n)
n (n>0, k=1)
C(n-1, k) + C(n-1, k-1) (n>1, 0
试写出计算C(n, k)的递归函数：
int combine ( int n, int k) {






}


13. 已知二叉树中的结点类型BinTreeNode定义为:
struct BinTreeNode {char data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面函数声明编写出求一棵二叉树高度的算法，该高度由函数返回。假定树根的层次为0，参数BT初始指向这棵二叉树的根结点。
int BTreeHeight(BinTreeNode* BT);


14. 已知二叉树中的结点类型BinTreeNode定义为:
struct BinTreeNode {char data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。
int BTreeCount(BinTreeNode* BT);


15. 已知二叉树中的结点类型BinTreeNode定义为:
struct BinTreeNode {char data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。
int BTreeLeafCount(BinTreeNode* BT);


16. 已知二叉树中的结点类型BinTreeNode定义为:
struct BinTreeNode {char data; BinTreeNode *left, *right;};
其中data为结点值域，left和right

分别为指向左、右子女结点的指针域，根据下面函数声明编写出删除一棵二叉树中所有结点的算法，并使树根指针为空。假定引用参数BT初始指向这棵二叉树的根结点。
void ClearBTree(BinTreeNode*& BT);


17. 已知二叉树中的结点类型BinTreeNode定义为:
struct BinTreeNode {char data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出判断两棵二叉树是否相等的算法，若相等则返回1否则返回0。算法中参数T1和T2为分别指向这两棵二叉树根结点的指针。当两棵树的结构完全相同并且对应结点的值也相同时才被认为相等。
int BTreeEqual(BinTreeNode* T1,BinTreeNode* T2);


18. 已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode {char data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出交换一棵二叉树中所有结点的左、右指针域值的算法，算法中参数BT初始指向这棵二叉树的根结点。
void BTreeSwop(BinTreeNode* BT)



19. 已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode {char data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出复制一棵二叉树的算法，并返回复制得到的二叉树的根结点指针。算法中参数BT初始指向待复制二叉树的根结点。
BinTreeNode* BTreeCopy(BinTreeNode* BT);


20. 已知二叉树中的结点类型BinTreeNode定义为:
struct BinTreeNode {char data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出从一棵二叉树中求出结点值大于X的结点个数的算法，并返回所求结果。算法中参数BT初始指向一棵二叉树的根结点。
int BTreeCount(BinTreeNode* BT, ElemType x);



21. 假定元素类型为ElemType的一维数组R[n]中保存着按关键码升序排列的n个记录，记录的关键码域key的类型为KeyType，试按照下面的函数声明编写一个非递归算法，从一维数组R[n]中折半搜索出关键码等于K的记录，若搜索成功则返回记录位置（即元素下标），否则返回-1。
int BinSearch(ElemType R[], int n, KeyType K);


22. 已知二叉搜索树中的结点类型BinTreeNode定义为:
struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数BST指向一棵二叉搜索树的根结点。试根据下面的函数声明编写一个非递归算法，从BST

树中搜索出具有item参数值的结点，若搜索成功则返回该结点的地址，否则返回NULL。
BinTreeNode* Find(BinTreeNode* BST, const ElemType& item);


23. 已知二叉搜索树中的结点类型BinTreeNode定义为:
struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数BST指向一棵二叉搜索树的根结点。试根据下面的函数声明编写一个递归算法，向BST树中插入值为item的结点，若树中不存在item结点则进行插入并返回1表示插入成功，若树中已存在item结点则不插入并返回0表示插入失败。
Int Insert(BinTreeNode*& BST, const ElemType& item);


24. 已知二叉搜索树中的结点类型BinTreeNode定义为:
struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数BST指向一棵二叉搜索树。试根据下面的函数声明编写一个非递归算法，向BST树中插入值为item的结点，若树中不存在item结点则进行插入并返回1表示插入成功，若树中已存在item结点则不插入并返回0表示插入失败。

Int Insert(BinTreeNode*& BST, const ElemType& item);


25. 有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个数据互不相同的表进行排序，并将排序结果存放到另一个新表中。针对表中的每个数据，计数算法都要扫描一趟表，统计出表中有多少个数据比它小。假设针对某个数据，统计出的计数值为c，则这个数据在新表中的合适存放位置应为c。
在下面的函数模板countsort中，数组src中存放的是要排序的数据；数组dest用于存放排序的结果；size为这两个数组的大小。请补充完整countsort的函数体中遗漏部分，使其能够完成计数排序任务。

template
void countsort(T src[], T dest[], int size){
int i, j, c;
for(i=0; i//此处遗漏了若干语句，请将这些语句插入到下面




dest[c]=src[i];
}
}


26. 假定函数reArrange通过扫描一遍data数组达到重新排列数据的目的, 使得所有负值数据位于所有非负值和0值数据之前。请补充完整reArrange函数体中遗漏部分，使其能够完成所要求的功能。(提示：从两端向中间扫描)

template
void reArrange(T data[],int size){
int i=0,j=size-1;
T temp;
while(i//此处遗漏了若干语句，请将它们插入到下面






}
}

第二章
算法设计题参考解答
1. template
void inverse(Type A[], int n){
Type tmp; //变量名任意
for(int i=0; i<=(n-1)/2; i++){ //或把i<=(n-1)/2改为i

tmp=A[i]; A[i]=A[n-i-1]; A[n-i-1]=tmp;
}
}

2. #include “SeqList.h”
template void FindMaxMin ( SeqList& A, int& Max, int& Min ) {
Max = Min = A.getData(0);
for ( int i = 1; i < A.Length( ); i++ ) {
if ( A.getData(i) > Max ) Max = A.getData(i);
else if ( A.getData(i) < Min ) Min = A.geyData(i);
}
}

3. template
void merge(SeqList& A, SeqList& B, SeqList& C) {
int m=A.Length(), n=B.Length(), mpn=m+n;
if(mpn>C.maxLength()){
cerr<<“合并后表的长度超出表C的最大允许长度”<exit(1);
}
int i=0, j=0, k=0, av=A.getData(i), bv=B.getData(j);
while(iif(av<=bv) {C.setData(k++, av); av=A.getData(++i);}
if(av>=bv){C.setData(k++, bv); bv=B.getData(++j);}
}
if(iwhile(kelse
while(k}

4. #include
#include "string1.h"
void frequency( char* s, char A[ ], int C[ ], int &k ) {int i, j, len =strlen(s);
if ( !len ) { cout << "The string is empty. " << endl; k = 0; return; }
A[0] = s[0]; C[0] = 1; k = 1;
for ( i = 1; i < len; i++ ) C[i] = 0;
for ( i = 1; i < len; i++ ) {
for ( j = 0; j < k && A[j] != s[i]; j++ );
if ( j == k ) { A[k] = s[i]; C[k]++; k++; }
else C[j]++;
}
}

5. p=p->link = new ListNode;
if ( p1->data == p2->data )
{ p->data = p1->data; p1 = p1->link; p2 = p2->link; }
else if ( p1->data < p2->data )
{ p->data = p1->data; p1 = p1->link; }
else { p->data = p2->data; p2 = p2->link; }

6. while ( p != NULL) { //2分
if(p->data >= min && p->data <=max) {
q->link=p->link; delete p; p=q->link;
} //4分
else {q=p; p=p->link;} //2分
}

7. while(p!=NULL) {
if(isdigit(p->data)) {pa->link=p; pa=p;}
else if(isalpha(p->data)) {pb->link=p; pb=p;}
else {pc->link=p; pc=p;}
p=p->link;
}

8. int Max(LinkNode *f) //递归算法: 求链表中的最大值
{
if(f==NULL) return 0;
if(f->link==NULL) return f->data;
int temp=Max(f->link);
if(f->data>temp) return f->data;
else return temp;
}

int Num(LinkNode *f); //递归算法: 求链表中结点个数
{
if(f==NULL) return 0;
return 1+Num(f->link);
}

9. // 将x插入至队尾
if (Q.rear == Q.front && Q.tag == 1) return false;
Q.elem[Q.rear] = x;
Q.rear = (Q.rear+1) % M;
if (Q.rear == Q.front) Q.tag = 1;
return true;

// 删除队头元素
if (Q.front == Q.rear && Q.tag == 0) return false;
x = Q.elem[Q.front];
Q.front = (Q.front+1) % M;
if (Q.front == Q.rear) Q.tag = 0;
return true;

10. //将x插入至队尾
if(Q.lengt

h==M) return false;
Q.elem[Q.rear]=x;
Q.rear=(Q.rear+1)%M;
Q.length++;
return true;

//删除队头元素
if(Q.length==0) return false;
x=Q.elem[(Q.rear-Q.length+M)%M];
Q.length--;
return true;

11. float poly ( float x, float A[ ], int n ) {
if ( ! n ) return A[0];
else return x * poly( x, A, n-1 ) + A[n];
}

12.
int combine (int n, int k)
{
if(n<=0 || nif(k==0 || k==n) return 1;
if(k==1) return n;
return combine (n-1,k)+ combine (n-1,k-1);
}

13. int BTreeHeight(BinTreeNode* BT)
{
if(BT==NULL)
//对于空树，返回-1并结束递归
return –1;
else
{
//计算左子树的高度
int h1=BTreeHeight(BT->left);
//计算右子树的高度
int h2=BTreeHeight(BT->right);
//返回树的高度
if(h1>h2) return h1+1;
else return h2+1;
}
}
说明：函数体中的两个else可以没有

14. int BTreeCount(BinTreeNode* BT)
{
if(BT==NULL)
return 0;
else
return BTreeCount(BT->left)+BTreeCount(BT->right)+1;
}

15. int BTreeLeafCount(BinTreeNode* BT)
{
if(BT==NULL) return 0;
else if(BT->left==NULL && BT->right==NULL) return 1;
else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right);
}
说明：函数体中的两个else可以没有

16. void ClearBTree(BinTreeNode*& BT)
{
if(BT!=NULL)
{
//递归删除左子树
ClearBTree(BT->left);
//递归删除右子树
ClearBTree(BT->right);
//回收根结点
delete BT;
//置根指针为空
BT=NULL;
}
}

17. int BTreeEqual(BinTreeNode* T1,BinTreeNode* T2)
{
//若两棵树均为空则返回1表示相等
if(T1==NULL && T2==NULL) return 1;
//若一棵为空一棵不为空则返回0表示不等
else if(T1==NULL || T2==NULL) return 0;
//若根结点值相等并且左、右子树对应相等则两棵树相等
else if(T1->data==T2->data && BTreeEqual(T1->left, T2->left) &&
BTreeEqual(T1->right, T2->right) )
return 1;
//若根结点值不等或左、右子树对应不等则两棵树不等
else
return 0;
}

另一个参考答案：

int BTreeEqual(BinTreeNode* T1,BinTreeNode* T2)
{
//若两棵树均为空或实际上是同一棵树时返回1表示相等
if(T1==T2) return 1;
//若一棵为空一棵不为空则返回0表示不等
if(T1==NULL || T2==NULL) return 0;
//若根结点值不等返回0表示不等
if(T1->data!=T2->data) return 0;
//若根结点值相等则两棵树是否相等取决于它们的左、右子树是否对应相等
return BTreeEqual(T1->left, T2->left) && BTreeEqual(T1->right, T2->right);
}

18. void BTreeSwop(BinTreeNode* BT)
{
if(BT!=NULL) {
//交换左右子女指针域的值
BinTreeNode* pt=BT->left;
BT->left=BT->right;
BT->right=pt;
//对左子树进行同样处理
BTreeSwop(BT->left);
//

对右子树进行同样处理
BTreeSwop(BT->right);
}
}

19. BinTreeNode* BTreeCopy(BinTreeNode* BT)
{
if(BT==NULL) return NULL;
else {
//得到新结点
BinTreeNode* pt=new BinTreeNode;
//复制根结点值
pt->data=BT->data;
//复制左子树
pt->left=BTreeCopy(BT->left);
//复制右子树
pt->right=BTreeCopy(BT->right);
//返回新树的树根指针
return pt;
}
}
说明：函数体中的else可以没有

20. //统计出二叉树中大于给定值x的结点个数，该统计值由函数返回
int BTreeCount(BinTreeNode* BT, ElemType x)
{
if(BT==NULL) return 0;
else if( BT->data>x)
return BTreeCount( BT->left, x)+BTreeCount( BT->right, x)+1;
else
return BTreeCount( BT->left, x)+BTreeCount( BT->right, x); //3分
}
说明：函数体中的两个else可以没有

21. int BinSearch(ElemType R[], int n, KeyType K)
{
int low=0, high=n-1;
while(low<=high)
{
int mid=(low+high)/2;
if(K==R[mid].key) return mid;
else if(Kelse low=mid+1;
}
return -1;
}
说明：函数体中第一个else可以没有

22. BinTreeNode* Find(BinTreeNode* BST, const ElemType& item)
{
while(BST!=NULL)
{
if(item==BST->data) return BST;
else if(itemdata) BST=BST->left;
else BST=BST->right;
}
return NULL;
}

说明：函数体中第一个else可以没有

23. int Insert(BinTreeNode*& BST, const ElemType& item)
{
if(BST==NULL){
BinTreeNode* p=new BinTreeNode;
p->data=item;
p->left=p->right=NULL;
BST=p;
return 1;
}
else if(item==BST->data) return 0;
else if(itemdata)
return Insert(BST->left, item);
else
Insert(BST->right, item);
}
说明：函数体中的三个else可以没有

24. int Insert(BinTreeNode*& BST, const ElemType& item)
{
//搜索插入位置
BinTreeNode* t=BST, *parent=NULL;
while(t!=NULL) {
parent=t;
if(item==t->data) return 0;
else if(itemdata) t=t->left;
else t=t->right;
}
//建立值为item，左、右指针域为空的新结点
BinTreeNode* p=new BinTreeNode;
p->data=item;
p->left=p->right=NULL;
//将新结点插入到二叉搜索树中的确定位置上
if(parent==NULL) BST=p;
else if(itemdata) parent->left=p;
else parent->right=p;
}

说明：while循环体中的第一个else可以没有

25. c=0;
for(j=0; j
26. while(data[i]<0 && iwhile(data[j]>=0 && j>i) j--;

if(itemp=data[j]; data[j]=data[i]; data[i]=temp;
i++; j--;