數(shù)據(jù)結構（中國海洋大學）智慧樹知到期末考試答案章節(jié)答案2024年中國海洋大學

數(shù)據(jù)結構（中國海洋大學）智慧樹知到期末考試答案+章節(jié)答案2024年中國海洋大學求圖的最小生成樹有兩種算法，普里姆算法適合于求稠密圖的最小生成樹

答案:對二維數(shù)組A[8][9]按行優(yōu)先順序存儲，若數(shù)組元素A[2][3]的存儲地址為1087，A[4][7]的存儲地址為1153，則數(shù)組元素A[6][7]的存儲地址為（）

答案:1207數(shù)據(jù)元素是數(shù)據(jù)的最小單位。

答案:錯線性表的特點是每個元素都有一個前驅和一個后繼。

答案:錯

答案:4線性表中的所有元素都有一個前驅元素和后繼元素。

答案:錯調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。

答案:錯

答案:A具有6個頂點的無向連通圖至少應該有（）條邊。

答案:5設某有向圖的鄰接表中有n個表頭結點和m個表結點，則該圖中有（）條有向邊。

答案:m二路歸并排序的時間復雜度為（）。

答案:O(nlog2n)先序線索二叉樹中如果某個結點的左孩子標志為1，則其左孩子指針指向該結點的（）

答案:先序前驅設有向圖G中的有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，5>，<5，3>，<4，6>，<6，5>}，則該圖的一個拓撲序列為(）

答案:124653設一棵二叉樹的深度為k，則該二叉樹中最多有（）個結點。

答案:2k-1在表長為n的順序表上做插入運算，平均要移動的結點數(shù)為（）

答案:n/2設某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（）存儲方式最節(jié)省運算時間。

答案:雙向循環(huán)鏈表廣義表是（）的推廣。

答案:樹以下關于線性表的敘述，正確的是（）

答案:除第一個和最后一個元素外，其余每個元素都有一個且僅有一個前驅和后繼元素若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數(shù)為（）

答案:11線性表的鏈表存儲結構和順序存儲結構相比，優(yōu)點是（）

答案:便于插入和刪除元素對稀疏矩陣進行壓縮存儲的目的是（）

答案:節(jié)省存儲空間廣義表(a,b,c,d)的長度為（）

答案:4將兩個各有n個元素的遞增有序順序表歸并成一個有序順序表，其最少的比較次數(shù)是（）

答案:n16.（）是由零個或者多個字符組成的有限序列。

答案:字符串三元組用來存儲（）

答案:稀疏矩陣廣義表(a,(a,b),d,e,((i,j),k))的長度是（），深度是（）。

答案:5，3一個稀疏矩陣采用壓縮后，和直接采用二維數(shù)組存儲相比，會失去（）

答案:隨機存取設一組初始記錄關鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關鍵字序列進行一趟歸并后的結果為（）。

答案:15，25，35，50，20，40，80，85，36，70已知棧的最大容量為4。若進棧序列為1，2，3，4，5，6，且進棧和出?？梢源┎暹M行,則可能出現(xiàn)的出棧序列為

答案:3，2，5，4，1，6下列排序算法中，算法（）在進行一趟相應的排序處理結束后不一定能選出一個元素放到其最終位置上。

答案:歸并排序循環(huán)隊列存儲在數(shù)組A[0..m-1],則出隊時的操作為（）

答案:front=(front+1)modm設某棵三叉樹中有40個結點，則該三叉樹的最小高度為（）。

答案:4設一條單鏈表的頭指針變量為head且該鏈表沒有頭結點，則其判空條件是（）。

答案:head==0下面（）方法可以判斷出一個有向圖中是否有環(huán)（回路）

答案:拓撲排序稀疏矩陣的壓縮存儲一般采用（）存儲方式。

答案:三元組表如果在數(shù)據(jù)結構中每個數(shù)據(jù)元素只可能有一個直接前驅，但可以有多個直接后繼，則該結構是

答案:樹廣義表（（（））,a,((b,c),(),d),(((e)))）的長度為（）

答案:4鏈表中邏輯上相鄰的元素其物理地址（）相鄰

答案:不一定設二維數(shù)組a[6,10]，每個數(shù)組元素占用4個存儲單元，若按行優(yōu)先順序存放的數(shù)組元素a[0,0]的存儲地址為860，則a[3,5]的存儲地址是（）

答案:1000在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）

答案:1鏈式存儲的特點是利用指針來表示數(shù)據(jù)元素之間的邏輯關系。

答案:對數(shù)組的運算有存取元素和修改元素。

答案:對廣義表中的元素或者是一個不可分割的原子，或者是一個非空的廣義表。

答案:錯設二叉排序樹上有n個結點，則在二叉排序樹上查找結點的平均時間復雜度為（）。

答案:O(1og2n)在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍

答案:1

答案:B廣義表((a,b),c,d)的表尾是（）

答案:(c,d)設n行n列的下三角矩陣A已壓縮到一維數(shù)組B[0..n*（n+1）/2-1]中，若按行為主序存儲，則A[i,j](i>=j)對應的B中存儲位置為()。

答案:i(i-1)/2+j-1設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為（）。

答案:2e下列四種排序中（）的空間復雜度最大。

答案:快速排序函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為（）。

答案:“STRUCTURE”設有一個二維數(shù)組A[m][n]，假設A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進制表示。

答案:692設用鏈表作為棧的存儲結構則退棧操作（）。

答案:必須判別棧是否為空若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進行二分查找，則查找A［3］的比較序列的下標依次為()。

答案:9，4,2,3具有6個頂點的無向圖至少應該有（）條邊才能確保是一個連通圖。

答案:5不論線性表采用順序存儲結構還是鏈式存儲結構，刪除值為X的結點的時間復雜度均為O(n)。

答案:對在單鏈表中，除了首元結點外，任一結點的存儲位置由其前驅結點的鏈域的值指示。

答案:對設一組初始記錄關鍵字序列為(345，253，674，924，627)，則用基數(shù)排序需要進行（）趟的分配和回收才能使得初始關鍵字序列變成有序序列。

答案:3表示圖的三種存儲結構為鄰接矩陣、鄰接表和邊集數(shù)組

答案:對二維數(shù)組和多維數(shù)組均不是特殊的線性結構。

答案:錯在二叉排序樹中插入一個結點的時間復雜度為（）。

答案:O(n)下列各項鍵值序列中不是堆的為（）

答案:{5，23，16，73，94，72，71，68}設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作（）

答案:模式匹配已知二叉樹的中序序列和后序序列均為ABCDEF，則該二叉樹的先序序列為（）

答案:FEDCBA已知數(shù)組A[0..9,0..9]的每個元素占5個存儲單元，將其按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A[6，8]的地址為（）。

答案:1340一個圖的鄰接矩陣不是對稱矩陣，則該圖可能是（）

答案:無向圖有一組數(shù)據(jù){15，9，7，8，20，1，7，4}，用堆排序的篩選方法建立的初始堆為（）

答案:{1，4，7，8，20，15，7，9}設一組初始記錄關鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結束后前4條記錄關鍵字為（）。

答案:15,40,60,20一個棧的進棧序列是a,b,e.d,e,則棧的不可能的輸出序列是（）

答案:dceab圖的深度優(yōu)先遍歷算法中需要設置一個標志數(shù)組，以便區(qū)分圖中的每個頂點是否被訪問過。

答案:對廣義表的取表尾運算，其結果通常是個表，但有時也可是個單元素值。

答案:錯單鏈表中邏輯上相鄰的元素的物理位置不一定緊鄰。

答案:對用鄰接矩陣作為圖的存儲結構時，則其所占用的存儲空間與圖中頂點數(shù)無關而與圖中邊數(shù)有關。

答案:錯若以S和X分別表示進棧和退棧操作，則對初始狀態(tài)為空的?？梢赃M行的棧操作系列合法的是（）

答案:SSSXXSXX算法的時間復雜度與（）有關

答案:問題的規(guī)模設無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結構進行深度優(yōu)先或廣度優(yōu)先遍歷時的時間復雜度為()；用鄰接表作為圖的存儲結構進行深度優(yōu)先或廣度優(yōu)先遍歷的時間復雜度為()。

答案:O(n2)，O(n+e)以下有關廣義表的表述中，正確的是（）

答案:由0個或多個原子或子表構成的有限序列設串sl=″DataStructureswithJava″,s2=“it″，則子串定位函數(shù)index(s1,s2)的值為（）

答案:18設一組初始記錄關鍵字序列為(45，80，55，40，42，85)，則以第一個記錄關鍵字45為基準而得到一趟快速排序的結果是（）。

答案:42，40，45，55，80，85一個字符串中任意個連續(xù)字符成為該串的子串。

答案:對串是一種特殊的線性表，其特殊性體現(xiàn)在（）

答案:數(shù)據(jù)元素是單個字符廣義表運算：tail(((a,b),(c,(d,e))))=（）。

答案:((c,(d,e)))設有序表中有1000個元素，則用二分查找查找元素X最多需要比較（）次。

答案:10對稀疏矩陣進行壓縮存儲目的是（）。

答案:節(jié)省存儲空間在哈希查找過程中，可用（）來處理沖突。

答案:線性探測法在單鏈表中設置頭結點的作用是插入和刪除首元結點時不用進行特殊處理。

答案:對深度為k的完全二叉樹中最少有（）個結點。

答案:2k-1排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進行比較，將其放入已排序序列的正確位置上的方法稱為（）

答案:插入排序數(shù)據(jù)的最小單位是（）。

答案:數(shù)據(jù)項設一個有序的單鏈表中有n個結點，現(xiàn)要求插入一個新結點后使得單鏈表仍然保持有序，則該操作的時間復雜度為（）。

答案:O(n)廣義表（（a,b,c,d））的表尾是（）。

答案:((a,b,c,d))對于一個具有n個結點的單鏈表，在已知的結點*p后插入一個新結點的時間復雜度為（）,在給定值為x的結點后插入一個新結點的時間復雜度為（)。

答案:O(1),O(n)

答案:5稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。

答案:對數(shù)據(jù)的邏輯結構說明數(shù)據(jù)元素之間的順序關系,它依賴于計算機的儲存結構。

答案:錯設有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（）。

答案:log2n+1一趟排序結束后不一定能夠選出一個元素放在其最終位置上的是（）。

答案:希爾排序具有10個葉子結點的二叉樹中有（）個度為2的結點

答案:9在順序表中插入或刪除一個元素，需要平均移動表中一半元素，具體移動的元素個數(shù)與元素在表中的位置有關。

答案:對普里姆算法是用來解決（）

答案:最小生成樹若串S=‘soft',其子串的數(shù)目是（）。

答案:11設一組權值集合W={2，3，4，5，6}，則由該權值集合構造的哈夫曼樹中帶權路徑長度之和為（）。

答案:45設某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復雜度為（）。

答案:O(n+e)順序表中邏輯上相鄰的元素的物理位置必定緊鄰。

答案:對連通分量指的是有向圖中的極大連通子圖。

答案:錯棧和隊列的共同點是（）

答案:只允許在端點處插入和刪除元素線性表是具有n個（）的有限序列

答案:數(shù)據(jù)元素兩個字符串相等的充分必要條件是長度相等，相應位置上字符相等。

答案:對設連通圖G中的邊集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為（）。

答案:acfebd對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結構為()

答案:用尾指針表示的單循環(huán)鏈表對用鄰接矩陣表示的具有n個頂點和e條邊的圖進行任一種遍歷時，其時間復雜度為（），對用鄰接表表示的圖進行任一種遍歷時，其時間復雜度為（）。

答案:O(n2)，O(e)子串“ABC”在主串“AABCABCD”中的位置為2。

答案:對鏈表是采用鏈式存儲結構的線性表,進行插入、刪除操作時，在鏈表中比在順序存儲結構中效率高。

答案:對執(zhí)行一趟快速排序能夠得到的序列是（）。

答案:[41，12，34，45，27]55[72，63]在計算機內(nèi)實現(xiàn)遞歸算法時所需的輔助數(shù)據(jù)結構是（

）

答案:棧在含有27個結點的二叉排序樹上查找關鍵字為35的結點，則依次比較的關鍵字有可能是（）

答案:46，36，18，28，35一棵二叉樹的先序遍歷序列為ABCDEF，中序遍歷序列為CBAEDF,則后序遍歷序列為（）

答案:CBEFDA設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點X，則入隊列的操作序列為（）。

答案:rear->next=s；rear=s；樹的先根序列等同于與該樹對應的二叉樹的（）

答案:先序序列根據(jù)使用頻率為5個字符設計的哈夫曼編碼不可能是（）

答案:00，100，101，110，111廣義表GetTail[GetHead[GetTail[((a,b),(c,d))]]]操作的結果為（

）

答案:(d）下列陳述中正確的是()

答案:二叉樹中最多只有兩棵子樹，并且有左右之分N個頂點的連通圖的生成樹含有()條邊

答案:N-1下述二叉樹中，（

）滿足性質：從任一結點出發(fā)到根的路徑上所經(jīng)過的結點序列按其關鍵字有序。

答案:哈夫曼樹采用順序查找方法查找長度為n的線性表時，不成功情況下的平均比較次數(shù)為（）

答案:n設二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。

答案:任一結點無右孩子在非空線性鏈表中由p所指結點的后面插入一個由q所指的結點，應依次執(zhí)行

答案:q->next=p->next；p->next=q；在單鏈表中刪除結點p（p不是最后一個結點）的后繼的語句是（）

答案:p->next=p->next->next一棵二叉樹中有7個葉子結點和5個單分支結點，其總共有（）結點。

答案:18以下數(shù)據(jù)結構中，是非線性數(shù)據(jù)結構的是（）

答案:樹元素的進棧次序為A，B，C，D，E，則退棧中不可能的序列是（）

答案:E，A，B，C，D設某哈夫曼樹中有199個結點，則該哈夫曼樹中有（）個葉子結點。

答案:100若用鄰接矩陣表示一個有向圖，則其中每一行包含的″1″的個數(shù)為()

答案:圖中每個頂點的出度有一組數(shù)據(jù){15，9，7，8，20，1，7，4}，用堆排序的篩選方法建立的初始堆為（

）

答案:{1，4，7，8，20，15，7，9}G是一個非連通無向圖，共有28條邊，則該圖至少有(）個頂點。

答案:9廣義表((a,b),c,d)的表頭是(

)

答案:(a,b)設輸入序列是1、2、3、……、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（）。

答案:n+1-i深度為3的二叉樹至多有（）結點

答案:7深度為5的二叉樹至多有（）個結點。

答案:31一組記錄的排列碼為(46,79,56,38,40,84),則利用堆排序的方法建立的初始堆為（）

答案:84,79,56,38,40,46若有序表的關鍵字序列為（b,c,d,e,f,g,q,r,s,t），則在二分查找關鍵字b的過程中，先后進行比較的關鍵字依次為()

答案:f,c,b線性表采用鏈式存儲結構時，要求內(nèi)存中可用存儲單元的地址()

答案:連續(xù)和不連續(xù)都可以設一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復雜度為（）。

答案:O(1)有一個有序表為（1,3,9,12,32,41,45,62,75,77,82,95,100），當二分查找值為82的結點時，（）比較后查找成功。

答案:4采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的（

）

答案:先序遍歷28.線性表是n個具有相同類型（

）的有限序列(n>=0)。

答案:數(shù)據(jù)元素關鍵路徑是事件結點網(wǎng)絡中（）

答案:從源點到匯點的最長路徑設某二叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為Nl，度數(shù)為2的結點數(shù)為N2，則下列等式成立的是（）。

答案:N0=N2+1下列敘述中不符合m階B樹定義要求的是（）

答案:葉結點之間通過指針鏈接用二叉鏈表表示具有n個結點的二叉樹時，值為空的指針域的個數(shù)為（）

答案:n+1已知一個單鏈表中，指針q指向指針p的前驅結點，若在指針q所指結點和指針p所指結點之間插入指針s所指結點，則需執(zhí)行（B）

答案:q→next=s；s→next=p；下面說法不正確的是()。

答案:廣義表的表頭總是一個廣義表在長度為n的順序表的第i個位置上插入一個元素(1<

=i<

=n+1)，元素的移動次數(shù)為：

答案:n-i+1時間復雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（）。

答案:堆排序順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為（）。

答案:O(n)一棵二叉排序樹是由關鍵字集合{18，43，27，44，36，39}構建的，其中序遍歷序列是（）

答案:18，27，36，39，43，44設一棵m叉樹中度數(shù)為0的結點數(shù)為N0，度數(shù)為1的結點數(shù)為Nl，……，度數(shù)為m的結點數(shù)為Nm，則N0=（）。

答案:l+N2+2N3+3N4+……+(m-1)Nm對線性表進行二分查找時，要求線性表必須是（）

答案:以順序方式存儲，且結點按關鍵字有序排列設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為（）。

答案:第i列非0元素的個數(shù)之和快速排序方法在（）情況下最不利于發(fā)揮其長處。

答案:要排序的數(shù)據(jù)已基本有序設一組初始記錄關鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關鍵字序列進行一趟歸并后的結果為（

）。

答案:15，25，35，50，20，40，80，85，36，702.快速排序方法在情況下最不利于發(fā)揮其長處。(

)

答案:要排序的數(shù)據(jù)已基本有序一組記錄的排序碼為(46,79,56,38,40,84),則利用堆排序的方法建立的初始推為（

）。

答案:84,79,56,38,40,461.編寫算法，對n個關鍵字取整數(shù)值的記錄序列進行整理，以使所有關鍵字為負值的記錄排在關鍵字為非負值的記錄之前，要求：(1)采用順序存儲結構，至多使用一個記錄的輔助存儲空間；(2)算法的時間復雜度為O(n);voidDivide(inta[],intn)//把數(shù)組a中所有值為負的記錄調(diào)到非負的記錄之前{low=0;high=n-1;while(

){while(low=0)high--;//以0作為虛擬的樞軸記錄a[low]<->a[high];while(lowa[high];}}//Divide

答案:low<

high試以L.r[k+1]作為監(jiān)視哨改寫教科書10.2.1節(jié)中給出的直接插入排序算法。其中，L.r[1..k]為待排序記錄且k=1;--i)

{

if(L.r[i+1].key<L.r[i].key)

{

L.r[k+1]=L.r[i];

//復制為監(jiān)視哨for(j=i+1;L.r[k+1].key>L.r[j].key;

++j)L.r[j-1]=L.r[j];

//記錄前移}//endif

}//endfor

}//InsertSort

答案:L.r[j]=L.r[k+1];1.設一組初始記錄關鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結束后前4條記錄關鍵字為（

）。

答案:15，40，60，204.試將折半查找的算法改寫成遞歸算法。

Int

bisearch

(sqlistL,intlow,inthigh

,

elemtypex

)

{

If(low>high)

return(

0

);

else

{

if(L.data[mid]=

=x)

return

(mid);

elseif

(L.data[mid]>x)

bisearch(L,low,mid-1,x);

else

bisearch(L,mid+1,high,x);

}

}//bisearch

答案:mid=(low+high)/2m階B_樹中的m是指？

答案:每個結點至多有m棵子樹3.設哈希表長m=14，哈希函數(shù)H(key)=key%11。表中已有4個結點：

addr(15)=4;

addr(38)=5;

addr(61)=6;

addr(84)=7

如用二次探測再散列處理沖突，關鍵字為49的結點的地址是(

)

答案:95.設計算法判定給定二叉樹是否為二叉排序樹。

voidBSTree(BiTreet,int&flag,int&last);//聲明StatusIsBSTree(BiTreet){

intflag=1;

intlast=0;

BSTree(t,flag,last);

returnflag;}voidBSTree(BiTreet,int&flag,int&last)//取地址不需要返回值{

if(t->lchild&&flag)BSTree(t->lchild,flag,last);//遍歷左子樹

if(t->data.key>last&&flag)

last=t->data.key;elseflag=0;//last原為父節(jié)點值，但到了樹葉節(jié)點后被樹葉節(jié)點的key值覆蓋，然后開始向上反饋keyif(t->rchild&&flag)

}

答案:BSTree(t->rchild,flag,last);1.對線性表進行二分查找時,要求線性表必須（

）。

答案:以順序方式存儲,且結點按關鍵字有序排序2.下列描述中不符合二叉排序樹特點的是

(

)

答案:根結點的關鍵字大于左、右子樹中所有結點的關鍵字編寫算法實現(xiàn)建立圖的鄰接表

StatusCreateAG(ALGraph&G){

intn,e,k,i,j;

cout<<"請輸入頂點數(shù)：";

cin>>n;

cout<<"請輸入邊數(shù)：";

cin>>e;

G.vernum=n;

G.arcnum=e;

//建立頂點數(shù)組

for(k=0;k>G.vertices[k].data;

G.vertices[k].firstarc=NULL;

}

//建立鄰接表

VertexTypev1,v2;

ArcNode*p,*q;

for(k=0;k>v1>>v2;

i=LocateVex(G,v1);

if(i<0||i>G.vernum-1)returnERROR;

j=LocateVex(G,v2);

if(j<0||j>G.vernum-1)returnERROR;

if(i==j)returnERROR;

p=newArcNode;

if(!p)returnERROR;

p->adjvex=j;

p->nextarc=NULL;

q=G.vertices[i].firstarc;

if(!q)G.vertices[i].firstarc=p;

else{

while(q->nextarc)__________

//指針定位于鄰接表的尾結點

q->nextarc=p;

}

}

returnOK;}

答案:q=q->nextarc

答案:aeeddccbegdf對于一個具有n個頂點的無向圖,若采用鄰接矩陣表示,則該矩陣的大小為（

）；

答案:n×n編寫算法實現(xiàn)從鄰接表中取出某個頂點V的存儲位置。intLocateVex(ALGraph&G,VertexTypev){

inti=0;

while(______&&i答案:G.vertices[i].data!=v采用鄰接表存儲的圖的寬度優(yōu)先遍歷算法類似于二叉樹的（

）。

答案:層次遍歷判定一個有向圖是否存在回路除了可以利用拓撲排序方法外,還可以利用（

）；

答案:深度優(yōu)先遍歷算法

答案:1試寫一個算法，為一棵二叉樹建立后序線索二叉樹。StatusPostOrderThreading(BiThrTree&T,BiThrTree&pre);//首先建立后序線索樹StatusFindNextInBiThrTree(BiThrTree&q,TElemType*p);//再進行查找

//后序線索二叉樹的算法StatusPostOrderThreading(BiThrTree&Thrt,BiThrTree&T){

BiThrTreepre;

Thrt=newBiThrNode;//為線索二叉樹建立頭結點

if(!Thrt)exit(OVERFLOW);

Thrt->LTag=Link;

Thrt->RTag=Thread;

Thrt->rchild=Thrt;//右子樹回指

if(!T)Thrt->lchild=Thrt;//若二叉樹空，左子樹回指

else{

Thrt->lchild=T;

pre=Thrt;

PostThreading(T,pre);//后序遍歷進行后序線索化

pre->rchild=Thrt;//最后一個結點線索化

pre->RTag=Thread;

Thrt->rchild=pre;

}

returnOK;}

StatusPostThreading(BiThrTree&T,BiThrTree&pre){

if(T){

if(T->LTag==Link)PostThreading(T->lchild,pre);

if(T->RTag==Link)PostThreading(T->rchild,pre);

if(!T->lchild){

T->LTag=Thread;

___________

}

if(pre&&!pre->rchild){

pre->RTag=Thread;

pre->rchild=T;

}

pre=T;

}

returnOK;}

答案:T->lchild=pre;已知一棵樹邊的集合為{,,,,,,,,,,,,},將此樹轉化為二叉樹后，E的左孩子為（

）；

答案:I已知一棵樹邊的集合為{,,,,,,,,,,,,},問這棵樹中結點G的雙親結點為(

)

答案:C假如一棵二叉樹的中序遍歷結果為ABCD，則結點A和結點D的關系一定不是（

）；

答案:結點A是結點D的右子樹上的結點1.編寫遞歸算法，將二叉樹中所有結點的左、右子樹相互交換。StatusExchangeBiTree(BiTree&T){

BiTreep;

if(T){

p=T->lchild;

T->lchild=T->rchild;

T->rchild=p;

ExchangeBiTree(T->lchild);

}

returnOK;}

答案:ExchangeBiTree(T->rchild);寫遞歸算法，將二叉樹中所有結點的左、右子樹相互交換。StatusExchangeBiTree(BiTree&T){

BiTreep;

if(T){

p=T->lchild;

T->lchild=T->rchild;

T->rchild=p;

ExchangeBiTree(T->lchild);

__________

}

returnOK;}

答案:ExchangeBiTree(T->rchild);一棵二叉樹中，葉子的個數(shù)為10，則其度為2的結點的個數(shù)為(

)；

答案:9一棵哈夫曼樹有17個結點，則其葉子結點的個數(shù)是

_________。

答案:9廣義表（（（））,a,((b,c),(),d),(((e)))）的長度為（

）；

答案:4下面說法不正確的是(

)。

答案:廣義表的表頭總是一個廣義表數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)是______。

答案:2401.試按教科書5.5節(jié)圖5.10所示的結點結構編寫復制廣義表的遞歸算法。//由廣義表L復制廣義表TintCopyGList(GList&T,GList&L){

if(!L)T=NULL;

else{

T=newGLNode;

if(!T)exit(OVERFLOW);

T->tag=L->tag;

if(L->tag==ATOM)T->atom=L->atom;

else{

________

CopyGList(T->tp,L->tp);

}

}

returnOK;}

答案:CopyGList(T->hp,L->hp);假設有二維數(shù)組A6×8，每個元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。已知A的起始存儲位置為1000，計算數(shù)組A按行存儲時元素A[14]第一個字節(jié)的位置（

）；

答案:1072若采用三元組壓縮技術存儲稀疏矩陣,只要把每個元素的行下標和列下標互換,就完成了對該矩陣的轉置運算,這種觀點（

）。

答案:錯誤設s=’IAMASTUDENT’,t=’GOOD’,則Concat(Substring(s,6,2),Concat(t,SubString(s,7,8)))=(

)

答案:AGOODSTUDENT串是一種數(shù)據(jù)對象和操作都特殊的線性表。

答案:對串的長度是指（

）

答案:串中所含字符的個數(shù)設串sl=″DataStructureswithJava″,s2=“it″，則子串定位函數(shù)index(s1,s2)的值為（）；

答案:18空串與空格串是相同的，這種說法____。

答案:不正確設計一個迷宮求解的算法，采用___________數(shù)據(jù)結構最佳。

答案:棧Status

SymmetryString(char*

p){Queue

q;if(!InitQueue(q))

return

0;Stack

s;InitStack(s);ElemType

e1,e2;while(*p){Push(s,*p);EnQueue(q,*p);p++;}while(!StackEmpty(s)){

(

)

DeQueue(q,e2);if(e1!=e2)

return

FALSE;}return

OK;}

答案:Pop(s,e1);循環(huán)隊列存儲在數(shù)組A[0..m-1],則出隊時的操作為（

）

答案:front=(front+1)modm1.試寫一個算法，識別依次讀入的一個以@為結束符的字符序列是否為形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，‘a(chǎn)+b&b+a’是屬該模式的字符序列，而‘1+3&3-1’則不是。BOOLSymmetry(chara[]){

inti=0;

Stacks;

InitStack(s);

ElemTypex;

while(a[i]!='&'&&a[i]){

_________

i++;

}

if(!a[i])returnFALSE;

i++;

while(a[i]){

Pop(s,x);

if(x!=a[i]){

DestroyStack(s);

returnFALSE;

}

i++;

}

returnTRUE;}

答案:Push(s,a[i])若以S和X分別表示進棧和退棧