2023-2023北京交通大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法期末考試參考答案

1、北京交通大學(xué)考試試題A卷課程名稱:數(shù)據(jù)結(jié)構(gòu)與算法 2023-2023學(xué)年第一學(xué)期出題教師:張勇(請考生注意:1本試卷共有六道大題，2答案一律寫在答題紙上，3試卷不得帶出考場)題號一二三四五六總分得分閱卷人填空題每空2分，共20分1. 在順序表中訪問任意一個元素的時間復(fù)雜度均為，因此順序表也稱為的數(shù)據(jù)結(jié)構(gòu)。2三維數(shù)組a432(下標(biāo)從0開始)，假設(shè)a000的地址為50，數(shù)據(jù)以行序優(yōu)先方式存儲，每個元素的長度為2字節(jié)，那么a211的地址是。3. 直接插入排序用監(jiān)視哨的作用是。4. 廣義表Ls=(a, (b, c), (d, e), 運用head和tail函數(shù)取出Ls中的原子d的運算是。5對有14個元

2、素的有序表A1.14進行折半查找，當(dāng)比較到A4時算法結(jié)束。被比較元素除A4外，還有。6. 在AOV網(wǎng)中，頂點表示，邊表示。 7. 有向圖G可進行拓撲排序的判別條件是。 8. 假設(shè)串S1=ABCDEFGHIJK,S2=451223,S3=#,那么執(zhí)行Substring(S1,Strlength(S3),Index(S2,12選擇題每空2分，共20分在以下存儲形式中，哪一個不是樹的存儲形式？A雙親表示法 B孩子鏈表表示法C孩子兄弟表示法 D順序存儲表示法查找n個元素的有序表時，最有效的查找方法是。A順序查找 B分塊查找C折半查找 D二叉查找將所示的s所指結(jié)點加到p所指結(jié)點之后，其語句應(yīng)為 。(A)

3、 s-next=p+1 ; p-next=s;(B) (*p).next=s; (*s).next=(*p).next;(C) s-next=p-next ; p-next=s-next;(D) s-next=p-next ; p-next=s;在有向圖的鄰接表存儲結(jié)構(gòu)中，頂點v在鏈表中出現(xiàn)的次數(shù)是。A. 頂點v的度 B. 頂點v的出度C. 頂點v的入度 D. 依附于頂點v的邊數(shù)算法的時間復(fù)雜度為Onlog2n、空間復(fù)雜度為O(1)的排序算法是 。A. 堆排序 B. 快速排序 C. 歸并排序D.直接選擇設(shè)矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角局部如右圖所示按行序存放在一維數(shù)組B 1,

4、n(n-1)/2 中，對下三角局部中任一元素ai,j(ij), 在一維數(shù)組B中下標(biāo)k的值是：i(i-1)/2+j-1 i(i-1)/2+j i(i+1)/2+j-1 i(i+1)/2+j由一個長度為11的有序表，按二分查找法對該表進行查找，在表內(nèi)各元素等概率情況下，查找成功的平均查找長度是 。A29/11 B. 31/11 CAVL樹是一種平衡的二叉排序樹，樹中任一結(jié)點的。A. 左、右子樹的高度均相同 B. 左、右子樹高度差的絕對值不超過1 C. 左子樹的高度均大于右子樹的高度 D. 左子樹的高度均小于右子樹的高度 以下四種排序方法中，不穩(wěn)定的方法是。A. 直接插入排序B. 冒泡排序C. 歸并

5、排序D. 堆排序設(shè)樹的度為4，其中度為1,2,3,4的結(jié)點個數(shù)分別為4, 2, ,1, 1, 那么T中的葉子數(shù)為。A5 B6 C7 D8判斷題10分，每題1分順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。數(shù)組不適合作任何二叉樹的存儲結(jié)構(gòu)。廣義表的取表尾運算，其結(jié)果通常是個表，但有時也可是個原子。在含有n個結(jié)點的樹中，邊數(shù)只能是n-1條。所謂一個排序算法是否穩(wěn)定，是指該算法在各種情況下的效率是否相差不大。簡單項選擇擇排序在最好情況下的時間復(fù)雜度為O(n)。在二叉排序樹中插入一個新結(jié)點，總是插入到葉結(jié)點下面。采用線性探測處理沖突，當(dāng)從哈希表中刪除一個記錄時，不應(yīng)將該記錄所在位置置空，因為

6、這會影響以后的查找。有n個數(shù)存放在一維數(shù)組A1.n中，在進行順序查找時，這n個數(shù)的排列有序或無序，其平均查找長度不同。廣義表中原子個數(shù)即為廣義表的長度。( )應(yīng)用題24分1. 6分將以下由三棵樹組成的森林轉(zhuǎn)換為二叉樹。2(6分)給定以下列圖，完成以下問題1畫出該圖的鄰接矩陣和鄰接表2根據(jù)所畫的鄰接表，從頂點B出發(fā)，畫出圖的深度優(yōu)先搜索樹3根據(jù)普里姆Prim算法，求它的最小生成樹不必寫出全部過程，在生成樹中標(biāo)出邊生成的次序即可36分輸入一個正整數(shù)序列53,17,12,66,58,70,87,25,56,60，試完成以下各題：1構(gòu)造一棵二叉排序樹，計算查找成功的平均查找長度；2依此二叉排序樹，如何

7、得到一個從大到小的有序序列；3畫出在此二叉排序樹中，刪除“66后的樹結(jié)構(gòu).4. 6分將序列25, 34, 12, 7, 15, 47, 65, 79，47+，16 中的關(guān)鍵字按升序重新排列，請寫出1冒泡排序一趟掃描的結(jié)果2以第一個元素為分界點的快速排序一趟掃描的結(jié)果3堆排序所建的初始堆和第一趟排序結(jié)果。程序填空題10分，每空1分以下算法是建立單鏈表的算法，請?zhí)顚戇m當(dāng)?shù)恼Z句，完成該功能。typedef struct Lnode ElemType data; struct Lnode *next; LNode, *LinkList;Status CreatList_L(LinkList &L, i

8、nt n) /正序輸入n個元素的值,建立帶表頭結(jié)點的單鏈線性表L L=(LinkList) malloc(sizeof(LNode); if(!L) return ERROR; L-next=NULL; p= ( 1 ) ; for(i=0;idata); (2) ; (3) ; p-next=NULL; return OK;/CreatList_L2. 以下算法是經(jīng)典模式匹配算法程序，請?zhí)顚戇m當(dāng)?shù)恼Z句，完成該功能。#define MAXSTRLEN 255typedef unsigned char SStringMAXSTRLEN+1; /0號單元存放串長int Index(SString

9、S, SString T, int pos) if(pos=1&pos=S0) i=pos; j= (4) ; while(i=S0 & jT0) return (7) ; else return 0; else return 0; 3. 用鏈表實現(xiàn)的簡單項選擇擇排序。設(shè)鏈表頭指針為L, 鏈表無頭結(jié)點，請?zhí)顚戇m當(dāng)?shù)恼Z句，完成該功能。void SelectSort(LinkList L)p=L;while(p)q=p; r=q-next; while( r )if( (8) ) q=r;r= (9) ;tmp=q-data; q-data=p-data; p-data=tmp; p= (10)

10、;算法設(shè)計題16分1.8分一個帶有頭結(jié)點的單鏈表，假設(shè)該鏈表只給出了頭指針L。在不改變鏈表結(jié)構(gòu)的前提下，請設(shè)計一個盡可能高效的算法，查找鏈表中倒數(shù)第k個位置上的結(jié)點k為正整數(shù)，假設(shè)查找成功，那么打印該結(jié)點的值，并返回1；否那么，只返回0。鏈表結(jié)構(gòu)定義為：typedef struct Lnode ElemType data; struct Lnode *next; LNode, *LinkList;2、(8分) 下題中任選一題1給定一棵赫夫曼樹T，編寫算法，求該赫夫曼樹T的帶權(quán)路徑長度。赫夫曼樹T采用如下定義的存儲結(jié)構(gòu)：typedef struct BiTNodeTElemType data;

11、/此處data代表結(jié)點的權(quán)值struct BiTNode *lchild, *rchild;BiTNode, *BiTree;2假設(shè)一棵二叉樹以二叉鏈表表示，元素值為整數(shù)，且元素值無重復(fù)，編寫算法，打印以元素值等于某個給定的整數(shù)的結(jié)點為根的子樹中的各個葉結(jié)點。二叉樹T采用如下定義的存儲結(jié)構(gòu)：typedef struct BiTNodeTElemType data; struct BiTNode *lchild, *rchild;BiTNode, *BiTree;3設(shè)計一算法，要求將二叉樹的葉結(jié)點按從左到右的順序連成一個單鏈表，表頭指針為head, 二叉樹按二叉鏈表方式存儲，鏈接時用葉結(jié)點的右指

12、針域來存放單鏈表指針，分析算法的時間、空間復(fù)雜度。假設(shè)二叉樹T采用如下定義的存儲結(jié)構(gòu)：typedef struct BiTNodeTElemType data;struct BiTNode *lchild, *rchild;BiTNode, *BiTree;填空題O(1) 隨機存取80防止數(shù)組下標(biāo)越界Head【Head【Tail【TailLS】A3 A5 A7活動 活動之間的先后關(guān)系該有向圖無環(huán)DEF選擇題1.D 2.C 3.D 4.C 5.A6.B 7.C 8.B 9.D 10.D判斷題1. 2. 3. 4. 5.6. 7. 8. 9. 10.應(yīng)用題(1)鄰接矩陣：鄰接表：(2)深度優(yōu)先搜索

13、樹為：(3)最小生成樹：(1)二叉排序樹如下：平均查找長度ASL=(1+2X2+4X3+3X4)/10=2.9(2)按照右子樹根節(jié)點左子樹的順序遍歷該二叉樹，即可得到從大到小的順序(3)(4)eq oac(,1)25、12、7、15、34、47、65、47+、16、79eq oac(,2)16、15、12、7、25、47、65、79、47+、34eq oac(,3)初始堆：79、47+、65、34、16、47、12、7、25、15第一趟排序后：65、47+、47、34、16、15、12、7、25、79二叉樹表示方法也可程序填空題Lp-next = sp = s1i = i - j + 2j =

14、 1i j + 1q-data r-datar-nextp-next算法設(shè)計題三種根本思路，1設(shè)一指針p指向鏈表的第1個結(jié)點，之后找到離p距離為k的結(jié)點q如果有的話，然后p與q同時移動，直到q指向鏈表尾部。2計算出單鏈表的長度，從而計算出要查找的節(jié)點在正向的位置，再從頭遍歷，將其找出。3將單鏈表所有節(jié)點入棧，出棧過程中找到第K個節(jié)點。第一種思路可得總分值，后兩種扣2分。第二種方法參考代碼：int Search(LinkList L, int k)Lnode *p;int length = 0, i;if(!L | !L-next) return -1;p = L-next;while(p)le

15、ngth+;p = p-next;if(length next;for(i=0; inext;printf(“該元素為：%dn, p-data);return p-data;(1)int Hvalue(BiTree T, int h)int lvalue, rvalue;if(!T) return 0;if(T-lchild = NULL & T-rchild = NULL)return h*T-data;lvalue = Hvalue(T-lchild, h+1);rvalue = Hvalue(T-rchild, h+1);return lvalue + rvalue;(2)采用先序遍歷方式遍歷整棵樹，設(shè)置標(biāo)志位，標(biāo)識是否找到所需節(jié)點，假設(shè)找到，那么打印其子樹，同時后續(xù)監(jiān)視是否已經(jīng)返回，假設(shè)返回那么關(guān)閉標(biāo)志，停止打印bool flag=false;int Print(BiTree T, int k)if(!T) return 0;if(T-data = k) flag = true;if(flag)printf(“%d , T-data);Print(T-lchild, k);Print(T-rchild, k);if(T-data = k) flag=false;3采用先序遍歷方式遍歷整棵樹，如果找到葉子結(jié)點，那么將其串到鏈表中。bool Fi