數(shù)據(jù)結(jié)構(gòu)期末總復(fù)習(xí)題

1、1套題1一、選擇題（每題一、選擇題（每題2分，共分，共15題，總計(jì)題，總計(jì)30分）分）1以下敘述中正確的是_____。A數(shù)組是數(shù)據(jù)的最小單位B數(shù)據(jù)對(duì)象就是一組數(shù)據(jù)元素的集合C順序存儲(chǔ)方式只能用于存儲(chǔ)線形結(jié)構(gòu)D樹(shù)對(duì)應(yīng)到的二叉樹(shù)其根結(jié)點(diǎn)的右子樹(shù)總是空的2一個(gè)數(shù)組的第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素長(zhǎng)度為2，則第5個(gè)元素的存儲(chǔ)地址是_____。A110B108C100D1203一個(gè)棧的入棧順序是abcde，則其出棧順序不可能是_____。

2、AabcdeBedcbaCdceabDdecba4棧的特點(diǎn)是_____。A先進(jìn)先出B先進(jìn)后出C隨即存取D鏈?zhǔn)綄?shí)現(xiàn)5一個(gè)隊(duì)列的入隊(duì)順序是1，2，3，4，5，那么出隊(duì)順序是_____。A5，4，3，2，1B1，2，3，5，4C1，2，3，4，5D1，3，2，4，56向一個(gè)長(zhǎng)度為10的數(shù)組的第5個(gè)元素之前插入一個(gè)元素時(shí)，需向后移動(dòng)_____個(gè)元素。A3B5C6D77若一棵二叉樹(shù)有101個(gè)結(jié)點(diǎn)，且無(wú)度為1的結(jié)點(diǎn)，則葉結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)____。A4

3、8B49C50D518高度為6的完全二叉樹(shù)中第4層結(jié)點(diǎn)的個(gè)數(shù)為_(kāi)____。A2B4C8D169具有n個(gè)頂點(diǎn)的無(wú)向完全圖，其邊數(shù)為_(kāi)____。AnBn(n1)Cn(n1)2Dn210具有n個(gè)頂點(diǎn)的有向完全圖，其邊數(shù)為_(kāi)____。AnBn(n1)Cn(n1)2Dn211在有7個(gè)頂點(diǎn)的無(wú)向圖中至少有_____條邊才能確保該圖連通。A1B6C7D2112對(duì)于一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示法，則該矩陣的大小是_____。An1BnC(

4、n1)2Dn213在序列1，10，12，15，23，40，66，77，85中利用直接查找，查找15所需的比較次數(shù)為_(kāi)____。A2B3C4D614采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為_(kāi)____。AO(n)BO(nlogn)CO(n2)DO(logn)15在待排序元素基本有序的前提下，效率最高的排序方法是_____。A插入排序B選擇排序C快速排序D歸并排序二、填空題（每空二、填空題（每空2分，共分，共20空，總

5、計(jì)空，總計(jì)40分）分）1判定下列程序段的時(shí)間復(fù)雜度為_(kāi)________________，其中語(yǔ)句A[i][j]頻度為_(kāi)__________________f(i=0ini)f(j=0j=nj)3StatusList_L(LinkLists→next=p→next=returnOKList_L3下圖為一個(gè)無(wú)向圖G，請(qǐng)給出該圖從A出發(fā)的兩個(gè)可能的廣度優(yōu)先遍歷序列①(2分)②(2分)③畫(huà)出該圖的鄰接矩陣表示（4分）四、算法設(shè)計(jì)題（共四、算法設(shè)

6、計(jì)題（共1題，總計(jì)題，總計(jì)1010分）分）設(shè)有兩個(gè)棧S1S2都采用順序棧方式，并且共享一個(gè)存儲(chǔ)區(qū)[O..maxsize1]為了盡量利用空間，減少溢出的可能，可采用棧頂相向，迎面增長(zhǎng)的存儲(chǔ)方式。試設(shè)計(jì)S1S2有關(guān)入棧和出棧的操作算法。套題2一、選擇題（每題一、選擇題（每題2分，共分，共10題，總計(jì)題，總計(jì)20分）分）1一個(gè)數(shù)組的第一個(gè)元素的存儲(chǔ)地址是1000，每個(gè)元素長(zhǎng)度為4，則第4個(gè)元素的存儲(chǔ)地址是_____。A1004B1008C10