2023年數(shù)據(jù)結構試題庫答案nana

數(shù)據(jù)結構試題及答案一、單項選擇題一個算法應當是（）。A)程序 B)問題求解環(huán)節(jié)的描述C)要滿足五個基本屬性 D)A和C算法指的是（）。A)計算機程序 B)解決問題的計算方法C)排序算法 D)解決問題的有限運算序列。與數(shù)據(jù)元素自身的形式、內(nèi)容、相對位置、個數(shù)無關的是數(shù)據(jù)的（）。A)存儲結構 B)邏輯結構 C)算法 D)操作從邏輯上可以把數(shù)據(jù)結構分為（）兩大類。A)動態(tài)結構、靜態(tài)結構 B)順序結構、鏈式結構C)線性結構、非線性結構 D)初等結構、構造型結構下列敘述中對的的是()。A）一個邏輯數(shù)據(jù)結構只能有一種存儲結構B）數(shù)據(jù)的邏輯結構屬于線性結構，存儲結構屬于非線性結構C）一個邏輯數(shù)據(jù)結構可以有多種存儲結構，且各種存儲結構不影響數(shù)據(jù)解決的效率D）一個邏輯數(shù)據(jù)結構可以有多種存儲結構，且各種存儲結構影響數(shù)據(jù)解決的效率數(shù)據(jù)的基本單位是（） A)數(shù)據(jù)項 B)數(shù)據(jù)類型 C)數(shù)據(jù)元素 D)數(shù)據(jù)變量下列程序的時間復雜度為（）i=0；s=0；while（s<n）{i++；s=s+i；}A)O（） B)O（） C)O（n） D)O（n2）下列程序段的漸進時間復雜度為（）。for(inti=1;i<=n;i++)for(intj=1;j<=m;j++)A[i][j]=i*j;A）O(m2) B）O(n2) C）O(m*n) D）(m+n)程序段如下：sum=0；for(i=1;i<=n;i++)for(j=1;j<=n;j++)sum++；其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（）。A）O(n） B)O(nlogn) C)O(n3) D)O(n2)在下面的程序段中，對x的賦值語句的頻度為（）。for(i=1;i>=n;i++)for(j=1;j>=n;j++)x:=x+1;A)O(2n) B)O(n) C)O(n2) D)O(log2n)程序段for(i:=n-1;i<=1;i--）for(j:=1;j>=i;j++)if(a[j]>a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}其中n為正整數(shù)，則最后一行的語句頻度在最壞情況下是（）。A)O(n） B)O(nlogn) C)O(n3) D)O(n2)設有一個遞歸算法如下：intfact(intn){/*大于等于0*/if(n<=0)return1;elsereturnn*fact(n-1);}則計算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（）。A)n B)n+1 C)n+2 D)n-1下述程序段中語句①的頻度是（）。s=0;for(i=1;i<m;i++)for(j=0;j<=i;j++)s+=j;A) B) C) D)若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則最節(jié)省運算時間的存儲方式是（）。A)單鏈表 B)僅有頭指針的單循環(huán)鏈表C)雙鏈表 D)僅有尾指針的單循環(huán)鏈表求循環(huán)鏈表中當前結點的后繼和前驅(qū)的時間復雜度分別是（）。A)O(n)和O(1) B)O(1)和O(1) C)O(1)和O(n) D)O(n)和O(n)求單鏈表中當前結點的后繼和前驅(qū)的時間復雜度分別是（）。 A)O（n）和O（1） B)O（1）和O（1） C)O（1）和O（n） D)O(n)和O（n）非空的單循環(huán)鏈表的頭指針為head,尾指針為rear，則下列條件成立的是（）。 A)rear->next==head B)rear->next->next==head C)head->next==rear D)head->next->next==rear從一個長度為n的順序表中刪除第i個元素（1≤i≤n）時，需向前移動的元素的個數(shù)是（）。A)n-i B)n-i+1 C)n-i-1 D)已知一個有序表為（13，18，24，35，47，50，62，83，90，115，134），當二分檢索值為90的元素時，檢索成功需比較的次數(shù)是（）。A)1 B)2 C)3 D)假設以行優(yōu)先順序存儲三維數(shù)組R[6][9][6]，其中元素R[0][0][0]的地址為2100，且每個元素占4個存儲單元，則存儲地址為2836的元素是（）。A)R[3][3][3] B)R[3][3][4] C)R[4][3][5] D)R[4][3][4]設有一個10階的對稱矩陣A，采用壓縮存儲方式以行序為主序存儲，a00為第一個元素，其存儲地址為0，每個元素占有1個存儲地址空間，則a45的地址為（）。A)13 B)35 C)17 D)36線性表采用鏈式存儲時，節(jié)點的存儲的地址（）。A)必須是不連續(xù)的 B)連續(xù)與否均可C)必須是連續(xù)的 D)和頭節(jié)點的存儲地址相連續(xù)用鏈表表達線性表的優(yōu)點是（）。A)便于隨機存取 B)花費的存儲空間比順序表少C)數(shù)據(jù)元素的物理順序與邏輯順序相同D)便于插入與刪除鏈表不具有的特點是（）。A)插入、刪除不需要移動元素 B)可隨機訪問任一元素C)不必事先估計存儲空間 D)所需空間與線性長度成正比在長度為n的順序表中刪除第i個元素(1≤i≤n)時，元素移動的次數(shù)為()。A)n-i+1 B)i C)i+1 D)n-i采用順序搜索方法查找長度為n的順序表達，搜索成功的平均搜索長度為（）。A)n B)n/2 C)(n-1)/2 D)將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為（）。A)O(1) B)O(n) C)O(m) D)O(m+n)若不帶頭結點的單鏈表的頭指針為head，則該鏈表為空的鑒定條件是()。A)head==NULL B)head->next==NULL C)head!=NULL D)head->next==head某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節(jié)省運算時間。A)單鏈表 B)僅有頭指針的單循環(huán)鏈表C)雙鏈表 D)僅有尾指針的單循環(huán)鏈表若允許表達式內(nèi)多種括號混合嵌套，則為檢查表達式中括號是否對的配對的算法，通常選用的輔助結構是（）。 A)棧 B)線性表 C)隊列 D)二叉排序樹順序棧S中top為棧頂指針，指向棧頂元素所在的位置，elem為存放棧的數(shù)組，則元素e進棧操作的重要語句為（）。A)s.elem［top］=e； s.top=s.top+1； B)s.elem［top+1］=e；s.top=s.top+1；C)s.top=s.top+1； s.elem［top+1］=e； D)s.top=s.top+1；s.elem［top］=e；循環(huán)隊列sq中，用數(shù)組elem［0··25］存放數(shù)據(jù)元素，sq.front指示隊頭元素的前一個位置，sq.rear指示隊尾元素的當前位置，設當前sq.front為20，sq.rear為12，則當前隊列中的元素個數(shù)為（）。A)8 B)16 C)17 D)18鏈式棧與順序棧相比，一個比較明顯的優(yōu)點是（）。A)插入操作更加方便 B)通常不會出現(xiàn)棧滿的情況C)不會出現(xiàn)棧空的情況 D)刪除操作更加方便一個遞歸的定義可以用遞歸過程求解，也可以用非遞歸過程求解，但單從運營時間來看，通常遞歸過程比非遞歸過程（）。A)較快 B)較慢 C)相同 D)不定若已知一個棧的入棧序列是1,2,3,4……n，其輸出序列為p1,p2,p3,……pn，若p1==n,則pi為（）。 A)i B)n==i C)n-i+1 D)不擬定一個棧的入棧序列是a,b,c,d,e，則棧的不也許的輸出序列是()。A)edcba B)decba C)dceab D)abcde若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則不也許出現(xiàn)的出棧序列是()。A)2，4，3，1，5，6 B)3，2，4，1，6，5C)4，3，2，1，5，6 D)2，3，5，1，6，4對于棧操作數(shù)據(jù)的原則是（）。A)先進先出 B)后進先出 C)后進后出 D)不分順序棧和隊列的共同點是（）。A)都是先進先出 B)都是先進后出C)只允許在端點處插入和刪除元素 D)沒有共同點一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是（）。A)4,3,2,1 B)1,2,3,4 C)1,4,3,2 D)3,2,4,1設數(shù)組data[m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出對操作后其頭指針front值為（）。A)front=front+1 B)front=(front+1)%(m-1)C)front=(front-1)%m D)front=(front+1)%m引起循環(huán)隊列隊頭位置發(fā)生變化的操作是()。A)出隊 B)入隊 C)取隊頭元素 D)取隊尾元素設以數(shù)組A[m]存放循環(huán)隊列的元素，其頭尾指針分別為front和rear，則當前隊列中的元素個數(shù)為（）。A）(rear-front+m)%mB）rear-front+1 C）(front-rear+m)%mD）二維數(shù)組A[12][18]采用列優(yōu)先的存儲方法，若每個元素各占3個存儲單元，且A[0][0]地址為150，則元素A[9][7]的地址為()。A)429 B)432 C)435設有一個10階的對稱矩陣A[10][10]，采用壓縮方式按行將矩陣中下三角部分的元素存入一維數(shù)組B[]中，A[0][0]存入B[0]中，則A[8][5]在B[]中（）位置。A)32 B)33 C)41 若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(涉及主對角線上所有元素)依次存放于一維數(shù)組B［1..(n(n+1))/2］中，則在B中擬定aij（i<j）的位置k的關系為()。A)i*(i-1)/2+j B)j*(j-1)/2+i C)i*(i+1)/2+j D)j*(j+1)/2+i對稀疏矩陣進行壓縮存儲目的是（）。A)便于進行矩陣運算 B)便于輸入和輸出C)節(jié)省存儲空間 D)減少運算的時間復雜度對廣義表L=((a,b),(c,d),(e,f))執(zhí)行操作tail(tail(L))的結果是()。A)(e,f) B)((e,f)) C)(f) D)()設廣義表L=（（a,b,c）），則L的長度和深度分別為（）。A)1和1 B)1和3 C)1和2 D)樹中所有結點的度之和等于所有結點數(shù)加（）。A)0 B)1 C)-1 D)2在一棵具有n個結點的二叉鏈表中，所有結點的空域個數(shù)等于（）。A)n B)n-1 C)n+1 D)2*n某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A)空或只有一個結點 B)高度等于其節(jié)點數(shù)C)任一結點無左孩子 D)任一結點無右孩子具有10個結點的二叉樹中，度為0的結點數(shù)為4，則度為2的結點數(shù)為（）A)3 B)4 C)5 D)6除第一層外，滿二叉樹中每一層結點個數(shù)是上一層結點個數(shù)的（）A)1/2倍 B)1倍 C)2倍 D)3倍對一棵有100個結點的完全二叉樹按層編號，則編號為49的結點，它的父結點的編號為（）A)24 B)25 C)98 D)99可以惟一地轉(zhuǎn)化成一棵一般樹的二叉樹的特點是（）A)根結點無左孩子 B)根結點無右孩子 C)根結點有兩個孩子 D)根結點沒有孩子設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數(shù)至少為（）。A)2h B)2h-1 C)2h+1 D)h+1在一棵度為3的樹中，度為3的節(jié)點個數(shù)為2，度為2的節(jié)點個數(shù)為1，則度為0的節(jié)點個數(shù)為（）。 A)4 B)5 C)6 D)設森林F相應的二叉樹為B，它有m個結點，B的根為p，p的右子樹結點個數(shù)為n,森林F中第一棵 子樹的結點個數(shù)是（）。A)m-n B)m-n-1 C)n+1 D)條件局限性，無法擬定將一株有100個節(jié)點的完全二叉樹從上到下，從左到右依次進行編號，根節(jié)點的編號為1，則編號為49的節(jié)點的左孩子編號為（）。A)98 B)89 C)50 D)沒有孩子下列圖示的順序存儲結構表達的二叉樹是(A)樹最適合用來表達（）。A)有序數(shù)據(jù)元素 B)無序數(shù)據(jù)元素 C)元素之間具有分支層次關系的數(shù)據(jù) D)元素之間無聯(lián)系的數(shù)據(jù)在一個非空二叉樹的中序遍歷序列中，根結點的右邊（）。 A)只有右子樹上的所有結點 B)只有右子樹上的部分結點C)只有左子樹的上的部分結點 D)只有左子樹上的所有結點任何一棵二叉樹的葉結點在先序、中序和后序遍歷序列中相對順序（）。 A)不發(fā)生改變 B)發(fā)生改變 C)不能擬定 D)以上都不對在有n個葉子結點的哈夫曼樹中，其結點總數(shù)為（）。 A)不擬定 B)2n C)2n+1 D)2n-1權值為{1,2,6,8}的四個結點構成的哈夫曼樹的帶權途徑長度是（）。 A)18 B)28 C)19 D)29對一個滿二叉樹，m個樹葉，k個分枝結點，n個結點，則（）。 A)n=m+1 B)m+1=2n C)m=k-1 D)n=2k+1在具有n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為（）。A)e B)2e C)n2-e D)n2-2e若采用鄰接矩陣翻存儲一個n個頂點的無向圖，則該鄰接矩陣是一個（）。 A)上三角矩陣 B)稀疏矩陣 C)對角矩陣 D)對稱矩陣在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍。 A)1/2 B)1 C)2 D)4在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍。 A)1/2 B)1 C)2 D)4對于含n個頂點和e條邊的圖，采用鄰接矩陣表達的空間復雜度為（）。A) O（n） B) O(e) C)O(n+e) D)O(n2)假如求一個連通圖中以某個頂點為根的高度最小的生成樹，應采用（）。A) 深度優(yōu)先搜索算法 B) 廣度優(yōu)先搜索算法C)求最小生成樹的prim算法 D)拓撲排序算法n個頂點的連通圖至少中具有()。 A)n-1 B)n C)n+1 D)0n個頂點的完全有向圖中具有()。A)n-1條有向邊B)n條有向邊 C)n(n-1)/2條有向邊D)n(n-1)條有向邊假設一個有n個頂點和e條弧的有向圖用鄰接表表達，則刪除預某個頂點vi相關的所有弧的時間復雜度是（）。 A)O(n) B)O(e) C)O(n+e) D)O(n*e)在無向圖中定義頂點Vi域Vj之間的途徑為從Vi到達Vj的一個（）。A)頂點序列 B)邊序列 C)權值總和D)邊的條數(shù)無向圖G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對該圖進行深度優(yōu)先遍歷，得到的頂點序列對的的是（）。A)a,b,e,c,d,f B)a,c,f,e,b,d C)a,e,b,c,f,d D)a,e,d,f,c,b下面哪一方法可以判斷出一個有向圖是否有環(huán)（回路）。A)求節(jié)點的度 B)拓撲排序 C)求最短途徑 D)求關鍵途徑圖的廣度優(yōu)先搜索類似于樹的（）順序遍歷。A)先根 B)中根 C)后根 D)層次在圖采用鄰接表存儲時，求最小生成樹的Prim算法的時間復雜度為()。A)O(n) B)O(n+e) C)O(n2) D)O(n3)已知有向圖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,V7 B)V1,V3,V2,V6,V4,V5,V7C)V1,V3,V4,V5,V2,V6,V7 D)V1,V2,V5,V3,V4,V6,V7關鍵途徑是事件結點網(wǎng)絡中（）。A)從源點到匯點的最長途徑 B)從源點到匯點的最短途徑C)最長回路 D)最短回路有n個結點的有向完全圖的弧數(shù)是（）。A)n2 B)2n C)n(n-1) D)2n(n+1)設圖的鄰接鏈表如題12圖所示，則該圖的邊的數(shù)目是（）。83題圖83題圖A)4 B)5 C)10 D)20在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的（）倍。A)1/2 B)1 C)2 D)4在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍。A)1/2 B)1 C)2 D)4有8個結點的無向圖最多有（）條邊。A)14 B)28 C)56 D)112有8個結點的無向連通圖最少有（）條邊。A)5 B)6 C)7 D)8有8個結點的有向完全圖有（）條邊。A)14 B)28 C)56 D)112用鄰接表表達圖進行廣度優(yōu)先遍歷時，通常是采用（）來實現(xiàn)算法的。A)棧 B)隊列 C)樹 D)圖用鄰接表表達圖進行深度優(yōu)先遍歷時，通常是采用（）來實現(xiàn)算法的。A)棧 B)隊列 C)樹 D)圖已知圖的鄰接矩陣，根據(jù)算法思想，則從頂點0出發(fā)按深度優(yōu)先遍歷的結點序列是（）。 A)0243156 B)0136542 C)0423165 D)0361542建議：0134256已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點0出發(fā)，按深度優(yōu)先遍歷的結點序列是（）。A)0243156 B)0135642 C)0423165 D)0134256已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點0出發(fā)，按廣度優(yōu)先遍歷的結點序列是（）。A)0243651 B)0136425 C)0423156 D)0134256（建議：0123456）已知圖的鄰接矩陣同上題8，根據(jù)算法，則從頂點0出發(fā)，按廣度優(yōu)先遍歷的結點序列是（）。A)0243165 B)0135642 C)0123465 D)0123456已知圖的鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按深度優(yōu)先遍歷的結點序列是（）。A)132 B)0231 C)0321 D)0123已知圖的鄰接表如下所示，根據(jù)算法，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結點序列是（）。A)0321 B)0123 C)0132 D)0312深度優(yōu)先遍歷類似于二叉樹的（）。A)先序遍歷 B)中序遍歷 C)后序遍歷 D)層次遍歷廣度優(yōu)先遍歷類似于二叉樹的（）。A)先序遍歷 B)中序遍歷 C)后序遍歷 D)層次遍歷任何一個無向連通圖的最小生成樹（）。A)只有一棵 B)一棵或多棵 C)一定有多棵 D)也許不存在（注，生成樹不唯一，但最小生成樹唯一，即邊權之和或樹權最小的情況唯一）在分析折半查找的性能時經(jīng)常加入失敗節(jié)點，即外節(jié)點，從而形成擴充的二叉樹。若設失敗節(jié)點i所在層次為Li，那么查找失敗到達失敗點時所做的數(shù)據(jù)比較次數(shù)是（）。A)Li+1 B)Li+2 C)Li-1 D)Li向一個有127個元素原順序表中插入一個新元素并保存本來順序不變，平均要移動（）個元素。 A)8 B)63.5 C)63 D)7由同一組關鍵字集合構造的各棵二叉排序樹()。A)其形態(tài)不一定相同，但平均查找長度相同B)其形態(tài)不一定相同，平均查找長度也不一定相同C)其形態(tài)均相同，但平均查找長度不一定相同D)其形態(tài)均相同，平均查找長度也都相同衡量查找算法效率的重要標準是（）。A)元素的個數(shù) B)所需的存儲量 C)平均查找長度D)算法難易限度適合對動態(tài)查找表進行高效率查找的組織結構是（）。A)有序表 B)分塊有序表 C)二叉排序樹D)快速排序能進行二分查找的線性表,必須以（）。A)順序方式存儲，且元素按關鍵字有序B)鏈式方式存儲，且元素按關鍵字有序C)順序方式存儲，且元素按關鍵字分塊有序D)鏈式方式存儲，且元素按關鍵字分塊有序為使平均查找長度達成最小,當由關鍵字集合{05,11,21,25,37,40,41,62,84}構建二叉排序樹時,第一個插入的關鍵字應為（）A) 5 B)37 C)41 D)62對關鍵字序列(56,23,78,92,88,67,19,34)進行增量為3的一趟希爾排序的結果為()。A)(19,23,56,34,78,67,88,92) B)23,56,78,66,88,92,19,34)C)(19,23,34,56,67,78,88,92) D)(19,23,67,56,34,78,92,88)用某種排序方法對關鍵字序列{35,84,21,47,15,27,68,25,20}進行排序時，序列的變化情況如下：20,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,84則采用的方法是（）。A)直接選擇排序 B)希爾排序 C)堆排序 D)快速排序一組記錄的排序碼為(46,79,56,38,40,84)，則運用快速排序的方法，以第一個記錄為基準得到的第一次劃分結果為（）。 A)38,40,46,56,79,84 B)40,38,46,79,56,84 C)40,38,46,56,79,84 D)快速排序在最壞情況下的時間復雜度是（）A)O(n2log2n) B)O(n2) C)O(nlog2n) D)O(log2n)下列排序算法中不穩(wěn)定的是（）。A)直接選擇排序 B)折半插入排序 C)冒泡排序 D)快速排序?qū)Υ判虻脑匦蛄羞M行劃分，將其分為左、右兩個子序列，再對兩個子序列進行同樣的排序操作，直到子序列為空或只剩下一個元素為止。這樣的排序方法是（）。A)直接選擇排序 B)直接插入排序 C)快速排序 D)冒泡排序?qū)?個不同的數(shù)據(jù)進行排序，至多需要比較（）次。A)8B)9 C)10 D)25排序算法中，第一趟排序后，任一元素都不能擬定其最終位置的算法是（）。A)選擇排序 B)快速排序 C)冒泡排序 D)插入排序排序算法中，不穩(wěn)定的排序是（）。A)直接插入排序 B)冒泡排序 C)堆排序 D)選擇排序排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的對的位置上的方法，稱為（）.A)希爾排序 B)冒泡排序C)插入排序D)選擇排序從未排序序列中挑選元素，并將其依次插入已排序序列（初始時為空）的一端的方法，稱為（）。A)希爾排序 B)歸并排序C)插入排序D)選擇排序?qū)Γ顐€不同的排序碼進行冒泡排序，在下列哪種情況下比較的次數(shù)最多。（）A)從小到大排列好的 B)從大到小排列好的C)元素無序 D)元素基本有序?qū)Γ顐€不同的排序碼進行冒泡排序，在元素無序的情況下比較的次數(shù)為（）。A)n+1B)n C)n-1 D)n(n-1)/2快速排序在下列哪種情況下最易發(fā)揮其長處。（）A)被排序的數(shù)據(jù)中具有多個相同排序碼B)被排序的數(shù)據(jù)已基本有序C)被排序的數(shù)據(jù)完全無序D)被排序的數(shù)據(jù)中的最大值和最小值相差懸殊對有n個記錄的表作快速排序，在最壞情況下，算法的時間復雜度是（）。A)O(n) B)O(n2) C)O(nlog2n) D)O(n3)若一組記錄的排序碼為（46,79,56,38,40,84），則運用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為（）。A)38,40,46,56,79,84B)40,38,46,79,56,84C)40,38，46,56,79,84 D)40,38,46,84,56,79下列關鍵字序列中，（）是堆。A)16,72,31,23,94,53 B)94,23,31,72,16,53C)16,53,23,94，31,72 D)16,23,53,31,94,72堆是一種（）排序。A)插入 B)選擇 C)互換 D)歸并堆的形狀是一棵（）。A)二叉排序樹B)滿二叉樹 C)完全二叉樹D)平衡二叉樹若一組記錄的排序碼為（46,79,56,38,40,84），則運用堆排序的方法建立的初始堆為（）。A)79,46,56,38,40,84 B)84,79,56,38,40,46C)84,79,56,46,40,38 D)84,56,79,40,46,38下述幾種排序方法中，規(guī)定內(nèi)存最大的是（）。A)插入排序 B)快速排序 C)歸并排序D)選擇排序有一組數(shù)據(jù)（15，9，7，8，20，-1，7，4），用堆排序的篩選方法建立的初始堆為（）。A)-1，4，8，9，20，7，15，7 B)-1，7，15，7，4，8，20，9C)-1，4，7，8，20，15，7，9 D)A，B，C均不對。51．下列四個序列中，哪一個是堆（）。A)75,65,30,15,25,45,20,10 B)75,65,45,10,30,25,20,15C)75,45,65,30,15,25,20,10 D)75,45,65,10,25,30,20,15以下序列不是堆的是()。A)(100,85,98,77,80,60,82,40,20,10,66) B)(100,98,85,82,80,77,66,60,40,20,10)C)(10,20,40,60,66,77,80,82,85,98,100) D)(100,85,40,77,80,60,66,98,82,10,20)快速排序方法在（）情況下最不利于發(fā)揮其長處。A)要排序的數(shù)據(jù)量太大 B)要排序的數(shù)據(jù)中具有多個相同值C)要排序的數(shù)據(jù)個數(shù)為奇數(shù) D)要排序的數(shù)據(jù)已基本有序?qū)﹃P鍵碼序列28，16，32，12，60，2，5，72快速排序，從小到大一次劃分結果為（）。A)(2,5,12,16)26(60,32,72) B)(5,16,2,12)28(60,32,72)C)(2,16,12,5)28(60,32,72) D)(5,16,2,12)28(32,60,72)對下列關鍵字序列用快速排序法進行排序時，速度最快的情形是（）。A){21,25,5,17,9,23,30} B){25,23,30,17,21,5,9}C){21,9,17,30,25,23,5} D){5,9,17,21,23,25,30}二、填空題數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和運算等的學科。數(shù)據(jù)結構被形式地定義為（D,R），其中D是數(shù)據(jù)元素的有限集合，R是D上的關系有限集合。數(shù)據(jù)結構涉及數(shù)據(jù)的邏輯結構、數(shù)據(jù)的存儲結構和數(shù)據(jù)的運算這三個方面的內(nèi)容。數(shù)據(jù)結構按邏輯結構可分為兩大類，它們分別是線性結構和非線性結構。線性結構中元素之間存在一對一關系，樹形結構中元素之間存在一對多關系，圖形結構中元素之間存在多對多關系。在線性結構中，第一個結點沒有前驅(qū)結點，其余每個結點有且只有1個前驅(qū)結點；最后一個結點沒有后續(xù)結點，其余每個結點有且只有1個后續(xù)結點。在樹形結構中，樹根結點沒有前驅(qū)結點，其余每個結點有且只有1個前驅(qū)結點；葉子結點沒有后續(xù)結點，其余每個結點的后續(xù)結點數(shù)可以任意多個。在圖形結構中，每個結點的前驅(qū)結點數(shù)和后續(xù)結點數(shù)可以任意多個。數(shù)據(jù)的存儲結構可用四種基本的存儲方法表達，它們分別是順序、鏈式、索引和散列。數(shù)據(jù)的運算最常用的有5種，它們分別是插入、刪除、修改、查找、排序。一個算法的效率可分為時間效率和空間效率。對于給定的n個元素,可以構造出的邏輯結構有集合，線性表，樹，圖四種。順序映象的特點是借助元素在存儲器中的相對位置來表達數(shù)據(jù)元素之間的邏輯關系。非順序映象的特點是借助是指示元素存儲地址的指針表達數(shù)據(jù)元素之間的邏輯關系。任何一個算法的設計取決于選定邏輯結構，而算法的實現(xiàn)依賴于采用的存儲結構。數(shù)據(jù)類型是一組___________性質(zhì)相同的值集合以及定義在這個值集合上的一組操作的總稱。數(shù)據(jù)對象是___________性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。假如操作不改變原邏輯結構的“值”，而只是從中提取某些信息作為運算結果，則稱該類運算為型運算。引用算法的健壯特性是指做為一個好的算法，當輸入的數(shù)據(jù)非法時，也能適本地做出對的反映或進行相應的解決，而不會產(chǎn)生一些莫名其妙的輸出結果。算法分析不是針對實際執(zhí)行時間的精確的算出算法執(zhí)行具體時間的分析，而是針對算法中語句的執(zhí)行次數(shù)做出估計，從中得到算法執(zhí)行時間的信息。T(n)=O(f(n))，它表達隨問題規(guī)模n的增大算法的執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸進時間復雜度，簡稱時間復雜度。若算法執(zhí)行時所需要的輔助空間相對于輸入數(shù)據(jù)量而言是個常數(shù)，則稱這個算法為原地工作，輔助空間為O(1)。在帶有頭結點的單鏈表中L中，第一個元素結點的指針是。L->next在一個帶頭節(jié)點的單循環(huán)鏈表中，p指向尾結點的直接前驅(qū)，則指向頭結點的指針head可用p表達為head=。p->next->next設單鏈表的結點結構為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結點，指針py指向data為y的新結點,若將結點y插入結點x之后，則需要執(zhí)行以下語句:py->next=px->next;px->next=py。對于棧操作數(shù)據(jù)的原則是。后進先出設以數(shù)組A[m]存放循環(huán)隊列的元素，其頭尾指針分別為front和rear，則當前隊列中的元素個數(shù)為。(rear-front+m)%m若已知一個棧的入棧序列是1,2,3,4……n，其輸出序列為p1,p2,p3,……pn，若p1==n,則pi為。n-i+1隊列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。通常程序在調(diào)用另一個程序時，都需要使用一個棧來保存被調(diào)用程序內(nèi)分派的局部變量。形式參數(shù)的存儲空間以及返回地址。棧下溢是指在___棧空_____時進行出棧操作。用P表達入棧操作，D表達出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應的P和D的操作串為_______。PDPPDPDD在具有n個單元的循環(huán)隊列中，隊滿共有n-1個元素。隊列是被限定為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。循環(huán)隊列的引入，目的是為了克服_______假溢出。所謂稀疏矩陣指的是_______非零元很少(t<<m*n)且分布沒有規(guī)律。在稀疏矩陣表達所相應的三元組線性表中，每個三元組元素按行為主序，列號為輔序的順序排列。二位數(shù)組Am×n按行優(yōu)先順序存儲在內(nèi)存中，元素a00地址為loc(a00),每個元素在內(nèi)存中占d個字節(jié)，元素aij的地址計算公式為loc(aij)=loc(a00)＋(i*n+j)*d。去除廣義表LS=(a1,a2,a3,……，an)中第1個元素，由其余元素構成的廣義表稱為LS的____表尾_____。樹內(nèi)個結點的度最大值稱為樹的度。一個二叉樹第5層節(jié)點最多有16個。已知完全二叉樹T的第5層只有7個結點，則該樹共有____11____個葉子結點。在一棵二叉樹中，度為零的結點的個數(shù)為N0,度為2的結點的個數(shù)為N2,則有N0=______N2+1。假設用于通信的電文由8個字母組成，其頻率分別為7,19,2,6,32,3,27,10。設計哈夫曼編碼，其中字母的編碼長度最大是5位。一棵具有257個結點的完全二叉樹，它的深度為。9圖的深度優(yōu)先遍歷序列不是惟一的。在圖中，任何兩個結點之間都也許存在關系，因此圖的數(shù)據(jù)元素之間時一種多對多的關系。在有向圖中，以頂點v為終點的邊的數(shù)目稱為v的___入度_____。一個無向圖有n個頂點，e條邊，則所以頂點的度數(shù)之和為2e。圖有鄰接矩陣、鄰接表等存儲結構，遍歷圖有深度優(yōu)先遍歷、廣度優(yōu)先遍歷等方法。有向圖G用鄰接表矩陣存儲，其第i行的所有非零元素之和等于頂點i的。出度假如n個頂點的圖是一個環(huán)，則它有棵生成樹。n（以任意一頂點為起點，得到n-1條邊）n個頂點e條邊的圖，若采用鄰接矩陣存儲，則空間復雜度為。O(n2)n個頂點e條邊的圖，若采用鄰接表存儲，則空間復雜度為。O(n+e)設有一稀疏圖G，則G采用鄰接表存儲較省空間。設有一稠密圖G，則G采用鄰接矩陣存儲較省空間。圖的逆鄰接表存儲結構只合用于有向圖。已知一個圖的鄰接矩陣表達，刪除所有從第i個頂點出發(fā)的方法是將鄰接矩陣的第i行所有置0。圖的深度優(yōu)先遍歷序列不是惟一的。n個頂點e條邊的圖采用鄰接矩陣存儲，深度優(yōu)先遍歷算法的時間復雜度為O(n2)；若采用鄰接表存儲時，該算法的時間復雜度為O(n+e)。n個頂點e條邊的圖采用鄰接矩陣存儲，廣度優(yōu)先遍歷算法的時間復雜度為O(n2)；若采用鄰接表存儲，該算法的時間復雜度為O(n+e)。圖的BFS生成樹的樹高比DFS生成樹的樹高小或相等。用普里姆(Prim)算法求具有n個頂點e條邊的圖的最小生成樹的時間復雜度為O(n2)；用克魯斯卡爾(Kruskal)算法的時間復雜度是O(elog2e)。若規(guī)定一個稀疏圖G的最小生成樹，最佳用克魯斯卡爾(Kruskal)算法來求解。若規(guī)定一個稠密圖G的最小生成樹，最佳用普里姆(Prim)算法來求解。用Dijkstra算法求某一頂點到其余各頂點間的最短途徑是按途徑長度遞增的順序來得到最短途徑的。拓撲排序算法是通過反復選擇具有0個前驅(qū)頂點的過程來完畢的。在各種查找方法中，平均查找長度與結點個數(shù)n無關的查找方法是散列查找。散列法存儲的基本思想是由關鍵字的值決定數(shù)據(jù)的存儲地址。大多數(shù)排序算法都有兩個基本的操作：。比較和移動由于查找算法的基本運算是關鍵字之間的比較操作，所以可用平均查找長度來衡量查找算法的性能。查找有靜態(tài)查找和動態(tài)查找，當查找不成功時動態(tài)查找會將查找關鍵字插入在表中。順序查找法中設立監(jiān)視哨，可以起到防止越界的作用。假設列表長度為n，那么查找第i個數(shù)據(jù)元素時需進行n-i+1次比較。假設查找每個數(shù)據(jù)元素的概率相等，即Pi=1/n，則順序查找算法的平均查找長度為：ASL=(n+1)/2。折半查找法又稱為二分法查找法，這種方法規(guī)定待查找的列表必須是按關鍵字大小有序排列的順序表。假定將長度為n的表提成b塊，且每塊含s個元素，則b=n/s。又假定表中每個元素的查找概率相等，在有序表(12,24,36,48,60,72,84)中二分查找關鍵字72時所需進行的關鍵字比較次數(shù)為2。折半查找有序表（4,6,12,20,28,38,50,70,88,100），若查找表中元素20，它將依次與表中元素28，6，12，20比較大小。在各種查找方法中，平均查找長度與結點個數(shù)n無關的查找方法是散列查找。散列法存儲的基本思想是由關鍵字的值決定數(shù)據(jù)的存儲地址。當關鍵字集合很大時，關鍵字值不同的元素也許會映象到哈希表的同一地址上，即k1≠k2，但H（k1）=H（k2），這種現(xiàn)象稱為沖突.產(chǎn)生沖突現(xiàn)象的兩個關鍵字稱為該散列函數(shù)的____同義詞________。在散列函數(shù)H(key)=keyMODp中，p應取素數(shù)。設哈希表長m=14,哈希函數(shù)H(key)=keyMOD11.表中已有4個結點；addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址為空。如用二次探測再散列解決沖突，關鍵字為49的結點的地址是。9希爾排序是屬于插入排序的改善方法。給出一組關鍵字T＝（20,4,34,5,16,33,18,29,2,40,7），規(guī)定從下到大進行排序，試給出快速排序（選一個記錄為樞紐）第一趟排序結果。7,4,2,85,16,18,20,,29,33,40,34大多數(shù)排序算法都有兩個基本的操作：比較和移動。在對一組記錄（54,38,96,23,15,72,60,45,83）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置至少需比較次。6。在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用插入；若初始數(shù)據(jù)基本反序，則選用選擇。在堆排序和快速排序中，若初始記錄接近正序或反序，則選用堆排序；若初始記錄基本無序，則最佳選用快速排序。對于n個記錄的集合進行冒泡排序，在最壞的情況下所需要的時間是O(n2)。若對其進行快速排序，在最壞的情況下所需要的時間是O(n2)對于n個記錄的集合進行歸并排序，所需要的平均時間是O(nlog2n)，所需要的附加空間是O(n)。7．對于n個記錄的表進行2路歸并排序，整個歸并排序需進行┌l(fā)og2n┐趟（遍）。8.設要將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關鍵碼按字母序的升序重新排列，則：冒泡排序一趟掃描的結果是HCQPAMSRDFXY；初始步長為4的希爾（shell）排序一趟的結果是PACSQHFXRDMY；二路歸并排序一趟掃描的結果是HQCYAPMSDRFX；快速排序一趟掃描的結果是FHCDPAMQRSYX；堆排序初始建堆的結果是ADCRFQMSYPHX。9.在堆排序、快速排序和歸并排序中，若只從存儲空間考慮，則應一方面選取方法，另一方面選取快速排序方法，最后選取歸并排序方法；若只從排序結果的穩(wěn)定性考慮，則應選取歸并排序方法；若只從平均情況下最快考慮，則應選取堆排序、快速排序和歸并排序方法；若只從最壞情況下最快并且要節(jié)省內(nèi)存考慮，則應選取堆排序方法。三、程序填空題以下程序的功能是實現(xiàn)帶附加頭結點的單鏈表數(shù)據(jù)結點逆序連接，請?zhí)羁胀晟浦oidreverse(pointerh)/*h為附加頭結點指針；*/{pointerp,q;p=h->next;h->next=NULL;while((1)________){q=p;p=p->next;q->next=h->next;h->next=(2)________;}}(1)p!=null∥鏈表未到尾就一直作(2)q∥將當前結點作為頭結點后的第一元素結點插入下面是用c語言編寫的對不帶頭結點的單鏈表進行就地逆置的算法，該算法用L返回逆置后的鏈表的頭指針，試在空缺處填入適當?shù)恼Z句。voidreverse（linklist&L）{p=null；q=L；while（q！=null）{(1);q->next=p；p=q；(2)___;}(3)_____;}(1)L=L->next;∥暫存后繼(2)q=L;∥待逆置結點(3)L=p;∥頭指針仍為L以下算法的功能是用頭插法建立單鏈表的算法，請?zhí)羁胀晟浦?/p>

Linklist

CreateFromHead()

{

LinkList

L;

Node

*s;

char

c;

L=(Linklist)malloc(sizeof(Node));

/*為頭結點分派存儲空間*/

L->next=NULL;

While((c=getchar())!=’*’)

{s=(Node*)malloc(sizeof(Node));/*為讀入的字符分派存儲空間*/s->data=c;s->next=L->next;L->next=s;}

returnL;}以下算法的功能是尾插法創(chuàng)建鏈表，請?zhí)羁胀晟浦?。typedefstructNode/*結點類型定義*/{chardata;structNode*next;}Node,*LinkList;/*LinkList為結構指針類型*/Linklist

CreateFromTail()/*將新增的字符追加到鏈表的末尾*/{

LinkListL;

Node*r,*s;

charc;

L=(Node*)malloc(sizeof(Node));

/*為頭結點分派存儲空間*/

L->next=NULL;

r=L;

/*r指針指向鏈表的當前表尾，以便于做尾插入，其初值指向頭結點*/

while(

(c=getchar())!=’$’)/*當輸入‘$’時，建表結束*/{

s=(Node*)malloc(sizeof(Node));s->data=c;；r->next=s;r=s;}；r->next=NULL/*將最后一個結點的next鏈域置為空，表達鏈表的結束*/returnL;}

/*CreateFromTail*/

下列算法在順序表L中依次存放著線性表中的元素，在表中查找與e相等的元素，若L.elem[i]=e,則找到該元素，并返回i+1，若找不到，則返回“-1”，請?zhí)羁胀晟浦?/p>

int

Locate(SeqListL，inte){

i=0;

/*i為掃描計數(shù)器，初值為0，即從第一個元素開始比較*/

while((i<=L.last)&&(L.elem[i]!=e))

i++;

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

if

(i<=L.last)

return(i+1);

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

else

return(-1);

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

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

void

InsList(SeqList*L,inti,inte){intk;if((i<1)||(i>L->last+2))printf(“插入位置i值不合法”)；

if(L->last>=maxsize-1)printf(“表已滿無法插入”)；for(k=L->last;k>=i-1;k--)

/*為插入元素而移動位置*/L->elem[k+1]=L->elem[k];L->elem[i-1]=e;

/*在C語言數(shù)組中，第i個元素的下標為i-1*/L->last++;

}下列算法是在順序表L中刪除第i個數(shù)據(jù)元素，并用指針參數(shù)e返回其值。i的合法取值為1≤i≤L.last+1，請?zhí)羁胀晟浦?/p>

int

DelList(SeqList*L,inti,int*e){

intk;if((i<1)||(i>L->last+1))

printf(“刪除位置不合法！”)；*e=L->elem[i-1];

/*將刪除的元素存放到e所指向的變量中*/for(k=i;i<=L->last;k++)L->elem[k-1]=L->elem[k];

/*將后面的元素依次前移*/L->last--;}四、解答題假設以數(shù)組seqn［m］存放循環(huán)隊列的元素，設變量rear和quelen分別指示循環(huán)隊列中隊尾元素的位置和元素的個數(shù)。(1)寫出隊滿的條件表達式；(2)寫出隊空的條件表達式；(3)設m=40,rear=13,quelen=19,求隊頭元素的位置；(4)寫出一般情況下隊頭元素位置的表達式。(1)quelen==m(2)quelen==0(3)(13-19+40)%40=34(4)(rear-quelen+m)%mABABECFHDG前序：A,B,D,G,C,E,F,H中序：D,G,B,A,E,C,H,F后序：G,D,B,E,H,F,C,A層次：A,B,C,D,E,F,G,H已知一棵二叉樹的前序序列為：A,B,D,G,J,E,H,C,F,I,K,L中序序列：D,J,G,B,E,H,A,C,K,I,L,F。寫出該二叉樹的后序序列；畫出該二叉樹；求該二叉樹的高度(假定空樹的高度為－1)和度為2、度為1、及度為0的結點個數(shù)。該二叉樹的后序序列為：J,G,D,H,E,B,K,L,I,F,C,A。該二叉樹的形式如圖所示：AABJKIFCGEDLH該二叉樹高度為：5。度為2的結點的個數(shù)為：3。度為1的結點的個數(shù)為：5。度為0的結點個數(shù)為：4。有一份電文中共使用6個字符:a,b,c,d,e,f,它們的出現(xiàn)頻率依次為2,3,4,7,8,9，試構造一棵哈夫曼樹，并求其加權途徑長度WPL，字符c的編碼。WPL＝80字符c：001（不唯一）下圖是帶權的有向圖G的鄰接表表達法。從結點V1出發(fā)，求出：深度遍歷圖G；G的一個拓撲序列；從結點V1到結點V8的最短途徑。題29圖題29圖26635011128433811212624V1V3V4V6V71V2V8V5參考答案：v1,v2,v3,v8,v4,v5,v7,v6(2分)v1,v2,v4,v6,v5,v3,v7,v8(2分)V1到結點V8的最短途徑為：v1,v2,v3,v8(2分)已知如圖所示的有向圖，請給出該圖的：（1）

每個頂點的入度、出度；（2）

鄰接矩陣；（3）

鄰接表；VV1V3V4V6V71V2V8V5對下面的有向圖，從頂點V1開始進行遍歷，試畫出遍歷得到的DFS生成森林和BFS生成森林。圖全對給4分，錯一個頂點扣1分，扣完為止。遍歷得到的DFS生成森林和BFS生成森林如下圖：VV1V3V4V6V7V2V8V5DFS生成森林VV1V3V4V6V7V2V8V5BFS生成森林采用哈希函數(shù)Ｈ(k)=3*kmod13并用線性探測開放地址法解決沖突，在數(shù)列地址空間［0..12］中對關鍵字序列22,41,53,46,30,13,1,67,51（1）構造哈希表（畫示意圖）；（2）裝填因子；等概率下（3）成功的和（4）不成功的平均查找長度1）散列地址0123456789101112關鍵字13225314167465130比較次數(shù)111212111（2）裝填因子=9/13=0.7（3）ASLsucc=11/9（4）ASLunsucc=29/13設有一組關鍵字{9,01,23,14,55,20,84,27}，采用哈希函數(shù)：H（key）=keymod7，表長為10，用開放地址法的二次探測再散列方法Hi=(H(key)+di)mod10(di=12,22,32,…,)解決沖突。規(guī)定：對該關鍵字序列構造哈希表，并計算查找成功的平均查找長度。散列地址0123456789關鍵字140192384275520比較次數(shù)11123412平均查找長度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8以關鍵字27為例：H（27）=27%7=6（沖突）H1=（6+1）%10=7（沖突）H2=（6+22）%10=0（沖突）H3=（6+33）%10=5所以比較了4次。對于給定的一組記錄的關鍵字{23,13,17,21,30,60,58,28,30,90},試分別寫出冒泡排序、快速排序、堆排序、歸并排序第一趟排序后的結果。冒泡排序13,23,17,21,,28,30,60,58,30*,90快速排序：(21,13,17,)13,(30,60,58,28,30*,90)堆排序：13,21,17,23,30,60,58,28,30*,90,歸并排序按層遍歷：(1323)(1721)(3060)(2858)(30*90)采用哈希函數(shù)Ｈ(k)=2*kmod13并用鏈地址法解決沖突，在數(shù)列地址空間［0..12］中對關鍵字序列22,41,53,46,30,13,1,67,51進行下列工作：（a）構造哈希表（畫示意圖）；（b）等概率下成功的和不成功的平均查找長度。參考答案：鏈地址表全對給8分。錯一個結點扣1分，扣完為止。0→13^1→46^2→53→1^3^4→41→67^5→22^6^7^8→30^9^10^11→51^12^ASLsucc=(7+4)/13=11/9（1分）ASLunsucc=(5+4)/13=9/13（1分）四、算法設計題(10分)閱讀下列遞歸算法，寫出非遞歸方法實現(xiàn)相同功能的C程序。voidtest(int&sum){intx；scanf(x)；if(x=0)sum=0else{test(sum);sum+=x;}printf(sum)；}＃include<stdio.h>(1分)voidmain()(1分){intx,sum=0,top=0,s[];(1分)scanf(“%d”,&x)while(x<>0){s[++top]:=a;scanf(“%d”,&x);}(3分)while(top)sum+=s[top--];(3分)printf(“%d”,sum);(1分)}試寫出把圖的鄰接矩陣表達轉(zhuǎn)換為鄰接表表達的算法。設圖的鄰接矩陣為g[n][n]（針對無向圖），定義鄰接表節(jié)點的類型為structedgenode{intadjvex;edgenodenext;}typedefedgenode*adjlist[n];voidmatritolist(intg[][],adjlistgl,intn){edgenode*p,*q;for(inti=0i<n;i++)gl[i]=null;for(inti=0;i<n;i++)for(intj=0;j<n;j++){if(g[i][j]!=0)p=(edgenode*)malloc(sizeof(edgenode));p->adjvex=j;p->next=null;if(gl[i]=null){gl[i]==p;q=p;}else(q->next=p;q=p;}}}閱讀算法并根據(jù)輸入數(shù)據(jù)畫出鏈表。linklistcreatelistr1(){charch;linklisthead=(listnode*)malloc(sizeof(listnode));listnode*p，*r；r=head;while((ch=getchar())!=‵\n′){p=(listnode*)malloc(sizeof(listnode));while(p)p=(listnode*)malloc(sizeof(listnode));p–>data=ch;r–>next=p;r=p;}r–>next=NULL;return(head);}輸入數(shù)據(jù)為：textttrxt^head閱讀算法并指出下列各段程序完畢的功能。voidadd_poly(Lnode*pa,Lnode*pb){Lnode*p,*q,*u,*pre;intx;p=pa->next;q=pb->next;pre=pa;while((p!=NULL)&&((q!=NULL)){if(p->exp<q->exp){