數(shù)據(jù)結(jié)構(gòu)作業(yè)題(存儲(chǔ)版)
【正文】 2 12 16 30排序碼比較7次排序碼比較9次2 10 12 16 16* 20 28 306 182 6 10 12 16 16* 18 20 28 30。大量實(shí)驗(yàn)表明，取α=。nαn/2 (1) 直接插入排序 (2) 希爾排序(增量為5,2,1) (3) 起泡排序 (4) 快速排序 (5) 直接選擇排序 (6) 基數(shù)排序 (7) 堆排序 (8) 二路歸并排序 【解答】(1) 直接插入排序 初始排列 0 1 2 3 4 5 6 7 8 9 排序碼比較次數(shù) i = 1[ 12 ] 21630281016*20 618 1 i = 2[ 212 ]1630281016*20 618 1 i = 3[ 212 16 ]30281016*20 618 1 i = 4[ 212 16 30 ]281016*20 618 2 i = 5[ 212 16 2830 ]1016*20 618 5 i = 6[ 21012162830 ]16*20 618 3 i = 7[ 210121616*2830 ]20 618 3 i = 8[ 210121616*202830 ] 618 3 i = 9[ 2 610121616*202830 ]18 8[ 2 610121616*18202830 ](2) 希爾排序(增量為5,2,1)初始排列 0 1 2 3 4 5 6 7 8 9排序碼比較次數(shù) 12 21630281016*20 618 1+1+1+1+1 = 5 d = 5 10 216 6181216*203028 (1+1+2+1) + (1+1 d = 2+1+1) = 9 10 216 616*1218203028 1+1+3+1+3+1+1 d = 1+1+2 = 14 2 6 10 121616*18202830 希爾(shell)本人采取的增量序列為 235。83將關(guān)鍵碼DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN 依次插入到一棵初始為空的AVL樹（平衡二叉樹）中，畫出每插入一個(gè)關(guān)鍵碼后的AVL樹，并標(biāo)明平衡旋轉(zhuǎn)的類型。(A,B,D)(A,B,D)(A,B,D)165。 2 184。 (1) 這個(gè)工程最早可能在什么時(shí)間結(jié)束。矩陣中非零元素的個(gè)數(shù)與邊的條數(shù)有關(guān)（無向圖非零元素的個(gè)數(shù)是邊數(shù)的2倍；有向圖非零元素的個(gè)數(shù)等于邊數(shù)）。若等長(zhǎng)C1至C8編碼分別為000~111，平均長(zhǎng)度為3。（1）先序全線索化 （2）中序全線索化 （3）后續(xù)后繼線索化121131411921054315768 67 已知一棵二叉樹的前序遍歷的結(jié)果是ABECDFGHIJ, 中序遍歷的結(jié)果是EBCDAFHIGJ, 試畫出這棵二叉樹。63 如果一棵含有n個(gè)結(jié)點(diǎn)的樹中，只有度為k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)。n的壓縮存儲(chǔ)方式,我們把它們按行存放于一個(gè)一維數(shù)組B中:（1）設(shè)有一個(gè)n180。第四章 設(shè)有模式串T1,T2，T1=‘a(chǎn)aab’，T2=‘a(chǎn)bcabaa’，目標(biāo)串s為‘a(chǎn)bc aaabbabcabaacbacba’，（1）計(jì)算模式串T1的next(j) 和nextval(j)函數(shù)的值,并（按照nextval(j) ）畫出KMP算法匹配過程。amp。當(dāng)top[0]+1 == top[1]時(shí)或top[0] == top[1]1時(shí)，?？臻g滿，此時(shí)不能再向任一棧加入新的元素。按增長(zhǎng)率由小至大的順序排列下列各函數(shù)：2100, (3/2)n，(2/3)n， nn , , n! ，2n ，lgn ,nlgn, n(3/2) 第二章27 針對(duì)帶表頭結(jié)點(diǎn)的單鏈表，試編寫下列函數(shù)。 y=100。 k=0。第一章設(shè)n為正整數(shù)，利用大O記號(hào)，將下列程序段的執(zhí)行時(shí)間表示為n的函數(shù)。 (2) i=0。 j=0。(5) x=91。} else x++。當(dāng)向第0號(hào)棧插入一個(gè)新元素時(shí)，使top[0]增1得到新的棧頂位置，當(dāng)向第1號(hào)棧插入一個(gè)新元素時(shí)，使top[1]減1得到新的棧頂位置。}判?？账惴ǎ篿nt DStackEmpty(DoubleStack ds , int i) {//判斷雙棧ds的第i（0或1）個(gè)棧是否為空，空則返回1，否則返回0if (i==0 amp。 a + b * (c d) – e （表示結(jié)束符）步序掃描項(xiàng)項(xiàng)類型 動(dòng)作OPND棧變化OPTR棧變化0F OPTR棧與OPND棧初始化, ‘’ 進(jìn)OPTR棧, 取第一個(gè)符號(hào)1a操作數(shù)F a 進(jìn)OPND棧, 取下一符號(hào)a2+操作符F ‘ + ’ ‘’, 進(jìn)OPTR棧, 取下一符號(hào)a+………………………………33 分別寫出順序循環(huán)隊(duì)列隊(duì)列Q狀態(tài)為“空”還是“滿”的條件和計(jì)算隊(duì)列中元素個(gè)數(shù)的公式。問下列元素的存儲(chǔ)地址是什么？（1）a0000 （2）a
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號(hào)-1