往年的acm試題及答案

單項(xiàng)選擇題（每題2分，共10題）1.以下哪種排序算法平均時(shí)間復(fù)雜度為O(nlogn)？A.冒泡排序B.選擇排序C.歸并排序D.插入排序2.在圖論中，一個(gè)有n個(gè)頂點(diǎn)的完全圖的邊數(shù)是？A.n(n-1)B.n(n-1)/2C.nD.n23.棧的操作特點(diǎn)是？A.先進(jìn)先出B.先進(jìn)后出C.隨機(jī)進(jìn)出D.只進(jìn)不出4.計(jì)算2的10次方，在C語(yǔ)言中可以表示為？A.2^10B.pow(2,10)C.210D.10^25.線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，其地址？A.必須是連續(xù)的B.部分地址必須連續(xù)C.一定是不連續(xù)的D.連續(xù)與否均可6.一棵深度為5的滿(mǎn)二叉樹(shù)，其節(jié)點(diǎn)總數(shù)為？A.31B.32C.63D.647.快速排序在最好情況下的時(shí)間復(fù)雜度是？A.O(n2)B.O(nlogn)C.O(n)D.O(logn)8.哈希表的平均查找長(zhǎng)度與什么有關(guān)？A.元素個(gè)數(shù)B.哈希函數(shù)C.裝填因子D.以上都是9.以下哪種數(shù)據(jù)結(jié)構(gòu)適合實(shí)現(xiàn)廣度優(yōu)先搜索？A.棧B.隊(duì)列C.樹(shù)D.圖10.已知數(shù)組a[10]，訪(fǎng)問(wèn)數(shù)組元素a[5]，其地址計(jì)算方式為？A.a+5B.&a+5C.a[5]D.a+sizeof(int)5多項(xiàng)選擇題（每題2分，共10題）1.以下屬于動(dòng)態(tài)內(nèi)存分配函數(shù)的有（）A.mallocB.freeC.callocD.realloc2.下列算法中，哪些屬于貪心算法（）A.迪杰斯特拉算法B.普里姆算法C.克魯斯卡爾算法D.弗洛伊德算法3.關(guān)于鏈表的描述，正確的有（）A.插入操作時(shí)間復(fù)雜度O(1)（已知插入位置）B.可以隨機(jī)訪(fǎng)問(wèn)元素C.內(nèi)存空間不一定連續(xù)D.比順序表更節(jié)省內(nèi)存4.常見(jiàn)的圖的存儲(chǔ)結(jié)構(gòu)有（）A.鄰接矩陣B.鄰接表C.十字鏈表D.邊集數(shù)組5.以下哪些是遞歸算法的特點(diǎn)（）A.算法簡(jiǎn)潔B.效率高C.可能導(dǎo)致棧溢出D.易于理解6.排序算法中，穩(wěn)定的排序算法有（）A.冒泡排序B.歸并排序C.插入排序D.希爾排序7.下列關(guān)于棧和隊(duì)列的說(shuō)法，正確的是（）A.棧可以實(shí)現(xiàn)函數(shù)調(diào)用B.隊(duì)列可用于層次遍歷C.棧和隊(duì)列都是線(xiàn)性結(jié)構(gòu)D.棧和隊(duì)列都只能在一端進(jìn)行操作8.關(guān)于哈希表，說(shuō)法正確的有（）A.哈希函數(shù)設(shè)計(jì)越好，沖突越少B.處理沖突的方法有開(kāi)放定址法等C.哈希表查找效率與元素個(gè)數(shù)無(wú)關(guān)D.哈希表存儲(chǔ)元素?zé)o序9.二叉樹(shù)遍歷方式有（）A.前序遍歷B.中序遍歷C.后序遍歷D.層次遍歷10.以下哪些屬于算法的特性（）A.有窮性B.確定性C.可行性D.輸入輸出判斷題（每題2分，共10題）1.順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是存儲(chǔ)密度大，插入、刪除操作效率高。（）2.遞歸算法一定比非遞歸算法效率低。（）3.圖的深度優(yōu)先搜索類(lèi)似于樹(shù)的前序遍歷。（）4.快速排序在最壞情況下時(shí)間復(fù)雜度為O(nlogn)。（）5.線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都可以隨機(jī)訪(fǎng)問(wèn)元素。（）6.一個(gè)有向無(wú)環(huán)圖一定可以進(jìn)行拓?fù)渑判颉＃ǎ?.哈希表查找成功的平均查找長(zhǎng)度與裝填因子有關(guān)。（）8.堆排序是一種不穩(wěn)定的排序算法。（）9.二叉樹(shù)的中序遍歷可以得到一個(gè)有序序列。（）10.算法的空間復(fù)雜度是指算法執(zhí)行過(guò)程中所需要的臨時(shí)存儲(chǔ)空間。（）簡(jiǎn)答題（每題5分，共4題）1.簡(jiǎn)述冒泡排序的基本思想。答案：比較相鄰元素，若順序錯(cuò)誤就把它們交換過(guò)來(lái)。對(duì)每一對(duì)相鄰元素作同樣工作，從開(kāi)始第一對(duì)到結(jié)尾最后一對(duì)，這樣一趟下來(lái)最大元素“浮”到末尾。重復(fù)此過(guò)程，直到整個(gè)數(shù)組有序。2.簡(jiǎn)述棧和隊(duì)列的區(qū)別。答案：棧是先進(jìn)后出，只在棧頂進(jìn)行插入和刪除操作；隊(duì)列是先進(jìn)先出，在隊(duì)尾插入，隊(duì)頭刪除，二者操作特性不同。3.簡(jiǎn)述迪杰斯特拉算法的用途。答案：用于在帶權(quán)有向圖中計(jì)算一個(gè)源點(diǎn)到其他各頂點(diǎn)的最短路徑。通過(guò)不斷選擇當(dāng)前距離源點(diǎn)最近且未確定最短路徑的頂點(diǎn)，更新其鄰接頂點(diǎn)的距離。4.簡(jiǎn)述哈希表處理沖突的開(kāi)放定址法。答案：當(dāng)發(fā)生沖突時(shí)，通過(guò)某種探測(cè)序列在哈希表中尋找下一個(gè)空的哈希地址，將新元素存入。常見(jiàn)探測(cè)序列有線(xiàn)性探測(cè)、二次探測(cè)等。討論題（每題5分，共4題）1.討論在實(shí)際應(yīng)用中，如何選擇合適的排序算法？答案：若數(shù)據(jù)量小且要求穩(wěn)定排序，可選用冒泡、插入排序；數(shù)據(jù)量大且對(duì)穩(wěn)定性無(wú)要求，快速排序較好；若要求最壞情況性能穩(wěn)定，歸并排序合適；數(shù)據(jù)基本有序，插入排序效率高。2.討論圖的鄰接矩陣和鄰接表存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。答案：鄰接矩陣優(yōu)點(diǎn)是直觀、方便判斷邊的存在；缺點(diǎn)是空間浪費(fèi)大，適用于稠密圖。鄰接表優(yōu)點(diǎn)是節(jié)省空間，適合稀疏圖；缺點(diǎn)是判斷邊存在相對(duì)復(fù)雜。3.討論遞歸算法在什么情況下可能導(dǎo)致棧溢出，如何解決？答案：遞歸深度過(guò)大，不斷壓棧導(dǎo)致棧溢出。解決方法有優(yōu)化算法減少遞歸深度，或用棧模擬遞歸過(guò)程（將遞歸改為非遞歸）。4.討論哈希表在數(shù)據(jù)存儲(chǔ)和查找方面的優(yōu)勢(shì)以及面臨的挑戰(zhàn)。答案：優(yōu)勢(shì)是查找效率高，平均時(shí)間復(fù)雜度接近O(1)。挑戰(zhàn)主要是哈希函數(shù)設(shè)計(jì)，若設(shè)計(jì)不好沖突多，影響性能；還有處理沖突的方法選擇，要平衡空間和時(shí)間復(fù)雜度。答案單項(xiàng)選擇題1.C2.B3.B4.B5.D6.A7.B8.D9.B10.A多項(xiàng)選擇題1.ACD2.ABC3.