數(shù)字結構數(shù)據(jù)結構題目

1、數(shù)據(jù)結構題目(手打整理版)鳴謝、同學的拍攝一、選擇題（10*2=20 分）1. 在一個長度為 n 的順序表中順序搜素一個值為 x 的元素時，在等概率的情況下，搜索成功的數(shù)據(jù)平均比較次數(shù)為_ C 。等差數(shù)列求和：（1+2+3+。+n）/2n=(n+1)/2A、nB、n/2C、(n+1)/2D、(n-1)/2間的B關系。2. 樹型結構對應的是數(shù)據(jù)元：書上 146.。可以復習鏈式和樹和圖各個之間的元素關系。A、一一對應B、一對多C、多對多D、離散3. 設有一個二維數(shù)組 A1020，按行存放與續(xù)的空間中，A00的地址是200，每個數(shù)組元素占2 個字，則A62的地址為_ D 。10代 表 有 十 行 ，

2、 20代 表 每 行 有20個元 素 ， 所 以A62=(6*20+2)*2+200=444.因為數(shù)組是從 A【0】【0】開始，所以前面應該是有六行。（特別注意）A、226B、322C、341D、4444. 非空的循環(huán)單鏈表的尾結點（由 p 所指向）滿足_D。因為要循環(huán)，所以尾節(jié)點必須要指向頭結點。應該是這樣，如果有什么疑問，再去看看書上關于循環(huán)鏈表的程序，看看是怎么回事，書上的東西是標準，重視?？赡苓@道題目打錯了，NULL 不該有那么多。A、p-next=NULL B、p=NULL C、p-next=NULL D、p=5. 設有一個廣義表 A(x，(a，b)，(x，(a，b)，y)，運算 H

3、ead(Head(A)的執(zhí)行結果為 A。書上 126 頁關于廣義表的定義，重點復習 5.3.1.。理解！重點！A、xB、(a，b)C、(x，(a，b)D、A6. 在一棵具有 n 個結點的二叉樹，二叉鏈表中的空指針域個數(shù)等于 C。自己可以畫一棵簡單的二叉樹，看看規(guī)律。符合一般性就好了。如果問題，看看關于二叉樹的空指針到底是怎么回事，書上 161 頁圖 7.9A、nB、n-1C、n+1D、2*n7. 在一棵完全二叉樹中，若為 i 的結點存在左孩子，則左孩子為_A _。同理，也可以花一顆很簡單的完全二叉樹，結點的自己看出來。A、2iB、2i-1C、2i+1D、2i+28.通圖的生成樹是包含圖中所有頂

4、點的一個C子圖。書上 210 頁生成樹和最小生成樹的概念。A、極小B、連通C、極小連通D、無環(huán)9.對 5 個不同的數(shù)據(jù)元素進行直接排序，最多需要進行次比較。（B）了解直接排序的含義。書上 276 頁有兩個公式，好好看看。A、8B、10C、15D、2510. 設散列地址空間為 0m-1，k 為表項的關鍵碼，散列函數(shù)采用除留余數(shù)法，即 Hash(k)=k%p。為了減少發(fā)生的頻率，一般取 p 為 B。書上 264 頁，除留余數(shù)法。A、mB、小于等于 m 的最大質數(shù)C、大于 m 的最小質數(shù)D、小于等于 m 的最大合數(shù)二、填空題（6*1=6 分）1. 對于長度為 18 的有序順序表，若采用折半搜索，嘖搜

5、索第 15 個元素的搜索次數(shù)為_4。書上 238 頁，看看二分查找的程序和概念，這很重要！再看看例題 9.1、注意，結合程序和例題看，自己動手做做到底是怎么回事，這個程序一定要背下來，重點！2. 在一棵樹中，根結束沒有前驅結點，_葉子結點沒有后繼結點。3. 從一個順序結構的循環(huán)隊列中增加一個元素時，需要隊列長度加一。這個我是自己寫的，不一定對，你別人的、4. 已知二叉樹有 16 個葉子結點， 該二叉樹總結點數(shù)至少有1+2+2*2+2*2*2+2*2*2*2_個。（這其實就是一個滿二叉樹）5.一棵樹德廣義表表示為 a(b(c,d(e,f),g(h),i(j,k(x,y)，結點k 的所有先祖的結點

6、數(shù)為2個重點！。書上 126 頁關于廣義表的定義，重點復習 5.3.1.。理解！重點！最好能結合畫出他的樹的樣子。三、（6 分）給出一組關鍵字 T=（35,67,18,29,53,44,9,21）要求從小到大進行排序，試給出快速排序。（選第一個為樞軸）重點體會 283 頁的快速排序的過程，只要滿足左邊小，右邊大就好！四、（6 分）已知一組關鍵字為4，9,1,0,8,6,3,5,2,7，按表中的元素順序依次到一顆初始為空的二叉排序樹中，畫出該二叉排序樹，并求在等概率情況下查找成功的平均查找長度。書上 245 頁，例題 9.1、好好看看。了解二分查找的過程，會畫這棵二叉查找樹。重點！看看二分查找的

7、程序，在 238 頁，變化圖邊看程序，程序是指導。這個程序是重點。最好能背下來！初始排列3567第 1 趟排序結果5344第 2 趟排序結果918292135534467918212935446753五、（8 分）已知一顆二叉樹的靜態(tài)數(shù)組表示（即順序表示）如下，其中#表示空指針，請畫出該二叉樹，并分別寫出該二叉樹的前序、中序和后序遍歷的序列。0123456789101112前序序列： ABDEGHCFH中序序列：DBGEHAFLC后序序列：_DGHEBLFCA_ABCDEFHGL書上 165 頁。看看二叉樹遍歷的定義、重點。再仔細看看做做這道題。重點！ABCDEF#GH#L六、（8 分）假定無

8、向圖 G 有 6 個頂點0,1,2,3,4,5，9 條邊依次為0，1，0,2，0,4，1,2，2,3，2,4，3,4，4,5。（1）請畫出該無向圖；（2）建立圖 G 的鄰接表；（注意：鄰接頂點按升序）（3）根據(jù)鄰接表，寫出總頂點 3 出發(fā)，按深度優(yōu)先搜索法進行遍歷的結點序列。（3）鄰接表好好看看書上 202 圖 8.6，再自己做做題目。七、八、應用 Prim（姆）算法求解連通圖的最小生成樹。要求按如下格式在構造最小生成樹過程中順序選出的各條邊，并畫出最小生成204315321450樹。0612345012345其實這個和離散差不多。結合知識去做吧。好好看看書吧。始頂點號終頂點號權值22九、算法

9、設計題（4 小題，共 34 分）1.（10 分）設計算法，對包含 n 個的數(shù)組 R0,n-1實現(xiàn)遞增有序的直接選擇排序，數(shù)據(jù)類型和函數(shù)參考如下。typedef char InfoType10;typedef struct/*類型*/key;/*關鍵字項*/Info Typedata;/*其他數(shù)據(jù)項，類型為 InfoType*/Rectype;void SelectSort(RecType R,n)/*對 R0,n-1按遞增有序進行直接選擇排序*/程序：286 頁，看看程序和過程。其實就是以前學習的選擇法。最好你會寫這個程序。！重點啊。2.（8 分）設計算法，在有序表 R0,n-1中進行二分查找

10、法查找關鍵字為 k 的。成功時返回的位置，失敗時返回-1。數(shù)據(jù)類型和函數(shù)如下。typedef structKeyType key;/*KeyType 為關鍵字的數(shù)據(jù)類型*/InfoType data;/*其他數(shù)據(jù)*/NodeType;Typedef NodeType SeqListMAXL;/*順序表類型*/BanSearch (SeqList R,n,KeyType k)程序：書上 238 頁.。重點！最好能記下來。這個很重要！3.（8 分）設計函數(shù) F 的算法判斷已知字符串是否為回文串，例如：字符串“abcde”經過 F 處理后，返回-1，字符串“abcba”經過 F 處理后，返回 1.（

11、字符串的數(shù)據(jù)結構自定）/文件名：exp1-3.cpp#include #include #define MAX 100/字符串的最大長度func(char s)flag=1;i,j,slen=strlen(s);/slen 為字符串 s 的長度for (i=0,j=slen-1;ilchild=NULL&b-rchild=NULL)n=n+1;LeafNpdes(b-lchild);LeafNpdes(b-rchild);最后在給你提及個意見:去復習下以下內容，可能會出現(xiàn)在天空選擇，判斷題里面。1. 邏輯結構類型。書上 5 頁2.結構類型。書上 7 頁3.算法：書上 11 頁4. 算法設計的目標：書上 14 頁、5. 棧的定義。“先進后出”，一定要理解。比如：asdfgh 近棧，出棧的順序應該是 hgfdsa去看看書上的題目，60 頁的例題3.1 和 3.26. 還有隊列，：“先進先出”比如 asdfhg 進入隊列，出來的時候也是按照 asdfhg7. 重點是二叉樹和查找以及排序。二分查找一定要背下來。排序的幾種排序一定要搞清楚它屬于哪一類，不能，多去看看，試著背幾個程序。8.排序：直接排序，二分排序，排序，重點看看直接排序的過程。注意排序的