目前刚整理了 的试题 过几天 的也会上传上去
希翼对你有匡助。。。。。。。
答案与试题是配套的 选择题没有解析 有不懂得可以在文库上 我
2022 1-5 ：BCDBC 6-10：BADBA
41.该方法求得的路径不一定是最
短路径。例如，对于下图所示的带权
图，如果按照题中的原则，从A 到 C
的最短路径为 A→B →C，事实上其最
短路径为 A →D →C。
42. (1)算法的基本设计思想：定义两个指针变量p 和 q，初始时均指向头 结点的下一个结点。 P 指针沿链表挪移；当p 指针挪移到第 k 个结点时， q 指针 开始与 p 指针同步挪移；当 p 指针挪移到链表最后一个结点时， q 指针所指元素 为倒数第 k 个结点。以上过程对链表仅进行一遍扫描。
(2)算法的详细实现步骤：
①count=0,p 和 q 指向链表表头结点的下一个结点；
②若 p 为空，转⑤；
③若 count 等于 k,则 q 指向下一个结点;否则,count=count+1;
④p 指向下一个结点， 转步骤②；
⑤若 count 等于 k,则查成功,输出该结点的 data 域的值,返回 1;返回； 查失败,返回 0;
⑥算法结束。(3)算法实现：
typedef struct LNode{
int data;
struct LNode * link;
} * LinkList;
int SearchN(LinkList list,int k){
LinkList p,q;
int count=0; /*计数器赋初值*/
p=q=list->link; /*p 和 q 指向链表表头结点的下一个结点*/
while(p!=NULL){
if(count<k) count++; /*计数器+1*/
2022
41.
else q=q->link;/*q 移到下一个结点*/
p=p->link; /*p 移到下一个结点*/
}
if(count<k)return(0);/*如果链表的长度小于 k,查失败*/
查成功*/
return (1);}//else}//SearchN
1-5 ：DCDCB 6- 11 ：ACBBDA
(1)构造的散列表如下
(2)查成功的平均查长度:ASL 成功=12/7。
查不成功的平均查长度:ASL 不成功=18/7。
42.(1)给出算法的基本设计思想： 先将 n 个数据 x0x1…xp…xn- 1 原地逆置， 得到 xn- 1…xpxp- 1…x0,然后再将前 n-p 个和后 p 个元素分别原地逆置， 得到最终 结果:xpxp+1…xn- 1x0x1…xp- 1。
(2)算法实现：
void reverse(int r[],int left,int right){
int k=left,j=right,temp; //k 等于左边界 left,j 等于右边界 right
while(k<j){//交换 r[k]和 r[j]
temp=r[k];
r[k]=r[j];
r[j]=temp;
k++;//k 右移一个位置
j--;//j 左移一个位置
}
}
void leftShift(int r[],int n,int p){
if(p>0&&p<n){
reverse(r,0,n-1);//将全部数据逆置
reverse(r,0,n-p-1);//将前 n-p 个元素逆置
reverse(r,n-p,n-1);//将后 p 个元素逆置
}
}
(3)说明算法复杂性：上述算法的时间复杂度为 O(n),空间复杂度为 O(1)。 2022 1-5 ：ABBCC 6-10：DACBA
41.高分笔记 图 最后一题
42.(1)算法的基本设计思想： (5 分)
是 O(n)，空间复杂度 O(n)。
2) 高效的方法：分别求两个升序序列 A 和 B 的中位数，设为 a 和b 。 如 果 a=b，则 a 或者b 即为所求的中位数。
原因：如果将两序列归并排序，则最终序列中，排在子序列 ab 前边的元素 为先前两序列中排在 a 和 b 前边的元素;排在子序列ab 后边的元素为先前两序列考研计算机真题 a 和 b 后边的元素。所以子序列ab 一定位于最终序列的中间，有因为 单招录取通知书查询a=b，显然 a 就是中位数。
如果 a≠b(假设 a< p>
原因：同样可以用归并排序后的序列来验证，归并后排序后必然有形如… a…b…的序列浮现，中位数必然浮现在(a，2022国家公务员局专题网站b)范围内。因此可以做如下处理：舍 弃 a 所在序列A 之中比较小的一半， 同时舍弃 b 所在序列 B 之中比较大的一半。 在保留的两个升序序列中求出新的中位数 a 和b，重复上述过程， 直到两个序列 只含一个元素为止，则较小者即为所求中位数。
(2)算法实现(高效方法)：(8 分)
int Search(int A[], int博学之审问之慎思之明辨之笃行之>2022年河南省公务员考试报名入口 B[], int n){
int s1,e1,mid1,s2,e2,mid2;
s1=0;e1=n-1;s2=1;e2=n-1;
while(s1!=e1||s2!=e2){
mid1=(s1+e1)/2;
mid2=(s2+e2)/2;
if(A[mid1]==B[mid2]) return A[mid1];
if(A[mid1]< p){//分别考虑奇数和偶数，保持两个子数组元素个数相等 历年省考进面分数线if((s1+e1)%2==0){//若元素个数为奇数
s1=mid1;//舍弃 A 中间点以前部份且保留中间点
e2=mid2; //舍弃 B 中间点以后部份且保留中间点
}//if
else{//若元素个数为偶数
s1=mid1+1;//舍弃 A 中间点以前部份且保留中间点
e2=mid2; //舍弃 B 中间点以后部份且保留中间点
}//else
}//if
else{
if((s1+e1)%2==0){//若元素个数为奇数个
e1=mid1;//舍弃 A 中间点以后部份且保留中间点
s2=mid2;//舍弃 B 中间点以前部份且保留中间点
}//if
else {//若元素个数为偶数个
e1=mid1+1;//舍弃 A 中间点以后部份且保留中间点
s2=mid2;//舍弃 B 中间点以前部份且保留中间点
}//else
}//else
}//while
return (A[s1])
}//search
发布评论