事業(yè)單位招錄計(jì)算機(jī)專業(yè)知識(shí)（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷1

事業(yè)單位招錄計(jì)算機(jī)專業(yè)知識(shí)（數(shù)據(jù)結(jié)構(gòu)與算法）模擬試卷1一、單項(xiàng)選擇題(本題共24題，每題1.0分，共24分。)1、雙向鏈表中有兩個(gè)指針域llink和rlink，分別指向前驅(qū)和后繼，設(shè)p指向表中的一個(gè)結(jié)點(diǎn)，q指向一待插入結(jié)點(diǎn)，現(xiàn)要求在p前插入q，則正確的插入為()。A、p→llinkB、q→llink→—＞＜—p→llink；p—＞llink—＞dink—＞＜—q；q—＞llink—＞＜—p—＞llinkC、q→rlink→dink—－＞＜—q；p—＞rlink—＞＜q；p—＞llink—＞rlink—＞＜—p；D、p→link→rlink—－＞＜—q；q—＞rlink—＞＜—p；q—＞llink—＞＜—p—＞llink；p—＞1link—＞＜—q標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：p→llink→rlink＝q；q→rlink＝p；q→link＝p→llink；p→link＝q。2、假設(shè)執(zhí)行語(yǔ)句S的時(shí)間為0(1)，則執(zhí)行下列程序段的時(shí)間為()。for(i＝1；i＜＝n；i＋＋)for(j＝1；j＜＝n；j＋＋)S：A、O(n)B、O(n^2)C、O(n＊i)D、O(n＋1)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：觀察可知，程序段S的執(zhí)行頻度為T(n)＝n＾2，得時(shí)間復(fù)雜度T(n)＝O(n^2)。3、廣義表中的元素可以是原子，也可以是表，因此廣義表的適用存儲(chǔ)結(jié)構(gòu)是()。A、散列表B、靜態(tài)數(shù)組C、動(dòng)態(tài)數(shù)組D、鏈表標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：暫無(wú)解析4、線性表采用鏈接存儲(chǔ)時(shí)，其地址()。A、必須是連續(xù)的B、部分地址必須是連續(xù)的C、一定是不連續(xù)的D、連續(xù)與否均可以標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：線性表的鏈接存儲(chǔ)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。5、在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個(gè)數(shù)為()。A、n－1B、2n－1C、n＋1D、2n＋1標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：本題考查的是二叉樹的鏈?zhǔn)酱鎯?chǔ)。由于在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，值為空的鏈域的個(gè)數(shù)為n＋1個(gè)，而總的鏈域?yàn)?n(在二叉樹中每個(gè)結(jié)點(diǎn)頭2個(gè)鏈域)。所以，非空的鏈域的個(gè)數(shù)為2n－(n＋1)＝n－1。6、下列與數(shù)據(jù)元素有關(guān)的敘述中，哪一項(xiàng)是不正確的()。A、數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體B、數(shù)據(jù)元素是由獨(dú)立含義的數(shù)據(jù)最小單位C、數(shù)據(jù)元素又稱為節(jié)點(diǎn)D、數(shù)據(jù)元素又稱為記錄標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體。有些情況下也把數(shù)據(jù)元素稱為節(jié)點(diǎn)、記錄、表目等。一個(gè)數(shù)據(jù)元素可由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是由獨(dú)立含義的數(shù)據(jù)最小單位。7、在一個(gè)單鏈表中，若p所指的結(jié)點(diǎn)不是最后結(jié)點(diǎn)，則刪除p所指的結(jié)點(diǎn)的后繼結(jié)點(diǎn)的正確操作是()。A、p＝p－＞nextB、p－＞next＝p－＞nextC、p－＞next＝p－＞next－＞nextD、p－＞next＝p標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：本題考查的是單鏈表的刪除操作。在已知鏈表中元素插入或刪除確切位置的情況下，在單鏈表中插入或刪除一個(gè)結(jié)點(diǎn)時(shí)，僅需修改指針而無(wú)須移動(dòng)元素。8、對(duì)于只在表的首尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)是()。A、順序表B、用頭指針表示的單循環(huán)鏈表C、用尾指針表示的單循環(huán)鏈表D、單鏈表標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：本題考查的是線性表的插入與刪除操作。當(dāng)線性表用尾指針表示的單循環(huán)鏈表存儲(chǔ)時(shí)，很容易找到線性表的首、尾元素。此時(shí)，尾指針的后繼即是線性表的首端。9、鏈表不具有的特點(diǎn)是()。A、不必事先估計(jì)存儲(chǔ)空間B、可隨機(jī)訪問(wèn)任一元素C、插入刪除不需要移動(dòng)元素D、所需空間與線性表長(zhǎng)度成正比標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：鏈表采用的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它克服了順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：①它的結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng)和釋放；②它的數(shù)據(jù)元素的邏輯次序靠結(jié)點(diǎn)的指針來(lái)指示，不需要移動(dòng)數(shù)據(jù)元素。但是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也有不足之處：①每個(gè)結(jié)點(diǎn)中的指針域需額外占用存儲(chǔ)空間；②鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種非隨機(jī)存儲(chǔ)結(jié)構(gòu)。10、鏈表不具有的特點(diǎn)是()。A、可隨機(jī)訪問(wèn)任意元素B、不必事先估計(jì)存儲(chǔ)空間C、插入數(shù)據(jù)元素時(shí)不需要移動(dòng)數(shù)據(jù)元素D、刪除數(shù)據(jù)元素時(shí)不需要移動(dòng)數(shù)據(jù)元素標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：順序鏈表不可以隨機(jī)訪問(wèn)任意元素。11、在向下生成的堆棧中，如果入棧指令PUSHX的操作定義為：S←(SP)＋1，M(SP)←M(X)，則出棧指令POPX應(yīng)定義為()。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標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：入棧是先定位棧頂指針然后存儲(chǔ)數(shù)據(jù)，出棧是先出數(shù)據(jù)，然后再定位棧頂指針。12、設(shè)一個(gè)棧的輸入序列是1、2、3、4、5，則下列序列中，是棧的合法輸出序列的是()。A、51234B、45123C、43125D、32154標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：棧的進(jìn)出原則是先進(jìn)后出原則，要不就是先進(jìn)先出原則。A選項(xiàng)中5最先出，說(shuō)明1234都在棧里，這樣說(shuō)明1是在棧低，則先不出來(lái)。BD的原因一樣，所以答案選擇D。13、對(duì)于長(zhǎng)度為m(m＞1)的指定序列，通過(guò)初始為空的一個(gè)棧、一個(gè)隊(duì)列后，錯(cuò)誤的敘述是()。A、入棧序列與出棧序列關(guān)系為1：1，而入隊(duì)序列與出隊(duì)序列關(guān)系是1：n(n≥1)B、若入棧和入隊(duì)的序列相同，則出棧序列和出隊(duì)序列可以互為逆序C、入隊(duì)序列與出隊(duì)序列關(guān)系為1：1，而入棧序列與出棧序列關(guān)系是1：n(n≥1)D、若入棧和入隊(duì)的序列相同，則出棧序列和出隊(duì)序列可能相同標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：隊(duì)列的元素按特點(diǎn)是先進(jìn)先出。對(duì)于隊(duì)列，元素的進(jìn)入次序和出隊(duì)的次序相同，例如，入隊(duì)的序列為a、b、c，則出隊(duì)的序列也為a、b、c。對(duì)于棧則不同，棧的運(yùn)算特點(diǎn)是后進(jìn)先出。若入棧序列為a、b、c，則出棧序列可能為a、b、c，a、c、b，b、a、c，b、c、a或者c、b、a，而c、a、b則不行，因此，入棧序列與出棧序列關(guān)系為1：1，而入隊(duì)序列與出隊(duì)序列關(guān)系為1：n(n≥1)。14、當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定top＝n表示棧空，則向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)該執(zhí)行下列哪個(gè)語(yǔ)句修改的top指針()。A、top＋＋1B、top－－C、top＝0D、top標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：暫無(wú)解析15、設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5和e6依次通過(guò)棧S，1個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e2，e4，e3，e6，e5，e1，則棧S的容量至少應(yīng)該是()。A、6B、4C、3D、2標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：根據(jù)棧的性質(zhì)(LIFO)得，e2出棧前，棧中存有e1和e2兩個(gè)元素，e4出棧前，棧中存有e1、e3和e43個(gè)元素，e4和e3出棧以后，e5和e6入棧，棧中同樣存在e1、e5和e63個(gè)元素，然后3個(gè)元素依次出棧，所以棧的容量至少應(yīng)該為3。16、假設(shè)以S和X分別表示進(jìn)棧和出棧操作，則對(duì)輸入序列a，B，c，d，E進(jìn)行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為()。A、B，c，E，d，aB、B，E，e，a，dC、E，c，B，d，aD、c，E，B，a，d標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：a，B進(jìn)棧(SS)，B出棧(X)，輸出“B”，c進(jìn)棧(S)，c出棧(X)，輸出“c”，d，E進(jìn)棧(SS)，E，d，a出棧(XXX)，輸出“E，d，a”，所以結(jié)果為B，c，E，d，a。17、若一個(gè)棧的輸入序列是1，2，3，…，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是()。A、不確定B、n－iC、n－i－1D、n－i＋1標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：此時(shí)，輸出序列一定是輸入序列的逆序，故第i個(gè)輸出元素為n－i＋1。18、以下哪一個(gè)不是棧的基本運(yùn)算()。A、刪除棧頂元素B、刪除棧底元素C、判斷棧是否為空D、將棧置為空棧標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：棧的基本運(yùn)算有入棧、出棧(刪除棧頂元素)、初始化、置空、判斷是否為空或滿、提取棧頂元素等，對(duì)棧元素的操作都是在棧頂進(jìn)行的。19、若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針top為n＋1，則下面x進(jìn)棧的正確操作是()。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標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：棧是運(yùn)算受限的線性表，只允許在棧頂進(jìn)行插入和刪除操作。本題中棧頂指針為n+1，該數(shù)組將棧頂放在了下標(biāo)大的一端，所以在進(jìn)行入棧操作時(shí)top指針應(yīng)該進(jìn)行減1操作。通常元素進(jìn)棧的操作為：先移動(dòng)棧頂指針后存人元素。20、單向鏈表中往往含有一個(gè)頭結(jié)點(diǎn)。該結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)元素，一般令鏈表的頭指針指向該結(jié)點(diǎn)，而該結(jié)點(diǎn)指針域的值為第一個(gè)元素結(jié)點(diǎn)的指針。以下關(guān)于單鏈表頭結(jié)點(diǎn)的敘述中，錯(cuò)誤的是()。A、若在頭結(jié)點(diǎn)中存入鏈表長(zhǎng)度值，則求鏈表長(zhǎng)度運(yùn)算的時(shí)間復(fù)雜度為O(1)B、在鏈表的任何一個(gè)元素前后進(jìn)行插入和刪除操作可用一致的方式進(jìn)行處理C、加入頭結(jié)點(diǎn)后，在鏈表中進(jìn)行查找運(yùn)算的時(shí)間復(fù)雜度為O(1)D、加入頭結(jié)點(diǎn)后，代表鏈表的頭指針不因?yàn)殒湵頌榭斩淖儤?biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在鏈表中加入頭結(jié)點(diǎn)后，查找表中某一元素仍然要從頭指針出發(fā)，順序找到目標(biāo)元素或失敗時(shí)找到表尾為止，時(shí)間復(fù)雜度與表長(zhǎng)成正比。故D項(xiàng)錯(cuò)誤。21、Hash表是用于數(shù)據(jù)存儲(chǔ)的一種有效的數(shù)據(jù)結(jié)構(gòu)，Hash表的查找復(fù)雜度依賴于Hash值算法的有效性，在最好的情況下，Hash表的查找復(fù)雜度為()。A、O(nlogn)B、O(logn)C、O(n)D、O(1)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：O(1)，哈希表是通過(guò)計(jì)算hashcode來(lái)定位元素位置，所以只需一次即可。22、設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1：30)，初始狀態(tài)front＝rear＝30，先經(jīng)過(guò)一系列入隊(duì)和退隊(duì)運(yùn)算后，front＝10，rear＝10，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為()。A、30B、0C、29D、0或30標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：當(dāng)frontrear時(shí)，循環(huán)隊(duì)列中的元素個(gè)數(shù)為N－front＋rear(N為循環(huán)隊(duì)列容量)。當(dāng)front＝rear時(shí)，循環(huán)隊(duì)列中的元素個(gè)數(shù)可能為空，也可能為滿。23、若一個(gè)程序語(yǔ)言可以提供鏈表的定義和運(yùn)算，則其運(yùn)行時(shí)的()。A、數(shù)據(jù)空間必須采用堆存儲(chǔ)分配策略B、指令空間需要采用棧結(jié)構(gòu)C、指令代碼必須放入堆區(qū)D、數(shù)據(jù)空間適合采用靜態(tài)存儲(chǔ)分配策略標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：鏈表中的結(jié)點(diǎn)空間需要程序員根據(jù)需要申請(qǐng)和釋放，因此，數(shù)據(jù)空間應(yīng)采用堆存儲(chǔ)分配策略。24、棧和隊(duì)列的共同點(diǎn)是()。A、都是先進(jìn)先出B、都是先進(jìn)后出C、只允許在端點(diǎn)處插入和刪除元素D、沒(méi)有共同點(diǎn)標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：棧和隊(duì)列都是運(yùn)算受限的線性表，只允許在表端點(diǎn)處進(jìn)行操作。二、簡(jiǎn)答題(本題共9題，每題1.0分，共9分。)25、設(shè)計(jì)將帶表頭的鏈表逆置的算法。標(biāo)準(zhǔn)答案：設(shè)單循環(huán)鏈表的頭指針為head，類型為L(zhǎng)inkList。逆置時(shí)需將每一個(gè)結(jié)點(diǎn)的指針域進(jìn)行修改，使其原前驅(qū)結(jié)點(diǎn)成為后繼。如果更改Q結(jié)點(diǎn)的指針域時(shí)，設(shè)S指向其原前驅(qū)結(jié)點(diǎn)，p指向其原后驅(qū)結(jié)點(diǎn)，則只需進(jìn)行Q－＞next＝S操作即可。算法描述如下：voidinvert(LinkList＊head){／／逆置head指針?biāo)赶虻膯窝h(huán)鏈表Linklist＊p，＊Q，＊S；Q＝head；p＝head－＞next；while(p!＝head)／／當(dāng)表不為空時(shí)，逐個(gè)結(jié)點(diǎn)逆置{S＝Q；Q＝p；p＝p－＞next；Q－＞next＝S；}p－＞next＝Q；}知識(shí)點(diǎn)解析：暫無(wú)解析26、閱讀下面的算法：LinkListmynote(LinkListL){／／L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L＆＆L－＞next){Q＝L；L＝L－＞next；p＝L；S1：while(p－＞next)；p＝p－＞next；S2：p－＞next＝Q；Q－＞next＝NULL；}returnL；}請(qǐng)回答下列問(wèn)題：(1)說(shuō)明語(yǔ)句S1的功能。(2)說(shuō)明語(yǔ)句S2的功能。(3)設(shè)鏈表表示的線性表為(a1，a2，…，an)，寫出算法執(zhí)行語(yǔ)句S2后的返回值所表示的線性表。標(biāo)準(zhǔn)答案：(1)查詢鏈表的尾結(jié)點(diǎn)。(2)將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)。(3)返回的線性表為(a2，a3，…，an，a1)。知識(shí)點(diǎn)解析：暫無(wú)解析27、線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問(wèn)：(1)如果有n個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)?為什么?(2)若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)?為什么?標(biāo)準(zhǔn)答案：(1)選鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它可動(dòng)態(tài)申請(qǐng)內(nèi)存空間，不受表長(zhǎng)度(即表中元素個(gè)數(shù))的影響，插入、刪除時(shí)間復(fù)雜度為O。(2)選順序存儲(chǔ)結(jié)構(gòu)。順序表可以隨機(jī)存取，時(shí)間復(fù)雜度為O。知識(shí)點(diǎn)解析：暫無(wú)解析28、試敘述頭結(jié)點(diǎn)、首元結(jié)點(diǎn)、頭指針這三個(gè)概念的區(qū)別。標(biāo)準(zhǔn)答案：在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點(diǎn)則是鏈表的頭結(jié)點(diǎn)的指針，頭指針具有標(biāo)識(shí)作用，故常用頭指針冠以鏈表的名字。頭結(jié)點(diǎn)是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無(wú)意義(當(dāng)然有些情況下也可存放鏈表的長(zhǎng)度，用做監(jiān)視哨等等)，有頭結(jié)點(diǎn)后，對(duì)在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一結(jié)點(diǎn)，其操作與其它結(jié)點(diǎn)的操作統(tǒng)一。而且無(wú)論鏈表是否為空，頭指針均不為空。首元結(jié)點(diǎn)也就是第一元素結(jié)點(diǎn)，它是頭結(jié)點(diǎn)后邊的第一個(gè)結(jié)點(diǎn)。知識(shí)點(diǎn)解析：暫無(wú)解析29、有線性表(a1，a2，…，an))，采用單鏈表存儲(chǔ)，頭指針為H，每個(gè)結(jié)點(diǎn)中存放線性表中一個(gè)元素，現(xiàn)查找某個(gè)元素值等于X的結(jié)點(diǎn)。分別寫出下面三種情況的查找語(yǔ)句。要求時(shí)間盡量少。(1)線性表中元素?zé)o序。(2)線性表中元素按遞增有序。(3)線性表中元素按遞減有序。標(biāo)準(zhǔn)答案：(1)while(p!＝null&&p－＞data!＝X)p＝p－＞next；if(p＝＝null)return(null)；／／查找失敗elsereturn(p)；＝查找成功(2)while(p!＝nuU＆＆p－＞data＜X)p＝p－＞ext，if(p＝＝null‖p－＞data＞X)return(null)；／／查找失敗elsereturn(p)；(3)while(p!＝null＆＆p－＞data＞X)p＝p－＞next；if(p)＝＝null‖p－＞data＜X)return(null)；／／查找失敗elsereturn(p)；／／查找成功知識(shí)點(diǎn)解析：暫無(wú)解析30、線性表的兩種存儲(chǔ)結(jié)構(gòu)各有哪些優(yōu)缺點(diǎn)?標(biāo)準(zhǔn)答案：線性表具有兩種存儲(chǔ)結(jié)構(gòu)，即順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。線性表的順序存儲(chǔ)結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時(shí)將會(huì)引起元素的大量移動(dòng)，因而降低效率。在鏈接存儲(chǔ)結(jié)構(gòu)中內(nèi)存采用動(dòng)態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲(chǔ)方便，但結(jié)點(diǎn)的插入、刪除操作較簡(jiǎn)單。知識(shí)點(diǎn)解析：暫無(wú)解析31、在數(shù)據(jù)結(jié)構(gòu)中，如果元素的進(jìn)棧序列為6個(gè)整數(shù)1，2，3，4，5，6，通過(guò)棧操作能否得到以下兩個(gè)序列：4，3，5，6，1，2和1，3，5，4，2，6，如果不能則說(shuō)明理由，如果能夠也說(shuō)明理由。標(biāo)準(zhǔn)答案：按照?！昂筮M(jìn)先出”原則，對(duì)于序列(4，3，5，6，1，2)：1進(jìn)棧、2進(jìn)棧、3進(jìn)棧、4進(jìn)棧、4出棧、3出棧、5進(jìn)棧、5出棧、6進(jìn)棧、6出棧，2出棧、1出棧，得到的序列為(4，3，5，6，2，1)，因此得不到此序列。對(duì)于序列(1，3，5，4，2，6)：1進(jìn)棧、1出棧、2進(jìn)棧、3進(jìn)棧、3出棧、4進(jìn)棧、5進(jìn)棧、5出棧、4出棧、2出棧、6進(jìn)棧、6出棧，沒(méi)有分后進(jìn)先出原則，可以得到序列(1，3，5，4，2，6)。知識(shí)點(diǎn)解析：暫無(wú)解析32、設(shè)一數(shù)列的輸入順序?yàn)?23456，若采用堆棧結(jié)構(gòu)，并以A和D分別表示入棧和出棧操作，試問(wèn)通過(guò)入出棧操作的合法序列。(1)能否得到輸出順序?yàn)?25641的序列。(2)能否得到輸出順序?yàn)?54623的序列。標(biāo)準(zhǔn)答案：(1)能得到325641。在123依次進(jìn)棧后，3和2出棧，得部分輸出序列32；然后4，5入棧，5出棧，得部分出棧序列325；6入棧并出棧，得部分輸出序列3256；最后退棧，直到?？?。得輸出序列325641。其操作序列為AAADDAADADDD。(2)不能得到輸出順序?yàn)?54623的序列。部分合法操作序列為ADAAAADDAD，得到部分輸出序列1546后，棧中元素為23，3在棧頂，故不可能2先出棧，得不到輸出序列154623。知識(shí)點(diǎn)解析：暫無(wú)解析33、在一個(gè)算法中需要建立多個(gè)堆棧時(shí)可以選用下列三種方案之一，試問(wèn)：這三種方案之間相比較各有什么優(yōu)缺點(diǎn)?(1)分別用多個(gè)順序存儲(chǔ)空間建立多個(gè)獨(dú)立的堆棧。(2)多個(gè)堆棧共享一個(gè)順序存儲(chǔ)空間。(3)分別建立多個(gè)獨(dú)立的鏈接堆棧。標(biāo)準(zhǔn)答案：(1)每個(gè)棧僅用一個(gè)順序存儲(chǔ)空間時(shí)，操作簡(jiǎn)便，但分配存儲(chǔ)空間小了，容易產(chǎn)生溢出，分配空間大了，容易造成浪費(fèi)，各棧不能共享空間。(2)多個(gè)棧共享一個(gè)順序存儲(chǔ)空間，充分利用了存儲(chǔ)空間，只有在整個(gè)存儲(chǔ)空間都用完時(shí)才能產(chǎn)生溢出，其缺點(diǎn)是當(dāng)一個(gè)棧滿時(shí)要向左、右棧查詢有無(wú)空閑單元。如果有，則要移動(dòng)元素和修改相關(guān)的棧底和棧頂指針。當(dāng)接近棧滿時(shí)，查詢空閑單元、移動(dòng)元素和修改棧底棧頂指針的操作頻繁，計(jì)算復(fù)雜并且耗費(fèi)時(shí)間。(3)多個(gè)鏈棧一般不考慮棧的溢出(僅受用戶內(nèi)存空間限制)，缺點(diǎn)是棧中元素要以指針相鏈接，比順序存儲(chǔ)多占用了存儲(chǔ)空間。知識(shí)點(diǎn)解析：暫無(wú)解析一、單項(xiàng)選擇題(本題共24題，每題1.0分，共24分。)34、雙向鏈表中有兩個(gè)指針域llink和rlink，分別指向前驅(qū)和后繼，設(shè)p指向表中的一個(gè)結(jié)點(diǎn)，q指向一待插入結(jié)點(diǎn)，現(xiàn)要求在p前插入q，則正確的插入為()。A、p→llinkB、q→llink→—＞＜—p→llink；p—＞llink—＞dink—＞＜—q；q—＞llink—＞＜—p—＞llinkC、q→rlink→dink—－＞＜—q；p—＞rlink—＞＜q；p—＞llink—＞rlink—＞＜—p；D、p→link→rlink—－＞＜—q；q—＞rlink—＞＜—p；q—＞llink—＞＜—p—＞llink；p—＞1link—＞＜—q標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：p→llink→rlink＝q；q→rlink＝p；q→link＝p→llink；p→link＝q。35、假設(shè)執(zhí)行語(yǔ)句S的時(shí)間為0(1)，則執(zhí)行下列程序段的時(shí)間為()。for(i＝1；i＜＝n；i＋＋)for(j＝1；j＜＝n；j＋＋)S：A、O(n)B、O(n^2)C、O(n＊i)D、O(n＋1)標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：觀察可知，程序段S的執(zhí)行頻度為T(n)＝n＾2，得時(shí)間復(fù)雜度T(n)＝O(n^2)。36、廣義表中的元素可以是原子，也可以是表，因此廣義表的適用存儲(chǔ)結(jié)構(gòu)是()。A、散列表B、靜態(tài)數(shù)組C、動(dòng)態(tài)數(shù)組D、鏈表標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：暫無(wú)解析37、線性表采用鏈接存儲(chǔ)時(shí)，其地址()。A、必須是連續(xù)的B、部分地址必須是連續(xù)的C、一定是不連續(xù)的D、連續(xù)與否均可以標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：線性表的鏈接存儲(chǔ)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以連續(xù)，也可以不連續(xù)，甚至可以零散分布在內(nèi)存中任意位置。38、在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，值為非空的鏈域的個(gè)數(shù)為()。A、n－1B、2n－1C、n＋1D、2n＋1標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：本題考查的是二叉樹的鏈?zhǔn)酱鎯?chǔ)。由于在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，值為空的鏈域的個(gè)數(shù)為n＋1個(gè)，而總的鏈域?yàn)?n(在二叉樹中每個(gè)結(jié)點(diǎn)頭2個(gè)鏈域)。所以，非空的鏈域的個(gè)數(shù)為2n－(n＋1)＝n－1。39、下列與數(shù)據(jù)元素有關(guān)的敘述中，哪一項(xiàng)是不正確的()。A、數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體B、數(shù)據(jù)元素是由獨(dú)立含義的數(shù)據(jù)最小單位C、數(shù)據(jù)元素又稱為節(jié)點(diǎn)D、數(shù)據(jù)元素又稱為記錄標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體。有些情況下也把數(shù)據(jù)元素稱為節(jié)點(diǎn)、記錄、表目等。一個(gè)數(shù)據(jù)元素可由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)是由獨(dú)立含義的數(shù)據(jù)最小單位。40、在一個(gè)單鏈表中，若p所指的結(jié)點(diǎn)不是最后結(jié)點(diǎn)，則刪除p所指的結(jié)點(diǎn)的后繼結(jié)點(diǎn)的正確操作是()。A、p＝p－＞nextB、p－＞next＝p－＞nextC、p－＞next＝p－＞next－＞nextD、p－＞next＝p標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：本題考查的是單鏈表的刪除操作。在已知鏈表中元素插入或刪除確切位置的情況下，在單鏈表中插入或刪除一個(gè)結(jié)點(diǎn)時(shí)，僅需修改指針而無(wú)須移動(dòng)元素。41、對(duì)于只在表的首尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)是()。A、順序表B、用頭指針表示的單循環(huán)鏈表C、用尾指針表示的單循環(huán)鏈表D、單鏈表標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：本題考查的是線性表的插入與刪除操作。當(dāng)線性表用尾指針表示的單循環(huán)鏈表存儲(chǔ)時(shí)，很容易找到線性表的首、尾元素。此時(shí)，尾指針的后繼即是線性表的首端。42、鏈表不具有的特點(diǎn)是()。A、不必事先估計(jì)存儲(chǔ)空間B、可隨機(jī)訪問(wèn)任一元素C、插入刪除不需要移動(dòng)元素D、所需空間與線性表長(zhǎng)度成正比標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：鏈表采用的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它克服了順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)：①它的結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng)和釋放；②它的數(shù)據(jù)元素的邏輯次序靠結(jié)點(diǎn)的指針來(lái)指示，不需要移動(dòng)數(shù)據(jù)元素。但是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也有不足之處：①每個(gè)結(jié)點(diǎn)中的指針域需額外占用存儲(chǔ)空間；②鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種非隨機(jī)存儲(chǔ)結(jié)構(gòu)。43、鏈表不具有的特點(diǎn)是()。A、可隨機(jī)訪問(wèn)任意元素B、不必事先估計(jì)存儲(chǔ)空間C、插入數(shù)據(jù)元素時(shí)不需要移動(dòng)數(shù)據(jù)元素D、刪除數(shù)據(jù)元素時(shí)不需要移動(dòng)數(shù)據(jù)元素標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：順序鏈表不可以隨機(jī)訪問(wèn)任意元素。44、在向下生成的堆棧中，如果入棧指令PUSHX的操作定義為：S←(SP)＋1，M(SP)←M(X)，則出棧指令POPX應(yīng)定義為()。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標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：入棧是先定位棧頂指針然后存儲(chǔ)數(shù)據(jù)，出棧是先出數(shù)據(jù)，然后再定位棧頂指針。45、設(shè)一個(gè)棧的輸入序列是1、2、3、4、5，則下列序列中，是棧的合法輸出序列的是()。A、51234B、45123C、43125D、32154標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：棧的進(jìn)出原則是先進(jìn)后出原則，要不就是先進(jìn)先出原則。A選項(xiàng)中5最先出，說(shuō)明1234都在棧里，這樣說(shuō)明1是在棧低，則先不出來(lái)。BD的原因一樣，所以答案選擇D。46、對(duì)于長(zhǎng)度為m(m＞1)的指定序列，通過(guò)初始為空的一個(gè)棧、一個(gè)隊(duì)列后，錯(cuò)誤的敘述是()。A、入棧序列與出棧序列關(guān)系為1：1，而入隊(duì)序列與出隊(duì)序列關(guān)系是1：n(n≥1)B、若入棧和入隊(duì)的序列相同，則出棧序列和出隊(duì)序列可以互為逆序C、入隊(duì)序列與出隊(duì)序列關(guān)系為1：1，而入棧序列與出棧序列關(guān)系是1：n(n≥1)D、若入棧和入隊(duì)的序列相同，則出棧序列和出隊(duì)序列可能相同標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：隊(duì)列的元素按特點(diǎn)是先進(jìn)先出。對(duì)于隊(duì)列，元素的進(jìn)入次序和出隊(duì)的次序相同，例如，入隊(duì)的序列為a、b、c，則出隊(duì)的序列也為a、b、c。對(duì)于棧則不同，棧的運(yùn)算特點(diǎn)是后進(jìn)先出。若入棧序列為a、b、c，則出棧序列可能為a、b、c，a、c、b，b、a、c，b、c、a或者c、b、a，而c、a、b則不行，因此，入棧序列與出棧序列關(guān)系為1：1，而入隊(duì)序列與出隊(duì)序列關(guān)系為1：n(n≥1)。47、當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定top＝n表示棧空，則向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)該執(zhí)行下列哪個(gè)語(yǔ)句修改的top指針()。A、top＋＋1B、top－－C、top＝0D、top標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：暫無(wú)解析48、設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5和e6依次通過(guò)棧S，1個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e2，e4，e3，e6，e5，e1，則棧S的容量至少應(yīng)該是()。A、6B、4C、3D、2標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：根據(jù)棧的性質(zhì)(LIFO)得，e2出棧前，棧中存有e1和e2兩個(gè)元素，e4出棧前，棧中存有e1、e3和e43個(gè)元素，e4和e3出棧以后，e5和e6入棧，棧中同樣存在e1、e5和e63個(gè)元素，然后3個(gè)元素依次出棧，所以棧的容量至少應(yīng)該為3。49、假設(shè)以S和X分別表示進(jìn)棧和出棧操作，則對(duì)輸入序列a，B，c，d，E進(jìn)行一系列棧操作SSXSXSSXXX之后，得到的輸出序列為()。A、B，c，E，d，aB、B，E，e，a，dC、E，c，B，d，aD、c，E，B，a，d標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：a，B進(jìn)棧(SS)，B出棧(X)，輸出“B”，c進(jìn)棧(S)，c出棧(X)，輸出“c”，d，E進(jìn)棧(SS)，E，d，a出棧(XXX)，輸出“E，d，a”，所以結(jié)果為B，c，E，d，a。50、若一個(gè)棧的輸入序列是1，2，3，…，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是()。A、不確定B、n－iC、n－i－1D、n－i＋1標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：此時(shí)，輸出序列一定是輸入序列的逆序，故第i個(gè)輸出元素為n－i＋1。51、以下哪一個(gè)不是棧的基本運(yùn)算()。A、刪除棧頂元素B、刪除棧底元素C、判斷棧是否為空D、將棧置為空棧標(biāo)準(zhǔn)答案：B知識(shí)點(diǎn)解析：棧的基本運(yùn)算有入棧、出棧(刪除棧頂元素)、初始化、置空、判斷是否為空或滿、提取棧頂元素等，對(duì)棧元素的操作都是在棧頂進(jìn)行的。52、若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針top為n＋1，則下面x進(jìn)棧的正確操作是()。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標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：棧是運(yùn)算受限的線性表，只允許在棧頂進(jìn)行插入和刪除操作。本題中棧頂指針為n+1，該數(shù)組將棧頂放在了下標(biāo)大的一端，所以在進(jìn)行入棧操作時(shí)top指針應(yīng)該進(jìn)行減1操作。通常元素進(jìn)棧的操作為：先移動(dòng)棧頂指針后存人元素。53、單向鏈表中往往含有一個(gè)頭結(jié)點(diǎn)。該結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)元素，一般令鏈表的頭指針指向該結(jié)點(diǎn)，而該結(jié)點(diǎn)指針域的值為第一個(gè)元素結(jié)點(diǎn)的指針。以下關(guān)于單鏈表頭結(jié)點(diǎn)的敘述中，錯(cuò)誤的是()。A、若在頭結(jié)點(diǎn)中存入鏈表長(zhǎng)度值，則求鏈表長(zhǎng)度運(yùn)算的時(shí)間復(fù)雜度為O(1)B、在鏈表的任何一個(gè)元素前后進(jìn)行插入和刪除操作可用一致的方式進(jìn)行處理C、加入頭結(jié)點(diǎn)后，在鏈表中進(jìn)行查找運(yùn)算的時(shí)間復(fù)雜度為O(1)D、加入頭結(jié)點(diǎn)后，代表鏈表的頭指針不因?yàn)殒湵頌榭斩淖儤?biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：在鏈表中加入頭結(jié)點(diǎn)后，查找表中某一元素仍然要從頭指針出發(fā)，順序找到目標(biāo)元素或失敗時(shí)找到表尾為止，時(shí)間復(fù)雜度與表長(zhǎng)成正比。故D項(xiàng)錯(cuò)誤。54、Hash表是用于數(shù)據(jù)存儲(chǔ)的一種有效的數(shù)據(jù)結(jié)構(gòu)，Hash表的查找復(fù)雜度依賴于Hash值算法的有效性，在最好的情況下，Hash表的查找復(fù)雜度為()。A、O(nlogn)B、O(logn)C、O(n)D、O(1)標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：O(1)，哈希表是通過(guò)計(jì)算hashcode來(lái)定位元素位置，所以只需一次即可。55、設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1：30)，初始狀態(tài)front＝rear＝30，先經(jīng)過(guò)一系列入隊(duì)和退隊(duì)運(yùn)算后，front＝10，rear＝10，則循環(huán)隊(duì)列中的元素個(gè)數(shù)為()。A、30B、0C、29D、0或30標(biāo)準(zhǔn)答案：D知識(shí)點(diǎn)解析：當(dāng)frontrear時(shí)，循環(huán)隊(duì)列中的元素個(gè)數(shù)為N－front＋rear(N為循環(huán)隊(duì)列容量)。當(dāng)front＝rear時(shí)，循環(huán)隊(duì)列中的元素個(gè)數(shù)可能為空，也可能為滿。56、若一個(gè)程序語(yǔ)言可以提供鏈表的定義和運(yùn)算，則其運(yùn)行時(shí)的()。A、數(shù)據(jù)空間必須采用堆存儲(chǔ)分配策略B、指令空間需要采用棧結(jié)構(gòu)C、指令代碼必須放入堆區(qū)D、數(shù)據(jù)空間適合采用靜態(tài)存儲(chǔ)分配策略標(biāo)準(zhǔn)答案：A知識(shí)點(diǎn)解析：鏈表中的結(jié)點(diǎn)空間需要程序員根據(jù)需要申請(qǐng)和釋放，因此，數(shù)據(jù)空間應(yīng)采用堆存儲(chǔ)分配策略。57、棧和隊(duì)列的共同點(diǎn)是()。A、都是先進(jìn)先出B、都是先進(jìn)后出C、只允許在端點(diǎn)處插入和刪除元素D、沒(méi)有共同點(diǎn)標(biāo)準(zhǔn)答案：C知識(shí)點(diǎn)解析：棧和隊(duì)列都是運(yùn)算受限的線性表，只允許在表端點(diǎn)處進(jìn)行操作。二、簡(jiǎn)答題(本題共9題，每題1.0分，共9分。)58、設(shè)計(jì)將帶表頭的鏈表逆置的算法。標(biāo)準(zhǔn)答案：設(shè)單循環(huán)鏈表的頭指針為head，類型為L(zhǎng)inkList。逆置時(shí)需將每一個(gè)結(jié)點(diǎn)的指針域進(jìn)行修改，使其原前驅(qū)結(jié)點(diǎn)成為后繼。如果更改Q結(jié)點(diǎn)的指針域時(shí)，設(shè)S指向其原前驅(qū)結(jié)點(diǎn)，p指向其原后驅(qū)結(jié)點(diǎn)，則只需進(jìn)行Q－＞next＝S操作即可。算法描述如下：voidinvert(LinkList＊head){／／逆置head指針?biāo)赶虻膯窝h(huán)鏈表Linklist＊p，＊Q，＊S；Q＝head；p＝head－＞next；while(p!＝head)／／當(dāng)表不為空時(shí)，逐個(gè)結(jié)點(diǎn)逆置{S＝Q；Q＝p；p＝p－＞next；Q－＞next＝S；}p－＞next＝Q；}知識(shí)點(diǎn)解析：暫無(wú)解析59、閱讀下面的算法：LinkListmynote(LinkListL){／／L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L＆＆L－＞next){Q＝L；L＝L－＞next；p＝L；S1：while(p－＞next)；p＝p－＞next；S2：p－＞next＝Q；Q－＞next＝NULL；}returnL；}請(qǐng)回答下列問(wèn)題：(1)說(shuō)明語(yǔ)句S1的功能。(2)說(shuō)明語(yǔ)句S2的功能。(3)設(shè)鏈表表示的線性表為(a1，a2，…，an)，寫出算法執(zhí)行語(yǔ)句S2后的返回值所表示的線性表。標(biāo)準(zhǔn)答案：(1)查詢鏈表的尾結(jié)點(diǎn)。(2)將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)。(3)返回的線性表為(a2，a3，…，an，a1)。知識(shí)點(diǎn)解析：暫無(wú)解析60、線性表有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表。試問(wèn)：(1)如果有n個(gè)線性表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)?為什么?(2)若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)?為什么?標(biāo)準(zhǔn)答案：(1)選鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它可動(dòng)態(tài)申請(qǐng)內(nèi)存空間，不受表長(zhǎng)度(即表中元素個(gè)數(shù))的影響，插入、刪除時(shí)間復(fù)雜度為O。(2)選順序存儲(chǔ)結(jié)構(gòu)。順序表可以隨機(jī)存取，時(shí)間復(fù)雜度為O。知識(shí)點(diǎn)解析：暫無(wú)解析61、試敘述頭結(jié)點(diǎn)、首元結(jié)點(diǎn)、頭指針這三個(gè)概念的區(qū)別。標(biāo)準(zhǔn)答案：在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點(diǎn)則是鏈表的頭結(jié)點(diǎn)的指針，頭指針具有標(biāo)識(shí)作用，故常用頭指針冠以鏈表的名字。頭結(jié)點(diǎn)是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無(wú)意義(當(dāng)然有些情況下也可存放鏈表的長(zhǎng)度，用做監(jiān)視哨等等)，有頭結(jié)點(diǎn)后，對(duì)在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一結(jié)點(diǎn)，其操作與其它結(jié)點(diǎn)的操作統(tǒng)一。而且無(wú)論鏈表是否為空，頭指針均不為空。首元結(jié)點(diǎn)也就是第一元素結(jié)點(diǎn)，它是頭結(jié)點(diǎn)后邊的第一個(gè)結(jié)點(diǎn)。知識(shí)點(diǎn)解析：暫無(wú)解析62、有線性表(a1，a2，…，an))，采用單鏈表存儲(chǔ)，頭指針為H，每個(gè)結(jié)點(diǎn)中存放線性表中一個(gè)元素，現(xiàn)查找某個(gè)元素值等于X的結(jié)點(diǎn)。分別寫出下面三種情況的查找語(yǔ)句。要求時(shí)間盡量少。(1)線性表中元素?zé)o序。(2)線性表中元素按遞增有序。(3)線性表中元素按遞減有序。標(biāo)準(zhǔn)答案：(1)while(p!＝null&&p－＞data!＝X)p＝p－＞next；if(p＝＝null)return(null)；／／查找