数据结构与算法试题(8)

float RecurveArray::Average(int n) { if (n= =1) return (float)Elements[0];

else return ((float) Elements[n-1]+(n-1)*Average(n-1))/n; }

int main(int argc, char *argv[ ]){ int size=1;

cout<<”No.of the Elements:”; while (size<1) cin>>size; RecurveArray ra(size); Ra.InputArray( );

Cout<<”\\n The max is :”<

3、 试编写一个函数计算n!*2n的值，结果存放于数组A[arraySize]的第n个数组元素中，0 ? n ? arraySize。若设计算机中允许的整数的最大值为maxInt，则当n > arraySize或者对于某一个k (0 ? k ? n)，使得k!*2k > maxInt时，应按出错处理。可有如下三种不同的出错处理方式：

(1) 用cerr <<及exit (1)语句来终止执行并报告错误；

(2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回； (3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种

错误返回。

用你认为是最好的方式实现它。

答案：#include “iostream.h” #define arraySize 100 #define MaxInt 0x7fffffff int calc (int t[ ],int n){ int i,edge=MaxInt/n/2; t[0]=1; if (n!=0) {

for (i=1;iedge) return 0; }

t[n]=t[n-1]*n*2; }

cout<<”t[“<

void main()

{int A[arraySize];int i; for(i=0;i

cout<<”failed at ”<

4、 编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。

答案：

include include”string.h”

const int charnumber=128;

void frequency(string&s,int C[ ]){ for(int i=0;i< charnumber;i++) C[i]=0; for( i=0;i< s.length();i++) C[atoi(s[i])]++; for( i=0;i< charnumber;i++)

if(C[i]>0) cout<<”(”<

测试数据 s=”cast cast sat at a tasa\\0” 测试结果 A C c 2 a 7 s 4 t 5 空格 5 5、 若矩阵Am?n中的某一元素A[i][j]是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵，试编写一个函数，确定鞍点在数组中的位置（若鞍点存在时），并分析该函数的时间复杂度

答案：int minmax(int A[ ][ ],const int m,const int n) { int *row=new int [m]; int *col=new int [n]; int i,j; for(i=0;i

if(A[i][j]

}

for(j=0;j

if(A[i][j]>col[j]) col[j]=A[i][j]; }

for(i=0;i

cout<<”The saddle point is :(“<

此算法有3个并列二重循环，其时间复杂度为O(m*n).

6、试编写一个函数，将一个有n个非零元素的整数一维数组A[n]拆分为两个一维数组，使得A[ ]中大于零的元素存放在B[ ]中，小于零的元素存放在C[ ]中。

答案：

void fenjie(int A[],int B[],int C[],int n,int &pb,int &pc){ pb=pc=-1;

for(int k=0;k0) B[++pb]=A[k]; else C[++pc]=A[k];}

7、已知在一维数组A[m+n]中依次存放着两个顺序表（a0, a1, ... am-1,）和（b0, b1, ... bn-1,），试编写一个函数，将数组中两个顺序表的位置互换，即交（b0, b1, ... bn-1,）

放在（a0, a1, ... am-1,）的前面。 答案：#define mpn 20 typedef int DataType;

void inverse(DataType A[ ],int st, int ed); void exchange(DataType A[ ],int m, int n){ inverse(A,0,m+n-1); inverse(A,0,n-1); inverse(A,n,m+n-1); }

void inverse(DataType A[ ],int st, int ed){ int md=(st+ed)/2; for(int i=0;i

{ DataType temp=A[st+i]; A[st+i]= A[ed-i]; A[ed-i]=temp;}} 8、 设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。

答案：templatevoid List ::Inverse(){ if(first==Null) return ;

ListNode*p=first->link,*pr=Null; While(p!=Null){ First->link=pr;

Pr=first;first=p;p=p->link;

}

first->link=pr; }