2014暨南大學數(shù)據(jù)結構考研真題

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

{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算法構造出圖1所示的圖G的一棵最小生成樹(要求寫出構造過程)。(10分)假設二叉樹采用順序存儲結構，如圖2所示。（6分）（1） 畫出二叉樹表示（2） 寫出先序遍歷，中序遍歷，后序遍歷的結果ABCDEFGHI圖26.設關鍵字序列為（64,5,95,53,18,25,65,27,16），散列函數(shù)為H（key）=key%7，采用鏈地址法解決沖突，請回答：（8分）（1） 畫出散列表示意圖（用頭插法向單鏈表中插入結點）（2） 查找關鍵字95時，需要依次與哪些關鍵字比較（3） 求等概率下查找成功的平均查找長度五?算法填空，（每空2分，共18分）1.設計一個函數(shù)功能為：在帶頭結點的單鏈表中刪除值最小的元素。請將代碼補充完整。共6共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; ; ;}2 以下程序使用冒泡排序法對存放在a[1],a[2],……a[n]中的序列進行排序，完成程序中的空格部分，其中n是元素個數(shù)，要求按升序排列。typedefstruct{intkey;infotypeotherinfo;}No