《算法分析與設(shè)計(jì)》練習(xí)題一

《算法分析與設(shè)計(jì)》練習(xí)題一一、簡(jiǎn)答題程序書(shū)寫(xiě)格式應(yīng)該遵循哪四個(gè)原則？答：（1）正確使用縮進(jìn)：一定要有縮進(jìn)，否則代碼的層次不明顯。在一行內(nèi)只寫(xiě)一條語(yǔ)句。‘{’, ‘}’位置不可隨意放置。變量和運(yùn)算符之間最好加1個(gè)空格什么是算法？答：用計(jì)算機(jī)解決問(wèn)題的過(guò)程可以分成三個(gè)階段：分析問(wèn)題、設(shè)計(jì)算法和實(shí)現(xiàn)算法。算法可以理解為有基本運(yùn)算及規(guī)定的運(yùn)算順序所構(gòu)成的完整的解題步驟，它是求解問(wèn)題類(lèi)的、機(jī)械的、統(tǒng)一的方法，它由有限多個(gè)步驟組成，對(duì)于問(wèn)題類(lèi)中每個(gè)給定的具體問(wèn)題，機(jī)械地執(zhí)行這些步驟就可以得到問(wèn)題的解答。或者看成按照要求設(shè)計(jì)好的有限的確切的計(jì)算序列，并且這樣的步驟和序列可以解決一類(lèi)問(wèn)題。什么是線性結(jié)構(gòu)？什么是非線性結(jié)構(gòu)？答：線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的一類(lèi)。它的特征是若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都有且只有一個(gè)直接前趨和一個(gè)直接后繼。線性表就是一個(gè)典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性結(jié)構(gòu)。非線性結(jié)構(gòu)：數(shù)據(jù)邏輯結(jié)構(gòu)中的另一大類(lèi)，它的邏輯特征是一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。數(shù)組、廣義表、樹(shù)和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。已知二叉樹(shù)后序遍歷序列是DABEC,中序遍歷序列是DEBAC,則前序遍歷序列是什么？答:前序遍歷序列是CEDBA什么是數(shù)制？答：數(shù)制是人們利用符號(hào)進(jìn)行計(jì)數(shù)的一種科學(xué)方法。數(shù)制也稱(chēng)計(jì)數(shù)制,是用一組固定的符號(hào)和統(tǒng)一的規(guī)則來(lái)表示數(shù)值的方法。如果將十進(jìn)制數(shù)106轉(zhuǎn)換為八進(jìn)制數(shù)，結(jié)果是多少？答：152請(qǐng)問(wèn)查找算法的效率用什么進(jìn)行度量？答：平均查找長(zhǎng)度ASL：在查找其關(guān)鍵字等于給定值的過(guò)程中，需要和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值稱(chēng)為查找成功時(shí)的平均查找長(zhǎng)度。ASL=^ipciii=1其中，n是結(jié)點(diǎn)的個(gè)數(shù)；是查找第i個(gè)結(jié)點(diǎn)的概率，是找到第i個(gè)結(jié)點(diǎn)所需要的比較次數(shù)。寫(xiě)出快速排序法的基本思想。答：快速排序的基本思想是：將原問(wèn)題分解為若干個(gè)規(guī)模更小但結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題。遞歸地解決這些子問(wèn)題，然后將這些子問(wèn)題的解組合為原問(wèn)題的解。（1）先從數(shù)列中取出一個(gè)數(shù)作為基準(zhǔn)數(shù)。（2）分區(qū)過(guò)程，將比這個(gè)基準(zhǔn)數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。（3）再對(duì)左右區(qū)間重復(fù)第（2）步，直到各區(qū)間只有一個(gè)數(shù)。遞歸算法解決問(wèn)題的特點(diǎn)是什么？答：（1）遞歸就是在函數(shù)里調(diào)用自身。（2）在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱(chēng)為遞歸出口。（3）遞歸算法解題通常顯得很簡(jiǎn)潔，但遞歸算法的運(yùn)行效率較低。（4）在遞歸調(diào)用的過(guò)程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開(kāi)辟了棧來(lái)存儲(chǔ)。遞歸次數(shù)過(guò)多容易造成棧溢出等。所以一般不提倡用遞歸算法設(shè)計(jì)程序。簡(jiǎn)述空串與空格串的區(qū)別。答：不含任何字符的串稱(chēng)為空串，其長(zhǎng)度為0。僅含有空格字符的串稱(chēng)為空格串，其長(zhǎng)度為串中空格字符的個(gè)數(shù)。空格符可用來(lái)分割一般的字符，便于人們識(shí)別和閱讀，但計(jì)算串長(zhǎng)時(shí)應(yīng)包括這些空格符?？沾诖幚碇锌勺鳛槿我獯淖哟３绦蛘{(diào)試的作用是什么？經(jīng)過(guò)調(diào)試后的程序是否需要再測(cè)試？答：程序調(diào)試的作用是將程序測(cè)試過(guò)程中發(fā)現(xiàn)的錯(cuò)誤改正過(guò)來(lái)，程序調(diào)試后需要再次進(jìn)行測(cè)試。算法通常有哪些特征？答：（1）輸入：所謂輸入是指從算法在執(zhí)行時(shí)需要從外界取得必要的信息。一個(gè)算法有零個(gè)或多個(gè)輸入，以刻畫(huà)運(yùn)算對(duì)象的初始情況。（2）確定性：算法的每一個(gè)步驟必須要確切地定義。即算法中所有有待執(zhí)行的動(dòng)作必須嚴(yán)格而不含混地進(jìn)行規(guī)定，不能有歧義性，以保證算法的實(shí)際執(zhí)行結(jié)果是精確地符合要求或期望，通常要求實(shí)際運(yùn)行結(jié)果是確定的。（3）有窮性（有限性）：一個(gè)算法在執(zhí)行有限步之后必須結(jié)束。也就是說(shuō)，一個(gè)算法，它所包含的計(jì)算步驟應(yīng)是有限的。（4）輸出：算法有一個(gè)或多個(gè)的輸出，即與輸入有某個(gè)特定關(guān)系的量，簡(jiǎn)單地說(shuō)就是算法的最終結(jié)果。（5）有效性（可行性）：算法中有待執(zhí)行的運(yùn)算和操作必須是相當(dāng)基本的，換言之，它們都是能夠精確地進(jìn)行的，算法執(zhí)行者甚至不需要掌握算法的含義即可根據(jù)該算法的每一步驟要求進(jìn)行操作，并最終得出正確的結(jié)果。什么是數(shù)據(jù)結(jié)構(gòu)？答：數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。一般包括三個(gè)方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。一個(gè)棧的初始狀態(tài)為空，首先將元素5，4，3，2，1依次入棧，然后退棧一次，再將元素A、B、C、D依次入棧，之后將所有元素全部退棧，則所元素退棧（包括中間退棧的元素）的順序?yàn)槭裁矗看穑?DCBA2345列出幾種常見(jiàn)的進(jìn)制（至少三種）答：通常采用的進(jìn)制有十進(jìn)制、二進(jìn)制、八進(jìn)制和十六進(jìn)制等。如果將十進(jìn)制數(shù)238轉(zhuǎn)換為二進(jìn)制數(shù)，結(jié)果是多少？答：11101110什么是查找？答：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。寫(xiě)出插入排序基本思想及排序步驟。答：排序基本思想：每次將一個(gè)待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。插入排序步驟：第i次插入的數(shù)是a[i],這時(shí)數(shù)組b中的b[0]~b[i-1]E經(jīng)有序了，將a[i]插入到數(shù)組b中的合適位置。插入@[V的過(guò)程，分為3個(gè)步驟：（1）從b[0]開(kāi)始，在b[0]~b[i-1]范圍內(nèi)找第一個(gè)大于a[i]的數(shù)，其位置記為k;（2）從b[i-1]開(kāi)始，將b[i-1]~b[k]復(fù)制到后一個(gè)位置，相當(dāng)于將這些數(shù)“后移”一個(gè)位置；（3）將a[i]放置在b[k]位置上，替換b[k]。遞推算法與遞歸算法的區(qū)別是什么？答：遞推：知道第一個(gè)，推出下一個(gè)，直到達(dá)到目的。遞歸：要知道第一個(gè)，需要先知道下一個(gè)，直到一個(gè)已知的，再反回來(lái)，得到上一個(gè)，直到第一個(gè)。簡(jiǎn)述主串與子串的關(guān)系。答：串中任意個(gè)連續(xù)的字符組成的子序列被稱(chēng)為該串的子串。包含子串的串又被稱(chēng)為該子串的主串。子串在主串中第一次出現(xiàn)的第一個(gè)字符的位置稱(chēng)子串在主串中的位置。如果將二進(jìn)制數(shù)101001101011轉(zhuǎn)換為十六進(jìn)制數(shù)，結(jié)果是多少？答：A6B對(duì)于長(zhǎng)度為n的有序表，折半查找的平均查找長(zhǎng)度是多少？答：平均查找長(zhǎng)度是logn次。2寫(xiě)出歸并排序法的基本思想。答：歸并排序是將兩個(gè)或兩個(gè)以上的有序子表合并成一個(gè)新的有序表。初始時(shí)，把含有n個(gè)結(jié)點(diǎn)的待排序序列看作由n個(gè)長(zhǎng)度都為1的有序子表組成，將它們依次兩兩歸并得到長(zhǎng)度為2的若干有序子表，再對(duì)它們兩兩合并。直到得到長(zhǎng)度為n的有序表，排序結(jié)束。請(qǐng)寫(xiě)出遞歸的基本概念，以及設(shè)計(jì)遞歸算法的兩個(gè)關(guān)鍵問(wèn)題。答：遞歸的概念：一個(gè)函數(shù)直接或間接調(diào)用自己本身，這種函數(shù)叫遞歸函數(shù)。設(shè)計(jì)遞歸算法的兩個(gè)關(guān)鍵問(wèn)題：（1）確定遞推公式（2）確定邊界（終了）條件（遞歸出口）25.寫(xiě)出如下字符處理函數(shù)的功能：（1）intisdigit（intc）（2）intisalpha（intc）（3）intisalnum（intc）（4）intislower（intc）（5）intisupper（intc）答：（1）intisdigit（intC）判斷C是否是數(shù)字字符，是則返回1,否則返回0。（2）intisalpha（intC）判斷C是否是