1、“數據結構期末測試試題一、單項選擇題(每題2分,共12分)1.在一個單鏈表HL中,假設要向表頭插入一個由指針p指向的結點,那么執行().A.HL=pspnext=HLB.p一next=HL;HL=p3C.p一next=Hl;p=HL;D.p一next=HLnext;HLnext=p；2.n個頂點的強連通圖中至少含有().A.nl條有向邊B.n條有向邊C.n(n1)/2條有向邊D.n(n1)條有向邊3.從一棵二叉搜索樹中查找一個元素時,其時間復雜度大致為().A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)4.由權值分別為3,8,6,2,5的葉子結點生成一棵哈夫曼樹,它的帶權路徑長度為

2、().A.24B.48C.72D.535 .當一個作為實際傳遞的對象占用的存儲空間較大并可能需要修改時,應最好把它說明為()參數,以節省參數值的傳輸時間和存儲參數的空間.A.整形B.引用型C.指針型D.常值引用型6 .向一個長度為n的順序表中插人一個新元素的平均時間復雜度為().A.O(n)B.O(1)C.O(n2)D.O(10g2n)二、填空題(每空1分,共28分)1 數據的存儲結構被分為、和四種.2 在廣義表的存儲結構中,單元素結點與表元素結點有一個域對應不同,各自分別為域和域.3 中綴表達式3十x*(2.4/56)所對應的后綴表達式為.4 .在一棵高度為h的3叉樹中,最多含有一一結點.5

3、 .假定一棵二叉樹的結點數為18,那么它的最小深度為一一,最大深度為6 .在一棵二叉搜索樹中,每個分支結點的左子樹上所有結點的值一定一一該結點的值,右子樹上所有結點的值一定一一該結點的值.7 ,當向一個小根堆插入一個具有最小值的元素時,該元素需要逐層一一調整,直到被調整到一一位置為止.8 ,表本圖的三種存儲結構為、和.9 .對用鄰接矩陣表示的具有n個頂點和e條邊的圖進行任一種遍歷時,其時間復雜度為一一,對用鄰接表表示的圖進行任一種遍歷時,其時間復雜度為一一.10 .從有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素時,其查找長度分別為一一和11 .假定對長度

4、n=144的線性表進行索引順序查找,并假定每個子表的長度均為,那么進行索引順序查找的平均查找長度為一一,時間復雜度為12 .一棵B長樹中的所有葉子結點均處在一一上.13 ,每次從無序表中順序取出一個元素,把這插入到有序表中的適當位置,此種排序方法叫做一一排序；每次從無序表中挑選出一個最小或最大元素,把它交換到有序表的一端,此種排序方法叫做一一排序.14 .快速排序在乎均情況下的時間復雜度為一一,最壞情況下的時間復雜度為一一.三、運算題(每題6分,共24分)1 .假定一棵二叉樹廣義表表示為a(b(c,d),c(,8),分別寫出對它進行先序、中序、后序和后序遍歷的結果.先序：中序；后序：2 .一個

5、帶權圖的頂點集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,那么求出該圖的最小生成樹的權.最小生成樹的權；3 .假定一組記錄的排序碼為(46,79,56,38,40,84,50,42),那么利用堆排序方法建立的初始堆為一一.4 .有7個帶權結點,其權值分別為3,7,8,2,6,10,14,試以它們為葉子結點生成一棵哈夫曼樹,求出該樹的帶權路徑長度、高度、雙分支結點數.帶權路徑長度：一一長度：一一雙分支結點數：一一.四、閱讀算法,答復以下問題(每題8分,共16分)1 .VOl

6、dAC(List&L)InitList(L)；InsertRear(L;25);InsertFront(L,50);IntaL4=5,8,12,15,36;for(inti=0;i<5;i+)if(ai%2=0)InsertFront(L,ai)；elselnsertRear(L,ai)；該算法被調用執行后,得到的線性表L為：2 .voidAG(Queue&Q)InitQueue(Q)；inta5=6,12,5,15,8;for(inti=0;i<5;i+)QInsert(Q,ai)；QInsert(Q,QDelete(Q);QInsert(Q,20);QInser

7、t(Q,QDelete(Q)十16);while(!QueueEmpty(Q)cout<<QDelete(Q)<<該算法被調用后得到的輸出結果為：五、算法填空,在畫有橫線的地方填寫適宜的內容(每題6分,共12分)1.從一維數組An)中二分查找關鍵字為K的元素的遞歸算法,假設查找成功那么返回對應元素的下標,否那么返回一1.IntBinsch(ElemTypeA口,Intlow,inthigh,KeyTypeK)if(low<=high)intmid=(low+high)/2；if(K=Amid.key)；elseif(K<Amid.key)；else；else

8、returnl；2.二叉樹中的結點類型BinTreeNode定義為：structBinTreeNodeElemTypedata；BinTreeNode*left,*right；其中data為結點值域,left和right分別為指向左、右子女結點的指針域.下面函數的功能是返回二叉樹BT中值為x的結點所在的層號,請在劃有橫線的地方填寫適宜內容.IntNodeLevel(BinTreeNode*BT,ElemTypeX)if(BT:=NULL)return0;/空樹的層號為0elseif(BT一>data=X)return1;/根結點的層號為1/向子樹中查找x結點elseintcl=NodeL

9、evel(BT>left,X);if(cl>=1)returncl+1;intc2=；if；/假設樹中不存在X結點那么返回oelsereturn0；六、編寫算法(8分)按所給函數聲明編寫一個算法,從表頭指針為HL的單鏈表中查找出具有最大值的結點,該最大值由函數返回,假設單鏈表為空那么中止運行.ElemTypeMaxValue(LNOde*HL);“數據結構期末測試試題答案一、單項選擇題(每題2分,共12分)評分標準；選對者得2分,否那么不得分.1.B2,B3.C4.D5.B6,A二、填空題(每空1分,共28分)1.順序結構鏈接結構索引結構散列結構(次序無先后)2.值(或data)子

10、表指針(或sublist)3.3x2.45/6一*十4 .(3八一1)/25 .5186 .小于大于(或大于等于)7.向上堆頂8.鄰接矩陣鄰接表邊集數組(次序無先后)9.O(n2)O(e)10.1311,130()12 .同一層13 .插人選擇14 .O(nlog2n)O(n2)三、運算題(每題6分,共24分)1.先序：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.最小生成樹的權：31/6分3.(84,79,56,42,40,46,50,38)/6分4.帶權路徑長度：131/3分高度：5/2分雙分支結點數：6/1分四、閱讀算法,

11、答復以下問題(每題8分,共16分)評分標準：每題正確得8分,出現一處錯誤扣4分,兩處及以上錯誤不得分.1.(36,12,8,50,25,5,15)2.515862028五、算法填空,在畫有橫線的地方填寫適宜的內容(每題6分,共12分)1 .feturnmid/2分returnBinsch(A,low,mid1,K)/2分returnBmsch(A,mid+1,high,K)/2分2 .NodeLevel(BTright,X)/3分(c2>=1)returnc2十1/3分六、編寫算法(8分)評分標準：請參考語句后的注釋,或根據情況酌情給分.ElemTypeMaxValue(LNodeO*H

12、L.)if(HL=NUlL)/2分cerr<<"Linked11stisempty!"<<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分數據結構復習資料一、填空題1 .數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和運算等的學2 .數據結構被形式地定義為D,R,其中D是數據元素的有限集合,R是D

13、上的關系有限集合.3 .數據結構包括數據的邏輯結構、數據的存儲結構和數據的運算這三個方面的內容.4 .數據結構按邏輯結構可分為兩大類,它們分別是線性結構和非線性結構.5 .線性結構中元素之間存在一對一關系,樹形結構中元素之間存在一對多關系,圖形結構中元素之間存在多對多關系.6 .在線性結構中,第一個結點沒有前驅結點、其余每個結點有且只有1個前驅結點；最后一個結點沒有后續結點、其余每個結點有且只有1個后續結點.7 .在樹形結構中,樹根結點沒有前驅結點、其余每個結點有且只有1個前驅結點;葉子結點沒有后續結點、其余每個結點的后續結點數可以任意多個.8 .在圖形結構中,每個結點的前驅結點數和后續結點數

14、可以任意多個.9 .數據的存儲結構可用四種根本的存儲方法表示,它們分別是順序、鏈式、索引和散列.10 .數據的運算最常用的有5種,它們分別是插入、刪除、修改、查找、排序.11 .一個算法的效率可分為時間效率和空間效率.12 .在順序表中插入或刪除一個元素,需要平均移動表中一半元素、具體移動的元素個數與表長和該元素在表中的位置有13 .線性表中結點的集合是有限的、結點間的關系是一對一的.14 .向一個長度為n的向量的第i個元素1&iwn+1之前插入一個元素時,需向后移動n-i+1個元素.15 .向一個長度為n的向量中刪除第i個元素1&iwn時,需向前移動n-i個元素.16 .在順

15、序表中訪問任意一結點的時間復雜度均為O1,因此,順序表也稱為隨機存取的數據結構.17 .順序表中邏輯上相鄰的元素的物理位置35定相鄰.單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰.18 .在單鏈表中,除了首元結點外,任一結點的存儲位置由其直接前驅結點的鏈域的值指示.19 .在n個結點的單鏈表中要刪除結點*p、需找到它的前驅結點的地址,其時間復雜度為On.20 .向量、棧和隊列都是線忤結構,可以在向量的任何位置插入和刪除元素:對于棧只能在棧頂插入和刪除元素；對于隊列只能在隊尾插入和隊首刪除元素.21 .棧是一種特殊的線性表,一允許插入和刪除運算的一端稱為棧頂.不允許插入和刪除運算的一端稱為棧底.

16、22 .隊列是被限定為只能在表的一端進行插入運算,在表的另一端進行刪除運算的線性表.23 .不包含任何字符(長度為0)的串稱為空串；由一個或多個空格(僅由空格符)組成的串稱為空白串.24 .子串的定位運算稱為串的模式匹配;被匹配的主串稱為目標串,子串稱為模式.一25 .假設有二維數組A6X8,每個元素用相鄰的6個字節存儲,存儲器按字節編址.一A的起始存儲位置(基地址)為1000,那么數組A的體積(存儲量)為288B;末尾元素4的第一個字節地址為1282;假設按行存儲時,元素A4的第一個字節地址為(8+4)X6+1000=1072廠假設按列存儲時,元素A47的第一個字節畫E為一彳收7+4)X6+

17、1000)=1276.26 .由3個結點所構成的二叉樹有5種形態.27 .一棵深度為6的滿二叉樹有m+nz=0+n2=n°-1=31個分支結點和26-1=32個葉子.注：滿二叉樹沒有度為1的結點,所以分支結點數就是二度結點數.28 .一棵具有257個結點的完全二叉樹,它的深度為9.(注：用log2(n)+1=8.xx+1=929 .設一棵完全二叉樹有700個結點,那么共有350個葉子結點.答：最快方法：用葉子數=n/2=35030 .設一棵完全二叉樹具有1000個結點,那么此完全二叉樹有500個葉子結點,有499個度為2的結點,有結點只有非空左子樹,有0個結點只有非空右子樹.答：最快

18、方法：用葉子數=n/2=500,n2=n0-1=499.另外,最后一結點為2i屬于左葉子,右葉子是空的,所以有1個非空左子樹.完全二叉樹的特點決定不可能有左空右不空的情況,所以非空右子樹數=0.31 .在數據的存放無規律而言的線性表中進行檢索的最正確方法是順序查找(線性查找).32 .線性有序表(a,a2,a3,注56)是從小到大排列的,對一個給定的值k,用二分法檢索表中與k相等的元素,在查找不成功的情況下,最多需要檢索8次.設有100個結點,用二分法查找時,最大比擬次數是7.33 .假設在有序線性表a20上進行折半查找,那么比擬一次查找成功的結點數為1;比擬兩次查找成功的結點數為2;比較四次

19、查找成功的結點數為8;平均查找長度為3.7o解：顯然,平均查找長度=OHIogln)<5次(25).但具體是多萬次,那么不應當根據公式來計算(即(21Xlog221)/20=4.6次并不正確！).由于這是在假設n=2m-1的情況下推導出來的公式.應當用窮舉法羅列：全部元素的查找次數為=(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比擬大小.35 .在各種查找方法中,平均查找長度與結點個數n無關的查找方法是散列查找.36

20、 .散列法存儲的根本思想是由關鍵字的值決定數據的存儲地址.一二、判斷正誤(在正確的說法后面疔石I,反之打叉)(x)1.鏈表的每個結點中都恰好包含一個指針.答：錯誤.鏈表中的結點可含多個指針域,分別存放多個指針.例如,雙向鏈表中的結點可以含有兩個指針域,分別存放指向其直接前趨和直接后繼結點的指針.(X)2.鏈表的物理存儲結構具有同鏈表一樣的順序.錯,鏈表的存儲結構特點是無序,而鏈表的示意圖有序.(X)3.鏈表的刪除算法很簡單,由于當刪除鏈中某個結點后,計算時機自動地將后續的各個單元向前移動.錯,鏈表的結點不會移動,只是指針內容改變.(X)4.線性表的每個結點只能是一個簡單類型,而鏈表的每個結點可

21、以是一個復雜類型.錯,混淆了邏輯結構與物理結構,鏈表也是線性表！且即使是順序表,也能存放記錄型數據.(X)5.順序表結構適宜于進行順序存取,而鏈表適宜于進行隨機存取.錯,正好說反了.順序表才適合隨機存取,鏈表恰恰適于“順藤摸瓜(X)6.順序存儲方式的優點是存儲密度大,且插入、刪除運算效率高.錯,前一半正確,但后一半說法錯誤,那是鏈式存儲的優點.順序存儲方式插入、刪除運算效率較低,在表長為n的順序表中,插入和刪除一個數據元素,平均需移動表長一半個數的數據元素.(X)7.線性表在物理存儲空間中也一定是連續的.錯,線性表有兩種存儲方式,順序存儲和鏈式存儲.后者不要求連續存放.(X)8.線性表在順序存

22、儲時,邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰.錯誤.線性表有兩種存儲方式,在順序存儲時,邏輯上相鄰的元素在存儲的物理位置次序上也相鄰.(X)9.順序存儲方式只能用于存儲線性結構.錯誤.順序存儲方式不僅能用于存儲線性結構,還可以用來存放非線性結構,例如完全二叉樹是屬于非線性結構,但其最正確存儲方式是順序存儲方式.(后一節介紹)(X)10.線性表的邏輯順序與存儲順序總是一致的.錯,理由同7.鏈式存儲就無需一致.(X)11.線性表的每個結點只能是一個簡單類型,而鏈表的每個結點可以是一個復雜類型.錯,線性表是邏輯結構概念,可以順序存儲或鏈式存儲,與元素數據類型無關.(X)12.在表結構中最常用

23、的是線性表,棧和隊列不太常用.錯,不一定吧？調用子程序或函數常用,CP加也用隊列.(M)13.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表,是一種后進先出型結構.(M)14.對于不同的使用者,一個表結構既可以是棧,也可以是隊列,也可以是線性表.正確,都是線性邏輯結構,棧和隊列其實是特殊的線性表,對運算的定義略有不同而已.(X)15.棧和鏈表是兩種不同的數據結構.錯,棧是邏輯結構的概念,是特殊殊線性表,而鏈表是存儲結構概念,二者不是同類項.(X)16.棧和隊列是一種非線性數據結構.錯,他們都是線性邏輯結構,棧和隊列其實是特殊的線性表,對運算的定義略有不同而已.(,)17.棧和隊列的存儲

24、方式既可是順序方式,也可是鏈接方式.(,)18.兩個棧共享一片連續內存空間時,為提升內存利用率,減少溢出時機,應把兩個棧的棧底分別設在這片內存空間的兩端.(X)19.隊是一種插入與刪除操作分別在表的兩端進行的線性表,是一種先進后出型結構.錯,后半句不對.(X)20.一個棧的輸入序列是12345,那么棧的輸出序列不可能是12345.錯,有可能.(,)21.假設二叉樹用二叉鏈表作存貯結構,那么在n個結點的二叉樹鏈表中只有n1個非空指針域.(x)22.二叉樹中每個結點的兩棵子樹的高度差等于1.(V)23.二叉樹中每個結點的兩棵子樹是有序的.(X)24.二叉樹中每個結點有兩棵非空子樹或有兩棵空子樹.(

25、X)25.二叉樹中每個結點的關鍵字值大于其左非空子樹(假設存在的話)所有結點的關鍵字值,且小于其右非空子樹(假設存在的話)所有結點的關鍵字值.(應當是二叉排序樹的特點)(X)26.二叉樹中所有結點個數是2k-1-1,其中k是樹的深度.(應2i-1)(X)27.二叉樹中所有結點,如果不存在非空左子樹,那么不存在非空右子樹.(X)28.對于一棵非空二叉樹,它的根結點作為第一層,那么它的第i層上最多能有2i1個結點.(應2")(V)29.用二叉鏈表法(link-rlink)存儲包含n個結點的二叉樹,結點的2n個指針區域中有n+1個為空指針.(V)30.具有12個結點的完全二叉樹有5個度為2

26、的結點.三、單項選擇題(B)1.非線性結構是數據元素之間存在一種：A)一對多關系B)多對多關系C)多對一關系D)一對一關系(C)2.數據結構中,與所使用的計算機無關的是數據的結構；A)存儲B)物理C)邏輯D)物理和存儲(C)3.算法分析的目的是：A)找出數據結構的合理性B)研究算法中的輸入和輸出的關系C)分析算法的效率以求改良D)分析算法的易懂性和文檔性(A)4.算法分析的兩個主要方面是：A)空間復雜性和時間復雜性B)正確性和簡明性C)可讀性和文檔性D)數據復雜性和程序復雜性(C)5.計算機算法指的是：A)計算方法B)排序方法C)解決問題的有限運算序列D)調度方法(B)6.計算機算法必須具備輸

27、入、輸出和等5個特性.A)可行性、可移植性和可擴充性B)可行性、確定性和有窮性C)確定性、有窮性和穩定性D)易讀性、穩定性和平安性(C)7.數據在計算機存儲器內表示時,物理地址與邏輯地址相同并且是連續的,稱之為：(A)存儲結構(B)邏輯結構(C)順序存儲結構(D)鏈式存儲結構(B)8.一個向量第一個元素的存儲地址是100,每個元素的長度為2,那么第5個元素的地址是(A)110(B)108(C)100(D)120(A)9.在n個結點的順序表中,算法的時間復雜度是O(1)的操作是：(A) 訪問第i個結點(1<i<n)和求第i個結點的直接前驅(2<i<n)(B) 在第i個結點

28、后插入一個新結點(1&iwn)(C) 刪除第i個結點(1&i&n)(D) 將n個結點從小到大排序(B)10.向一個有127個元素的順序表中插入一個新元素并保持原來順序不變,平均要移動_個元素(A)8(B)63.5(C)63(D)7(A)11.鏈接存儲的存儲結構所占存儲空間：(A) 分兩局部,一局部存放結點值,另一局部存放表示結點間關系的指針(B) 只有一局部,存放結點值(C)只有一局部,存儲表示結點間關系的指針(D)分兩局部,一局部存放結點值,另一局部存放結點所占單元數(B)12.鏈表是一種采用存儲結構存儲的線性表；(A)順序(B)鏈式(C)星式(D)網狀(D)13.線

29、性表假設采用鏈式存儲結構時,要求內存中可用存儲單元的地址(A)必須是連續的(C)一定是不連續的(B)14.線性表L在_(A)需經常修改L中的結點宿(C)L中含有大量的結點(B)局部地址必須是連續的(D)連續或不連續都可以情況下適用于使用鏈式結構實現.(B)需不斷對L進行刪除插入(D)L中結點結構復雜(B)15.棧中元素的進出原那么是D.棧滿那么出CA.BA.)16.假設一個棧的入棧序列是C.n-i+1)17.判定一個棧ST(最多元素為ST->top<>0B,ST->top=01,2,3,n,其輸出序列為p1,p2,p3,pn,假設p1=n,那么pi為D.不確定m0)為空

30、的條件是C.ST->top<>m0D.ST->top=m0(C)18.在一個圖中,所有頂點的度數之和等于圖的邊數的倍.A.1/2B.1C.2D.4(B)19.在一個有向圖中,所有頂點的入度之和等于所有頂點的出度之和的倍A.1/2B.1C.2D.4B)20.有8個結點的無向圖最多有條邊.A.14B.28C.56D.112C)21.有8個結點的有向完全圖有條邊.A.14B.28C.56D.112B)22.在表長為n的鏈表中進行線性查找,它的平均查找長度為A.ASL=n;B.ASL=(n+l)/2;C.ASL=目+1；D.ASLlog2(n+l)1(A)23.折半查找有序表(

31、4,6,10,12,20,30,50,70,88,100).假設查找表中元素58,那么它將依次與表中比較大小,查找結果是失敗.A20,70,30,50B.30,88,70,50C.20,50D.30,88,50(C)24.對22個記錄的有序表作折半查找,當查找失敗時,至少需要比擬次關鍵字.A3B.4C.5D,6(A)25.鏈表適用于查找A.順序B.二分法一C一.順序,也能二分法D.隨機?數據結構與算法?復習題一、選擇題.1 .在數據結構中,從邏輯上可以把數據結構分為C.A動態結構和靜態結構B.緊湊結構和非緊湊結構C.線性結構和非線性結構D.內部結構和外部結構2 .數據結構在計算機內存中的表示是

32、指A.A數據的存儲結構B.數據結構C.數據的邏輯結構D.數據元素之間的關系3 .在數據結構中,與所使用的af算機無關的是數據的A結構.A.邏輯B.存儲C.邏輯和存儲D.物H4 .在存儲數據時,通常不僅要存儲各數據元素的值,而且還要存儲C.A.數據的處理方法B.數據元素的類型C數據元素之間的關系D.數據的存儲方法5 .在決定選取何種存儲結構時,一般不考慮A.A.各結點的值如何B.結點個數的多少C.對數據有哪些運算D.所用的編程語言實現這種結構是否方便.6 .以下說法正確的選項是DoA.數據項是數據的根本單位B.數據元素是數據的最小單位C.數據結構是帶結構的數據項的集合D.一些外表上很不相同的數據

33、可以有相同的邏輯結構7 .算法分析的目的是C,算法分析的兩個主要方面是A.研究算法中的輸入和輸出的關系.分析算法的易讀性和文檔性,正確性和簡明性.數據復雜性和程序復雜性(1) A.找出數據結構的合理性BC.分析算法的效率以求改良C(2) A.空間復雜度和時間復雜度BC.可讀性和文檔性D8 .下面程序段的時間復雜度是O(n2)s=0;for(I=0;i<n;i+)for(j=0;j<n;j+)s+=B皿;sum=s;9 .下面程序段的時間復雜度是O(n*m)for(i=0;i<n;i+)for(j=0;j<m;j+)A皿=0;10 .下面程序段的時間復雜度是O(log3n

34、)1 =0；while(i<=n)i=i*3；11 .在以下的表達中,正確的選項是_B.A.線性表的順序存儲結構優于鏈表存儲結構B.二維數組是其數據元素為線性表的線性表C.棧的操作方式是先進先出D.隊列的操作方式是先進后出12 .通常要求同一邏輯結構中的所有數據元素具有相同的特性,這意味著A.數據元素具有同一特點B.不僅數據元素所包含的數據項的個數要相同,而且對應的數據項的類型要一致C.每個數據元素都一樣D.數據元素所包含的數據項的個數要相等13 .鏈表不具備的特點是A.A可隨機訪問任一結點B插入刪除不需要移動元素C.不必事先估計存儲空間D.所需空間與其長度成正比14 .不帶頭結點的單鏈

35、表head為空的判定條件是A.Ahead=NULLBhead->next=NULLC.head->next=headDhead!=NULL15.帶頭結點的單鏈表head為空的判定條件是B.A.head=NULLBhead->next=NULLC.head->next=headDhead!=NULL16 .假設某表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點,那么采用D存儲方式最節省運算時間.A單車防!一B.給出表頭指針的單循環鏈表C.雙鏈表D.帶頭結點的雙循環鏈表17 .需要分配較大空間,插入和刪除不需要移動元素的線性表,其存儲結構是BA.單鏈表B.靜

36、態鏈表C.線性鏈表D.順序存儲結構18 .非空的循環單鏈表head的尾結點由p所指向滿足CA.p->next=NULLB,p=NULLC. p->next=headD.p=head19.在循環雙鏈表的p所指的結點之前插入s所指結點的操作是DA.p->prior=sB.p->prior=sC.s->next=p；s->prior=p->prior；s->prior=p->prior；p->prior->next=s；s->next=p；p->prior->next=s；p->prior->next=s

37、；s->next=p；s->prior=p->prior；p->prior=sD. s->next=p；s->prior=p->prior；p->prior->next=s；p->prior=s20 .如果最常用的操作是取第i個結點及其前驅,那么采用_D_存儲方式最節省時間A.單鏈表B.雙鏈表C.單循環鏈表D.順序不21 .在一個具有n個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是B_oA.O(1)B.O(n)C.O(n2)D.O(nlog2n)22 .在一個長度為n(n>1)的單鏈表上,設有頭和尾兩個指針,執行

38、B操作與鏈表的長度有關.A.刪除單鏈表中的第一個元素B.刪除單鏈表中的最后一個元素C.在單鏈表第一個元素前插入一個新元素D.在單鏈表最后一個元素后插入一個新元素23 .與單鏈表相比,雙鏈表的優點之一是DoA.插入、刪除操作更簡單B.可以進行隨機訪問C.可以省略表頭指針或表尾指針D.順序訪問相鄰結點更靈活24 .如果對線性表的操作只有兩種,即刪除第一個元素,在最后一個元素的后面插入新元素,那么最好使用BA只有表頭指針沒有表尾指針的循環單鏈表B.只有表尾指針沒有表頭指針的循環單鏈表C.非循環雙鏈表D.循環雙鏈表25 .在長度為n的順序表的第i個位置上插入一個元素(10i<n+1),元素的移動次數為：A.A.ni+1B.niC.iD.i126 .對于只在表的首、尾兩端進行插入操作的線性表,宜采用的存儲結構為CA.順序表B.用頭指針表示的循環單鏈表C.用尾指針表