往年的acm試題及答案VIP

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