汕頭大學(xué)2021年碩士學(xué)位研究生入學(xué)考試試題計(jì)算機(jī)基礎(chǔ)綜合

汕頭大學(xué)2021年攻讀碩士學(xué)位研究生入學(xué)考試試題科目名稱：計(jì)算機(jī)基礎(chǔ)綜合答案一律寫在答題紙上，答在試題紙上的不得分!請(qǐng)用黑色字跡簽字筆作答，答題要寫清題號(hào)，不必抄原題。第一部分?jǐn)?shù)據(jù)結(jié)構(gòu)(100分)1、數(shù)據(jù)結(jié)構(gòu)中邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)的關(guān)系是什么?2、設(shè)計(jì)一個(gè)“好”的算法應(yīng)考慮達(dá)到哪些目標(biāo)?3、順序表和鏈表分別適用于什么場(chǎng)合?4、隊(duì)列、棧和線性表的區(qū)別與聯(lián)系是什么?5、順序隊(duì)列“假上溢”產(chǎn)生的原因是什么?解決辦法有哪些?6、樹(shù)有哪幾種表示法?樹(shù)的存儲(chǔ)結(jié)構(gòu)有哪幾種?7、一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)有多少個(gè)度為1的結(jié)點(diǎn)?有多少個(gè)分支(非終端)結(jié)點(diǎn)和葉子結(jié)點(diǎn)?該滿二叉樹(shù)的高度為多少?8、哈希表處理沖突的方法有哪些?請(qǐng)列舉其中49、二叉樹(shù)的遍歷方法有哪些?10、什么是關(guān)鍵路徑?舉例說(shuō)明它的實(shí)際應(yīng)二、綜合題(共30分，每題6分)求對(duì)角線元素之和運(yùn)算的優(yōu)缺點(diǎn)。一定是一棵平衡二叉樹(shù)。3、簡(jiǎn)述“拓?fù)渑判颉苯鉀Q問(wèn)題的方法，并例舉實(shí)際問(wèn)題說(shuō)相應(yīng)的Huffiman樹(shù)并給出一個(gè)Huffman編碼方案。5、評(píng)述快速排序和堆排序算法的原理，并討論其時(shí)間復(fù)雜三、算法設(shè)計(jì)(共30分，每題10分)1、已知有一個(gè)單鏈表L,其中可能出現(xiàn)值域重復(fù)的結(jié)點(diǎn)，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法刪除值域重復(fù)的結(jié)點(diǎn)，并分析算法的時(shí)間復(fù)雜度。要求：(1)描述算法基本設(shè)計(jì)思想；(2)采用程序設(shè)計(jì)語(yǔ)言(C、C++或Java)描述算法并給出關(guān)鍵注釋。歸算法求樹(shù)t中度為k的結(jié)點(diǎn)個(gè)數(shù)。要求：(1)描述算法基本設(shè)計(jì)思想；(2)采用程序設(shè)計(jì)語(yǔ)言(C、C++或Java)描述算法并給出關(guān)鍵注釋。中從源點(diǎn)S出發(fā)到圖中其它所有頂點(diǎn)的最長(zhǎng)距離。要求：(1)描述算法基本設(shè)計(jì)思想；(2)采用程序設(shè)計(jì)語(yǔ)言(C、C++或Java)描述算法并給出關(guān)鍵注第二部分操作系統(tǒng)(50分)四、簡(jiǎn)答題(共36分，每題6分)及時(shí)性和交互性。2、簡(jiǎn)述進(jìn)程三狀態(tài)模型中的三種狀態(tài)，并列出它們之間可能的轉(zhuǎn)換關(guān)系。3、簡(jiǎn)述死鎖和死鎖產(chǎn)生的原因。簡(jiǎn)述進(jìn)程資源圖中出現(xiàn)環(huán)路與死鎖的關(guān)系。4、簡(jiǎn)述頁(yè)面替換中的抖動(dòng)現(xiàn)象。寫出FIFO和LRU頁(yè)面替換算法的中文名字。簡(jiǎn)述最佳頁(yè)面替換算法(OPT)的思想。5、簡(jiǎn)述系統(tǒng)調(diào)用與一般過(guò)程調(diào)用的區(qū)別?！輨e表示什么?五、解答題(14分)假設(shè)有5位哲學(xué)家，他們的生活只是思考和吃飯。這些哲學(xué)家共用一個(gè)圓桌，每位都有一把椅子，在桌子中央有一碗米飯，相鄰的兩哲學(xué)家之間放有1根筷子，如圖所示。當(dāng)哲學(xué)家想要吃飯時(shí)，他只有拿到與他相近的兩根筷子才能吃飯。如下為試圖采用信號(hào)量和P、V操作解決同步問(wèn)題的示意代碼。請(qǐng)回答下列問(wèn)題。米飯米飯P(chopstick[i]);//拿左邊的筷子第4頁(yè)共4頁(yè)P(yáng)(chopstick[(i+1)%5]);}1、上述方法存在什么問(wèn)題?(2分)2、請(qǐng)給出兩種解決上述問(wèn)題