數(shù)據(jù)結構題庫

考證素材考證素材數(shù)據(jù)結構(課程代碼02331)一、單項選擇題(本大題共15小題，每題2分，共30分)在每題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內(nèi)。錯選、多項選擇或未選均無分。1、對順序存儲的線性表，設其長度為n在任何位置上插入或刪除操作都是等概率的。插入一個元素時平均要移動表中的〔A〕個元素。A、n/2B、(n+1)/2C、(n-1)/2D、n2、一個向量(一種順序表)第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素TOC\o"1-5"\h\z的地址是B___。A、100B、108C、110D、1203、一個棧的入棧序列a,b,c,d,e,則棧的不可能的輸出序列是_C。A、edcbaB、decbaC、dceabD、abcde4、假設已知一個棧的入棧序列是1,2,3,…，n,其輸出序列為p1,p2,p3,…，pn,假設p1=n，則pi為_C。A、iB、n-iC、n-i+1D、n-i-15、判定一個循環(huán)隊列QU〔最多元素為m〕為空的條件是___C_oA、rear-front==mB、rear-front-1==mC、front==rearD、front==rear+16、判定一個循環(huán)隊列QU〔最多元素為m,m==MaxsizeT〕為滿隊列的條件是__A__。A、((rear-front)+Maxsize)%Maxsize==mB、rear-front-1==mC、front==rearD、front==rear+17、循環(huán)隊列用數(shù)組A0,m-1］存放其元素值，已知其頭尾指針分別是front和rear,則當前隊列中的元素個數(shù)是—丄。A、(rear-front+m)%mB、rear-front+1C、rear-front-1D、rear-front8、設串的長度為n,則它的子串個數(shù)為oA、nB、n(n+1)C、n(n+1)/2D、n(n+1)/2+19、S1=“ABCD〃，S2=“CD〃則S2在S3中的位置是〔C〕A、1B、2C、3D、410、設數(shù)組a7］6］的基地址為1024,每個元素占2個存儲單元,假設以行序為主序順序存儲，則元素a2］4］的存儲地址是_B_。A、1054B、1056C、1058D、109811、二維數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標i從0到7,列下標j從0到9,從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按列存放時，元素A4］7］的起始地址為—亠_。A、SA+141B、SA+180C、SA+222D、SA+22512、二維數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從0到7,列下標j從0到9,從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的字節(jié)數(shù)是__C__oA、80B、100C、240D、27013、二維數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標i從0到7,列下標j從0到9,從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，數(shù)組元素A7]4]的起始地址為丄__。A、SA+141B、SA+144C、SA+222D、SA+22514、假定在一棵二叉樹中，雙分支結點數(shù)為15個，單分支結點數(shù)為30個，則葉子結點個數(shù)為TOC\o"1-5"\h\zB。A、15B、16C、17D、4715、按照二叉樹的定義，具有3個結點的不同形狀的二叉樹有亠種。A、3B、4C、5D、616、深度為5的二叉樹至多有丄—個結點。A、16B、32C、31D、1017、設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數(shù)至少為__A__oA、2hB、2h-1C、2h+1D、h+118、對一個滿二叉樹，m個樹葉，n個結點，深度為h，則』__。A、n=h+mB、h+m=2nC、m=h-1D、n=2h-119、如果某二叉樹的前根次序遍歷結果為stuwv，中序遍歷為uwtvs，那么該二叉樹的后序為CoA、uwvtsB、vwutsC、wuvtsD、wutsv20、某二叉樹的前序遍歷結點訪問順序是abdgcefh，中序遍歷的結點訪問順序是dgbaechf，則其后序遍歷的結點訪問順序是__D__oA、bdgcefhaB、gdbecfhaC、bdgaechfD、gdbehfca21、已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是__D__oA、acbedB、decabC、deabcD、cedba22、由帶權為9,2,5,7的四個葉子結點構造一棵哈夫曼樹，該樹的帶權路徑長度為(D)oTOC\o"1-5"\h\zA、23B、37C、46D、4423?在一棵具有n個結點的二叉樹第i層上，最多具有(C)個結點。A、2iB、2i+1C、2i-1D、2n24、在一個圖中，全部頂點的度數(shù)之和等于全部邊數(shù)的倍數(shù)為亠C__。A、1/2B、1C、2D、425、在一個有向圖中，全部頂點的入度之和等于全部頂點的出度之和的__^倍。A、1/2B、1C、2D、426、一個有n個頂點的無向圖的邊數(shù)最多為亠C__。A、nB、n(n-1)C、n(n-1)/2D、2n27、具有4個頂點的無向完全圖有__A_—條邊。A、6B、12C、16D、2028、具有6個頂點的無向圖至少應有_A__條邊才能確保是一個連通圖。A、5B、6C、7D、829、在一個具有n個頂點的無向圖中，要連通全部頂點至少需要_=C=_條邊。A、nB、n+1C、n-1D、n/230、對于一個具有n個頂點的無向圖，假設采納鄰接矩陣表示，則該矩陣的大小是—_D__。A、nB、(n-1)2C、n-1D、n231、對于一個具有n個頂點和e條邊的無向圖，假設采納鄰接表表示，則表頭向量的大小為—丄。A、nB、n+1C、n-1D、n+e32、判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以利用_D___。A、求關鍵路徑的方法B、求最短路徑的Dijkstra方法C、寬度優(yōu)先遍歷算法D、深度優(yōu)先遍歷算法33、關鍵路徑是事件結點網(wǎng)絡中一匸。A、從源點到匯點的最長路徑B、從源點到匯點的最短路徑C、最長的回路D、最短的回路34、一個有n個頂點的無向連通圖，它所包含的連通重量個數(shù)為_^。A、0B、1C、nD、n+135?對于一個有向圖，假設一個頂點的入度為k1,、出度為k2，則對應鄰接表中該頂點單鏈表中的結點數(shù)為B。A、k1B、k2C、k1-k2D、k1+k236、對于一個有向圖，假設一個頂點的入度為k1,、出度為k2，則對應逆鄰接表中該頂點單鏈表中的結點數(shù)為—A一。A、k1B、k2C、k1-k2D、k1+k237、具有n個頂點的有向圖最多有(B)條邊。A、nB、n(n-1)C、n(n+1)2D、n38、n個頂點的強連通圖至少有(A)條邊。A、nB、n-1C、n+1D、n(n-1)39、在一個具有n個頂點的有向圖中，假設全部頂點的出度之和為s,則全部頂點的入度之和為(A)。A、sB、s-1C、s+1D、n40、在一個無向圖中，假設兩個頂點之間的路徑長度為k,則該路徑上的頂點數(shù)為(B)。A、kB、k+1C、k+2D、2k41、一個圖中包含k個連通重量，假設按深度優(yōu)先(DFS)搜索方法訪問全部結點，則必須調(diào)用(A)次深度優(yōu)先遍歷算法。A、kB、1C、k-1D、k+142、設G1=(V1,E1)和G2=(V2,E2)為兩個圖，V1cV2,E1cE2，則稱〔A〕A、G1是G2的子圖B、G2是G1的子圖C、G1是G2的連通重量D、G2是G1的連通重量43、采納順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為_C__.A、nB、n/2C、(n+1)/2D、(n-1)/244、采納二分查找方法查找長度為n的線性表時，每個元素的平均查找長度為亠D__。A、O〔n2〕B、O(nlogn)C、O(n)D、O(logn)45、有一個有序表為｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，當二分查找值82為的結點時，—_C_—次比擬后查找成功。A、1B、2C、4D、846、有一個長度為12的有序表，按二分查找法對該表進行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比擬次數(shù)為__B__oA、35/12B、37/12C、39/12D、43/1247、對于18個元素的有序表采納二分(折半)查找，則查找A3］的比擬序列的下標為(D)oA、1、2、3B、9、5、2、3C、9、5、3D、9、4、2、348、一組記錄的排序碼為〔46,79,56,38,40，84〕，則利用堆排序的方法建立的初始堆為__B__。A、79，46，56，38，40，80B、38，40,56，79，46，84，C、84，79，56，46，40，38D、84，56，79，40，46，3849、一組記錄的關鍵碼為〔4679，56，38，40，84〕，則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為COA、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，7950、一組記錄的排序碼為〔瓦48，16,35,79,82,23,40,36,72〕，其中含有5個長度為2的有序表，按歸并排序的方法對該序列進行一趟歸并后的結果為_A_oA、16，25，35，48，23，40，79，82，36，72B、16，25，35，48，79，82，23，36，40，72C、16，25，48，35，79，82，23，36，40，72D、16，25，35，48，79，23，36，40，72，8251、下述幾種排序方法中，要求內(nèi)存量最大的是丄__。A、插入排序B、選擇排序C、快速排序D、歸并排序52、在對n個元素進行簡單項選擇擇排序過程中，第i趟需從(A)個元素中選擇出最小值元素。A、n-i+1B、n-iC、iD、i+153、n個記錄直接插入排序所需的記錄最小比擬次數(shù)是(A)A、n-1B、2(n-1)C、(n+2)(n-1)/2D、n54、一組記錄的關鍵字為〔45,80,55,40,42,85〕，則利用堆排序的方法建立的初始堆為(B)。A、〔80,45,55,40,42,85,B、〔85,80,55,40,42,45,C、〔85,80,55,45,42,40,D、〔85,55,80,42,45,40,55、一組記錄的關鍵字為〔45,，80,55,4(0,42,，85,,貝利用快速排序的方法，以第一個記錄為基準得到一次劃分結果是(C)qA、〔40,42,45,55,80,85,B、〔42,40,45,80,55,85,C、〔42,40,45,55,80,85,D、〔42,40,45,85,55,80,56?將一棵有100個結點的完全二叉樹從根這一層開始，每一層上從左到右依次對結點進行編號，根結點的編號為1,則編號為49的結點的左孩子編號為〔A〕。TOC\o"1-5"\h\zA,98B,99C,50D,48—組記錄的排序碼為(48,24,18,53,16,26,40),采納冒泡排序法進行排序，則第一趟排序需要進行記錄交換的次數(shù)是〔C〕。A,3B,4C,5D,6采納分塊查找時，如某線性表有256個元素，查找每個元素的概率相同，假設采納順序查找來確定元素所在的塊，則每塊包含〔C,個結點時，平均查找長度最小。A,256B,15(:,16D,18-01疔A=10101059.對于有向圖的鄰接矩陣,該圖共有〔B，條弧。A,5B,4C,3D,2TOC\o"1-5"\h\z60.由帶權9、1、3、5、6的五個葉子結點生成的哈夫曼樹的帶權路徑長度為〔C〕。A,50B,60C,52D,65二、填空題(本大題共10小題，每題2分，共20分)請在每題的空格中填上正確答案。錯填、不填均無分。1、下面程序段的時間復雜度是O(mXn)。for(i=0;i〈n;i++)for(j=0;j〈m;j++)ai]j]=0;2、下面程序段的時間復雜度是____O(Qn)一。i=s=0while(s〈n){i++;/Xi=i+1X/s+=i;/Xs=s+iX/}3、下面程序段的時間復雜度是___O(n2>qs=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=bi]j];sum=s;4、下面稈序段的時間復雜度是一_Odogp)_一。Oi=1;while(i<=n)i=iX3;5、在順序表中，假設第一個元素所在的地址為Loc(a1),每個元素在內(nèi)存中占有L個存儲單元,TOC\o"1-5"\h\z貝U元素ai在內(nèi)存中的地址Loc(ai)=__Loc(a1)+(iT)XL。6、向一個長度為n的順序表的第i個元素〔1WiWn+1〕之前插入一個元素時，需向后移動亠n-i+l_個元素。7、向一個長度為n的順序表中刪除第i個元素〔IWiWn〕時，需向前移動—n-i—個元素。8、串s='abcdef',s1='cde',si在s中的位置為3。9、已知二維數(shù)組Am]n]采納行序為主方法存儲，每個元素占k個存儲單元，并且第一個元素的存儲地址是LOC(AO]O])，則Ai]j]的地址是LOC(A0]0])+(nXi+j)Xk。10、二維數(shù)組A10]20]采納列序為主方法存儲，每個元素占一個存儲單元并且A0]0]的存儲地址是200，則A6]12]的地址是__326_。11、二維數(shù)組A10…20]5…10]采納行序為主方法存儲，每個元素占4個存儲單元，并且A10]5]的存儲地址是1000，則A18]9]的地址是_」208一。12、現(xiàn)有一個n階的對稱矩陣an]n]，現(xiàn)將其壓縮存儲在一個一維數(shù)組sm]中，則m=,n(n+l)/2，假設以行序為主序進行存儲，則元素ai]j](i〉=j)在s中的下標k=i(i-1)/2+j-1__。13、在一個mXn的矩陣中，假設a0]0]是第一個元素，則ai]j]是第—iXn+j—__個元素。14、在二叉樹中，某一結點x的編號為i,x假設有雙親，其雙親編號應為__卩/2」亠；x假設有左孩子，其左孩子編號應為___2Xi___；x假設有右孩子，其右孩子應為__2Xi+l。15、8層完全二叉樹至少有—128一個結點，擁有100個結點的完全二叉樹的最大層數(shù)為7_。16、n個頂點的連誦圖至少—nT__條邊。17、在無向圖G的鄰接矩陣A中，假設Ai]j]等于1,則Aj]i]等于=1—_。n18、一個無向圖有n個頂點和e條邊，則全部頂點的度的和即乞di(表示頂點i的度)=i=12e。19、在有n個頂點的有向圖中，每個頂點的度最大可達—2(nT)一。20、對于長度為n的線性表，假設進行順序查找，則時間復雜度為___O〔〕__；假設采納折半法查找，則時間復雜度為__O(log2i)__。21、已知有序表為〔12，18，24，35，47，50，62，83，90，115，134〕，當用折半查找90時，需進行一2—次查找可確定成功；查找47時，需進行—次查找成功；查找100時，需進行3次查找才能確定不成功。22、平衡二叉排序樹上任一結點的平衡因子只可能是0、丄或-1。23、用起泡法對n個關鍵碼排序，在最好情況下，只需做——n-1次比擬；在最壞的情況下要做n(n-1)/2次比擬。24、設字符串S1=“ABCDEF"，S2=“PQRS"，則運算S=C0NCAT〔SUB〔S1，2，LEN〔S2〕，SUB〔S1，LEN〔S2〕，2,后的串值為“BCDEDE"_。25、在一棵二叉排序樹上按___—中序___遍歷得到的結點序列是一個有序序列。26、在一個圖中，全部頂點的度數(shù)之和等于全部邊數(shù)的___2一—倍。27、在一個具有n個頂點的無向完全圖中，包含有__n(n-l)/2______條邊，在一個具有n個頂點的有向完全圖中，包含有—n(nT)____條邊。28、假定一個有向圖的頂點集為｛a,b,c,d,e,f｝，邊集為｛〈a,c〉，〈a,e〉，〈c,f〉，〈d,c〉，〈e,b〉,〈e,d〉｝，則出度為0的頂點個數(shù)為___2_，入度為1的頂點個數(shù)為_4_=__。29、在一個具有n個頂點的無向圖中，要連通全部頂點則至少需要nT條邊。30、假設一個圖的頂點集為｛a,b,c,d,e,f｝，邊集為｛(a,b),(a,c),(b,c),(d,e)｝，則該圖含有_個連通重量。31、對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數(shù)和邊數(shù)分別為_亠____和nT__。32、假定一個順序表的長度為40，并假定查找每個元素的概率都相同，則在查找成功情況下的平均杳找長度._20.5，在杳找不成功情況下的平均杳找長度一_41.一。33、在索引查找中，假定查找表〔即主表，的長度為96，被等分為8個子表，則進行索引查找的平均查找長度為11__。34、假定對長度n=50的有序表進行折半查找，則對應的判定樹高度為__6__，最后一層的結TOC\o"1-5"\h\z點數(shù)為19一。35、假定在索引查找中，查找表長度為n,每個子表的長度相等，設為s,則進行成功查找的平均查找長度為(n/s+s)/2+1_。46、假定一組記錄為(46,79,56,38,40,84)，則利用堆排序方法建立的初始小根堆為(38,40,56,79,46,84)。37、假定一組記錄為(46,79,56,38,40,84)，在冒泡排序的過程中進行第一趟排序后的結果為(46,56,38,40,79,84)一。38、假定一組記錄為(46,79,56,64,38,40,84,43)，在冒泡排序的過程中進行第一趟排序時，元素79將最終下沉到其后第______個元素的位置。39、假定一組記錄為(46,79,56,38,40,80),對其進行快速排序的第一次劃分后的結果為___403846567980]。40、假定一組記錄為(46,79,56,38,40,80,46,75,28,46)，對其進行歸并排序的過程中，第二趟歸并后的子表個數(shù)為3“三、應用題(本大題共4小題,每題7分,共28分)1、分別畫出具有3個結點的樹和三個結點的二叉樹的全部不同形態(tài)。解：具有3個結點的樹有兩種不同形態(tài)。具有3個結點的二叉樹有以下五種不同形態(tài)。2、如下列圖所示的二叉樹,試分別寫出它的順序表示和鏈接表示〔二叉鏈表〕。解：〔1〕順序表示?！?〕該二叉樹的二叉鏈表表示。3、假定用于通信的電文由8個字符A、B、C、D、E、F、G、H組成，各字母在電文中出現(xiàn)的概率為5％、25％、4％、7％、9％、12％、30％、8％,試以這8個字母構造哈夫曼樹。解：依據(jù)題意，設這8個字母對應的權值分別為〔5，25，4，7，9，12，30，8〕，并且n=8。步驟如下：4、假設一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請寫出該二叉樹的后序遍歷序列。解：后序序列：ACDBGJKIHFE5、已知一個無向圖的鄰接表下列圖所示，要求：〔1〕畫出該無向圖；⑵依據(jù)鄰接表，分別寫出用DFS(深度優(yōu)先搜索)和BFS〔廣度優(yōu)先搜索〕算法從頂點V0開始遍歷該圖后所得到的遍歷序列。解：〔1〕該無向圖如下列圖所示?！?〕依據(jù)該無向圖的鄰接表表示，從頂點V0開始的深度優(yōu)先遍歷序列為：VO、V2、V3、VI、V4、V6、V5。廣度優(yōu)先遍歷序列為VO、V2、V5、V6、VI、V3、V4。6、如下列圖所示的一個網(wǎng)，按照Prim方法，從頂點VI出發(fā)，求該網(wǎng)的最小生成樹的產(chǎn)生過程。解：步驟如下：7、記錄的關鍵字序列為：63，90，70，55，67，42，98，83，10，45，58，則畫出構造一棵二叉排序樹的過程。解：構造二叉排序樹的過程如下列圖所示。8、已知一組記錄為(46,74,53,14,26,38,86,65,27,34)，給出采納冒泡排序法進行排序時每一趟的排序結果。解：排序過程如下：(0)46745314263886652734](1)46531426387465273486(2)46142638536527347486(3)14263846532734657486(4)14263846273453657486(5)14263827344653657486(6)14262734384653657486(7)142627343846536574869、已知一組記錄為(46,74,53,14,26,38,86,65,27,34)，給出采納直接插入排序法進行排序時每一趟的排序結果。解：排序過程如下所示：(0)46745314263886652734(1)46745314263886652734(2)46537414263886652734(3)14465374263886652734(4)14264653743886652734(5)14263846537486652734(6)14263846537486652734(7)14263846536574862734(8)14262738465365748634(9)14262734384653657486]10、關鍵字序列為〔47,7,29,11,16,92,22,8,3,50,37,89,94,21〕，哈希函數(shù)為：Hash(key)=keymod11,用拉鏈表處理沖突。解：建表如下：11、已知如下列圖所示的有向圖,請給出該圖的(1)每個頂點的出/入度；(2)鄰接矩陣；(3)鄰接表；解：(1)每個頂點的出/入度是：(2)鄰接矩陣：(3)鄰接表：12、已知圖的鄰接矩陣如下列圖所示。試分別畫出自頂點A出發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。解：〔1〕深度優(yōu)先搜索如下所示：(2)廣度優(yōu)先搜索如下所示：13、已知一組記錄為(46,74,53,14,26,38,86,65,27,34),給出采納歸并排序法進行排序時每一趟的排序結果。解：排序過程如下所示：(0)46745314263886652734](1)46741453263865862734](2)14465374263865862734](3)14263846536574862734](4)14262734384653657486]14、假定一個待哈希存儲的線性表為(32,75,29,63,48,94,25,36,18,70,49,80),哈希地址空間為HT12],假設采納除留余數(shù)法構造哈希函數(shù)和拉鏈法處理沖突，試畫出最后得到的哈希表，并求出平均查找長度。解：H(K)=K%11,哈希表如下列圖所示,平均查找長度17/12。15、對于一個無向圖如下所示,假定采納鄰接矩陣表示,試分別寫出從頂點0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷得到的頂點序列。解：〔1〕深度優(yōu)先搜索序列：0,1,2,8,3,4,5,6,7,9〔2〕廣度優(yōu)先搜索序列：0,1,4,2,7,3,8,6,5,916、已知如下列圖所示的一個網(wǎng),按照Kruskal方法,求該網(wǎng)的最小生成樹的產(chǎn)生過程。解：過程如下列圖所示。四、算法設計題(本大題共2小題,每題11分,共22分)1、編寫一個單鏈表類的成員函數(shù)，完成刪除不帶頭結點的單鏈表中數(shù)據(jù)域值等于X的第一個結點的操作。假設刪除成功，則返回被刪除結點的位置；否則，返回-1。算法設計如下：publicintremove(Objectx){Nodep=head;//初始化,p指向首結點Nodeq=null;//q用來記錄p的前驅(qū)結點intj=0;//j為計數(shù)器//從單鏈表中的首結點元素開始查找，直到p.getData()指向元素x或到達單鏈表的表尾while(p!=null&!p.getData().equals(x)){q=p;p=p.getNext();//指向下一個元素++j;//計數(shù)器的值增1}if(p!=null&&q==null)//刪除的是單鏈表中的首結點head=p.getNext();elseif(p!=null){//刪除的是單鏈表中的非首結點q.setNext(p.getNext());}elsereturnT;//值為x的結點在單鏈表中不存在returnj;}2、編寫一個單鏈表類的成員函數(shù)，完成刪除帶頭結點的單鏈表中數(shù)據(jù)域值等于x的全部結點的操作。要求函數(shù)返回被刪除結點的個數(shù)。算法設計如下：publicintremoveAll(Objectx){Nodep=head.getNext();//初始化,p指向首結點，j為計數(shù)器Nodeq=head;//用來記錄p的前驅(qū)結點intj=0;//用來記錄被刪除結點的個數(shù)while(p!=null){//從單鏈表中的首結點開始對整個鏈表遍歷一次if(p.getData().equals(x)){q.setNext(p.getNext());++j;//計數(shù)器的值增1}elseq=p;p=p.getNext();//指向下一個元素}returnj;//返回被刪除結點的個數(shù)}3、試設計算法，用插入排序方法對單鏈表進行排序。算法設計如下：publicstaticvoidinsertSort(LinkListL){Nodep,q,r,u;p=L.getHead().getNext();L.getHead().setNext(null);//置空表，然后將原鏈表結點逐個插入到有序表中while(p!=null){//當鏈表尚未到尾，p為工作指針r=L.getHead();q=L.getHead().getNext();while(q!=null&(Integer.parseInt((String)q.getData()))<=(Integer.parseInt((String)p.getData()))){//查P結點在鏈表中的插入位置，這時q是工作指針r=q;q=q.getNext();}u=p.getNext();p.setNext(r.getNext());r.setNext(p);p=u;//將P結點鏈入鏈表中，r是q的前驅(qū)，u是下一個待插入結點的指針}}4、試設計算法，用選擇排序方法對單鏈表進行排序。算法設計如下：//單鏈表選擇排序算法publicstaticvoidselectSort(LinkListL){//p為當前最小,r為此過程中最小,q為當前掃描接點Nodep,r,q;NodenewNode=newNode();newNode.setNext(L.getHead());L.setHead(newNode);//制造一個最前面的節(jié)點newNode，解決第一個節(jié)點的沒有前續(xù)節(jié)點需要單獨語句的問題。p=L.getHead();while(p.getNext().getNext()!=null){r=p.getNext();q=p.getNext().getNext();while(q.getNext()!=null){if(Integer.parseInt((String)q.getNext().getData())<=(Integer.parseInt((String)r.getNext().getData()))){r=q;}q=q.getNext();}if(r!=p){//交換p與rNodeswap=r.getNext();r.setNext(r.getNext().getNext());//r的next指向其后繼的后繼swap.setNext(p.getNext());p.setNext(swap);//p的后繼為swap}p=p.getNext();}//whilep.setNext(null);}5、試設計算法，使用非遞歸方法完成快速排序。算法設計如下：publicstaticvoidNonrecursiveQuickSort(intary){if(ary.length<2){return;}//數(shù)組棧：記錄著高位和低位的值int]stack=newint2]ary.length];//棧頂部位置inttop=0;//低位，高位，循環(huán)變量，基準點//將數(shù)組的高位和低位位置入棧stack1]top=ary.length-1;stack0]top=0;top++;//要是棧頂不空，那么繼續(xù)while(top!=0){//將高位和低位出棧//低位：排序開始的位置top--;intlow=stack0]top];//高位：排序結束的位置inthigh=stack1]top];//將高位作為基準位置//基準位置intpivot=high;inti=low;for(intj=low;j<high;j++){if(aryj<=arypivot]){inttemp=aryj];aryj=aryi];aryi=temp;i++;}}//如果i不是基準位，那么基準位選的就不是最大值//而i的前面放的都是比基準位小的值，那么基準位//的值應該放到i所在的位置上if(i!=pivot){inttemp=aryi];aryi=arypivot];arypivot=temp;}if(i-low>1){//此時不排i的原因是i位置上的元素已經(jīng)確定了，i前面的都是比i小的，i后面的都是比i大的stack1]top=i-1;stack0]top=low;top++;}//當high-i小于等于1的時候，就不往棧中放了，這就是外層while循環(huán)能結束的原因//如果從i到高位之間的元素個數(shù)多于一個，那么需要再次排序if(high-i>1){//此時不排i的原因是i位置上的元素已經(jīng)確定了，i前面的都是比i小的，i后面的都是比i大的stack1]top=high;stack0]top=i+1;top++;}}}6、試設計算法，推斷完全二叉樹是否為大頂堆。算法設計如下：booleancheckmax(BiTreeNodet)//推斷完全二叉樹是否為大頂堆{BiTreeNodep=t;if(p.getLchild()==null&p.getRchild()==null){returntrue;}else{if(p.getLchild()!=null&p.getRchild()!=null){if((((RecordNode)p.getLchild().getData()).getKey())pareTo(((RecordNode)p.getData()).getKey())<=0&(((RecordNode)p