數(shù)據(jù)結(jié)構(gòu)試卷與答案

1、算法與程序有何區(qū)別和聯(lián)系？（6 分）算法是對(duì)特定問題求解步驟的一種描述，可以用自然語言、流程圖、偽代碼、程序代碼來表示。程序是算法的具體實(shí)現(xiàn)，可以用不同的語言實(shí)現(xiàn)。2 樹的結(jié)構(gòu)。（6 分）方法主要有哪些？任你畫一個(gè)樹舉例說明具體2.(1)雙親表示法以一組連續(xù)空間結(jié)點(diǎn)的位置。樹的結(jié)點(diǎn)，在每個(gè)結(jié)點(diǎn)中設(shè)一個(gè)指示器指示雙親(2)孩子表示法每個(gè)結(jié)點(diǎn)的孩子以單鏈表的形式，n 個(gè)結(jié)點(diǎn)有 n 個(gè)孩子鏈表，n 個(gè)頭指針又組成一個(gè)線性表，并以順序結(jié)構(gòu)。結(jié)構(gòu)，鏈表中的結(jié)點(diǎn)的兩個(gè)指針分別指向(3)孩子兄弟表示法以二叉鏈表作為樹的該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。設(shè)有序表的長(zhǎng)度為 10，用二分查找方法進(jìn)行查找，試

2、計(jì)算查找成功情況下的平均查找長(zhǎng)度（6 分）ASL = 1/10 *(1+2*2+4*3+3*4) = 2.9圖的遍歷方法主要有哪些？任你畫一個(gè)圖舉例具體說明。（6 分）深度優(yōu)先搜索，寬度優(yōu)先搜索。例如：深度優(yōu)先搜索遍歷：ABXFYDEC寬度優(yōu)先搜索遍歷：ABCDXEYF5 畫出廣義表 D=( )，x，(a，(b，c)的結(jié)構(gòu)，并寫出廣義表類型定義。;#define ATOM 0#define LIST 1 typedef enum/后繼結(jié)點(diǎn)結(jié)構(gòu) struct GLNodeElemTag tag; unionatom;ATOM,ElemTag;LIST/表頭表尾結(jié)構(gòu) struct GLNodeEl

3、emTag tag; unionatom; structstruct GLNode *hp; struct GLNode *tp;ptr;/原子結(jié)點(diǎn)的值域struct GLNode *hp;struct GLNode *tp;/區(qū)分原子結(jié)點(diǎn)表結(jié)點(diǎn)/表結(jié)點(diǎn)的頭指針/下一個(gè)元素結(jié)點(diǎn)采用后繼結(jié)點(diǎn)的結(jié)構(gòu)6. 分別畫出一個(gè) B 樹和 B+樹的例子，并它們之間的區(qū)別。（6 分）第 1 頁 共 5頁B 樹與 B+樹的區(qū)別：1) B 樹：每個(gè)結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)等于指針個(gè)數(shù)減 1。 B+樹：每個(gè)結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)等于指針個(gè)數(shù)。2) B+樹中所有葉子結(jié)點(diǎn)包含了全部關(guān)鍵字信息，以及指向關(guān)鍵字的指針，葉子節(jié)點(diǎn)依關(guān)鍵字大小

4、自小到大。非終端結(jié)點(diǎn)作索引，結(jié)點(diǎn)中含有其子樹根結(jié)點(diǎn)的最大（最?。╆P(guān)鍵字。7. 你知道有哪些排序算法？試比較各種排序算法的性能。（8 分）8設(shè)一組關(guān)鍵字為（7，15，20，31，48，53，64，76，82，99），Hash 函數(shù)H（key）= key% 11，Hash 表表長(zhǎng) m=11，用線性探測(cè)法解決，試構(gòu)造Hash 表，并分別計(jì)算查找成功和查找失敗情況下的平均查找長(zhǎng)度。（8 分）7%11=7找 1 次成功15%11=4找 1 次成功查76%11=10 10+1+1+1-11=2查找 4 次成功82%11=55+1=6成功查找 2 次查99%11=00+1+1+1=3查找 4 次成功20%1

5、1=9找 1 次成功查查找成功時(shí)的平均查找長(zhǎng)度： (1+1+1+2+2+3+4+4+2+4)/10=2.4查找失敗的平均查找長(zhǎng)度：（1+2+3+4+5+6+7+8+9+10+11）/11=631%11=9功9+1=10查找 2 次成48%11=4功4+1 =5查找 2 次成53%11=99+1+1-11=0查找 3 次成功64%11=99+1+1+1-11=1查找 4 次成功二、簡(jiǎn)述利用 Dijkstra 算法求解從某頂點(diǎn)到其余各頂點(diǎn)最短路徑的步驟。Dijkstra 算法：(1)求解順序：按最短路徑遞增的順序求解。(2)到某個(gè)定點(diǎn)的最短路徑找到后，它對(duì)其余頂點(diǎn)當(dāng)前最短路徑的影響。第 2 頁 共

6、 5頁選擇排序O(n2)O(1)不穩(wěn)定堆排序O(nlogn)O(1)不穩(wěn)定歸并排序O(nlogn)O(n)穩(wěn)定基數(shù)排序O(d(n+rd)O(rd)不穩(wěn)定排序算法時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性直接排序O(n2)O(1)穩(wěn)定冒泡排序O(n2)O(1)穩(wěn)定快速排序O(nlogn)O(logn)不穩(wěn)定算法步驟：1）設(shè) arcs帶權(quán)有向圖的邊的權(quán)值，v 為出發(fā)頂點(diǎn)，S 為已找到的從 v 出發(fā)的最短路徑的終點(diǎn)集合，開始為空。從 v 出發(fā)到圖中其余頂點(diǎn) vi 最短路徑長(zhǎng)度初始值為 Di=arcsoi o, i 為 v, vi 的位置選擇 vj，使得 Dj=MinDi| viV-S vj 是從v 出發(fā)的最短路徑的

7、終點(diǎn)。S=Sj修改從 v 出發(fā)到集合 V-S 任一頂點(diǎn) vk 可達(dá)的最短路徑長(zhǎng)度。如果 Dj+arcsjkDk，則 Dk= Dj+arcsjk。重復(fù) 2，3 n-1 次，由此求出從 v 到其它頂點(diǎn)的最短路徑。三、試編寫歸并排序算法。（12 分）TR1s = SRs;elsem = (s+t)/2; /SRs.t平分為SRs.m和 SRm+1.tMSort(SR,TR2,s,m);/遞歸地將SRs.m歸并為有序的TR2s.mMSort(SR,TR2,m+1,t); /遞歸地將SRm+1.t歸并為有序的TR2m+1.t Merge(TR2,TR1,s,m,t); /將TR2s.m和TR2m+1.t

8、歸并到TR1s.t#include /將有序的SRi.m和SRm+1.n歸并為有序的TRi.nvoid Merge( n)j,k; j = m+1; k = i;SR,TR,i,m,while(i=m & j=n) if(SRi=SRj)TRk+ = SRi+;elseTRk+ = SRj+;while(i=m) TRk+ = SRi+;while(j=n) TRk+ = SRj+;/主函數(shù)，調(diào)用歸并排序MSort void main()s10 = 2,6,7,4,5,10,9,1,3,8;MSort(s,s,0,9); i;for(i=0;i10;i+)/將SRs.t歸并排序?yàn)門R1s.tp

9、rf(%d , si);void MSort(SR,m; TR210;if(s = t)TR1,s,t)第 3 頁共 5頁四、試編寫一個(gè)算法將線性表 L 中的數(shù)據(jù)建立一棵二叉排序樹。（12 分）for(i=1; il.length; i+)p = root;while(p != NULL) /新結(jié)點(diǎn)定位 if(l.elemidata)q = p;p = p-lchild;else if(l.elemip-data)q = p;p = p-rchild;else/該值已在排序樹中出現(xiàn)，不再 break;if(p = NULL)r = (BiTNode*) malloc(sizeof(BiTNod

10、e); r-data = l.elemi;r-lchild = NULL;r-rchild = NULL;/生成新結(jié)點(diǎn) if(l.elemidata)q-lchild = r; elseq-rchild = r; /新結(jié)點(diǎn)作q 的葉子結(jié)點(diǎn)/線性表結(jié)點(diǎn)typedef struct SqList* elem; length; listsize; SqList;/二叉樹結(jié)點(diǎn)typedef struct BiTNodedata;struct BiTNode *lchild, *rchild; BiTNode;/建立二叉排序樹void CreateBST(SqList l, BiTNode* &root)i;BiTNode *p, *q, *r; if(l.lenght=0)root = NULL; return;root =(BiTNode*) malloc(sizeof(BiTNode); root-data = l.elem0;root-lchild=root-rchild=NULL; /二叉排序樹的根節(jié)點(diǎn)五、設(shè)單鏈表 L 中的結(jié)點(diǎn)按 data 域數(shù)值遞減排列，試設(shè)計(jì)一個(gè)算法將 L 中的結(jié)點(diǎn)按 data 域數(shù)值遞增加排列，要求算法的時(shí)間復(fù)雜性為 O（n）。（12 分）void TraverseList(LN