暨南大學(xué)計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)2013

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