數(shù)據(jù)結(jié)構(gòu)與算法-模擬試題1及答案

數(shù)據(jù)結(jié)構(gòu)與算法-模擬試題1一、單項選擇題（每個題只有一個答案是正確的，請將正確的答案填寫到括號內(nèi)。本題共15個小題，每小題3分，共45分）1.算法的時間復雜度是指算法所需要的（）。A.時間資源B.空間資源C.輸入規(guī)模D.輸出結(jié)果2.對線性表，在下列（）情況下應當采用鏈表表示。A.經(jīng)常需要隨機地存取元素B.經(jīng)常需要進行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲空間D.表中元素的個數(shù)不變3.若進棧序列為a,b,c，則通過入出棧操作可能得到的a,b,c的不同排列個數(shù)為（）。A.4B.5C.6D.74.若用一個大小為6的數(shù)組來實現(xiàn)的循環(huán)隊列，且head=3，tail=0。當從隊列中刪除一個元素，再加入兩個元素后，head和tail的值分別為（）。A.1和5 B.2和4 C.4和2 D.5和15.串與普通的線性表相比較，它的特殊性體現(xiàn)在（）。A.順序的存儲結(jié)構(gòu) B.鏈式存儲結(jié)構(gòu) C.數(shù)據(jù)元素是一個字符 D.數(shù)據(jù)元素任意6.廣義表G=(a,(b,c),(a,(b,c),d))的長度為（）。A.2B.3C.7D.47.三個結(jié)點的二叉樹有（）種形態(tài)。A.3B.4C.5D.18.高度為h的二叉樹最多有（）個結(jié)點。A.hB.h*(h+1)C.2h-1D.h-19.n個頂點的有向強連通圖至多有（）條邊。A.n×(n-1)B.n×(n-1)/2C.n-1D.n10.圖進行廣度優(yōu)先搜索時，下列說法錯誤的是（）。A.廣度優(yōu)先搜索后可以得到一個線性的頂點序列B.廣度優(yōu)先搜索過程可以生成廣度優(yōu)先生成樹C.廣度優(yōu)先搜索和深度優(yōu)先搜索得到的頂點序列一定是不同的D.廣度優(yōu)先搜索和深度優(yōu)先搜索都屬于圖的遍歷11.設一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134)，利用順序查找方法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為（）。 A.1 B.5 C.9 D.1012.散列技術(shù)中的沖突指的是（）。A.兩個元素具有相同的序號B.兩個元素的鍵值不同，而其他屬性相同C.數(shù)據(jù)元素過多D.不同鍵值的元素對應于相同的存儲地址13.下列（）排序算法的平均時間復雜度為O(nlog2n)。 A．簡單選擇B.直接插入C.快速D.冒泡14.序列狀態(tài)為（）時，快速排序達到最好的時間復雜度。A.序列基本有序B.序列逆序C.序列正序D.序列無序15.將大問題轉(zhuǎn)化為相互獨立的相同的小問題，然后各個擊破，解決完各個小問題后再合成大問題的解是（）的算法思想。A.遞歸算法B.分治法C.回溯算法D.貪心算法二、判斷題（正確的在括號內(nèi)打上“√”，錯誤的打上“╳”。本題共15個小題，每小題2分，共30分）16.數(shù)據(jù)結(jié)構(gòu)從邏輯結(jié)構(gòu)上可以分為順序結(jié)構(gòu)和鏈式結(jié)構(gòu)。（）17.隊列是后進先出的線性表。（）18.棧只能在棧頂端進行插入刪除。（）19.鏈表是順序存儲結(jié)構(gòu)的線性表。（）20.串的長度不同時不能進行比較。（）21.廣義表可以用來表示樹型結(jié)構(gòu)。（）22.二叉樹遍歷的結(jié)果是一個線性序列。（）23.森林不可以轉(zhuǎn)換為二叉樹。（）24.圖可以只有頂點沒有邊。（）25.連通圖的最小生成樹是唯一的。（）26.平衡二叉樹的左右子樹是等高的。（）27.折半查找中第一個比較的元素是查找序列的第一個元素。（）28.從平均性能看，快速排序是所有基于比較的排序算法中最快的。（）29.待排數(shù)據(jù)量n較大時，要想排序的時間效率高且所用輔助空間少，可以采用堆排序。（）30.一個問題只能由一種算法解決。（）綜合題（本題共5個小題，每題5分，共25分）31.請根據(jù)程序注釋為下面程序中空缺的①和②位置選擇正確的語句。Stackstack=newStack();for(inti=1;i<6;i++)//將1,2,3,4,5添加到棧中，即入棧1,2,3,4,5{stack.①(String.valueOf(i));}outputstack(stack);//遍歷并打印出該棧stack.②();//出棧棧頂元素pushB.popC.peekD.set32.現(xiàn)有葉子權(quán)值序列為（1，2，5，7），則①將其構(gòu)造的哈夫曼樹為（）。②該哈夫曼樹的帶權(quán)路徑長度WPL為（）。A.30B.26C.25D.1533.對如下圖所示的無向連通網(wǎng)圖從頂點a開始用普林姆（Prim）算法構(gòu)造最小生成樹，在構(gòu)造過程中加入最小生成樹的前4條邊依次是（）。A.(a,b)5，(b,e)3，(e,f)2，(f,d)4B.(a,b)5，(b,f)4，(f,e)2，(e,b)4C.(a,b)5，(b,e)3，(b,f)4，(f,e)2D.(e,f)2，(b,e)3，(d,f)4，(b,f)434.按{40，25，18，76，66，87}的順序構(gòu)成的二叉排序樹，其形態(tài)是（）。35.對一組關(guān)鍵字序列{30851578063345}進行簡單選擇排序（每次選擇最小關(guān)鍵字），第一趟掃描排序結(jié)果為①；若對該關(guān)鍵字序列{30851578063345}進行從前向后的冒泡排序，第一趟掃描排序結(jié)果為②。A.06153078853345B.06851578303345C.30157806334585D.15853078063345數(shù)據(jù)結(jié)構(gòu)與算法-模擬試題1-參考答案及評分標準一、單項選擇題（每個題只有一個答案是正確的，請將正確的答案填寫到括號內(nèi)。本題共15個小題，每小題3分，共45分）1A2B3B4C5C6B7C8C9A10C11C12D13C14D15B二、判斷題（正確的在括號內(nèi)打上“√”，錯誤的打上“╳”。本題共15個小題，每小題2分，共30分）16╳17╳18