算法設(shè)計(jì) 考研題

1. 帶權(quán)圖的最短路徑問題是找出 沖初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一 條最短路徑，假設(shè)從初始頂點(diǎn)到目 標(biāo)頂點(diǎn)之間存在路徑，現(xiàn)有一種解 決該問題的方法：1)該最短路徑 初始時(shí)僅包含初始頂點(diǎn)，令當(dāng)前頂 點(diǎn)u為初始頂點(diǎn)；2)選擇離u最 近且尚未在最短路徑中的一個(gè)頂 點(diǎn)▼，加入到最短路徑中，修改當(dāng) 前頂點(diǎn)u=v； 3)重復(fù)(2)，直到 u是目標(biāo)頂點(diǎn)時(shí)為止。請(qǐng)問上述方 法能否求得最短路徑？若可行證 明，否舉例。 不能。如下圖，括號(hào)中的是權(quán)(路 徑長(zhǎng)度)，頂頂是點(diǎn)，從0到3， 如果按照貪心法，將走0-2-3，而 實(shí)際最短為0-1-3。 0——(10)——2 I (2) I 1 (2) 3 2. 已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈 表：假設(shè)該鏈表只給出了頭指針 list，在不改變鏈表的前提下，設(shè) 計(jì)一個(gè)盡可能高效的算法，查找鏈 表中倒數(shù)第K個(gè)位置上的結(jié)點(diǎn)(K 為正整數(shù))，若成功，算法輸出該 結(jié)點(diǎn)的data域的值，并返回1；否 則只返回0。要求：1)描述算法的 基本設(shè)計(jì)思想；2)描述步驟，給 出簡(jiǎn)要注釋。 增加2個(gè)指針變量和一個(gè)整型變 量，從鏈表頭向后遍歷，其中指針 p指向當(dāng)前遍歷的結(jié)點(diǎn)，指針p1指 向P1所指向結(jié)點(diǎn)的前k個(gè)結(jié)點(diǎn)， 如果p之前沒有k個(gè)結(jié)點(diǎn)，那么p1 指向表頭結(jié)點(diǎn)。用整型變量i表示 當(dāng)前遍歷了多少個(gè)結(jié)點(diǎn)，當(dāng)i&gt;k 時(shí)，p1隨著每次的遍歷，也向請(qǐng)移 動(dòng)一個(gè)結(jié)點(diǎn)。則遍歷完成時(shí)，p1或 者指向表頭結(jié)點(diǎn)，或者指向鏈表中 倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)?？臻g3, 時(shí)間n p=list->link; p1=list; i=1; while (p) { p=p->link; i++; if (i>k) p1=p1->next; } if (p1==list) return 0; else { printf("%d\n", p1->data); return 1; } 3設(shè)將n(n,1)個(gè)整數(shù)存放到一維數(shù) 組R中，試設(shè)計(jì)一個(gè)在時(shí)間和空間 兩方面盡可能有效的算法，將R中 保有的序列循環(huán)左移P(0<P<n) 個(gè)位置，即將R中的數(shù)據(jù)由(X0 X1……Xn-1)變換為(Xp Xp+1 Xn-1 X0 X1 Xp-1) 要求：1)給出算法的基本設(shè)計(jì)思 想。2)表述算法，給出注釋。3)說 明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和 空間復(fù)雜度 分析：時(shí)間復(fù)雜度為O(n),空間復(fù) 雜度為O(1) (1) 當(dāng) n%p==0 時(shí)，可以做 p*(n/p) 次搬運(yùn)，具體的說就是每一趟搬運(yùn) 的是等價(jià)類，做p次。2)當(dāng)n%p!=0 時(shí)，做 n 次 a[(j+p)%n]=a[j] 代碼 void move_p_steps(int a[],int n,int p){ int i,j,temp,temp1; if(n%p==0){ for(i=0;i<p;i++){ temp=a[n-1-i]; for(j=n-1-i-p;0<=j;j-=p) a[j+p]=a[j]; a[(n-1-i+p)%n]=temp;}} else{j=0;temp=a[0]; for(i=0;i<n;i++){ temp1=a[(j+p)%n]; a[(j+p)%n]=temp; temp=temp1; j=(j+p)%n;}}} 4. 一個(gè)長(zhǎng)度為L(zhǎng)(LN1)的升序序列 S，處在第L/2個(gè)位置的數(shù)稱為S 的中位數(shù)。例如，若序列S1=(11, 13, 15, 17, 19)，則S1的中位數(shù)是15。 兩個(gè)序列的中位數(shù)是含它們所有 元素的升序序列的中位數(shù)。例如若 S2=(2, 4, 6, 8, 20)，則 S1 和 S2 的中位數(shù)是11?，F(xiàn)有兩個(gè)等長(zhǎng)升序 序列A和B，試設(shè)計(jì)一個(gè)在時(shí)間和 空間兩方面都盡可能高效的算法， 找出兩個(gè)序列A和B的中位數(shù)。要 求：1)給出算法的基本設(shè)計(jì)思想。 2)根據(jù)設(shè)計(jì)思想，描述算法，關(guān)鍵 之處給出注釋。3)說明你所設(shè)計(jì)算 法的時(shí)間復(fù)雜度和空間復(fù)雜度。 (1)分別求兩個(gè)升序序列A和B的 中位數(shù)，設(shè)為a和b。 如果a=b，則a或者b即為所 求的中位數(shù)。 原因：如果將兩序列歸并排 序，則最終序列中，排在子序列ab 前邊的元素為先前兩序列中排在a 和b前邊的元素;排在子序列ab后 邊的元素為先前兩序列a和b后邊 的元素。所以子序列ab 一定位于 最終序列的中間，有因?yàn)閍=b，顯 然a就是中位數(shù)。 如果a#b(假設(shè)a 原因：同樣可以用歸并排序后 的序列來驗(yàn)證，歸并后排序后必然 有形如…a“?b…的序列出現(xiàn)，中位 數(shù)必然出現(xiàn)在(a，b)范圍內(nèi)。因此 可以做如下處理：舍棄a所在序列 A之中比較小的一半，同時(shí)舍棄b 所在序列B之中比較大的一半。在 保留的兩個(gè)升序序列中求出新的 中位數(shù)a和b，重復(fù)上述過程，直 到兩個(gè)序列只含一個(gè)元素為止，則 較小者即為所求中位數(shù)。 (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] {//分別考慮奇數(shù)和偶數(shù)，保 持兩個(gè)子數(shù)組元素個(gè)數(shù)相等一 if((s1+e1)%2==0)//若元素 個(gè)數(shù)為奇數(shù) {s1=mid1;//舍棄A中間點(diǎn)以 前部分且保留中間點(diǎn) e2=mid2; //舍棄B中間點(diǎn)以 后部分且保留中間點(diǎn) }else//若元素個(gè)數(shù)為偶數(shù) {s1=mid1+1;//舍棄A中間點(diǎn) 以前部分且保留中間點(diǎn) e2=mid2; //舍棄B中間點(diǎn)以 后部分且保留中間點(diǎn) }}else{if((s1+e1)%2==0)// 若元素個(gè)數(shù)為奇數(shù)個(gè) {e1=mid1;//舍棄A中間點(diǎn)以 后部分且保留中間點(diǎn) s2=mid2;//舍棄B中間點(diǎn)以前 部分且保留中間點(diǎn) }else //若元素個(gè)數(shù)為偶數(shù)個(gè) {e1=mid1+1;//舍棄A中間點(diǎn) 以后部分且保留中間點(diǎn) s2=mid2;//舍棄B中間點(diǎn)以前 部分且保留中間點(diǎn) }}}return (A[s1]} (3) 上述所給算法的時(shí)間、空間復(fù) 雜度分別是O(log2n)和O(1)。 因?yàn)槊看慰偟脑貍€(gè)數(shù)變?yōu)樵瓉?的一半，所以有： 第一次：元素個(gè)數(shù)為 n/2=n/(21) 第二次：元素個(gè)數(shù)為 n/4=n/(22) 第k次：元素個(gè)數(shù)為n/(2k) 最后元素個(gè)數(shù)為2 則有 n/(2k)=2 解得 k= log2n - 1 因此：時(shí)間復(fù)雜度為 O(log2n)，而空間復(fù)雜度從上述程 序中可看出為O(1)。