历年计算机算法真题

《历年计算机算法真题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、datalink0942.（15分）己知一个带有表头结点的单链表，结点结构为假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表屮倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0o要求：（1）描述算法的基本设计思想（2）描述算法的详细实现步骤（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实现），关键Z处请给出简要注释。42.（1）算法基本思想如下：从头至尾遍历单链表，并用指针P指向当前节点的前K个节点。

2、当遍历到链表的最后一个节点时，指针P所指向的节点即为所查找的节点。（2）详细实现步骤：增加两个指针变暈和一个整型变暈，从链表头向后遍历，其屮指针P1指向当前遍历的节点，指针P指向P1所指向节点的前K个节点，如果PlZ前没有K个节点，那么P指向表头节点。用整型变量i表示当前遍历了多少节点，当i>k时，指针P随着每次遍历，也向前移动一个节点。当遍历完成时，P或者指向表头就节点，或者指向链表中倒数第K个位置上的节点。（3）算法描述：IntLocateElement（linklist1ist,intk）{Pl=list->link;P二li

3、st;i二1；while（Pl）{Pl=Pl->link;i++；if（i>k）p=p一〉next;//如果i>k,则p也往后移}if（p==list）return0;//说明链表没有k个结点elseprintf("%d“，p->data);return1;1042.(13分)设将n(n>l)个整数存放到一维数组R•!',试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P(0

4、。(2)根据设计思想，釆用C或C卄或JAVA语言表述算法，关键之处给出注释。(3)说明你所设计算法的吋间复杂度和空间复杂度01234567894567890123解答：(1)前P个数依次进队，wh订e(1

5、数。例如，若S2=(2,4,6,&20),则S1和S2的中位数是11。现有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法，找岀两个序列A和B的中位数。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。(1)算法的基本设计思想如下。分别求出序列A和B的中位数，设为a和b,求序列A和B的中位数过程如21)若a二b,则a或b即为所求中位数，算法结束。2)若以乩则舍弃序列A中较小的一半，同时舍弃序列B中较大的

6、一半，耍求舍弃的长度相等：3)若a>b,则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求舍弃的长度相等；在保留的两个升序序列中，重复过程1)、2)、3),直到两个序列中只含一个元素时为止，较小者即为所求的中位数。(3)算法的时间复杂度为0(log2n),空间复杂度为0(1)