專升本《數(shù)據(jù)結(jié)構(gòu)》主觀題常見題型及答案總結(jié)

專升本《數(shù)據(jù)結(jié)構(gòu)》主觀題常見題型及答案總結(jié)：專升本《數(shù)據(jù)結(jié)構(gòu)》主觀題常見題型及答案總結(jié)：一、名詞解釋1、隊(duì)列：是一種先進(jìn)先出的線性表,它只允許在表的一段進(jìn)行插入,而另一端刪除元素,允許插入的一端叫做隊(duì)尾,允許刪除的一端稱為隊(duì)首。2、滿二叉樹：是一棵深度為k的,且有(2^k)-1個(gè)結(jié)點(diǎn)的二叉樹。3、折半查找：取表的中間位置的記錄關(guān)鍵字和所給關(guān)鍵字進(jìn)行比較。4、關(guān)鍵字：是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值,用它可以識(shí)別一個(gè)或一組數(shù)據(jù)元素。5、循環(huán)鏈表：是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn),整個(gè)鏈表形成一個(gè)環(huán)。6、分塊查找：先確定待查記錄所在的塊(子表),然后在塊中順序查找。7、動(dòng)態(tài)查找表:在查找過程中同時(shí)插入查找不存在的數(shù)據(jù)元素,或者從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素。8、雙向鏈表：采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表,每個(gè)結(jié)點(diǎn)除一個(gè)數(shù)據(jù)域外,還有兩個(gè)指針域,其一指向直接前驅(qū),另一指向直接后繼。9、循環(huán)隊(duì)列：循環(huán)隊(duì)列是將隊(duì)列的數(shù)據(jù)區(qū)看成頭尾相接的循環(huán)結(jié)構(gòu)。10、二叉樹:是一種樹型的結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)之多有兩棵子樹，且有左右之分，不可任意顛倒。11、順序存儲(chǔ)：用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表的元素。12、有向完全圖：有n(n-1)條邊的有向圖稱為有向完全圖(圖中每個(gè)頂點(diǎn)和其余n-1個(gè)頂點(diǎn)都有弧相連)。13、查找表:是由同一類型的數(shù)據(jù)元素或記錄構(gòu)成的集合。14、排序:就是按關(guān)鍵字值的遞增或遞減的次序，把文件中的各記錄一次排列起來，可使一個(gè)無序文件變成有序文件的一種操作。二、簡(jiǎn)答題1、二分查找法的基本思想。折半(二分)查找的基本思路:先取表的中間位置的記錄關(guān)鍵字和所給關(guān)鍵字進(jìn)行比較,若相等,則查找成功,如果給定關(guān)鍵字比該記錄的關(guān)鍵字小,則說明所要查找的記錄只可能在表的前半部分,反之,則在后半部分,重復(fù)步驟,每一次比較就可以將查找范圍縮小一半,直到找到給定的關(guān)鍵字的記錄,查找成功,找不到為查找失敗.2、簡(jiǎn)述深度優(yōu)先遍歷的方法。假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)均未被訪問過,則深度優(yōu)先搜索可從某個(gè)頂點(diǎn)V出發(fā)，首先訪問此頂點(diǎn)(稱此頂點(diǎn)為初始點(diǎn))，然后依次從V的任一個(gè)未被訪問的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷,直到圖中所有與V有路徑相通的頂點(diǎn)都被訪問到，若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作為初始點(diǎn)，重復(fù)上述步驟，直到圖中所有頂點(diǎn)都被訪問過為止。3、簡(jiǎn)述順序表和鏈表各自的缺點(diǎn)。順序表：1）結(jié)點(diǎn)中只存放數(shù)據(jù)元素本身的信息,無附加內(nèi)容。2）可直接存取數(shù)據(jù)元素。3）存取操作速度較快。4）插入.刪除數(shù)據(jù)元素時(shí),由于需要保持?jǐn)?shù)據(jù)元素之間的邏輯關(guān)系,必須大量移動(dòng)元素,因此實(shí)現(xiàn)起來較慢。5）順序存儲(chǔ)是一種靜態(tài)結(jié)構(gòu),存儲(chǔ)密度大,空間利用率低,預(yù)分配空間大小難以確定。鏈表：1）.結(jié)點(diǎn)中除存放數(shù)據(jù)元素本身的信息外,還需存放附加的指針。2）.不能直接存取數(shù)據(jù)元素,需順鏈查找,存取速度較慢。3）.插入.刪除元素時(shí)不必移動(dòng)其他元素,速度較快。4）.鏈?zhǔn)酱鎯?chǔ)是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu),空間利用率高,存儲(chǔ)密度小,不存在預(yù)分配空間問題。4、簡(jiǎn)述線性結(jié)構(gòu)的特點(diǎn)。線性結(jié)構(gòu)的特點(diǎn)是：除第一個(gè)元素和最后一個(gè)元素外，每個(gè)數(shù)據(jù)元素都有唯一的前驅(qū)和唯一的后繼，第一個(gè)元素沒有前驅(qū)，最后一個(gè)元素沒有后繼，關(guān)系是一對(duì)一的。5、樹和二叉樹之間的區(qū)別。二叉樹的一個(gè)結(jié)點(diǎn)至多有2個(gè)子樹，樹則不然。二叉樹的一個(gè)結(jié)點(diǎn)的子樹有左右之分，而樹則沒有此要求。6、簡(jiǎn)述圖的廣度優(yōu)先搜索遍歷的方法。1）.從圖中某個(gè)頂點(diǎn)V0出發(fā)，首先訪問V0，依次訪問V0的各個(gè)未被訪問的鄰接點(diǎn)。2）.分別從這些鄰接點(diǎn)(端結(jié)點(diǎn))出發(fā),依次訪問各個(gè)未被訪問的鄰接點(diǎn)，訪問時(shí)應(yīng)保證：:如果Vi和Vk為當(dāng)前結(jié)點(diǎn)，且Vi在Vk之前被訪問，則Vi的所有未被訪問的鄰接點(diǎn)應(yīng)在Vk的所有未被訪問的鄰接點(diǎn)之前訪問。3）.重復(fù)步驟2，直到所有結(jié)點(diǎn)均沒有未被訪問的鄰接點(diǎn)。4）.若此時(shí)還有頂點(diǎn)未被訪問，則選一個(gè)未被訪問的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過程，直至所有頂點(diǎn)均被訪問過為止。7、什么叫遍歷二叉樹？寫出對(duì)下圖所示二叉樹進(jìn)行先序、中序、后序遍歷結(jié)點(diǎn)序列。二叉樹遍歷是指按照一定次序訪問樹中所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅被訪問一次的過程。先序遍歷序列：中序遍歷序列：后序遍歷序列：三、論述題1、試表述各種內(nèi)部排序方法并論述如何選擇。（1）若n(待排序的記錄數(shù)目)較小，可采用直接插入排序或直接選擇排序；（2）若記錄的初始狀態(tài)已經(jīng)按關(guān)鍵字基本有序，則選用直接插入排序或冒泡排序法。（3）若n較大，則采用時(shí)間復(fù)雜度為0（nlog2n）的排序方法：快速排序、堆排序或歸并排序。但快速排序、堆排序都是不穩(wěn)定排序，若要求穩(wěn)定排序，則可選用歸并排序。（4）基數(shù)排序可在0(dxn)時(shí)間內(nèi)完成對(duì)n個(gè)記錄的排序，d是指邏輯關(guān)鍵字的個(gè)數(shù)，一般遠(yuǎn)小于n。（5）當(dāng)記錄本身的信息量很大時(shí)，為避免大量時(shí)間用在移動(dòng)數(shù)據(jù)上，可用鏈表作為存儲(chǔ)結(jié)構(gòu)，插入排序和歸并排序都容易在鏈表上實(shí)現(xiàn)，但有的排序方法，如快速排序和堆排序在鏈表上很難實(shí)現(xiàn)。2、折半查找法的基本思想。折半(二分)查找的基本思路:先取表的中間位置的記錄關(guān)鍵字和所給關(guān)鍵字進(jìn)行比較,若相等,則查找成功,如果給定關(guān)鍵字比該記錄的關(guān)鍵字小,則說明所要查找的記錄只可能在表的前半部分,反之,則在后半部分,重復(fù)步驟,每一次比較就可以將查找范圍縮小一半,直到找到給定的關(guān)鍵字的記錄,查找成功,找不到為查找失敗。四、解答題3、設(shè)待排序的表有10個(gè)元素，其關(guān)鍵字分別為（9，8，7，6，5，4，3，2，1，0）。說明采用直接插入排序方法進(jìn)行排序的過程。4、已知一組關(guān)鍵字為{25，18，46，2，53，39，32，4，74，67，60，11}。按表中的元素順序依次插入到一棵初始為空的二叉排序樹中，畫出該二叉排序樹。求在等概率的情況下查找成功的平均查找長(zhǎng)度和查找不成功的平均查找長(zhǎng)度。二叉排序樹（簡(jiǎn)稱BST）又稱二叉查找（搜索）樹，其定義為：二叉排序樹或者是空樹，或者是滿足如下性質(zhì)（BST性質(zhì)）的二叉樹：若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)值（指關(guān)鍵字值）均小于根結(jié)點(diǎn)值；若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)值均大于根結(jié)點(diǎn)值；左、右子樹本身又各是一棵二叉排序樹。注意：二叉排序樹中沒有相同關(guān)鍵字的結(jié)點(diǎn)。5、W={0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11}建立一顆哈夫曼樹。構(gòu)造哈夫曼樹的過程：（1）給定的n個(gè)權(quán)值{W1，W2，…，Wn}構(gòu)造n棵只有一個(gè)葉結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹的集合F={T1，T2，…，Tn}。（2）在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和。（3）在集合F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合F中。（4）重復(fù)（2）、（3）兩步，當(dāng)F中只剩下一棵二叉樹時(shí)，這棵二叉樹便是所要建立的哈夫曼樹。哈夫曼樹的特點(diǎn)：n1=0：因?yàn)槊看蝺煽脴浜喜?。n=n0+n1+n2=n0+n2=2n0-1。6、設(shè)待排序的表有10個(gè)記錄，其關(guān)鍵字分別為（6，8，7，9，0，1，3，2，4，5）。說明采用快速排序方法進(jìn)行排序的過程?？焖倥判蛩惴ㄊ腔诜种尾呗缘牧硪粋€(gè)排序算法。該方法的基本思想是：1．先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)，記為x。2．分區(qū)過程，將不小于x的數(shù)全放到它的右邊，不大于x的數(shù)全放到它的左邊。（這樣key的位置左邊的沒有大于key的，右邊的沒有小于key的，只需對(duì)左右區(qū)間排序即可）3．再對(duì)左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個(gè)數(shù)。7、設(shè)下圖中的頂點(diǎn)表示村莊，有向邊代表交通路線，若要建立一家醫(yī)院，試問建在哪一個(gè)村莊能使各村莊總體交通代價(jià)最小。普里姆（Prim）算法是一種構(gòu)造性算法，用于構(gòu)造最小生成樹。過程如下：（1）初始化U={v}。v到其他頂點(diǎn)的所有邊為候選邊；（2）重復(fù)以下步驟n-1次，使得其他n-1個(gè)頂點(diǎn)被加入到U中：從候選邊中挑選權(quán)值最小的邊輸出，設(shè)該邊在V-U中的頂點(diǎn)是k，將k加入U(xiǎn)中；考察當(dāng)前V-U中的所有頂點(diǎn)j，修改候選邊：若(j，k)的權(quán)值小于原來和頂點(diǎn)k關(guān)聯(lián)的候選邊，則用(k，j)取代后者作為候選邊?？唆斔箍枺↘ruskal）算法過程：（1）置U的初值等于V（即包含有G中的全部頂點(diǎn)），TE的初值為空集（即圖T中每一個(gè)頂點(diǎn)都構(gòu)成一個(gè)連通分量）。（2）將圖G中的邊按權(quán)值從小到大的順序依次選?。喝暨x取的邊未使生成樹T形成回路，則加入TE；否則舍棄，直到TE中包含(n-1)條邊為止?？唆斔箍査惴ㄇ蠼庾钚∩蓸涞倪^程8、假設(shè)哈希表長(zhǎng)度m=13，采用除留余數(shù)法哈希函數(shù)建立如下關(guān)鍵字集合的哈希表(16，74，60，43，54，90，46，31，29，88，77)，共11個(gè)關(guān)鍵字。解：n=11，m=13，設(shè)計(jì)除留余數(shù)法的哈希函數(shù)為：h(k)=kmodpp應(yīng)為小于等于m的素?cái)?shù)，設(shè)p=13。哈希沖突解決方法：開放定址法：沖突時(shí)找一個(gè)新的空閑的哈希地址。（1）線性探查法線性探查法的數(shù)學(xué)遞推描述公式為：d0=h(k)di=(di-1+1)modm(1≤i≤m-1)非同義詞沖突：哈希函數(shù)值不相同的兩個(gè)記錄爭(zhēng)奪同一個(gè)后繼哈希地址堆積（或聚集）現(xiàn)象。（2）平方探查法平方探查法的數(shù)學(xué)描述公式為：d0=h(k)di=(d0±i2)modm(1≤i≤m-1)查找的位置依次為：d0、d0+1、d0-1、d0+4、d0-4、平方探查法是一種較好