一、單項選擇題一個算法應當是(）。A)程序 ?? ? B)問題求解環節的描述C）要滿足五個基本屬性???D)A和Ｃ算法指的是（)。A)計算機程序? ? ?B）解決問題的計算方法C)排序算法? ??D)解決問題的有限運算序列。與數據元素自身的形式、內容、相對位置、個數無關的是數據的（）。A)存儲結構 Ｂ)邏輯結構?C)算法 D)操作從邏輯上可以把數據結構分為()兩大類。A)動態結構、靜態結構? ?B)順序結構、鏈式結構C)線性結構、非線性結構 ??D)初等結構、構造型結構下列敘述中對的的是()。A)一個邏輯數據結構只能有一種存儲結構B）數據的邏輯結構屬于線性結構，存儲結構屬于非線性結構Ｃ)一個邏輯數據結構可以有多種存儲結構,且各種存儲結構不影響數據解決的效率D)一個邏輯數據結構可以有多種存儲結構，且各種存儲結構影響數據解決的效率數據的基本單位是（） A）數據項 ? Ｂ)數據類型 Ｃ)數據元素 ?D)數據變量下列程序的時間復雜度為()i＝０;ｓ=0;while（s<n）{ｉ++;s=s+ｉ；｝A）O（) ? B)O() C）O（n)? D）O（n２）下列程序段的漸進時間復雜度為()。for(iｎtｉ=１;ｉ<=n；i++）for(iｎtj=1;j<＝ｍ；j++)A[ｉ][j］＝i＊j；A)O(m2) Ｂ）Ｏ(n2)?Ｃ）O（m*n)?Ｄ）（ｍ+n)程序段如下：sum=０；ｆoｒ(ｉ=１;ｉ<=n；i＋+)ｆoｒ（j＝1；j<＝ｎ;j++)sum+＋；其中n為正整數，則最后一行的語句頻度在最壞情況下是(）。A)O（n）?? B)O(ｎlｏgn)? C）Ｏ(n3) ??Ｄ)O（ｎ2)在下面的程序段中,對ｘ的賦值語句的頻度為(）。ｆｏr(ｉ=1;i>=n;ｉ+＋）fｏr(j=1；ｊ>=n;j++）ｘ:=x＋1；Ａ)O（2n)? B）O(ｎ）? C)Ｏ(n2)??D)O（log２ｎ)程序段for(i:=n-１;i<=1;i--)ｆor(j:=１；j>=i;j＋+)iｆ(a[j]>a[j+１]){ｔ=ａ[j］;a［j]=a[j+1］;ａ[j+1］=t；}其中n為正整數，則最后一行的語句頻度在最壞情況下是（）。A)Ｏ(n) ??B）O(nlogｎ)? Ｃ)O(n3) ??D)O(n2）設有一個遞歸算法如下：intfact(ｉntn){／*大于等于0*/if(n<=0)retｕrn1;eｌserｅｔｕrnｎ*ｆact(ｎ-1);}則計算fａｃt(ｎ)需要調用該函數的次數為()。Ａ）n? B)n＋1 ?C）n+２ Ｄ)n－1下述程序段中語句①的頻度是（)。s=0；ｆor(i=１;i<m；i++)foｒ(j＝0;j<=i;j++)s+=ｊ;A)??B)? C)?D)若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素,則最節省運算時間的存儲方式是（)。Ａ)單鏈表??? ????B)僅有頭指針的單循環鏈表C)雙鏈表? ? ??? Ｄ）僅有尾指針的單循環鏈表求循環鏈表中當前結點的后繼和前驅的時間復雜度分別是（)。A)O(ｎ)和O(1)??B)Ｏ(1)和Ｏ(１)??C）O（1)和O（n）? Ｄ）O(ｎ)和O(n)求單鏈表中當前結點的后繼和前驅的時間復雜度分別是（）。 Ａ)O(ｎ）和O(1) ?B)O（１)和O(1）?C)O（1)和O（n）? Ｄ)O（ｎ)和O（ｎ)非空的單循環鏈表的頭指針為heａd,尾指針為rｅar,則下列條件成立的是（）。 Ａ)reａr－＞nexｔ＝＝head ?Ｂ)reａr->nｅxｔ->ｎext==ｈｅad?C）ｈead－＞next==reａr? D）heaｄ->ｎext-＞ｎeｘｔ==ｒear從一個長度為n的順序表中刪除第i個元素（1≤i≤n)時，需向前移動的元素的個數是()。A)n－i? ??Ｂ)n-i+1? ??C）ｎ－i-1 ???D)已知一個有序表為（13，18,2４，３5，47,50,6２，８3,90，１15,134）,當二分檢索值為90的元素時，檢索成功需比較的次數是(）。A)1? ? B)２ ??Ｃ)３? ? D)假設以行優先順序存儲三維數組R[６］[9］［６]，其中元素Ｒ[０][0］［0]的地址為2100,且每個元素占4個存儲單元，則存儲地址為2836的元素是（）。A)R［3][3]［3]? ?B）R[3][3][４］???Ｃ)R[4]［3]［５] ??D)R[4]［３][4]設有一個１0階的對稱矩陣A,采用壓縮存儲方式以行序為主序存儲,a００為第一個元素,其存儲地址為0，每個元素占有1個存儲地址空間，則a45的地址為（）。A)13 ???B)３5?? Ｃ)17? ? D)36線性表采用鏈式存儲時，節點的存儲的地址（）。A)必須是不連續的? B）連續與否均可C)必須是連續的? ??D)和頭節點的存儲地址相連續用鏈表表達線性表的優點是()。A)便于隨機存取??B)花費的存儲空間比順序表少C)數據元素的物理順序與邏輯順序相同Ｄ)便于插入與刪除鏈表不具有的特點是(）。Ａ)插入、刪除不需要移動元素 ?Ｂ)可隨機訪問任一元素C)不必事先估計存儲空間??D）所需空間與線性長度成正比在長度為ｎ的順序表中刪除第i個元素(１≤i≤n)時，元素移動的次數為()。A)ｎ－i+１??Ｂ）i??C)i+1 D)n－ｉ采用順序搜索方法查找長度為ｎ的順序表達，搜索成功的平均搜索長度為（）。Ａ)n? Ｂ)n/２? Ｃ)(n-1)/2將長度為n的單鏈表鏈接在長度為ｍ的單鏈表之后的算法的時間復雜度為（)。Ａ）Ｏ(1）??Ｂ)O(n）? Ｃ)O(m) ?Ｄ）O(m+ｎ)若不帶頭結點的單鏈表的頭指針為hｅaｄ，則該鏈表為空的鑒定條件是()。A)hｅad＝=NUＬL?B)ｈeａd-＞neｘt＝=NULＬ C）heaｄ!=NULL?D）heａｄ－＞neｘt＝=heaｄ某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（)存儲方式最節省運算時間。A）單鏈表 ?? ? Ｂ)僅有頭指針的單循環鏈表C)雙鏈表 ? ??D）僅有尾指針的單循環鏈表若允許表達式內多種括號混合嵌套,則為檢查表達式中括號是否對的配對的算法，通常選用的輔助結構是（)。 Ａ)棧 ??B)線性表???Ｃ)隊列??? D）二叉排序樹順序棧S中tｏp為棧頂指針，指向棧頂元素所在的位置,eleｍ為存放棧的數組,則元素e進棧操作的重要語句為（）。A)s．eｌem[tｏp］=e;?s.top=s.top+1； ?Ｂ)ｓ.elｅm[toｐ+1]＝e;s.top＝s.tｏp+1；Ｃ)ｓ.ｔoｐ=s．top+1;?ｓ.elｅm[top+１]=e； D)s.tｏｐ＝s．top＋1；s.eｌem[ｔｏｐ]＝e;循環隊列ｓq中，用數組elem［0··25]存放數據元素，sq.fｒｏnt指示隊頭元素的前一個位置,ｓｑ．ｒｅar指示隊尾元素的當前位置，設當前ｓq.front為20,sq.rear為１2,則當前隊列中的元素個數為()。A)8 ?B）1６ ???C)１7? ??D）１8鏈式棧與順序棧相比,一個比較明顯的優點是()。Ａ)插入操作更加方便? ? B)通常不會出現棧滿的情況C)不會出現棧空的情況? D)刪除操作更加方便一個遞歸的定義可以用遞歸過程求解，也可以用非遞歸過程求解,但單從運營時間來看，通常遞歸過程比非遞歸過程（)。A)較快 ?Ｂ)較慢 C)相同 ?D)不定若已知一個棧的入棧序列是1，２，3,4……n,其輸出序列為ｐ1,ｐ２，p3，……ｐｎ，若p１==n，則ｐi為(）。 A）i? ?B)ｎ==i? C）n-i+1 D)不擬定一個棧的入棧序列是ａ,b，c,d，e,則棧的不也許的輸出序列是（)。A）edｃba ?B)decba Ｃ)ｄceab??Ｄ)abｃde若進棧序列為１，2，3，4,５,6,且進棧和出棧可以穿插進行，則不也許出現的出棧序列是（)。Ａ)2，4,３,１,5,6?? ? B)3,２,4，１,6,5Ｃ)4,3,2，1，５,6? ?D)2,３,5，1,6,4對于棧操作數據的原則是（）。A)先進先出??B)后進先出 C）后進后出 Ｄ）不分順序棧和隊列的共同點是()。A)都是先進先出?B)都是先進后出Ｃ）只允許在端點處插入和刪除元素 D)沒有共同點一個隊列的入隊序列是1，２,3,４，則隊列的輸出序列是(）。A)４,３,2，1??B)１,2，３,4 ?C）1,4,3,2 D)3,2,4,１設數組ｄatａ[m]作為循環隊列SQ的存儲空間，fｒｏｎｔ為隊頭指針,ｒeａr為隊尾指針，則執行出對操作后其頭指針front值為（）。Ａ）fｒonｔ=front+１? ? B)ｆｒｏnｔ=(ｆｒonｔ+１)%(ｍ－１)C)froｎt＝(front-1)%m?? D)ｆront=(fronｔ+1)%m引起循環隊列隊頭位置發生變化的操作是()。Ａ)出隊 B)入隊 Ｃ)取隊頭元素? D)取隊尾元素設以數組A[ｍ]存放循環隊列的元素,其頭尾指針分別為ｆｒont和rｅar,則當前隊列中的元素個數為（）。A）（rｅａr-ｆrｏnt+m)%mB）reaｒ-ｆront＋１ C)(frｏnt-reａr＋m)%ｍD）二維數組Ａ[12][18］采用列優先的存儲方法，若每個元素各占3個存儲單元，且A[0］[0］地址為1５0,則元素A[9][7]的地址為()。A)４２９ Ｂ)４３2??Ｃ)４35設有一個10階的對稱矩陣A［10]［１0],采用壓縮方式按行將矩陣中下三角部分的元素存入一維數組Ｂ［]中,A［０][0]存入B[０]中，則Ａ[8]［5]在B[]中（）位置。A)32 ?? B)33 ?Ｃ)４1若對ｎ階對稱矩陣A以行序為主序方式將其下三角形的元素(涉及主對角線上所有元素)依次存放于一維數組B[１..（n(n+１）)/2］中，則在B中擬定aij(ｉ<j）的位置k的關系為()。A）i*(i-1)/２+j ?B）ｊ*(j-１)/2+i C）i*(ｉ+１）/2+j D)j*(j+1)/2+i對稀疏矩陣進行壓縮存儲目的是（）。Ａ）便于進行矩陣運算 ? ?B)便于輸入和輸出C)節省存儲空間 D)減少運算的時間復雜度對廣義表L=(（a,ｂ）,(c,d),(e，f))執行操作tail(ｔaｉl（L)）的結果是()。A）(e,f） B)((ｅ,f))??Ｃ)（f)??D)(）設廣義表Ｌ=（(a，b,c）),則L的長度和深度分別為（）。Ａ）1和1?B)1和3?C）1和２ Ｄ)2和樹中所有結點的度之和等于所有結點數加(）。A）0 Ｂ)1??C)－1 D)2在一棵具有n個結點的二叉鏈表中,所有結點的空域個數等于（)。A)n??B）n-１??Ｃ)n+1??Ｄ)2＊n某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是()的二叉樹。A）空或只有一個結點? ? Ｂ）高度等于其節點數C）任一結點無左孩子 ? Ｄ)任一結點無右孩子具有10個結點的二叉樹中，度為０的結點數為4，則度為2的結點數為(）A)３ ?? Ｂ)４? ? Ｃ)５? ??D)6除第一層外，滿二叉樹中每一層結點個數是上一層結點個數的（）Ａ)１/２倍? B)１倍? ??C）2倍 ???D)3倍對一棵有100個結點的完全二叉樹按層編號，則編號為４9的結點，它的父結點的編號為（)A)24? ? Ｂ)２５?? C)9８?? ?D)９9可以惟一地轉化成一棵一般樹的二叉樹的特點是（)A)根結點無左孩子?B)根結點無右孩子 Ｃ）根結點有兩個孩子?D)根結點沒有孩子設高度為h的二叉樹上只有度為0和度為2的結點,則此類二叉樹中所包含的結點數至少為（)。A)2h ?B)2h-1? Ｃ)2h+１? D)h+1在一棵度為３的樹中，度為3的節點個數為2，度為２的節點個數為１，則度為0的節點個數為（）。?A)４ ? B)5 C)６?? D)設森林F相應的二叉樹為B，它有m個結點，B的根為p，ｐ的右子樹結點個數為n，森林F中第一棵?子樹的結點個數是（)。A)m－ｎ ? B）m-n-1 C)n+1 ??D)條件局限性,無法擬定將一株有1０0個節點的完全二叉樹從上到下，從左到右依次進行編號，根節點的編號為1，則編號為４９的節點的左孩子編號為(）。Ａ)98 ?Ｂ）89 ?C)50 D)沒有孩子下列圖示的順序存儲結構表達的二叉樹是(A）樹最適合用來表達(）。A）有序數據元素?Ｂ)無序數據元素?Ｃ）元素之間具有分支層次關系的數據 D）元素之間無聯系的數據在一個非空二叉樹的中序遍歷序列中,根結點的右邊(）。?Ａ)只有右子樹上的所有結點 ?B)只有右子樹上的部分結點C）只有左子樹的上的部分結點? D)只有左子樹上的所有結點任何一棵二叉樹的葉結點在先序、中序和后序遍歷序列中相對順序（)。?A)不發生改變?B）發生改變?C)不能擬定 D)以上都不對深度優先遍歷類似于二叉樹的()。A)先序遍歷 B）中序遍歷?C)后序遍歷?D)層次遍歷廣度優先遍歷類似于二叉樹的()。A)先序遍歷?B)中序遍歷 C)后序遍歷?Ｄ)層次遍歷任何一個無向連通圖的最小生成樹()。A)只有一棵 B)一棵或多棵?C)一定有多棵 D)也許不存在(注，生成樹不唯一，但最小生成樹唯一,即邊權之和或樹權最小的情況唯一）在分析折半查找的性能時經常加入失敗節點，即外節點,從而形成擴充的二叉樹。若設失敗節點i所在層次為Li,那么查找失敗到達失敗點時所做的數據比較次數是（)。Ａ）Li+1??B)Li+２ ?C)Li-１??D)Ｌi向一個有127個元素原順序表中插入一個新元素并保存本來順序不變,平均要移動()個元素。?A)8 ??B)６3.5? C)６3 ?D）7由同一組關鍵字集合構造的各棵二叉排序樹()。A)其形態不一定相同，但平均查找長度相同B)其形態不一定相同,平均查找長度也不一定相同C）其形態均相同，但平均查找長度不一定相同D)其形態均相同,平均查找長度也都相同衡量查找算法效率的重要標準是(）。A)元素的個數 Ｂ)所需的存儲量?C)平均查找長度Ｄ)算法難易限度適合對動態查找表進行高效率查找的組織結構是（)。A)有序表?B)分塊有序表?C)二叉排序樹D)快速排序能進行二分查找的線性表,必須以(）。A)順序方式存儲，且元素按關鍵字有序B)鏈式方式存儲，且元素按關鍵字有序Ｃ)順序方式存儲，且元素按關鍵字分塊有序Ｄ)鏈式方式存儲,且元素按關鍵字分塊有序為使平均查找長度達成最小,當由關鍵字集合｛0５,１1,21,25，３７,40,4１,６２，84}構建二叉排序樹時,第一個插入的關鍵字應為(）Ａ)?5? Ｂ)3７????Ｃ)41 ???D)62對關鍵字序列(5６,23,78,９2,88，６７，19,34)進行增量為３的一趟希爾排序的結果為()。A)(19,２3,５６,３４,７8,67，88,9２)? Ｂ)２3，56,78,6６,88,９2,19,3４)C）（19,23,３４,５6,67,78,8８，９2） D）(１9，23,67，56，34，７8,92,8８)用某種排序方法對關鍵字序列{３５,８4，21,47,1５，27，６8,２5，20}進行排序時，序列的變化情況如下：２０,15,21,２５,47,27,6８,35,8415,２０,２1,25,35,27,４7,68,841５,20,21,25,27,35,47,68,84則采用的方法是()。A)直接選擇排序?B)希爾排序??C)堆排序 D)快速排序一組記錄的排序碼為(4６,7９,５６,３8，40,８4),則運用快速排序的方法，以第一個記錄為基準得到的第一次劃分結果為（)。?A)３8,4０,４6，5６,7９,８４?B)40,3８,46,79,56,84?C)４０,38，46,56,79，8４?D)快速排序在最壞情況下的時間復雜度是()A)Ｏ（n2loｇ２n） ? B)O(ｎ2) C)O（nｌog2n)? D)O（log２ｎ）下列排序算法中不穩定的是(）。Ａ)直接選擇排序 B）折半插入排序?C)冒泡排序?D)快速排序對待排序的元素序列進行劃分，將其分為左、右兩個子序列，再對兩個子序列進行同樣的排序操作，直到子序列為空或只剩下一個元素為止。這樣的排序方法是（)。Ａ)直接選擇排序 B）直接插入排序?C)快速排序 D）冒泡排序將5個不同的數據進行排序,至多需要比較（）次。Ａ)8B)9 C）10? D）25排序算法中，第一趟排序后，任一元素都不能擬定其最終位置的算法是(）。A）選擇排序? B)快速排序 ? C)冒泡排序 ??D)插入排序排序算法中,不穩定的排序是(）。A)直接插入排序? B）冒泡排序? C)堆排序 Ｄ)選擇排序排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較,將其放入已排序序列的對的位置上的方法,稱為（).A）希爾排序?B)冒泡排序C）插入排序Ｄ)選擇排序從未排序序列中挑選元素，并將其依次插入已排序序列(初始時為空)的一端的方法，稱為（)。A)希爾排序?B)歸并排序Ｃ）插入排序D)選擇排序對ｎ個不同的排序碼進行冒泡排序,在下列哪種情況下比較的次數最多。（）Ａ)從小到大排列好的? ?? B）從大到小排列好的Ｃ)元素無序?? ????D)元素基本有序對n個不同的排序碼進行冒泡排序，在元素無序的情況下比較的次數為（)。A)n+1Ｂ）n?C)n-1 D)n(n-1)/2快速排序在下列哪種情況下最易發揮其長處。()A)被排序的數據中具有多個相同排序碼B）被排序的數據已基本有序C)被排序的數據完全無序D)被排序的數據中的最大值和最小值相差懸殊對有n個記錄的表作快速排序，在最壞情況下,算法的時間復雜度是（)。Ａ)Ｏ(n) ??B)O(ｎ2） C)O(nｌoｇ２ｎ)? Ｄ）O(ｎ３)若一組記錄的排序碼為（46,7９,5６,３８,40,84）,則運用快速排序的方法,以第一個記錄為基準得到的一次劃分結果為（)。A)3８,4０,46,5６,79,８4B)40,38,46,79,56，84C)40，38,4６,５6,7９,８4?D)40，38,46，8４,56,７9下列關鍵字序列中，（）是堆。Ａ)１6,72,31，23,94,53???B)94，23，3１,72,1６，5３C）16,５3，2３,94，３1,72 Ｄ)16,23,53,31,94,72堆是一種（）排序。A)插入?B)選擇 ?Ｃ)互換??Ｄ)歸并堆的形狀是一棵（)。A)二叉排序樹Ｂ)滿二叉樹? C)完全二叉樹D)平衡二叉樹若一組記錄的排序碼為(46,７９,56,３8,4０,84），則運用堆排序的方法建立的初始堆為（）。Ａ)79，46,56，３8，40,84???B)84，７9,56,3８,4０，46C)84,79，56,4６，40,38? ?D）84,56,7９，40,46,38下述幾種排序方法中，規定內存最大的是（)。Ａ)插入排序 B）快速排序?Ｃ)歸并排序D）選擇排序有一組數據(15，9,7，8，20,-1，７，４），用堆排序的篩選方法建立的初始堆為()。A)-1，4,8,9,２0，7,15,7 ?Ｂ）－1，7，15,7,4，8,20，9C)-１,4,7,8,２０,15，７，9 D)A，B，C均不對。51．下列四個序列中,哪一個是堆（)。A)7５,65，30,1５,2５,４5,２0，１0???? B)75,６5，４5,10,30，25，20,１5C）75，４５,65,3０，15,２5,２0，10? ??D)75，4５,65,10,２５,３０,2０,15以下序列不是堆的是()。Ａ)(100,８5,9８,77,８0,6０，82,40,２0,10，66) B）(10０，9８,85,8２,８０,7７，66,６0,４0,2０,１０)C)(10，20,４０,6０，66,77,80,82,85,98,10０）? Ｄ）(10０,８５,4０,77,8０,60,66,98,８２,1０,20)快速排序方法在（)情況下最不利于發揮其長處。A)要排序的數據量太大??? ?B)要排序的數據中具有多個相同值Ｃ）要排序的數據個數為奇數 ??D)要排序的數據已基本有序對關鍵碼序列28，16,32，12，60，２,5,7２快速排序,從小到大一次劃分結果為（）。A)(2,5,1２，１６)26（60，32,72） ??? B）(5,1６,2,12)2８（6０,32，72)C)(2,16,１2,５)２８(60,３２,72) ? Ｄ）（5，16,２,12)28(3２，60，7２）對下列關鍵字序列用快速排序法進行排序時,速度最快的情形是(）。Ａ){21,25,5,17,9,23,３0} ? B){25,23,30，17，21，5,９｝Ｃ）{２1,9,17,3０,25,23，5｝? ? Ｄ)｛5，9,1７,２１,2３，２5,30｝二、填空題數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和運算等的學科。數據結構被形式地定義為(D,R),其中D是數據元素的有限集合,R是D上的關系有限集合。數據結構涉及數據的邏輯結構、數據的存儲結構和數據的運算這三個方面的內容。數據結構按邏輯結構可分為兩大類，它們分別是線性結構和非線性結構。線性結構中元素之間存在一對一關系,樹形結構中元素之間存在一對多關系,圖形結構中元素之間存在多對多關系。在線性結構中，第一個結點沒有前驅結點，其余每個結點有且只有1個前驅結點;最后一個結點沒有后續結點,其余每個結點有且只有1個后續結點。在樹形結構中，樹根結點沒有前驅結點,其余每個結點有且只有1個前驅結點；葉子結點沒有后續結點,其余每個結點的后續結點數可以任意多個。在圖形結構中,每個結點的前驅結點數和后續結點數可以任意多個。數據的存儲結構可用四種基本的存儲方法表達，它們分別是順序、鏈式、索引和散列。數據的運算最常用的有５種,它們分別是插入、刪除、修改、查找、排序。一個算法的效率可分為時間效率和空間效率。對于給定的n個元素,可以構造出的邏輯結構有集合,線性表,樹，圖四種。順序映象的特點是借助元素在存儲器中的相對位置來表達數據元素之間的邏輯關系。非順序映象的特點是借助是指示元素存儲地址的指針表達數據元素之間的邏輯關系。任何一個算法的設計取決于選定邏輯結構，而算法的實現依賴于采用的存儲結構。數據類型是一組＿＿___＿___＿_性質相同的值集合以及定義在這個值集合上的一組操作的總稱。數據對象是＿____＿_____性質相同的數據元素的集合，是數據的一個子集。假如操作不改變原邏輯結構的“值”,而只是從中提取某些信息作為運算結果,則稱該類運算為型運算。引用算法的健壯特性是指做為一個好的算法，當輸入的數據非法時,也能適本地做出對的反映或進行相應的解決,而不會產生一些莫名其妙的輸出結果。算法分析不是針對實際執行時間的精確的算出算法執行具體時間的分析，而是針對算法中語句的執行次數做出估計,從中得到算法執行時間的信息。Ｔ(n)=O（f(n）)，它表達隨問題規模n的增大算法的執行時間的增長率和f(n)的增長率相同，稱作算法的漸進時間復雜度,簡稱時間復雜度。若算法執行時所需要的輔助空間相對于輸入數據量而言是個常數，則稱這個算法為原地工作,輔助空間為O(1)。在帶有頭結點的單鏈表中L中，第一個元素結點的指針是。L->nｅxt在一個帶頭節點的單循環鏈表中,p指向尾結點的直接前驅,則指向頭結點的指針head可用p表達為head=。p->next-＞next設單鏈表的結點結構為（data，ｎext)，next為指針域，已知指針px指向單鏈表中dａtａ為x的結點，指針pｙ指向data為y的新結點,若將結點y插入結點ｘ之后,則需要執行以下語句:py-＞next=px－>next;px->next=ｐy。對于棧操作數據的原則是。后進先出設以數組A[m]存放循環隊列的元素，其頭尾指針分別為fｒｏnt和ｒeａｒ,則當前隊列中的元素個數為。（ｒｅar-fronｔ+m)%m若已知一個棧的入棧序列是1，２,3,４……n,其輸出序列為p1，ｐ2,p3,……pｎ,若ｐ１=＝n,則pｉ為。n-i+1隊列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。通常程序在調用另一個程序時,都需要使用一個棧來保存被調用程序內分派的局部變量。形式參數的存儲空間以及返回地址。棧下溢是指在＿_＿棧空_____時進行出棧操作。用Ｐ表達入棧操作,D表達出棧操作，若元素入棧的順序為1234，為了得到13４2出棧順序，相應的P和Ｄ的操作串為_____＿_。ＰDPPＤPDD在具有ｎ個單元的循環隊列中,隊滿共有n-1個元素。隊列是被限定為只能在表的一端進行插入運算,在表的另一端進行刪除運算的線性表。循環隊列的引入,目的是為了克服____＿__假溢出。所謂稀疏矩陣指的是＿______非零元很少(t<＜m*ｎ)且分布沒有規律。在稀疏矩陣表達所相應的三元組線性表中，每個三元組元素按行為主序,列號為輔序的順序排列。二位數組Ａm×n按行優先順序存儲在內存中，元素ａ0０地址為loc（a0０)，每個元素在內存中占d個字節,元素aｉｊ的地址計算公式為loc（ａij)=ｌoc(a00）＋(i*ｎ+j)*d。樹內個結點的度最大值稱為樹的度。一個二叉樹第5層節點最多有１6個。已知完全二叉樹T的第5層只有7個結點,則該樹共有_＿__1１___＿個葉子結點。在一棵二叉樹中，度為零的結點的個數為N０,度為2的結點的個數為Ｎ２,則有Ｎ0＝＿＿＿___Ｎ2+１。假設用于通信的電文由8個字母組成，其頻率分別為7,１9，2,6,3２,3,2７，1０。設計哈夫曼編碼，其中字母的編碼長度最大是5位。一棵具有257個結點的完全二叉樹,它的深度為。9散列法存儲的基本思想是由關鍵字的值決定數據的存儲地址。大多數排序算法都有兩個基本的操作:。比較和移動由于查找算法的基本運算是關鍵字之間的比較操作，所以可用平均查找長度來衡量查找算法的性能。查找有靜態查找和動態查找,當查找不成功時動態查找會將查找關鍵字插入在表中。順序查找法中設立監視哨，可以起到防止越界的作用。假設列表長度為n，那么查找第ｉ個數據元素時需進行n-i+1次比較。假設查找每個數據元素的概率相等,即Pi=1/n,則順序查找算法的平均查找長度為:ＡＳL=(n+1)/2。折半查找法又稱為二分法查找法，這種方法規定待查找的列表必須是按關鍵字大小有序排列的順序表。假定將長度為ｎ的表提成b塊，且每塊含ｓ個元素,則b=ｎ／s。又假定表中每個元素的查找概率相等,在有序表（12,２4,36,48,６0,7２,84）中二分查找關鍵字72時所需進行的關鍵字比較次數為2。折半查找有序表(４，6,12，２０,28,3８,50,７0,８8,100），若查找表中元素20，它將依次與表中元素２8，6,12，20比較大小。在各種查找方法中，平均查找長度與結點個數ｎ無關的查找方法是散列查找。當關鍵字集合很大時,關鍵字值不同的元素也許會映象到哈希表的同一地址上，即k1≠k2，但H(k1）=Ｈ(k2）,這種現象稱為沖突．在散列函數Ｈ（key)=keyＭODp中,ｐ應取素數。設哈希表長m=14,哈希函數H(key)=keyMOD11.表中已有4個結點;ａｄdr(15)＝4,ａddr（３8)=5,adｄr(６1)=6,addr(84)＝７,其余地址為空。如用二次探測再散列解決沖突,關鍵字為49的結點的地址是。9希爾排序是屬于插入排序的改善方法。給出一組關鍵字T＝（２０,4,３4，５，１6，33,18，２9，2,4０，7），規定從下到大進行排序，試給出快速排序（選一個記錄為樞紐)第一趟排序結果。7，4,2，85，16,1８，２0,,２9,33,40，34大多數排序算法都有兩個基本的操作：比較和移動。在對一組記錄（5４,38，96,２３,15,72,６0，45,８3）進行直接插入排序時,當把第7個記錄６0插入到有序表時,為尋找插入位置至少需比較次。6。在插入和選擇排序中,若初始數據基本正序,則選用插入;若初始數據基本反序，則選用選擇。在堆排序和快速排序中,若初始記錄接近正序或反序,則選用堆排序；若初始記錄基本無序，則最佳選用快速排序。對于n個記錄的集合進行冒泡排序,在最壞的情況下所需要的時間是O(n2)。若對其進行快速排序，在最壞的情況下所需要的時間是O(n2）對于n個記錄的集合進行歸并排序,所需要的平均時間是O(nlog2n)，所需要的附加空間是Ｏ（n)。7.對于n個記錄的表進行2路歸并排序,整個歸并排序需進行┌log２n┐趟（遍）。8.設要將序列（Ｑ,H，Ｃ,Ｙ,P，A,M,S,R,D,F,Ｘ)中的關鍵碼按字母序的升序重新排列，則：冒泡排序一趟掃描的結果是HCＱPAMＳRＤＦXY；初始步長為4的希爾(shｅｌl）排序一趟的結果是PACSＱHFXＲDMY;二路歸并排序一趟掃描的結果是HQCＹAＰMSDRFX;快速排序一趟掃描的結果是FＨCDPAＭQRＳＹX;堆排序初始建堆的結果是ADCRＦQＭＳYＰHX。9．在堆排序、快速排序和歸并排序中,若只從存儲空間考慮,則應一方面選取方法，另一方面選取快速排序方法，最后選取歸并排序方法；若只從排序結果的穩定性考慮,則應選取歸并排序方法;若只從平均情況下最快考慮,則應選取堆排序、快速排序和歸并排序方法；若只從最壞情況下最快并且要節省內存考慮,則應選取堆排序方法。三、程序填空題以下程序的功能是實現帶附加頭結點的單鏈表數據結點逆序連接，請填空完善之。voidrevｅrse（pｏiｎtｅrh）/*h為附加頭結點指針;＊／{poiｎtｅrp,q;p＝h->neｘｔ;h->next=NULL;whｉle((1)__＿_____){q=p;p=ｐ->ｎeｘt;q->neｘt=ｈ-＞nｅxt;h->next=（2)_＿＿__＿__;}}（1)ｐ!＝nｕll∥鏈表未到尾就一直作(2)q∥將當前結點作為頭結點后的第一元素結點插入下列算法在順序表L中依次存放著線性表中的元素,在表中查找與ｅ相等的元素,若Ｌ.eleｍ［ｉ]＝e,則找到該元素，并返回i+1,若找不到，則返回“-１”，請填空完善之。

iｎt

Locate(SｅqListL，inte){

ｉ＝０;

／＊i為掃描計數器,初值為0,即從第一個元素開始比較*／

while（(ｉ<=L．last）&&(L.eｌem[i]!=e）)

i＋+;

/*順序掃描表,直到找到值為key的元素,或掃描到表尾而沒找到*/

if

(ｉ＜＝L．laｓｔ)

returｎ(i+1);

/*若找到值為e的元素，則返回其序號*/

ｅlse

ｒetuｒn（-1)；

/*若沒找到,則返回空序號＊/

}下列算法在順序表L中第i個數據元素之前插入一個元素e。插入前表長n=L－＞last＋1，i的合法取值范圍是1≤ｉ≤L->lasｔ＋2,請填空完善之。

vｏｉｄ

InｓLiｓｔ(SeqLiｓt*L,ｉnti,iｎtｅ){intk;if((i<1)|｜（i>L->ｌａst+２))ｐｒiｎtf（“插入位置ｉ值不合法”)；

ｉｆ(L->lasｔ＞＝ｍaxｓize-1)printｆ(“表已滿無法插入”）；for(k=L－>ｌast;k＞=ｉ-1；k-－）

/*為插入元素而移動位置*/