數(shù)字結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)題目

1、數(shù)據(jù)結(jié)構(gòu)題目(手打整理版)鳴謝、同學(xué)的拍攝一、選擇題（10*2=20 分）1. 在一個(gè)長(zhǎng)度為 n 的順序表中順序搜素一個(gè)值為 x 的元素時(shí)，在等概率的情況下，搜索成功的數(shù)據(jù)平均比較次數(shù)為_(kāi) C 。等差數(shù)列求和：（1+2+3+。+n）/2n=(n+1)/2A、nB、n/2C、(n+1)/2D、(n-1)/2間的B關(guān)系。2. 樹(shù)型結(jié)構(gòu)對(duì)應(yīng)的是數(shù)據(jù)元：書(shū)上 146.?？梢詮?fù)習(xí)鏈?zhǔn)胶蜆?shù)和圖各個(gè)之間的元素關(guān)系。A、一一對(duì)應(yīng)B、一對(duì)多C、多對(duì)多D、離散3. 設(shè)有一個(gè)二維數(shù)組 A1020，按行存放與續(xù)的空間中，A00的地址是200，每個(gè)數(shù)組元素占2 個(gè)字，則A62的地址為_(kāi) D 。10代 表 有 十 行 ，

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

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

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

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

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

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

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

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

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

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