數(shù)據(jù)結構作業(yè)題及參考答案

東北農業(yè)大學網絡教育學院數(shù)據(jù)結構作業(yè)題（一）一、選擇題（每題2分，共20分）1在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為（ ）。A、O(n)B、O (n/2)C、O (1)D、O (n2)2帶頭結點的單鏈表first為空的判定條件是（ ）。A、first = NULL; B、first-link = NULL;C、first-link = first; D、first != NULL;3在一棵樹中，（ ）沒有前驅結點。A、分支結點 B、葉結點 C、樹根結點 D、空結點4在有向圖中每個頂點的度等于該頂點的（ ）。A、入度 B、出度C、入度與出度之和D、入度與出度之差5對于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為（ ）的值除以9。A、20B、18C、25D、226下列程序段的時間復雜度為（ ）。 s=0； for(i=1；in；i+) for(j=1；j0)個結點的d度樹，若用多重鏈表表示，樹中每個結點都有d個鏈域，則在表示該樹的多重鏈表中有多少個空鏈域? 為什么?儲，則A7,1和A2,4的第一個字節(jié)的地址是多少？數(shù)據(jù)結構作業(yè)題（二）一、選擇題（每題2分，共20分）1在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結點，則執(zhí)行（ ）。A、HL=p; p-next=HL; B、p-next=HL; HL=p;C、p-next=HL; p=HL; D、p-next=HL-next; HL-next=p;2由權值分別為3,8,6,2,5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（ ）。A、24 B、48 C、72 D、533一個數(shù)組元素ai與（ ）的表示等價。A、*(a+i)B、a+iC、*a+iD、&a+i 4下面程序段的時間復雜度為（ ）。 for(int i=0; im; i+) for(int j=0; j0)個結點的d度樹，若用多重鏈表表示，樹中每個結點都有d個鏈域，則在表示該樹的多重鏈表中有多少個空鏈域? 為什么?6有一個二維數(shù)組A0:8,1:5，每個數(shù)組元素用相鄰的4個字節(jié)存儲,存儲器按字節(jié)編址，假設存儲數(shù)組元素A0,1的第一個字節(jié)的地址是0，那么存儲數(shù)組的最后一個元素的第一個字節(jié)的地址是多少？若按行存儲,則A3,5和A5,3的第一個字節(jié)的地址是多少？若按列存儲，則A7,1和A2,4的第一個字節(jié)的地址是多少？數(shù)據(jù)結構作業(yè)題（三）一、單選題（每題2分，共10分）1、在長度為n的順序存儲的線性表中，刪除第i個元素（1in）時，需要從前向后依次前移 個元素。A、n-i B、n-i+1 C、n-i-1 D、i2、設一個廣義表中結點的個數(shù)為n，則求廣義表深度算法的時間復雜度為 。A、O(1) B、O(n) C、O(n2) D、O(log 2 n)3、假定一個順序隊列的隊首和隊尾指針分別為f和r，則判斷隊空的條件為 。A、f+1=r B、r+1=f C、f=0 D、f=r4、由3 個結點可以構造出多少種不同的二叉樹 。A、2 B、3 C、4 D、5 5、適用于折半查找的表的存儲方式及元素排列要求為 。A、鏈接方式存儲，元素無序 B鏈接方式存儲，元素有序C、順序方式存儲，元素無序 D順序方式存儲，元素有序二、填空題（每空1分，共25分）1、在線性結構、樹結構和圖結構中，前驅和后繼結點之間分別存在著 、 和 的聯(lián)系。 2、在線性表的單鏈接存儲中，若一個元素所在結點的地址為p，則其后繼結點的地址為 ，若假定p為一個數(shù)組a中的下標，則其后繼結點的下標為 。 3、在初始化一個稀疏矩陣的函數(shù)定義中，矩陣形參應說明為 參數(shù)。 4、棧又稱為 表，隊列又稱為 表。 5、后綴表達式“4 5 + 3 * 2 4 + * ”的值為 。 6、一棵深度為5的滿二叉樹中的結點數(shù)為 個，一棵深度為3的滿四叉樹中的結點數(shù)為 個。 7、對于一棵含有40個結點的理想平衡樹，它的高度為 。 8、從一棵二叉搜索樹中查找一個元素時，若元素的值等于根結點的值，則表明 ，若元素的值小于根結點的值，則繼續(xù)向 查找，若元素的值大于根結點的值，則繼續(xù)向 查找。 9、對于一個具有n個頂點的圖，若采用鄰接矩陣表示，則矩陣大小為 。10、對于一個具有n個頂點和e條邊的連通圖，其生成樹中頂點數(shù)和邊數(shù)分別為 和 。 11、二分查找過程所對應的判定樹既是一棵 ，又是一棵 。12、在歸并排序中，進行每趟歸并的時間復雜度為 ，整個排序過程的時間復雜度為 ，空間復雜度為 。13、給定一組數(shù)據(jù)6，2，7，10，3，12以它構造一棵哈夫曼樹，則樹高為_，帶權路徑長度WPL的值為_。三、運算題（每題6分，共24分） 1、假定一棵普通樹的廣義表表示為 a(b(e),c(f(h,i,j),g),d)，分別寫出先根、后根、按層遍歷的結果。先根： 。后根： 。按層： 。 2、已知一個帶權圖的頂點集V和邊集G分別為： V = 0，1，2，3，4，5，6，7； E = （0，1）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13， （3，5）9，（3，6）10，（4，6）4，（5，7）20 ； 則求出該圖的最小生成樹的權。最小生成樹的權： 。 3、對于線性表（18,25,63,50,42,32,90,66）進行散列存儲時，若選用H(K)=K%9作為散列函數(shù)，則散列地址為0的元素有 個，散列地址為3的元素有 個，散列地址為5的元素有 個。 4、假定一組記錄的排序碼為（46，79，56，38，40，80，25，34），在對其進行快速排序的過程中，對應二叉搜索樹的深度為 ，分支結點數(shù)為 。四、閱讀算法（第一題7分，第二題8分） 1、void AA(LNode * & HL) InitList(HL); InsertRear(HL,30); InsertRear(HL,50);int a5 = 15,8,9,26,12;for ( int i=0; i=HBT.heapj) break; HBT.heapi=HBT.heapj; i=j; HBT.heapi=x; 該算法的功能為： 。五、算法填空，在畫有橫線的地方填寫合適的內容。（12分）從一維數(shù)組An中二分查找關鍵字為K的元素的遞歸算法，若查找成功則返回對應元素的下標，否則返回-1。int Binsch( ElemType A , int low , int high , KeyType K ) if ( low=high )int mid = (low+high)/2;if ( K=Amid.key) ; else if (KLlink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C. q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;6若一個棧的輸入序列為1,2,3,n，輸出序列的第一個元素是i，則第j個輸出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不確定的7有六個元素6，5，4，3，2，1 的順序進棧，問下列哪一個不是合法的出棧序列？（ ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 8用鏈接方式存儲的隊列，在進行刪除運算時（ ）。A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改D. 頭、尾指針可能都要修改9若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 10棧和隊列的共同點是（ ）。A. 都是先進先出 B. 都是先進后出 C. 只允許在端點處插入和刪除元素 D. 沒有共同點二、填空題（每空2分，共30分）1數(shù)據(jù)結構中評價算法的兩個重要指標是 和 。2一個算法具有5個特性: 、 、 ，有零個或多個輸入、有一個或多個輸出。3在一個長度為n的順序表中第i個元素（1=i=n）之前插入一個元素時，需向后移動_個元素。4對于雙向鏈表,在兩個結點之間插入一個新結點需修改的指針共 _個，單鏈表為_個。5設數(shù)組a1.50,1.80的基地址為2000，每個元素占2個存儲單元，若以行序為主序順序存儲，則元素a45,68的存儲地址為_ _;若以列序為主序順序存儲，則元素a45,68的存儲地址為_ _。6所謂稀疏矩陣指的是_。7廣義表的_ 定義為廣義表中括弧的重數(shù)。8具有256個結點的完全二叉樹的深度為_。9已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點，則該樹有_個葉子結點。10高度為8的完全二叉樹至少有_個葉子結點。三、計算題（每題6分，共30分）1如果輸入序列為1 2 3 4 5 6,試問能否通過棧結構得到以下兩個序列:4 3 5 6 1 2和1 3 5 4 2 6;請說明為什么不能或如何才能得到。2假定一棵二叉樹廣義表表示為a(b(c),d(e,f)，分別寫出對它進行先序、中序、后序、按層遍歷的結果。先序：中序：后序：按層：3已知一個圖的頂點集V和邊集G分別為：V=0,1,2,3,4,5,6,7;E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20,(6,7)30;按照普里姆算法從頂點0出發(fā)得到最小生成樹，試寫出在生成最小生成樹的過程中依次得到的各條邊。_, _, _, _, _, _, _。4. 已知一個圖的頂點集V和邊集G分別為：V=0,1,2,3,4,5,6,7,8;E=,;若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都是按照終點序號從小到大的次序鏈接的，則按主教材中介紹的進行拓撲排序的算法，寫出得到的拓撲序列（提示：先畫出對應的圖形，然后再運算）。拓撲序列：5假定一組記錄的排序碼為(46,79,56,38,40,80,25,34)，則對其進行快速排序的第一次劃分后的結果為_。四、算法填空（10分）1 五、編程（10分）1設計算法以求解從集合1.n中選取k（knext=p一next；p一next=q；B p一next=q一next；q=p；C 9一next=p一next；p一next=q；D p一next=q一next；q一next=p；3在一個順序隊列中，隊首指針指向隊首元素的（ ）位置。A前一個 B后一個 C當前4向二叉搜索樹中插入一個元素時，其時間復雜度大致為（ ）。A O（1） B O（1og2n）C O（n） D O（nlog2n）5假設有兩個串A和B，求B在A中首次出現(xiàn)的位置的操作，我們稱為（ ）。A.連接B.模式匹配 C.求子串 D.求串長6我們對記錄進行排序的目的是（ ）。A.分類 B.合并 C.存儲 D.查找7在最壞的情況下，冒泡排序法的時間復雜度為（ ）。A.O(lgn) B.O(nlgn) C.O(n2) D.O(n)8廣義表(A,B,E,F,G)的表尾是（ ）。A.(B, E , F, G) B.( )C.（A，B， E，F(xiàn)，G) D.（G）9線性表如果采用鏈式存儲結構，要求內存中的存儲單元的地址（ ）。A.必須是連續(xù)的B.部分要求是連續(xù)的C.一定不是連續(xù)的D.可以是連續(xù)的，也可以是不連續(xù)的10在數(shù)據(jù)結構中，從邏輯結構上，我們可以把數(shù)據(jù)結構分為（ ）。A.線性結構和非線性結構B.內部結構和外部結構C.順序結構和鏈式結構 D.動態(tài)結構和靜態(tài)結構二、填空題（每空1分，共25分）1數(shù)據(jù)的邏輯結構被分為 、 、 和 四種。2對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復雜度為 ，在表尾插入元素的時間復雜度為 。3在一個稀疏矩陣中，每個非零元素所對應的三元組包括該元素的 、 和 三項。4在廣義表的存儲結構中，每個結點均包含有 個域。5當用長度為N的數(shù)組順序存儲一個棧時，假定用top = =N表示棧空，則表示棧滿的條件為 。6假定一棵三叉樹的結點個數(shù)為50，則它的最小深度為 ，最大深度為 。7在一棵二叉樹中，第5層上的結點數(shù)最多為 。8在一個小根堆中，堆頂結點的值是所有結點中的 ，在一個大根堆中，堆頂結點的值是所有結點中的 。9在一個具有n個頂點的無向圄中，要連通所有頂點則至少需要 條邊。10假定一個圖具有n個頂點和e條邊，貝采用鄰接矩陣、鄰接表和邊集數(shù)組表示時，其相應的空間復雜度分別為 、 和 。11以二分查找方法查找一個線性表時，此線性表必須是 存儲的 表。12在索引表中，若一個索引項對應主表中的一條記錄，則稱此索引為 表。13快速排序在平均情況下的空間復雜度為 ，在最壞情況下的空間復雜度為 。三、運算題（每題5分，共20分）1假定一個大堆為（56，38，42，30，25，40，35，20），則依次從中刪除兩個元素后得到的堆為 。2已知一個圖的頂點集V和邊集6分別為： V=0，1，2，3，4，5，6，7； E=（04）8，（0，2）5，（0，3）2，（1，5）6，（2，3）25，（2，4）13，（3，5）9，（3，6）10，（4，6）4，（5，7）20； 按照克魯斯卡爾算法得到最小生成材，拭寫出在最小生成樹中依次得到的各條邊。 ， ， ， ， ， ， 。3假定一組數(shù)據(jù)的初始堆為（84，79，56，42，40，46，50，38），請寫出在堆排序階段進行前三次對換和篩運算后數(shù)據(jù)的排列情況。 數(shù)據(jù)排列情況： 。4假定一組記錄的徘序碼為（46，79，56，38，40，80，36，40，75，66，84，24），對其進行歸并排序的過程中，第三趟歸并后的結果為： 。四、閱讀算法，回答問題（每題5分，共10分）1void AA （ListL） InitList（L）； InsertRear （L，30）； InsertFront（L，50）； int a 4=5，8，12，15 for（int i=0；14；i InsertRear（L，a i）； 該算法被調用執(zhí)行后，得到的線性表L為： 。2void AF（QueueQ） InitQueue（Q）： int a 4=5，8，12，15 for（int i一0；i4；i斗 Qlnsert（Q，遷6）； QInsert（Q，QDelete（Q）； QInsert（Q，30）； QInsert（Q，QDelete（Q）10）； whi1e（！QueueEmpty（Q） coutQDeleie（Q）”； 該算法被調用后得到的輸出結果為： 。五、算法填空，在畫有橫線的地方填寫合適的內容（10分）從一維數(shù)組An上進行快速排序的遞歸算法。void QuickSort（ElemType A ， int s， int t） int i=s j=t十1； ElemType x=As； d0 do i+； while ；填寫一個循環(huán)條件 do j - - ； while（A j stnxstn）； if（I0）個結點的d度樹共有nd個鏈域，除根結點外，每個結點均有一個指針所指，故該樹的空鏈域有nd-(n-1)=n(d-1)+1個。習題二參考答案一、選擇題（每題2分，共20分）12345678910BDACDDBBCA二、填空題（每空2分，共40分）1n-12（15，02，21，24，26，57，43，66，81，48，73）3O（n）4HL-next=NULL HL-next=HL5O(nlog2n) ；O(n2)66； 31； 1972； 1； 1； 68 6 9集合結構；線性結構；樹型結構；圖形結構10n-i+1三、應用題（每題10分，共60分）1答：可以做到。取a與b進行比較，c與d進行比較。設ab,cd(ab和cd，則有序abd；若bdb，此時已進行了3次比較。再把另外兩個元素按折半插入排序方法，插入到上述某個序列中共需4次比較，從而共需7次比較。2該排序方法為快速排序。3快速排序 冒泡排序 直接插入排序4答：（1）T樹的最大深度Kmax=6（除根外，每層均是兩個結點）T樹的最小深度Kmin=4（具有6個葉子的完全二叉樹是其中的一種形態(tài)）456123（2）非葉子結點數(shù)是5。（n2=n0-1） （3）哈夫曼樹見下圖，其帶權路徑長度wpl=51Wpl=4*3+3*3+2*(4+5+6)=515答：n（n0）個結點的d度樹共有nd個鏈域，除根結點外，每個結點均有一個指針所指，故該樹的空鏈域有nd-(n-1)=n(d-1)+1個。6答：（1）176 （2）76和108 （3）28和116。習題三參考答案一、單選題（每題2分，共10分） 1、A 2、B 3、D 4、D5、D二、填空題（每空1分，共25分） 1、1:1 1:N M:N （或者 1對1 1對N M對N） 2、p-next ap.next 3、引用 4、后進先出 先進先出 5、162 6、31 21 7、6 8、查找成功 左子樹 右子樹 9、n2 10、n n-111、二叉搜索樹 理想平衡樹 （次序無先后） 12、O(n) O(nlog2n) O(n)13、596 三、運算題（每題6分，共24分） 1、 先根：a,b,e,c,f,h,i,j,g,d; （2分） 后根：e,b,h,i,j,f,g,c,d,a; （2分） 按層：a,b,c,d,e,f,g,h,i,j; （2分） 2、 最小生成樹的權：55 3、 3 1 2 4、 5 6 四、閱讀算法，回答問題（第一題7分，第二題8分） 1、（12，26，9，8，15，30，50） 2、向HBT堆中插入一個值為item的元素，使得插入后仍是一個堆。五、算法填空，在畫有橫線的地方填寫合適的內容（12分） return mid return Binsch(A , low , mid-1 , K) return Binsch(A , mid+1 , high , K)六、編寫算法（14分） 評分標準：請根據(jù)編程情況酌情給分。bool Find( BTreeNode * BST , ElemType & item ) while ( BST != NULL ) if ( item = BT-data ) item = BST-data;return true; else if (itemdata) BST=BST-left;else BST=BST-right; return false;習題四參考答案一、選擇題（每題2分，共20分）12345678910CDACCDCDBC二、填空題（每空2分，共30分）1算法的時間復雜度和空間復雜度2有窮性； 確定性； 可行性。3n-