2019年真題

題目：設線性表L=（a1，a2，a3,......,a(n-2)，a(n-1)，a(n)），采用帶頭結點的單鏈表保存，鏈表中的結點定義如下。請設計一個空間復雜度為O(1)且時間上盡可能高效的算法，重新排列L中的各結點，得到新線性表L'=（a1，a(n)，a2，a(n-1)，a3，a(n-2),......）。

typedef struct node {int data;struct node *next; } NODE;

?思路分析：①先找到鏈表的中心結點，使用兩個指針p，每次p走一步，q走兩步，當q到鏈表尾時，p正好在鏈表中心結點。②將鏈表后半段原地逆置。③將單鏈表前后兩段中依次各取一個結點，進行重排。

NODE *reverseList(NODE *head) {//將指針全部反轉 NODE* pre = NULL;NODE* cur = head;NODE* tmp = NULL;//記錄cur的下一個結點while(cur != NULL) {//記錄當前節點的下一個節點tmp = cur->next;//然后將當前節點指向precur->next = pre;//pre和cur節點都前進一位pre = cur;cur = tmp;}return pre; } void changeList(NODE *head) {NODE *p, *q, *temp;p = q = head;//1、找到中間結點 while(q->next != NULL) {p = p->next;q = q->next;if(q->next != NULL) {//q走兩步。用if再判斷一次是為了防止走一步后就已到隊尾，出現NULL->next異常 q = q->next;}} //此時p指向鏈表L的中心結點 n/2，向下取整。 //2、后半段鏈表反轉。 NODE *back = reverseList(p-next);//將后半段鏈表逆置，back指向后半段鏈表的第一個節點。 NODE *pre = head->next; //pre指向前半段鏈表的第一個節點。 //3、前半段鏈表和后半段鏈表依次各取一個結點。 while(e != NULL) {temp = back->next;//用于back指針后移back->next = pre->next;pre->next = back;pre = back->next;//pre指針后移 back = temp; //back指針后移 } }

鏈表的算法題一定要手動模擬一遍。其中鏈表反轉部分參考力扣：https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/

?

2018年真題

題目：給定一個含n（n>=1）個整數的數組，請設計一個在時間上盡可能高效的算法，找出數組中未出現的最小正整數。例如，數組{-5,3,2,3}中未出現的最小正整數是1；數組{1,2,3}中未出現的最小正整數是4。

思路分析：基于map的思想，創建一個和數組等長的map<int,int>，遍歷數組，對map[i]++；再遍歷一次map，對第一次出現的map[i]!=0時的鍵i輸出，即為最小正整數。但408不讓用STL，因此用數組來代替map。

1、創建動態數組：

在堆中開辟一塊大小為n*sizeof(int)的一塊內存空間（因為int是32位，因而此處開辟了n*4Bit的存儲空間）；

指針B指向這塊內存空間的起始地址（即數組的第一個元素）；

malloc前面的（int*）用于強制類型轉換，表示這塊空間用來存儲int型數組。

int *B = (int *)malloc(n*sizeof(int)); free(B);void* malloc(size_t size); //其中參數size_t size表示動態內存分配空間的大小，以字節為單位。malloc返回值是一個指針。void free(void *ptr); //當不在使用malloc()函數申請的空間之后，應釋放掉這個內存空間：

2、批量賦初值：對數組B中的n個元素均賦值為0。

memset(B,0,n*sizeof(int));void *memset(void *s, int v, size_t n); //這里s可以是數組名，也可以是指向某一內在空間的指針； //v為要填充的值； //n為要填充的字節數；

完整代碼：

#include <iostream> #include <string.h> using namespace std;/*數組中未出現的最小正整數*/int findMissMin(int A[], int n){int *B = (int *)malloc(n*sizeof(int)); //創建動態數組并分配存儲空間memset(B,0,n*sizeof(int)); //賦初值int i;for(i = 0; i < n; ++i) {if(A[i] > 0 && A[i] < n){// 僅對數組A中的值為1~n的元素進行處理B[ A[i]- 1 ]++;}}for(i = 0; i < n; ++i) {if(B[i] == 0){break;}}free(B);return i + 1; }int main(){int a[3] = {1,2,3}, c[4] = {-5,3,2,3};cout<<"{1,2,3}中未出現的最小正整數："<<findMissMin(a, 3)<<endl;cout<<"{-5,3,2,3}中未出現的最小正整數："<<findMissMin(c, 4)<<endl;return 0; }

2010年真題（順序表）（循環左移p位）

設將n(n>1)個整數存放到一維數組R中，設計一個在時間和空間方面都盡可能高效的算法。將R中的序列循環左移p (0<p<n) 個位置，即將R中的數據由{Xo，X, …， Xn-1}變換為{Xp，Xp+1, … Xn-1, X0，X1, …，Xp-1}。

思路分析：用a表示數組的前p個元素，用b表示余下的(n-p)個元素。本題將數組ab轉換為ba，則考慮對a、b分別逆置后，在對整體逆置，即可得到循環左移后的序列。(類似線代的可逆矩陣）

#include <iostream> using namespace std; #define n 10 //數組最大長度為10void Reverse(int R[], int l, int r){int i, j, temp;for(i = l, j = r; i < j; ++i, --j){temp = R[i];R[i] = R[j];R[j] = temp;} }int main() {int p = 7; //循環左移7位 int *R = (int *)malloc(sizeof(int) * n);for(int i = 0; i < n; ++i){R[i] = i + 1;} Reverse(R, 0, p-1); // 前p位逆序為：7 6 5 4 3 2 1 Reverse(R, p, n-1); //余下n-p位逆序為： 10 9 8Reverse(R, 0, n-1);// 整體逆序為：8 9 10 1 2 3 4 5 6 7 for(int i = 0; i < n; ++i){cout<<R[i]<<" ";} return 0; }

效率分析：時間復雜度在于Reverse函數，為O(n)，空間復雜度O(1) 。

2011年真題（順序表）（升序序列取中值）

一個長度為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的中位數。

思路分析：考慮歸并排序中merge函數的思想，從兩個升序序列的首部通過比較依次取出較小值，取出的第L個數即為整體中值。本方法的時間復雜度為O(n)，但勝在思路與代碼簡單，另還有較復雜的優化的O(logn)方法。

#include <iostream> using namespace std; #define n 3int findMid(int A[], int B[], int L){int i = 0, j = 0; int mid;while(i + j < L){//當i+j=L時跳出循環，取中值 if(A[i] < B[j]) {mid = A[i++];}else {mid = B[j++];}}return mid; }int main() {int A[n] = {1, 3, 5};int B[n] = {2, 4, 6};cout<<findMid(A,B,n);return 0; }

?

2009年真題（單鏈表）（查找倒數第k個數）

typedef struct node{/*結點類型定義*/ElemType data;/*結點的數據域*/struct node *next;/*結點的指針域*/ }LNode,*LinkList;int Search_K(LinkList L, ElemType k) { //查找倒數第k個結點 LNode *p = L->next;LNode *q = L->next;while(p != NULL) {if(k > 0) k--;//p先行走k步 else q = q->next;p = p->next;}if(k > 0){//p遍歷完了k仍為減到0，查找失敗 return 0;}else{cout<<q->data<<endl;return 1; } }

?

總結

以上是生活随笔為你收集整理的计算机考研408的算法题详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。