做网站的数据库,wordpress说说加分类,logo制作用什么软件,网站营销的特征有第二章 线性表算法题(线性表的顺序表示) 二、综合应用题 01.从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值。空出的位 置由最后一个元素填补#xff0c;若顺序表为空#xff0c;则显示出错信息并退出运行。 算法思想#xff1a;搜索整个顺序表#xf…第二章 线性表算法题(线性表的顺序表示) 二、综合应用题 01.从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值。空出的位 置由最后一个元素填补若顺序表为空则显示出错信息并退出运行。 算法思想搜索整个顺序表查找最小值元素并记录其位置搜索结束后用最后一个元素填补空出的最小值元素的位置。
bool Del_Min(SqList L,ElemType value)
{if(L.length0)return false;valueL.data[0];//假定0号元素的值最小 int pos0;for(int i1;iL.length;i){if(L.data[i]value){valueL.data[i];posi;}}L.data[pos]L.data[L.length-1];//空出的位置由最后一个元素填补 L.length--; return true;
} 02. 设计一个高效算法将顺序表L的所有元素逆置要求算法的空间复杂度为0(1)。 算法思想扫描顺序表L的前半部分元素对于元素L.data[i](0iL.length/2),将其与后半部分的对应元素L.data[L.length-i-1]进行交换。
void Reverse(SqList L)
{ElemType temp;for(int i0;iL.length/2;i){tempL.data[i];L.data[i]L.data[L.length-i-1];L.data[L.length-i-1]temp;}
} 03.对长度为n的顺序表L编写一个时间复杂度为0(m)、空间复杂度为0(1)的算法该算法删除线性表中所有值为x的数据元素。 算法思想解法1用k记录顺序表L中不等于x的元素个数(即需要保存的元素个数)扫描时将不等式x的元素移动到下标k的位置并更新k值。扫描结束后修改L的长度。
void del_x_1(SqList L,ElemType x)
{int k0,i;//记录值不等于x的元素个数for(i0;iL.length;i){if(L.data[i]!x){L.data[k]L.data[i];k;//不等于x的元素增1 } }L.lengthk; //顺序表L的长度等于k
} 算法思想解法2用k记录顺序表L中等于x的元素个数边扫描L边统计k,并将不等于x的元素前移k个位置。扫描结束后修改L的长度。
void Del_x_2(SqList L,ElemType x)
{int k0,i0;//k记录值等于x的元素个数 while(iL.length){if(L.data[i]x)k;elseL.data[i-k]L.data[i];//当前元素前移k个位置 i;}L.lengthL.length-k;//顺序表L的长度递减
} 04. 从有序顺序表中删除其值在给定值s与t之间(要求st)的所有元素若s或t不合理 或顺序表为空则显示出错信息并退出运行。 算法思想先寻找值大于或等于s的第一个元素(第一个删除的元素)然后寻找值大于t的第一个元素(最后一个删除的元素的下一个元素)要将这段元素删除只需直接将后面的元素前移。
bool Del_s_t2(SqList L,ElemType s,ElemType t)
{int i,j;if(st||L.length0)return false;for(i0;iL.lengthL.data[i]s;i)//寻找值大于或等于s的第一个元素 if(iL.length)return false;//所有值均小于s,返回 for(ji;jL.lengthL.data[j]t;j)//寻找值大于t的第一个元素 for(;jL.length;i,j)L.data[i]L.data[j];//前移填补被删除的元素 L.lengthi;return true;
} 05. 从顺序表中删除其值在给定值s与t之间(包含s和t要求st)的所有元素若s成 1不合理或顺序表为空则显示出错信息并退出运行。 算法思想从前向后扫描顺序表L用k记录下元素值在s到t之间元素的个数(初始时k0)。对于当前扫描的元素若其值不在s到t之间则前移k个元素否则执行k。由于这样每个不在s到t之间的元素仅移动一次因此算法效率高。
bool Del_s_t(SqList L,ElemType s,ElemType t)
{int i,k0;if(L.length0||st)return false;//线性表为空或s,t不合法返回 for(i0;iL.length;i){if(L.data[i]sL.data[i]t)k;elseL.data[i-k]L.data[i];//当前元素前移k个位置 }L.length-k;//长度减小 return true;
} 06.从有序顺序表中删除所有其值重复的元素使表中所有元素的值均不同。 算法思想注意是有序顺序表值相同的元素一定在连续的位置上用类似于直接插入排序的思想初始时将第一个元素视为非重复的有序表。之后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同若相同则继续向后判断若不同则插入前面的非重复有序表的最后直至判断到表尾为止。
bool Delete_Same(SqList L)
{if(L.length0)return false;int i,j;//i存储第一个不相同的元素j为工作指针 for(i0,j1;jL.length;j)if(L.data[i]!L.data[j])//查找下一个与上个元素值不同的元素 L.data[i]L.data[j];//找到后将元素前移 L.lengthi1;return true;
} 07.将两个有序顺序表合并为一个新的有序顺序表并由函数返回结果顺序表。 算法思想首先按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后看哪个表还有剩余将剩下的部分加到新的顺序表后面。
bool Merge(SqList A,SqList B,SqList C)
{if(A.lengthB.lengthC.length)//大于顺序表的最大长度 returnint i0,j0,k0;while(iA.lenthjB.length)//循环两两比较小者存入结果表 {if(A.data[i]B.data[j])C.data[k]A.data[i];elseC.data[k]B.data[j];}while(iA.length)//还剩一个没有比较完的顺序表 C.data[k]A.data[i];while(jB.length)C.data[k]B.data[j];C.lengthk;return true;
} 08.已知在一维数组A[m n]中依次存放两个线性表(a,1,a2,a3,...,am)和(b1,b2,b3,...,bn)。编写一个函数将数组中两个顺序表的位置互换即将(b1, b2, b3,...,bn)放在(a1,a2,a3,...,am)的前面。 算法思想先将数组A[mn]中全部元素(a1,a2,a3,...,am,b1,b2,b3,...,bn)原地逆置为(bn,bn-1,bn-2,...,b1,am,am-1,am-2,...,a1),再对前n个元素和后m个元素分别使用逆置算法即可得到(b1,b2,b3,...,nn,a1,a2,a3,...,am),从而实现顺序表的位置互换。
typedef int DataType;
void Reverse(DataType A[],int left,int right,int arraySize)
{if(leftright||rightarraySize)return;int mid(leftright)/2;for(int i0;imid-left;i){DataType tempA[lefti];A[lefti]A[right-i];A[right-i]temp;}
}
void Exchange(DataType A[],int m,int n,int arraySize)
{Reverse(A,0,mn-1,arraySize);Reverse(A,0,n-1,arraySize);Reverse(A,n,mn-1,arraySize);
} 09.线性表(a1,a2 a3,..., an)中的元素递增有序且按顺序存储于计算机内。要求设计一个算法完成用最少时间在表中查找数值为x的元素若找到则将其与后继元素位置相交换若找不到则将其插入表中并使表中元素仍递增有序。 算法思想顺序存储的线性表递增有序可以顺序查找也可以折半查找。题目要求“用最少的时间在表中查找数值为x的元素,这里应使用折半查找。
//09
void SearchExchangeInsert(ElemType A[],ElemType x)
{int low0,highn-1,mid;//low和high指向顺序表下界和上界的下标 while(lowhigh){mid(lowhigh)/2;//找中间位置 if(A[mid]x) break;else if(A[mid]x)lowmid1;elsehighmid-1;}if(A[mid]xmid!n-1)//若最后一个元素与x相等则不存在与其后继交换的操作 {tA[mid];A[mid]A[mid1];A[mid1]t;}if(lowhigh)//查找失败插入数据元素x {for(in-1;ihigh;i--)//后移元素 A[i1]A[i];A[i1]x;//插入x }
} 10. [2010统考真题]设将n(n1)个整数存放到一维数组R中。设计一个在时间和空间 两方面都尽可能高效的算法。将R中保存的序列循环左移p(0pn)个位置即将R 中的数据由(X0,X1,...,Xn-1)变换为(Xp.Xp1,...,Xn-1,X0,X1,...,Xp-1).要求: 1)给出算法的基本设计思想。 可将问题视为把数组ab转换成数组ba(a代表数组的前p个元素b代表数组中余下的n-p个元素)先将a逆置得到a逆b,再将b逆置得到a逆b逆最后将整个a逆b逆逆置得到(a逆b逆)逆ba。设Reverse函数执行将数组逆置的操作对abcdefgh向左循环移动3(p3)个位置的过程如下 Reverse(0,p-1)得到cbadefgh; Reverse(p,n-1)得到cbahgfed; Reverse(0,n-1)得到defghabc; 2)根据设计思想采用C或C或Java语言描述算法关键之处给出注释。
void Reverse(int R[],int from,int to)
{int i,temp;for(i0;i(to-from)/2;i){tempR[fromi];R[fromi]R[to-i];R[to-i]temp;}
}
void Converse(int R[],int n,int p)
{Reverse(R,0,p-1);Reverse(R,n,p-1);Reverse(R,0,n-1);
} 3)说明你所设计算法的时间复杂度和空间复杂度。 上述算法中三个Reverse函数的时间复杂度分别为O(p/2)、O((n-p)/2)和O(n/2),故所设计的算法的时间复杂度为O(n),空间复杂度为O(1。 11. [2011统考真题]一个长度为L(L≥1)的升序序列s, 处在第[L21个位置的数称为S 的中位数例如若序列S,(11,13,15,17,19) 则S的中位数是15,两个序列的中位 数是含它们所有元素的升序序列的中位数例如若S:(2,4,6,8,20) 则S和S:的中 位数是11.现在有两个等长升序序列4和B,试设计一个在时间和空间两方面都尽可能 高效的算法找出两个序列A和B的中位数、要求: 1)给出算法的基本设计思想。 分别求两个升序序列A、B的中位数设为a和b,求序列A、B的中位数过程如下
1.若ab,则a或b即为所求中位数算法结束。
2.若ab,则舍弃序列A中较小的一半同时舍弃序列B中较大的一半要求两次舍弃的长度相等。
3.若ab,则舍弃序列A中较大的一半同时舍弃序列B中较小的一半要求两次舍弃的长度相等。 2)根据设计思想采用C或C或Java语言描述算法关键之处给出注释。
int M_Search(int A[],int B[],int n)
{int s10,d1n-1,m1,s20,d2n-1,m2;while(s1!d1||s2!d2){m1(s1d1)/2;m2(s2d2)/2;if(A[m1]B[m2])return A[m1];//满足条件1 if(A[m1]A[m2])//满足条件2 {if((s1d1)%20)//若元素个数为奇数 {s1m1;//舍弃A中间点以前的部分且保留中间点 d2m2;//舍弃B中间点以后的部分且保留中间点 }else//若元素个数为偶数 {s1m11;//舍弃A中间点及中间点以前的部分 d2m2;//舍弃B中间点以后部分且保留中间点 }}else//满足条件3 {if((s2d2)%20)//若元素个数为奇数 {d1m1;//舍弃A中间点以后的部分且保留中间点 s2m2;//舍弃B中间点以前的部分且保留中间点}else//若元素个数为偶数 {d1m1;//舍弃A中间点以后的部分且保留中间点 s2m21;//舍弃B中间点及中间点以前部分 }}}return A[s1]B[s2]?A[s1]:B[s2];
} 3)说明你所设计算法的时间复杂度和空间复杂度。 算法的时间复杂度为O(log2n),空间复杂度为O(1)。 12. [2013统考真题]已知一个整数序列A(a0,a1,...,an-1),其中0≤ain(0≤in)。若 存在ap1ap2...apmx且mn/2 (0≤pkn,1≤k≤m),则称x为A的主元素。例如 A(0,5,5,3,5,7,5,5),则5为主元素;又如A(0,5,5,3,5,1,5,7) 则A中没有主元 素。假设A中的n个元素保存在一个一维数组中请设计一个尽可能高效的算法找出 A的主元素。若存在主元素则输出该元素:否则输出-1.要求: 1)给出算法的基本设计思想。 算法的基本设计思想:算法的策略是从前向后扫描数组元素标记出一个可能成为主元素的元素Num。然后重新计数确认Num是否是主元素。 算法可分为以下两步:
①选取候选的主元素。依次扫描所给数组中的每个整数将第一个遇到的整数Num保存到c中记录Num的出现次数为1;若遇到的下一个整数仍等于Num, 则计数加1否则计数减1;当计数减到0时将遇到的下一个整数保存到c中计数重新记为1开始新一轮计数即从当前位置开始重复上述过程直到扫描完全部数组元素。
②判断c中元素是否是真正的主元素。再次扫描该数组统计C中元素出现的次数若大于n/2则为主元素;否则序列中不存在主元素。
2根据设计思想采用C或C或Java语言描述算法关键之处给出注释。
int Majority(int A[],int n)
{int i,c,count1;//c用来保存候选主元素count用来计数 cA[0];//设置A[0]为候选主元素for(i1;in;i)//查找候选主元素 {if(A[i]c)count;//对A中的候选主元素计数 elseif(count0)//处理不是候选主元素的情况 count--;else//更换候选主元素重新计数 {cA[i];count1; }} if(count0)for(icount0;in;i)//统计候选主元素的实际出现次数 if(A[i]c)count;if(countn/2)return c;//确认候选主元素 elsereturn -1;//不存在主元素
}
3说明你所设计算法的时间复杂度和空间复杂度。 实现的程序的时间复杂度为O(n),空间复杂度为O(1)。
