《數(shù)據(jù)結(jié)構(gòu)》期末考試復(fù)習(xí)題庫（含答案）

PAGEPAGE1《數(shù)據(jù)結(jié)構(gòu)》期末考試復(fù)習(xí)題庫（含答案）一、單選題1.根據(jù)使用頻率為5個字符設(shè)計的哈夫曼編碼不可能是()。A、000，001，010，011，1B、0000，0001，001，01，1C、000，001，01，10，11D、00，100，101.110，111答案：D2.單鏈表的存儲密度（)。A、大于1B、等于1C、小于1D、不能確定答案：C3.一個順序表所占用存儲空間的大小與()無關(guān)。A、順序表長度B、順序表中元素的數(shù)據(jù)類型C、順序表中元索各數(shù)據(jù)項的數(shù)據(jù)類型D、順序表各元素的存放次序答案：D4.下列關(guān)于串的敘述中，不正確的是（)。A、串是寧符的有限序列B、空串是由空格構(gòu)成的串C、模式匹配是串的一種重要運算D、串既可以采用順序存儲,也可以采用鏈?zhǔn)酱鎯Υ鸢福築5.隊列的插入操作是在()進(jìn)行。A、隊首B、隊尾C、隊前D、隊后答案：B6.已知一棵完全二叉樹的第6層(設(shè)根為第一層)有8個葉子結(jié)點，則該完全二叉樹的結(jié)點個數(shù)最少是()。A、89B、52C、111D、119答案：A7.順序表和鏈表相比存儲密度較大，這是因為()。A、順序表不需要增加指針來表示元素之間的邏輯關(guān)系B、順序表的存儲空間是預(yù)先分配的C、鏈表中所有結(jié)點的地址是連續(xù)的D、順序表中所有元素的存儲地址是不連續(xù)的答案：A8.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為()兩大類。A、動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B、順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C、線性結(jié)構(gòu)、非線性結(jié)構(gòu)D、初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)答案：C9.順序查找法適合于存儲結(jié)構(gòu)為()的線性表。A、哈希存儲B、順序存儲和鏈?zhǔn)酱鎯、壓縮存儲D、索引存儲答案：B10.被計算機加工的數(shù)據(jù)元素不是孤立的，它們彼此之間一般存在某種關(guān)系，通常把數(shù)據(jù)元素之間的這種關(guān)系稱為()A、規(guī)則B、結(jié)構(gòu)C、集合D、運算答案：B11.以下（）是"abcd321ABCD串的子串。A、abcdB、321ABC、"abcABC"D、“21AB答案：D12.順序表的插入算法中，當(dāng)n個空間已滿時，可再申請增加分配m個空間，若申請失敗，則說明系統(tǒng)沒有()可分配的存儲空間。A、m個B、m個連續(xù)C、n+m個D、n+m個連續(xù)答案：D13.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成()。A、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)答案：C14.沒有向圖G=(VE)，頂點集V=V。V.V-V.E=(<VV2><VV:>,V-V.>V.V.>)，若從頂點V,開始對圖進(jìn)行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個數(shù)是()。A、2B、3C、4D、5答案：D15.由權(quán)值分別為9、2、7、5的4個葉子結(jié)點構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長度為()。A、23B、44C、37D、27答案：B16.比較次數(shù)與排序的初始狀態(tài)無關(guān)的排序方法是()。A、直接插入排序B、起泡排序C、快速排序D、簡單選擇排序答案：D17.在一個具有n個結(jié)點的單鏈表中查找值為m的某結(jié)點若查找成功，則平均比較()個結(jié)點。A、nB、n/2C、(n-1)/2D、(n+1)/2答案：D18.設(shè)有向圖G=(V.E)，頂點集V={V0,V1,V2,V3},E={<V0,V>,<V0,V2><V0,V3><V1,V3>，若從頂點V0,開始對圖進(jìn)行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個數(shù)是()。A、2B、3C、4D、5答案：D19.連續(xù)存儲設(shè)計時，存儲單元的地址()。A、一定連續(xù)B、一定不連續(xù)C、不定連續(xù)D、部分連續(xù)，部分不連續(xù)答案：A20.設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1,e2，e3,e4,e5和e6依次進(jìn)入棧S,一個元素出棧后即進(jìn)入Q，若6個元素出隊的序列是e2,e4,e3,e6,e5和e1,則棧S的容量至少應(yīng)該是()A、2B、3C、4D、6答案：B21.下面（)算法適合用于構(gòu)造―個稠密圖的最小生成樹。A、Dijkstra算法B、Prim算法C、Floyd算法D、Kruskal算法答案：B22.線性表(a,a,-,a,)以鏈接方式存儲時，訪問第i個位置上元素的時間復(fù)雜度為()。A、O(i)B、O(1)C、O(n)D、O(i-1)答案：C23.在一棵度為4的樹T中，若有20個度為4的結(jié)點，10個度為3的結(jié)點，1個度為2的結(jié)點，10個度為1的結(jié)點，則樹T的葉結(jié)點個數(shù)是()。A、41B、32C、113D、122答案：B24.以下不屬于存儲結(jié)構(gòu)的是()。A、棧B、二叉鏈表C、哈希表D、雙向鏈表答案：A25.一個圖中包含有k個連通分星,若按深度優(yōu)先(DFS)搜索方法訪問所有結(jié)點.則必須調(diào)用()次深度優(yōu)先遍歷算法。A、kB、1C、k-1D、k+1答案：A26.若編號1~7的7個數(shù)按照5274163的次序進(jìn)棧進(jìn)棧的中間可以出棧則出棧序列不可能是()。A、5217463B、5714623C、2471536D、5143672答案：A27.用不帶頭結(jié)點的單鏈表存儲隊列時，其隊頭指針指向隊頭結(jié)點其隊尾指針指向隊尾結(jié)點則在進(jìn)行刪除操作時()。A、僅修改隊頭指針B、僅修改隊尾指針C、隊頭、隊尾指針都要修改D、隊頭、隊尾指針都可能要修改答案：D28.兩個棧采用順序存儲結(jié)構(gòu)時，共享同一個數(shù)組空間的好處是()。A、減少存取時間，降低下溢出發(fā)生的機率B、節(jié)省存儲空間，降低上溢出發(fā)生的機率C、減少存取時間，降低上溢出發(fā)生的機率D、節(jié)省存儲空間，降低下溢出發(fā)生的機率答案：B29.某二叉樹中序序列為abcdefg.,后序列動為bafg.則前序序列是()。A、egfacdbB、eacbdgfC、eagcfbdD、其它的都不對答案：B30.冒泡排序最少關(guān)鍵字移動的次數(shù)是()。A、0B、nC、1D、3n(n-1)/2答案：A31.串的長度是指()。A、串中所含不同字母的個數(shù)B、串中所含字符的個數(shù)C、串中所含不同字符的個數(shù)D、串中所含非空格字符的個數(shù)答案：B32.快速排序在()情況下最不利于發(fā)揮其長處。A、排序的數(shù)據(jù)量太大B、排序的數(shù)據(jù)個數(shù)為奇數(shù)C、排序的數(shù)據(jù)中含有多個相同值D、排序的數(shù)據(jù)已基本有序答案：D33.假設(shè)以行序為主序存儲二維數(shù)組A=array[1..100,1.100]，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC[55]=()。A、808B、818C、1010D、1020答案：B34.兩個字符串相等的條件是()。A、串的長度相等B、含有是每個人字符集C、都是非空串D、串的長度相等且對應(yīng)的字符相同答案：D35.數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容不涉及()。A、數(shù)據(jù)如何組織B、數(shù)據(jù)如何存儲C、數(shù)據(jù)運算如何實現(xiàn)D、算法用什么語言來描述答案：D36.將算術(shù)表達(dá)式"1+6/(8-5)*3*轉(zhuǎn)換成后綴表達(dá)式，在求后綴表達(dá)式的過程中，當(dāng)遇到*時，運算數(shù)棧(從棧頂?shù)綏５状涡?為()。A、861B、581C、321D、361答案：C37.將10階對稱矩陣A壓縮存儲到―維數(shù)組B中，則數(shù)組B的長度最少為（)。A、100B、40C、80D、55答案：D38.線性表有一個特點()。A、至少有兩個元素，即開始元素和終端元素B、若沒有開始元素，則一定沒有終端元素C、每個元素必須有一個前趨元素D、任何一個元素都可能既是開始元素又是終端元素答案：B39.在含有n個結(jié)點的二叉排序中查找某關(guān)鍵字的結(jié)點時，最多進(jìn)行()次比較。A、n/2B、log2nC、log2n+1D、n答案：D40.設(shè)串s為一個長度為n的串，其中各字符不相同，則s中真子串的數(shù)目是()。A、n(n-1)/2B、n(n+1)/2C、n(n+1)/2+1D、n(n-1)/2+1答案：B41.對下圖所示的有向圖進(jìn)行拓?fù)渑判颍梢缘玫讲煌耐負(fù)湫蛄械膫€數(shù)是()A、4B、3C、2D、1答案：B42.二叉排序樹中，最大關(guān)鍵字結(jié)點()。A、沒有左孩子結(jié)點B、沒有右孩子結(jié)點C、一定沒有左右孩子結(jié)點D、一定存在左右孩子結(jié)點答案：B43.設(shè)哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有()個葉子結(jié)點。A、99B、100C、101D、102答案：B44.串是—種特殊的線性表,其特殊性體現(xiàn)在()。A、可以順序存儲B、數(shù)據(jù)元素是單個字符C、可以鏈?zhǔn)酱鎯、數(shù)據(jù)元素可以是多個字符答案：B45.堆的形狀是一棵()。A、滿二叉樹B、二叉判定樹C、平衡二叉樹D、完全二叉樹答案：D46.對如下圖所示的有向圖進(jìn)行拓?fù)渑判?，得到的拓?fù)湫蛄锌赡苁?)A、3，1，4，2.6,5B、3,1，2，4，5，6C、3,1，2，4，6.5D、3，1，4，2，5，6答案：A47.對于只在表的首尾兩端進(jìn)行插入操作的線性表宜采用的存儲結(jié)構(gòu)為()。A、順序表B、用頭指針表示的單循環(huán)鏈表C、用尾指針表示的單循環(huán)鏈表D、單鏈表答案：C48.一個n個頂點的連通無向圖.其邊的個數(shù)至少為()。A、n-1B、nC、n+1D、nlog2n答案：A49.穩(wěn)定的排序方法是()。A、直接插入排序和快速排序B、折半插入排序和起泡排序C、簡單選擇排序和四路歸并排序D、樹形選擇排序和hel排序答案：B50.以下()方法在數(shù)據(jù)基本有序時效率最好。A、快速排序B、冒泡排序C、堆排序D、希爾排序答案：B51.n個頂點的連通圖的生成樹有()個頂點。A、n-1B、nC、n+1D、不確定答案：B52.有一組數(shù)據(jù)(15.9.7.8.20.-1,7.4).用快速排序的劃分方法進(jìn)行一趟劃分后數(shù)據(jù)的排序為()(按遞增序)。A、其它選項都不對B、9.7.8.4-1.7.15.20C、20.15,8.9.7-1.4.7D、9.4.7.87.-1.15,20答案：A53.在排序算法中，每次從未排序的記錄中挑出最小(或最大)關(guān)鍵碼字的記錄,加入到已排序記錄的末尾該排序方法是()。A、選擇B、冒泡C、插入D、堆答案：A54.若線性表最常用的操作是存取第i個元素及其前驅(qū)的值，則采用()存儲方式節(jié)省時間。A、單鏈表B、雙鏈表C、單循環(huán)鏈表D、順序表答案：D55.對特殊矩陣采用壓縮存儲的主要目的是（)。A、表達(dá)變得簡單B、對矩陣元素的存取變得簡單C、去掉矩陣中多余的元素D、減少不必要的存儲空間答案：D56.鏈接存儲的存儲結(jié)構(gòu)所占存儲空間（)。A、分為兩部分，一部分存放結(jié)點值,另一部分存放表示結(jié)點間關(guān)系的指針B、只有一部分，存放結(jié)點值C、只有一部分,存儲表示結(jié)點間關(guān)系的指針D、分兩部分，—部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)答案：A57.n個頂點的連通圖的生成樹有()條邊。A、nB、n-1C、n+1D、不確定答案：B58.多維數(shù)組之所以有行優(yōu)先順序和列優(yōu)先順序兩種存儲方式是因為()。A、數(shù)組的元素處在行和列兩個關(guān)系中B、數(shù)組的元素必須從左到右順序排列C、數(shù)組的元素之間存在次序關(guān)系D、數(shù)組是多維結(jié)構(gòu)，內(nèi)存是一維結(jié)構(gòu)答案：D59.哈希查找的基本思想是根據(jù)()來決定元素的存儲地址。A、元素的序號B、元素個數(shù)C、關(guān)鍵字值D、非關(guān)鍵字屬性值答案：C60.若元素a、b、C、d、e、f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行，但不允許連續(xù)三次進(jìn)行退棧工作，則不可能得到的出棧序列是()。A、dcebfaB、cbdaefC、bcaefdD、afedcb答案：D61.若從無向圖的任意一個頂點出發(fā)進(jìn)行一次深度優(yōu)先搜索，可以訪問圖中所有的頂點，則該圖一定是（）圖。A、非連通B、連通C、強連通D、有向答案：B62.數(shù)據(jù)結(jié)構(gòu)是具有()的數(shù)據(jù)元素的集合。A、性質(zhì)相同B、相同物理結(jié)構(gòu)C、數(shù)據(jù)項D、相互關(guān)系答案：D63.函數(shù)(f(x:y)定義如下:

F(xy)=f(x-1.y)+f(x,y-1)當(dāng)x>0且y>0

F(xy)=x+y否則

則f(2,1)的值是()。A、1B、2C、3D、4答案：D64.以下關(guān)于哈希查找的敘述中錯誤的是（)。A、用拉鏈法解決沖突易引起堆積現(xiàn)象B、用線性探測法解決沖突易引起堆積現(xiàn)象C、哈希函數(shù)選得好可以減少沖突現(xiàn)象D、哈希函數(shù)H(k)=kMODp，p通常取小于等于表長的素數(shù)答案：A65.有數(shù)據(jù)(30.37.1245.24.963.從空二叉樹開始逐個插入數(shù)據(jù)來形成二叉排序樹，若希望高度最小則應(yīng)選擇下面哪個序列輸入?()A、45.24.53.12.37.96.30B、37,24.12.30.53.45.96C、12.24,30,37.45,53.96D、30,24,12.37.45,96,53答案：B66.線性表中哪些元素只有一個直接前驅(qū)和一個直接后繼?()A、首元素B、尾元素C、中間元素D、所有的元素答案：C67.內(nèi)排序方法的穩(wěn)定性是指()。A、經(jīng)過排序后，能使關(guān)鍵字相同的元素保持原順序中的相對位置不變B、經(jīng)過排序后，能使關(guān)鍵字相同的元素保持原順序中的絕對位置不變C、排序算法的性能與被排序元素的數(shù)量關(guān)系不大D、排序算法的性能與被排序元素的數(shù)量關(guān)系密切答案：A68.為解決計算機主機與打印機間速度不匹配問題，通常設(shè)一個打印數(shù)據(jù)緩沖區(qū)。主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是()。A、隊列B、棧C、線性表D、有序表答案：A69.設(shè)棧的輸入序列是1、2、...、m.若輸出序列的第一個元素是n.,則第i個輸出元素是()。A、不確定B、n-i+1C、iD、n-i答案：B70.表達(dá)式的.2(42024215*求值過程中當(dāng)掃描到時，對象棧和算符棧為(),其中為乘冪，為表達(dá)式開始和結(jié)束的界定符。A、3,2.4,1,1;#*^(+*-B、3,2.8;#*^-C、3,2.4,2,2;#*^-D、3.2.8;*^<-答案：D71.若一棵完全二叉樹有768個結(jié)點，則該二叉樹中葉子結(jié)點的個數(shù)是()。A、257B、258C、384D、385答案：C72.下列四個序列中，哪一個是堆?()A、75.65.30.15.25.45.20.10B、75,6545.10.3025.20.15C、7545.65.30.15.25.20.10D、75.45,65,10.25.30,20,15答案：C73.一棵含有n個結(jié)點的線索二叉樹中，其線索個數(shù)為()。A、2nB、n-1C、n+1D、n答案：C74.在一個無向圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的()倍。A、1/2B、1C、2D、4答案：C75.把一棵樹轉(zhuǎn)化為二叉樹后，這棵二叉樹的形態(tài)是()。A、唯一的B、有多種C、有多種，但根結(jié)點沒有左孩子D、有多種，但根結(jié)點沒有右孩子答案：A76.一棵具有1025個結(jié)點的二叉樹的高h(yuǎn)為()。A、10B、11C、11至1025之間D、10至1024之間答案：C77.已知一棵完全二叉樹的第6層(設(shè)根為第一層)有8個葉子結(jié)點，則該完全二叉樹的結(jié)點個數(shù)最多是()。A、39B、52C、111D、119答案：C78.采用順序查找方法查找長度為n的線性表時，成功查找的平均查找長度為()。A、nB、n/2C、(n+1)/2D、(n-1)/2答案：C79.哈希查找方法一般適用于()情況下的查找。A、查找表為鏈表B、查找表為有序表C、關(guān)鍵字集合比地址集合大得多D、關(guān)鍵字集合與地址集合之間存在著某種對應(yīng)關(guān)系答案：D80.分別以下列序列構(gòu)造二叉排序數(shù)，與用其他三個序列所構(gòu)造的結(jié)果不同的是（)。A、(100,80,90,60，120，110，130)B、(100，120，110，130,80，60,90)C、(100,6o,80,90，120,110，130)D、(100，80，60，90,120，130,110)答案：C81.以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是()。A、循環(huán)隊列B、鏈表C、哈希表D、棧答案：D82.設(shè)散列表的長m-14.散列函數(shù)為a(太=以%11,表中已有4個記錄如表所示),如果采用二次探測再蘇敞列采處理沖突則天鍵子力+9的記錄具仔儲地址是()。A、8B、3C、5D、9答案：D83.若一個棧以向量V[1-n]存儲，初始棧頂指針top設(shè)為n+1，則元素x進(jìn)棧的正確操作是()。A、top++;V[top]=x;B、V[top]=x;top++;C、top--;V[top]=x;D、V[top]=x;top--;答案：C84.二維數(shù)組A的每個元素是由10個字符組成的串，其行下標(biāo)-=1..8.列下標(biāo)=1.2,:-;10。若A按行先存儲，元素A[8,5]的起始地址與當(dāng)A按列先存儲時的元素()的起始地址相同。設(shè)每個字符占1個字節(jié)。A、A[8,5]B、A[3,10]C、A[5,8]D、A[0.9]答案：B85.對序列{15.9.7.8.20-1.4.3.用希爾排序方法排序,經(jīng)一趟后序列變?yōu)閧15,-1.4.8,20.9.7}.則該次采用的增量是()。A、1B、4C、3D、2答案：B86.在含有n(n>2)個數(shù)據(jù)結(jié)點的數(shù)據(jù)結(jié)構(gòu)中，終端結(jié)點是指()的結(jié)點。A、沒有前趨結(jié)點B、含有一個或多個前趨結(jié)點C、沒有后繼結(jié)點D、含有一個或多個后繼結(jié)點答案：B87.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復(fù)雜度為()。A、0(1)B、O(n)C、O(m)D、O(m+n)答案：C88.設(shè)有數(shù)組A[iu，數(shù)組的每個元素長度為3個字節(jié)i的值為1~8，j的值為1~10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時，元素A5,8]的存儲首地址為A、BA+141B、BA+180C、BA+222D、BA+225答案：B89.下面幾個符號串編碼集合中，不是前綴編碼的是()。A、{0.10.11.111}B、{11.10,001,101,0001}C、{00,010,0110,1000}D、{b.c.aa,ac,aba,abb,abc}答案：B90.在一個圖中，每個頂點的前趨頂點和后繼頂點數(shù)可以有()。A、1個B、2個C、任意多個D、0個答案：C91.在一個具有n個結(jié)點的有序單鏈表中插入-個新結(jié)點并使插入結(jié)點后的單鏈表仍然有序則該操作的時間復(fù)雜性量級是()。A、O(1)B、O(n)C、O(nlog2n)D、O(n2)答案：B92.在線性表的下列運算中，不改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運算是()。A、插入B、刪除C、排序D、定位答案：D93.某隊列允許在其兩端進(jìn)行入隊操作，但僅允許在-端進(jìn)行出隊操作，元素abcde依次入隊列，則不可能得到的出隊順序是()。A、bacdeB、dbaceC、dbcaeD、ecbad答案：C94.折半查找有序表(4.6.10,12.20,30,50,70,88,100)。若查找表中元素58，則它將依次與表中()比較大小，查找結(jié)果是失敗。A、20,70,30,50B、30,88,70,50C、20,50D、30,88,50答案：A95.具有n個頂點的有向圖最多有()條邊。A、nB、n(n-1)C、n(n+1)D、n*n答案：B96.正確的遞歸算法應(yīng)包含()。A、遞歸出口B、遞歸體C、遞歸出口和遞歸體D、以上都不包含答案：C97.已知圖的鄰接表如下圖所示，則從頂點V,出發(fā)按深度優(yōu)先遍歷的結(jié)果是（)。A、1032B、0123C、0321D、0231答案：B98.設(shè)森林F中有3棵樹，第一、第二和第三棵樹的結(jié)點個數(shù)分別為9、8和7，則與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是()。A、16B、15C、7D、17答案：B99.以下排序中，()不需要進(jìn)行關(guān)鍵字的比較。A、快速排序B、歸并排序C、基數(shù)排序D、堆排序答案：C100.線性表(a1，a2，…,an)以鏈接方式存儲時，訪問第i個位置上元素的時間復(fù)雜度為（)。A、O(i)B、O(1)C、o(n)D、O(i-1)答案：C101.對n階對稱矩陣壓縮存儲時，需要表長為()的順序表。A、n/2B、n2/2C、n(n+1)/2D、n(n-1)/2答案：C102.以下數(shù)據(jù)結(jié)構(gòu)中,哪一個是線性結(jié)構(gòu)?()A、廣義表B、二叉樹C、稀疏矩陣D、串答案：D103.以下敘述中錯誤的是()。A、圖的遍歷是從給定的初始點出發(fā)訪問每個頂點且每個頂點僅訪問一次B、圖的深度優(yōu)先遍歷適合無向圖C、圖的深度優(yōu)先遍歷不適合有向圖D、圖的深度優(yōu)先遍歷是一個遞歸過程答案：C104.若需在o(nlogn)的時間內(nèi)完成對數(shù)組的排序,且要求排序是穩(wěn)定的.則可選擇的排序方法是()。A、快速排序B、堆排序C、歸并排序D、直接插入排序答案：C105.設(shè)圖的鄰接矩陣A如下圖所示。各頂點的度依次是()A、1，2，1.2B、2,2，1，1C、3,4，2，3D、4，4，2，2答案：C106.查找效率低的數(shù)據(jù)結(jié)構(gòu)是（）A、有序順序表B、二叉排序樹C、堆D、二叉平衡樹答案：C107.對序列{15,9,7,8,20,-1,4}進(jìn)行排序,經(jīng)一趟排序后的排列為{9.15,7,8,20,-1.4]}.則采用的是()排序。A、選擇B、堆C、直接插入D、冒泡答案：C108.下圖的深度優(yōu)先搜索序列為()。A、DFS(A)-ABEDCFB、DFS(A):AEFCDBC、DFS(A):ABCEDFD、DFS(A):ACBDEF答案：B109.線性表的順序存儲結(jié)構(gòu)是一種()。A、隨機存取的存儲結(jié)構(gòu)B、順序存取的存儲結(jié)構(gòu)C、索引存取的存儲結(jié)構(gòu)D、散列存取的存儲結(jié)構(gòu)答案：A110.一個棧的入棧序列是.b,c.d.e.則棧的不可能的輸出序列是()。A、edcbaB、decbaC、dceabD、abcde答案：C111.如圖所示的循環(huán)隊列中元素數(shù)目是()。

其中tail=32指向隊尾元素head=15指向隊頭元素的前一個空位置隊列空間m=60。A、42B、16C、17D、41答案：C112.若森林F有15條邊、25個結(jié)點，則F包含樹的個數(shù)是()。A、8B、9C、10D、11答案：C113.隊列的刪除操作是在()進(jìn)行。A、隊首B、隊尾C、隊前D、隊后答案：A114.一個遞歸算法必須包括（)。A、遞歸部分B、終止條件和遞歸部分C、迭代部分D、終止條件和迭代部分答案：B115.設(shè)有100個元素的有序表，用折半查找時，不成功時最大的比較次數(shù)是()。A、25B、50C、10D、7答案：D116.線性表中各元素之間的關(guān)系是()關(guān)系。A、層次B、網(wǎng)狀C、有序D、集合答案：C117.下面（）算法適合用于構(gòu)造一個稠密圖的最小生成樹。A、Dijkstra算法B、Prim算法C、Floyd算法D、Kruskal算法答案：B118.在一棵深度為h的具有n個元素的二叉排序樹中,查找所有元素的最長查找長度為()。A、nB、1og2nC、(h+1)/2D、h答案：D119.靜態(tài)查找與動態(tài)查找的根本區(qū)別在于()。A、它們的邏輯結(jié)構(gòu)不一樣B、施加在其上的操作不同C、所包含的數(shù)據(jù)元素的類型不-樣D、存儲實現(xiàn)不一樣答案：B120.設(shè)串長為n,模式串長為m.則KMP算法所需的附加空間為()。A、o(m)B、o(0)C、O(nlog'm)D、o(m*n)E、其他答案：A121.下面的敘述中不正確的是()。A、關(guān)鍵活動不按期完成就會影響整個工程的完成時間B、任何一個關(guān)鍵活動提前完成將使整個工程提前完成C、所有關(guān)鍵活動都提前完成，則整個工程將提前完成D、某些關(guān)鍵活動若提前完成將使按個工程提前完成答案：B122.在—棵平衡二叉樹中,每個結(jié)點的平衡因子取值范圍是()。A、-1~1B、-2~2C、1~2D、0~1答案：A123.5個字符有如下4種編碼方案，不是前綴編碼的是()。A、01，0000，0001，001，1B、011，000，001，010，1C、000，001，010，011，100D、0，100，110.1110.1100答案：D124.下列說法中,正確的有()A、最小生成樹也是哈夫曼樹B、最小生成樹唯一C、普里姆(Prim)最小生成樹算法時間復(fù)雜變?yōu)?(2)D、克魯斯卡爾(Kruska)最小生成樹算法比普里姆算法更適合于邊稠密的網(wǎng)答案：C125.以下不屬于內(nèi)排序方法的是()。A、二路歸并排序B、拓?fù)渑判駽、堆排序D、直接插入排序答案：B126.快速排序方法在(情況下最不利于發(fā)揮其長處。A、要排序的數(shù)據(jù)量太大B、要排序的數(shù)據(jù)中含有多個相同值C、要排序的數(shù)據(jù)個數(shù)為奇數(shù)D、要排序的數(shù)據(jù)已基本有序答案：D127.圖的遍歷是指()。A、訪問圖的所有頂點B、以某種次序訪問圖的所有頂點C、從一個頂點出發(fā)訪問圖中所有頂點且每個頂點只能訪問一次D、從一個頂點出發(fā)訪問圖中所有頂點但每個頂點可以訪問多次答案：C128.在一棵深度為的具有n個元素的二叉排序樹中，查找所有元素的最長查找長度為()。A、nB、1og2nC、(h+1)/2D、h答案：D129.某算法的空間復(fù)雜度為O(1)，則()。A、該算法執(zhí)行不需要任何輔助空間B、該算法執(zhí)行所需輔助空間大小與問題規(guī)模n無關(guān)C、該算法執(zhí)行不需要任何空間D、該算法執(zhí)行所需全部空間大小與問題規(guī)模n無關(guān)答案：B130.表達(dá)式#3*2^(4+2*2-6*3)-5#求值過程中當(dāng)掃描到6時,對象棧和算符棧為(),其中^為乘冪,#為表達(dá)式開始和結(jié)束的界定符。A、3,2,4,1,1;#*^(+*-B、3,2,8;#*^-C、3,2,4,2,2;#*^(-D、3,2,8;#*^(-答案：D131.棧和隊列的主要區(qū)別在于()。A、它們的邏輯結(jié)構(gòu)不一樣B、它們的存儲結(jié)構(gòu)不一樣C、所包含的運算不--樣D、插入、刪除運算的限定不一樣答案：D132.將一個A[..100.1.10o]的三角矩陣.按行優(yōu)先存入一維數(shù)組B...298]中.A中素af6,f(即該元素下標(biāo)i=66j=-65),在B數(shù)組中的位置k為()。A、198B、195C、197D、199答案：B133.下面關(guān)于散列查找的說法，不正確的是()。A、采用鏈地址法處理沖突時，查找任何一個元素的時間都相同B、采用鏈地址法處理沖突時，若插入規(guī)定總是在鏈?zhǔn)祝瑒t插入任一個元素的時間是相同的C、用鏈地址法處理沖突，不會引起二次聚集現(xiàn)象D、用鏈地址法處理沖突，適合表長不確定的情況答案：A134.以下說法錯誤的是()。A、存在這樣的二叉樹,對它采用任何次序遍歷其結(jié)點訪問序列均相同B、二叉樹是樹的特殊情形C、由樹轉(zhuǎn)換成二叉樹,其根結(jié)點的右子樹總是空的D、在二叉樹只有一棵子樹的情況下也耍明確指出該子樹是左子樹還是右子樹答案：B135.在單鏈表的一個結(jié)點中有()個指針。A、1B、2C、3D、4答案：A136.若用鄰接矩陣存儲有向圖，矩陣中主對角線以下的元素均為零，則關(guān)于該圖拓?fù)湫蛄械慕Y(jié)論是()。A、存在，且唯一B、存在，且不唯一C、存在，可能不唯一D、無法確定是否存在答案：C137.假定一個順序循環(huán)隊列存儲于數(shù)組A[]中.其隊首和隊尾指針分別用from和rear表示則判斷隊滿的條件是()。A、(rcar-1)%n==frontB、(rear+1)%n=-frontC、rear==(front-1)%nD、rear==(front+1)%n答案：B138.利用逐點插入法建立序列50.724385.75.20.35.45.,65,30}對應(yīng)的二叉排序樹以后查找元素35要進(jìn)行()元素間的比較。A、4次B、5次C、7次D、10次答案：A判斷題1.無向圖的鄰接矩陣是對稱的，因此可以只存儲鄰接矩陣的下(或上)三角陣。()A、正確B、錯誤答案：A2.順序查找只能在順序存儲結(jié)構(gòu)上進(jìn)行。A、正確B、錯誤答案：B3.循環(huán)鏈表不是線性表。A、正確B、錯誤答案：B4.遞歸算法轉(zhuǎn)換為非遞歸算法時，通常借助于隊列來實現(xiàn)。A、正確B、錯誤答案：B5.隊列邏輯上是一個下端和上端既能增加又能減少的線性表。()A、正確B、錯誤答案：A6.數(shù)據(jù)的邏輯結(jié)構(gòu)與各數(shù)據(jù)元素在計算機中如何存儲有關(guān)。A、正確B、錯誤答案：B7.線性表的邏輯順序與物理順序總是—致的。()A、正確B、錯誤答案：B8.二叉樹就是結(jié)點度為2的樹。()A、正確B、錯誤答案：B9.棧是一種特殊的線性表，其特殊之處在于棧的存儲結(jié)構(gòu)比較特殊。A、正確B、錯誤答案：B10.任何數(shù)據(jù)結(jié)構(gòu)都具備3個基本運算:插入、刪除和查找。A、正確B、錯誤答案：B11.稀疏矩陣壓縮存儲后，必會失去隨機存取功能。()A、正確B、錯誤答案：A12.對一個堆按二叉樹層次進(jìn)行遍歷可以得一個有序列。()A、正確B、錯誤答案：B13.二叉樹中每個結(jié)點至多有兩個孩子結(jié)點，而一般樹沒有這種限制，所以二叉樹是樹的特殊情形。A、正確B、錯誤答案：B14.哈夫曼樹中是帶權(quán)路徑長度最短的二叉樹，權(quán)值越大的結(jié)點離根結(jié)點越遠(yuǎn)。A、正確B、錯誤答案：B15.棧具有先進(jìn)后出的特點，其中數(shù)據(jù)的邏輯結(jié)構(gòu)是任意的。A、正確B、錯誤答案：B16.影響外排序的時間因素主要是內(nèi)存與外存交換信息的次數(shù)。A、正確B、錯誤答案：A17.由二叉樹的中序遍歷序列和后序遍歷序列,能夠唯―確定該二叉樹。A、正確B、錯誤答案：A18.二叉排序樹是用來進(jìn)行排序的。A、正確B、錯誤答案：B19.由二叉樹的先序遍歷序列和后序遍歷序列，能夠唯一確定該二叉樹。A、正確B、錯誤答案：B20.散列表的結(jié)點中包含數(shù)據(jù)元素自身的信息,不包含任何指針。()A、正確B、錯誤答案：B21.在任意一棵非空二叉樹中，刪除某結(jié)點后又將其插入，則所得二叉排序樹與刪除前原二叉樹排序樹相同。()A、正確B、錯誤答案：B22.一種邏輯結(jié)構(gòu)的數(shù)據(jù)只有一種對應(yīng)的存儲結(jié)構(gòu)。A、正確B、錯誤答案：B23.數(shù)據(jù)的運算描述是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的。A、正確B、錯誤答案：A24.由一棵二叉樹的前序序列和后序序列可以唯一確定它。()A、正確B、錯誤答案：B25.隊列是一種對進(jìn)隊、出隊操作的次數(shù)做了限制的線性表。A、正確B、錯誤答案：B26.棧和隊列邏輯上都是線性表。A、正確B、錯誤答案：A27.順序查找方法只能從順序表的前端向后端查找。A、正確B、錯誤答案：B28.n個元素進(jìn)隊的順序和出隊的順序總是一致的。A、正確B、錯誤答案：A29.直接選擇排序算法在最好情況下的時間復(fù)雜度為O(n)。()A、正確B、錯誤答案：B30.用棉爾咖方法排序時，若關(guān)鍵字的初始排序雜亂無序則排序效率就低。A、正確B、錯誤答案：B31.空棧是指棧中元素沒有賦值。A、正確B、錯誤答案：B32.給定一棵樹,可以找到唯一的一棵二叉樹與之對應(yīng)。()A、正確B、錯誤答案：A33.線性表中所有元素的數(shù)據(jù)類型必須相同。A、正確B、錯誤答案：A34.將二叉樹變?yōu)榫€索二叉樹的過程稱為線索化。A、正確B、錯誤答案：A35.哈夫曼樹中結(jié)點個數(shù)可以是偶數(shù)也可以是奇數(shù)。A、正確B、錯誤答案：B36.從邏輯關(guān)系上講.數(shù)據(jù)結(jié)構(gòu)主要分為兩大類:線性結(jié)構(gòu)和非線性結(jié)構(gòu)。()A、正確B、錯誤答案：A37.遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行效率也高。A、正確B、錯誤答案：B38.二路歸并排序算法的時間復(fù)雜度與初始數(shù)據(jù)序列的順序無關(guān)。A、正確B、錯誤答案：A39.對于有N個結(jié)點的二叉樹,其高度為1og2n。()A、正確B、錯誤答案：B40.順序存儲的線性表可以隨機存取。()A、正確B、錯誤答案：A41.哈夫曼樹中是帶權(quán)路徑長度最短的二叉樹，權(quán)值越大的結(jié)點離根結(jié)點越遠(yuǎn)。A、正確B、錯誤答案：B42.數(shù)據(jù)運算的實現(xiàn)是基于數(shù)據(jù)的邏輯結(jié)構(gòu)的。A、正確B、錯誤答案：B43.二叉排序樹可以是一棵空樹。A、正確B、錯誤答案：A44.非空二叉樹的中序序列的最后一個結(jié)點一定是葉子結(jié)點。A、正確B、錯誤答案：B45.循環(huán)隊列通常用指針來實現(xiàn)隊列的頭尾相接。()A、正確B、錯誤答案：B46.哈希表發(fā)生沖突是由于選取的解決沖突的方法不當(dāng)造成的。A、正確B、錯誤答案：B47.只要是算法，肯定可以在有限的時間內(nèi)完成。A、正確B、錯誤答案：A48.在二叉樹的第i層上至少有2i-1個結(jié)點(i>=1)。()A、正確B、錯誤答案：B49.一棵樹中的葉子數(shù)-定等于與其對應(yīng)的二叉樹的葉子數(shù)。()A、正確B、錯誤答案：B50.在隊空間大小為n的非循環(huán)隊列中，最多只能進(jìn)行n次進(jìn)隊操作。A、正確B、錯誤答案：A51.任何一個圖，一旦指定源點，其深度優(yōu)先遍歷序列是唯一的。A、正確B、錯誤答案：B52.在具有頭結(jié)點的鏈?zhǔn)酱鎯Y(jié)構(gòu)中,頭指針指向鏈表中的第一個數(shù)據(jù)結(jié)點。()A、正確B、錯誤答案：B53.一個圖中的簡單路徑是指該路徑上的邊不重復(fù)出現(xiàn)。A、正確B、錯誤答案：B54.線性表中的結(jié)點按前趨、后繼關(guān)系可以排成一個線性序列。A、正確B、錯誤答案：A55.用鏈表(link-rlink)存儲包含個結(jié)點的二叉樹時，結(jié)點的2n個指針區(qū)域中有n+1個空指針。A、正確B、錯誤答案：A56.棧的定義不涉及數(shù)據(jù)的邏輯結(jié)構(gòu)。A、正確B、錯誤答案：B57.在有向圖中，如果頂點i到頂點j有路徑，而頂點到頂點k沒有路徑，則頂點j到頂點k也沒有路徑。A、正確B、錯誤答案：A58.線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)。A、正確B、錯誤答案：B59.在單鏈表中要訪問某個結(jié)點只要知道該結(jié)點的指針即可:因此，單鏈表是一種隨機存儲結(jié)構(gòu)。A、正確B、錯誤答案：B60.棧在算法設(shè)計中用于保存臨時數(shù)據(jù),這些數(shù)據(jù)具有先進(jìn)后出的特點，如果某算法中只產(chǎn)生一個臨時數(shù)據(jù)，那么用棧和隊列都可以。A、正確B、錯誤答案：A61.在無向圖中，如果頂點i到頂點j有路徑，而頂點j到頂點k沒有路徑，則頂點i到頂點k也沒有路徑。A、正確B、錯誤答案：A62.對于無向圖生成樹，從同一頂點出發(fā)所得到的生成樹一定是相同的。A、正確B、錯誤答案：B63.非空二叉樹的后序序列的最后一個結(jié)點一定是葉子結(jié)點。A、正確B、錯誤答案：B64.循環(huán)隊列也存在空間溢出問題。(,A、正確B、錯誤答案：A65.外排序與外部設(shè)備的特性無關(guān)。A、正確B、錯誤答案：B66.圖的深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列不是唯一的。()A、正確B、錯誤答案：A67.在線性表的順序存儲結(jié)構(gòu)中插入和刪除元素時，移動元素的個數(shù)與該元素的位置有關(guān)。A、正確B、錯誤答案：A68.由二叉樹的先序遍歷序列和中序遍歷序列，能夠唯一確定該二叉樹。A、正確B、錯誤答案：A69.KMP算法的最大特點是指示主串的指針不需回溯。()A、正確B、錯誤答案：A70.調(diào)用自身的函數(shù)稱為遞歸函數(shù)。A、正確B、錯誤答案：A71.如果連通網(wǎng)中存在相同權(quán)值的邊，則最小生成樹不唯一。()A、正確B、錯誤答案：A72.用鏈表(link-rlink)存儲包含n個結(jié)點的二叉樹結(jié)點的2n個指針區(qū)域中有n-1個空指針。A、正確B、錯誤答案：B73.隊列是一種對進(jìn)隊、出隊操作的次序做了限制的線性表。A、正確B、錯誤答案：B74.排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。A、正確B、錯誤答案：B75.一個遞歸算法可以沒有遞歸體，但必須包含遞歸出口部分。A、正確B、錯誤答案：B76.在初始數(shù)據(jù)表已經(jīng)有序時:快速排序算法的時間復(fù)雜度為0(1og2n)。()A、正確B、錯誤答案：B77.二叉樹中不存在度大于2的結(jié)點當(dāng)某個結(jié)點只有一棵予樹時無所謂左、右子樹之分。A、正確B、錯誤答案：B78.空串是由空格構(gòu)成的串。A、正確B、錯誤答案：B79.內(nèi)排序過程在數(shù)據(jù)量很大時就變成了外排序過程。A、正確B、錯誤答案：B80.用鄰接矩陣存儲一個圖時，所占用的存儲空間大小只與圖中結(jié)點的個數(shù)有關(guān)而與圖的邊數(shù)無關(guān)。()A、正確B、錯誤答案：A81.二叉排序樹的任意-棵子樹中，關(guān)鍵字最小的結(jié)點必?zé)o左孩子，關(guān)鍵字最大的結(jié)點必?zé)o右孩子。A、正確B、錯誤答案：A82.線性表的長度是線性表占用的存儲空間的大小。A、正確B、錯誤答案：B83.數(shù)組可看成線性結(jié)構(gòu)的一種推廣，因此與線性表一樣，可以對它進(jìn)行插入刪除等操作。A、正確B、錯誤答案：B84.無向圖的鄰接矩陣一定是對稱矩陣,且有向圖的鄰接矩陣一定是非對稱矩陣。()A、正確B、錯誤答案：B85.二叉樹就是度為2的有序樹。A、正確B、錯誤答案：B86.哈希沖突是指同一個關(guān)鍵宇對應(yīng)多個不同的哈希地址。A、正確B、錯誤答案：B87.對于無向圖生成樹，其深度優(yōu)先生成樹和廣度優(yōu)先生成樹一定不相同。A、正確B、錯誤答案：B88.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關(guān)系。()A、正確B、錯誤答案：B89.圖的遍歷就是訪問圖中所有頂點。A、正確B、錯誤答案：B90.連通分量是無向圖中的極小連通子圖。()A、正確B、錯誤答案：B填空題1.如果結(jié)點A有3個兄弟，而且B是A的雙親則B的度是()。答案：42.字符串中任意個連續(xù)的字符組成的子序列稱為該串的()。答案：子串3.已知一無向圖G=(,),其中V={a,b,c,d,e},E={(a,b)（a，d）（a，c）（d，c）（b，e）}，現(xiàn)用某一種遍歷方法從頂點a開始遍歷圖，得到的序列為adbce,則采用的是()遍歷方法。答案：廣度優(yōu)先4.根據(jù)二叉樹的定義.具有三個結(jié)點的二叉樹有()種不同的形態(tài)。答案：55.下面程序段的時間復(fù)雜度是()。

I=0;

S=0;.

While(s<n)

{

I++;

S+=1;

}答案：0(√n)6.含有n個頂點的無向圖都連通全部頂點至少需要()條邊。答案：n-17.順序表中第一個元素的存儲地址為100，每個元素的長度為2.則第五個元素的存儲地址為()。答案：1088.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,那么它的先序遍歷序列是()。答案：|cedba9.用一維數(shù)組存放一棵完全二叉樹:ABCDEFGHIJKL.則后序遍歷該二叉樹的結(jié)點序列為()。答案：HIDJKEBLFGCA10.對于一棵具有n個結(jié)點的樹.該樹中所有結(jié)點的度數(shù)之和為()。答案：n-111.在有n個頂點的有向圖中,每個頂點的度最大可達(dá)()。答案：2(n-1)12.設(shè)正文串長度為n,模式串長度為m，則串匹配的KMP算法的時間復(fù)雜度為()。答案：O(n+m)13.有一個循環(huán)隊列Q，存儲空間的大小為10，起始時Q.front=O，Q.rear=5，執(zhí)行進(jìn)隊3個數(shù)據(jù)元素，再出隊2個數(shù)據(jù)元素以后Qfront的值為(),Q.rear的值為（）答案：2|814.已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,那么它的先序遍歷序列是()。答案：|cedba15.組成串的數(shù)據(jù)元素只能是()。答案：字符16.設(shè)有序表有100個元素用折半查找法查找最大比較次數(shù)為().最小比較次數(shù)為()。答案：|7|117.兩個串相等的充分必要條件是()。答案：兩個串的長度相等且對應(yīng)的字符相同18.圖中所有頂點的度之和為圖中邊數(shù)的()倍。答案：219.有n個頂點的無向圖最多有（）條邊。答案：n(n-1)/220.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的()以及它們之間的()和運算的學(xué)科。答案：操作對象|關(guān)系21.空格串是()，其長度等于()。答案：由一個或多個空格字符組成的串|其包含的空格個數(shù)22.已知有序表為12.12435.47562,3.9.115,134).當(dāng)用二分法查找90時，需進(jìn)行()次查找可確定成功查找100時,需進(jìn)行()次查找才能確定不成功。答案：2|323.一棵完全二叉樹有999個結(jié)點它的深度是()。答案：1024.如下圖的樹中.結(jié)點H的祖先為()。答案：A、D、G25.二叉樹共有()種不同的形態(tài)。答案：526.肚分法查找一個線性表時，該線性表必須具有的特點是().而分塊查找法要求將待查找的表均勻地分成若干塊且塊中諸記錄的順序可以是任意的,但塊與塊之間()。答案：順序存儲且有序|有序27.設(shè)有一個順序共享棧S[0:n-1]，其中第一個棧頂指針top1的初值為-1,第二個棧頂指針top22的初值為n，則判斷共享棧滿的條件是()。答案：Top1+1==top228.一棵含有50個結(jié)點的二叉樹，它的最小高度是（)。答案：629.算法具有5個特性，分別是有零個或多個輸入有一個或多個輸出，().().()。答案：有窮性|確定性|可行性30.具有10個頂點的無向圖.邊的總數(shù)最多為()。答案：4531.一棵含有50個結(jié)點的二叉樹，它的最大高度是()答案：5032.已知一無向圖G=(V,E).其中V={a,b,c,d,e},E={(a,b),(a,d),(a,c),(d,c),(b,e)},現(xiàn)用某一種遍歷方法從頂點a開始遍歷圖，得到的序列為adbce,則采用的是()遍歷方法。答案：|深度優(yōu)先|簡答題1.編寫算法實現(xiàn):有一個長度大于2的整數(shù)單鏈表L，設(shè)計一個算法查找L的中間位置的元素。例如:L=(1,2,3),返回元素2;L=(1,2,3.4)，返回元素為2。

要求:

(1)寫出單鏈表的Python語言定義;

(2)描述算法的基本設(shè)計思想

(3)根據(jù)設(shè)計思想，完成算法代碼的編寫。答案：(1)單鏈表的存儲結(jié)構(gòu)的定義如下:

ClassLinkNode:

#單鏈表結(jié)點類

Def_init_(self,data=None):

Self.data=data

Self.next=None

ClassLinkList.

#單鏈表類

Def_init_(self):

Self.head=LinkNode(

Self.head.next=None

(2)算法的基本思想(參考):

1)計算出單鏈表L的長度n;

2）若首結(jié)點的編號為1，則中間位置的元素編號為(n-1)/2+1，置j=1,p指向首結(jié)點，讓其后移(n-1)/2-1個結(jié)點即可;

3）返回p的數(shù)據(jù)元素。

(3)參考算法:

DefMiddle1(L):

J=1

N=L.getsize(

P=Lhead.next

Whilej<=(n-1)//2:

J+=1

P=p.next

Returnp.data2.簡述棧和隊列的相同點和不同點。答案：

相同點:從數(shù)據(jù)的邏輯結(jié)構(gòu)角度來看，棧和隊列都是線性結(jié)構(gòu);從操作的角度來看，棧和隊列都是操作受限的線性表。

不同點:棧是限定僅在表