數(shù)據(jù)結(jié)構(gòu)模擬題(今天練習(xí))

1、數(shù)據(jù)結(jié)構(gòu)模擬卷一、選擇題1下面關(guān)于線性表的敘述錯(cuò)誤的是（ D ）。 (A) 線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間(B) 線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間(C) 線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)(D) 線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)2設(shè)順序循環(huán)隊(duì)列Q0：M-1的頭指針和尾指針分別為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（ D）。012345678 9ABCRF012345678 9CDA BFR（2-8+10）%10=4(A) R-F(B) F-R(C) (R-F+M)M(D) (F-R

2、+M)M3設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ A ）。(A) BADC(B) BCDA(C) CDAB(D) CBDA4設(shè)某完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有（ A）條邊。(A) n(n-1)/2(B) n(n-1)(C) n2 (D) n2-15設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（ C ）。(A) 2，3，5，8，6(B) 3，2，5，8，6 (C) 3，2，5，6，8(D) 2，3，6，5，8二、簡(jiǎn)答題1、 什么是數(shù)據(jù)結(jié)構(gòu)？列舉5種數(shù)據(jù)結(jié)構(gòu)棧，圖，串，隊(duì)列，二叉

3、樹，堆，鏈表，哈希表，數(shù)組，樹2、 鏈?zhǔn)浇Y(jié)構(gòu)有什么優(yōu)缺點(diǎn)？舉例說明鏈?zhǔn)浇Y(jié)構(gòu)有哪些應(yīng)用鏈表，鄰接表，鏈?zhǔn)疥?duì)列，鏈棧，線索二叉樹ARR三、應(yīng)用題1、設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量q指向被插入結(jié)點(diǎn)B，要求給出在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)B的操作序列（設(shè)雙向鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別為llink和rlink）。 q.rlink=p.rlink; p.rlink=q;q.llink=p;q.rlink.llink=q;2、設(shè)有無向圖G（如下圖所示），要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。 (1,3) (2,3) (3,5) (5,6) (4,6)2+3+4+1+1=11 3、設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。 454080224878四、算法設(shè)計(jì)題 1 設(shè)有一組初始記錄關(guān)鍵字序列（K0，K1，Kn-1），要求設(shè)計(jì)一個(gè)算法能夠在O(n)的時(shí)間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個(gè)