初試2015年考研真題844答案

1、2015科學(xué)入學(xué)參考數(shù)據(jù)結(jié)構(gòu)試題（75分）一、簡答每小題5分，共15分1抽象數(shù)據(jù)類型的定義。答：抽象數(shù)據(jù)類型定義了一個數(shù)據(jù)對象、該數(shù)據(jù)對象中各元素間的邏輯關(guān)系以及一組基本操作。抽象數(shù)據(jù)類型使我們可以忽略細(xì)節(jié)，而將精力放到解決問題本質(zhì)上來。2算法的時間復(fù)雜度。答：算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量，它定量描述了該算法的運行時間。一般是計算基本語句的執(zhí)行次數(shù)，用問題規(guī)模n的一個函數(shù)來表示。實際中一般使用漸進時間復(fù)雜度，即不包括這個函數(shù)的低階項和首項系數(shù)，用大O符號表述，當(dāng)輸入值大小趨近無窮時的情況。3冒泡排序在哪種情況下性能最好？哪種情況下性能？答：最好情況：元素按關(guān)鍵字有序排列，此時

2、經(jīng)過一趟排序即可完成。比較次數(shù)為n-1次比較，不需移動元素。時間復(fù)雜度為O(n)；最壞情況：待排序按關(guān)鍵字逆序排列，此時，算法的時間復(fù)雜度為O(n2)。二、分析1一棵完全二每小題5分，共15分第6層有8個葉子結(jié)點，該二最少有多少結(jié)點？最多有多少結(jié)點？給出分析過程與結(jié)果。分析：最少結(jié)點個數(shù)：因第6層不滿，當(dāng)結(jié)點個數(shù)最少時，第6層是最后一層， 前5層滿，此時結(jié)點個數(shù)為25-1+8=39個。最多結(jié)點個數(shù)：第6層是倒數(shù)第2層，該二共7層。第6層共有結(jié)點32個，其中8個葉子，24個非葉子。24個非葉子結(jié)點在第7層最多產(chǎn)生48個結(jié)點。此時該二共有結(jié)點26-1+48=111個。2設(shè)圖有n個頂點e條邊，分析采

3、用鄰接矩陣和鄰接表時所需的空間復(fù)雜度。分析：采用鄰接矩陣，需要的空間為n+n2個，因此其空間復(fù)雜度為O(n2)；采用鄰接表圖，需要n+e個時，如果為無空間，因此其，需要n+2e個空間，如果為有向空間復(fù)雜度為O(n+e)。3.在棧的順序結(jié)構(gòu)中，如何區(qū)分?？蘸蜅M？分析：順序判棧S滿：結(jié)構(gòu)一般會實現(xiàn)指定大小，假設(shè)為MAXSIZE.Int IsFull(SeqStack *S) /返回1表示滿；否則返回0if(S->top=MAXSIZE-1) return 1;else return0;判棧S空：Int IsEmpty(SeqStack *S) /返回1表示空；否則返回0if(S->t

4、op=-1) return 1;else return0;三、構(gòu)造結(jié)果每小題5分，共15分1、給出以數(shù)據(jù)序列3，4，6，8，10，12，18結(jié)點的所構(gòu)造的樹，并計算該樹的帶權(quán)路徑長度2.對關(guān)鍵字集合 56，28，13，22，96，17，36，55 構(gòu)造二叉排序樹，并計算等概率情況下查找的平均查找長度。3. 對關(guān)鍵字序列56,33,24,68,97,40,12,85，構(gòu)建初始大根堆。四、編寫算法每小題10分，共30分1.鍵盤輸入N個值，編寫算法要求按照輸入順序依次建立鏈表中各個結(jié)點。尾插法建鏈表。LinkList CreateFromTail()LinkList L,*r,*s; int i;L

5、= (Linklist)malloc(sizeof(Node);L->next=NULL;r=L;for(i=1;i<=N;i+)c=getchar();s=(Node*)malloc(sizeof(Node);s->data=c;r->next=s;r=s；r->next=NULL;2. 已知二采用二叉鏈表存放,要求編寫算法不用遞歸也不用棧，返回二T 的后序序列中的第一個結(jié)點的指針。BiTNode* FirstNRD(BiTree bt)p=bt;while(p!=NULL&& (p->LChild!=NULL| p->RChild!

6、=NULL)if(p->LChild!=NULL) p=p->LChild;elsep=p->RChild;return p;3.構(gòu)建表。voidCreateHash(HashTable ht)int h0,di,hi;輸入一個r，其關(guān)鍵字為K;while(K!=ENDKEY)h0=hash(K);if(hth0.key=NULLKEY) hth0=r;else for(di=1;di<=m-1;di+) hi=(h0+di)%m;if(hthi.key=NULLKEY)hthi=r; break;繼續(xù)輸入一個r，其關(guān)鍵字為K;一：選擇（5）1：把按類型排序編號，并要求

7、進程嚴(yán)格按序申請，這種方法破壞了死鎖四個必要條件中的哪個條件？A互斥條件2：臨界區(qū)是（） A一個進程B 部分分配條件C 不條件D 環(huán)路等待條件B 一種C一段程序區(qū)D3：在段頁式A 需C 至少管理系統(tǒng)中，當(dāng)一次主存兩次主存主存中的一條指令或數(shù)據(jù)時，（）B 需兩次主存D 至少三次主存4：成組鏈法是用于（） A 文件的邏輯組織B 文件的物理組織D 文件的目錄組織方式的？（）C 文件器空閑空間的組織5：以下哪種調(diào)度算法不可能是A 先來先服務(wù)B 最短 CPU 執(zhí)行期優(yōu)先C 最高優(yōu)先權(quán)D 輪轉(zhuǎn)法二：簡答題（30）6：在一個多道程序操作系統(tǒng)中，簡述一個廠 I/O 操作時間的 I/O 請求（比如磁盤文件讀寫）

8、的處理。7：文件共享主要有哪些方法？試比較這些方法。UNIX 如何實現(xiàn)文件保護？8：在請頁式圖。管理中，什么叫快表？為什么要引入快表？畫出具有快表的地址變換機構(gòu)9：進程調(diào)度的功能是什么？調(diào)度算法主要有哪些？UNIX 系統(tǒng)采用什么調(diào)度算法？10：在一個請求頁式管理系統(tǒng)中，進程 P 的地址空間共有 6 頁組成，系統(tǒng)為該進程固定分配 3 個內(nèi)存塊（頁框），且假定其初始狀態(tài)全為空，若采用 LRU 動態(tài)頁面調(diào)入策略，對于如下虛頁中斷次數(shù)。序列：3,2,3,0,3,1,2,3,2,3,5,4，請畫出描述頁面調(diào)入和置換過程，并統(tǒng)計缺頁11：假定某磁盤的旋轉(zhuǎn)速度是每圈 20 毫秒，每個盤面被格式化為 10 個

9、扇區(qū)，現(xiàn)有 10 個記錄的文件放在同一個磁道，如圖，若每讀出一個后要用 4 毫秒進行處理，并需順序處理這些。試回答：1） 處理完這 10 個2） 請給出一種共需多少時間？優(yōu)化分布的方案，使得對這 10 個的處理時間最短，并計算優(yōu)化分布時總的處理時間。（如下圖所示：）三：綜合題（40）1：何謂死鎖定理？請用類 C 語言描述死鎖檢測算法：1）所用數(shù)據(jù)結(jié)構(gòu)；2）處理流程（用詳細(xì)注釋或流程圖說明）。2：在一個操作系統(tǒng)中，設(shè)有三個進程 P1，P2，P3，它們共享一個由 K 個單元的緩沖區(qū)，持續(xù)處理來自輸入設(shè)備的信息。P1 負(fù)責(zé)從輸入設(shè)備讀信息，每讀一條信息，把它存放在緩沖區(qū)；P2 負(fù)責(zé)對緩沖區(qū)中的信息進行，并將結(jié)果也放入緩沖區(qū)；P3 負(fù)責(zé)把結(jié)果打印輸出。假設(shè)一條信息和一個結(jié)果都恰好放在一個單元。請問信號量機制（PV 操作）描述進程P1，P2，P3 正確執(zhí)行的流程。3：假定由一個磁盤組共有 199 個柱面，每個柱面有 16 個磁道，每個磁道被劃分成 8 個扇區(qū)，柱面、磁道、扇區(qū)的編號均從 0 開始?，F(xiàn)有一個 700 個邏輯的文件，邏輯大小與扇區(qū)大小相同，其編號從 0 開始。該文件以順序結(jié)構(gòu)的形式，從磁盤的 1 號柱面，5 磁道，0 扇區(qū)開始存放，試