春天大數(shù)據(jù)結(jié)構(gòu)在線作業(yè)一

1、數(shù)據(jù)結(jié)構(gòu)在線作業(yè)一 一、單選題（共 40 道試題，共 100 分。）1. 設(shè)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均平均查找長(zhǎng)度為（ ）。. O(1). O(log2n). O(n4). O(n2 )正確答案：2. 對(duì)一個(gè)滿二叉樹(shù)，m個(gè)樹(shù)葉，n個(gè)結(jié)點(diǎn)，深度為h，則（）。. n=h+m. h+m=2n. m=h-1. n=2的h次方-1正確答案：3. 設(shè)一維數(shù)組中有n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為（ ）。. O(n). O(nlog2n). O(1). O(n2 )正確答案：4. 已知某二叉樹(shù)的后序遍歷序列是，中序遍歷序列是，它的前序遍歷序列是（）。. . . . 正確答

2、案：5. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？( ). 隊(duì)列. 棧. 線性表. 二叉樹(shù)正確答案：6. 向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，則執(zhí)行（）。(不帶空的頭結(jié)點(diǎn)). HSnxt=s;. snxt= HSnxt;HSnxt=s;. snxt= HS;HS=s;. snxt= HS;HS= HSnxt;正確答案：7. 設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有（ ）條邊。. n(n-1). n+1. n. n(n+1)正確答案：8. 一個(gè)棧的入棧序列，則棧的不可能的輸出序列是（）。. . . . 正確答案：9. 若已知一個(gè)棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，

3、p3，pn，若p1=n，則pi為（）。. i. n=i. n-i+1. 不確定正確答案：10. 在二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）。. O(1). O(n). O(log2n). O(n2 )正確答案：11. 對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為( ). O（1）. O（n）. O（1og2n）. O（n2）正確答案：12. 設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為( )。. 10，15，14，18，20，36，40，21. 10，15，14，18，20，40，36，21. 1

4、0，15，14，20，18，40，36，2l. 15，10，14，18，20，36，40，21正確答案：13. 一個(gè)隊(duì)列的數(shù)據(jù)入列序列是1，2，3，4，則隊(duì)列的出隊(duì)時(shí)輸出序列是（） 。. 4，3，2，1. 1，2，3，4. 1，4，3，2. 3，2，4，1正確答案：14. 設(shè)哈夫曼樹(shù)中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹(shù)中總共有（ ）個(gè)空指針域。. 2m-1. 2m. 2m+1. 4m正確答案：15. 二維數(shù)組中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址S開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素47的起始地址為（）。. S+141. S

5、+180. S+222. S+225正確答案：16. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。. 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu). 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu). 線性結(jié)構(gòu)和非線性結(jié)構(gòu). 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)正確答案：17. 設(shè)串s1='FG'，s2='PQRST'，函數(shù)on(x,y)返回x和y串的連接串，sus(s,i,j)返回串s的從序號(hào)i的字符開(kāi)始的j個(gè)字符組成的子串，ln(s)返回串s的長(zhǎng)度，則on(sus(s1,2,ln(s2),sus(s1,ln(s2),2)的結(jié)果串是（）。. F. FG. PQRST. FF正確答案：18. 設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（

6、 ）條邊。. n-1. n(n-1)/2. n(n+1)/2. 0正確答案：19. 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作（）。. 連接. 模式匹配. 求子串. 求串長(zhǎng)正確答案：20. 在一棵具有5層的滿二叉樹(shù)中結(jié)點(diǎn)數(shù)為（ ）. 33. 32. 31. 31正確答案：21. 設(shè)一棵二叉樹(shù)的深度為k，則該二叉樹(shù)中最多有（ ）個(gè)結(jié)點(diǎn)。. 2k-1. 2k. 2k-1. 2k -1正確答案：22. 在以下的敘述中，正確的是（）。. 線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu). 線性表的順序存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況. 線性表的鏈表存儲(chǔ)結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況.

7、線性表的鏈表存儲(chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)正確答案：23. 設(shè)串的長(zhǎng)度為n，則它的子串個(gè)數(shù)為（）。. n. n(n+1). n(n+1)/2. n(n+1)/2+1正確答案：24. 哈希表中的沖突可以通過(guò)改變哈希函數(shù)完全避免。. 正確. 錯(cuò)誤正確答案：25. 任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（）。. 不發(fā)生改變. 發(fā)生改變. 不能確定. 以上都不對(duì)正確答案：26. 設(shè)一組初始記錄關(guān)鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進(jìn)行（ ）趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。. 3. 4. 5. 8正確答案：27. 從一個(gè)棧頂指針為HS的

8、鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（）。(不帶空的頭結(jié)點(diǎn)). x=HS;HS= HSnxt;. x=HSt;. HS=HSnxt;x=HSt;. x=HSt;HS= HSnxt;正確答案：28. 若有18個(gè)元素的有序表存放在一維數(shù)組19中，第一個(gè)元素放1中，現(xiàn)進(jìn)行二分查找，則查找3的比較序列的下標(biāo)依次為( ). 1，2，3. 9，5，2，3. 9，5，3. 9，4，2，3正確答案：29. 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)，若刪除單鏈表中結(jié)點(diǎn)，則需要修改指針的操作序列為（ ）。. q=p->nxt；p->t=q->t；p->nxt=q->nxt；fr(q

9、)；. q=p->nxt；q->t=p->t；p->nxt=q->nxt；fr(q)；. q=p->nxt；p->nxt=q->nxt；fr(q)；. q=p->nxt；p->t=q->t；fr(q)正確答案：30. 從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較（）個(gè)結(jié)點(diǎn)。. n. n/2. (n-1)/2. (n+1)/2正確答案：31. 常對(duì)數(shù)組進(jìn)行的兩種基本操作是（）。. 建立與刪除. 索引和修改. 對(duì)數(shù)據(jù)元素的存取和修改. 查找與索引正確答案：32. 對(duì)于線性表（7，34，55，25，

10、64，46，20，10）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個(gè). 1. 2. 3. 4正確答案：33. 假定在一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為（）個(gè)。. 15. 16. 17. 47正確答案：34. 設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)，則該無(wú)向圖的最小生成樹(shù)上有（ ）條邊。. n. n-1. 2n. 2n-1正確答案：35. 某二叉樹(shù)的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是gfh，中序遍歷的結(jié)點(diǎn)訪問(wèn)順序是ghf，則其后序遍歷的結(jié)點(diǎn)訪問(wèn)順序是（）。. gfh. gfh. ghf. ghf正確答案：36. 判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m0）為空的條件是（）。. rr - front= =m0. rr-front-1= =m0. front= = rr. front= = rr+1正確答案：37. 設(shè)順序循環(huán)隊(duì)列Q0：M-1的頭指針和尾指針?lè)謩e為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（ ）。. R-F. F-R. (R-F+M)M. (F-R+M)M正確答案：38. 數(shù)據(jù)結(jié)構(gòu)S(t Strut)可以被形式地定義為S=（，R），其中是（）有限集合，R是上的關(guān)系有限集合。. 算法. 數(shù)據(jù)元素. 數(shù)據(jù)操作