長(zhǎng)沙理工大學(xué)數(shù)據(jù)結(jié)構(gòu)期末考試試卷

1、長(zhǎng)沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院2013-2014學(xué)年二學(xué)期數(shù)據(jù)結(jié)構(gòu)期末考試試卷(B卷)班級(jí):_學(xué)號(hào):_姓名:_得分:_題號(hào)一二三四五六七八九十成績(jī)復(fù)核得分            閱卷           題目部分，(卷面共有31題,100分,各大題標(biāo)有題量和總分)一、應(yīng)用題(1小題,共8分)1已知無(wú)向圖G的鄰接表如圖所示，分別寫出從頂點(diǎn)1出發(fā)的深度遍歷和廣度遍歷序列

2、。二、判斷正誤(7小題,共14分)1串中任意個(gè)字符組成的子序列稱為該串的子串。 2帶權(quán)無(wú)向圖的最小生成樹(shù)是唯一的。（  ）3如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。（  ）4無(wú)向圖的鄰接矩陣一定是對(duì)稱的，有向圖的鄰接矩陣一定是不對(duì)稱的。（  ）5向二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹(shù)的高度。（  ）6堆是完全二叉樹(shù)，完全二叉樹(shù)不一定是堆。（  ）7數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是相同的。（  ） 三、單項(xiàng)選擇題(10小題,共20分)1在順序表中，只要知道（ &#

3、160;  ），就可以求出任一結(jié)點(diǎn)的存儲(chǔ)地址。A基地址          B結(jié)點(diǎn)大小        C 向量大小       D基地址和結(jié)點(diǎn)大小  2設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操作序列為（  ）。  A  q=p->next；p->data=q->data；p->

4、;next=q->next；free(q)； B  q=p->next；q->data=p->data；p->next=q->next；free(q)； C  q=p->next；p->next=q->next；free(q)；D  q=p->next；p->data=q->data；free(q)；3循環(huán)隊(duì)列占用的空間(    )。  A必須連續(xù)          

5、;B不必連續(xù)    C不能連續(xù)      D可以不連續(xù)4若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前front和rear的值分別為3和0，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，front和rear的值分別為(    )。  A5和1        B4和2         C2和4    

6、60;        D1和55設(shè)某棵二叉樹(shù)的高度為10，則該二叉樹(shù)上葉子結(jié)點(diǎn)最多有（  ）。     A  20                      B  256      

7、0;          C  512                 D  10246設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹(shù)的深度為（  ）。     A  4   &#

8、160;                    B  5                     C  6       

9、             D  7 7若有18個(gè)元素的有序表存放在一維數(shù)組A19中，第一個(gè)元素放A1中，現(xiàn)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為(      )  A. 1，2，3                 B. 9

10、，5，2，3 C. 9，5，3                       D. 9，4，2，3 8在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來(lái)考慮應(yīng)最好選擇（   ）排序，如果從節(jié)省存儲(chǔ)空間的角度來(lái)考慮則最好選擇（   ）排序。9設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個(gè)記錄關(guān)

11、鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（  ）。       A  40，42，45，55，80，83            B  42，40，45，80，85，88       C  42，40，45，55，80，85         

12、   D  42，40，45，85，55，80 10下列敘述正確的是（ ）A算法的執(zhí)行效率與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān) B算法的空間復(fù)雜度是指算法程序中指令（或語(yǔ)句）的條數(shù) C算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止 D算法的時(shí)間復(fù)雜度是指執(zhí)行算法程序所需要的時(shí)間 四、算法設(shè)計(jì)題(4小題,共32分)1設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。2一個(gè)循環(huán)隊(duì)列Queue，只有頭指針front，不設(shè)尾指針，另設(shè)一個(gè)含有元素個(gè)數(shù)的記數(shù)器cont，試寫出相應(yīng)的入隊(duì)算法和出隊(duì)算法。3設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。4設(shè)計(jì)算法，計(jì)算圖中出度

13、為零的頂點(diǎn)個(gè)數(shù)。五、填空題(6小題,共12分)1當(dāng)循環(huán)隊(duì)列為空時(shí)，不能進(jìn)行出隊(duì)運(yùn)算，這種情況稱為（  ）。2已知順序棧S，在對(duì)S進(jìn)行進(jìn)棧操作之前首先要判斷（    ），在對(duì)S進(jìn)行出棧操作之前首先要判斷（    ）。 3設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)尾指針，則出隊(duì)操作的時(shí)間復(fù)雜度為(    )。4完全二叉樹(shù)中第5層上最少有（   ）個(gè)結(jié)點(diǎn)，最多有（   ）個(gè)結(jié)點(diǎn)。5表示一個(gè)有100個(gè)頂點(diǎn)，1000條邊的有向圖的鄰接矩陣有（ ）個(gè)非零矩陣

14、元素。6若一個(gè)算法中的語(yǔ)句頻度之和為T（n）=3n+nlog2n+n2，則算法的時(shí)間復(fù)雜度為（   ） 六、簡(jiǎn)答題(2小題,共10分)1設(shè)一數(shù)列的輸入順序?yàn)?23456，若采用堆棧結(jié)構(gòu)，并以A和D分別表示入棧和出棧操作，試問(wèn)通過(guò)入出棧操作的合法序列， 能否得到輸出順序?yàn)?54623的序列。2設(shè)有無(wú)向圖G（如下圖所示），要求給出用普里姆算法構(gòu)造最小生成樹(shù)所走過(guò)的邊的集合。   七、名詞解釋(1小題,共4分)1什么是AOE網(wǎng)?長(zhǎng)沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院2013-2014學(xué)年二學(xué)期數(shù)據(jù)結(jié)構(gòu)期末考試試卷(B卷)答案部分，(卷面共有31題

15、,100.0分,各大題標(biāo)有題量和總分)一、應(yīng)用題(1小題,共8分)1【解答】深度優(yōu)先遍歷序列為：1，2，3，4，5，6   廣度優(yōu)先遍歷序列為：1，2，4，3，5，6二、判斷正誤(7小題,共14分)1錯(cuò)2錯(cuò)3對(duì)4錯(cuò)5錯(cuò)6對(duì)7錯(cuò)三、單項(xiàng)選擇題(10小題,共20分)1D2A3A4B5C6A7D8快速   堆9C10C四、算法設(shè)計(jì)題(4小題,共32分)1int isriselk(lklist *head)if(head=0|head->next=0) return(1);else For(q=head,p=head->next; p!=0; q=p

16、,p=p->next)if(q->data>p->data) return(0);return(1); 2解：用一個(gè)循環(huán)數(shù)組Queue0，n-1表示該循環(huán)隊(duì)列，頭指針為front，計(jì)數(shù)器count用來(lái)記錄隊(duì)列中結(jié)點(diǎn)的個(gè)數(shù)。（1）入隊(duì)算法：  void inqueqe(int x)   int temp;if (count=n)   printf(" 隊(duì)列上溢出n"); Else   count+     temp=(front+co

17、unt)%n;     Queuetemp=x       （2）出隊(duì)算法：  int outqueue()  int temp;if (count=0)   printf(" 隊(duì)列下溢出n"); Else   temp=Queuefront;     front=(front+1)%n;     count-;   

18、  return temp;       3void countnode(bitree *bt,int &count)   if(bt!=0) count+; countnode(bt->lchild,count); countnode(bt->rchild,count); 4在有向圖的鄰接矩陣中，一行對(duì)應(yīng)一個(gè)頂點(diǎn)，每行的非零元素的個(gè)數(shù)等于對(duì)應(yīng)頂點(diǎn)的出度。因此，當(dāng)某行非零元素的個(gè)數(shù)為零時(shí)，則對(duì)應(yīng)頂點(diǎn)的出度為零。據(jù)此，從第一行開(kāi)始，查找每行的非零元素個(gè)數(shù)是否為零，若是則計(jì)數(shù)器加1。具體算法如下：五、填空題(6小題,共12分)1下溢2棧是否滿      棧是否空