軍隊文職人員（收發(fā)員兼通信員）考試題庫大全-數(shù)據(jù)結(jié)構(gòu)與算法（重點題）

PAGEPAGE1軍隊文職人員（收發(fā)員兼通信員）考試題庫大全-數(shù)據(jù)結(jié)構(gòu)與算法一、單選題1.由權(quán)值分別為11，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為()。A、53B、73C、48D、24答案：B解析：根據(jù)赫夫曼樹的構(gòu)造方法可構(gòu)造出赫夫曼樹，經(jīng)計算可得帶權(quán)路徑長度為73。2.順序查找法適合于()結(jié)構(gòu)的線性表。A、哈希存儲B、順序存儲或鏈式存儲C、壓縮存儲D、索引存儲答案：B解析：順序查找法適合于線性表(不論線性表采用順序存儲還是鏈式存儲)。而哈希存儲查找是根據(jù)哈希函數(shù)值直接查找。壓縮存儲是通過對應關系進行查找。索引存儲是通過索引表進行查找。3.下列排序算法中，()排序在某趟結(jié)束后不一定選出一個元素放到其最終的位置上。A、選擇B、冒泡C、歸并D、堆答案：C解析：根據(jù)歸并排序的思想，在歸并排序工程中，某趟排序結(jié)束后，某個元素只在它的子序列中找到了最終的位置。4.在一個具有n個單元的順序棧中，假定以地址低端(即下標為0的單元)作為棧底，以top作為棧頂指針，當出棧時，top的變化為()。A、top=top-1；B、top=top+1；C、不變D、top=0；答案：A解析：以top作為棧頂指針，當出棧時，top的變化為top=top-1。5.設一個有序的單鏈表中有n個節(jié)點，現(xiàn)要求插入一個新節(jié)點后使得單鏈表仍然保持有序，則該操作的時間復雜度為()。A、AB、BC、CD、D答案：C解析：對單鏈表進行插入節(jié)點的操作，就是對單鏈表進行查找，找到節(jié)點需要插入的位置，然后修改指針，將節(jié)點插入單鏈表。6.雙向鏈表中有兩個指針域llink和rlink，分別指向前驅(qū)和后繼，設β指向表中的一個結(jié)點，q指向一待插入結(jié)點，現(xiàn)要求在p前插入q，則正確的插人為()。A、AB、BC、CD、D答案：D解析：p→llink→rlink=q；q→rlink=p；q→llink=p→llink；p→llink=q7.一個隊列的入隊順序是a，b，c，d，則出隊順序是()。A.a，b，C，dB.b，C，d，aA、d，B、b，aC、D、d，a，b答案：A解析：隊列的特點是先進先出，因此出隊的序列于入隊的序列完全相同，這點與棧不同。8.A、AB、BC、CD、D答案：C解析：9.A、45B、46C、55D、56答案：D解析：本題目甲對角線以下均為-3，個與共他元素里復，可知這45個元素只需用一個但米表示，故該矩陣只需用(100-45)+1=56個元素來表示。10.堆排序分為兩個階段，其中第一階段將給定的序列建成一個堆，第二階段逐次輸出堆頂元素。設給定序列{48，62，35，77，55，14，35，98}，若在堆排序的第一階段將該序列建成一個堆(大根堆)，那么交換元素的次數(shù)為()。A、5B、6C、7D、8答案：B解析：11.用二分(對半)查找表的元素的速度比用順序法的速度要()。A、必然快B、必然慢C、相等D、不能確定答案：D解析：兩者的查找速度要看元素是否有序以及所找元素所在的位置。比如：如果要查找的元素是表的第一個元素，則順序查找速度要快。如果要查找的元素剛好位于順序表的中間位置，則二分查找更快。12.設二維數(shù)組A[6][0]，每個數(shù)組元素占用4個存儲單元，若按行優(yōu)先順序存放的數(shù)組元素，a[0][0]的存儲地址為860，則a[3][5]的存儲地址為()。A、1000B、860C、1140D、1200答案：A解析：每個數(shù)組元素占用4個存儲單元，按行優(yōu)先順序存放的數(shù)組元素，則a[3][5]的存儲地址為860+(3×10+5)×4=1000。13.高度為5(除葉子層之外)的三階B-樹至少有()個結(jié)點。A、30B、31C、32D、33答案：B解析：14.深度為k的完全二叉樹中最少有()個結(jié)點。A、k-1B、2C、k+1D、2-1答案：B解析：最少有兩個結(jié)點，一個為根結(jié)點，另一個為根結(jié)點的左子樹。15.下面關于線性表的敘述中，錯誤的是()。A、線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B、線性表采用順序存儲，便于進行插入和刪除操作C、線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元D、線性表采用鏈接存儲，便于插入和刪除操作答案：B解析：線性表的順序存儲稱為順序表。順序表就是把線性表中的所有元素按照其邏輯順序。依次存儲到從計算機存儲器中指定存儲位置開始的一塊連續(xù)的存儲空間中，不便于插入和刪除；線性表的鏈式存儲稱為鏈表。在鏈式存儲中，存儲結(jié)點之間通過指針鏈接到下一個結(jié)點，不必占用一片連續(xù)的存儲單元，而且便于插入和刪除操作。16.若一組記錄的關鍵碼為(46，79，56，38，40，84)，則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為()。A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，79答案：C解析：由于選擇第一個記錄為基準，第一次排序即對整個序列進行一趟快速排序。使得位于基準左側(cè)的關鍵碼均小于基準，位于基準右側(cè)的關鍵碼均大于基準。17.n個結(jié)點的線索二叉樹上含有的線索數(shù)為()。A、nB、2nC、n-1D、n+1答案：D解析：對于有n個結(jié)點的二叉樹，采用二叉鏈存儲結(jié)構(gòu)時，每個結(jié)點有兩個指針域，總共有2n個指針域，由于只有n-1個結(jié)點被有效指針所指向.則共有2n-(n-1)=n+1個空鏈域。用這些空鏈域存放指向結(jié)點的前驅(qū)和后繼結(jié)點的指針，這些指針稱作線索。18.設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主進行存儲，a1，1為第一元素，其存儲地址為1，每個元素占一個地址空間，則a8·5的地址是()。A、13B、33C、18D、40答案：B解析：數(shù)組下標從1開始，只存儲其下三角形元素，在A，5的前面有7行，第1行有1個元素，第2行有2個元素，…，第7行有7個元素，這7行共有(1+7)×7/2=28個元素，在第8行中，a8·5的前面有4個元素，所以a8·5前有28+4=32個元素，其地址為33。19.字符串的長度是指()。A、串中不同字母的個數(shù)B、串中字符不同的個數(shù)C、串中不同數(shù)字的個數(shù)D、串中所含字符的個數(shù)答案：D解析：字符串的長度是指串中所含的字符的個數(shù)。20.有種關系模式R=＜U，F(xiàn)＞，U={C，T，H，X，S}，F(xiàn)={C→T，(H，X)→C，(H，T)→YC，(H，S)→Y}則表示模式R的碼是()。A.CB.(H，S)A、B、Y)C、D、T)答案：B解析：由題可得如下推導：(H，S)+R，(H，R)+C，C--4T，(H，T)--4R，故可知(H，S)為關系模式的碼。21.線性表是()。A、一個有限序列，可以為空B、一個有限序列，不可以為空C、一個無限序列，可以為空D、一個無限序列，不可以為空答案：A解析：線性表是具有相同特性的數(shù)據(jù)元素的一個有限序列，可以為空。22.對下列關鍵字序列用快速排序法進行排序時，速度最快的是()。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}答案：A解析：對于快速排序，若數(shù)據(jù)初始特性能夠使每趟排序劃分的兩塊大小相當，則排序效率會比較高。在A中，第一個元素21剛好是序列中7個元素的中間元素，將序列分成的兩個部分大小相等，第一次劃分后的結(jié)構(gòu)為(9，17，5)21(25，23，30)；第二次劃分，左右兩部分的第一個元素也剛好是所在塊序列的中間元素，同樣將所在塊分成均等的兩部分。在這種情況下排序的速度最快。23.設有向無環(huán)圖G中的有向邊集合E={＜1，2＞，＜2，3＞，＜3，4＞，＜1，4＞}，則下列屬于該有向圖G的一種拓撲排序序列的是()。A、1，2，3，4B、2，3，4，1C、1，2，4，3D、1，4，2，3答案：A解析：24.表長為n的順序存儲的線性表，當在任何位置上刪除一個元素的概率相等時，刪除一個元素所需移動元素的平均個數(shù)為()。A、nB、n/2C、(n-1)/2D、(n+1)/2答案：C解析：25.A、AB、BC、CD、D答案：C解析：26.設有一組初始記錄關鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關鍵字生成的二叉排序樹的深度為()。A、4B、6C、5D、7答案：A解析：27.A、21/7B、28/7C、15/6D、21/6答案：B解析：28.單向鏈表中往往含有一個頭結(jié)點，該結(jié)點不存儲數(shù)據(jù)元素，一般令鏈表的頭指針指向該結(jié)點，而該結(jié)點指針域的值為第一個元素結(jié)點的指針。以下關于單鏈表頭結(jié)點的敘述中，錯誤的是()。A、若在頭結(jié)點中存入鏈表長度值，則求鏈表長度運算的時間復雜度為O(1)B、在鏈表的任何一個元素前后進行插入和刪除操作可用一致的方式進行處理C、加入頭結(jié)點后，在鏈表中進行查找運算的時間復雜度為O(1)D、加入頭結(jié)點后，代表鏈表的頭指針不因為鏈表為空而改變答案：C解析：在鏈表中加入頭結(jié)點后，查找表中某一元素仍然要從頭指針出發(fā)，順序找到目標元素或失敗時找到表尾為止，時間復雜度與表長成正比。故D項錯誤。29.如果要求一個線性表既能較快的查找，又能適應動態(tài)變化的要求，則可采用的查找法是()。A、分塊查找B、順序查找C、折半查找D、基于屬性答案：A解析：分塊查找又稱索引順序查找，是一種性能介于順序查找和二分查找之間的查找方法。其基本思想是：(1)首先查找索引表：索引表是有序表，可采用二分查找或順序查找，以確定待查的結(jié)點在哪一塊。(2)然后在已確定的塊中進行順序查找：由于塊內(nèi)無序，只能用順序查找。分塊查找既能較快的查找，又能適應動態(tài)變化的要求。30.在向圖的鄰接矩陣表示中，計算第i個頂點八度的方法是()。A、第i行非零元素個數(shù)B、第i列非零元素個數(shù)C、第i行零元素個數(shù)D、第i列零元素個數(shù)答案：B解析：先用一個二維數(shù)組Edge存儲表示鄰接矩陣，輸入文件中頂點的序號是從1開始，當輸入一條有向邊＜u，v＞時，將Edge[u-1][v-1]=1即可；第i+1個頂點的出度等于鄰接矩陣中第i行所有元素中元素值為1的個數(shù)，把第i行所有元素值累加起來，得到的結(jié)果也是該頂點的出度，同理，在計算第i+1個頂點的入度時，也只需要將第i列所有元素值累加起來即可。31.若G是一個具有36條邊的非連通無向圖(不含自回路和多重邊)，則圖G至少有()個頂點。A、11B、10C、9D、8答案：B解析：要使圖的頂點數(shù)最少，應該盡量構(gòu)造一個完全圖，具有36條邊的無向完全圖的頂點數(shù)是9，又因為圖示非連通的，所以再加一個孤立的頂點即可。所以至少有10個頂點。32.從一個具有N個結(jié)點的單鏈表中查找其值等于X結(jié)點時，查找成功的情況下，需平均比較()結(jié)點。A、NB、N/2C、(N-1)/2D、(N+1)/2答案：D解析：33.快速排序在最壞情況下的時間復雜度為()。A、AB、BC、CD、D答案：D解析：34.設棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，es，e6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出隊的順序是e2，e4，e3，e6，e5，e1，則棧S的容量至少應該是()。A、6B、4C、3D、2答案：C解析：35.在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)()倍。A、1/2B、2C、1D、4答案：B向圖中每條邊都有兩個頂點，所以所有頂點的度數(shù)之和等于所有邊數(shù)的2倍。36.一棵m階非空B-樹，每個結(jié)點最多有()棵子樹。A、m/2B、m-1C、mD、m+1答案：C解析：B-樹中每個結(jié)點之多有m棵子樹，m就是B-樹的階。37.樹形結(jié)構(gòu)的特點是：一個結(jié)點可以有()。A、多個直接前驅(qū)B、多個直接后繼C、多個前驅(qū)D、一個后繼答案：B解析：樹的唯一根節(jié)點無前驅(qū)，葉子結(jié)點可以有多個且無后繼，樹的其他結(jié)點可以有多個后繼但只能有一個前驅(qū)。38.在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲()。A、數(shù)據(jù)的處理方法B、數(shù)據(jù)元素的類型C、數(shù)據(jù)元素之間的關系D、數(shù)據(jù)的存儲方法答案：C解析：在存儲數(shù)據(jù)時，需要存儲數(shù)據(jù)元素的值和數(shù)據(jù)元素之間的關系。39.向一個帶頭結(jié)點HS的鏈棧中插入一個s所指結(jié)點時需執(zhí)行()。A、HS-＞next=s；B、s-＞next=HS-＞next；HS-＞next=s；C、s-＞next=HS：HS=s；D、s-＞next=HS；HS=HS-＞next；答案：B解析：為了將結(jié)點s插入到帶頭結(jié)點HS的鏈棧中，首先需要修改s的指針域，使得s的下一個結(jié)點為鏈棧中的第一個有效結(jié)點，即數(shù)據(jù)域中存放有效數(shù)據(jù)的結(jié)點，該結(jié)點可由HS的指針域獲得，因此相應的語句為s-＞next=HS-＞next，之后使s結(jié)點成為鏈棧中的第一個有效結(jié)點，即HS的指針域指向s，相應的語句為HS-＞next=S。40.A、n-iB、n-i+lC、n-i-lD、i答案：A解析：順序表中的刪除操作是通過將當前結(jié)點用后面結(jié)點的值覆蓋來實現(xiàn)的，因此刪除第i個元素主要是前移第i個元素后的所有的元素，即n-i個元素。41.非空的循環(huán)單鏈表head的尾結(jié)點P滿足的條件是()。A、P.link=headB、p.link=NILC、p=NIL，D、p=head答案：A解析：對于循環(huán)單鏈表來說尾結(jié)點的指針指向第一個元素。42.在一裸m階的B+樹中，每個非葉結(jié)點的兒子數(shù)S應滿足()。A、AB、BC、CD、D答案：A解析：m階B+樹包含如下兩個特點：(1)每個分支結(jié)點至多有m棵子樹。(2)除根結(jié)點外的所有非終端結(jié)點每個結(jié)點至少有1(m+1)/21棵子樹。43.在有n個結(jié)點的二叉鏈表中，值為非空的鏈域的個數(shù)為()。A、n-1B、2n-1C、n+1D、2n+1答案：A解析：本題考查的是二叉樹的鏈式存儲。由于在有n個結(jié)點的二叉鏈表中，值為空的鏈域的個數(shù)為n+1個，而總的鏈域為2n(在二叉樹中每個結(jié)點頭2個鏈域)。所以，非空的鏈域的個數(shù)為2n-(n+1)=n-1。44.在一個雙鏈表中，刪除P結(jié)點之后的一個結(jié)點的操作是()。A、AB、BC、CD、D答案：C解析：考查雙鏈表中插入操作，要注意保存后繼節(jié)點。45.在向下生成的堆棧中，如果入棧指令PUSHX的操作定義為：SP←(SP)+1，M(SP)←M(X)，則出棧指令POPX應定義為()。A、SP←(SP)-1，M(X)←M(SP)B、SP←(SP)+1，M(X)←M(SP)C、M(X)←M(SP)，SP←(SP)-1D、M(X)←M(SP)，SP←(SP)+1答案：C解析：入棧是先定位棧頂指針然后存儲數(shù)據(jù)，出棧是先出數(shù)據(jù)，然后再定位棧頂指針。46.有n個記錄的文件，若關鍵字位數(shù)為d，基數(shù)為r，則基數(shù)排序共需進行()遍分配與收集。A、nB、rC、dD、d+r答案：C解析：47.以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？()A、線性表B、棧C、隊列D、二叉樹答案：D解析：線性表、棧、隊列都是線性結(jié)構(gòu)，樹、圖是非線性結(jié)構(gòu)。48.非空的循環(huán)單鏈表FIRST的尾結(jié)點(由P所指向)滿足：()。A、P—＞EXT=NULL；B、P=NULL；C、P—NEXT-FIRST；D、P=FIRST；答案：C解析：循環(huán)單鏈表是單鏈表的一種特殊形式，其結(jié)構(gòu)特點是鏈表中最后一個結(jié)點的指針域不再是結(jié)束標記(NULL)，而是指向鏈表中的第一個結(jié)點，從而使鏈表形成一個環(huán)。在本題中，F(xiàn)IRST指向循環(huán)單鏈表的首結(jié)點，P指向尾結(jié)點，可知P—＞NEXI=FIRST。49.設有5000個元素，希望用最快的速度挑選出前10個最大的，采用()方法最好。A、希爾排序B、歸并排序C、快速排序D、堆排序答案：D解析：堆排序不必將整個序列排序即可確定前若干個最大(或最小)元素。50.如果一棵完全二叉樹共有26個結(jié)點，則必定有()個結(jié)點的度為1。A、0B、1C、3D、13答案：B解析：26個結(jié)點，可知該二叉樹有5層。由于前4層組成一棵滿二叉樹，共15個結(jié)點，則共有11個葉子結(jié)點，可知只有1個結(jié)點的度為1。51.設二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均查找長度為()。A、AB、BC、CD、D答案：B解析：52.設無向圖的頂點個數(shù)為n，則該圖最多有()條邊。A、AB、BC、CD、D答案：B解析：53.下列不屬于內(nèi)部排序的算法是()。A、歸并排序B、拓撲排序C、樹型排序D、折半插入排序答案：B解析：歸并排序、樹型排序、折半插入排序?qū)儆趦?nèi)部排序算法，拓撲排序不屬于內(nèi)部排序算法。54.在由4棵樹組成的森林中，第一、第二、第三和第四棵樹中的結(jié)點個數(shù)分別為30，10，20，5，當把森林轉(zhuǎn)換成二叉樹后，對應的二叉樹中根結(jié)點的左子樹中結(jié)點個數(shù)為()。A、20B、29C、30D、35答案：B解析：當把森林轉(zhuǎn)換成二叉樹后，第二、第三和第四棵樹均在第一棵樹的根結(jié)點的右子樹上。55.二維數(shù)組A的每個元素是由6個字符組成的串，行下標的范圍從0～8，列下標的范圍是從0～9，則存放A至少需要()個字節(jié)。A、240B、540C、90D、180答案：B解析：數(shù)組A為9行10列，共有90個元素，所以，存放A至少需要90×6=540個存儲單元。56.若對27個元素只進行三趟多路歸并排序，則選取的歸并路數(shù)為()。A、2B、3C、4D、5答案：B解析：57.在一棵高度為h的理想平衡二叉樹中，最少含有()個結(jié)點，最多含有()個結(jié)點。A、AB、BC、CD、D答案：D解析：58.A、abcfdegB、abcgfdeC、abcdefgD、abcfgde答案：A解析：本題考查深度優(yōu)先算法。59.如果以鏈表作為棧的存儲結(jié)構(gòu)，則退鏈棧操作時()A、必須判斷鏈棧是否滿B、判斷鏈棧元素的類型C、必須判斷鏈棧是否空D、對鏈棧不做任何判斷答案：C解析：在鏈表的退鏈棧操作時，如果棧已空.就沒有元素可供退棧，返回退棧失敗信息，所以必須判斷鏈棧是否空。60.循環(huán)隊列qu的隊空條件是()。A、(qu.rear+1)%MaxSize==(qu.front+1)%MaxSizeB、(qu.rear+1)%MaxSize-=qu.front+1C、(qu.rear+1)%MaxSize==qu.frontD、qu.rear==qu.front答案：D解析：循環(huán)隊列為空，當且僅當隊尾指針等于隊尾指針.具體的操作語句為qu.rear==qu.front。61.中綴表達式A-(B+C/D)*E的后綴形式是()。A、AB-C+D/E*B、ABC+D/-E*C、ABCD/E*+-D、ABCD/+E*-答案：D解析：將中綴表達式表示成二叉樹的形狀，則這棵二叉樹的后序遍歷序列即為表達式的后綴形式。62.用s表示入棧操作，*表示出棧操作，棧的初態(tài)、終態(tài)均為空，人棧和出棧的操作序列可表示成僅為由S和*組成的序列。下面的序列中合法的操作序列有()。A、S*SS*S**B、SSS****SC、S**S*SS*D、SSS*S*S*答案：A解析：要使棧的初態(tài)、終態(tài)均為空，入棧和出棧的操作次數(shù)應該相等，因此排除D項。而BC兩項項都出現(xiàn)某一時刻棧已空的情況下執(zhí)行出棧操作。63.若一個具有n個結(jié)點、k條邊的非連通無向圖是一個森林(n＞k)，則該森林中必有()棵樹。A、kB、nC、n-kD、n+k答案：C解析：一個具有n個結(jié)點的樹有n-l條邊，結(jié)點數(shù)比邊數(shù)多1，則若一個森林中有m棵樹，其結(jié)點數(shù)比邊數(shù)多m。反過來，森林中樹的個數(shù)等于結(jié)點數(shù)減去邊數(shù)。64.頭指針為head的帶頭結(jié)點的循環(huán)鏈表為空的判定條件是()。A、head=nullB、head—＞next=nullC、head—＞next=headD、head—＞null答案：C解析：循環(huán)鏈表為空，即頭結(jié)點的后繼結(jié)點是頭結(jié)點本身，具體的操作語句為head—＞next=head。65.設有向圖G=(V，E)和G′-(V′，E′).如(G′)是G生成樹，下面說法中不正確的是()A、G′為G的連通分量B、G′為G的無環(huán)子圖C、G′為G的子圖D、G′為G的極小連通子圖且V′=V答案：A解析：B項、D項都是生成樹的特點，而A項為概念錯誤：G′為連通圖而非連通分量，圖的連通分量是指無向圖中的極大連通子圖。66.對于具有n個頂點、6條邊的圖()。A、采用鄰接矩陣表示圖時，查找所有頂點的鄰接頂點的時間復雜度為O(n2)B、進行廣度優(yōu)先遍歷運算所消耗的時間與采用哪一種存儲結(jié)構(gòu)無關C、采用鄰接表表示圖時，查找所有頂點的鄰接頂點的時間復雜度為O(n*e)D、進行深度優(yōu)先遍歷運算所消耗的時間與采用哪一種存儲結(jié)構(gòu)無關答案：A解析：67.在()存儲結(jié)構(gòu)中，數(shù)據(jù)結(jié)構(gòu)中元素的存儲地址與其關鍵字之間存在某種映射關系。A、樹形存儲結(jié)構(gòu)B、鏈式存儲結(jié)構(gòu)C、索引存儲結(jié)構(gòu)D、散列存儲結(jié)構(gòu)答案：D解析：散列存儲結(jié)構(gòu)中是根據(jù)設定的哈希函數(shù)和處理沖突的方法將一組關鍵字映像到一個連續(xù)的地址集上，并以關鍵字在地址集中的象作為記錄在表中的存儲位置。而樹形存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)和索引存儲結(jié)構(gòu)中關鍵字在結(jié)構(gòu)中的相對位置是隨機的。68.A、頂點序列B、邊序列C、權(quán)值總和D、邊的條數(shù)答案：A解析：69.(1)靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元素的時間與i無關。(2)靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時就確定了，以后不能增加。(3)靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動。以上錯誤的是()。A、(1)，(2)B、(1)C、(1)，(2)，(3)D、(2)答案：B解析：靜態(tài)鏈表借用一維數(shù)組來描述線性鏈表。數(shù)組中的一個分量表示一個結(jié)點，同時使用游標(指示器cur)代替指針以指示結(jié)點在數(shù)組中的相對位置。這種存儲結(jié)構(gòu)仍然需要預先分配一個較大空間，但是在進行線性表的插入和刪除操作時不需要移動元素，僅需要修改“指針”，因此仍然具有鏈式存儲結(jié)構(gòu)的主要優(yōu)點，(2)，(3)是正確的，但它不具備直接存取數(shù)據(jù)的特性，所以只有(1)是錯誤的。70.在一棵具有n個結(jié)點的二叉樹中，所有結(jié)點的空子樹個數(shù)等于()。A、nB、n-1C、n+1D、2×n答案：C解析：71.在最好和最壞情況下的時間復雜度均為0(nlogn)且穩(wěn)定的排序方法是()。A、基數(shù)排序B、歸并排序C、快速排序D、堆排序答案：B解析：快速排序和堆排序是不穩(wěn)定的，基數(shù)排序和歸并排序是穩(wěn)定的。基數(shù)排序的平均時間為O(d(n+rd))，最壞情況下時間復雜度為O(d(n+rd))；歸并排序是一種穩(wěn)定的排序方法，其最好和最壞情況下的時間復雜度為O(nlogn)。72.假定一棵度為3的樹中結(jié)點數(shù)為50，則其最小高度應為()。A、5B、6C、3D、4答案：A解析：73.快速排序最易發(fā)揮其長處的情況是()。A、被排序的數(shù)據(jù)中含有多個相同排序碼B、被排序的數(shù)據(jù)已基本有序C、被排序的數(shù)據(jù)完全無序D、被排序的數(shù)據(jù)中的最大值和最小值相差懸殊答案：C解析：74.用順序存儲的方法將完全二叉樹中的所有結(jié)點逐層存放在數(shù)組A[1]～A[n]中，結(jié)點A[i]若有左子樹，則左子樹的根結(jié)點是()。A、A[i/2]B、A[2i]C、A[2i-1]D、A[2i+1]答案：B解析：據(jù)二叉樹的性質(zhì)5，對完全二叉樹從上到下、從左至右給結(jié)點編號，若編號為2i的結(jié)點存在，則i的左子樹一定是A[2i]。75.在單鏈表指針為P的結(jié)點之后插入指針為s的結(jié)點，正確的操作是()。A、AB、BC、CD、D答案：B解析：在單鏈表結(jié)點P后插入結(jié)點s，要先改變s結(jié)點的指針域，指向p的后繼結(jié)點。然后將s的地址賦給P的指針域。具體的操作語句為s—＞next=P—＞next；p—＞next=s。76.在具有n個結(jié)點的順序表，算法的時間復雜度是O(1)的操作是()。A、AB、BC、CD、D答案：A解析：77.二維數(shù)組A的每個元素是由6個字符組成的串，其行下標i=O，1，…，8，列下標j=1，2，…，10。設每個字符占一個字節(jié)。若A按行先存儲，元素A[8，5]的起始地址與當A按列先存儲時起始地址相同的元素是()。A、A[8，5]B、A[3，10]C、A[5，8]D、A[0，9]答案：B解析：元素A[8，5]的起始地址與當A按列先存儲時的A[i，j]元素的起始地址相同，即8×10+5-1=(j-1)×9+i，將四個答案代入可得正確答案。78.下列文件的物理結(jié)構(gòu)中，不利于文件長度動態(tài)增長的文件物理結(jié)構(gòu)是()。A、順序結(jié)構(gòu)B、鏈式結(jié)構(gòu)C、索引結(jié)構(gòu)D、Hash結(jié)構(gòu)答案：A解析：順序結(jié)構(gòu)又稱連續(xù)結(jié)構(gòu)。這是一種最簡單的物理結(jié)構(gòu)，它把邏輯上連續(xù)的文件信息依次存放在連續(xù)編號的物理塊中，只要知道文件在存儲設備上的起始地址(首塊號)和文件長度(總塊數(shù))，就能很快地進行存取。這種結(jié)構(gòu)的優(yōu)點是訪問速度快，缺點是文件長度增加困難。因此，順序結(jié)構(gòu)的磁盤空間利用率不高，不利于文件長度動態(tài)增長。79.將5個字母“ooops”按此順序入棧，則有()種不同的出棧順序可以仍然得到“ooops”。A、1B、3C、5D、6答案：C解析：此題可以首先列出所有可能的出棧順序，然后列出各個出戰(zhàn)順序的結(jié)果，計數(shù)即可。80.有m個葉子結(jié)點的哈夫曼樹所具有的結(jié)點數(shù)為()。A、mB、m+1C、2mD、2m-1答案：D解析：哈夫曼樹中僅有度為0和2的結(jié)點，由二叉樹的性質(zhì)可知，具有m個葉子結(jié)點的哈夫曼樹具有m-1個度為2的結(jié)點，因此，具有m個葉子結(jié)點的哈夫曼樹所具有的節(jié)點數(shù)為2m-1。81.已知一個有序表為(12，18，24，35，47，50，62，83，90，115，134)，當折半查找值為90的元素時，經(jīng)過()次比較后查找成功。A、2B、3C、4D、5答案：A解析：根據(jù)二分法查找的查找過程，首先將90與表中中間的元素50進行比較，由于90大于50，所以在線性表的后半部分查找。第二次與比較的元素是后半部分的中間元素，即90，這時兩者相等，即查找成功。82.設一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為()。A、219B、129C、189D、229答案：D解析：83.散列函數(shù)有一個共同的性質(zhì)，即函數(shù)值應當以()概率取其值域的每個值。A、最大概率B、最小概率C、平均概率D、同等概率答案：D解析：散列函數(shù)的構(gòu)造萬痃有很多，每種構(gòu)造方法的目的都是盡量減少沖突。為了減少沖突計算出的結(jié)果應以同等概率分布到值域的各個部分。84.n個頂點的連通圖至少有多少條邊()。A、n-1B、nC、n+1D、0答案：A解析：至少要有(n-1)條邊(也就是樹)才能保證圖為連通圖。85.一個棧的入棧序列是1，2，3，4，5，則棧的不可能的輸出序列是()。A、43512B、12345C、54321D、45321答案：A解析：此題有一個技巧：在輸出序列中任意元素后面不能出現(xiàn)比該元素小并且是升序(指的是元素的序號)的兩個元素。86.設一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點，則其判空條件是()。A、head==0B、head-＞next==0C、head！=0D、head-＞next==head答案：A解析：因為單鏈表沒有頭結(jié)點，所以當頭指針為空時證明鏈表為空。87.A、14B、19C、21D、26答案：C解析：本題考查最小生成樹算法。88.A、(1)，(2)，(3)B、(1)C、(1)，(3)D、(2)，(3)答案：C解析：89.線索化的二叉樹中，某結(jié)點*P沒有孩子的充要條件是()。A、p-＞lchild=NULLB、p-＞ltag=l&&p-＞rtag=1C、p-＞ltag=0D、p-＞lchild=NULL&&p-＞ltag=1答案：B解析：考查線索二叉樹。90.算法分析的目的是()。A、找出數(shù)據(jù)結(jié)構(gòu)的合理性B、研究算法中輸入和輸出的關系C、分析算法的效率以求改進D、分析算法的易懂性和文檔性答案：C解析：算法分析的目的是分析算法的效率以求改進。91.順序查找不論在順序線性表中還是在鏈式線性表中的時間復雜度為()。A、AB、BC、CD、D答案：B論是順序存儲還是鏈式存儲，使用順序查找法的時間復雜度相同。92.高度為7的AVL樹最少有()個結(jié)點。A、31B、32C、33D、34答案：C解析：93.下列命題正確的是()。A、一個圖的鄰接矩陣表示不唯一的，鄰接表表示也不唯一B、一個圖的鄰接矩陣表示是唯一的，鄰接表表示也唯一C、一個圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一D、一個圖的鄰接矩陣表示不唯一的，鄰接表表示是唯一答案：C解析：一個圖的鄰接矩陣表示是唯一的，鄰接表表示不唯一。94.在一個長度為n(n＞1)的帶頭結(jié)點單鏈表h上，另設有尾指針r(指向尾結(jié)點)。與鏈表的長度有關的操作是()。A、刪除單鏈表中的第一個元素B、刪除單鏈表中的最后一個元素C、在單鏈表第一個元素前插入一個新元素D、在單鏈表最后一個元素后插入一個新元素答案：B解析：在單鏈表中要刪除最后一個元素必須找到尾結(jié)點的前驅(qū)結(jié)點的指針。由于單鏈表只能訪問結(jié)點的下一個結(jié)點，所以根據(jù)尾指針不能夠直接找到它的前驅(qū)結(jié)點，只有從頭開始依次向下找到尾結(jié)點的前驅(qū)結(jié)點。所以刪除單鏈表中的最后一個元素與鏈表的長度有關。95.設一棵二叉樹的深度為k，則該二叉樹中最多有()個結(jié)點。A、1B、2k-1C、2D、k-1答案：B解析：一棵深度為k的二叉樹，結(jié)點最多為2k-1個。96.如果S是由有序樹T轉(zhuǎn)換的二叉樹，則T中的結(jié)點的后序遍歷順序是S結(jié)點的()。A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷答案：B解析：樹轉(zhuǎn)換成二叉樹的過程：將結(jié)點的最左邊的孩子作為該節(jié)點的左孩子，下一個兄弟結(jié)點作為右孩子。所以樹的后序遍歷恰好對應于二叉樹的中序遍歷。97.指出在順序表F={2，5，7，10，14，15，18，23，35，41，52}中，用二分查找法查找12需要進行多少次比較()。A、2B、3C、4D、5答案：C解析：折半查找又稱二分查找，其基本思想：首先用要查找的關鍵字k與中間位置的結(jié)點的關鍵字相比較，這個中間結(jié)點把線性表分成了兩個子表，若比較結(jié)果相等則查找完成；若不相等，再根據(jù)k與該中問結(jié)點關鍵字的比較大小確定下一步查找哪個子表，這樣遞歸進行下去，直到找到滿足條件的結(jié)點或者該線性表中沒有這樣的結(jié)點。98.線索二叉樹中某結(jié)點R沒有左孩子的充要條件是()。A、R.ltag=1B、R.rchild=NULLC、R.lchild=NULLD、R.ltag=0答案：D解析：線索二叉樹中某結(jié)點是否有左孩子，不能通過左指針域是否為空來判斷，而要判斷左標志是否為0。99.設有n個關鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關鍵字映射到HASH表中需要做()次線性探測。A、n(n+1)B、nC、n(n+1)/2D、n(n-1)/2答案：D解析：線性探測解決沖突的辦法指一旦目標空間被占有，則探測相鄰的下一個空間，如果空閑則插入，否則繼續(xù)向下一個探測，如果到了隊列末尾則返回隊列頭探測，一旦全部空間都被占據(jù)則無法插入。100.快速排序最不利于發(fā)揮其長處的情況是()。A、待排序的數(shù)據(jù)中含有多個相同值B、待排序的數(shù)據(jù)已基本有序C、待排序的數(shù)據(jù)量太大D、被排序的數(shù)據(jù)數(shù)量為奇數(shù)答案：B解析：各種排序方法對待排序的數(shù)據(jù)中是否含有多個相同值、被排序的數(shù)據(jù)數(shù)量為奇數(shù)或偶數(shù)都沒有影響。快速排序等改進的排序方法均適用于待排序數(shù)據(jù)量較大的情況。101.二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷：HFIEJKG。該二叉樹根的右子樹的根是()A、EB、FC、GD、H答案：C解析：102.串′ababaaababaa′的next數(shù)組值為()。A、01234567899B、012121111212C、011234223456D、0123012322345答案：C解析：103.設指針q指向單鏈表中結(jié)點A，指針p指向單鏈表中結(jié)點A的后繼結(jié)點B，指針s指向被插入的結(jié)點X，則在結(jié)點A和結(jié)點B插入結(jié)點X的操作序列為()。A、p-＞next=s；s-＞next=q；B、q-＞next=s；s-＞next=p；C、p-＞next=s-＞next；s-＞next=p；D、s-＞next=p-＞next；p-＞next=-s；答案：B解析：插入s結(jié)點，應使s的next指針指向p結(jié)點，使q結(jié)點的next指針指向s。104.隊列是一種()的線性表。A、先進先出B、只能插入C、先進后出D、只能刪除答案：A解析：隊列的特點是先進先出、后進后出。105.設無向圖G中有n個頂點e條邊，則其對應的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別為()。A、e，nB、n.eC、2n，eD、n.2e答案：D解析：使用鄰接表存儲圖，圖有多少結(jié)點，鄰接表就有多少個表頭，無向圖的表結(jié)點個數(shù)為2e。106.設一組初始關鍵字記錄關鍵字為(20，15，14，18，21，36，40，10)，則以20為基準記錄的一趟快速排序結(jié)束后的結(jié)果為()。A、10，15，14，18，20，36，40，21B、15，10，14，18，20，36，40，21C、10，15，14，20，18，40，36，21D、10，15，14，18，20，40，36，21答案：A解析：快速排序的每趟排序在待排序列中選取一個數(shù)為基準，將序列劃分為兩段，一段的值比基準值小，另一段大于或等于基準值。在快速排序中通常有兩個指針分別為i和j，j從后向前遍歷，找第一個小于基準值的節(jié)點，將值交換，i從前向后遍歷，找到第一個大于或等于基準值的節(jié)點，將值交換，重復此過程，直至i和j指向同一節(jié)點，一趟排序結(jié)束。107.對關鍵碼序列28，16，32，12，60，2，5，72快速排序.從小到大一次劃分結(jié)果為()。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)答案：B解析：根據(jù)快速排序的思想，容易得到序列28，16，32，12，60，2，5，72一次排序后的結(jié)果(5，16，2，12)28(60，32，72)。108.求解Hanoi問題時，若初始有5個圓盤，則移動圓盤的次數(shù)是()。A、7B、15C、31D、5答案：C解析：109.二叉排序樹中，最小值結(jié)點的()。A、左、右指針均為空B、左、右指針均不為空C、左指針一定為空D、右指針一定為空答案：C解析：在二叉排序樹中，值最小的結(jié)點一定是中序遍歷序列中第一個被訪問的結(jié)點，即二叉樹的最左下結(jié)點。110.某二叉樹的前序遍歷序列為UKLMNO，中序遍歷序列為JLKINMO，則后序遍歷序列為()。A、JLKMNOIB、LKNJOMIC、LKJNOMID、LKNoMI答案：C解析：111.關于哈夫曼樹，下列說法正確的是()。A、在哈夫曼樹中，權(quán)值相同的葉子結(jié)點都在同一層上B、在哈夫曼樹中，權(quán)值較大的葉子結(jié)點一般離根結(jié)點較遠C、哈夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點離根較近D、在哈夫曼編碼中，當兩個字符出現(xiàn)頻率相同時，其編碼也相同，對于這種情況應作特殊外理答案：C解析：哈弗曼編碼中不允許出現(xiàn)兩個字符編碼相同的情況。112.設順序線性表的長度為30，分成5塊，每塊6個元素，如果采用分塊查找，則其平均查找長度為()。A、5B、11C、7D、6.5答案：D解析：分塊查找是先在索引下進行查找，找到該元素可能存在的塊號，然后在塊中順序查找。則本題的平均查找長度為(5+1)/2+(6+1)/2=6.5。113.將兩個長度為N的有序表歸并到一個長度為2N的有序表，最少需要比較的次數(shù)是()，最多需要比較的次數(shù)是()。A、N，2N-1B、N-l，2NC、N，2ND、N-l，2N-1答案：A解析：對于此題而言最少的比較次數(shù)是，其中一個有序表的最后一個數(shù)小于另一表的的第一個數(shù)，那么直接合并即可。當一個表遞增一個表遞減且遞減表時，需要比較ZN-1次。114.靜態(tài)查找與動態(tài)查找的根本區(qū)別在于()。A、所包含的數(shù)據(jù)元素的類型不一樣B、存儲實現(xiàn)不一樣C、它們的邏輯結(jié)構(gòu)不一樣D、施加在其上的操作不同答案：D解析：靜態(tài)查找不涉及插入和刪除操作，而動態(tài)查找涉及插入和刪除操作。115.判斷一個有向圖是否存在回路的方法除了可以利用拓撲排序方法外。還可以用()。A、求關鍵路徑的方法B、求最短路徑的Dijkstra方法C、廣度優(yōu)先遍歷算法D、深入度優(yōu)先遍歷算法答案：D解析：判斷一個圖是否存在回路的方法包括：(1)設圖G是n個頂點的無向圖，若G的邊數(shù)e＞=n，則圖G中一定有回路存在。(2)設圖G是n個頂點的無向連通圖，若G的每個頂點的度＞=2，則圖G中一定有回路存在。(3)利用拓撲排序算法可以判斷圖中是否存在回路。即在拓撲排序輸出結(jié)束后所余下的頂點均有前驅(qū)，則說明只得到了部分頂點的拓撲有序序列，圖中存在有回路。(4)利用深度優(yōu)先遍歷算法可以判定圖G中是否存在回路。對于無向圖來說，若深度優(yōu)先遍歷過程中遇到了回邊則必定存在環(huán)；對于有向圖來說，這條回邊可能是指向深度優(yōu)先森林中另一棵生成樹上頂點的弧；但是，如果從有向圖上的某個項點v出發(fā)進行深度優(yōu)先遍歷，若在dfs(v)結(jié)束之前出現(xiàn)一條認頂點v到頂點v的回邊，因u在生成樹上是v的孫子，則有向圖必定存在半含頂點u和頂點v的環(huán)。116.若要求盡可能快地對序列進行穩(wěn)定的排序，則應選()A、快速排序B、歸并排序C、冒泡排序D、堆排序答案：B解析：117.若用單鏈表來表示隊列，則應該選用()。A、帶尾指針的非循環(huán)鏈表B、帶尾指針的循環(huán)鏈表C、帶頭指針的非循環(huán)鏈表D、帶頭指針的循環(huán)鏈表答案：B解析：假設尾指針為TAIL，則通過TAIL可訪問隊尾，通過TAIL—＞next可訪問隊頭。118.設有一個二維數(shù)組A[m][n]，假設A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3]存放在什么位置？腳注(10)表示用10進制表示。()A、678B、688C、692D、696答案：C解析：A[2][2]是A[0][0]后面的第2n+2個元素，即2n+2=676-644，解得n=15。A[3][3]是A[2][2]后面的第n+1個元素，676+n+1=692，則A[3][3]存放位置是692。119.采用開放定址法處理散列表的沖突時，其平均查找長度()。A、與鏈接法處理沖突相同B、高于二分查找C、低于鏈接法處理沖突D、高于鏈接法處理沖突答案：D解析：開放定址法處理沖突的平均查找長度高于鏈接法。120.按照二叉樹的定義，具有3個結(jié)點的二叉樹有()種。A、3B、4C、5D、6答案：C解析：121.完全二叉樹高度為h，則最左邊的葉子結(jié)點序號為()。A、AB、BC、CD、D答案：B解析：122.在一棵完全二叉樹中，其根的序號為1，()可判定序號為p和q的兩個結(jié)點是否在同一層。A、AB、BC、CD、D答案：A解析：123.以比較為基礎的排序算法在最壞情況下的計算時間下界為()。A、AB、BC、CD、D答案：D解析：124.對特殊矩陣采用壓縮存儲的目的主要是為了()。A、去掉矩陣中的多余元素B、減少不必要的存儲空間C、表達變得簡單D、對矩陣元素的存取變得簡單答案：B解析：在特殊矩陣中，有很多值相同的元素并且他們的分布有規(guī)律，沒有必要為值相同的元素重復存儲。125.算法指的是()。A、計算機程序B、解決問題的計算方法C、排序算法D、解決問題的有限運算序列答案：D解析：算法是精確定義的一系列規(guī)則，它指出怎樣從給定的輸入信息經(jīng)過有限步驟產(chǎn)生所求的輸出信息。它既不是計算機程序，也不是某種算術(shù)運算。126.設某強連通圖中有n個頂點，則該強連通圖中至少有()條邊。A、n+1B、n(n-1)C、nD、n(n+1)答案：C解析：強連通圖是指在一個有向圖中，若從節(jié)點i到節(jié)點j有路徑，并且節(jié)點j到i有路徑，那么為強連通圖。127.Hash表是用于數(shù)據(jù)存儲的一種有效的數(shù)據(jù)結(jié)構(gòu)，Hash表的查找復雜度依賴于Hash值算法的有效性，在最好的情況下，Hash表的查找復雜度為()。A、O(nlogn)B、O(logn)C、O(n)D、O(1)答案：D解析：0(1)，哈希表是通過計算hashcode來定位元素位置，所以只需一次即可。128.有關二叉樹下列說法正確的是()。A、二叉樹的度為2B、一棵二樹的度可以小于2C、二叉樹中至少有一個結(jié)點的度為2D、二叉樹中任何一個結(jié)點的度都為2答案：B解析：二叉樹的特點是每個結(jié)點至多有兩棵子樹，即不存在度大于2的結(jié)點。B項是說可以小于2，符合二叉樹的特點。129.A、AB、BC、CD、D答案：D解析：130.A、O(m×n×t)B、O(m+n+t)C、O(m×t+n)D、O(m+n×t)答案：A解析：在程序段中，有兩段循環(huán)程序，第一段是一個雙層嵌套循環(huán)，另一個是三層嵌套循環(huán)，所以基本操作是c[i][j]=c[i][j]+a[i][k]×b[k][j]，此基本操作共執(zhí)行m×t×n次。131.下面關于求關鍵路徑的說法不正確的是()。A、求關鍵路徑是以拓撲排序為基礎的B、一個事件的最早開始時間同以該事件為尾的弧的活動最早開始時間相同C、一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差D、關鍵活動一一定位于關鍵路徑上答案：C解析：最遲開始時間應等于本工作的最遲完成時間與其持續(xù)時間之差。132.下列排序算法中，()算法可能會出現(xiàn)下面情況：在最后一趟開始之前，所有元素都不在其最終的位置上。A、堆排序B、冒泡排序C、快速排序D、插入排序答案：D解析：插入排序在最后一個元素被插入時，所有元素都要后移，即在最后一趟開始之前，所有元素都不在其最終的位置上。133.設無向圖G中的邊的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為()。A、aedfcbB、aedfbcC、aebcfdD、acfebd答案：A解析：134.A、AB、BC、CD、D答案：C解析：135.引入二叉線索樹的目的是()。A、加快查找結(jié)點的前驅(qū)或后繼的速度B、為了能在二叉樹中方便地進行插入與刪除C、為了能方便地找到雙親D、使二叉樹的遍歷結(jié)果唯一答案：A解析：當以二叉鏈表作為存儲結(jié)構(gòu)存儲非線索化的二叉樹時，只能找到結(jié)點的左、右孩子信息，而不能直接得到結(jié)點在任一遍歷序列中的直接前驅(qū)和直接后繼的結(jié)點信息，這種信息只有在遍歷的動態(tài)過程中才能得到。二叉線索樹利用空鏈域存放結(jié)點的前驅(qū)和后繼結(jié)點的信息，這樣能保存遍歷過程中得到的信息?？梢?，引入二叉線索樹的目的是方便查找結(jié)點的前驅(qū)或后繼結(jié)點的速度。136.設用數(shù)組A[1，n]作為兩個棧S1、S2的共用存儲空間，對任一個棧，只有當數(shù)組A[1，n]全滿時才不作入棧操作，則分配這兩個?？臻g的最佳方案是()。A、S1的棧底位置設為1，S2的棧底位置設為nB、S1的棧底位置設為n/2，S2的棧底位置設為n/2+1C、S1的棧底位置設為1，S2的棧底位置設為n/2D、S1的棧底位置設為n/2，S2的棧底位置設為1答案：A解析：由于棧中元素個數(shù)不固定，因此如果將棧底設在中間位置，固定了棧中元素的個數(shù)，不能滿足只有當數(shù)組全滿時才不作入棧操作的要求。137.以下說法正確的是()。A、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系。B、數(shù)據(jù)元素是數(shù)據(jù)結(jié)構(gòu)的最小單位。C、數(shù)據(jù)結(jié)構(gòu)的基本操作的設置的最重要的準則是，實現(xiàn)應用程序與存儲結(jié)構(gòu)的獨立。D、判斷某個算法是否容易閱讀是算法分析的任務之一。答案：C解析：A項，數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)元素之間的邏輯關系，而不是數(shù)據(jù)項之間的邏輯關系。B項，數(shù)據(jù)元素是數(shù)據(jù)結(jié)構(gòu)的基本單位，數(shù)據(jù)結(jié)構(gòu)的最小單位是數(shù)據(jù)項。D項，算法分析是一個軟件的驗證確認任務，用于保證選擇的算法是正確的、合適的和穩(wěn)定的，并且滿足所有精確性、規(guī)模和時間方面的要求，保證產(chǎn)品高質(zhì)量高效率的運行。容易閱讀是增加算法的可讀性，不是算法分析的任務。138.下面幾個符號串編碼集合中，不是前綴編碼的是()。A、{0，10，110，1111}B、{11，10，001，101，0001}C、{00，010，0110，1000}D、{b，c，aa，aba，abb，abc}答案：B解析：前綴編碼的定義：任一個字符的編碼都不是另一個字符的編碼的前綴。B選項中10是101的前綴，因此其不是前綴編碼。139.在單鏈表中，指針p指向結(jié)點A，若要刪除A之后的結(jié)點(存在)，則指針的操作方式為()。A、p—＞next=p—＞next—＞nextB、p=p—＞nextC、p=p—＞next—＞nextD、p-＞next-p答案：A解析：要在單鏈表中刪除p指向的結(jié)點的后繼結(jié)點，需要將后繼結(jié)點的后繼交給p所指結(jié)點的指鏟域。具體實現(xiàn)語句為p—＞next=p—＞next—＞next。140.設有廣義表D(a，b，D)，其長度為3，深度為()A、∞B、3C、2D、5答案：A解析：長度為3，但是因第三個元素是一個廣義表，所以深度為無窮。141.設森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是()。A、M1B、M1+M2C、M3D、M2+M3答案：D解析：森林轉(zhuǎn)換成二叉樹的原則：將第一棵樹的根結(jié)點作為根結(jié)點，所有結(jié)點的第一個左孩子作為左孩子，下一個兄弟結(jié)點作為右孩子，其它樹作為第一棵樹的右孩子。所以森林F對應的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是M2+M3。142.設某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為()。A、12B、10C、11D、9答案：C解析：想使二叉樹的高度最小，即為完全二叉樹的時候，所以高度最小為11。143.有六個元素6，5，4，3，2，1的順序進棧.下列選項中，()不是合法的出棧序列。A、543612B、453126C、346521D、234156答案：C解析：根據(jù)棧的后進先出的特點，對于C選項中前兩個元素得出棧順序可以看出，4在5和6前先出棧，有根據(jù)入站順序，4在5和6后入棧，因此4出棧時，5和6必定在棧內(nèi)，且5在6之上，所以出棧時5要比6先出棧。144.若允許表達式內(nèi)多種括號混合嵌套，則為檢查表達式中括號是否正確配對的算法，通常選用的輔助結(jié)構(gòu)是()。A、棧B、線性表C、隊列D、二叉排序樹答案：A解析：棧(stack)又稱為堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算，這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素稱作出棧或退棧，它是把棧頂元素刪除，使其相鄰的元素成為新的棧頂元素。145.設森林F對應的二叉樹為B，它有m個結(jié)點，B的根為p，p的右子樹結(jié)點個數(shù)為n，森林F中，第一棵樹的結(jié)點個數(shù)是()。A、m-nB、m-n-1C、n+1D、條件不足，無法確定答案：A解析：森林轉(zhuǎn)換成二叉樹的原則：將第一棵樹的根結(jié)點作為根結(jié)點，所有結(jié)點的第一個左孩子作為左孩子，下一個兄弟結(jié)點作為右孩子，其它樹作為第一棵樹的右孩子。所以森林F中第一棵樹的結(jié)點個數(shù)是m-n。146.A、AB、BC、CD、D答案：A解析：147.用P代表入棧，O代表出棧。棧的初始狀態(tài)和最終狀態(tài)都為空，則下列棧操作正確的是()。A、POOPOOPPB、POPOPOOPC、PPPOOOPPD、PPPOOPOO答案：D解析：AB兩項，均會出現(xiàn)下溢，即出棧時棧為空。C項，導致出現(xiàn)最終狀態(tài)不為空。148.以下有關算法的說法錯誤的是()。Ⅰ.算法原地工作的含義是指不需要任何額外的輔助空間；Ⅱ，在相同的規(guī)模n下，復雜度O(n)的算法在時間上總是優(yōu)于復雜度O(2n)的算法；Ⅲ.所謂最壞時間復雜度是指最壞情況下估算算法執(zhí)行時間的一個上界；Ⅳ，同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低。A、ⅠB、Ⅰ和ⅡC、Ⅰ和ⅣD、Ⅲ答案：C解析：算法原地工作的含義是指算法的空間復雜度為O(1)，同一個算法實現(xiàn)語言的級別越高執(zhí)行效率并不一定越低。149.A、(1)B、(1)、(2)C、(1)、(4)D、(3)答案：C解析：(1)項，原地工作不是不需要額外空間，而是額外空間相對于問題的規(guī)模(輸入數(shù)據(jù)量)來說是個常數(shù)，那么我們就稱之為原地工作。(4)項，這個結(jié)論不是絕對的，要看具體情況而定，一般情況下是這樣的。150.一棵有n個結(jié)點的二叉樹，按層次從上到下，同一層從左到右順序存儲在一維數(shù)組A[1.n]中，則二叉樹中第i個結(jié)點(i從1開始用上述方法編號)的右孩子在數(shù)組A中的位置是()。A、A[2i](2i＜=n)B、A[2i+1](2i+1＜=n)C、A[i-2]D、條件不充分，無法確定答案：D解析：本題目并未明確所給二叉樹的形狀，因此不能根據(jù)第i個結(jié)點在數(shù)組A中的存儲位置確定其右孩子在數(shù)組A中的位置。151.循環(huán)鏈表的主要優(yōu)點是()。A、不再需要頭指針B、已知某個結(jié)點的位置后，能很容易找到它的直接前驅(qū)結(jié)點C、在進行刪除操作后，能保證鏈表不斷開D、從表中任一結(jié)點出發(fā)都能遍歷整個鏈表答案：D解析：A項，頭指針不能省略，因為沒有頭指針就沒有辦法引用該鏈表了；B項，循環(huán)鏈表還是單鏈表，要找到直接前驅(qū)結(jié)點，必須至少循環(huán)遍歷整個鏈表一次才行；C項，無論鏈表是不是循環(huán)的，都能保證在刪除時鏈表不斷開；D項，因為循環(huán)鏈表首尾相接，形成一個環(huán)，從循環(huán)鏈表中任何一個結(jié)點開始都能遍歷整個鏈表。152.下列說法不正確的是()。A、圖的遍歷是從給定的源點出發(fā)每一個頂點僅被訪問一次B、遍歷的基本算法有兩種：深度遍歷和廣度遍歷C、圖的深度遍歷不適用于有向圖D、圖的深度遍歷是一個遞歸過程答案：C解析：圖的遍歷是指從給定圖中任意指定的頂點出發(fā)，按照某種搜索方法沿著圖的邊訪問圖中的所有頂點，便每個丁貞點僅被訪問一次。遍歷的基本算法有兩種：深度遍歷和廠度遍歷。圖的深度遍歷是一個遞歸過程，既適用于無向圖，也適用于有向圖。153.若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用()存儲方式最節(jié)省時間。A、順序表B、雙鏈表C、帶頭結(jié)點的雙循環(huán)鏈表D、單循環(huán)鏈表答案：A解析：在線性表的順序存儲中，可以存取任一指定序號的元素。當插入和刪除運算是在最后操作時，順序表的實現(xiàn)也非常方便。BCD三項都不同時具備這兩個特點。154.對于棧操作數(shù)據(jù)的原則是()。A、先進先出B、后進先出C、后進后出D、不分順序答案：B解析：棧的特點就是后進先出，入棧和出棧的操作只能在棧頇進行.而隊列的特點是先進先出，這兩點容易混淆，要注意區(qū)分。155.設某棵三叉樹中有40個結(jié)點，則該三叉樹的最小高度為()A、6B、4C、5D、3答案：B解析：樹高度最小時即為每一層都是滿的，只有最下層不滿的情況是樹的高度最小的情況。156.由圈權(quán)值為9.2.5.7的四個葉子結(jié)點構(gòu)造一顆哈夫曼樹，該樹的帶權(quán)路徑長度為()。A、23B、37C、44D、46答案：C解析：157.已知二叉樹的前序序列為ABCDEFG，中序序列為DBCAFEG，則后序序列為()。A、DCBAFGEB、DCBFGEAC、DCBFEGAD、DCBGFEA答案：B解析：本題考查的是二叉樹的遍歷過程。在本題中，由于前序遍歷首先訪問的是根結(jié)點，所以根結(jié)點是A，又由于后序遍歷最后訪問的是根結(jié)點，所以排除選項A；根據(jù)中序序列知道，DBC是左子樹的結(jié)點，F(xiàn)EG是右子樹的結(jié)點。158.設n階方陣是一個上三角矩陣，則需存儲的元素個數(shù)為()。A、nB、n×nC、n×n/2D、n(n+1)/2答案：D解析：在上三角矩陣中，第一行有1個元素，第二行有2個元素，…，第n行有n個元素，則共n(n+1)/2個。159.設有13個值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有()個結(jié)點。A、13B、12C、26D、25答案：D解析：哈夫曼樹的特點：具有n個葉子結(jié)點的哈夫曼樹共有2×n-1個結(jié)點。160.下面術(shù)語中，與數(shù)據(jù)的存儲結(jié)構(gòu)無關的是()。A、循環(huán)隊列B、棧C、散列表D、單鏈表答案：B解析：只有棧是邏輯結(jié)構(gòu)，其他選項都是存儲結(jié)構(gòu)(或物理結(jié)構(gòu))。161.以下排序方法中，在初始序列已基本有序的情況下，排序效率最高的是()。A、歸并排序B、直接插入排序C、快速排序D、堆排序答案：B解析：直接插入排序?qū)τ诨居行虻男蛄羞M行排序效率最高。162.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進行二分查找，則查找A[3]的比較序列的下標依次為()。A、9，5，3B、9，5，2，3C、1，2，3D、9，4，2，3答案：D解析：二分查找的基本思想是將n個元素分成大致相等的兩部分，取中間位置的節(jié)點值與關鍵字做比較，如果相等，則查找成功；如果關鍵字的值小于中間節(jié)點，則只要在數(shù)組的左半部分繼續(xù)搜索，重復與中間值進行比較，直至查找成功或失敗；如果關鍵字大于中間值，則只要在數(shù)組的右半部搜索即可。163.設二叉排序樹上有n個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時間復雜度為()。A、AB、BC、CD、D答案：D解析：164.下列排序算法中，在待排序數(shù)據(jù)已有序時，花費時間反而最多的排序是()。A、冒泡B、希爾C、快速D、堆答案：C解析：在待排序數(shù)據(jù)已有序時，快速排序會退化為冒泡排序，時間復雜度為O(n)。165.已知有向圖G=(V，A)，其中V={a，b，C，d，e}，A={＜a，b＞，＜a，c＞，＜d，c＞，＜d，e＞，＜b，e＞，＜c，e＞}，對該圖進行拓撲排序，下面序列中()不是拓撲排序A、a，d，c，b，eB、d，a，b，c，eC、a，b，d，c，eD、a，b，c，d，e答案：D解析：166.線性表的靜態(tài)鏈表存儲結(jié)構(gòu)與順序存儲結(jié)構(gòu)相比優(yōu)點是()。A、所有的操作算法實現(xiàn)簡單B、便于隨機存取C、便于插入與刪除D、便于利用零散的存儲器空間答案：C解析：基礎題。靜態(tài)鏈表具有鏈表的插入和刪除方便的優(yōu)點，也不需要移動較多的元素。167.將10個元素散列到100000個單元的哈希表中，()產(chǎn)生沖突？A、一定會B、一定不會C、仍可能會D、可能不會答案：C解析：168.設某完全無向圖中有n個頂點，則該完全無向圖中有()條邊。A、n(n-1)/2B、n(n-1)C、n+1D、n答案：A解析：因為無向圖的邊是沒有方向的，所以完全無向圖有n(n-l)/2條邊。169.若一個棧以向量V[1.n]存儲，初始棧頂指針top為n+1，則下面x進棧的正確操作是()。A、top=top+1；V[top]=xB、V[top]=x；top=top+1C、top=top-1；V[top]=xD、V[top]=x；top=top-1答案：C解析：棧是運算受限的線性表，只允許在棧頂進行插入和刪除操作。本題中棧頂指針為n+1，該數(shù)組將棧頂放在了下標大的一端，所以在進行人棧操作時top指針應該進行減1操作。通常元素進棧的操作為：先移動棧頂指針后存入元素。170.A、AB、BC、CD、D答案：C解析：171.下列序列中，滿足堆定義的是()。A、(100，86，48，73，35，39，42，57，66，21)B、(12，70，33，65，24，56，48，92，86，33)C、(103，97，56，38，66，23，42，12，30，52，6，26)D、(5，56，20，23，40，38，29，61，36，76，28，100)答案：A解析：n個元素的序列{K1，K2，…，Kn}當且僅當滿足下面關系：Ki＜=K2i和Ki＜=K(2i+1)或者Ki＞=K2i和Ki＞K(2i+1)時，稱之為堆。B項，其構(gòu)成的是小頂堆，70和24之間不滿足小頂堆性質(zhì)；C項，其構(gòu)成的是大頂堆，23和26不滿足大頂堆性質(zhì)；D項，其構(gòu)成的是小頂堆，56和23，40和28不滿足小頂堆性質(zhì)。A項對應的是大頂堆，滿足大頂堆性質(zhì)。172.適用于折半查找的表的存儲方式及元素排列要求為()。A、鏈接方式存儲，元素無序B、鏈接方式存儲，元素有序C、順序方式存儲，元素無序D、順序方式存儲，元素有序答案：D解析：折半查找的線性表中的結(jié)點必須已按關鍵字值的遞增或遞減順序排列，而且為順序存儲。173.二路歸并排序的時間復雜度為()。A、AB、BC、CD、D答案：C解析：174.一棵完全二叉樹上有1001個結(jié)點.其中葉子結(jié)點的個數(shù)是()。A、250B、500C、505D、501答案：D解析：175.散列技術(shù)中的沖突指的是()。A、兩個元素具有相同的序號B、數(shù)據(jù)元素過多C、兩個元素的鍵值不同，而其他屬性相同D、不同鍵值的元素對應于相同的存儲地址答案：D解析：散列技術(shù)中的沖突指的是不同鍵值的元素對應于相同的存儲地址。176.對任意7個關鍵字進行排序，至少要進行()次關鍵字之間的兩兩比較。A、13B、14C、15D、16答案：C解析：177.下列的敘述不正確的個數(shù)是()。(1)9階B-樹，除根以外的任一結(jié)點的關鍵字個數(shù)不少于4(2)理想情況下，在散列表中查找一個元素的時間復雜度為0(1)(3)在采用線性探測法處理沖突的散列表中，所有同義詞在表中相鄰(4)在索引順序表的查找中，對索引表既可以采用順序查找方法，也可采用=分查找方法A、1B、2C、3D、4答案：A解析：如果發(fā)生多次沖突，則同義詞在表中就不會相鄰，因此(3)是錯誤的，其它正確。178.A、AB、BC、CD、D答案：A解析：179.與單鏈表相比，雙鏈表的優(yōu)點之一是()。A、插入、刪除操作更簡單B、可以進行隨機訪問C、可以省略表頭指針或表尾指針D、訪問前后相鄰結(jié)點更靈活答案：D解析：對于插入、刪除操作單鏈表更簡單，因為需要改動的指針域少，而隨機訪問是順序表的特點。無論是單鏈表還是雙鏈表都要有表頭指針或表尾指針，在雙鏈表中可以訪問任一結(jié)點的前后相鄰結(jié)點，而單鏈表中只能訪問任意結(jié)點的后繼結(jié)點。180.數(shù)據(jù)的存儲結(jié)構(gòu)是指()。A、數(shù)組類型B、指針類型C、數(shù)據(jù)之間的邏輯關系D、數(shù)據(jù)之間的物理關系答案：D解析：數(shù)據(jù)的存儲結(jié)構(gòu)就是物理結(jié)構(gòu)，指數(shù)據(jù)之間的物理關系。181.下列敘述中，不符合m階B樹定義要求的是()。A、根節(jié)點最多有m棵子樹B、所有葉結(jié)點都在同一層上C、各結(jié)點內(nèi)關鍵字均升序或降序排列D、葉結(jié)點之間通過指針鏈接答案：D解析：B樹的定義。182.設某哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有()個葉子結(jié)點。A、101B、100C、99D、102答案：B解析：在哈夫曼樹中的結(jié)點只有兩種，一種是度為零的結(jié)點，另一種是度為1的結(jié)點。183.下面關于工程計劃的AOE網(wǎng)的敘述中，不正確的是()。A、某些關鍵活動若提前完成，那么整個工程將會提前完B、關鍵活動不按期完成就會影響整個工程的完成時間C、任何一個關鍵活動提前完成，那么整個工程將會提前完成D、所有的關鍵活動都提前完成，那么整個工程將會提前完成答案：C解析：AOE網(wǎng)中的關鍵路徑可能不止一條，如果某一個關鍵活動提前完成，還不能提前整個工程，則必須同時提高在幾條關鍵路徑上的關鍵活動。184.若將數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素稱為結(jié)點，則一般沒有開始結(jié)點和終端結(jié)點的數(shù)據(jù)結(jié)構(gòu)是()。A、樹B、圖C、多維數(shù)組D、線性表答案：B解析：圖G由兩個集合V和E組成，記為G=(V，E)。其中V是頂點的有限集合，記為V((G)；E是連接V中兩個不同頂點(頂點對)的邊的有限集合，記為E(G)。圖是由有限集合的頂點和邊構(gòu)成，沒有開始結(jié)點和終端結(jié)點。185.在線索二叉樹中，一個結(jié)點是葉子結(jié)點的充要條件為()。A、左、右線索標志均為0B、左、右線索標志均為1C、左線索標志為0，右線索標志為1D、左線索標志為1，右線索標志為O答案：A解析：一個結(jié)點是葉子結(jié)點的充要條件是沒有左孩子，并且沒有右孩子。186.設n、m為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，n在m前的條件是()。A、n在m右方B、n是m祖先C、n在m左方D、n是m子孫答案：C解析：中序遍歷時，先訪問左子樹，再訪問根結(jié)點。n在m前，則n必須在m的左子樹中。187.二叉排序樹中左子樹上所有結(jié)點的值均()根結(jié)點的值。A、＜B、=C、＞D、！=答案：A解析：二叉排序樹的左子樹的結(jié)點的值全部小于根結(jié)點的值，并且根結(jié)點的值小于右子樹左右結(jié)點的值。188.下列與數(shù)據(jù)元素有關的敘述中，哪一項是不正確的()。A、數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體B、數(shù)據(jù)元素是由獨立含義的數(shù)據(jù)最小單位C、數(shù)據(jù)元素又稱為節(jié)點D、數(shù)據(jù)元素又稱為記錄答案：B解析：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體。有些情況下也把數(shù)據(jù)元素稱為節(jié)點、記錄、表目等。一個數(shù)據(jù)元素可由一個或多個數(shù)據(jù)項組成，數(shù)據(jù)項是由獨立含義的數(shù)據(jù)最小單位。189.設有一組記錄的關鍵字為{19，14，23，1，68，20，84，27，55，11，10，79}，用鏈地址法構(gòu)造散列表，散列函數(shù)為H(key)=keyMOD13，散列地址為1的鏈中有()個記錄。A、1B、2C、3D、4答案：D解析：由散列函數(shù)H(key)=keyMOD13計算每個記錄的散列地址，散列地址為1的關鍵字有14，1，27，79，共4個記錄。190.設指針變量p指向單鏈表中結(jié)點A，若刪除單鏈表中結(jié)點A，則需要修改指針的操作序列為()。A、q=p-＞next；p-＞data=q-＞data；p-＞next=q-＞next；free(q)；B、q=p-＞next；p-＞data=q-＞data；free(q)；C、q=p-＞next；p-＞next=q-＞next；free(q)；D、q=p-＞next；q-＞data=p-＞data；p-＞next=q-＞next；free(q)；答案：A解析：應先使指針q指向結(jié)點A之后的結(jié)點，以防鏈表斷裂，然后刪除結(jié)點q，最后將刪除的結(jié)點q的存儲空間釋放。191.下列說法正確的是()。A、任何有向網(wǎng)絡(AOV-網(wǎng))拓撲排序的結(jié)果是唯一的B、有回路的圖不能進行拓撲排序C、在AOE網(wǎng)中一定只有一條關鍵路徑D、一個正常的AOE網(wǎng)中只能有一個源點、一小匯點和一條關鍵路徑答案：B解析：拓撲排序的結(jié)果不一定是唯一的；在AOE網(wǎng)中，關鍵路徑不止一條。192.下列排序方法中，屬于不穩(wěn)定的排序方法的是()。A、直接插入排序法B、冒泡排序法C、基數(shù)排序法D、堆排序法答案：D解析：本題選項所述的四種排序方法中，只有堆排序是不穩(wěn)定的。193.假設執(zhí)行語句S的時間為0(1)，則執(zhí)行下列程序段的時間為()。for(i=l;k=n;it+)for(j=l;jA、0(n)B、0(n^2)C、O(n×i)D、0(n+1)答案：B解析：觀察可知，程序段S的執(zhí)行頻度為T(n)=n^2，得時間復雜度T(n)=O(n^2)。194.設循環(huán)隊列的存儲空間為Q(1：30)，初始狀態(tài)front=rear=30，先經(jīng)過一系列入隊和退隊運算后，front=10，rear=10，則循環(huán)隊列中的元素個數(shù)為()。A、30B、0C、29D、0或30答案：D解析：當frontrear時，循環(huán)隊列中的元素個數(shù)為N-front+rear(N為循環(huán)隊列容量)。當front=rear時，循環(huán)隊列中的元素個數(shù)可能為空，也可能為滿。195.采用分塊查找時.若線性表中共有625個元素，查找每個元素的概率相同，假設采用順序查找來確定結(jié)點所在的塊時，每塊應分()個結(jié)點最佳。A、10B、25C、6D、625答案：B解析：196.判定一個棧ST(最多元素為m0)為滿的條件是()。A、ST-＞top=m0-1B、ST-＞top=0C、ST-＞top＜＞m0D、ST-＞top＜＞0答案：A解析：如果一個棧的棧頂指針為m0-1，則該棧為滿。197.下面關于圖的存儲的敘述中，正確的是()。A、用鄰接矩陣法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關，而與邊數(shù)無關B、用鄰接矩陣法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關，而與結(jié)點個數(shù)無關C、用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關，而與邊數(shù)無關D、用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關，而與結(jié)點個數(shù)無關答案：A解析：對于n個節(jié)點的圖來說，用鄰接矩陣法存儲圖，需要n×n個存儲單元，只與圖中結(jié)點個數(shù)有關，與邊數(shù)無關；用鄰接表法存儲圖，與圖的結(jié)點個數(shù)和邊數(shù)都有關。198.設某有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點，則該圖中有()條有向邊。A、n-1B、nC、m-1D、m答案：B解析：鄰接表的表頭結(jié)點個數(shù)即為圖中結(jié)點的個數(shù)。199.A、AB、BC、CD、D答案：D解析：考查雙鏈表中插入操作，要注意保存后繼節(jié)點。200.占用的額外空間的空間復雜度為0(1)的排序算法是()。A、堆排序算法B、歸并排序算法C、快速排序算法D、以上答案都不對答案：A解析：歸并排序中，由于每一趟都要一個TR數(shù)組來復制，因此需要與待排記錄等量的輔助空間O(n)；而快速排序中的遞歸所耗費的?？臻g最好情況下也要O(logn)；堆排序僅在交換是需要一個記錄的輔助空間。201.()不是算法的基本特性。A、可行性B、長度有限C、在規(guī)定的時間內(nèi)完成D、確定性答案：B解析：算法的5個重要特性：①確定性；②有窮性；③可行性；④輸入；⑤輸出。C項指的是有窮性，而有窮性并不是指長度有限，而是指執(zhí)行的時間是有限的。202.G是一個非連通無向圖，共有28條邊，則該圖至少有()個頂點。A、8B、9C、6D、7答案：B解析：n個頂點的無向圖中，邊數(shù)e≤n(n-l)/2，將e=28代入，有n≥8，現(xiàn)已知無向圖非連通，則n=9。203.某高度為k的完全二叉樹中，所含葉子結(jié)點的個數(shù)最少為()。A、AB、BC、CD、D答案：C解析：204.簡單無向圖的鄰接矩陣是對稱的，可以對其進行壓縮存儲。若無向圖G有n個結(jié)