《數(shù)據(jù)結構》期末考試試卷試題及答案2套

《數(shù)據(jù)結構》期末考試試卷試題及答案一、簡答題（每題5分，共20分）1、一棵有n個結點的k叉樹采用k叉鏈表存儲，空鏈域的總數(shù)目是多少？寫出求解過程。2、在圖的遍歷中，設置訪問標志數(shù)組的作用是什么？3、折半查找的前提條件是什么？4、分析冒泡排序的最好性能和最壞性能（性能即關鍵字比較次數(shù)和移動元素的次數(shù)）。二、單項選擇題（每題1分，共10分）1、棧和隊列的共同特點是()。A）只允許在端點處插入和刪除元素 B）都是先進后出C）都是先進先出 D）沒有共同點2、100個結點的完全二叉樹采用順序存儲，從1開始按層次編號，則編號最小的葉子結點的編號應該是（）。A)100B)49C)50D)513、在順序存儲的線性表上R[3]上，從前向后進行順序查找。若查找第一個元素的概率是1/2，查找第二個元素的概率是1/3，查找第三個元素的概率是1/6。則查找成功的平均查找長度為（）。A）7/3B）2C）3D）5/34、在一個有n個頂點的有向圖中，若所有頂點的出度之和為s，則所有頂點的入度之和為（）A)n-sB)nC)sD)s-15、設某二叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為Nl，度數(shù)為2的結點數(shù)為N2，則下列等式成立的是（）。A)N0=N1+1B)N0=Nl+N2C)N0=N2+1D)N0=2N1+l6、設有6個結點的無向圖，該圖至少應有()條邊才能確保是一個連通圖。A）5B）6C）7D）87、已知單鏈表中的指針p所指的結點不是鏈尾結點，若在p結點后插入s結點，應執(zhí)行（）。A)s->next=p

;p->next=s

; B)p->next=s

;s->next=p

;C)s->next=p->next

;p=s

; D)s->next=p->next

;p->next=s

;8、設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為（）。 A)第i行非0元素的個數(shù)之和B)第i列非0元素的個數(shù)之和 C)第i行0元素的個數(shù)之和 D)第i列0元素的個數(shù)之和9、排序時掃描待排序記錄序列，順次比較相鄰的兩個元素的大小，逆序時就交換位置。這是（）排序方法的基本思想。A）堆排序 B）直接插入排序 C）快速排序 D）冒泡排序10、設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（）方法可以達到此目的。A）快速排序 B）堆排序 C）歸并排序 D）基數(shù)排序三、填空題（每空2分，共20分）1、下面算法的時間復雜度是。i=1;while(i<=n)i=i*2;2、設線索二叉樹中，判斷p所指向的結點為葉子結點的條件是____________________________________。2、對任意一棵有n個結點的樹，這n個結點的度之和為。3、Prim算法適合求解連通網的最小生成樹。（填稀疏或稠密）4、關鍵路徑是從源點到匯點的路徑。5、深度為k的二叉樹中最少有個結點，最多有個結點。6、設有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓撲序列為____________________7、根據(jù)初始關鍵字序列(25，22，11，38，10)建立的二叉排序樹的高度為_________。 8、用某種排序方法對關鍵字序列（25，84，21，47，15，27，68，35，20）進行排序時，序列的變化情況如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84則所采用的排序方法是。四、構造題（共30分）1、(8分)設一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求：①用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結構；（2分）②將該樹轉化成對應的二叉樹。（2分）③寫出該樹的先序和后序遍歷序列。（4分）2、（8分）某圖的鄰接表存儲結構為圖1所示：①畫出從V1出發(fā)的深度優(yōu)先生成樹；②給出該圖的鄰接矩陣存儲結構。圖1第四題第2小題圖3、（8分）一個線性序列（36，13，40，63，22，6），假定采用散列函數(shù)Hash(key)=key%7來計算散列地址，將其散列存儲在A[0~9]中，采用線性探測再散列解決沖突。構造哈希表，并計算等概率情況下的查找成功和不成功的平均查找長度。4、（6分）欲對關鍵字{36，15,13，40，63，22，6}從小到大排序，若采用堆排序，寫出將關鍵字序列建初堆過程。五、算法設計題（每小題10分，共20分）注：只要求給出描述算法的子函數(shù)，不需要編寫完整的實現(xiàn)程序。1、編寫折半查找算法。（遞歸、非遞歸均可）2、已知二叉樹采用二叉鏈表存放，該結點結構為：LChild data RChild level編寫算法，將二叉樹中每個結點所在的層次值置入相應的level域?！稊?shù)據(jù)結構》期末考試試卷2參考答案一、簡答題1、n個結點的k叉樹采用k叉鏈表存儲，鏈域總數(shù)為k*n，又：n=B+1,B為分支總數(shù)即非空鏈域總數(shù)，B=n-1,所以空鏈域總數(shù)為：（k-1）*n+1。2、訪問標志數(shù)組的作用是：保證圖中的每個頂點都被訪問到，且僅訪問一次。3、折半查找的前提條件是1）列表元素順序存儲；2）列表元素按關鍵字有序存儲；4、冒泡排序最好情況：移動元素次數(shù)為0，關鍵字比較次數(shù)為：n-1次；冒泡排序最壞情況：移動元素次數(shù)為3n*(n-1)/2,關鍵字比較次數(shù)為n*(n-1)/2。二、選擇題1.A 2.D 3.D 4.C 5.C6.A 7.D 8.B 9.D 10.B三、填空題1、O（log2n） 2、p->ltag==1&&p->rtag==13、n-1 4、稠密 5、最少k,最多2k-1 6、1,4,2,3 7、高度為4 8、快速排序四、構造題1.1)該樹的孩子兄弟表示法為：（2分）2)轉化的二叉樹為:（2分）3）先序遍歷序列為：ABECFGD（2分）后序遍歷序列為:EBFGCDA（2分）2.1）此為有向圖的鄰接表表示法，該圖為：2）深度優(yōu)先搜索得到的遍歷序列為：V1，V4，V5，V6，V2，V7，V3;深度優(yōu)先生成樹為：3）其鄰接矩陣表示法為：頂點數(shù)組：鄰接矩陣：1 V12 V23 V34 V45 V56 V67 V70 0 0 1 1 0 10 0 0 1 0 0 00 0 0 0 0 1 10 0 0 0 0 0 00 1 0 0 0 1 00 0 0 0 0 0 00 0 1 1 1 0 03、1）構造的哈希表為：（4分）地址 0 1 2 3 4 5 6 7 8 9元素 63 36 22 40 13 6 比較次數(shù) 1 1 2 1 1 2 2）（2分）查找成功時的ＡＳＬ＝（１＋１＋２＋１＋１＋２）／６＝８/６ｏｒ４/３（2分）查找不成功時的ＡＳＬ＝（４＋３＋２＋１＋１＋４＋３）／７＝１８/７4、據(jù)題意，欲得到遞增有序，需要建大根堆（1分）。建初堆過程如下：五．算法設計題1、折半查找算法：1）非遞歸算法：intBinSearch(RecordListL,KeyTypek){low=1;high=L.length;while(low<=high){mid=(low+high)/2;if(L->r[mid].key==k)returnmid;elseif(k<L->r[mid].key)high=mid-1;elselow=mid+1;}return0;}2)遞歸算法intBinSearch(RecordListL,KeyTypek，intlow,inthigh)//首次調用，low=1，high=L.length;{if(low<=high){mid=(low+high)/2;if(L->r[mid].key==k)returnmid;elseif(k<L->r[mid].key)return(BinSearch(L,k,low,mid-1));elsereturn(BinSearch(L,k,mid+1,high));}}2、二叉樹中每個結點的level域置值算法：利用二叉樹的先序遍歷給每個結點的level域置值。voidSetLevel（BiTreebt，intlayer）//首次調用時，bt參數(shù)為二叉樹的根指針，layer參數(shù)值為1。 {if（bt） {bt->level=layer; SetLevel（bt->lchild，layer+1）； SetLevel(bt-)rchild，layer+1）；} }注：此題也可以借助層次遍歷完成?！稊?shù)據(jù)結構》期末考試試卷及答案一、簡答題（每題5分，共20分）1、具有n個結點的k叉樹，若采用k叉鏈表存儲，則空鏈域有多少個？（要求寫出求解步驟）。2、分析二叉排序樹的性能（最好、最壞和平均查找性能）。3、希爾排序基本思想。4、圖遍歷中，設置訪問標志數(shù)組visited[]的作用。二、單項選擇題（每題1分，共10分）1、在一棵平衡二叉排序樹中，每個結點的平衡因子的取值范圍是（）A)-1~1 B)-2~2 C)1~2 D)0~12、在單鏈表中，下列說法正確的是（）A)單鏈表中頭結點是必不可少的；B)單鏈表中頭指針是必不可少的；C)在單鏈表中可以實現(xiàn)隨機存??；D)單鏈表的存儲密度小于順序表3、假設以數(shù)組A[M]存放循環(huán)隊列的元素，其頭尾指示器分別為front和rear，則當前隊列中的元素個數(shù)為()。A)rear-front+1B)(rear-front+1)%MC)(front-rear+M)%MD)(rear-front+M)%M4、已知廣義表L=((a,b,c),(d,e,f)),運用下列（）運算可以得到結果：e。A)head（tail(L)）B)tail(head(L))C)head(tail(head(tail(L))))D)head(tail(tail(head(L))))5、線索二叉樹中，某結點p是葉子結點,下列（）表達式的值為真。A)p->lchild==NULL

B)p->ltag==1&&p->rtag==1C)p->ltag==0

D)p->lchild==NULL&&p->rchild==NULL6、一個具有567個結點的完全二叉樹的高度為（

）A)9

B)10

C)11

D)127、具有n個頂點的強連通圖，至少有（

）條邊A)n-1

B)n

C)n(n-1)

D)n(n-1)/28、在含n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為（）A)eB)2eC)n2-eD)n2-2e9、對關鍵字序列(20,15,14,18,36,40,10,21)進行快速排序，以第一個關鍵字為基準得到的一趟劃分后的結果是（）。A)(10,15,14,18,20,36,40,21)B)(10,15,14,18,20,40,36,21)C)(10,15,14,20,18,40,36,21)D)(15,10,14,18,20,36,40,21)10、下列四種排序方法中，不穩(wěn)定的方法是()。A)冒泡排序B)直接插入排序C)歸并排序D)快速排序三、填空題（每空2分，共20分）1、一個算法中，基本操作的語句頻度為(n3+n2log2n+14n)/n2，該算法的時間復雜度為()2、65個結點的完全二叉樹，按層次，從左到右編號，則最后一個非葉子結點的編號為()。3、折半查找的兩個前提條件分別是（）和（）4、一個有序表為{4，8，12，16，20，24，28}，采用折半查找法查找值為24時需要比較（）次。5、有向圖的鄰接表表示法中，第i條鏈上邊表結點的個數(shù)為該頂點的（）。6、已知一個帶頭結點的鏈棧，其頭指針為top；指針s指向一個新結點，要將結點s進棧，則進棧的語句應為：（）和（）。7、有一種排序算法，其時間復雜度為O（n2），關鍵字比較次數(shù)與待排序記錄的初始排列順序無關且排序不穩(wěn)定，則該排序算法是（）8、對二叉排序樹進行中序遍歷，會得到一個（）序列。四、構造題（每題6分，共30分）1、假定用于通信的某電文僅由8個字母構成，各字母在電文中出現(xiàn)的頻率分別為（12，5，3，7，14，21，9，15）。請完成：1）構造哈夫曼樹；2）為這8個字母設計不等長的Huffman編碼，并計算WPL。2、已知一個圖的頂點為A、B、C、D，其鄰接矩陣的下三角元素全為0（包括主對角線元素），其他元素均為1。請畫出該圖，并給出其鄰接表。3、用普利姆算法從頂點A出發(fā)，構造圖1所示連通網的最小生成樹（寫出過程）。圖14、一個線性序列{38，25，74，63，52，48}，假定采用散列函數(shù)Hash(key)=key%7來計算散列地址，將其散列存儲在A[0~9]中，采用線性探測再散列解決沖突。構造哈希表，并計算等概率情況下的查找成功和不成功的平均查找長度。5、對序列{57，40，38，11，13，34，48，75，6，19，9，7}，采用堆排序算法進行遞減排序，請構造相應的初始堆即建初堆（只寫初堆結果即可）。五、算法設計題（每題10分共20分）注：算法設計題只要求給出描述算法的子函數(shù)，不需要編寫完整的實現(xiàn)程序。1、在一個帶頭結點的循環(huán)鏈隊列中只有尾指針rear，請給出這種隊列的入隊和出隊操作的實現(xiàn)過程。隊列的定義如下：typedefstructNode{

QueueElementType

data;

/*數(shù)據(jù)域*/

structNode

*next;

/*指針域*/}LinkQueueNode,*LinkQueue;2、假設二叉樹上的結點值各不相同，設計一個在二叉樹中求值為e的結點的雙親結點。函數(shù)名已給出，如下：/*若e有雙親，則返回雙親結點指針；若e是根結點或二叉樹中無e結點，則返回NULL*/BiTNode*Parent(BiTreebt，ElemTypee)《數(shù)據(jù)結構》期末考試試卷1參考答案一、簡答題（5分*4=20分）1、n個結點的k叉樹，共nk個鏈域；分支樹為n-1個，即n-1個非鏈域，則空鏈域有nk-n+1個2、當二叉排序樹的左右子樹比較均衡時，查找性能最好，此時時間復雜度為O(nlogn)；當二叉排序樹每個結點為單分支時，查找性能最差，與順序查找類似，此時時間復雜度為O(n2)。但二叉排序的平均查找時間復雜度為O(nlogn)。3、按某個間隔，將待排序記錄序列分割成若干個子序列，分別進行直接插入排序；繼續(xù)縮小間隔，對每個子序列進行直接插入排序；最后再對全部記錄進行一次直接插入排序。4、防止重復訪問；防止遺漏訪問。 二、選擇題（1分*10=10分）(1~5) A D D C B(6~10) B B D B D三、填空題（2分*10=20分）1、O(n)或O(n+logn) 2、323、元素有序順序存儲 4、25、出度 6、s->next=top->next;top->next=s;7、簡單選擇排序 8、遞增或非遞減或從小到大四、構造題（6分*6=30分）1、WPL=21*2+(14+15+9+12+7)*3+(5+3)*4=245(該哈夫曼樹有多種形態(tài))2、3、4、構造的哈希表為：0 1 2 3