什么叫算法簡(jiǎn)述算法的基本特性

1、31什么叫算法？簡(jiǎn)述算法的基本特性。2如何評(píng)價(jià)一個(gè)算法？簡(jiǎn)述空間復(fù)雜性和時(shí)間復(fù)雜性的概念3試分析下列各程序段的時(shí)間復(fù)雜性。1)i=1;(2)for(i=1;iv=m;i+)(3)x=n;/*n1*/k=0;for(j=1;jv=n;j+)y=0;n=100;Aij=i*j;while(x=(y+1)*(y+1)dok=k+10*i;y=y+1;i+;while(i!100);4.簡(jiǎn)述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類(lèi)型、數(shù)據(jù)結(jié)構(gòu)；5簡(jiǎn)述數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)運(yùn)算的概念。6線(xiàn)性表可用順序表和單鏈表作為存儲(chǔ)結(jié)構(gòu)。試問(wèn)：兩種存儲(chǔ)表示各有哪些主要優(yōu)缺點(diǎn)？如果有n個(gè)表同時(shí)并存，且處理過(guò)程中個(gè)

2、表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，表的總數(shù)也可能自動(dòng)變化，在此情況下應(yīng)選用哪種存儲(chǔ)表示？為什么？若表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快速度存取表中元素，這時(shí)應(yīng)采用哪種存儲(chǔ)表示？為什么？7設(shè)ha和hb分別是兩個(gè)帶表頭結(jié)點(diǎn)的升序單鏈表的表頭指針。試設(shè)計(jì)一個(gè)算法將這兩個(gè)鏈表合并成為一個(gè)降序單鏈表。要求結(jié)果鏈表仍使用原來(lái)兩個(gè)鏈表的結(jié)點(diǎn)空間而不另開(kāi)辟其他存儲(chǔ)空間，表中允許出現(xiàn)重復(fù)數(shù)據(jù)。設(shè)有一個(gè)線(xiàn)性表L=(a,a,a)，試分別在順序表和單鏈表兩種存儲(chǔ)表示方式12n下，各設(shè)計(jì)一個(gè)將線(xiàn)性表L逆置的算法，要求不重新開(kāi)辟存儲(chǔ)空間。所謂逆置是指將線(xiàn)性表中的元素次序顛倒過(guò)來(lái)，即成為L(zhǎng)f=(a,a,a)。nn-1

3、1設(shè)有一個(gè)棧，元素的進(jìn)棧次序依次為A,B,C,D,E.試問(wèn)能否得到下面的出棧序列？若能請(qǐng)寫(xiě)出操作序列，若不能請(qǐng)說(shuō)明原因。(1)C,E,A,B,D(2)C,B,A,D,E(3)D,C,A,B,E(4)A,C,B,E,D(5)A,B,C,D,E(6)E,A,B,C,D何謂隊(duì)列的上溢現(xiàn)象？解決它有哪些方法？分別簡(jiǎn)述其工作原理。11試寫(xiě)一個(gè)算法，它借助棧逆置一個(gè)單鏈表。12.已知一棵樹(shù)邊的集合為vi,m,vi,n,ve,i,vb,e,vb,d,va,b,vg,j,vg,k,，請(qǐng)畫(huà)出這棵樹(shù)，并回答下列問(wèn)題：(1)哪個(gè)結(jié)點(diǎn)是根結(jié)點(diǎn)？(2)哪些是葉子結(jié)點(diǎn)？(3)哪個(gè)是結(jié)點(diǎn)g的雙親？(4)哪些是結(jié)點(diǎn)g的祖先？

4、(5)哪些是結(jié)點(diǎn)g的孩子？(6)哪些是結(jié)點(diǎn)e的子孫？(7)哪些是結(jié)點(diǎn)e的兄弟？哪些是結(jié)點(diǎn)f的兄弟？(8)結(jié)點(diǎn)b和n的層次號(hào)分別是什么？(9)樹(shù)的深度是多少？樹(shù)的度是多少？(10)以結(jié)點(diǎn)c為根的子樹(shù)深度是多少？13試分別畫(huà)出具有3個(gè)結(jié)點(diǎn)的樹(shù)和3個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。14已知一棵度為k樹(shù)中有n個(gè)度為1的結(jié)點(diǎn)，有n個(gè)度為2的結(jié)點(diǎn)，有n12k個(gè)度為k的結(jié)點(diǎn)，問(wèn)：樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)？15對(duì)于如圖所示的兩棵二叉樹(shù)，分別寫(xiě)出：（1）前序遍歷序列，（2）中序遍歷序列，（3）后序遍歷序列，（4）層序遍歷序列。16已知某二叉樹(shù)的后序遍歷序列為：DCEGBFHKJIA，中序遍歷序列為：DCBGEAHFIJ

5、K,請(qǐng)畫(huà)出該二叉樹(shù)，并寫(xiě)出它的前序序列和層序序列。17已知某二叉樹(shù)的層序遍歷序列為：ABCDEFGHIJ，中序遍歷序列為:DBGEHJACIF，請(qǐng)畫(huà)出該二叉樹(shù)，并寫(xiě)出它的前序序列和后序序列。18.把下圖所示的兩棵樹(shù)分別轉(zhuǎn)換為相應(yīng)的二叉樹(shù)。19假設(shè)用于通信的電文僅有8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為719，2，6，32，3，21，10。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。20給出右圖所示有向圖的鄰接矩陣、鄰接表，并給出每個(gè)頂點(diǎn)的入度和出度。21.對(duì)右圖所示網(wǎng)分別給出：（1）深度優(yōu)先搜索遍歷序列（分別從V1和V4開(kāi)始）;（2）廣度優(yōu)先搜索遍歷序列（分別從V1和V4開(kāi)始）;（3）用普里姆算法求得最

6、小生成樹(shù)的過(guò)程；（4）用克魯斯卡爾算法求得最小生成樹(shù)的過(guò)程；32v2V32v45v5V664v722對(duì)于右圖所示的帶權(quán)有向圖分別給出：（a）網(wǎng)的帶權(quán)鄰接矩陣，（b）用DIJKSTRA方法求從V1出發(fā)到個(gè)頂點(diǎn)的最短路徑的過(guò)程。23給出右圖所示無(wú)環(huán)圖的所有拓?fù)溆行蛐蛄小?4什么是排序算法？什么是內(nèi)部排序？什么是外部排序？25.給定排序碼序列為（17,8,21,35,32,15,21,25,12,23），試分別寫(xiě)出使用以下排序方法進(jìn)行排序的過(guò)程。（1）直接插入排序（7）快速排序（8）直接選擇排序（11）二路歸并排序（12）基數(shù)排序。26設(shè)結(jié)點(diǎn)序列為（60,30,90,50,120,70,40,80），試用二叉檢索樹(shù)的插入方法，畫(huà)出按此結(jié)點(diǎn)序列建立的一棵二叉檢索樹(shù)。27.已知如下所示長(zhǎng)度為12的表（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）按表中元素的順序依次插入一棵初試為空的二叉排序樹(shù)，請(qǐng)畫(huà)出插入完成之后的二叉排序樹(shù)，并求其在等概率情況下查找成功的平均查找長(zhǎng)度。28對(duì)關(guān)鍵字（22，41，53，46，30，13