數(shù)據(jù)結構章節(jié)練習(2020.06.08)

來源：考試資料網(wǎng)

1.填空題單鏈表是（）的鏈接存儲表示。

2.填空題在對11個記錄的序列（12，35，9，7，2，11，56 ，95 ，37，58 ，60）進行直接插入排序時，當把第6個記錄11插入到有序表時，為尋找插入位置，元素間需比較（）次。（由小到大排列）

3.問答題求在等概率下的查找成功和不成功情況下的平均查找長度。

參考答案：ASL_成功=（1×1+2×2+4×3+3×4）/10=29/10。
ASL_不成...

4.問答題有關鍵字序列（16，15，18，16，17，18，20，13），現(xiàn)采用冒泡排序對關鍵字按遞增序排列，請寫出具體過程。

5.問答題假設稱正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’和‘a(chǎn)babab’則不是回文。試寫一個算法判別讀入的一個以‘@’為結束符的字符序列是否是“回文”。

6 一個棧的入棧序列是a，b，c，d，e，則不可能的出棧序列是（）。

7.問答題編號為n的結點的第i個孩子結點如果存在，編號是多少？

參考答案：編號為n的結點的第i個孩子結點如果存在，編號是(n-1)*m+i+1。

8 數(shù)據(jù)結構里，棧是后進先出的線性表，后進先出英文是（）。

9.判斷題二叉樹以后序遍歷序列與前序遍歷序列反映的同樣的信息（他們反映的信息不獨立）。

10.判斷題在索引順序結構的搜索中，對索引表既可以采取順序搜索，也可以采用折半搜索。