數(shù)據(jù)結(jié)構(gòu)考研題

1、1求整數(shù)n(n 0)階乘的算法如下，其時間復(fù)雜度是int fact(i nt n) if (npre_op,則將c入棧，并讀入下一個字符，若ci,m,w e 、i,川，v cii , m,w d 、川，w, v答案：a選擇排序：每趟排序在當(dāng)前待排序序列中選出關(guān)鍵字最小的記錄，添加到有序序列中。 可以希爾排序：先將待排序序列劃分為若干小序列，在這些小序列中進(jìn)行插入排序；逐步擴大小序列的長度，減少小序列的個數(shù)，這樣使待排序序列逐漸處于更有序序列。不可以快速排序：從待排序記錄序列中選取一個記錄作為樞軸，其關(guān)鍵字值設(shè)為k，將關(guān)鍵字記錄小于k的移到k前面，關(guān)鍵字大于k的記錄移到k后面結(jié)果將待排序序列分為

2、兩個子表，最后將關(guān)鍵字值為k的記錄插入分界處，再在兩個子表中遞歸劃分。可以堆排序：每趟排序找出關(guān)鍵字最小的元素的同時找出關(guān)鍵字值較小的元素?？梢远窔w并排序：將若干有序序列進(jìn)行兩兩歸并，直至所有待排序記錄為一個有序序列。不可以11、對一待排序序列分別進(jìn)行折半插入排序和直接插入排序，兩者之間可能的不同是A、排序的總趟數(shù) E、元素的移動次數(shù) C、使用輔助空間的數(shù)量 D元素直接的比較次數(shù) 答案：D41、設(shè)有6個有序表A、B、C、D E、F,分別含有 10、35、40、50、60和200 個數(shù)據(jù) 元素，各表中元素按升序排列。要求通過 5次兩兩合并，將6個表最終合并成1個升序表，并在最壞情況 下比較的總

3、次數(shù)達(dá)到最小。請問答下列問題。(1) 給出完整的合并過程，并求出最壞情況下比較的總次數(shù)。(2) 根據(jù)你的合并過程，描述n (n2)個不等長升序表的合并策略，并說明理由。解答：一、要使比較的次數(shù)達(dá)到最小，即使含有元素越多的表，越在最后與其他表進(jìn)行合并。1）五次合并過程：第一次：合并A、B表，生產(chǎn)含有45個元素的AE表； 第二次：合并AB（表，生產(chǎn)含有85個元素的AB（表;第三次：合并 D E表，生產(chǎn)含有110個元素的DE表;第四次：合并ABC DE表生成含有195個元素的ABCD表；第五次：合并ABCDE F表，生成含有395個元素的ABCDE表 ；2）比較次數(shù)最壞的比較情況是在比較結(jié)束時，兩個

4、有序表都被遍歷結(jié)束。此時的比較次數(shù)為兩表表長之和減1.，所以，第一次比較次數(shù) 44次，第二次比較次數(shù)84次，第三次比較次數(shù)109次， 第四次比較次數(shù)194次，第五次比較次數(shù) 294次，即總的比較次數(shù)為 44+84+109+194+394=825二、進(jìn)行n個不等長的有序表合并時，要使最終的比較次數(shù)達(dá)到最小，在進(jìn)行兩兩合并的過 程中，應(yīng)每次選擇當(dāng)前長度最短的兩個有序表進(jìn)行合并。42、假定采用帶頭結(jié)點的單鏈表保存單詞，當(dāng)兩個單詞有相同的后綴時，則可共享相同的后綴存儲空間，例如，“ loading ”和being ”的存儲映像如下圖所示s1t2 .1 IJ-*111S JI TC P設(shè)str1和str

5、2分別指向兩個單詞所在單鏈表的頭結(jié)點，鏈表結(jié)點結(jié)構(gòu)為Datan ext請設(shè)計一個時間上盡可能高效的算法，找出str1和str2所指向的兩個鏈表共同后綴的起始位置（如圖中字符i所在的結(jié)點位置 p）要求：（1）給出算法的基本設(shè)計思想（2）根據(jù)設(shè)計思想，采用 C或C+或 JAVA語言描述算法，關(guān)鍵之處給出注釋（3）說明你所設(shè)計的算法的時間復(fù)雜度解答：一、算法思想：因為兩個單鏈表共享的存儲空間是從單鏈表的尾部的字母開始依次往前，連續(xù)相同的n的字符存儲在相同的儲存空間中，所以一起從頭部遍歷兩個長度不同的單鏈表時單鏈表不能保證他們同時到達(dá)兩個鏈表的尾結(jié)點。假設(shè)長的鏈表比短的鏈表多k個結(jié)點，則應(yīng)該先在長鏈表

6、上遍歷k個結(jié)點，之后同步遍歷兩個鏈表，這樣才能夠保證它們同時到達(dá)最后一個結(jié)點了。即應(yīng)該：1） 遍歷兩個單鏈表求出它們的長度L1，L2；2）比較兩個單鏈表長度L1和L2的大小找出較長的鏈表，并求出長的鏈表比短的鏈表多的結(jié)點數(shù) k=|L1-L2| ；3）先遍歷長鏈表的k個結(jié)點；4）同步遍歷兩個鏈表，直至找到相同結(jié)點或鏈表結(jié)束。二、算法實現(xiàn)代碼Lin kList Fin d（L in kList L1,L in kList L2）int len1=L1.Listlength（）,len2=L2.ListLength（）;調(diào)用 LIstLength （）函數(shù)求單鏈表的長度Lin kList Ion g

7、,short;分別表示較長和較短的單鏈表if（le n1le n2）Iong=L1-next;/略去L1和L2開始時的空的頭結(jié)點short=L2-next;k=len1-len2;/ 單鏈表長度之差elselong=L2-next;/ 將長的鏈表賦給 long ，短的鏈表賦給 shortshort=L1-next;k=len2-len1;int n=0 ；While(nnext;while(long!=NULL)if(long=short)/ 結(jié)點數(shù)值相等則為共同結(jié)點，返回該結(jié)點 return long;else/ 結(jié)點不同繼續(xù)比較兩者的下一個結(jié)點 long=long-next;short=short-next;if (