數(shù)據(jù)結構期末總復習題

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

2、AabcdeBedcbaCdceabDdecba4棧的特點是_____。A先進先出B先進后出C隨即存取D鏈式實現(xiàn)5一個隊列的入隊順序是1，2，3，4，5，那么出隊順序是_____。A5，4，3，2，1B1，2，3，5，4C1，2，3，4，5D1，3，2，4，56向一個長度為10的數(shù)組的第5個元素之前插入一個元素時，需向后移動_____個元素。A3B5C6D77若一棵二叉樹有101個結點，且無度為1的結點，則葉結點的個數(shù)為_____。A4

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

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

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

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