數(shù)據(jù)結(jié)構(gòu)試題及答案(免費(fèi))

1、數(shù)據(jù)結(jié)構(gòu)試卷（十一）一、選擇題(30分)1設(shè)某無向圖有n個(gè)頂點(diǎn)，則該無向圖的鄰接表中有（ ）個(gè)表頭結(jié)點(diǎn)。(A) 2n(B) n(C) n/2(D) n(n-1)2設(shè)無向圖G中有n個(gè)頂點(diǎn)，則該無向圖的最小生成樹上有（ ）條邊。(A) n(B) n-1(C) 2n(D) 2n-13設(shè)一組初始記錄關(guān)鍵字序列為(60，80，55，40，42，85)，則以第一個(gè)關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是（ ）。(A) 40，42，60，55，80，85(B) 42，45，55，60，85，80(C) 42，40，55，60，80，85(D) 42，40，60，85，55，804（ ）二叉排序樹可以得到一

2、個(gè)從小到大的有序序列。(A) 先序遍歷(B) 中序遍歷(C) 后序遍歷(D) 層次遍歷5設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進(jìn)行順序編號，則編號為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號為（ ）。(A) 2i+1(B) 2i(C) i/2(D) 2i-16程序段s=i=0；do i=i+1； s=s+i；while(inext=0(C) head-next=head(D) head!=08設(shè)某棵二叉樹的高度為10，則該二叉樹上葉子結(jié)點(diǎn)最多有（ ）。(A) 20(B) 256(C) 512(D) 10249設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，1

3、34),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為（ ）。(A) 1(B) 2(C) 3(D) 410.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（ ）。(A) top=top+1;(B) top=top-1;(C) top-next=top;(D) top=top-next;二、判斷題(20分)1不論是入隊(duì)列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。（ ）2當(dāng)向二叉排序樹中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。（ ）3設(shè)某堆中有n個(gè)結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(log2n)。（ ）4完全二叉樹中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。

4、（ ）5哈夫曼樹中沒有度數(shù)為1的結(jié)點(diǎn)。（ ）6對連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點(diǎn)。（ ）7先序遍歷一棵二叉排序樹得到的結(jié)點(diǎn)序列不一定是有序的序列。（ ）8由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（ ）9線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。（ ）10.帶權(quán)無向圖的最小生成樹是唯一的。（ ）三、填空題(30分)1. 1. 設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為_=p；s-right=p-right；_=s； p-right-left=s；（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為left和right）。2. 2.

5、設(shè)完全有向圖中有n個(gè)頂點(diǎn)，則該完全有向圖中共有_條有向條；設(shè)完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中共有_條無向邊。3. 3. 設(shè)關(guān)鍵字序列為(Kl，K2，Kn)，則用篩選法建初始堆必須從第_個(gè)元素開始進(jìn)行篩選。4. 4. 解決散列表沖突的兩種方法是_和_。5. 5. 設(shè)一棵三叉樹中有50個(gè)度數(shù)為0的結(jié)點(diǎn)，21個(gè)度數(shù)為2的結(jié)點(diǎn)，則該二叉樹中度數(shù)為3的結(jié)點(diǎn)數(shù)有_個(gè)。6. 6. 高度為h的完全二叉樹中最少有_個(gè)結(jié)點(diǎn)，最多有_個(gè)結(jié)點(diǎn)。7. 7. 設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是_。8. 8. 設(shè)有一組初始關(guān)鍵字序列為(24，35，1

6、2，27，18，26)，則第3趟簡單選擇排序結(jié)束后的結(jié)果的是_。9. 9. 設(shè)一棵二叉樹的前序序列為ABC，則有_種不同的二叉樹可以得到這種序列。10. 10. 下面程序段的功能是實(shí)現(xiàn)一趟快速排序，請?jiān)谙聞澗€處填上正確的語句。struct record int key;datatype others;void quickpass(struct record r, int s, int t, int &i) int j=t; struct record x=rs; i=s; while(ij) while (ix.key) j=j-1; if (ij) ri=rj;i=i+1; while (_

7、) i=i+1; if (ileft=p，p-right2. 2. n(n-1)，n(n-1)/23. 3. n/24. 4. 開放定址法，鏈地址法5. 5. 146. 6. 2h-1，2h-17. 7. (12，24，35，27，18，26)8. 8. (12，18，24，27，35，26)9. 9. 510. 10. ij & ri.keynext=0) return; for(q=head; q!=0;q=q-next) min=q-data; s=q; for(p=q-next; p!=0;p=p-next) if(minp-data)min=p-data; s=p; if(s!=q)

8、t=s-data; s-data=q-data; q-data=t; 2. 2. 設(shè)計(jì)在順序存儲結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。void substring(char s , long start, long count, char t ) long i,j,length=strlen(s); if (startlength) printf(The copy position is wrong); else if (start+count-1length) printf(Too characters to be copied);else for(i=start-1,j=0; ikey=x) return

9、; else if (bt-keyx) level(bt-lchild,x); else level(bt-rchild,x);數(shù)據(jù)結(jié)構(gòu)試卷（十二）一、選擇題(30分)1. 1. 字符串的長度是指（ ）。(A) 串中不同字符的個(gè)數(shù)(B) 串中不同字母的個(gè)數(shù)(C) 串中所含字符的個(gè)數(shù)(D) 串中不同數(shù)字的個(gè)數(shù)2. 2. 建立一個(gè)長度為n的有序單鏈表的時(shí)間復(fù)雜度為（ ）(A) O(n)(B) O(1)(C) O(n2)(D) O(log2n)3. 3. 兩個(gè)字符串相等的充要條件是（ ）。(A) 兩個(gè)字符串的長度相等(B) 兩個(gè)字符串中對應(yīng)位置上的字符相等(C) 同時(shí)具備(A)和(B)兩個(gè)條件(D)

10、 以上答案都不對4. 4. 設(shè)某散列表的長度為100，散列函數(shù)H(k)=k % P，則P通常情況下最好選擇（ ）。(A) 99(B) 97(C) 91(D) 935. 5. 在二叉排序樹中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為（ ）。(A) O(n)(B) O(1og2n)(C) O(nlog2n)(D) O(n2)6. 6. 設(shè)一個(gè)順序有序表A1:14中有14個(gè)元素，則采用二分法查找元素A4的過程中比較元素的順序?yàn)? )。(A) A1，A2，A3，A4(B) A1，A14，A7，A4(C) A7，A3，A5，A4(D) A7，A5 ，A3，A47. 7. 設(shè)一棵完全二叉樹中有65個(gè)結(jié)點(diǎn)，則該完全

11、二叉樹的深度為（ ）。(A) 8(B) 7(C) 6(D) 58. 8. 設(shè)一棵三叉樹中有2個(gè)度數(shù)為1的結(jié)點(diǎn)，2個(gè)度數(shù)為2的結(jié)點(diǎn)，2個(gè)度數(shù)為3的結(jié)點(diǎn)，則該三叉鏈權(quán)中有（ ）個(gè)度數(shù)為0的結(jié)點(diǎn)。(A) 5(B) 6(C) 7(D) 89. 9. 設(shè)無向圖G中的邊的集合E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（ ）。(A) aedfcb(B) acfebd(C) aebcfd(D) aedfbc10. 10. 隊(duì)列是一種（ ）的線性表。(A) 先進(jìn)先出(B) 先進(jìn)后出(C) 只能插入(D) 只能刪除

12、 二、判斷題(20分)1. 1. 如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個(gè)關(guān)鍵字為同義詞。（ ）2. 2. 設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時(shí)間復(fù)雜度為O(nlog2n)。（ ）3. 3. 分塊查找的基本思想是首先在索引表中進(jìn)行查找，以便確定給定的關(guān)鍵字可能存在的塊號，然后再在相應(yīng)的塊內(nèi)進(jìn)行順序查找。（ ）4. 4. 二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。（ ）5. 5. 向二叉排序樹中插入一個(gè)結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹的高度。（ ）6. 6. 如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。（ ）7. 7. 非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指

13、針均不為空。（ ）8. 8. 不論線性表采用順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，刪除值為X的結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(n)。（ ）9. 9. 圖的深度優(yōu)先遍歷算法中需要設(shè)置一個(gè)標(biāo)志數(shù)組，以便區(qū)分圖中的每個(gè)頂點(diǎn)是否被訪問過。（ ）10. 10. 稀疏矩陣的壓縮存儲可以用一個(gè)三元組表來表示稀疏矩陣中的非0元素。（ ）三、填空題(30分)1 1 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為_。2 2 下面程序段的功能是實(shí)現(xiàn)在二叉排序樹中插入一個(gè)新結(jié)點(diǎn)，請?jiān)谙聞澗€處填上正確的內(nèi)容。typedef struct nodeint dat

14、a;struct node *lchild;struct node *rchild;bitree;void bstinsert(bitree *&t,int k)if (t=0 ) _;t-data=k;t-lchild=t-rchild=0;else if (t-datak) bstinsert(t-lchild,k);else_;3 3 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X需要執(zhí)行的語句序列：s-next=p-next; _;。4 4 設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量p指向雙向鏈表中的第一個(gè)結(jié)點(diǎn)，則指針變量p和指針變量h

15、ead之間的關(guān)系是p=_和head=_（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink）。5 5 設(shè)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為_。6 6 完全二叉樹中第5層上最少有_個(gè)結(jié)點(diǎn)，最多有_個(gè)結(jié)點(diǎn)。7 7 設(shè)有向圖中不存在有向邊，則其對應(yīng)的鄰接矩陣A中的數(shù)組元素Aij的值等于_。8 8 設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則第4趟直接選擇排序結(jié)束后的結(jié)果為_。9 9 設(shè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則對應(yīng)的最小生成樹上有_條邊。10 10 設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73

16、)，則將它們調(diào)整成初始堆只需把16與_相互交換即可。四、算法設(shè)計(jì)題(20分)1. 1. 設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)的算法。2. 2. 設(shè)計(jì)一個(gè)算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法。數(shù)據(jù)結(jié)構(gòu)試卷（12）參考答案一、選擇題1C2C3C4B5B6C7B8C9A10A二、判斷題1對2錯(cuò)3對4錯(cuò)5錯(cuò)6對7對8對9對10對三、填空題1. 1. (49，13，27，50，76，38，65，97)2. 2. t=(bitree *)malloc(sizeof(bitree)，bstinsert(t-rchild,k)3. 3. p-next=s4. 4. head-rlink，p-ll

17、ink5. 5. CABD6. 6. 1，167. 7. 08. 8. (13，27，38，50，76，49，65，97)9. 9. n-110. 10. 50四、算法設(shè)計(jì)題1. 1. 設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上統(tǒng)計(jì)二叉樹中結(jié)點(diǎn)個(gè)數(shù)的算法。void countnode(bitree *bt,int &count) if(bt!=0) count+; countnode(bt-lchild,count); countnode(bt-rchild,count);2. 2. 設(shè)計(jì)一個(gè)算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法。typedef struct int vertexm; int edgemm

18、;gadjmatrix;typedef struct node1int info;int adjvertex; struct node1 *nextarc;glinklistnode;typedef struct node2int vertexinfo;glinklistnode *firstarc;glinkheadnode;void adjmatrixtoadjlist(gadjmatrix g1 ,glinkheadnode g2 )int i,j; glinklistnode *p;for(i=0;i=n-1;i+) g2i.firstarc=0;for(i=0;i=n-1;i+) f

19、or(j=0;jadjvertex=j;p-nextarc=gi.firstarc; gi.firstarc=p;p=(glinklistnode *)malloc(sizeof(glinklistnode);p-adjvertex=i;p-nextarc=gj.firstarc; gj.firstarc=p;數(shù)據(jù)結(jié)構(gòu)試卷（13）一、選擇題(30分)1下列程序段的時(shí)間復(fù)雜度為（ ）。for(i=0； im； i+) for(j=0； jt； j+) cij=0；for(i=0； im； i+) for(j=0； jt； j+) for(k=0； kright=s； s-left=p； p-ri

20、ght-left=s； s-right=p-right；(B) s-left=p；s-right=p-right；p-right=s； p-right-left=s；(C) p-right=s； p-right-left=s； s-left=p； s-right=p-right；(D) s-left=p；s-right=p-right；p-right-left=s； p-right=s；6下列各種排序算法中平均時(shí)間復(fù)雜度為O(n2)是（ ）。(A) 快速排序(B) 堆排序(C) 歸并排序(D) 冒泡排序7設(shè)輸入序列1、2、3、n經(jīng)過棧作用后，輸出序列中的第一個(gè)元素是n，則輸出序列中的第i個(gè)輸出

21、元素是（ ）。(A) n-i(B) n-1-i(C) n+l -i(D) 不能確定8設(shè)散列表中有m個(gè)存儲單元，散列函數(shù)H(key)= key % p，則p最好選擇（ ）。(A) 小于等于m的最大奇數(shù)(B) 小于等于m的最大素?cái)?shù)(C) 小于等于m的最大偶數(shù)(D) 小于等于m的最大合數(shù)9設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè)，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有（ ）個(gè)。(A) 4(B) 5(C) 6(D) 710.設(shè)完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有（ ）條邊。 (A) n(n-1)/2(B) n(n-1)(C) n(n+1)/2(D) (n-1

22、)/211.設(shè)順序表的長度為n，則順序查找的平均比較次數(shù)為（ ）。(A) n(B) n/2(C) (n+1)/2(D) (n-1)/212.設(shè)有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過（ ）次比較。(A) 1(B) 2(C) 3(D) 413.設(shè)順序線性表的長度為30，分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查找長度為（ ）。(A) 6(B) 11(C) 5(D) 6.514.設(shè)有向無環(huán)圖G中的有向邊集合E=，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵?）。(A) 1，2，3，4(B) 2，3，4，1(C) 1，4，2

23、，3(D) 1，2，4，315.設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為（ ）。(A) 4(B) 5(C) 6(D) 7二、填空題(30分)1 1 設(shè)指針p指向單鏈表中結(jié)點(diǎn)A，指針s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的前面插入結(jié)點(diǎn)X時(shí)的操作序列為：1) s-next=_；2) p-next=s；3) t=p-data；4) p-data=_；5) s-data=t；2 2 設(shè)某棵完全二叉樹中有100個(gè)結(jié)點(diǎn)，則該二叉樹中有_個(gè)葉子結(jié)點(diǎn)。3 3 設(shè)某順序循環(huán)隊(duì)列中有m個(gè)元素，且規(guī)定隊(duì)頭指針F指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針R

24、指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中最多存儲_隊(duì)列元素。4 4 對一組初始關(guān)鍵字序列（40，50，95，20，15，70，60，45，10）進(jìn)行冒泡排序，則第一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為_，在整個(gè)排序過程中最多需要進(jìn)行_趟排序才可以完成。5 5 在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應(yīng)最好選擇_排序，如果從節(jié)省存儲空間的角度來考慮則最好選擇_排序。6 6 設(shè)一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長度是_。7 7 設(shè)一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉

25、樹的前序序列為_。8 8 設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10，根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹，則這棵哈夫曼樹的高度為_。9 9 設(shè)一組記錄關(guān)鍵字序列為(80，70，33，65，24，56，48)，則用篩選法建成的初始堆為_。10 10 設(shè)無向圖G（如右圖所示），則其最小生成樹上所有邊的權(quán)值之和為_。三、判斷題(20分)1 1 有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不一定相等。( )2 2 對鏈表進(jìn)行插入和刪除操作時(shí)不必移動鏈表中結(jié)點(diǎn)。( )3 3 子串“ABC”在主串“AABCABCD”中的位置為2。( )4 4 若一個(gè)葉子結(jié)

26、點(diǎn)是某二叉樹的中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的先序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。( )5 5 希爾排序算法的時(shí)間復(fù)雜度為O(n2)。( )6 6 用鄰接矩陣作為圖的存儲結(jié)構(gòu)時(shí)，則其所占用的存儲空間與圖中頂點(diǎn)數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。( )7 7 中序遍歷一棵二叉排序樹可以得到一個(gè)有序的序列。( )8 8 入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。( )9 9 順序表查找指的是在順序存儲結(jié)構(gòu)上進(jìn)行查找。（ ）10 10堆是完全二叉樹，完全二叉樹不一定是堆。（ ）五、算法設(shè)計(jì)題(20分)1 1 設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。2 2 設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)

27、之前的算法。3 3 設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。數(shù)據(jù)結(jié)構(gòu)試卷（13）參考答案一、選擇題1A2A3A4C5D6D7C8B9C10A11C12C13D14A15A二、填空題1. 1. p-next，s-data2. 2. 503. 3. m-14. 4. 6，85. 5. 快速，堆6. 6. 19/77. 7. CBDA8. 8. 69. 9. (24，65，33，80，70，56，48)10. 10. 8三、判斷題1錯(cuò)2對3對4對5錯(cuò)6錯(cuò)7對8對9錯(cuò)10對四、算法設(shè)計(jì)題1 1 設(shè)計(jì)計(jì)算二叉樹中所有結(jié)點(diǎn)值之和的算法。void sum(bitree *bt,int &s) if(bt!=0

28、) s=s+bt-data; sum(bt-lchild,s); sum(bt-rchild,s);2 2 設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。void quickpass(int r, int s, int t) int i=s,j=t,x=rs; while(ij) while (ij & rj%2=0) j=j-1; if (ij) ri=rj;i=i+1; while (ij & ri%2=1) i=i+1; if (inext=0) return(1);elsefor(q=head,p=head-next; p!=0; q=p,p=p-next)if(q-datap-data) r

29、eturn(0);return(1);數(shù)據(jù)結(jié)構(gòu)試卷（十四）一、選擇題(24分)1下列程序段的時(shí)間復(fù)雜度為（ ）。i=0，s=0； while (snext=p-next；p-next=-s；(B) q-next=s； s-next=p；(C) p-next=s-next；s-next=p；(D) p-next=s；s-next=q；4設(shè)輸入序列為1、2、3、4、5、6，則通過棧的作用后可以得到的輸出序列為（ ）。(A) 5，3，4，6，1，2(B) 3，2，5，6，4，1(C) 3，1，2，5，4，6(D) 1，5，4，6，2，35設(shè)有一個(gè)10階的下三角矩陣A（包括對角線），按照從上到下、從左

30、到右的順序存儲到連續(xù)的55個(gè)存儲單元中，每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲空間，則A54地址與A00的地址之差為（ ）。(A) 10(B) 19(C) 28(D) 556設(shè)一棵m叉樹中有N1個(gè)度數(shù)為1的結(jié)點(diǎn)，N2個(gè)度數(shù)為2的結(jié)點(diǎn)，Nm個(gè)度數(shù)為m的結(jié)點(diǎn)，則該樹中共有（ ）個(gè)葉子結(jié)點(diǎn)。(A) (B) (C) (D) 7. 二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均（ ）根結(jié)點(diǎn)的值。(A) (C) =(D) !=8. 設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為（ ）。(A) 129(B) 219(C) 189(D) 2299.

31、 設(shè)有n個(gè)關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個(gè)關(guān)鍵字映射到HASH表中需要做（ ）次線性探測。(A) n2 (B) n(n+1)(C) n(n+1)/2(D) n(n-1)/210.設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有（ ）個(gè)結(jié)點(diǎn)。(A) 2n(B) n+l(C) 2n-1(D) 2n+l 11.設(shè)一組初始記錄關(guān)鍵字的長度為8，則最多經(jīng)過（ ）趟插入排序可以得到有序序列。(A) 6(B) 7(C) 8(D) 912.設(shè)一組初始記錄關(guān)鍵字序列為(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)

32、果是（ ）。(A) F，H，C，D，P，A，M，Q，R，S，Y，X(B) P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y(C) A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X(D) H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y二、填空題(48分，其中最后兩小題各6分)1. 1. 設(shè)需要對5個(gè)不同的記錄關(guān)鍵字進(jìn)行排序，則至少需要比較_次，至多需要比較_次。2. 2. 快速排序算法的平均時(shí)間復(fù)雜度為_，直接插入排序算法的平均時(shí)間復(fù)雜度為_。3. 3. 設(shè)二叉排序樹的高度為h，則在該樹中查找關(guān)鍵字key最多需要比較_次。4. 4. 設(shè)在長度為20的有序表中進(jìn)行二分查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)有

33、_個(gè)，比較兩次查找成功有結(jié)點(diǎn)數(shù)有_個(gè)。5. 5. 設(shè)一棵m叉樹脂的結(jié)點(diǎn)數(shù)為n，用多重鏈表表示其存儲結(jié)構(gòu)，則該樹中有_個(gè)空指針域。6. 6. 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的語句序列為：q=p-next；p-data=q-data；p-next=_；feee(q)；7. 7. 數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：_、_和_。8. 8. 設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，則用鄰接矩陣作為圖的存儲結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷時(shí)的時(shí)間復(fù)雜度為_；用鄰接表作為圖的存儲結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷的時(shí)間復(fù)雜度為_。9. 9. 設(shè)散列表的長度為8，散列函數(shù)H(k)=k % 7，用線性探測法解決

34、沖突，則根據(jù)一組初始關(guān)鍵字序列(8，15，16，22，30，32)構(gòu)造出的散列表的平均查找長度是_。10. 10. 設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟冒泡排序結(jié)束后的結(jié)果為_。11. 11. 設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡單選擇排序后的結(jié)果為_。12. 12. 設(shè)有向圖G中的有向邊的集合E=，則該圖的一個(gè)拓?fù)湫蛄袨開。13. 13. 下面程序段的功能是建立二叉樹的算法，請?jiān)谙聞澗€處填上正確的內(nèi)容。typedef struct nodeint data;struct node *lchild;_;bitre

35、e;void createbitree(bitree *&bt)scanf(“%c”,&ch);if(ch=#) _;else bt=(bitree*)malloc(sizeof(bitree); bt-data=ch; _;createbitree(bt-rchild);14. 14. 下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請?jiān)谙聞澗€處填上正確的內(nèi)容。typedef struct node int data; struct node *next; lklist; void lklistcreate(_ *&head ) for (i=1;idata);p-next=0;if

36、(i=1)head=q=p;else q-next=p;_; 三、算法設(shè)計(jì)題(22分)1 1 設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。2 2 設(shè)計(jì)在二叉排序樹上查找結(jié)點(diǎn)X的算法。3 3 設(shè)關(guān)鍵字序列(k1，k2，kn-1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k1，k2，kn-1，x)調(diào)整為堆。數(shù)據(jù)結(jié)構(gòu)試卷（14）參考答案一、選擇題1A2D3B4B5B6D7A8D9D10C11B12D二、填空題1. 1. 4，102. 2. O(nlog2n)，O(n2)3. 3. n4. 4. 1，25. 5. n(m-1)+16. 6. q-next7. 7. 線性結(jié)構(gòu)，樹型結(jié)構(gòu)，圖型結(jié)構(gòu)8. 8. O(n2)， O(

37、n+e)9. 9. 8/310. 10. (38，13，27，10，65，76，97)11. 11. (10，13，27，76，65，97，38)12. 12. 12465313. 13. struct node *rchild，bt=0，createbitree(bt-lchild)14. 14. lklist，q=p三、算法設(shè)計(jì)題1. 1. 設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。void mergelklist(lklist *ha,lklist *hb,lklist *&hc) lklist *s=hc=0; while(ha!=0 & hb!=0) if(ha-datadata)if(s

38、=0) hc=s=ha; else s-next=ha; s=ha;ha=ha-next; else if(s=0) hc=s=hb; else s-next=hb; s=hb;hb=hb-next; if(ha=0) s-next=hb; else s-next=ha;2. 2. 設(shè)計(jì)在二叉排序樹上查找結(jié)點(diǎn)X的算法。bitree *bstsearch1(bitree *t, int key) bitree *p=t; while(p!=0) if (p-key=key) return(p);else if (p-keykey)p=p-lchild; else p=p-rchild; retu

39、rn(0);3. 3. 設(shè)關(guān)鍵字序列(k1，k2，kn-1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k1，k2，kn-1，x)調(diào)整為堆。void adjustheap(int r ,int n) int j=n,i=j/2,temp=rj-1; while (i=1) if (temp=ri-1)break; elserj-1=ri-1; j=i; i=i/2; rj-1=temp;數(shù)據(jù)結(jié)構(gòu)（十五）一、 單選題（每題 2 分，共20分）1. 1. 對一個(gè)算法的評價(jià)，不包括如下（B ）方面的內(nèi)容。 A健壯性和可讀性 B并行性 C正確性 D時(shí)空復(fù)雜度2. 2. 在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指

40、針p指向的結(jié)點(diǎn)，則執(zhí)行( )。 A. p-next=HL-next; HL-next=p; B. p-next=HL; HL=p; C. p-next=HL; p=HL; D. HL=p; p-next=HL;3. 3. 對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？( ) A.經(jīng)常需要隨機(jī)地存取元素 B.經(jīng)常需要進(jìn)行插入和刪除操作 C.表中元素需要占據(jù)一片連續(xù)的存儲空間 D.表中元素的個(gè)數(shù)不變4. 4. 一個(gè)棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( C ) A. 2 3 1B. 3 2 1 C. 3 1 2 D. 1 2 35. 5. AOV網(wǎng)是一種（ ）。 A有向圖 B無向圖 C無向無環(huán)圖 D有向無環(huán)圖6. 6. 采用開放定址法處理散列表的沖突時(shí)，其平均查找長度（ ）。A低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C與鏈接法處理沖突相同 D高于二分查找7. 7. 若需要利用形參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為（ ）參數(shù)。A值 B函數(shù) C指針 D引用8. 8. 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（ ）。A行號 B列號 C元素值 D非零元素個(gè)數(shù)9. 9. 快速排序在最壞情況下的時(shí)間復(fù)雜度為（ ）。AO(log2n) BO(nlog2n) C0(n) D0(n