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

iｎt

Locate(SｅqListL，inte){

ｉ＝０;

／＊i為掃描計(jì)數(shù)器,初值為0,即從第一個(gè)元素開始比較*／

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

i＋+;

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

if

(ｉ＜＝L．laｓｔ)

returｎ(i+1);

/*若找到值為e的元素，則返回其序號(hào)*/

ｅlse

ｒetuｒn（-1)；

/*若沒找到,則返回空序號(hào)＊/

}下列算法在順序表L中第i個(gè)數(shù)據(jù)元素之前插入一個(gè)元素e。插入前表長(zhǎng)n=L－＞last＋1，i的合法取值范圍是1≤ｉ≤L->lasｔ＋2,請(qǐng)?zhí)羁胀晟浦?/p>

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-－）

/*為插入元素而移動(dòng)位置*/