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