大學(xué)數(shù)據(jù)結(jié)構(gòu)期末考試題(有答案)

下載可編輯下載可編輯.專業(yè).整理..專業(yè).整理..專業(yè).整理..專業(yè).整理.“數(shù)據(jù)結(jié)構(gòu)”期末考試試題一、單選題(每小題2分，共12分)1?在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，貝0執(zhí)行()。HL=psp一〉next=HLp一〉next=HL；HL=p3p—〉next=Hl；p=HL；p—〉next=HL—〉next;HL—〉next=p；n個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有()。A.n—l條有向邊B.n條有向邊C.n(n—1)/2條有向邊D.n(n—1)條有向邊TOC\o"1-5"\h\z從一棵二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為()。A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)由權(quán)值分別為3，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為()。A.24B.48C.72D.53當(dāng)一個(gè)作為實(shí)際傳遞的對(duì)象占用的存儲(chǔ)空間較大并可能需要修改時(shí)，應(yīng)最好把它說明為()參數(shù)，以節(jié)省參數(shù)值的傳輸時(shí)間和存儲(chǔ)參數(shù)的空間。A.整形B.引用型C.指針型D.常值引用型?6?向一個(gè)長度為n的順序表中插人一個(gè)新元素的平均時(shí)間復(fù)雜度為()。A.O(n)B.O(1)C.O(n2)D.O(10g2n)二、填空題(每空1分，共28分)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為——、——、——和——四種。在廣義表的存儲(chǔ)結(jié)構(gòu)中，單元素結(jié)點(diǎn)與表元素結(jié)點(diǎn)有一個(gè)域?qū)?yīng)不同，各自分別為——域和——域。——中綴表達(dá)式3十x*(2.4/5—6)所對(duì)應(yīng)的后綴表達(dá)式為。4?在一棵高度為h的3叉樹中，最多含有——結(jié)點(diǎn)。5?假定一棵二叉樹的結(jié)點(diǎn)數(shù)為18，則它的最小深度為一一，最大深度為在一棵二叉搜索樹中，每個(gè)分支結(jié)點(diǎn)的左子樹上所有結(jié)點(diǎn)的值一定——該結(jié)點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值一定——該結(jié)點(diǎn)的值。當(dāng)向一個(gè)小根堆插入一個(gè)具有最小值的元素時(shí)，該元素需要逐層——調(diào)整，直到被調(diào)整到——位置為止。表示圖的三種存儲(chǔ)結(jié)構(gòu)為——、——和———。9?對(duì)用鄰接矩陣表示的具有n個(gè)頂點(diǎn)和e條邊的圖進(jìn)行任一種遍歷時(shí)，其時(shí)間復(fù)雜度為一一，對(duì)用鄰接表表示的圖進(jìn)行任一種遍歷時(shí)，其時(shí)間復(fù)雜度為——。從有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素時(shí)，其查找長度分別為和?假定對(duì)長度n=144的線性表進(jìn)行索引順序查找，并假定每個(gè)子表的長度均為，則進(jìn)行索引順序查找的平均查找長度為一一，時(shí)間復(fù)雜度為12?一棵B—樹中的所有葉子結(jié)點(diǎn)均處在一一上。每次從無序表中順序取出一個(gè)元素，把這插入到有序表中的適當(dāng)位置，此種排序方法叫做——排序；每次從無序表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做——排序。快速排序在乎均情況下的時(shí)間復(fù)雜度為——，最壞情況下的時(shí)間復(fù)雜度為——。三、運(yùn)算題(每小題6分，共24分)1?假定一棵二叉樹廣義表表示為a(b(c,d),c(((，8)))，分別寫出對(duì)它進(jìn)行先序、中序、后序和后序遍歷的結(jié)果。先序：中序；后序：已知一個(gè)帶權(quán)圖的頂點(diǎn)集V和邊集G分別為：V={0,1，2，3，4，5}；E={(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(4，5)10}，則求出該圖的最小生成樹的權(quán)。最小生成樹的權(quán)；3．假定一組記錄的排序碼為(46，79，56，38，40，84，50，42)，則利用堆排序方法建立的初始堆為——。4．有7個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3，7，8，2，6，10，14，試以它們?yōu)槿~子結(jié)點(diǎn)生成一棵哈夫曼樹求出該樹的帶權(quán)路徑長度、高度、雙分支結(jié)點(diǎn)數(shù)。帶權(quán)路徑長度：——高度：——雙分支結(jié)點(diǎn)數(shù)：——。四、閱讀算法，回答問題(每小題8分，共16分)1．VOldAC(List&L){InitList(L)；InsertRear(L;25)；InsertFront(L，50)；IntaL4]={5，8，12，15，36};for(inti=O;i〈5;i++)if(a[i]%2==0)InsertFront(L，a[i])；elselnsertRear(L，a[i])；}該算法被調(diào)用執(zhí)行后，得到的線性表L為：2．voidAG(Queue&Q){InitQueue(Q)；inta[5]={6，12，5，15，8}；for(inti=0;i〈5;i++)QInsert(Q，a[i])；QInsert(Q，QDelete(Q))；QInsert(Q，20)；QInsert(Q，QDelete(Q)十16)；while(!QueueEmpty(Q))cout〈〈QDelete(Q)〈〈”；}該算法被調(diào)用后得到的輸出結(jié)果為：五、算法填空，在畫有橫線的地方填寫合適的容(每小題6分，共12分)從一維數(shù)組A[n)中二分查找關(guān)鍵字為K的元素的遞歸算法，若查找成功則返回對(duì)應(yīng)元素的下標(biāo)，否則返回一1。IntBinsch(ElemTypeA[]，Intlow，inthigh，KeyTypeK){if(low〈=high){intmid=(low+high)/2；if(K==A[mid].key)；elseif(K〈A[mid].key)——；else；}elsereturn—l；}已知二叉樹中的結(jié)點(diǎn)類型BinTreeNode定義為：structBinTreeNode{ElemTypedata；BinTreeNode*left，*right}；其中data為結(jié)點(diǎn)值域，left和right分別為指向左、右子女結(jié)點(diǎn)的指針域。下面函數(shù)的功能是返回二叉樹BT中值為x的結(jié)點(diǎn)所在的層號(hào)，請(qǐng)?jiān)趧澯袡M線的地方填寫合適容。IntNodeLevel（BinTreeNode*BT，ElemTypeX）{if（BT：=NULL）return0；//空樹的層號(hào)為0elseif（BT—〉data==X）return1;//根結(jié)點(diǎn)的層號(hào)為1//向子樹中查找x結(jié)點(diǎn)else{intcl=NodeLevel（BT—〉left,X）；if（cl〉=1）returncl+1;intc2=；if——；//若樹中不存在X結(jié)點(diǎn)則返回oelsereturn0；}}六、編寫算法（8分）按所給函數(shù)聲明編寫一個(gè)算法，從表頭指針為HL的單鏈表中查找出具有最大值的結(jié)點(diǎn)，該最大值由函數(shù)返回，若單鏈表為空則中止運(yùn)行。EIemTypeMaxValue（LNOde*HL）;“數(shù)據(jù)結(jié)構(gòu)”期末考試試題答案一、單選題（每小題2分，共12分）評(píng)分標(biāo)準(zhǔn)；選對(duì)者得2分，否則不得分。1．B2．B3．C4．D5．B6．A二、填空題（每空1分，共28分）1．順序結(jié)構(gòu)結(jié)構(gòu)索引結(jié)構(gòu)散列結(jié)構(gòu)（次序無先后）2?值（或data）子表指針（或sublist）3．3x2．45/6一*十（3h一一1）/2TOC\o"1-5"\h\z5186?小于大于（或大于等于）向上堆頂鄰接矩陣鄰接表邊集數(shù)組（次序無先后）9.O（n2）O（e）10.1311.13O（）同一層插人選擇14.O（nlogn）O（n）22三、運(yùn)算題（每小題6分，共24分）TOC\o"1-5"\h\z1?先序：a，b，c，d，e，f，e//2分中序：c，b,d,a,f,8,e//2分后序：c,d,b,e,f,e,a//2分2?最小生成樹的權(quán)：31//6分（84,79,56,42,40,46,50,38）//6分4?帶權(quán)路徑長度：131//3分高度：5／／2分雙分支結(jié)點(diǎn)數(shù)：6／／1分四、閱讀算法，回答問題（每小題8分，共16分）評(píng)分標(biāo)準(zhǔn)：每小題正確得8分，出現(xiàn)一處錯(cuò)誤扣4分，兩處及以上錯(cuò)誤不得分1．（36，12，8，50，25，5，15）2．515862028五、算法填空，在畫有橫線的地方填寫合適的容（每小題6分，共12分）1．feturnmid／／2分returnBinsch（A,low,mid一1,K）//2分returnBmsch（A，mid+1，high，K）／／2分2.NodeLevel（BT—〉right,X）//3分（c2〉=l）returnc2十1//3分六、編寫算法（8分）評(píng)分標(biāo)準(zhǔn)：請(qǐng)參考語句后的注釋,或根據(jù)情況酌情給分。ElemTypeMaxValue（LNodeO*HL。）{if（HL==NUlL）{//2分cerr<<"Linkedllstisempty!”<<endl；exit（1）；}ElemTypemax：HL一〉data；//3分LNOde*p=HI一〉next；//4分while（P!：NULL）{//7分if（max〈p—〉data）max=p—〉data；p=p—〉next；}returnmax；//8分}數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料一、填空題數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R）,其中D是數(shù)據(jù)元素的有限集合,R是D上的關(guān)系有限集合。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算這三個(gè)方面的容。數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)戲有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)沒有—后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有前驅(qū)—結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)：葉子結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)。在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè)下載可編輯下載可編輯下載可編輯下載可編輯.專業(yè).整理..專業(yè).整理..專業(yè).整理..專業(yè).整理.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用四種基本的存儲(chǔ)方法表示，它們分別是順序、鏈?zhǔn)?、索引和散列。?shù)據(jù)的運(yùn)算最常用的有5種，它們分別是插入、刪除、修改、查找、排序。一個(gè)算法的效率可分為時(shí)間效率和空間—效率。在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半元素,具體移動(dòng)的元素個(gè)數(shù)與表長和該元素在表中的位置有關(guān)。線性表中結(jié)點(diǎn)的集合是有限的，結(jié)點(diǎn)間的關(guān)系是一對(duì)一的。向一個(gè)長度為n的向量的第i個(gè)元素（1WiWn+1）之前插入一個(gè)元素時(shí)，需向后移動(dòng)n-i+1_個(gè)元素。向一個(gè)長度為n的向量中刪除第i個(gè)元素（1WiWn）時(shí)，需向前移動(dòng)上丄_個(gè)元素。在順序表中訪問任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為0（1），因此,順序表也稱為隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)。順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。18?在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指示。在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為0（n。向量、棧和隊(duì)列都是_線性_結(jié)構(gòu)，可以在向量的任何位置插入和刪除元素；對(duì)于棧只能在棧頂插入和刪除元素：對(duì)于隊(duì)列只能在隊(duì)尾—插入和隊(duì)首刪除元素。棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂—。不允許插入和刪除運(yùn)算的一端稱為棧底。隊(duì)列—是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。不包含任何字余（長度為0的串稱為空串：由一個(gè)或多個(gè)空格（僅由空格符組成的串稱為空白串。子串的定位運(yùn)算稱為串的模式匹配:被匹配的主串—稱為目標(biāo)串，子串—稱為模式。假設(shè)有二維數(shù)組A，每個(gè)元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置6X8（基地址）為1000,則數(shù)組A的體積（存儲(chǔ)量）為288B：末尾元素A57的第一個(gè)字節(jié)地址為_1282:若按行存儲(chǔ)時(shí)，元素A的第一個(gè)字節(jié)地址為（8+4）X6+1000=1072:若按列存儲(chǔ)時(shí)，元14素A的第一個(gè)字節(jié)地址為（6X7+4）X6+1000）=127647由3個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有5—種形態(tài)。一棵深度為6的滿二叉樹有n+n=0+叮n-1=31_個(gè)分支結(jié)點(diǎn)和26-1=32個(gè)葉子。注：滿二叉樹沒有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)。一棵具有257個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度為9（注：用L噸㈤」+1=L8.xx」+1=9設(shè)一棵完全二叉樹有700個(gè)結(jié)點(diǎn)，則共有350個(gè)葉子結(jié)點(diǎn)。答：最快方法：用葉子數(shù)=[n/2]=350設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有500個(gè)葉子結(jié)點(diǎn)，有499—個(gè)度為2的結(jié)點(diǎn)，有1個(gè)結(jié)點(diǎn)只有非空左子樹，有0—個(gè)結(jié)點(diǎn)只有非空右子樹。答：最快方法：用葉子數(shù)=[n/2]=500，n=n-1=499。另外，最后一結(jié)點(diǎn)為2i屬于左葉子，右葉子是20空的，所以有1個(gè)非空左子樹。完全二叉樹的特點(diǎn)決定不可能有左空右不空的情況，所以非空右子樹數(shù)=0.在數(shù)據(jù)的存放無規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是順序查找（線性查找）。線性有序表（a，a，a,…，a）是從小到大排列的，對(duì)一個(gè)給定的值k，用二分法檢索表中與k相123256等的元素，在查找不成功的情況下，最多需要檢索8—次。設(shè)有100個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比較次數(shù)是7_。假設(shè)在有序線性表a[20]上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1：比較兩次查找成功的結(jié)點(diǎn)數(shù)為2:比較四次查找成功的結(jié)點(diǎn)數(shù)為8:平均查找長度為3.7。解：顯然，平均查找長度=0（log2n）<5次（25）。但具體是多少次，則不應(yīng)當(dāng)按照公式ASL=log2(n+1)來計(jì)算(即(21Xlog221)/20=4.6次并不正確！)。因?yàn)檫@是在假設(shè)n=2m-1的情況下ASL=全部元素的查找次數(shù)為=(1+2X2+4X3+8X4+5X5)=74；ASL=74/20=3.7!!!34．折半查找有序表(4，6，12，20，28，38，50，70，88，100)，若查找表中元素20，它將依次與表中元素28,6,12,20比較大小。在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是暑列查^_。散列法存儲(chǔ)的基本思想是由關(guān)鍵字的值決定數(shù)據(jù)的存儲(chǔ)地址。二、判斷正誤(在正確的說法后面打勾，反之打叉)(X)1.鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。答：錯(cuò)誤。鏈表中的結(jié)點(diǎn)可含多個(gè)指針域,分別存放多個(gè)指針。例如,雙向鏈表中的結(jié)點(diǎn)可以含有兩個(gè)指針域,分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針。(X)2.鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。錯(cuò),鏈表的存儲(chǔ)結(jié)構(gòu)特點(diǎn)是無序,而鏈表的示意圖有序。(X)3.鏈表的刪除算法很簡單,因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后,計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向前移動(dòng)。錯(cuò),鏈表的結(jié)點(diǎn)不會(huì)移動(dòng),只是指針容改變。(X)4.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型,而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。錯(cuò),混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu),鏈表也是線性表!且即使是順序表,也能存放記錄型數(shù)據(jù)。(X)5.順序表結(jié)構(gòu)適宜于進(jìn)行順序存取,而鏈表適宜于進(jìn)行隨機(jī)存取。錯(cuò),正好說反了。順序表才適合隨機(jī)存取,鏈表恰恰適于“順藤摸瓜”(X)6.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大,且插入、刪除運(yùn)算效率高。錯(cuò),前一半正確,但后一半說法錯(cuò)誤,那是鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)。順序存儲(chǔ)方式插入、刪除運(yùn)算效率較低,在表長為n的順序表中，插入和刪除一個(gè)數(shù)據(jù)元素，平均需移動(dòng)表長一半個(gè)數(shù)的數(shù)據(jù)元素。(X)7.線性表在物理存儲(chǔ)空間中也一定是連續(xù)的。錯(cuò),線性表有兩種存儲(chǔ)方式,順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。后者不要求連續(xù)存放。(X)8.線性表在順序存儲(chǔ)時(shí),邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰。錯(cuò)誤。線性表有兩種存儲(chǔ)方式,在順序存儲(chǔ)時(shí),邏輯上相鄰的元素在存儲(chǔ)的物理位置次序上也相鄰。(X)9.順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。錯(cuò)誤。順序存儲(chǔ)方式不僅能用于存儲(chǔ)線性結(jié)構(gòu),還可以用來存放非線性結(jié)構(gòu),例如完全二叉樹是屬于非線性結(jié)構(gòu),但其最佳存儲(chǔ)方式是順序存儲(chǔ)方式。(后一節(jié)介紹)(X)10.線性表的邏輯順序與存儲(chǔ)順序總是一致的。錯(cuò),理由同7。鏈?zhǔn)酱鎯?chǔ)就無需一致。(X)11.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型,而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。錯(cuò),線性表是邏輯結(jié)構(gòu)概念,可以順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ),與元素?cái)?shù)據(jù)類型無關(guān)。(X)12.在表結(jié)構(gòu)中最常用的是線性表,棧和隊(duì)列不太常用。錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)常用，CPU中也用隊(duì)列。(V)13.棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。V)14.對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。正確，都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。(X)15.棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。錯(cuò)，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是存儲(chǔ)結(jié)構(gòu)概念，二者不是同類項(xiàng)。(X)16.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。錯(cuò)，他們都是線性邏輯結(jié)構(gòu)，棧和隊(duì)列其實(shí)是特殊的線性表，對(duì)運(yùn)算的定義略有不同而已。(V)17.棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是方式。(V)18.兩個(gè)棧共享一片連續(xù)存空間時(shí)，為提高存利用率，減少溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片存空間的兩端。(X)19.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。錯(cuò)，后半句不對(duì)。(X)20.一個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。錯(cuò)，有可能。丿)21.若二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n個(gè)結(jié)點(diǎn)的二叉樹鏈表中只有n—1個(gè)非空指針域。X)22.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹的高度差等于1。丿)23.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。(X)24.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空子樹或有兩棵空子樹。(X)25.二叉樹中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹(若存在的話)所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空子樹(若存在的話)所有結(jié)點(diǎn)的關(guān)鍵字值。(應(yīng)當(dāng)是二叉排序樹的特點(diǎn))X)26.二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是2k-i-1，其中k是樹的深度(應(yīng)2i-1)X)27.二叉樹中所有結(jié)點(diǎn)，如果不存在非空左子樹，則不存在非空右子樹。X)28?對(duì)于一棵非空二叉樹，它的根結(jié)點(diǎn)作為第一層，則它的第i層上最多能有2i—1個(gè)結(jié)點(diǎn)(應(yīng)2i-1)(丿)29?用二叉鏈表法(link-rlink)存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。(丿)30.具有12個(gè)結(jié)點(diǎn)的完全二叉樹有5個(gè)度為2的結(jié)點(diǎn)。三、單項(xiàng)選擇題(B)1.非線性結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種：A)—對(duì)多關(guān)系B)多對(duì)多關(guān)系C)多對(duì)一關(guān)系D)—對(duì)一關(guān)系C)2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的.結(jié)構(gòu)；A)存儲(chǔ)B)物理C)邏輯D)物理和存儲(chǔ)(C)3.算法分析的目的是：A)找出數(shù)據(jù)結(jié)構(gòu)的合理性B)研究算法中的輸入和輸出的關(guān)系C)分析算法的效率以求改進(jìn)D)分析算法的易懂性和文檔性(A)4.算法分析的兩個(gè)主要方面是：A)空間復(fù)雜性和時(shí)間復(fù)雜性B)正確性和簡明性C)可讀性和文檔性D)數(shù)據(jù)復(fù)雜性和程序復(fù)雜性(C)5.計(jì)算機(jī)算法指的是：A)計(jì)算方法B)排序方法C)解決問題的有限運(yùn)算序列D)調(diào)度方法B)6.計(jì)算機(jī)算法必須具備輸入、輸出和.等5個(gè)特性。A)可行性、可移植性和可擴(kuò)充性B)可行性、確定性和有窮性C)確定性、有窮性和穩(wěn)定性D)易讀性、穩(wěn)定性和安全性(C)7．?dāng)?shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：存儲(chǔ)結(jié)構(gòu)(B)邏輯結(jié)構(gòu)(C)順序存儲(chǔ)結(jié)構(gòu)(D)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B)8.—個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素的長度為2,則第5個(gè)元素的地址是(A)110(B)108(C)100(D)120A)9.在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是：訪問第i個(gè)結(jié)點(diǎn)(1<iVn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2<i<n)在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)(1ViVn)刪除第i個(gè)結(jié)點(diǎn)(1<iVn)將n個(gè)結(jié)點(diǎn)從小到大排序(B)10.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)—個(gè)元(A)8(B)63.5(C)63(D)7(A)11.存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間：

分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針只有一部分，存放結(jié)點(diǎn)值只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)(B)12.鏈表是一種采用存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表；(A)順序(B)鏈?zhǔn)?C)星式(D)網(wǎng)狀D)13.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求存中可用存儲(chǔ)單元的地址:(A)必須是連續(xù)的(B)部分地址必須是連續(xù)的(C)一定是不連續(xù)的(D)連續(xù)或不連續(xù)都可以(B)14.線性表L在情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。(A)需經(jīng)常修改(A)需經(jīng)常修改L中的結(jié)點(diǎn)值(C)L中含有大量的結(jié)點(diǎn)B)15.棧中元素的進(jìn)出原則是先進(jìn)先出B.后進(jìn)先出(B)需不斷對(duì)L進(jìn)行刪除插入(D)L中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜C.?？談t進(jìn)D.棧滿則出(C)16.若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為pl，p2，p3，…，pn，若p1=n,則pi為iB.n=iC.n-i+1D.不確定(B)17.判定一個(gè)棧ST(最多元素為mO)為空的條件是A.ST->top<>0B.ST->top=0C.ST->top<>mOD.ST->top=mOA.ST->top<>0B.ST->top=0C.ST->top<>mOD.ST->top=mO(C)18.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的倍。A.1/2B.1C.2D.4(B)19.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍。A.1/2B.1C.2D.4(B)20.有8個(gè)結(jié)點(diǎn)的無向圖最多有條邊。A.14B.28C.56D.112(C)21.有8個(gè)結(jié)點(diǎn)的有向完全圖有條邊。A.14B.28C.56D.112(B)22.在表長為n的鏈表中進(jìn)行線性查找，它的平均查找長度為ASL=n;B.ASL=(n+l)/2;C.ASL=、n+l；D.ASL^log2(n+l)-l(A)23.折半查找有序表(4,6，10，12,20，30,50,70,88，100)。若查找表中元素58,則它將依次與表中比較大小，查找結(jié)果是失敗。20,70,30,50B.30,88,70,50C.20,50D.30,88,50(C)24.對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較次關(guān)鍵字。3B.4C.5D.6A)25.鏈表適用于查找順序B.二分法C.順序，也能二分法D.隨機(jī)《數(shù)據(jù)結(jié)構(gòu)與算法》復(fù)習(xí)題一、選擇題。1.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為C。動(dòng)態(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.部結(jié)構(gòu)和外部結(jié)構(gòu)2?數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)存中的表示是指A。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)B.數(shù)據(jù)結(jié)構(gòu)C.數(shù)據(jù)的邏輯結(jié)構(gòu)D.數(shù)據(jù)元素之間的關(guān)系在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的A結(jié)構(gòu)。邏輯B.存儲(chǔ)C.邏輯和存儲(chǔ)D.物理在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，而且還要存儲(chǔ)C。數(shù)據(jù)的處理方法B.數(shù)據(jù)元素的類型C.數(shù)據(jù)元素之間的關(guān)系D.數(shù)據(jù)的存儲(chǔ)方法在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮_A_。各結(jié)點(diǎn)的值如何B.結(jié)點(diǎn)個(gè)數(shù)的多少C.對(duì)數(shù)據(jù)有哪些運(yùn)算D.所用的編程語言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便。以下說法正確的是。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位數(shù)據(jù)元素是數(shù)據(jù)的最小單位數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)項(xiàng)的集合—些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)算法分析的目的是C，算法分析的兩個(gè)主要方面是」A.找出數(shù)據(jù)結(jié)構(gòu)的合理性A.找出數(shù)據(jù)結(jié)構(gòu)的合理性C.分析算法的效率以求改進(jìn)A.空間復(fù)雜度和時(shí)間復(fù)雜度C.可讀性和文檔性研究算法中的輸入和輸出的關(guān)系分析算法的易讀性和文檔性正確性和簡明性數(shù)據(jù)復(fù)雜性和程序復(fù)雜性8?下面程序段的時(shí)間復(fù)雜度是s=0;for(I=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;9?下面程序段的時(shí)間復(fù)雜度是for(i=0;i〈n;i++)for(j=0;j<m;j++)A[i][j]=0;10?下面程序段的時(shí)間復(fù)雜度是O(logn)3i=0；while(i〈=n)i=i*3；在以下的敘述中，正確的是B。線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu)二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表?xiàng)５牟僮鞣绞绞窍冗M(jìn)先出隊(duì)列的操作方式是先進(jìn)后出通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著丄。A.數(shù)據(jù)元素具有同一特點(diǎn)不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)的數(shù)據(jù)項(xiàng)的類型要一致每個(gè)數(shù)據(jù)元素都一樣數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等TOC\o"1-5"\h\z13?鏈表不具備的特點(diǎn)是A?？呻S機(jī)訪問任一結(jié)點(diǎn)B.插入刪除不需要移動(dòng)元素不必事先估計(jì)存儲(chǔ)空間D.所需空間與其長度成正比14?不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是A。A.head==NULLBhead-〉next==NULLC.head-〉next==headDhead!二NULL15?帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是B。A.head==NULLBhead-〉next==NULLC.head-〉next==headDhead!二NULL16?若某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)，則采用D存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表B.給出表頭指針的單循環(huán)鏈表C.雙鏈表D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表17?需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是B。A.單鏈表B.靜態(tài)鏈表C.線性鏈表D.順序存儲(chǔ)結(jié)構(gòu)18?非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向)滿足_。A.p->next==NULLB.p==NULLC.p-〉next==headD.p==head19?在循環(huán)雙鏈表的p所指的結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是D。p-〉prior=s；s-〉next=p；p-〉prior-〉next=s；s-〉prior=p-〉priorp-〉prior=s；p-〉prior-〉next=s；s-〉next=p；s-〉prior=p-〉priors-〉next=p；s-〉prior=p-〉prior；p-〉prior=s；p-〉prior-〉next=ss-〉next=p；s-〉prior=p-〉prior；p-〉prior-〉next=s；p-〉prior=s20?如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用存儲(chǔ)方式最節(jié)省時(shí)間。A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表21?在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是氐。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)22?在一個(gè)長度為n(n>1)的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行B操作與鏈表的長度有關(guān)。刪除單鏈表中的第一個(gè)元素刪除單鏈表中的最后一個(gè)元素在單鏈表第一個(gè)元素前插入一個(gè)新元素在單鏈表最后一個(gè)元素后插入一個(gè)新元素23?與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是D。插入、刪除操作更簡單可以進(jìn)行隨機(jī)訪問可以省略表頭指針或表尾指針順序訪問相鄰結(jié)點(diǎn)更靈活24．如果對(duì)線性表的操作只有兩種，即刪除第一個(gè)元素，在最后一個(gè)元素的后面插入新元素，則最好使用B_。只有表頭指針沒有表尾指針的循環(huán)單鏈表只有表尾指針沒有表頭指針的循環(huán)單鏈表非循環(huán)雙鏈表循環(huán)雙鏈表在長度為n的順序表的第i個(gè)位置上插入一個(gè)元素(1WiWn+1),元素的移動(dòng)次數(shù)為：AA.n-i+1B.n-iC.iD.i-1對(duì)于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為C。A.順序表B.用頭指針表示的循環(huán)單鏈表C.用尾指針表示的循環(huán)單鏈表D.單鏈表下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？C。A插入運(yùn)算方便B可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示C存儲(chǔ)密度大D刪除運(yùn)算方便下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？BA線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作。線性表是具有n個(gè)B的有限序列。A.字符B.數(shù)據(jù)元素C.數(shù)據(jù)項(xiàng)D.表元素在n個(gè)結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中，算法的時(shí)間復(fù)雜度是0(1)的操作是A。訪問第i(1〈二i〈二n)個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(1〈i〈二n)在第i(1〈二i〈二n)個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)刪除第i(1〈二i〈=n)個(gè)結(jié)點(diǎn)以上都不對(duì)若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為C。A.0(0)B.0(1)C.0(n)D.0(n2)32?對(duì)于順序存儲(chǔ)的線性表，訪問結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為C。A.0(n)0(n)B.0(n)0(1)C.0(1)0(n)D.0(1)0(1)33.線性表(a1,a2,…,an)以鏈?zhǔn)椒绞酱鎯?chǔ)，訪問第i位置元素的時(shí)間復(fù)雜度為C。0(0)B.0(1)C.0(n)D.O(n2)單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了—。A.使單鏈表至少有一個(gè)結(jié)點(diǎn)B.標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C.方面運(yùn)算的實(shí)現(xiàn)D.說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是B。A.p->next=s；s->next=p->nextB.s->next=p->next；p->next=s;C.p->next=s；p->next=s->nextD.p->next=s->next；p->next=s線性表的順序存儲(chǔ)結(jié)構(gòu)是一種A。A.隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)B.順序存取的存儲(chǔ)結(jié)構(gòu)C.索引存取的存儲(chǔ)結(jié)構(gòu)D.Hash存取的存儲(chǔ)結(jié)構(gòu)37?棧的特點(diǎn)是B，隊(duì)列的特點(diǎn)是A。A.先進(jìn)先出B.先進(jìn)后出棧和隊(duì)列的共同點(diǎn)是C。A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)—個(gè)棧的進(jìn)棧序列是a,b,c,d,e,則棧的不可能的輸出序列是C。A.edcbaB.decbaC.dceabD.abcde40?設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)锳、B、C、D、E。下列C是不可能的出棧序列。A.A,B,C,D,EB.B,C,D,E,AC.E,A,B,C,DD.E,D,C,B,A以下B不是隊(duì)列的基本運(yùn)算？A.從隊(duì)尾插入一個(gè)新元素B.從隊(duì)列中刪除第i個(gè)元素C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值若已知一個(gè)棧的進(jìn)棧序列是1,2,3,,n,其輸出序列為pl,p2,p3,…，pn,若p1=n,則pi為CA.iB.n-iC.n—i+1D.不確定43?判定一個(gè)順序棧st(最多元素為MaxSize)為空的條件是B。A.st->top!=-1B.st->top==-1C.st->top!=MaxSizeD.st->top==MaxSize44?判定一個(gè)順序棧st(最多元素為MaxSize)為滿的條件是D。A.st-〉top!=-1B.st-〉top==-1C.st->top!=MaxSizeD.st->top==MaxSize45.一個(gè)隊(duì)列的入隊(duì)序列是1,2,3,4,則隊(duì)列的輸出序列是_。A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1下載可編輯下載可編輯下載可編輯下載可編輯.專業(yè).整理..專業(yè).整理..專業(yè).整理..專業(yè).整理.46?判定一個(gè)循環(huán)隊(duì)列qu（最多元素為MaxSize）為空的條件是C。qu->rear-qu—〉front==MaxSizeB.qu->rear-qu—〉frontT==MaxSizeC.qu->rear==qu->frontD.qu->rear=qu->frontT47?在循環(huán)隊(duì)列中，若front與rear分別表示對(duì)頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條件是C。front==rear+1B.rear==front+1C.front==rearD.front==048?向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行操作。h-〉next=s;B.s-〉next=h;C.s-〉next=h;h=s;D.s-〉next=h-〉next;h-〉next=s;TOC\o"1-5"\h\z49?輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過的棧操作為_。A.push，pop，push，pop，push，popB.push，push，push，pop，pop，popC.push，push，pop，pop，push，popD.push，pop，push，push，pop，pop50?若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V[1m]，top[1]、top[2]分別代表第1和第2個(gè)棧的棧頂，棧1的底在V[1]，棧2的底在V[m]，則棧滿的條件是—。A.|top[2]-top[1]|=0B.top[1]+1二top[2]C.top[1]+top[2]=mD.top[1]=top[2]51?設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用D數(shù)據(jù)結(jié)構(gòu)最佳。A.線性表的順序存儲(chǔ)結(jié)構(gòu)B.隊(duì)列C.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.棧52?允許對(duì)隊(duì)列進(jìn)行的操作有D。A.對(duì)隊(duì)列中的元素排序B.取出最近進(jìn)隊(duì)的元素C.在隊(duì)頭元素之前插入元素D.刪除隊(duì)頭元素53?對(duì)于循環(huán)隊(duì)列53?對(duì)于循環(huán)隊(duì)列D。A.無法判斷隊(duì)列是否為空C.隊(duì)列不可能滿無法判斷隊(duì)列是否為滿以上說法都不對(duì)54.若用一個(gè)大小為6的數(shù)值來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為B。A.1和5B.2和4C.4和2D.5和155?隊(duì)列的“先進(jìn)先出”特性是指丿—。最早插入隊(duì)列中的元素總是最后被刪除當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先每當(dāng)有刪除操作時(shí)，總是要先做一次插入操作每次從隊(duì)列中刪除的總是最早插入的元素56?和順序棧相比，鏈棧有一個(gè)比較明顯的優(yōu)勢是A。A.通常不會(huì)出現(xiàn)棧滿的情況B.通常不會(huì)出現(xiàn)?？盏那闆r插入操作更容易實(shí)現(xiàn)D.刪除操作更容易實(shí)現(xiàn)57?用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，其頭指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行出隊(duì)操作

時(shí)C。B.僅修改隊(duì)尾指針D.B.僅修改隊(duì)尾指針D.隊(duì)頭、隊(duì)尾指針都要修改C.隊(duì)頭、隊(duì)尾指針都可能要修改若串S=‘software',其子串的數(shù)目是BA.8B.37C.36D.9串的長度是指—。串的長度是指—。A.串中所含不同字母的個(gè)數(shù)C.串中所含不同字符的個(gè)數(shù)串中所含字符的個(gè)數(shù)串中所含非空格字符的個(gè)數(shù)串是一種特殊的線性表，其特殊性體現(xiàn)在BA.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符可以鏈?zhǔn)酱鎯?chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符61?設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱為BA.連接B.模式匹配C.求子串D.求串長TOC\o"1-5"\h\z數(shù)組A中，每個(gè)元素的長度為3個(gè)字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首地址SA開始連續(xù)存放的存儲(chǔ)器，該數(shù)組按行存放，元素A[8][5]的起始地址為_。A.SA+141B.SA+144C.SA+222D.SA+225數(shù)組A中，每個(gè)元素的長度為3個(gè)字節(jié)，行下標(biāo)i從1到8,列下標(biāo)j從1到10,從首地址SA開始連續(xù)存放的存儲(chǔ)器，該數(shù)組按行存放，元素A[5][8]的起始地址為C。A.SA+141B.SA+180C.SA+222D.SA+225若聲明一個(gè)浮點(diǎn)數(shù)數(shù)組如下：froataverage[]=newfloat[30];假設(shè)該數(shù)組的存起始位置為200,average[15]的存地址是—。A.214B.215C.260D.25665?設(shè)二維數(shù)組A[1???m,1???n]按行存儲(chǔ)在數(shù)組B中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為A_。A.n*(i-1)+jB.n*(i-1)+j-1C.i*(jT)D.j*m+i-1TOC\o"1-5"\h\z66?有一個(gè)100X90的稀疏矩陣，非0元素有10，設(shè)每個(gè)整型數(shù)占2個(gè)字節(jié)，則用三元組表示該矩陣時(shí),所需的字節(jié)數(shù)是B。A.20B.66C.18000D.3367.數(shù)組A[0…4,-1…-3,5…了]中含有的元素個(gè)數(shù)是A。A.55B.45C.36D.1668?對(duì)矩陣講行壓縮存儲(chǔ)是為了D。A.方便運(yùn)算B.方便存儲(chǔ)C.提高運(yùn)算速度D.減少存儲(chǔ)空間69?設(shè)有一個(gè)10階的對(duì)稱矩陣A,采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a為第一個(gè)元素，其存儲(chǔ)地址1，1為1,每個(gè)元素占1個(gè)地址空間，則a的地址為B。8,5

A．13B．33C．18D．4070?稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種,即A．13B．33C．18D．4070?稀疏矩陣一般的壓縮存儲(chǔ)方式有兩種,即CA.二維數(shù)組和三維數(shù)組C.三元組和十字鏈表三元組和散列散列和十字鏈表71?樹最適合用來表示―。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)72?深度為5的二叉樹至多有C個(gè)結(jié)點(diǎn)。A.16B.32C.31C.1073?對(duì)一個(gè)滿二叉樹，m個(gè)葉子，n個(gè)結(jié)點(diǎn)，深度為h,則_。A.n=h+mBh+m=2nCm=hTDn=2h-1TOC\o"1-5"\h\z74?任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對(duì)次序A。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對(duì)還是線索化信森林F中第一75?在線索化樹中，每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息,息，若0標(biāo)識(shí)樹結(jié)構(gòu)信息，1還是線索化信森林F中第一A.00B.01C.10D.1176?在下述論述中，正確的是一D。①只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0;②二叉樹的度為2；③二叉樹的左右子樹可任意交換；④深度為K的順序二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。A.①②③B.②③④C.②④D.①④77?設(shè)森林F對(duì)應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p，p的右子樹的結(jié)點(diǎn)個(gè)數(shù)為n，棵樹的結(jié)點(diǎn)的個(gè)數(shù)是A。A.m-nB.m-nTC.n+1D.不能確定78?若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)的個(gè)數(shù)是一A.9B.11C.15D.不能確定79?具有10個(gè)葉子結(jié)點(diǎn)的二叉樹中有B個(gè)度為2的結(jié)點(diǎn)。A.8B.9C.10D.1180?在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的C倍。TOC\o"1-5"\h\zA.1/2B1C2D481?在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的_^倍。A.1/2B1C2D482?某二叉樹結(jié)點(diǎn)的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左子樹中結(jié)點(diǎn)數(shù)目為A.3B.2C.4D.5已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E,后綴形式為ABC*+DE/-,其前綴形式為DA.-A+B*C/DE-A+B*CD/EC-A.-A+B*C/DE-A+B*CD/EC-+*ABC/DE-+A*BC/DEabecdf法進(jìn)行遍歷，則可歷，則可能得到的①A.a，abecdf法進(jìn)行遍歷，則可歷，則可能得到的①A.a，b，e，c，d，fB.a，c，f，e，b，dC.a，e，b，c，f，d，D.a，e，d，f，c，b②A.a，b，c，e，d，fB.a，b，c，e，f，dC.a，e，b，c，f，d，D.a，c，f，d，e，b能得到的一種頂點(diǎn)序列為D;按廣度搜索法進(jìn)行遍一種頂點(diǎn)序列為A；已知一個(gè)圖，如圖所示，若從頂點(diǎn)a出發(fā)按深度搜索TOC\o"1-5"\h\z采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類似于二叉樹的A,A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的D,A.先序遍歷B.中序遍歷C.后序遍歷D.按層遍歷具有n個(gè)結(jié)點(diǎn)的連通圖至少有A條邊。A.n-1B.nC.n（nT）/2D.2n88.廣義表（（a），a）的表頭是C，表尾是C。A.aB（）C(a)D((a))89.廣義表（a））的表頭是C，表尾是B。A.aB（）C(a)D((a))90?順序查找法適合于存儲(chǔ)結(jié)構(gòu)為B的線性表。A散列存儲(chǔ)B順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C壓縮存儲(chǔ)D索引存儲(chǔ)TOC\o"1-5"\h\z對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須B。A以順序方式存儲(chǔ)B以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列C以鏈?zhǔn)椒绞酱鎯?chǔ)D以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列采用折半查找法查找長度為n的線性表時(shí)，每個(gè)元素的平均查找長度為D。AO（n2）BO（nlogn）CO（n）DO（logn）2293?有一個(gè)有序表為｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，當(dāng)折半查找值為82的結(jié)點(diǎn)時(shí)，_C次比較后查找成功。A.11B5C4D8二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法B。A正確B錯(cuò)誤下面關(guān)于B樹和B+樹的敘述中，不正確的結(jié)論是A。下載可編輯下載可編輯.專業(yè).整理..專業(yè).整理.AB樹和B+樹都能有效的支持順序查找BB樹和B+樹都能有效的支持隨機(jī)查找CB樹和B+樹都是平衡的多叉樹DB樹和B+樹都可用于文件索引結(jié)構(gòu)以下說法錯(cuò)誤的是B。散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針。負(fù)載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的飽滿程度。散列表的查找效率主要取決于散列表構(gòu)造時(shí)選取的散列函數(shù)和處理沖突的方法。查找效率最高的二叉排序樹是。所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹。所有結(jié)點(diǎn)的右子樹都為空的二叉排序樹。平衡二叉樹。沒有左子樹的二叉排序樹。98．排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為C。A.希爾排序B。冒泡排序C插入排序D。選擇排序在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是D。A.希爾排序B.冒泡排序C.直接插入排序D.直接選擇排序堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序列D是一個(gè)堆。A．94,31,53,23,16,7216,53,23,94,31,72A．94,31,53,23,16,7216,53,23,94,31,72堆排序是一種BA.插入B.選擇94,53,31,72,16,2316,31,23,94,53,72排序。交換D.歸并D在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率高。A.順序查找B.折半查找C.分塊查找D.插入直接選擇排序的時(shí)間復(fù)雜度為D。(n為元素個(gè)數(shù))A.O(n)B.0(logn)C.O(nlogn)D.0(n2)22二、填空題。數(shù)據(jù)邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱非線性結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)4種。在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn);最后一個(gè)結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。4?線性結(jié)構(gòu)中元素之間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對(duì)多關(guān)系。在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn);葉子結(jié)點(diǎn)沒有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以任意多個(gè)。數(shù)據(jù)結(jié)構(gòu)的基本存儲(chǔ)方法是順序、鏈?zhǔn)?、索引和散列存?chǔ)。衡量一個(gè)算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和時(shí)間復(fù)雜度與空間復(fù)雜度。8?評(píng)估一個(gè)算法的優(yōu)劣，通常從時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面考察。算法的5個(gè)重要特性是有窮性、確定性、可行性、輸入和輸出。在一個(gè)長度為n的順序表中刪除第i個(gè)元素時(shí)，需向前移動(dòng)n-i-1個(gè)元素。在單鏈表中，要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向前驅(qū)結(jié)點(diǎn)，另一個(gè)指向后繼結(jié)點(diǎn)。在順序表中插入或刪除一個(gè)數(shù)據(jù)元素，需要平均移動(dòng)n個(gè)數(shù)據(jù)元素，移動(dòng)數(shù)據(jù)元素的個(gè)數(shù)與位置有關(guān)。當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表的元素是，應(yīng)采用順序存儲(chǔ)結(jié)構(gòu)。根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成單鏈表和雙鏈表。16?順序存儲(chǔ)結(jié)構(gòu)是通過下標(biāo)表示兀素之間的關(guān)系的；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過指針表示兀素之間的關(guān)系的。17?帶頭結(jié)點(diǎn)的循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是L-〉next-〉next=L。18.棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表，其運(yùn)算遵循后進(jìn)先出的原則。19?空串是零個(gè)字符的串,其長度等于零?？瞻状怯梢粋€(gè)或多個(gè)空格字符組成的串，其長度等于其包含的空格個(gè)數(shù)。20?組成串的數(shù)據(jù)元素只能是單個(gè)字符。一個(gè)字符串中任意個(gè)連續(xù)字符構(gòu)成的部分稱為該串的子串。子串”str”在主串”datastrueture”中的位置是5。二維數(shù)組M的每個(gè)元素是6個(gè)字符組成的串，行下標(biāo)i的圍從0到8,列下標(biāo)j的圍從1到10,則存放M至少需要540個(gè)字節(jié);M的第8列和第5行共占108個(gè)字節(jié)。24?稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即三元組表和十字鏈表。25.廣義表((a),((b),c),(((d))))的長度是3，深度是4。26?在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有n0=TOC\o"1-5"\h\zn