傳媒大學(xué)計算機(jī)學(xué)院程序設(shè)計專業(yè)碩士歷年考研真題匯編

傳媒大學(xué)計算機(jī)學(xué)院程序設(shè)計專業(yè)碩士歷年考研真題匯編2013年中國傳媒大學(xué)計算機(jī)學(xué)院827程序設(shè)計[專業(yè)碩士]考研真題程序設(shè)計試題答題說明：答案一律寫在答題紙上，不需抄題，標(biāo)明題號即可，答在試題上無效。一、單項選擇題(每小題2分，共40分)1.若用數(shù)組名作為函數(shù)調(diào)用時的實參，則實際上傳遞給形參的是()。A.數(shù)組的首地址B.數(shù)組的第一個元素值C.數(shù)組中全部元素的值D.數(shù)組元素的個數(shù)2.C語言中函數(shù)返回值的類型由()決定的。A.return語句中的表達(dá)式類型B.調(diào)用該函數(shù)的主調(diào)函數(shù)的類型C.調(diào)用函數(shù)時臨時決定D.定義函數(shù)時所指定的函數(shù)類型3.對一個已排序的具有100萬個數(shù)的數(shù)組采用折半查找法，最多進(jìn)行()次4.假設(shè)已有定義inta[4][8];下面哪條語句是正確的?())類型的變量。A.字符或文件B.整型和枚舉C.共用體或結(jié)構(gòu)體D.實型或指針F(n-2),該遞歸函數(shù)的時間復(fù)雜度是()。8.若某線性表最常用的操作時存取任意指定序號的元素和最后進(jìn)行插入和刪除運(yùn)算，則利用()存儲方式最節(jié)省時間。A.順序表B.雙鏈表C.頭結(jié)點的雙循環(huán)鏈表D.單循環(huán)鏈表9.關(guān)于線索二叉樹，下列說法不正確的是()。A.中序線索二叉樹中，若某結(jié)點有右孩子，則其后繼是它的右子樹的左分支末端結(jié)點B.線索二叉樹利用二叉樹的n+1個空指針來存放其前趨和后繼信息C.在線索二叉樹中，每個結(jié)點通過線索都可以直接找到它的前趨和后繼D.中序線索二叉樹中，若某結(jié)點有左孩子，則其前趨是它的左子樹的右分支末端結(jié)點10.時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為0(nlog2n)的是()。11.含n個頂點的連通圖中任意一條簡單路徑，其長度不可能超過()。12.設(shè)無向圖G中的邊的集合E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},則從頂點a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點序列為13.設(shè)一組初始記錄關(guān)鍵字序列為(345,253,674,924,627),則用基數(shù)排序需要進(jìn)行()趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。14.下述二叉樹中，()從任意結(jié)點出發(fā)到根結(jié)點的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵碼有序。A.完全二叉樹B.平衡二叉樹15.關(guān)于散列查找，下面說法正確的是()。A.散列函數(shù)越復(fù)雜越好，因為這樣隨機(jī)性好，沖突小B.除留余數(shù)法是所有散列函數(shù)中最好的C.不存在特別好與壞的散列函數(shù)，要視情況而定D.若在散列表中刪除一個元素，只要直接將該元素刪除即可16.進(jìn)程和程序的一個本質(zhì)區(qū)別是()。A.前者分時使用CPU,后者獨(dú)占CPUB.前者存儲在內(nèi)存，后者存儲在外存C.前者在一個文件中，后者在多個文件中D.前者為動態(tài)的，后者為靜態(tài)的17.在操作系統(tǒng)中，死鎖出現(xiàn)是指()。A.計算機(jī)系統(tǒng)發(fā)生重大故障C.若干進(jìn)程因競爭資源而無限等待其他進(jìn)程釋放已占有的資源D.進(jìn)程同時申請的資源數(shù)超過資源總數(shù)18.用V操作喚醒一個等待進(jìn)程時，被喚醒進(jìn)程變?yōu)?)狀態(tài)。A.運(yùn)行B.等待C.就緒D.完成19.一個進(jìn)程在獲得資源后，只能在使用完資源后由自己釋放，這屬于死鎖必要條件的()。A.互斥條件B.請求和釋放C.不剝奪條件D.防止系統(tǒng)進(jìn)入不安全狀態(tài)20.在操作系統(tǒng)中，臨界區(qū)是()。A.一個緩沖區(qū)B.一段共享數(shù)據(jù)區(qū)C.一段程序D.一個互斥資源二、綜合應(yīng)用題：(21～30題，共110分)21.(10分)設(shè)計一個高效算法，將順序表的所有元素逆置，要求算法的空間復(fù)雜度為0(1)。22.(10分)有5個元素，其進(jìn)棧次序為A、B、C、D、E,在各種可能的出棧序列中，第一個出棧元素為C且第二個出棧元素為D的出棧序列有哪幾個?23.(15分)試找出分別滿足下面條件的所有二叉樹：(1)前序序列和中序序列相同；(2)中序序列和后序序列相同；(3)前序序列和后序序列相同。24.(10分)用克魯斯卡爾算法求下圖的最小生成樹。(1)寫出各條邊加入生成樹的次序；(2)畫出最終的最小生成樹。25.(15分)證明：若二叉排序樹中的某結(jié)點p有兩個孩子，則結(jié)點p的中序26.(10分)設(shè)散列表為T[0..12],散列函數(shù)為H(key)=keymod13,采用再其中REV(key)表示顛倒10進(jìn)制數(shù)key的各位，如REV(73)=37,REV(7)=7等。將27.(10分)試設(shè)計一個算法，判斷一個數(shù)據(jù)序列是否構(gòu)成一個小根堆。28.(10分)以數(shù)據(jù)集{2,5,7,9,13}為權(quán)值構(gòu)造一棵哈夫曼樹，并計算其既為生產(chǎn)者又為消費(fèi)者。使用P、V操作實現(xiàn)其同步30.(10分)Dijkstra于1965年提出銀行家算法，其主要思想是什么?它能夠用來解決實際中的死鎖問題嗎?為什么?2012年中國傳媒大學(xué)計算機(jī)學(xué)院827程序設(shè)計[專業(yè)碩士]考研真題中國傳媒大學(xué)程序設(shè)計試題答題說明：答案一律寫在答題紙上，不需抄題，標(biāo)明題號即可，答在試題上無效。一、單項選擇題(每小題2分，共40分)則以下不能滿足要求的表達(dá)式是()。不正確的語句是()。3.以下關(guān)于typedef的敘述不正確的是()。D.使用typedef便于程序的通用和移植4.若有如下定義，則對data中的a成員的正確引用是()。structsk{inta;A.*(p).data.aB.(*p).a5.以下關(guān)于文件的說法錯誤的是()。B.文件在讀寫之前必須打開，讀寫結(jié)束必須關(guān)閉C.feof函數(shù)可判斷文件指針是否處于文件結(jié)束位置，如是，則返回值為0,否則寫6.設(shè)某算法完成對n個元素進(jìn)行處理，所需的時間是T(n)=nlog2n+5n2+100n,則該算法的時間復(fù)雜度是()。7.在雙鏈表中pa所指結(jié)點后面插入pb所指結(jié)點，執(zhí)行的語句序列是()。8.設(shè)棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S,一個元素出棧后即進(jìn)入隊列Q,若6個元素出列的順序為E2、E4、E3、E6、E5和E1,則棧S的容量至少應(yīng)該是()。9.有m個葉子結(jié)點的哈夫曼樹所具有的結(jié)點數(shù)為()。10.深度為h(h>0)的滿二叉樹對應(yīng)的森林由()棵樹構(gòu)成。11.在具有n個結(jié)點的二叉鏈表中，共有()個空指針。C.n+1D.不確定12.()的鄰接矩陣是對稱矩陣。A.有向圖B.無向圖13.設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有()條邊才能確保是一個連通圖。14.快速排序的最大遞歸深度是()。15.設(shè)有1000個元素，希望用最快的速度挑選出前5個最大的元素，采用()方法最好。A.快速排序B.堆排序C.希爾排序D.歸并排序16.進(jìn)程有三種基本狀態(tài)，可能的狀態(tài)轉(zhuǎn)換是()。A.就緒態(tài)到運(yùn)行態(tài)、就緒態(tài)到掛起態(tài)、掛起態(tài)到運(yùn)行態(tài)B.就緒態(tài)到運(yùn)行態(tài)、就緒態(tài)到掛起態(tài)、運(yùn)行態(tài)到掛起態(tài)C.就緒態(tài)到等待態(tài)、等待態(tài)到就緒態(tài)、運(yùn)行態(tài)到等待態(tài)D.運(yùn)行態(tài)到就緒態(tài)、等待態(tài)到就緒態(tài)、運(yùn)行態(tài)到等待態(tài)17.在引入線程的操作系統(tǒng)中，資源調(diào)度分配的基本單位和CPU調(diào)度分配的基本單位相應(yīng)地分別為()。B.進(jìn)程和線程D.B.進(jìn)程和線程D.線程和程序C.作業(yè)和線程之一，通過下述()方法破壞了“請求保持”條件。19.一個進(jìn)程被喚醒，意味著()。A.該進(jìn)程重新占有了CPUB.進(jìn)程狀態(tài)變?yōu)榫途w20.一個進(jìn)程可以包含多個線程，各線程()。二、綜合應(yīng)用題(21～30題，共110分)21.(10分)在一個遞增有序的線形表中，有數(shù)值相同的元素存在。若存儲方式為單鏈表，設(shè)計算法去掉數(shù)值相同的元素，使表中不再有重復(fù)的元素。例如(7,10,10,21,30,42,42,42,51,70)將變作(7,10,21,30,42,51,70)。并分析該算法的時間22.(10分)某渡口，過江渡船每次能載10輛車過江。過江車輛分為客車類和貨車類，上渡船有如下規(guī)定：同類車先到先上船；客車先于23.(15分)已知某二叉樹的每個結(jié)點，要么其左、右子樹皆為空，要么其左、右子24.(15分)假設(shè)用于通信的電文由字符集{a,b,c,d,e,f,g}中的字符構(gòu)成，它們在電(1)為這7個字符設(shè)計哈夫曼編碼。(2)使用哈夫曼編碼比使用等長編碼使電文總長壓縮多少?25.(10分)已知下圖是一個無向圖：(1)畫出該無向圖的鄰接矩陣。(2)基于給出的鄰接矩陣，求從頂點A出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。26.(10分)已知關(guān)鍵碼集合為{53,17,19,61,98,75,79,63,46,49},將關(guān)鍵碼集合散(3)計算查找成功時平均查找長度(設(shè)等概率情況)。27.(10分)試設(shè)計一個算法，判斷一個數(shù)據(jù)序列是否構(gòu)成一個小根堆。28.(10分)(1)對n=7,(2)快速排序在什么情況下退化成起泡排序?如何改進(jìn)?29.(10分)假定系統(tǒng)有三個并發(fā)進(jìn)程read,move和print共享緩沖器B1和B2。進(jìn)請用PV操作(亦即wait,signal操作),寫出它們的并發(fā)程序。30.(10分)設(shè)系統(tǒng)中有下述解決死鎖的辦法：(1)銀行家算法。(3)資源預(yù)分配。按"并發(fā)性"從大到小對上述三種辦法進(jìn)行排序。2011年中國傳媒大學(xué)計算機(jī)學(xué)院827程序設(shè)計[專業(yè)碩士]考研真題2011年全國碩士研究生入學(xué)統(tǒng)一考試程序設(shè)計試題一、單項選擇題：1～20小題，每小題2分，共40分。在每小題給出的四個選項1.線性表是具有n個()的有限序列(n>0)。2.有六個元素6,5,4,3,2,13.下列關(guān)于AOE網(wǎng)的敘述中，不正確的是()。4.下列關(guān)于m階B-樹的說法錯誤的是()。A.根結(jié)點至多有m棵子樹C.非葉結(jié)點至少有m/2(m為偶數(shù))或m/2+1(m為奇數(shù))棵子樹5.二維數(shù)組A的每個元素是由6個字符組成的串，其行下標(biāo)的排序方法是()。A.快速排序B.堆排序7.設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1,M2和M3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是()。最小)的數(shù)據(jù)組成索引塊C.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大(或最小)的數(shù)據(jù)組成索引塊D.數(shù)據(jù)分成若干塊，每塊(除最后一塊外)中數(shù)據(jù)個數(shù)需相同A.冒泡排序B.希爾排序C.快速排序D.堆排序11.設(shè)無向圖的頂點個數(shù)為n,則該圖最多有()條邊。12.在下述結(jié)論中，正確的是()。(1)只有一個結(jié)點的二叉樹的度為0;(2)二叉樹的度為2;13.下面()方法可以判斷出一個有向圖是否有環(huán)(回路)。A.(100,85,98,77,80,60,82,40,20,10,B.(100,98,85,82,80,77,66,60,40C.(10,20,40,60,66,77,80D.(100,85,40,77,80,60,66,98,8215.下面關(guān)于算法說法錯誤的是()。A.算法最終必須由計算機(jī)程序?qū)崿F(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C.算法的可行性是指指令不能有二義性D.以上幾個都是錯誤的16.同一程序經(jīng)過多次創(chuàng)建，運(yùn)行在不同的數(shù)據(jù)集上，形成了()的進(jìn)程。A.不同B.相同C.同步D.互斥17.在一個單處理器的系統(tǒng)中，主存中有10個進(jìn)程，那么處于就緒狀態(tài)的進(jìn)程最的進(jìn)程狀態(tài)為()。A.阻塞B.運(yùn)行C.就緒D.不確定19.通常不采用()方法來從死鎖中恢復(fù)。A.終止一個死鎖進(jìn)程B.終止所有的死鎖進(jìn)程C.從死鎖進(jìn)程處搶奪資源D.從非死鎖進(jìn)程處搶奪資源20.銀行家算法是一種死鎖()的算法。A.忽略B.檢測與恢復(fù)C.避免D.預(yù)防二、綜合應(yīng)用題：21～30小題，共110分。(1)畫出這棵二叉樹。(2)畫出這棵二叉樹的后序線索樹。(3)將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹(或森林)。22.(10分)有七個帶權(quán)結(jié)點，其權(quán)值分別為6、7、9、12、10、1、18,試以它們?yōu)槿~子結(jié)點構(gòu)造一棵赫夫曼樹，并計算出帶權(quán)路徑長度WPL。23.(10分)已知一組關(guān)鍵字為(26,36,41,38,44,15,68,12,6,51,25),24.(10分)在設(shè)尾指針(記為rear,其中結(jié)點結(jié)構(gòu)為數(shù)據(jù)域data、指針域next)25.(15分)判定一棵給定的二叉樹是否是完全二叉樹。27.(10分)已知二叉樹中的結(jié)點類型用BinTreeNode表示，被定義為：28.(10分)設(shè)計一個算法，利用順序棧判定一個算術(shù)表達(dá)式中的圓括號是否正29.(10分)假設(shè)在某單CPU系統(tǒng)中有三個合作的循環(huán)進(jìn)程P1、P2、P3,它們的果)?如何采用PV2010年中國傳媒大學(xué)計算機(jī)學(xué)院827程序設(shè)計[專業(yè)碩士]考研真題2010年全國碩士研究生統(tǒng)一入學(xué)考試程序設(shè)計試題寫算法時可選用類C語言、類Pascal、C++、Java語言。一、單項選擇題(1～20小題，每小題2分，共40分。在每小題給出的四個選項中，請選出一項最符合題目要求的)一個操作()。3.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3,當(dāng)從隊列中刪除一個元素，再加入rearfront別為多少?()。4.將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度5.設(shè)結(jié)點x和y是二叉樹中任意的兩個結(jié)點，在該二叉樹的前序遍歷序列中x在y之前，而在其后序遍歷序列中x在y之后，則x和y的關(guān)系是()。A.x是y的左兄弟B.x是y的右兄弟C.x是y的祖先D.x是y的后裔6.對長度為n的有序單鏈表，若搜索每個元素的概率相等，則順序搜索到表中任一元素的平均搜索長度為()。7.算法的時間復(fù)雜度取決于()。A.問題的規(guī)模B.待處理數(shù)據(jù)的初態(tài)8.在n個結(jié)點的順序表，算法的時間復(fù)雜度是0(1)的操作是()。A.訪問第i個結(jié)點(1≤i≤n)和求第i個結(jié)點的直接前驅(qū)(2≤i≤n)B.在第i個結(jié)點后插入一個新結(jié)點(1≤i≤n)C.刪除第i個結(jié)點(1≤i≤n)D.將n個結(jié)點從大到小排序9.棧在()中應(yīng)用。A.遞歸調(diào)用B.子程序調(diào)用C.表達(dá)式求值D.A,B,C10.在平衡二叉樹中，()。A.任意結(jié)點的左、右子樹結(jié)點數(shù)目相同B.任意結(jié)點的左、右子樹高度相同C.任意結(jié)點的左右子樹高度之差的絕對值不大于1D.不存在度為1的結(jié)點11.樹最適合用來表示()。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間無聯(lián)系的數(shù)據(jù)D.元素之間有分支層次關(guān)系12.已知某二叉樹的中序、層序序列為DBAFCE、FDEBCA,則該二叉樹的后序序列13.在一個具有n個頂點的無向圖中，要連通全部頂點至少需要()條邊。14.從理論上講，將數(shù)據(jù)以()結(jié)構(gòu)存放，則查找一個數(shù)據(jù)所用時間不依賴于數(shù)據(jù)個數(shù)n。A.二叉查找樹B.鏈表C.二叉樹D.散列表15.設(shè)有10000個無序元素，希望用最快的速度挑選出其中前10個最大的元素，用()排序方法最好?A.堆排序B.快速排序C.基數(shù)排序D.希爾排序16.下面關(guān)于并發(fā)性的論述中正確的論述是()。A.并發(fā)性是指若干事件在同一時刻發(fā)生B.并發(fā)性是指若干事件在不同時刻發(fā)生C.并發(fā)性是指若干事件在同一時間間隔內(nèi)發(fā)生D.并發(fā)性是指若干事件在不同時間間隔內(nèi)發(fā)生17.在進(jìn)程管理中，當(dāng)(