《數(shù)據(jù)結(jié)構(gòu)》模擬試題綜合測(cè)試題帶答案 (10)

1、數(shù)據(jù)結(jié)構(gòu)模擬試題10一、單項(xiàng)選擇題（每題 3 分，共30分）1設(shè)某無(wú)向圖有n個(gè)頂點(diǎn)，則該無(wú)向圖的鄰接表中有（ ）個(gè)表頭結(jié)點(diǎn)。(A) 2n(B) n(C) n/2(D) n(n-1)2設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)，則該無(wú)向圖的最小生成樹(shù)上有（ ）條邊。(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、二叉排序樹(shù)可以得到一個(gè)從小到大的有序序列。(A) 先序遍歷(B) 中序遍歷(C) 后序遍歷(D) 層次遍歷5設(shè)按照從上到下、從左到右的順序從1開(kāi)始對(duì)完全二叉樹(shù)進(jìn)行順序編號(hào)，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為（ ）。(A) 2i+1(B) 2i(C) i/2(D) 2i-16程序段s=i=0；do i=i+1； s=s+i；while(i<=n)；的時(shí)間復(fù)雜度為（ ）。(A) O(n)(B) O(nlog2n)(C) O(n2)(D) O(n3/2)7設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（ ）。(A) head=0 (B) head->next=0(C)

3、head->next=head(D) head!=08設(shè)某棵二叉樹(shù)的高度為10，則該二叉樹(shù)上葉子結(jié)點(diǎn)最多有（ ）。(A) 20(B) 256(C) 512(D) 10249設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(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;二、填

4、空題（每題2分，共20分）1. 設(shè)指針變量p指向雙向鏈表中的結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為_(kāi)=p；s->right=p->right；_=s； p->right->left=s；（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為left和right）。2. 設(shè)完全有向圖中有n個(gè)頂點(diǎn)，則該完全有向圖中共有_條有向條；設(shè)完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中共有_條無(wú)向邊。3. 設(shè)關(guān)鍵字序列為(Kl，K2，Kn)，則用篩選法建初始堆必須從第_個(gè)元素開(kāi)始進(jìn)行篩選。4. 解決散列表沖突的兩種方法是_和_。5. 設(shè)一棵三叉樹(shù)中有50個(gè)度數(shù)為0的結(jié)點(diǎn)，21

5、個(gè)度數(shù)為2的結(jié)點(diǎn)，則該二叉樹(shù)中度數(shù)為3的結(jié)點(diǎn)數(shù)有_個(gè)。6. 高度為h的完全二叉樹(shù)中最少有_個(gè)結(jié)點(diǎn)，最多有_個(gè)結(jié)點(diǎn)。7. 設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是_。8. 設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟簡(jiǎn)單選擇排序結(jié)束后的結(jié)果的是_。9. 設(shè)一棵二叉樹(shù)的前序序列為ABC，則有_種不同的二叉樹(shù)可以得到這種序列。10. 下面程序段的功能是實(shí)現(xiàn)一趟快速排序，請(qǐng)?jiān)谙聞澗€(xiàn)處填上正確的語(yǔ)句。struct record int key;datatype others;void quickpass(struct

6、 record r, int s, int t, int &i) int j=t; struct record x=rs; i=s; while(i<j) while (i<j && rj.key>x.key) j=j-1; if (i<j) ri=rj;i=i+1; while (_) i=i+1; if (i<j) rj=ri;j=j-1; _;三、判斷題（每題 2 分，共20分）1不論是入隊(duì)列操作還是入棧操作，在順序存儲(chǔ)結(jié)構(gòu)上都需要考慮“溢出”情況。（ ）2當(dāng)向二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。（ ）3設(shè)某堆中有n個(gè)

7、結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(log2n)。（ ）4完全二叉樹(shù)中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。（ ）5哈夫曼樹(shù)中沒(méi)有度數(shù)為1的結(jié)點(diǎn)。（ ）6對(duì)連通圖進(jìn)行深度優(yōu)先遍歷可以訪(fǎng)問(wèn)到該圖中的所有頂點(diǎn)。（ ）7先序遍歷一棵二叉排序樹(shù)得到的結(jié)點(diǎn)序列不一定是有序的序列。（ ）8由樹(shù)轉(zhuǎn)化成二叉樹(shù)，該二叉樹(shù)的右子樹(shù)不一定為空。（ ）9線(xiàn)性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。（ ）10.帶權(quán)無(wú)向圖的最小生成樹(shù)是唯一的。（ ）四、算法設(shè)計(jì)題（每題10分，共30分）1. 設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡(jiǎn)單選擇排序算法。2. 設(shè)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。3. 設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹(shù)中層次的算法

8、。5數(shù)據(jù)結(jié)構(gòu)模擬試題10參考答案一、單項(xiàng)選擇題（每題 3 分，共30分）1B2B3C4B5B6A7C8C9B10D二、填空題（每小題2分，共20分）1. s->left=p，p->right2. n(n-1)，n(n-1)/23. n/24. 開(kāi)放定址法，鏈地址法5. 146. 2h-1，2h-17. (12，24，35，27，18，26)8. (12，18，24，27，35，26)9. 510. i<j && ri.key<x.key，ri=x三、判斷題（每題 2分，共20分）1對(duì)2對(duì)3對(duì)4對(duì)5對(duì)6對(duì)7對(duì)8錯(cuò)9錯(cuò)10錯(cuò)四、算法設(shè)計(jì)題（每題10分，共30

9、分）1. 設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡(jiǎn)單選擇排序算法。void simpleselectsorlklist(lklist *&head) lklist *p,*q,*s; int min,t; if(head=0 |head->next=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(min>p->data)min=p->data; s=p; if(s!=q)t=s->data; s->data=q-

10、>data; q->data=t; 2. 設(shè)計(jì)在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求子串算法。void substring(char s , long start, long count, char t ) long i,j,length=strlen(s); if (start<1 | start>length) printf("The copy position is wrong"); else if (start+count-1>length) printf("Too characters to be copied");else for(i=start-1,j=0; i<start+count-1;i+,j+) tj=si; tj= '0'3. 設(shè)計(jì)求結(jié)點(diǎn)在二叉排序樹(shù)中層次的算法。int lev=0;typedef struct nodeint key; struct node *lchild