數(shù)據(jù)結構試題

時間：2022-09-24 13:10:05 試題我要投稿

相關推薦

數(shù)據(jù)結構試題

　　一、選擇題（30分）

數(shù)據(jù)結構試題

　　1、下列程序段的時間復雜度為（）。

　�。ˋ）O（m*n*t）（B）O（m+n+t）（C）O（m+n*t）（D）O（m*t+n）

　　2、設順序線性表中有n個數(shù)據(jù)元素，則刪除表中第i個元素需要移動（）個元素。

　�。ˋ）n—i（B）n+l—i（C）n—1—i（D）i

　　3、設F是由T1、T2和T3三棵樹組成的森林，與F對應的二叉樹為B，T1、T2和T3的結點數(shù)分別為N1、N2和N3，則二叉樹B的根結點的左子樹的結點數(shù)為（）。

　�。ˋ）N1—1（B）N2—1（C）N2+N3（D）N1+N3

　　4、利用直接插入排序法的思想建立一個有序線性表的時間復雜度為（）。

　�。ˋ）O（n）（B）O（nlog2n）（C）O（n2）（D）O（1og2n）

　　5、設指針變量p指向雙向鏈表中結點A，指針變量s指向插入的結點X，則在結點A的后面插入結點X的操作序列為（）。

　�。ˋ）p—>right=s。s—>left=p。p—>right—>left=s。s—>right=p—>right。

　�。˙）s—>left=p。s—>right=p—>right。p—>right=s。p—>right—>left=s。

　�。–）p—>right=s。p—>right—>left=s。s—>left=p。s—>right=p—>right。

　�。―）s—>left=p。s—>right=p—>right。p—>right—>left=s。p—>right=s。

　　6、下列各種排序算法中平均時間復雜度為O（n2）是（）。

　　（A）快速排序（B）堆排序（C）歸并排序（D）冒泡排序

　　7、設輸入序列1、2、3、…、n經(jīng)過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是（）。

　�。ˋ）n—i（B）n—1—i（C）n+l—i（D）不能確定

　　8、設散列表中有m個存儲單元，散列函數(shù)H（key）=key%p，則p最好選擇（）。

　�。ˋ）小于等于m的最大奇數(shù)（B）小于等于m的最大素數(shù)

　�。–）小于等于m的最大偶數(shù)（D）小于等于m的最大合數(shù)

　　9、設在一棵度數(shù)為3的樹中，度數(shù)為3的結點數(shù)有2個，度數(shù)為2的結點數(shù)有1個，度數(shù)為1的結點數(shù)有2個，那么度數(shù)為0的結點數(shù)有（）個。

　　（A）4（B）5（C）6（D）7

　　10、設完全無向圖中有n個頂點，則該完全無向圖中有（）條邊。

　�。ˋ）n（n—1）/2（B）n（n—1）（C）n（n+1）/2（D）（n—1）/2

　　11、設順序表的長度為n，則順序查找的平均比較次數(shù)為（）。

　�。ˋ）n（B）n/2（C）（n+1）/2（D）（n—1）/2

　　12、設有序表中的元素為（13，18，24，35，47，50，62），則在其中利用二分法查找值為24的元素需要經(jīng)過（）次比較。

　�。ˋ）1（B）2（C）3（D）4

　　13、設順序線性表的長度為30，分成5塊，每塊6個元素，如果采用分塊查找，則其平均查找長度為（）。

　　（A）6（B）11（C）5（D）6、5

　　14、設有向無環(huán)圖G中的有向邊集合E={<1，2>，<2，3>，<3，4>，<1，4>}，則下列屬于該有向圖G的一種拓撲排序序列的是（）。

　�。ˋ）1，2，3，4（B）2，3，4，1（C）1，4，2，3（D）1，2，4，3

　　15、設有一組初始記錄關鍵字序列為（34，76，45，18，26，54，92），則由這組記錄關鍵字生成的二叉排序樹的深度為（）。

　�。ˋ）4（B）5（C）6（D）7

　　二、填空題（30分）

　　1、設指針p指向單鏈表中結點A，指針s指向插入的結點X，則在結點A的前面插入結點X時的操作序列為：

　　1）s—>next=___________。2）p—>next=s。3）t=p—>data。

　　4）p—>data=___________。5）s—>data=t。

　　2、設某棵完全二叉樹中有100個結點，則該二叉樹中有______________個葉子結點。

　　3、設某順序循環(huán)隊列中有m個元素，且規(guī)定隊頭指針F指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當前位置，則該循環(huán)隊列中最多存儲_______隊列元素。

　　4、對一組初始關鍵字序列（40，50，95，20，15，70，60，45，10）進行冒泡排序，則第一趟需要進行相鄰記錄的比較的次數(shù)為__________，在整個排序過程中最多需要進行__________趟排序才可以完成。

　　5、在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應最好選擇_________排序，如果從節(jié)省存儲空間的角度來考慮則最好選擇________排序。

　　6、設一組初始記錄關鍵字序列為（20，12，42，31，18，14，28），則根據(jù)這些記錄關鍵字構造的二叉排序樹的平均查找長度是_______________________________。

　　7、設一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹的前序序列為____________________。

　　8、設用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10，根據(jù)這些頻率作為權值構造哈夫曼樹，則這棵哈夫曼樹的高度為________________。

　　9、設一組記錄關鍵字序列為（80，70，33，65，24，56，48），則用篩選法建成的初始堆為_______________________。

　　10、10、設無向圖G（如右圖所示），則其最小生成樹上所有邊的權值之和為_________________。

　　三、判斷題（20分）

　　1、有向圖的鄰接表和逆鄰接表中表結點的個數(shù)不一定相等。（）

　　2、對鏈表進行插入和刪除操作時不必移動鏈表中結點。（）

　　3、子串“ABC”在主串“AABCABCD”中的位置為2。（）

　　4、若一個葉子結點是某二叉樹的中序遍歷序列的最后一個結點，則它必是該二叉樹的先序遍歷序列中的最后一個結點。（）

　　5、希爾排序算法的時間復雜度為O（n2）。（）

　　6、用鄰接矩陣作為圖的存儲結構時，則其所占用的存儲空間與圖中頂點數(shù)無關而與圖中邊數(shù)有關。（）

　　7、中序遍歷一棵二叉排序樹可以得到一個有序的序列。（）

　　8、入棧操作和入隊列操作在鏈式存儲結構上實現(xiàn)時不需要考慮棧溢出的情況。（）

　　9、順序表查找指的是在順序存儲結構上進行查找。（）

　　10、堆是完全二叉樹，完全二叉樹不一定是堆。（）

　　四、算法設計題（20分）

　　1、設計計算二叉樹中所有結點值之和的算法。

　　2、設計將所有奇數(shù)移到所有偶數(shù)之前的算法。

　　3、設計判斷單鏈表中元素是否是遞增的算法。

【數(shù)據(jù)結構試題】相關文章：

數(shù)據(jù)結構實習心得04-18