【正文】 f和r，則判斷隊空的條件為 。5．一棵有n(n0)個結點的d度樹，若用多重鏈表表示，樹中每個結點都有d個鏈域，則在表示該樹的多重鏈表中有多少個空鏈域? 為什么?6．有一個二維數(shù)組A[0:8,1:5]，每個數(shù)組元素用相鄰的4個字節(jié)存儲,存儲器按字節(jié)編址，假設存儲數(shù)組元素A[0,1]的第一個字節(jié)的地址是0，那么存儲數(shù)組的最后一個元素的第一個字節(jié)的地址是多少？若按行存儲,則A[3,5]和A[5,3]的第一個字節(jié)的地址是多少？若按列存儲，則A[7,1]和A[2,4]的第一個字節(jié)的地址是多少？數(shù)據(jù)結構作業(yè)題（三）一、單選題（每題2分，共10分）在長度為n的順序存儲的線性表中，刪除第i個元素（1≤i≤n）時，需要從前向后依次前移 個元素。（ ）排序的結果為：12，13，15，18，20，60（ ）排序的結果為：13，15，18，12，20，60（ ）排序的結果為：13，15，20，18，12，604．設T是一棵二叉樹，除葉子結點外，其它結點的度數(shù)皆為2，若 T中有6個葉結點，試問：（1）T樹的最大深度Kmax=?最小可能深度Kmin=?（2）T樹中共有多少非葉結點？(3) 若葉結點的權值分別為1,2,3,4,5,6。設一數(shù)組中原有數(shù)據(jù)如下：15，13，20，18，12，60。三、應用題（每題10分，共60分）1．設有5個互不相同的元素a、b、c、d、e，能否通過7次比較就將其排好序？如果能，請列出其比較過程；如果不能，則說明原因。9．數(shù)據(jù)的邏輯結構被分為 、 、 和 四種。7．假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則度為0的結點數(shù)分別為 、 、 和 個。5．快速排序在平均情況下的時間復雜度為 ，在最壞情況下的時間復雜度為 。3．一個算法的時間復雜度為(3n2+2nlog2n+4n7)/(5n)，其數(shù)量級表示為 。A、f,c,b B、f,d,b C、g,c,b D、g,d,b二、填空題（每空2分，共40分）1．含n個頂點的無向連通圖中至少含有 條邊。A、不一定相同 B、都相同 C、都不相同 D、互為逆序9．圖的鄰接矩陣表示法適用于表示（ ）。A、插入 B、刪除 C、排序 D、定位7．若進棧序列為1，2，3，4，5，6，且進棧和出?？梢源┎暹M行，則可能出現(xiàn)的出棧序列為（ ）。A、O(m2) B、O(n2) C、O(m*n) D、O(m+n)5．數(shù)據(jù)結構是（ ）。 jn。 im。a+i 4．下面程序段的時間復雜度為（ ）。A、24 B、48 C、72 D、533．一個數(shù)組元素a[i]與（ ）的表示等價。 HLnext=p。 p=HL。 HL=p。 pnext=HL。5．一棵有n(n0)個結點的d度樹，若用多重鏈表表示，樹中每個結點都有d個鏈域，則在表示該樹的多重鏈表中有多少個空鏈域? 為什么?儲，則A[7,1]和A[2,4]的第一個字節(jié)的地址是多少？數(shù)據(jù)結構作業(yè)題（二）一、選擇題（每題2分，共20分）1．在一個單鏈表HL中，若要向表頭插入一個由指針p指向的結點，則執(zhí)行（ ）。1）先序序列和中序序列相同 2）中序序列和后序序列相同 3）先序序列和后序序列相同 4）中序序列與層次遍歷序列相同4．設T是一棵二叉樹，除葉子結點外，其它結點的度數(shù)皆為2，若 T中有6個葉結點，試問：（1）T樹的最大深度Kmax=?最小可能深度Kmin=?（2）T樹中共有多少非葉結點？(3) 若葉結點的權值分別為1,2,3,4,5,6。2．判斷下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，請將它們調(diào)整為堆）。（2）用直接選擇排序。（1）用直接插入排序。2．已知一個有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 順序存儲于一維數(shù)組a[12]中，根據(jù)折半搜索過程填寫成功搜索下表中所給元素34, 56, 58, 63, 94時的比較次數(shù)。三、運算題（每題5分，共10分）1．設有一個10180。9．在線性結構、樹形結構和圖形結構中，前驅和后繼結點之間分別存在著 、 和 的聯(lián)系。7．假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則樹中所含的結點數(shù)為 個，樹的深度為 ，樹的度為 。5．對于一棵具有n個結點的二叉樹，若一個結點的編號為i(1≤i≤n)，則它的左孩子結點的編號為 ，右孩子結點的編號為 ，雙親結點的編號為 。3．已知8個數(shù)據(jù)元素為（34，76，45，18，26，54，92，65），按照依次插入結點的方法生成一棵二叉排序樹，則該樹的深度為 。A、16 B、17 C、31 D、3210．如圖所示有向圖的一個拓撲序列是( )A、ABCDEFB、FCBEADC、FEDCBAD、DAEBCF二、填空題（每空1分，共20分）1．n (n﹥0) 個頂點的無向圖最多有 條邊，最少有 條邊。若設定尾指針指向隊列中的隊尾元素，頭指針指向隊列中隊頭元素的前一個位置，則當前存于隊列中的元素個數(shù)為（ ）。 s=0； for(i=1；in；i++) for(j=1；jn；j++) s+=i*j；A、O (1) B、O (n) C、O (2n) D、O (n2)7．棧是一種操作受限的線性結構，其操作的主要特征是（ ）。A、入度 B、出度C、入度與出度之和 D、入度與出度之差5．對于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為（ ）的值除以9。3．在一棵樹中，（ ）沒有前驅結點。C、firstlink == first。A、first == NULL。. . . .東北農(nóng)業(yè)大學網(wǎng)絡教育學院數(shù)據(jù)結構作業(yè)題（一）一、選擇題（每題2分，共20分）1．在一個長度為n的順序表的任一位置插入一個新元素的漸進時間復雜度為（ ）。A、O(n) B、O (n/2) C、O (1) D、O (n2)2．帶頭結點的單鏈表first為空的判定條件是（ ）。 B、firstlink == NULL。 D、first != NULL。A、分支結點 B、葉結點 C、樹根結點 D、空結點4．在有向圖中每個頂點的度等于該頂點的（ ）。A、20 B、18 C、25 D、226．下列程序段的時間復雜度為（ ）。A、先進先出 B、后進先出 C、進優(yōu)于出 D、出優(yōu)于進8．假設以數(shù)組A[n]存放循環(huán)隊列的元素，其頭、尾指針分別為front和rear。A、(rearfront1)％n B、(rearfront)％nC、(frontrear+1)％n D、(rearfront+n)％n9．高度為5的完全二叉樹中含有的結點數(shù)至少為（ ）。2．在一棵AVL樹中，每個結點的左子樹高度與右子樹高度之差的絕對值不超過 。4．在二叉樹的第i層上至多有 結點。6．數(shù)據(jù)的存儲結構被分為 、 、 和 四種。8．在一個具有n個頂點的無向圖中，要連通所有頂點則至少需要 條邊。10．一棵含999個結點的完全二叉樹的深度為 。10的對稱矩陣A，將其下三角部分按行存放在一個一維數(shù)組B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。元素值3456586394比較次數(shù)四、應用題（每題10分，共50分）1．設待排序的記錄共7個，排序碼分別為8，3，2，5，9，1，6。試以排序碼序列的變化描述形式說明排序全過程（動態(tài)過程）要求按遞減順序排序。試以排序碼序列的變化描述形式說明排序全