算法设计考研题

1.带权图的最短路径问题是找出冲初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：1）该最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；2）选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v；3）重复（2），直到u是目标顶点时为止。

请问上述方法能否求得最短路径？若可行证明，否举例。

不能。如下图，括号中的是权（路径长度），顶顶是点，从0到3，如果按照贪心法，将走0-2-3，而实际最短为0-1-3。

2.已知一个带有表头结点的单链表：假设该链表只给出了头指针list，在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），若成功，算法输出该结点的data域的值，并返回1；否则只返回0。

要求：1）描述算法的基本设计思想；2）描述步骤，给出简要注释。

增加2个指针变量和一个整型变量，从链表头向后遍历，其中指针p指向当前遍历的结点，指针p1指向p1所指向结点的前k个结点，如果p之前没有k个结点，那么p1指向表头结点。用整型变量i表示当前遍历了多少个结点，当i>k时，p1随着每次的遍历，也向请移动一个结点。则遍历完成时，p1或者指向表头结点，或者指向链表中倒数第k个位置上的结点。

空间3，时间n

3设将n(n,1)个整数存放到一维数组r中，试设计一个在时间和空间两方面尽可能有效的算法，将r中保有的序列循环左移p(0﹤p﹤n)个位置，即将r中的数据由(x0 x1 ……xn-1)变换为(xp xp+1 ……xn-1 x0 x1 ……xp-1)要求：1)给出算法的基本设计思想。2)表述算法，给出注释。

3)说明你所设计算法的时间复杂度和空间复杂度。

分析：时间复杂度为o(n),空间复杂度为o(1)

1）当n%p==0时，可以做p*(n/p)次搬运，具体的说就是每一趟搬运的是等价类，做p次。2）当n%p!=0时，做n次a[(j+p)%n]=a[j]

**void move_p_steps(int a,int n,int p)}

else}}

4.一个长度为l(l≥1)的升序序列s，处在第l/2个位置的数称为s的中位数。例如，若序列s1=(11, 13, 15, 17, 19)，则s1的中位数是15。

两个序列的中位数是含它们所有元素的升序序列的中位数。例如若s2=(2, 4, 6, 8, 20)，则s1和s2的中位数是11。现有两个等长升序序列a和b，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列a和b的中位数。

要求：1)给出算法的基本设计思想。2)根据设计思想，描述算法，关键之处给出注释。

3)说明你所设计算法的时间复杂度和空间复杂度。

1)分别求两个升序序列a和b的中位数，设为a和b。

如果a=b，则a或者b即为所求的中位数。

原因：如果将两序列归并排序，则最终序列中，排在子序列ab前边的元素为先前两序列中排在a和b前边的元素；排在子序列ab后边的元素为先前两序列a和b后边的元素。所以子序列ab一定位于最终序列的中间，有因为a=b，显然a就是中位数。

如果a≠b(假设a

原因：同样可以用归并排序后的序列来验证，归并后排序后必然有形如…a…b…的序列出现，中位数必然出现在(a，b)范围内。因此可以做如下处理：

舍弃a所在序列a之中比较小的一半，同时舍弃b所在序列b之中比较大的一半。在保留的两个升序序列中求出新的中位数a和b，重复上述过程，直到两个序列只含一个元素为止，则较小者即为所求中位数。

(2)int search(int a,int 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]

else//若元素个数为偶数。

}elseelse //若元素个数为偶数个。

}}return (a[s1]}

3)上述所给算法的时间、空间复杂度分别是o(log2n)和o(1)。

因为每次总的元素个数变为原来的一半，所以有：

第一次：元素个数为n/2=n/(21)

第二次：元素个数为n/4=n/(22)

第k次：元素个数为n/(2k)

最后元素个数为2

则有n/(2k)=2

解得k= log2n – 1

因此：时间复杂度为o(log2n)，而空间复杂度从上述程序中可看出为o(1)。

算法设计考研题

《现代设计方法》考研题

机械设计考研题

2019考研题

其他用户还读了