蘭州大學(xué)23春“計(jì)算機(jī)科學(xué)與技術(shù)”《數(shù)據(jù)結(jié)構(gòu)》考試高頻考點(diǎn)參考題庫答案

長風(fēng)破浪會(huì)有時(shí)，直掛云帆濟(jì)滄海。蘭州大學(xué)23春“計(jì)算機(jī)科學(xué)與技術(shù)”《數(shù)據(jù)結(jié)構(gòu)》考試高頻考點(diǎn)參考題庫帶答案（圖片大小可自由調(diào)整）第I卷一.綜合考核(共15題)1.在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)()。A.數(shù)據(jù)的處理方法B.數(shù)據(jù)元素的類型C.數(shù)據(jù)元素之間的關(guān)系D.數(shù)據(jù)的存儲(chǔ)方法2.對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須()。A.以順序方式存儲(chǔ)B.以鏈接方式存儲(chǔ)C.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序D.以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序3.如果只想得到1000個(gè)元素組成的序列中第5個(gè)最小元素之前的部分排序的序列，用()方法最快。A、起泡排序B、快速排列C、Shell排序D、堆排序E、單單選擇排序4.序列49、38、65、97、76、13、27、49進(jìn)行一趟冒泡排序后的序列為()。A.49、38、65、97、76、13、27、49B.13、27、38、49、49、65、76、97C.38、49、65、76、13、27、49、97D.38、49、65、13、27、49、76、975.數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位。()A.正確B.錯(cuò)誤6.對(duì)于雙向鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共()個(gè)，單鏈表為()個(gè)。A.4，1B.4，2C.1，4D.2，47.中序遍歷的遞歸算法平均空間復(fù)雜度為()。A.2(n)B.n(2)C.0(n)D.2n8.對(duì)于哈希函數(shù)，沖突只能盡可能得少，不可能完全避免。()A.正確B.錯(cuò)誤9.隊(duì)列允許在隊(duì)尾刪除，在隊(duì)頭插入。()A.正確B.錯(cuò)誤10.基數(shù)排序需要進(jìn)行關(guān)鍵字的比較。()A.正確B.錯(cuò)誤11.廣度優(yōu)先遍歷類似于二叉樹的()。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷12.平衡二叉樹的平衡因子只可能是-1、0、1。()A.正確B.錯(cuò)誤13.滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。()A.正確B.錯(cuò)誤14.鄰接表法只能用于有向圖存儲(chǔ)。()A.正確B.錯(cuò)誤15.對(duì)于哈希函數(shù)，沖突只能盡可能的少，不可能完全避免。()A、正確B、錯(cuò)誤第II卷一.綜合考核(共15題)1.非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。()A.正確B.錯(cuò)誤2.單鏈表的結(jié)點(diǎn)包含()和()。A、結(jié)點(diǎn)域，符號(hào)域B、數(shù)據(jù)域，符號(hào)域C、結(jié)點(diǎn)域，指針域D、數(shù)據(jù)域，指針域3.森林的先序遍歷與其對(duì)應(yīng)的二叉樹的中序遍歷對(duì)應(yīng)。()A、正確B、錯(cuò)誤4.冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。()A.正確B.錯(cuò)誤5.設(shè)某完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有()條邊。A.n(n-1)/2B.n(n-1)C.n2D.n2-16.從未排序序列中挑選元素，并將其依次插入已排序序列(初始時(shí)為空)的一端的方法，稱為()。A.希爾排序B.歸并排序C.插入排序D.選擇排序7.分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。()A.正確B.錯(cuò)誤8.數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。()A.正確B.錯(cuò)誤9.二叉排序樹上左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值。()A.正確B.錯(cuò)誤10.在對(duì)含n個(gè)結(jié)點(diǎn)的二叉樹進(jìn)行先序、中序和后序遍歷時(shí)，其時(shí)間復(fù)雜度()。A.都不相同B.完全相同C.先序和中序相同，而與后序不同D.中序和后序相同，而與先序不同11.線性表的唯一存儲(chǔ)形式就是鏈表。()A.正確B.錯(cuò)誤12.如何知道循環(huán)隊(duì)列是空還是滿?13.設(shè)有一棵算術(shù)表達(dá)式樹，用什么方法可以對(duì)該樹所表示的表達(dá)式求值?14.對(duì)n個(gè)不同的排序碼進(jìn)行冒泡排序，在下列哪種情況下比較的次數(shù)最多()。A、從小到大排列好的B、從大到小排列好的C、元素?zé)o序D、元素基本有序15.寫出二叉樹進(jìn)行前序和中續(xù)遍歷的過程。第I卷參考答案一.綜合考核1.參考答案：C2.參考答案：C3.參考答案：D4.參考答案：C5.參考答案：A6.參考答案：B7.參考答案：C8.參考答案：A9.參考答案：A10.參考答案：B11.參考答案：D12.參考答案：A13.參考答案：A14.參考答案：B15.參考答案：A第II卷參考答案一.綜合考核1.參考答案：A2.參考答案：D3.參考答案：A4.參考答案：A5.參考答案：A6.參考答案：D7.參考答案：A8.參考答案：A9.參考答案：A10.參考答案：B11.參考答案：A12.參考答案：采用循環(huán)隊(duì)列是解決假溢出的途徑。另外，解決隊(duì)滿隊(duì)空的辦法有三：(1)設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空；(2)浪費(fèi)一個(gè)元素的空間，用于區(qū)別隊(duì)滿還是隊(duì)空；(3)使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)(即隊(duì)列長度)。我們常采用方法(2)，即隊(duì)頭指針、隊(duì)尾指針中有一個(gè)指向?qū)嵲兀硪粋€(gè)指向空閑元素。判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是：f=rear；隊(duì)滿標(biāo)志是：f=(r+1)%N13.參考答案：方法有二。一是對(duì)該算術(shù)表達(dá)式(二叉樹)進(jìn)行后序遍歷，得到表達(dá)式的后序遍歷序列，再按后綴表達(dá)式求值；二是遞歸求出左子樹表達(dá)式的值，再遞歸求出右子樹