2013年全國(guó)碩士研究生統(tǒng)一入學(xué)考試自命題試題（副卷）********************************************************************************************學(xué)科與專業(yè)名稱：計(jì)算機(jī)技術(shù)，軟件工程考試科目代碼與名稱：830數(shù)據(jù)結(jié)構(gòu)考生注意：所有答案必須寫在答題紙（卷）上，寫在本試題上一律不給分。一.選擇題（每題2分，共30分）TOC\o"1-5"\h\z在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)分為（ ）。動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu) D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)設(shè)某無(wú)向圖中有n個(gè)頂點(diǎn)e條邊，則該無(wú)向圖中所有頂點(diǎn)的度之和為（）。A.n B.e C.2n D.2e在內(nèi)部排序中，排序時(shí)不穩(wěn)定的有（ ）。A.插入排序 B.冒泡排序 C.快速排序 D.歸并排序在循環(huán)隊(duì)列中，若front與rear分別表示隊(duì)頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條件是（）。A.front==rear+1 B.rear==front+1C.front==rearD.front==05.6.設(shè)單鏈表中指針p指著結(jié)點(diǎn)A,若要?jiǎng)h除A之后的結(jié)點(diǎn)（5.6.設(shè)單鏈表中指針p指著結(jié)點(diǎn)A,若要?jiǎng)h除A之后的結(jié)點(diǎn)（若存在）,則需要修改指針的操作為（A.p->next=p->next->nextC.p=p->next->next最壞情況下堆排序的時(shí)間復(fù)雜度是（A.O（log2n） B.O（log2n2））。B.p=p->nextD.p->next=p）。C.O（nlog2n） D.0（n2）7.設(shè)使用的鄰接表表示某有向圖，則頂點(diǎn)筲在表結(jié)點(diǎn)中出現(xiàn)的次數(shù)等于（A.頂點(diǎn)筲的度 B.頂點(diǎn)片的出度&樹最適合用來表示（ ）。A.有序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)9.具有n個(gè)頂點(diǎn)的連通圖至少應(yīng)有（ ））。C.頂點(diǎn)片的入度D.無(wú)法確定B.D.條邊。無(wú)序數(shù)據(jù)元素元素之間無(wú)聯(lián)系的數(shù)據(jù)A.n-1 B.n C.n（n-1）/2 D.2n時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒定為0（nlog2n）的是（ ）。A.堆排序 B.冒泡排序 C.希爾排序 D.快速排序共6共6頁(yè)，第1頁(yè)TOC\o"1-5"\h\z任何一顆二叉樹的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì)次序（ ）。A.不變 B.發(fā)生改變 C.不能確定 D.以上全不對(duì)一組記錄（50,40,95,20,15,70,60,45,80）進(jìn)行冒泡排序時(shí)，第一趟需進(jìn)行相鄰記錄的交換的次數(shù)為（ ）。A.5 B.6 C.7 D.8循環(huán)隊(duì)列中是否可以插入下一個(gè)元素（ ）。與曾經(jīng)進(jìn)行過多少次插入操作有關(guān).只與隊(duì)尾指針的值有關(guān)，與隊(duì)頭指針的值無(wú)關(guān).只與數(shù)組大小有關(guān)，與隊(duì)首指針和隊(duì)尾指針的值無(wú)關(guān)與隊(duì)頭指針和隊(duì)尾指針的值有關(guān).某二叉樹的先序遍歷序列為abdgcefh,中序遍歷序列為dgbaechf,則它的左子樹的結(jié)點(diǎn)數(shù)目為（ ）。A.3 B.4 C.5 D.6對(duì)于元素是整數(shù)（占2個(gè)字節(jié)）的對(duì)稱矩陣A,采用以行序?yàn)橹鞯膲嚎s存儲(chǔ)方式（下三角）,若A[0][0]的地址是400,則元素A[8][5]的存儲(chǔ)地址是（C）。A.440 B.480C.482 D.582二?填空題（每題2分，共20分）稀疏矩陣一般的壓縮存儲(chǔ)方法主要有兩種，即 和 。2.線性結(jié)構(gòu)中元素之間存在 的關(guān)系，樹形結(jié)構(gòu)中元素之間存在的關(guān)系。由n個(gè)權(quán)值構(gòu)成的哈夫曼樹共有 個(gè)結(jié)點(diǎn)。在散列表（hash）查找中，評(píng)判一個(gè)散列函數(shù)優(yōu)劣的兩個(gè)主要條件是： TOC\o"1-5"\h\z和 。線索二叉樹的左線索指向 ，右線索指向 。6?在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n°,度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2,則該二叉樹有 個(gè)葉子結(jié)點(diǎn)。7.有一個(gè)100X90的稀疏矩陣，非0元素有10,設(shè)每個(gè)整型數(shù)占2個(gè)字節(jié)，則用三元組表示該矩陣時(shí)，所需的字節(jié)數(shù)是 。&帶頭結(jié)點(diǎn)的循環(huán)單鏈表L為空的條件是 。設(shè)給定權(quán)值集合w={9,2,5,7}，對(duì)應(yīng)huffman樹的加權(quán)路徑長(zhǎng)度WPL為 。若某記錄序列的關(guān)鍵字序列是（50,40,95,20,15,70），用簡(jiǎn)單選擇法進(jìn)行排序，第一次收集的結(jié)果 ?？荚嚳颇浚簲?shù)據(jù)結(jié)構(gòu) 共6頁(yè),第2頁(yè)三?判斷題（每題1分，共10分，正確的選t,錯(cuò)誤的選f）采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷相當(dāng)于樹的中序遍歷。（）TOC\o"1-5"\h\z無(wú)向圖的鄰接矩陣一定是對(duì)稱的。（ ）線性表中的每一個(gè)元素都有一個(gè)前驅(qū)和后繼元素。（ ）B和B+樹都能有效地支持隨機(jī)查找。（ ）拓?fù)渑判蚴前碅OE網(wǎng)中每個(gè)結(jié)點(diǎn)事件的最早發(fā)生事件對(duì)結(jié)點(diǎn)進(jìn)行排序。 （ ）—顆滿二叉樹同時(shí)又是一顆平衡樹。（ ）對(duì)初始堆進(jìn)行層次遍歷可以得到一個(gè)有序序列。（ ）&冒泡排序是穩(wěn)定的。（ ）哈夫曼樹中權(quán)值最小的結(jié)點(diǎn)離跟最近。（ ）帶權(quán)無(wú)向圖的最小生成樹是唯一的。（ ）四.簡(jiǎn)答題（50分）1.對(duì)圖1.所示的有向帶權(quán)圖，使用Dijkstra（迪杰斯特拉）算法求出從頂點(diǎn)0到其余各頂點(diǎn)的最短路徑，要求寫出過程。（10分）2圖1.設(shè)使用堆排序法對(duì)關(guān)鍵字序列T=（10,27,5,50,60,7,40,43,75進(jìn)行排序：（10分）（1） 畫出初始大根堆對(duì)應(yīng)的完全二叉樹（2） 寫出大根堆序列（3） 畫出第一趟排序后新堆對(duì)應(yīng)的完全二叉樹簡(jiǎn)述下列算法的功能。（6分）typedefstructBiTNode{int data;StructBiTNode*lchild;StructBiTNode*rchild;}BiTNode,*BiTree;intfunc（BiTreeT）考試科目：數(shù)據(jù)結(jié)構(gòu) 共6頁(yè)，第3頁(yè)

{if(T==NULL)return(0);elseif(T->data==0)return(1+func(T->lchild)+func(T->rchild));elsereturn(func(T->lchild)+func(T->rchild));}使用Prime算法構(gòu)造出圖1所示的圖G的一棵最小生成樹(要求寫出構(gòu)造過程)。(10分)假設(shè)二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，如圖2所示。（6分）（1） 畫出二叉樹表示（2） 寫出先序遍歷，中序遍歷，后序遍歷的結(jié)果ABCDEFGHI圖26.設(shè)關(guān)鍵字序列為（64,5,95,53,18,25,65,27,16），散列函數(shù)為H（key）=key%7，采用鏈地址法解決沖突，請(qǐng)回答：（8分）（1） 畫出散列表示意圖（用頭插法向單鏈表中插入結(jié)點(diǎn)）（2） 查找關(guān)鍵字95時(shí)，需要依次與哪些關(guān)鍵字比較（3） 求等概率下查找成功的平均查找長(zhǎng)度五?算法填空，（每空2分，共18分）1.設(shè)計(jì)一個(gè)函數(shù)功能為：在帶頭結(jié)點(diǎn)的單鏈表中刪除值最小的元素。請(qǐng)將代碼補(bǔ)充完整。共6共6頁(yè)，第4頁(yè)typedefintDataType;typedefstructNode{DataTypedata;structNode*next;}LinkList;voiddeleteMin(LinkList*L){ LinkList*p=L->next,*q;q=p;while( ){if(p->data<q->data)q=p; ;}if(!q)return;p=L;while(p->next!=q)p=p->next; ; ;}2 以下程序使用冒泡排序法對(duì)存放在a[1],a[2],……a[n]中的序列進(jìn)行排序，完成程序中的空格部分，其中n是元素個(gè)數(shù)，要求按升序排列。typedefstruct{intkey;infotypeotherinfo;}No