二、填空題(本大題共13小題，每小題2分，共26分)

請?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。

16.下列程序段的時(shí)間復(fù)雜度為___________。

i=1；

while（i<n）

i=i*2；

17.向一個(gè)長度為n的順序表中第i（1≤i≤n）個(gè)元素之前插入一個(gè)元素時(shí)，需向后移動___________個(gè)元素。

18.在循環(huán)雙鏈表中，刪除最后一個(gè)結(jié)點(diǎn)，其算法的時(shí)間復(fù)雜度為___________。

19.隊(duì)列的插入操作在隊(duì)列的___________部分進(jìn)行。

20.一個(gè)棧的輸入序列是1，2，3，…，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素為___________。

21.一個(gè)10階對稱矩陣A，采用行優(yōu)先順序壓縮存儲下三角，a₀₀為第一個(gè)元素，其存儲地址為1，每個(gè)元素占有1個(gè)存儲地址空間，則a₈₅的地址為___________。

22.設(shè)字符串S=″I□AM□A□STUDENT″（其中□表示空格字符），則S的長度為___________。

23.在樹形結(jié)構(gòu)中，沒有后繼的結(jié)點(diǎn)是___________結(jié)點(diǎn)。

24.一棵深度為n(n>1)的滿二叉樹中共有___________個(gè)結(jié)點(diǎn)。

25.在無向圖中，如果從頂點(diǎn)v到頂點(diǎn)v′有路徑，則稱v和v′是___________。

26.無向完全圖G采用___________存儲結(jié)構(gòu)較省空間。

27.在順序查找、二分查找、索引查找和散列查找四種查找方法中，平均查找長度與元素個(gè)數(shù)沒有關(guān)系的查找方法是___________。

28.快速排序最好情況下的時(shí)間復(fù)雜度為___________。