數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題和部分答案

PAGEPAGE14全國201?2年1月數(shù)據(jù)結(jié)構(gòu)導(dǎo)?論試題課程代碼：02142?一、單項(xiàng)選擇題?(本大題共1?5小題，每小題2分?，共30分)1.結(jié)點(diǎn)按邏輯?關(guān)系依次排?列形成一條?“鎖鏈”的數(shù)據(jù)結(jié)構(gòu)?是()A.集合B.線性結(jié)構(gòu)C.樹形結(jié)構(gòu)D.圖狀結(jié)構(gòu)2.下面算法程?序段的時間?復(fù)雜度為()for(inti=0;i<m;i++)for(intj=0;j<n;j++)a［i］［j］=i*j;A.O(m2)B.O(n2)C.O(mn)D.O(m+n)3.線性結(jié)構(gòu)是?()A.具有n（n≥0）個表元素的?有窮序列 B.具有n（n≥0）個字符的有?窮序列C.具有n（n≥0）個結(jié)點(diǎn)的有?窮序列 D.具有n（n≥0）個數(shù)據(jù)項(xiàng)的?有窮序列4.單鏈表中刪?除由某個指?針變量指向?的結(jié)點(diǎn)的直?接后繼，該算法的時?間復(fù)雜度是?()A.O(1)B.O()C.O(log2n?)D.O(n)5.關(guān)于串的敘?述，正確的是()A.串是含有一?個或多個字?符的有窮序?列B.空串是只含?有空格字符?的串C.空串是含有?零個字符或?含有空格字?符的串D.串是含有零?個或多個字?符的有窮序?列6.棧的輸入序?列依次為1?，2，3，4，則不可能的?出棧序列是?()A.1243B.1432C.21347.隊列是()A.先進(jìn)先出的?線性表B.先進(jìn)后出的?線性表C.后進(jìn)先出的?線性表D.隨意進(jìn)出的?線性表8.10階上三?角矩陣壓縮?存儲時需存?儲的元素個?數(shù)為()A.11B.56C.1009.深度為k（k≥1）的二叉樹，結(jié)點(diǎn)數(shù)最多?有()A.2k個B.(2k-1)個C.2k-1個D.(2k+1)個10.具有12個?結(jié)點(diǎn)的二叉?樹的二叉鏈?表存儲結(jié)構(gòu)?中，空鏈域NU?LL的個數(shù)?為()A.11B.13C.2311.具有n個頂?點(diǎn)的無向圖?的邊數(shù)最多?為()A.n+1B.n(n+1)C.n(n-1)/2D.2n(n+1)12.三個頂點(diǎn)v?1,v2,v3的圖的?鄰接矩陣為?，該圖中頂點(diǎn)?v3的入度?為()A.0B.1C.213.順序存儲的?表格中有6?0000個?元素，已按關(guān)鍵字?值升序排列?，假定對每個?元素進(jìn)行查?找的概率是?相同的，且每個元素?的關(guān)鍵字值?不相同。用順序查找?法查找時，平均比較次?數(shù)約為()A.20000?B.30000?14.外存儲器的?主要特點(diǎn)是?()A.容量小和存?取速度低B.容量大和存?取速度低C.容量大和存?取速度高D.容量小和存?取速度高15.在待排數(shù)據(jù)?基本有序的?前提下，效率最高的?排序算法是?()A.直接插入排?序B.直接選擇排?序C.快速排序D?.歸并排序二、填空題(本大題共1?3小題，每小題2分?，共26分)16.數(shù)據(jù)的不可?分割的最小?標(biāo)識單位是?_____?_，它通常不具?有完整確定?的實(shí)際意義?，或不被當(dāng)作?一個整體對?待。17.運(yùn)算分為加?工型運(yùn)算和?引用型運(yùn)算?，讀取操作是?_____?_運(yùn)算。18.帶有頭結(jié)點(diǎn)?的單向循環(huán)?鏈表L（L為頭指針?）中，指針p所指?結(jié)點(diǎn)為尾結(jié)?點(diǎn)的條件是?_____?_。19.在雙鏈表中?，前趨指針和?后繼指針分?別為pri?or和ne?xt。若使指針p?往后移動兩?個結(jié)點(diǎn)，則需執(zhí)行語?句_____?_。20.元素s1，s2，s3，s4，s5，s6依次進(jìn)?入順序棧S?，如果6個元?素的退棧順?序?yàn)閟2，s3，s4，s6，s5，s1，則順序棧的?容量至少為?_____?_。21.稀疏矩陣一?般采用的壓?縮存儲方法?是____?__。22.在一棵樹中?，_____?_結(jié)點(diǎn)沒有雙?親。23.一棵具有n?個結(jié)點(diǎn)的完?全二叉樹中?，從樹根起，自上而下、自左至右給?所有結(jié)點(diǎn)編?號。設(shè)根結(jié)點(diǎn)編?號為1，若編號為i?的結(jié)點(diǎn)有父?結(jié)點(diǎn)，那么其父結(jié)?點(diǎn)的編號為?_____?_。24.二叉樹的二?叉鏈表存儲?結(jié)構(gòu)中判斷?指針p所指?結(jié)點(diǎn)為葉子?結(jié)點(diǎn)的條件?是____?__。25.邊稀疏的無?向圖采用_____?_存儲較省?空間。26.除第一個頂?點(diǎn)和最后一?個頂點(diǎn)相同?外，其余頂點(diǎn)不?重復(fù)的回路?，稱為_____?_。27.二分查找算?法的時間復(fù)?雜度是_____?_。28.要將序列{51，18，23，68，94，70，73}建成堆，則只需把1?8與_____?_相互交換?。三、應(yīng)用題(本大題共5?小題，每小題6分?，共30分)29.將題29圖?所示的一棵?二叉樹轉(zhuǎn)換?成對應(yīng)的森?林。題29圖題31圖題32圖30.給定權(quán)值｛3，9，13，5，7｝，構(gòu)造相應(yīng)的?哈夫曼（Huffm?an）樹，并計算其帶?權(quán)路徑長度?。31.寫出題31?圖的鄰接矩?陣和每個頂?點(diǎn)的入度與?出度。32.二叉排序樹?的各結(jié)點(diǎn)的?值依次為2?0~28，請在題32?圖中標(biāo)出各?結(jié)點(diǎn)的值。33.用冒泡排序?法對數(shù)據(jù)序?列（55，38，65，97，76，138，27，49）進(jìn)行排序，寫出排序過?程中的各趟?結(jié)果。四、算法設(shè)計題?(本大題共2?小題，每小題7分?，共14分)34.設(shè)線性表A?=（a1，a2，…,am），B=（b1,b2,…,bn），試寫一個按?下列規(guī)則合?并A，B為線性表?C的算法，使得C=（a1,b1,…,am,bm,bm+1,…,bn）當(dāng)m≤n時；或者C=（a1,b1,…,an,bn,an+1,…,am）當(dāng)m>n時。線性表A，B和C均以?帶頭結(jié)點(diǎn)的?單鏈表作為?存儲結(jié)構(gòu)，且C表利用?A表和B表?中的結(jié)點(diǎn)空?間構(gòu)成。（注意：單鏈表的長?度值m和n?均未顯式存?儲。）35.二叉樹的二?叉鏈表類型?定義如下：typed?efstruc?tbtnod?e{datat?ypedata;struc?tbtnod?e*lchil?d,*rchil?d;}bitre?ptr;寫出后根遍?歷根指針為?t的二叉樹?的遞歸算法?(voidposto?rder(bitre?ptr*t))。全國201?1年10月?數(shù)據(jù)結(jié)構(gòu)導(dǎo)?論試題課程代碼:02142?一、單項(xiàng)選擇題?(本大題共1?5小題，每小題2分?，共30分)1.設(shè)棧S和隊?列Q的初始?狀態(tài)為空，元素e1，e2，e3，e4，e5和e6?依次通過棧?S，元素退棧后?即進(jìn)入隊列?Q，若6個元素?的出隊序列?是e2，e4，e3，e6，e5，e1，則棧S的容?量至少為()A.2B.3C.42.設(shè)計一個判?別表達(dá)式中?左右括號是?否配對出現(xiàn)?的算法，采用的最佳?數(shù)據(jù)結(jié)構(gòu)為?()A.線性表的順?序存儲結(jié)構(gòu)?B.隊列C.線性表的鏈?式存儲結(jié)構(gòu)?D.棧3.下列程序段?的時間復(fù)雜?度為()i=0；s=0；while?（s<n）{i++；s=s+i；}A.O（）B.O(log2n?)C.O(n)D.O(n2)4.設(shè)A是n×n的對稱矩?陣，將A的對角?線及對角線?上方的元素?Aij(1≤i,j≤n,i≤j)以列優(yōu)先順?序存放在一?維數(shù)組元素?B［1］至B［n(n+1)/2］中，則元素Ai?j(i≤j)在B中的位?置為()A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-15.在有向圖G?的拓?fù)湫蛄?中，若頂點(diǎn)Vi?在頂點(diǎn)Vj?之前，則下列情形?不可能出現(xiàn)?的是()A.G中有弧<Vi，Vj>B.G中有一條?從Vi到V?j的路徑C.G中沒有弧?<Vi，Vj>D.G中有一條?從Vj到V?i的路徑6.下列序列中?，由第一趟快?速排序可得?到的序列（排序的關(guān)鍵?字類型是字?符串）是()A.［da，ax，eb，de，bb］ff［ha，gc］ B.［cd，eb，ax，da］ff［ha，gc，bb］C.［gc，ax，eb，cd，bb］ff［da，ha］ D.［ax，bb，cd，da］ff［eb，gc，ha］7.不穩(wěn)定的排?序方法是()A.直接插入排?序B.冒泡排序C.堆排序D.二路歸并排?序8.設(shè)散列表表?長m=14，散列函數(shù)為?h（k）=k%11，表中已有4?個記錄，如果用二次?探測法處理?沖突，關(guān)鍵字為4?9的記錄的?存儲位置是?()01234567891011121315386184A.3B.5C.89.若元素1，2，3依次進(jìn)棧?，則退棧不可?能出現(xiàn)的次?序是()A.3，2，1B.2，1，3C.3，1，2D.1，3，210.直接插入排?序的時間復(fù)?雜度是()A.O（n2）B.O（nlog2?n）C.O（n）D.O（log2n?）11.稀疏矩陣是?指()A.元素少的矩?陣B.有少量零元?素的矩陣C.有少量非零?元素的矩陣?D.行數(shù)、列數(shù)很少的?矩陣12.深度為k（k≥1）的二叉樹，結(jié)點(diǎn)數(shù)最多?有()A.2kB.2k-1C.2k-1D.2k-113.由帶權(quán)為9?，2，5，7的四個葉?子結(jié)點(diǎn)構(gòu)造?一棵哈夫曼?樹，該樹的帶權(quán)?路徑長度為?()A.23B.37C.4414.有n個頂點(diǎn)?的有向完全?圖的弧數(shù)為?()A.n2 B.2nC.n（n-1） D.2n（n+1）15.圖的深度優(yōu)?先搜索類似?于二叉樹的?()A.先根遍歷B.中根遍歷C.后根遍歷D.層次遍歷二、填空題(本大題共1?3小題，每小題2分?，共26分)16.下列程序段?的時間復(fù)雜?度為___?_____?_。for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;17.數(shù)據(jù)結(jié)構(gòu)中?結(jié)點(diǎn)按邏輯?關(guān)系依次排?列形成一條?“鎖鏈”的結(jié)構(gòu)是_?_____?___。18.在表長為n?的順序表上?做刪除運(yùn)算?，平均要移動?的結(jié)點(diǎn)個數(shù)?為____?_____?。19.在帶有頭結(jié)?點(diǎn)的單循環(huán)?鏈表hea?d中，指針p所指?結(jié)點(diǎn)為尾結(jié)?點(diǎn)的條件是?_____?____。20.隊列又稱為?_____?____的?線性表。21.順序棧被定?義為結(jié)構(gòu)類?型，含有兩個域?：data和?top，則對棧*sq進(jìn)行初?始化的操作?是____?_____?。22.對于任何一?棵二叉樹T?，如果其終端?結(jié)點(diǎn)數(shù)為n?0，度為2的結(jié)?點(diǎn)數(shù)為n2?，則n2=_____?____。23.一棵具有n?個結(jié)點(diǎn)的二?叉樹，采用二叉鏈?表存儲，則二叉鏈表?中指向孩子?結(jié)點(diǎn)的指針?有____?_____?個。24.若連通圖G?的頂點(diǎn)個數(shù)?為n，則圖G的生?成樹的邊數(shù)?為____?_____?。25.一個具有n?個頂點(diǎn)的無?向圖的邊數(shù)?最多為__?_____?__。26.中根遍歷二?叉排序樹所?得到的結(jié)點(diǎn)?訪問序列是?鍵值的__?_____?__序列。27.冒泡排序的?平均時間復(fù)?雜度為__?_____?__。28.將序列{60，20，23，68，94，70，73}建成堆，則只需把2?0與___?_____?_互相交換?。三、應(yīng)用題(本大題共5?小題，每小題6分?，共30分)29.如題29圖?所示，在棧的輸入?端元素的輸?入順序?yàn)锳?，B，C，D，進(jìn)棧過程中?可以退棧，寫出在棧的?輸出端以A?開頭和以B?開頭的所有?輸出序列。題29圖題30圖題31圖題32圖30.一棵二叉樹?如題30圖?所示，寫出該二叉?樹的先根遍?歷序列、中根遍歷序?列和后根遍?歷序列。31.將題31圖?所示的一棵?二叉樹轉(zhuǎn)換?成森林。32.對于有向無?環(huán)圖：（1）敘述求拓?fù)?排序算法的?基本步驟；（2）對于題32?圖，寫出它的4?個不同的拓?撲排序序列?。33.判別以下序?列是否為堆?。如果不是，則把它調(diào)整?為堆。（1）（100，86，48，73，35，39，42，57，66，21）；（2）（12，70，33，65，24，56，48，92，86，33）。四、算法設(shè)計題?(本大題共2?小題，每小題7分?，共14分)34.n個結(jié)點(diǎn)的?完全二叉樹?按結(jié)點(diǎn)編號?將值順序存?放在一維數(shù)?組元素A［1］至A［n］中，試編寫算法?實(shí)現(xiàn)將順序?存儲結(jié)構(gòu)轉(zhuǎn)?換為二叉鏈?表存儲結(jié)構(gòu)?，其中根結(jié)點(diǎn)?由tree?指向。35.試寫出冒泡?排序算法。全國201?1年1月數(shù)據(jù)結(jié)構(gòu)導(dǎo)?論試題課程代碼：02142?一、單項(xiàng)選擇題?(本大題共1?5小題，每小題2分?，共30分)1.在順序表中?查找第i個?元素，時間效率最?高的算法的?時間復(fù)雜度?為()A.O(1)B.O()C.O(log2n?)D.O(n)2.樹形結(jié)構(gòu)中?，度為0的結(jié)?點(diǎn)稱為()A.樹根 B.葉子C.路徑D.二叉樹3.已知有向圖?G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>，<V1,V3>，<V1,V4>，<V2,V5>，<V3,V5>,<V3,V6>，<V4,V6>，<V5,V7>,，<V6,V7>}，則圖G的拓?撲序列是()A.V1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V4.有關(guān)圖中路?徑的定義，表述正確的?是()A.路徑是頂點(diǎn)?和相鄰頂點(diǎn)?偶對構(gòu)成的?邊所形成的?序列B.路徑是不同?頂點(diǎn)所形成?的序列C.路徑是不同?邊所形成的?序列D.路徑是不同?頂點(diǎn)和不同?邊所形成的?集合5.串的長度是?指()A.串中所含不?同字母的個?數(shù)B.串中所含字?符的個數(shù)C.串中所含不?同字符的個?數(shù)D.串中所含非?空格字符的?個數(shù)6.組成數(shù)據(jù)的?基本單位是?()A.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)類型C.數(shù)據(jù)元素D.數(shù)據(jù)變量7.程序段i=n；x=0；do{x=x+5*i；i--；}while?（i>0）；的時間復(fù)雜?度為()A.O（1）B.O（n）C.O（n2）D.O(n3)8.與串的邏輯?結(jié)構(gòu)不同的?數(shù)據(jù)結(jié)構(gòu)是?()A.線性表B.棧C.隊列D.樹9.二叉樹的第?i（i≥1）層上所擁有?的結(jié)點(diǎn)個數(shù)?最多為()A.2iB.2iC.2i-1D.2i-110.設(shè)單鏈表中?指針p指向?結(jié)點(diǎn)A，若要刪除A?的直接后繼?，則所需修改?指針的操作?為()A.p->next=p->next->nextB.p=p->nextC.p=p->next->nextD.p->next=p11.下列排序算?法中，某一趟結(jié)束?后未必能選?出一個元素?放在其最終?位置上的是?()A.堆排序B.冒泡排序C.直接插入排?序D.快速排序12.設(shè)字符串S?1=″ABCDE?FG″，S2=″PQRST?″，則運(yùn)算S=CONCA?T(SUBST?R(S1,2,LENGT?H(S2)),SUBST?R(S1,LENGT?H(S2),2))后S的結(jié)果?為()A.″BCQR″B.″BCDEF?″C.″BCDEF?G″D.″BCDEF?EF″13.在平衡二叉?樹中插入一?個結(jié)點(diǎn)后造?成了不平衡?，設(shè)最低的不?平衡結(jié)點(diǎn)為?A，并且A的左?孩子的平衡?因子為-1，右孩子的平?衡因子為0?，則使其平衡?的調(diào)整方法?為()A.LL型B.LR型C.RL型D.RR型14.如果結(jié)點(diǎn)A?有3個兄弟?結(jié)點(diǎn)，而且B為A?的雙親，則B的度為?()A.1B.3C.4D.515.數(shù)據(jù)表A中?每個元素距?其最終位置?較近，則最省時間?的排序算法?是()A.堆排序B.插入排序C.直接選擇排?序D.快速排序二、填空題(本大題共1?3小題，每小題2分?，共26分)16.下列程序段?的時間復(fù)雜?度為___?_____?___。i=1；while?（i<n）i=i*2；17.向一個長度?為n的順序?表中第i（1≤i≤n）個元素之前?插入一個元?素時，需向后移動?_____?_____?_個元素。18.在循環(huán)雙鏈?表中，刪除最后一?個結(jié)點(diǎn)，其算法的時?間復(fù)雜度為?_____?_____?_。19.隊列的插入?操作在隊列?的____?_____?__部分進(jìn)?行。20.一個棧的輸?入序列是1?，2，3，…，n，輸出序列的?第一個元素?是n，則第i個輸?出元素為_?_____?_____?。21.一個10階?對稱矩陣A?，采用行優(yōu)先?順序壓縮存?儲下三角，a00為第?一個元素，其存儲地址?為1，每個元素占?有1個存儲?地址空間，則a85的?地址為__?_____?____。22.設(shè)字符串S?=″I□AM□A□STUDE?NT″（其中□表示空格字?符），則S的長度?為____?_____?__。23.在樹形結(jié)構(gòu)?中，沒有后繼的?結(jié)點(diǎn)是__?_____?____結(jié)?點(diǎn)。24.一棵深度為?n(n>1)的滿二叉樹?中共有__?_____?____個?結(jié)點(diǎn)。25.在無向圖中?，如果從頂點(diǎn)?v到頂點(diǎn)v?′有路徑，則稱v和v?′是____?_____?__。26.無向完全圖?G采用__?_____?____存?儲結(jié)構(gòu)較省?空間。27.在順序查找?、二分查找、索引查找和?散列查找四?種查找方法?中，平均查找長?度與元素個?數(shù)沒有關(guān)系?的查找方法?是____?_____?__。28.快速排序最?好情況下的?時間復(fù)雜度?為____?_____?__。三、應(yīng)用題(本大題共5?小題，每小題6分?，共30分)29.稀疏矩陣A?如下，寫出矩陣A?的三元組表?及矩陣A的?轉(zhuǎn)置矩陣的?三元組表。30.一棵二叉樹?的前根遍歷?序列為AB?CDEFG?，中根遍歷序?列為CBD?AEGF，試構(gòu)造出該?二叉樹。31.下述矩陣表?示一個無向?連通網(wǎng)，試畫出它所?表示的連通?網(wǎng)及該連通?網(wǎng)的最小生?成樹。32.給定表（80，90，50，70，75，60，40，100），試按元素在?表中的順序?將它們依次?插入一棵初?始時為空的?二叉排序樹?，畫出插入完?成后的二叉?排序樹。33.試寫出一組?鍵值（46，58，15，45，90，18，10，62）應(yīng)用直接插?入排序算法?從小到大排?序后各趟的?結(jié)果。四、算法設(shè)計題?(本大題共2?小題，每小題7分?，共14分)34.試分別寫出?二叉樹的先?根遍歷和中?根遍歷的遞?歸算法。35.試編寫以單?鏈表為存儲?結(jié)構(gòu)實(shí)現(xiàn)直?接選擇排序?的算法。HYPER?LINK"http://www.4juan?.com/ke.htm"2011年?1月全國自?考數(shù)據(jù)結(jié)構(gòu)?導(dǎo)論參考答?案2010年?10月數(shù)據(jù)結(jié)構(gòu)導(dǎo)?論試題課程代碼：02142?一、單項(xiàng)選擇題?(本大題共1?5小題，每小題2分?，共30分)1．下列描述中?正確的是()A.數(shù)據(jù)元素是?數(shù)據(jù)的最小?單位B.數(shù)據(jù)結(jié)構(gòu)是?具有結(jié)構(gòu)的?數(shù)據(jù)對象C.數(shù)據(jù)結(jié)構(gòu)是?指相互之間?存在一種或?多種特定關(guān)?系的數(shù)據(jù)元?素的集合D.算法和程序?原則上沒有?區(qū)別，在討論數(shù)據(jù)?結(jié)構(gòu)時兩者?是通用的2．歸并排序的?時間復(fù)雜度?是()A．O（n2）B.O（nlog2?n）C.O（n）D.O（log2n?）3．二分查找的?時間復(fù)雜度?是()A．O（n2）B.O（nlog2?n）C.O（n）D.O（log2n?）4．順序存儲的?表中有90?000個元?素，已按關(guān)鍵字?值升序排列?，假設(shè)對每個?元素進(jìn)行查?找的概率相?同，且每個元素?的關(guān)鍵字值?皆不相同，用順序查找?法查找時，需平均比較?的次數(shù)為()A．25000?B.30000?C.45000?5．散列文件是?一種()A．順序文件B.索引文件C.鏈接文件D.計算尋址文?件6．兩個矩陣A?：m×n，B：n×p相乘，其時間復(fù)雜?度為()A．O(n) B.O(mnp)C.O(n2)D.O（mp）7.常用于函數(shù)?調(diào)用的數(shù)據(jù)?結(jié)構(gòu)是()A.棧B.隊列C.鏈表D.數(shù)組8．二維數(shù)組A?［n］［m］以列優(yōu)先順?序存儲，數(shù)組A中每?個元素占用?1個字節(jié)，A［1］［1］為首元素，其地址為0?，則元素A［i］［j］的地址為()A.（i-1）×m+(j-1)B.(j-1)×n+(i-1)C.(j-1)×n+ID.j×n+i9.圖的廣度優(yōu)?先搜索使用?的數(shù)據(jù)結(jié)構(gòu)?是()A．隊列B.樹C.棧D.集合10．序列（21,19,37,5,2）經(jīng)冒泡排序?法由小到大?排序，在第一次執(zhí)?行交換后所?得結(jié)果為()A．(19，21，37，5，2)B.(21，19，5，37，2)C.(21，19，37，2，5)D.(2，21，19，37，5)11．?dāng)?shù)據(jù)在計算?機(jī)存儲器內(nèi)?表示時，根據(jù)結(jié)點(diǎn)的?關(guān)鍵字直接?計算出該結(jié)?點(diǎn)的存儲地?址，這種方法稱?為()A．索引存儲方?法B.順序存儲方?法C.鏈?zhǔn)酱鎯Ψ?法D.散列存儲方?法12．在單鏈表中?，存儲每個結(jié)?點(diǎn)有兩個域?，一個是數(shù)據(jù)?域，另一個是指?針域，指針域指向?該結(jié)點(diǎn)的()A．直接前趨B.直接后繼C.開始結(jié)點(diǎn)D.終端結(jié)點(diǎn)13．在已知頭指?針的單鏈表?中，要在其尾部?插入一新結(jié)?點(diǎn)，其算法所需?的時間復(fù)雜?度為()A．O（1）B.O（log2n?）C.O（n）D.O（n2）14．在鏈隊列中?執(zhí)行入隊操?作，()A．需判別隊是?否空B.需判別隊是?否滿C.限制在鏈表?頭p進(jìn)行D.限制在鏈表?尾p進(jìn)行15．一整數(shù)序列?26，59，77，31，51，11，19，42，以二路歸并?排序從小到?大排序，第一階段的?歸并結(jié)果為?()A.31，51，11，42，26，77，59，19 B.26，59，31，77，11，51，19，42C.11，19，26，31，42，59，51，77 D.26，11，19，31，51，59，77，42二、填空題(本大題共1?3小題，每小題2分?，共26分)16．下列程序段?的時間復(fù)雜?度為___?____。i=0；s=0；while?（s<n）{i++；s=s+i；}17．?dāng)?shù)據(jù)的存儲?結(jié)構(gòu)被分為?順序存儲結(jié)?構(gòu)、_____?__、散列存儲結(jié)?構(gòu)和索引存?儲結(jié)構(gòu)4種?。18．從一個長度?為n的順序?表中刪除第?i個元素（1≤i≤n）時，需向前移動?_____?__個元素?。19．在單鏈表中?，插入一個新?結(jié)點(diǎn)需修改?_____?__個指針?。20．在隊列結(jié)構(gòu)?中，允許插入的?一端稱為_?