PAGE50-1緒論沈陽理工大學應用技術學院信息與控制學院計算機科學與技術教研室2011-5-8

數(shù)據(jù)結構復習題：緒論單選題1、在數(shù)據(jù)結構中，與所使用的計算機無關的數(shù)據(jù)叫____結構。A存儲|B物理|C邏輯|D物理和存儲2、在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成______。A動態(tài)結構和靜態(tài)結構|B緊湊結構和非緊湊結構|C線性結構和非線性結構|D內(nèi)部結構和外部結構圖3、數(shù)據(jù)結構在計算機內(nèi)存中的表示是指_______。數(shù)據(jù)的存儲結構|數(shù)據(jù)結構|數(shù)據(jù)的邏輯結構|數(shù)據(jù)元素之間的關系4、在數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的______結構。邏輯|存儲|邏輯和存儲|物理5、在以下的敘述中，正確的是_____。線性表的線性存儲結構優(yōu)于鏈表存儲結構|二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表|棧的操作方式是先進先出|隊列的操作方式是先進后出6、在決定選取何種存儲結構時，一般不考慮_______。各結點的值如何|結束個數(shù)的多少|(zhì)對數(shù)據(jù)有哪些運算|所用編程語言實現(xiàn)這種結構是否方便7、在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲_______。數(shù)據(jù)的處理方法|數(shù)據(jù)元素的類型|數(shù)據(jù)元素之間的關系|數(shù)據(jù)的存儲方法8、下面說法錯誤的是_______。(1)算法原地工作的含義是指不需要任何額外的輔助空間(2)在相同的規(guī)模n下，復雜度O(n)的算法在時間上總是優(yōu)于復雜度O(2n)的算法(3)所謂時間復雜度是指最壞情況下，估計算法執(zhí)行時間的一個上界(4)同一個算法，實現(xiàn)語句的級別越高，執(zhí)行效率越低(1)|(1)、(2)|(1)、(4)|(3)9、通常要求同一邏輯結構中的所有數(shù)據(jù)元素具有相同的特性。這意味著______。數(shù)據(jù)元素具有同一特點|不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應的數(shù)據(jù)項的類型要一致|每個數(shù)據(jù)元素都一樣|數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等10、以下說法正確的是_______。數(shù)據(jù)元素是數(shù)據(jù)的最小單位|數(shù)據(jù)項是數(shù)據(jù)的基本單位|數(shù)據(jù)結構是帶結構的數(shù)據(jù)項的集合|一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結構11、數(shù)據(jù)項是數(shù)據(jù)的最小單元,數(shù)據(jù)元素是數(shù)據(jù)的基本單位.數(shù)據(jù)項|數(shù)據(jù)元素|信息項|表元素12、數(shù)據(jù)結構是指__數(shù)據(jù)元素__以及它們之間的__結構___.(1)數(shù)據(jù)元素(2)結構|(1)計算方法(2)關系|(1)邏輯存儲(2)運算|(1)數(shù)據(jù)映像(2)算法13、計算機所處理的數(shù)據(jù)一般具備某種內(nèi)在的關系,這是的指_____.數(shù)據(jù)和數(shù)據(jù)之間存在的某種關系|元素和元素之間存在某種關系|元素內(nèi)部具有某種結構|數(shù)據(jù)項和數(shù)據(jù)項之間存在某種關系14、數(shù)據(jù)的邏輯結構可以分為_____兩類.動態(tài)結構和表態(tài)結構|緊湊結構和非緊湊結構|線性結構和非線性結構|內(nèi)部結構和外部結構15、數(shù)據(jù)的邏輯結構是指_____關系的整體.數(shù)據(jù)元素之間邏輯|數(shù)據(jù)項之間邏輯|數(shù)據(jù)類型之間|存儲結構之間16、在存儲數(shù)據(jù)時,通常不僅要存儲各數(shù)據(jù)元素的值,而且還要存儲_____.數(shù)據(jù)的處理方法|數(shù)據(jù)元素的類型|數(shù)據(jù)元素之間的關系|數(shù)據(jù)的存儲方法17、在數(shù)據(jù)的存儲結構中,一個存儲結點存儲一個_____.數(shù)據(jù)項|數(shù)據(jù)元素|數(shù)據(jù)結構|數(shù)據(jù)類型18、在計算機的存儲器中表示時,物理地址和邏輯地址直接對應并且是連續(xù)的,稱之為_____.邏輯結構|順序存儲結構|鏈式存儲結構|以上都對19、數(shù)據(jù)采用鏈式存儲結構時,要求_____.每個結點用占一片連續(xù)的存儲區(qū)域|所有結點占用一片連續(xù)的存儲區(qū)域|結點的最后一個數(shù)據(jù)域是指針類型|每個結點有多少個后繼,就設多少個指針域20、數(shù)據(jù)的運算_____.效率與采用何種存儲結構有關|是根據(jù)存儲結構來定義的|有算術運算和關系運算兩大類|必須用程序設計語言來描述21、下列說法中,不正確的是_____.數(shù)據(jù)元素是數(shù)據(jù)的基本單位|數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小可標識單位|數(shù)據(jù)可由若干個數(shù)據(jù)元素構成|數(shù)據(jù)項可由若干個數(shù)據(jù)元素構成22、_____不是算法的基本特性.可行性|長度有限|在規(guī)定的時間內(nèi)完成|確定性23、計算機中算法指的是解決某一問題的有限運算序列,它必須具備輸入、輸出、_____.可行性、可移植性和可擴充性|可行性、有窮性和確定性|確定性、有窮性和穩(wěn)定性|易讀性、穩(wěn)定性和確定性24、以下不屬于算法特性的是_____.可行性|有輸入|確定性|健壯性25、下面關于算法的說法正確的是_____.算法最終必須由程序?qū)崿F(xiàn)|算法的有窮性是對于任意的一組輸入值必須在有窮步驟后結束|算法的可行性是指指令不能有二義性|以上幾個都是錯誤的26、算法的時間復雜度與______有關問題規(guī)模|計算機硬件性能|編譯程序質(zhì)量|程序設計語言27、算法分析的主要任務是分析_____.算法是否具有較好的可讀性|算法中是否存在語法錯誤|算法的功能是否符合設計要求|算法的執(zhí)行時間和問題規(guī)模之間的關系28、某算法的時間復雜度為O(n2),表明該算法的_____.問題規(guī)模是n2|執(zhí)行時間等于n2|執(zhí)行時間與n2成正比|問題規(guī)模與n2成正比29、算法分析的目的是_____.找出數(shù)據(jù)結構的合理性|研究算法中輸入和輸出關系|分析算法的效率以求改進|分析算法的易讀性和文檔性30、線性表是具有n個______的有限序列。表元素|字符|數(shù)據(jù)元素|數(shù)據(jù)項31、線性表是______。一個有限序列，可以為空|一個有限序列，不可以為空|一個無限序列，可以為空|一個無限序列，不可以為空32、線性表采用鏈表存儲時，其地址______。必須是連續(xù)的|一定是不連續(xù)的|部分地址必須是連續(xù)的|連續(xù)與否均可以33、鏈表不具備的特點是______。可隨機訪問任一結點|插入刪除不需要移動元素|不必事先估計存儲空間|所需空間與其長度成正比34、線性表的靜態(tài)存儲結構與順序存儲結構相比優(yōu)點是_______。所有的操作算法實現(xiàn)簡單|便于隨機存取|便于插入和刪除|便于利用零散的存儲器空間35、設線性表有n個元素，以下操作中，_______在順序表上實現(xiàn)比在鏈表上實現(xiàn)效率更高。輸出第i(1<=i<=n)個元素值|交換第1個元素與第2個元素的值|順序輸出這n個元素的值|輸出與給定值x相等的元素在線性表中的序號36、對于一個線性表，既要求能夠較快地進行插入和刪除，又要求存儲結構能夠反映數(shù)據(jù)元素之間的邏輯關系，則應采用_______存儲結構。順序|鏈式|散列|索引37、設線性表中有2n個元素，以下操作中，______在單鏈表上實現(xiàn)要比在順序表上實現(xiàn)效率更高。刪除指定的元素|在最后一個元素的后面插入一個新元素|順序輸出前k個元素|交換第i個元素和第2n-i-1個元素的值(i=0，1，…，n-1)38、需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結構是______。單鏈表|靜態(tài)鏈表|線性鏈表|順序存儲結構39、如果最常用其所長的操作是取第i個結點及其前驅(qū)，則采用______結構方式最節(jié)省時間。單鏈表|雙鏈表|單循環(huán)鏈表|順序表40、與單鏈表相比，雙鏈表的優(yōu)點之一是______。插入、刪除操作更簡單|可以進行隨機訪問|可以省略表頭指針或表尾指針|訪問前后相鄰結點更靈活41、數(shù)據(jù)結構在計算機內(nèi)存中的表示是指______.數(shù)據(jù)的存儲結構|數(shù)據(jù)結構|數(shù)據(jù)的邏輯結構|數(shù)據(jù)元素之間的關系42、下面程序段的時間復雜度為_________．O(m)|O(n)|O(m*n)|O(m+n)for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;數(shù)據(jù)結構復習題：緒論判斷題1、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。2、數(shù)據(jù)項是數(shù)據(jù)的基本單位。3、數(shù)據(jù)元素是數(shù)據(jù)的最小單位4、數(shù)據(jù)對象就是一組任意數(shù)據(jù)元素的集合5、任何數(shù)據(jù)結構都具備3個基本運算:插入、刪除和查找.6、數(shù)據(jù)是由一些類型相同的數(shù)據(jù)元素構成的7、數(shù)據(jù)是邏輯結構與各數(shù)據(jù)元素在計算機中如何存儲有關8、如果數(shù)據(jù)元素值發(fā)生改變,則數(shù)據(jù)的邏輯結構也隨之改變.9、邏輯結構相同的數(shù)據(jù),可以采用多種不同的存儲方法.10、邏輯結構相同的數(shù)據(jù),結點類型也一定相同11、邏輯結構不相同的數(shù)據(jù),必須采用不同的存儲方式來存儲12、數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系.13、算法的優(yōu)劣與算法描述語言有無關，但與所有計算機有關。14、算法可以用不同的語言描述，如果用C或Pascal等高級語言來描述，則算法實際上就是程序了。15、程序一定是算法。16、算法最終必須由計算機程序?qū)崿F(xiàn)。F19、健壯的算法不會因非法入輸數(shù)據(jù)而出現(xiàn)莫名其妙的執(zhí)行結果。數(shù)據(jù)結構復習題：緒論算法分析題1、求兩個n階矩形的乘法C=A*B,其算法如下:#defineMAX100voidmaxtrixmult(int,floata[MAX][MAX],b[MAX][MAX],floatc[MAX][MAX]){inti,j,k;floatx;for(i=1;i<=n;i++)//①{for(j=1;j<=n;j++)//②{x=0;//③for(k=1;k<=n;k++)//④x+=a[i][k]*b[k][j];//⑤c[i][j]=x;//⑥}}}計算①～⑥各語句的頻度,并分析該算法的時間復雜度。2、設n是偶數(shù),試計算運行下列程序段后m的值并給出該程序段的時間復雜度。m=0;for(i=1;i<=n;i++)for(j=2*1;j<=n;j++)m++;3、閱讀下列算法:voidsuan_fa(intn){inti,j,k,s,x;for(s=0,i=0;i<n;i++)for(j=i;j<n;j++)s++;i=1;j=n;x=0;while(i<j){i++;j--;x+=2;}pirntf("s=%d,x=%d",s,x);}(1)分析算法中語句"s++;"的執(zhí)行次數(shù);(2)分析算法中語句"x+=2;"的執(zhí)行次數(shù);(3)分析該算法的時間復雜度;(4)假定n=5,試指出執(zhí)行該算法的輸出結果。6、設n是偶數(shù),試計算運行下列程序段后m的值并給出該程序段的時間復雜度。intm=0,i,j;for(i=1;i<=n;i++)for(j=2*i;j<=n;j++)m++;m=n*n/4O()數(shù)據(jù)結構復習題：緒論填空題1、一個數(shù)據(jù)結構在計算機中___映像___稱為存儲結構。2、數(shù)據(jù)邏輯結構包括、和三種類型，樹形結構和圖形結構合稱為________。3、在線性結構中，第一個結點________前驅(qū)結點，其余每個結點有且只有_______個前驅(qū)結點：最后一個結點______后續(xù)結點，其余每個結點有且只有______個后續(xù)結點。4、在樹形結構中，樹根結點沒有______結點，其余每個結點有且只有______個前驅(qū)結點:葉子結點沒有______結點,其余每個結點后的后續(xù)結點可以_______5、在圖形結構中，每個結點的前驅(qū)結點數(shù)和后續(xù)結點數(shù)可以___任意多個_____。6、線性結構中元素之間存在___一對一______關系，樹形結構中元素之間存在___一對多____關系，圖形結構中元素之間存在____多對多____關系。7、算法的5個重要特性是_________、__________、__________、輸入和輸出。8、算法可以用不同的語言描述，如果用C語言或PASCAL語言等高級語言來描述，則算法實現(xiàn)上就是程序了。這個斷言是________。9、數(shù)據(jù)結構、數(shù)據(jù)元素和數(shù)據(jù)項在計算機中的映射(或表示)分別稱為存儲結構、結點和數(shù)據(jù)域。這個斷言是_______。10、下面程序段的時間復雜度是_______。for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;11、下面程序段的時間復雜度是__O(sqrt(n))_____。i=s=0;while(s<n){i++;s+=i;}12、下面程序段的時間復雜度是_______。s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;13、下面程序段的時間復雜度是___O(log3n)_____。i=1;while(i<=n)i=i*3;14、有如下遞歸函數(shù)fact(n),分析其時間復雜度。intfact(intn){if(n<=1)return1;elsereturn(n*fact(n-1));}15、指出下列各算法的時間復雜度(1)prime(intn){inti=2;while(n%i!=0&&i<sqrt(n))i++;if(i*1.0>sqrt(n))printf"是一素數(shù)";elseprintf"不是一素數(shù)";}O(sqrt(n))(2)sum1(intn){intp=1,sum=0,i;for(i=1;i<=n;i++){p*=i;sum+=p;}returm(sum);}(3)sum2(intn){intsum=0,i,j;for(i=1;i<=n;i++){p=1;for(j=1;j<=i;j++)p*=j;sum+=p;}return(sum);}16、數(shù)據(jù)的邏輯結構是指_____.17、一個數(shù)據(jù)結構在計算機中的_表示_____稱為存儲結構.18、順序存儲方法是把邏輯上__相鄰的結點___存儲在物理位置上___相鄰的存儲單元___里;鏈式存儲方法中結點間的邏輯關系是由附加的指針字段表示____的.19、數(shù)據(jù)結構是指研究數(shù)據(jù)的__存儲結構___和__邏輯結構___以及它們之間的相互關系,并對這種結構定義相應的__運算___,設計出相應的__算法___,從而確保經(jīng)過這些運算后所得到的新結構是原來的結構類型.20、一個算法具有5個特性:_____、_____、_____、輸入和輸出。21、算法的執(zhí)行時間是_____的函數(shù)。22、數(shù)據(jù)的邏輯結構是從邏輯上描述數(shù)據(jù),它與數(shù)據(jù)的___存儲結構、物理結構___無關,是獨立于計算機的.23、數(shù)據(jù)的邏輯結構被分為____________、____________、___________和____________４種。24、數(shù)據(jù)的存儲結構被分為____________、____________、____________和____________４種。25、在線性結構、樹形結構和圖形結構中，前驅(qū)和后繼結點之間分別存在著____1:1________、____1：N________、_____M:N_______的聯(lián)系。26、一種抽象數(shù)據(jù)類型包括______數(shù)據(jù)______和____操作_______兩個部分。27、從一維數(shù)組a[n]中順序查找出一個最大值元素的時間復雜度為____________，輸出一個二維數(shù)組b[m][n]中所有元素值的時間復雜度為____________28、在下面程序段中，s=s+p語句的執(zhí)行次數(shù)為______n______，p*=j語句的執(zhí)行次數(shù)為______n*(n+1)/2______，該程序段的時間復雜度為______O(n*n)______。inti=0,s=0;while(++i<=n){intp=1;for(intj=1;j<=i;j++)p*=j;s=s+p;}29、一個算法的時間復雜度為（3*n*n+2nlog2n+4n-7)/(5n)，其數(shù)量級表示為_____O(n)_______。30、從一個數(shù)組a[10]中順序查找元素時，假定查找每個元素的概率都相同，則進行一次查找運算時的平均查找長度（即同元素的平均比較次數(shù)）為____________。31、從一個數(shù)組a[7]中順序查找元素時，假定查找第1個元素a[0]的概率為1/3，查找第2個元素a[1]的概率為1/4，其找其余元素的概率均相同，則在查找成功時同元素的平均比較次數(shù)為____35/12________。32、對于一個n*n的矩陣Ａ的任意矩陣元素a[i][j]，按行存儲時和按列存儲時的地址之差是____(i-j)*(n-1)*d______。設兩種存儲時的開始存儲地址均為ＬＯＣ(0,0)，每個元素所占存儲單元數(shù)均為d。33、設有一個二維數(shù)組A[10][20]，按行存放于一個連續(xù)的存儲空間中，A[0][0]的存儲地址是200，每個數(shù)組元素占1個存儲字，則A[6][2]的存儲字地址是____________34、設有一個二維數(shù)組A[10][20]，按列為主序存放于一個連續(xù)的存儲空間中，A[0][0]的存儲地址是200，每個數(shù)組元素占1個存儲字，則A[6][2]的存儲字地址是____________。37、在線性表的單鏈接存儲結構中，每個結點包含有兩個域，一個叫____________，另一個叫____________域。數(shù)據(jù)結構復習題：緒論問答題1、當你為解決某一問題而選擇數(shù)據(jù)結構時,應從哪些方面考慮?2、簡述邏輯結構與存儲結構的關系.3、數(shù)據(jù)運算是數(shù)據(jù)結構的一個重要方面,試舉例說明兩個數(shù)據(jù)結構的邏輯結構和存儲方式完全相同,只是對于運算的定義不同,因而兩個結構具有顯著不同的特性,則這兩個數(shù)據(jù)結構是不同的.數(shù)據(jù)結構復習題答案：緒論問答題1、解答：通常從兩方面考慮：第一是算法所需的存儲空間量；第二是算法所需的時間。對算法所需的時間又涉及以下三點：（1）程序運行時所需輸入的數(shù)據(jù)總量。（2）計算機執(zhí)行每條指令所需的時間。（3）程序中指令重復執(zhí)行的次數(shù)。2、答：數(shù)據(jù)的邏輯結構反映數(shù)據(jù)元素之間的邏輯關系（即數(shù)據(jù)元素之間的關聯(lián)方式或“鄰接關系”），數(shù)據(jù)的存儲結構是數(shù)據(jù)結構在計算機中的表示，包括數(shù)據(jù)元素的表示及其關系的表示。3、答：棧和隊列的邏輯結構相同，其存儲表示也可相同（順序存儲和鏈式存儲），但由于其運算集合不同而成為不同的數(shù)據(jù)結構。2線性表沈陽理工大學應用技術學院信息與控制學院計算機科學與技術教研室2011-5-8

數(shù)據(jù)結構復習題：線性表單選題1、在一個長度為n的順序表中，向第i個元素(1≤i≤n+1)之前插入一個新元素時，需向后移動_____個元素。2、從一個具有n個節(jié)點的單鏈表中查找其值等于x結點時，在查找成功的情況下，需平均比較__(n+1)/2___個結點。3、在一個單鏈表中，已知*q結點是*p結點的前驅(qū)結點，若在*q和*p之間插入*s結點，則執(zhí)行_____。4、線性表是_____。5、對順序存儲的線性表，設其長度為n，在任何位置上插入或刪除操作都是等概率的，刪除一個元素時大約要移動表中的_____個元素。6、線性表采用鏈式存儲時，其地址_____。7、設單鏈表中指針p指著結點m，指針f指著將要插入的新結點x，當x插在鏈表中最后一個結點m之后時，只要先修改_____后修改p->link=f即可。8、在雙向鏈表存儲結構中，刪除p所指的結點時需修改指針_____。9、在雙向鏈表存儲結構中，刪除p所指的結點的前趨結點（若存在）時需修改指針_____。10、根據(jù)線性表的鏈式存儲結構，每個結點所含指針的個數(shù)，鏈表分為單鏈表和_____。11、在線性表的鏈式存儲結構中，邏輯上相鄰的元素在物理位置上_____。12、鏈表不具備的特點是_______。13、不帶頭結點的單鏈表head為空的判定條件是______。14、帶頭結點的單鏈表的head為空的判定條件是______。15、帶頭結點的雙循環(huán)表L為空表的條件是__L->next==L____。16、非空的循環(huán)單鏈表head的尾結點(由p所指向)滿足_______。17、在循環(huán)雙鏈表的p所指結點之前插入s所指結點的操作是_______。18、若某表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點，則采用___帶頭結點的雙循環(huán)鏈表___存儲方式最節(jié)省運算時間。19、某線性表最常用的操作是在最后一個結點之后插入一個結點或刪除第一個結點，故采用___僅有尾指針的單循環(huán)鏈表__存儲方式最節(jié)省運算時間。20、需要分配較大空間，插入和刪除不需要移動元素的線性表，其存儲結構是_______。21、如果最常用的操作是取第i個結點及其前驅(qū)，則采用___順序表___存儲方式最節(jié)省時間。22、在一個具有n個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是______。23、在一個長度為n(n>1)的單鏈表上，設有頭和尾兩個指針，執(zhí)行____刪除單鏈表中的最后一個元素____操作與鏈表的長度有關。24、設線性表有n個元素，以下算法中，_______在順序表上實現(xiàn)比在鏈表上實現(xiàn)效率更高。25、設線性表中有2n個元素，算法___刪除所有值為x的元素____，在單鏈表上實現(xiàn)要比在順序表上實現(xiàn)效率更高。26、與單鏈表相比，雙鏈表的優(yōu)點之一是________。27、如果對線性表的運算只有4種，即刪除第一個元素，刪除最后一個元素，在第一個元素前面插入新元素，在最后一個元素的后面插入新元素，則最后使用___只有表頭指針沒有表尾指針的循環(huán)雙鏈表_____。28、如果對線性表的運算只有兩種，即刪除第一個元素，在最后一個元素的后面插入新元素，則最好使用_______。29、設有兩個長度為n的單鏈表，結點類型相同。若以h1為表頭指針的鏈表是非循環(huán)的，以h2為表頭指針的鏈表是循環(huán)的，則_______。30、在長度為n的______上，刪除第一個結點，其算法的時間復度為O(n)。31、將兩個各有n個元素的有序順序表歸并成一個有序順序表，其最少的比較次數(shù)是__n___。32、帶頭結點的單鏈表L為空的判定條件是______。33、在一個具有n個結點的有序單鏈表中插入一個新結點并仍然保持有序的時間復雜度是_______。34、在一個長度為n(n>1)的帶頭結點的單鏈表h上，，另設有尾指針r(指向尾結點)，執(zhí)行_______操作與鏈表的長度有關。35、在一個雙鏈表中，在*p結點之后插入結點*q的操作是______。36、在一個雙鏈表中，在*p結點之前插入*q結點的操作是______。37、在一個雙鏈表達式，刪除*p結點的操作是_______。38、在一個雙鏈表中，刪除*p結點之后的一個結點的操作是________。39、非空的循環(huán)單鏈表L的尾結點(由p所指向)滿足______。40、帶頭結點的雙循環(huán)鏈表L為空表的條件是______。41、若某表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點，則采用_____帶頭結點的循環(huán)雙鏈表____存儲方式最節(jié)省運算時間。42、如果對含有n(n>1)個元素的線性表的運算只有4種:刪除第一個元素；刪除最后一個元素；在第一個元素前面插入新元素；在最后一個元素的后面插入新元素，則最好使用____只有頭結點指針沒有尾結點指針的循環(huán)雙鏈表____。43、某線性表最常用的操作是在最后一個結點之后插入一個結點或刪除第一個結點，則采用____僅有尾結點指針的單循環(huán)鏈表___存儲方式最節(jié)省運算時間。44、設有兩個長度為n的單鏈表，結點類型相同，若以h1為頭結點的鏈表是非循環(huán)的，以h2為頭結點指針的鏈表是循環(huán)的，則________。45、在長度驎n(n>1)的___只有首結點指針h的不帶頭結點的循環(huán)單鏈表___上，刪除第一個元素，其算法的時間復雜度為O(n)。46、元素A、B、C、D依次進順序棧后，棧頂元素是_______，棧底元素是______。47、經(jīng)過以下棧運算后，X的值是______。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x);48、經(jīng)過以下的棧運算后，StackEmpty(s)的值是______。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)49、設一個棧的輸入序列為A、B、C、D，則借助一個棧所得到的輸出序列不可能是______。50、若線性表最常用的運算是存取第i個元素及其前驅(qū)的值,則采用______存儲方式節(jié)省時間.51、鏈表不具備的特點是______.52、在一個長度為n的順序存儲的線性表中，向第i個元素(1<=i<=n+1)位置插入一個新元素時，需要從后向前依次后移_________個元素．53、在一個長度為n的順序存儲的線性表中，刪除第i個元素(1<=i<=n)時，需要從前向后依次前移____n-i_____個元素．54、在一個長度為n的線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x同元素的平均比較次數(shù)，查找每個元素的概率都相等）為（）．57、在一個單鏈表HL中，若要刪除由指針q所指向結點的后繼結點，則執(zhí)行_________。數(shù)據(jù)結構復習題：線性表判斷題1、順序存儲的線性表可以隨機存取。2、線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此，是屬于同一數(shù)據(jù)對象。T3、在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯(lián)系，因為可以從頭結點查找任何一個元素。4、在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結構。5、鏈表的每個結點中，都恰好包含一個指針。6、線性表中每個元素都有一個直接前驅(qū)和直接后繼。7、線性表中所有元素的排列順序必須由小到大或由大到小。8、靜態(tài)鏈表的存儲空間在運算中可以改變大小。9、靜態(tài)鏈表既有順序存儲結構的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中的第i個元素的時間與i無關。10、靜態(tài)鏈表中能容納元素個數(shù)的最大數(shù)在定義時就確定了，以后不能增加。11、靜態(tài)鏈表與動態(tài)鏈表的插入、刪除操作類似，不需做元素的移動。12、線性表的順序存儲結構優(yōu)于鏈式存儲結構。15、在雙鏈表中，可以從任一結點開始沿同一方向查找任何其他結點。F數(shù)據(jù)結構復習題：線性表算法分析題1、己知一個順序表L,其中的元素按值非遞減有序排列,設計一個算法插入一個元素x后保持該順序表仍按遞減有序排列。要求算法的空間復雜度為O(1)。2、設計一個算法從順序表L中刪除所有值為X的元素。要求算法的空間復雜度為O(1)。3、從順序表L中刪除重復的元素,并使剩余元素間的相應次序保持不變.要求本算法的空間復雜記度為O(1)。4、有一個單鏈表(不同結點的數(shù)據(jù)域值可能相同),其頭指針為head,設計一個算法計算數(shù)據(jù)域為x的結點個數(shù)。5、己知線性表元素遞增有序,并以帶頭結點的單鏈表作存儲結構,設計一個高效算法,刪除表中所有值大于mink且小于maxk的元素(若表中存在這樣的元素)。并分析所寫算法的時間復雜度。6、設計一個在帶頭結點的單鏈表中刪除一個最小值結點的高效算法。7、有一個不帶頭結點的單鏈表L(至少有1人結點),其頭指針為head,設計一個算法將L逆置,即最后一個結點變成第一個結點,原來倒數(shù)第二個結點變成第二個結點,如此等等。8、用單鏈表表示集合,設計一個算法求兩個集合的差。要求不破壞原有的結點。9、用單鏈表表示集合,設計一個算法求兩個集合的并。要求不破壞原有的結點。10、設計一個算法,將一個頭結點指針為a的單鏈表A分解成兩個單鏈表A和B,其頭結點指針分別為a和b,使得A鏈表中含有原鏈表A中序號為奇數(shù)的元素,而B鏈表中含有原鏈表A中序號為倒數(shù)的元素,且保持原來的相對順序。11、有一個單鏈表,其結點的元素值以遞增有序排列,設計一個算法刪除該單鏈表中多余的元素值相同的結點。12、己知兩個存放整數(shù)的有序單鏈表(己按整數(shù)從小至大的順序排序),指針L1和L2分別指向這兩個單鏈表的頭結點。設計一個算法,將L1和L2合并成一個單鏈表,且新的鏈表仍按整數(shù)由小到大的順序排列,新的單鏈表的結點由L1和L2的結點構成。要求合并后的單鏈表利用原來單鏈表的存儲空間。13、設計一個算法,將線性表lb連接到la之后,要求其時間復雜度為O(1),占用的輔助空間盡量小。描述所用的結構。14、設指針p指向雙鏈表中的結點X,指針f指向?qū)⒁迦氲男陆Y點Y,Y要插入在結點X之后,寫出指針需要修改的有關步驟。15、有一個循環(huán)雙鏈表,每個結點由兩個指針(prior和next)以及關鍵字(data)構成,p指向其中某一結點,設計一個算法從該循環(huán)雙鏈表中刪除p所指的結點。16、設有一個循環(huán)雙鏈表,其中有一結點的指針為p,設計一個算法將p與其后續(xù)結點進行交換。19、設A和B是兩個單鏈表(帶頭結點)，其表中元素遞增有序。設計一個算法將A和B歸并成一個按元素值遞增有序的單鏈表C，要求輔助空晨為O(1)，并分析算法的時間復雜度。數(shù)據(jù)結構復習題：線性表填空題1、在線性結構中第一結點_____前驅(qū)結點，其余每個結點有且只有______個前驅(qū)結點；最后一個結點______后繼結點。2、對于順序存儲的線性表，當隨機插入或刪除一個元素時，約需平均移動表長______的元素。3、對于長度為n的順序表，插入或刪除元素的時間復雜性為________；對于順序棧或隊列，插入或刪除元素的時間復雜性為_________。4、在線性表的順序存儲中，元素之間的邏輯關系是通過_____相鄰位置_____決定的；在線性表的鏈接存儲中，元素之間的邏輯關系是通過______連接指針______決定的。5、一個單鏈表中刪除*p結點時，應執(zhí)行如下操作:(1)q=p->next;(2)p->data=p->next->data;(3)p->next=__________;(4)free(q);6、對于線性表的順序存儲，需要預先分配好存儲空間，若分配太多則容易造成存儲空間的__________，若分配太少又容易在算法中造成_____溢出_____，因此適應于數(shù)據(jù)量變化不大的情況；對于線性表的鏈接存儲(假定采用動態(tài)結點)，不需要__________存儲空間，存儲器中的整個____動態(tài)存儲區(qū)______都可供使用，分配和回收結點都非常方便，能夠有效地利用存儲空間，在算法中不必考慮_____溢出_____的發(fā)生，因此適應數(shù)據(jù)量變化較大的情況。7、從順序表中刪除第i個元素時，首先把第i個元素賦給_____變參或函數(shù)名_____帶回，接著從______連接指針_______開始向后的所有元素均___________一個位置，最后使線性表的長度_____________。8、向一個長度為n的順序表中的第i個元素(0<=i<=n-1)之前插入一個元素時，需向后移動______個元素。9、在一個長度為n的順序表刪除第i個元素(0<=i<=n-1)時，需向前移動______個元素。10、在單鏈表中設置頭結點的作用是_____簡化插入、刪除算法______。11、在單鏈表中，要刪除某一指定的結點，必須找到該結點的_______結點。12、訪問單鏈表中的結點，必須沿著_____指針鏈___依次進行。13、在雙鏈表中，每個結點有兩個指針域，一個指向________，另一個指向_________。14、在___循環(huán)雙___鏈表上，刪除最后一個結點，其算法的時間復雜度為O(1)。15、在一個單鏈表中的p所指結點之前插入一個s所指結點時，可執(zhí)行如下操作。(1)s->next=_________。(2)p->next=s;(3)t=p->data;(4)p->data=_________。(5)s-.data=_________。16、在一個單鏈表中刪除p所指結點時，應執(zhí)行以下操作：q=p->next;p_data=p->next->data;p->next=______;free(q);17、在一個單鏈表中p所指結點之后插入一個s所指結點時，應執(zhí)行s->next=_______和p->next=________的操作。18、對于一個具有n個結點的單鏈表，在*p結點后插入一個新結點的時間復雜度是____O(1)____；在給定值為x的結點后插入一后新結點的時間復雜度是________。19、在線性表的順序存儲中，元素之間的邏輯關系是通過___物理存儲位置___決定的；在線性表的鏈式存儲中，元素之間的邏輯關系是通過___鏈域的指針值___決定的。20、在一個長度為n的順序表中刪除第i個元素(1<=i<=n)時，需向前移動_______個元素。21、為了設置一個空的順序表L，采用的操作是___L->length=0___。22、刪除順序表的______元素，不需要移動任何元素。23、刪除順序表的___最后一個___元素，不需要移動的元素最多。24、在順序表_____元素后面插入一個元素，不需要移動任何元素。25、插入順序表的______元素，需要移動的元素最多。26、在長度為n的順序表L中查找指定元素值的元素，其時間復雜度為______。27、求單鏈表長度的時間復雜度為_______。28、刪除單鏈表L中某結點*p之后的一個結點，其時間復雜度為______。29、刪除單鏈表L中某結點*p之前的一個結點，其時間復雜度為___O(n)___。30、在一個單鏈表(己知每個結點含有數(shù)據(jù)域data和指針域next)中刪除p所指結點時，應執(zhí)行以下操作：(1)q=p->next;(2)p->data=q->data;(3)p->next=_____;(4)free(q);31、在一個單鏈表中的p所指結點之后插入*s結點時，應執(zhí)行s->next=_____和p->next=______的操作。32、對于一個具有n個結點的單鏈表，在*p結點后插入一個新結點的時間復雜度是_______;在給定值為x的結點后插入一個新結點的時間復雜度是_______。33、刪除雙鏈表L中某結點*p之后的一個結點，其時間復雜度為_______。34、刪除雙鏈表L中某結點*p之前的一個結點，其時間復雜度為_______。35、在非循環(huán)的______鏈表中，可以用表尾指針代替表頭指針。36、對于雙鏈表，在兩個結點之間插入一個新結點需要修改的指針共______。37、在一個雙鏈表中，若要在*p結點之前插入結點*q，則執(zhí)行的操作是______。38、循環(huán)單鏈表L為空的條件是_____。39、在單鏈表中,結點與結點之間的邏輯關系不是通過存儲單元的順序來表示的,而是通過___指向下一個結點的指針___來實現(xiàn)的.40、對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復雜度為____________，在表尾插入元素的時間復雜度為____________。41、對于一個單鏈接存儲的線性表，在表頭插入結點的時間復雜度為____________，在表尾插入元素的時間復雜度為____________。42、在線性表的順序存儲中，若一個元素的下標為i，則它的前驅(qū)元素的下標為____________，后繼元素的下標為____________。43、在線性表的單鏈接存儲中，若一個元素所在結點的地址為p，則其后繼結點的地址為_____p->next_______，若p為一個數(shù)組a中的下標，則其后繼結點的下標的______a[p]->next______。44、在循環(huán)單鏈表中，最后一個結點的指針域指向____________結點。45、在雙向鏈表中每個結點包含有兩個指針域，一個指向其____________結點，另一個指向其____________結點。46、在循環(huán)雙向鏈表中表頭結點的左指針域指向____________結點，最后一個結點的右指針域指向____________結點。47、在以ＨＬ為表頭指針的帶表頭附加結點的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為____________和____________。50、在由數(shù)組a中元素結點構成的單鏈表中，在下標為i的結點的后面插入一個下標為j的結點時，需要進行的操作為____________和____________語句。數(shù)據(jù)結構復習題：線性表問答題1、線性表有兩種存儲結構：一是順序表，二是鏈表。試問：(1)兩種存儲表示各有哪些主要優(yōu)缺點?(2)如果有n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)發(fā)生變化，線性表的總數(shù)也會自動地改變。在此情況下，應選用哪種存儲結構?為什么?(3)若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素，那么，應采用哪種存儲結構?為什么?解答：(1)順序存儲是按索引（隱含的）直接存取數(shù)據(jù)元素，方便靈活，效率高，但插入、刪除操作時將引起元素移動，因而降低效率；鏈接存儲內(nèi)存采用動態(tài)分配，利用率高，但需增設指示結點之間有序關系的指針域，存取數(shù)據(jù)元素不如順序存儲方便，但結點的插入、刪除操作十分簡單。(2)應選用鏈接表存儲結構。其理由是，鏈式存儲結構用一組任意的存儲單元依次存儲線性表里各元素，這里存儲單元可以是連續(xù)的，也可以是不連續(xù)的。這種存儲結構，在對元素作插入或刪除運算時，不需要移動元素，僅修改指針即可。所以很容易實現(xiàn)表的容量擴充。(3)應選用順序存儲結構。其理由是，每個數(shù)據(jù)元素的存儲位置和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的序號成正比的常數(shù)。由此，只要確定了起始位置，線性表中任一數(shù)據(jù)元素都可隨機存取，所以線性表的順序存儲結構是一種隨機存取的存儲結構。而鏈表則是一種順序存取的存儲結構。用線性表的順序結構來描述一個城市的設計和規(guī)劃合適嗎?為什么?不合適。因為一個城市的設計和規(guī)劃涉及非常多的項目，很復雜，經(jīng)常需要修改、擴充和刪除各種信息，才能適應不斷發(fā)展的需要。有鑒于此，順序線性表不能很好適應其需要，故是不合適的。在單鏈表和雙向表中，能否從當前結點出發(fā)訪問到任一結點?在單鏈表中只能由當前結點訪問其后的任一結點，因為沒有指向其前驅(qū)結點的指針。而在雙向鏈表中，既有指向后繼結點的指針又有指向前驅(qū)結點的指針，故可由當前結點出發(fā)訪問鏈表中任一結點。4、編寫下列算法(1)向類型有l(wèi)ist的線性表L的第i個元素（0≤i≤L.len）之后插入一個新元素x。(2)從類型為list的線性表L中刪除其值等于x的所有元素。(3)將兩個有序表A和B合并成一個有序表C，其中A，B，C均為list類型的變參。(1)解答:statusinsert(SqListL,inti,ElemTypex){//向線性表L中第i個元素之后插入值為x的新元素(1)if(L.len==m0)error('overflow');(2)if(i<0)||(i>L.len)error('outofrange');(3)for(j=L.len;j>=i＋1;--j)L.vec[j＋1]＝L.vec[j];}(4)L.vec[i＋1]＝x;(5)L.len＝len＋1;}(2)解答:statusdelete(L,x){//從線性表L中刪除其值等于x的所有元素i＝1;while(i<＝L.len)if(L.vec[i]==x){(Ⅰ)for(j＝i＋1;j<=L.len;++j)L.vec[5、編寫下列算法，假定單鏈表的表頭指針用HL表示，類型為linklist。(1)將一個單鏈表中的所有結點按相反次序鏈接。(2)刪除單鏈表中第i個（i≥1）結點。(3)刪除單鏈表中由指針p所指向的結點。(4)從帶有附加表頭結點的循環(huán)單鏈表中刪除其值等于x的第一個結點。(5)在單鏈表中指針p所指結點之前插入一個值為x的新結點。(6)從循環(huán)單鏈表中查找出最小值。(7)根據(jù)一維數(shù)組A(1:n)中順序存儲的具有n個元素的線性表建立一個帶有附加表頭結點的單鏈表。解答：(1)將一個單鏈表中的所有結點按相反次序鏈接。(1)解答:statuscontrary(HL){//使HL單鏈表中的所有結點按相反次序鏈接p＝HL;//p指向未被逆序的第一個結點，初始指向原表頭結點HL＝nil;//HL指向逆序后的表頭結點，初始值為空while(p!=nil){(1)q＝p;//q指向?qū)⒈荒嫘蜴溄拥慕Y點(2)p＝p＾.next;(3)q＾.next＝HL;(4)HL＝q;}}(2)刪除單鏈表中第i個（i≥1）結點。(2)解答:statusdelete(HL,i){(1)if(i<＝0)or(HL＝nil)error('noth&&le');(2)if(i＝1){HL＝HL->next;return;}(3)j＝1;p＝HL;//p指針所指向的結點，是單鏈表中第j對鏈表設置頭結點的作用是什么?(至少說出兩條好處)解答：(1)對帶頭結點的鏈表，在表的任何結點之前插入結點或刪除表中任何結點，所要做的都是修改前一結點的指針域，因為任何元素結點都有前驅(qū)結點。若鏈表沒有頭結點，則首元素結點沒有前驅(qū)結點，在其前插入結點或刪除該結點時操作會復雜些。(2)對帶頭結點的鏈表，表頭指針是指向頭結點的非空指針，因此空表與非空表的處理是一樣的。在單鏈表、雙鏈表和單循環(huán)表中，若僅知道指針p指向某結點，不知道頭指針，能否將結點*p從相應的鏈表中刪去？若可以，其時間復雜度各為多少？解答：1.單鏈表。當我們知道指針p指向某結點時，能夠根據(jù)該指針找到其直接后繼，但是由于不知道其頭指針，所以無法訪問到p指針指向的結點的直接前趨。因此無法刪去該結點。2.雙鏈表。由于這樣的鏈表提供雙向鏈接，因此根據(jù)已知結點可以查找到其直接前趨和直接后繼，從而可以刪除該結點。其時間復雜度為O(1)。3.單循環(huán)鏈表。根據(jù)已知結點位置，我們可以直接得到其后相鄰的結點位置(直接后繼)，又因為是循環(huán)鏈表，所以我們可以通過查找，得到p結點的直接前趨。因此可以刪去p所指結點。其時間復雜度應為O(n)。簡述順序表和鏈表存儲方式的特點。答：順序表可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時將會引起元素的大量移動，因而降低效率；而鏈表內(nèi)存采用動態(tài)分配，利用率高，但需增設指示結點之間關系的指針域，存取數(shù)據(jù)元素不如順序表方便，但結點的插入、刪除操作較簡單。有兩個遞增有序表，設計一個算法將它們歸并成一個有序表(假設每個表中沒有重復關鍵字的元素，歸并時重復關鍵字的元素只歸并一次)。答：voidMerge(LinkList&La,LinkListLb){pa=La->next;pb=Lb->next;p=La;while(pa&&pb){if(pa->data<=pb->data){p->next=pa;p=pa;pa=pa->next;}else{p->next=pb;p=pb;pb=pb->next;}}if(pa)p->next=pa;elsep->next=pb;free(Lb);}3棧和隊列沈陽理工大學應用技術學院信息與控制學院計算機科學與技術教研室2011-5-8數(shù)據(jù)結構復習題：棧和隊列單選題1、在一個具有n個單元的順序棧中，假定以地址低端作為棧底，以top作為棧頂指針，則當做退棧處理時，top變化為_____。2、向順序棧中壓入元素時，是__先移動棧頂指針，后存入元素___。3、在一個順序存儲的循環(huán)隊列中，隊首指針指向隊首元素的__前一個位置___。4、若進棧序列為1,2,3,4,進棧過程中可以出棧，則_____不可能是一個出棧序列。5、在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊首指針和隊尾指針，則判斷隊空的條件是_____。6、在具有n個單元的順序存儲的循環(huán)隊列中，假定front和rear分別為隊首指針和隊尾指針，則判斷隊滿的條件是_____。7、向一個棧項指針為hs的鏈棧中插入一個*s結點時，則執(zhí)行_____。8、在一個鏈隊列中，假定front和rear分別為隊首指針和隊尾指針，則進行插入*s結點的操作時應執(zhí)行_____。9、棧的特點是_______隊的特點是______10、棧和隊列的共同點是_______。11、一個棧的進棧序列是a,b,c,d,e,則棧的不可能的輸出序列是________。12、若己知一個棧的進棧序列是1,2,3,…,n,其輸出序列為p1,p2,p3,…,pn,若p1=n,則pi(1<i<=n)為________。13、若己知一個棧的進棧序列是1,2,3,…,n,其輸出序列為p1,p2,p3,…,pn,若pn=n,則pi(i<=i<n)為_______。14、若己知一個棧的進棧序列是1,2,3,…,n,其輸出序列為p1,p2,p3,…,pn，若p1=3,則p2_______。15、若己知一個棧的進棧序列p1,p2,p3,…,pn,輸出序列是1,2,3,…,n,若p3=1,則p1________。16、若己知一個棧的進棧序列p1,p2,p3,…,pn，輸出序列是1,2,3,…,n。若pn=1,則pi(1<=i<n)為______。17、判定一個順序棧st(最多元素為MaxSize)為空的條件是_______。18、判定一個順序棧st(最多元素為MaxSize)為棧滿的條件是_______。19、最不適合用作鏈棧的鏈表是___只有表頭指針沒有表尾指針的循環(huán)單鏈表_____。20、向一個棧項指針為hs的鏈棧中插入一個s所指結點時，則執(zhí)行_______。21、從一個棧項指針為hs的鏈棧中刪除一個結點時，用x保存被刪結點的值，則執(zhí)行__x=hs->data;hs=hs->next____。22、一個隊列的入隊序列是1,2,3,4,則隊列的輸出序列是_______。23、判定一個環(huán)形隊列qu(最多元素為MaxSize)為空的條件是________。24、判定一個環(huán)形隊列qi(最多元素為MaxSize)為滿隊列的條件是________。25、環(huán)形順序隊列中是否可以插入下一個元素,________。26、環(huán)形隊列用數(shù)組A[0...MaxSize-1]存放其元素值,己知其頭尾指針分別是front和rear,則當前隊列的元素個數(shù)是_______。27、若用一個大小為6的一維數(shù)組來實現(xiàn)環(huán)形隊列，且當前rear和front的值分別為0和3。當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別是______。28、最不適合用作鏈隊的鏈表是__只帶隊頭指針的非循環(huán)雙鏈表____。29、在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則插入s所指結點的運算是_______。30、在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則刪除一個結點的運算是_______。31、用單鏈表表示的鏈隊的隊頭在鏈用不著的____鏈頭____位置。32、中綴表達式A*(B+C)/(D-E+F)的后綴表達式是________。33、己知一個棧的進棧序列是ABC,出棧序列為CBA,經(jīng)過的棧操作是________。34、判定一個順序棧st為(元素個數(shù)最多為MaxSize)空的條件為______。35、判定一個順序棧st(元素個數(shù)最多為MaxSize)為棧滿的條件是______。36、表達式a*(b+c)-d的后綴表達式是______。37、表達式(2+2*3)*2+6*3/2的后綴表達式是______。38、鏈棧與順序棧相比有一個明顯的優(yōu)點,即___通常不會出現(xiàn)棧滿的情況___。39、最不適合用作鏈棧的鏈表是__只有表頭指針沒有表尾指針的循環(huán)單鏈表____。40、如果以鏈表作為棧的存儲結構,則退鏈棧操作時___必須差別鏈棧是否空___。41、向一個不帶頭結點的棧指針為1st的鏈棧中插入一個s所指結點時,則執(zhí)行______。42、從一個不帶頭結點的棧頂指針為1st的鏈棧中刪除一個結點時,用x保存被刪結點的值,則執(zhí)行______。43、一個棧的進棧序列是a,b,c,d,e,則棧的不可能的輸出序列是______.44、在一個長度為n的順序存儲的集合中查找值為x的元素時，在等概率情況下，查找成功時的平均查找長度為_________。45、在一個長度為n的鏈接存儲的集合中查找值為x的元素時，算法的時間復雜度為___O(n)______。46、已知一個元素x不屬于一個長度為n的順序或鏈接存儲的集合Ｓ中的元素，把它插入集合Ｓ時不進行比較過程，則插入過程的時間復雜度為_________。47、設一個具有t個非零元素的m*n大小的稀疏矩陣采用順序存儲，求其轉(zhuǎn)置矩陣的普通轉(zhuǎn)置算法的時間復雜度為____O(n*t)_____。數(shù)據(jù)結構復習題：棧和隊列判斷題1、棧底元素是不能刪除的元素。2、順序棧中元素值的大小是有序的。3、在n個元素進棧后,它們的出棧順序和進棧順序一定正好相反。4、棧頂元素和棧底元素有可能是同一個元素。5、若用S[1]-S[m]表示順序棧的存儲空間,則對棧的進棧、出棧操作最多只能進行m次。F6、空棧沒有棧頂指針。數(shù)據(jù)結構復習題答案：棧和隊列判斷題1、False2、False3、True4、True5、False6、False數(shù)據(jù)結構復習題：棧和隊列算法分析題設計一個算法,利用棧的基本運算將指定棧中的內(nèi)容進行逆轉(zhuǎn)。statusNizhuan(sqstacks,inta,intb,intt){If(s.top==s.base)error(‘nodata’);for(i=0;i<s.stacksize/2;i++){a=*--top;b=*s.base;a=t;t=b;b=a;s.top--;s.base++;}}設計一個算法,利用棧的基本運算返回指定棧中的棧底元素。statusGetbase(Aqstacks,int&e){If(s.top==s.base)Error(‘nodata’)elsee=*s.base;returne;}有兩個棧s1和s2共享存儲空間c[1..MaxSize],其中一個棧底設在c[1]處,另一個棧底設在c[MaxSize]處,分別編寫s1和s2的進棧push(i,x)、退棧pop(i)和設置棧空setnull(i)的函數(shù),其中i=1,2。注意:僅當整個空間c[1..MaxSize]占滿時才產(chǎn)生上溢。（1）初始化操作【共享棧的初始化】intinitDupStack(dupsqstack*s){/*創(chuàng)建兩個共享鄰接空間的空棧由指針S指出*/if((s=(dupsqstack*)malloc(sizeof(dupsqstack)))==NULL)returnFALSE;s->lefttop=-1;s->righttop=MAXNUM;returnTRUE;}（2）入棧操作【共享棧的入棧操作】intpushDupStack(dupsqstack*s,charstatus,Elemtypex){*把數(shù)據(jù)元素x壓入左棧（status=’L’）或右棧（status=’R’）*/if(s->lefttop+1==s->righttop)returnFALSE;/*棧滿*/if(status=’L’)s->stack[++s->lefttop]=x;/*左棧進棧*/elseif(status=’R’)s->stack[--s->lefttop]=x;/*右棧進棧*/elsereturnFALSE;/*參數(shù)錯誤*/returnTRUE;}（3）出棧操作【共享棧的出棧操作】ElemtypepopDupStack(dupsqstack*s,charstatus){/*從左棧（status=’L’）或右棧（status=’R’）退出棧頂用不帶頭結點的單鏈表存儲鏈棧,設計初始棧、判斷棧是否為空、進棧和出棧等相應的算法。（1）入棧操作【單個鏈棧的入棧操作】intpushLstack(slStacktype*top,Elemtypex){//將元素x壓入鏈棧top中slStacktype*p;if((p=(slStacktype*)malloc(sizeof(slStacktype)))==NULL)returnFALSE;//申請一個結點p->data=x;p->next=top;top=p;returnTRUE;}（2）出棧操作【單個鏈棧的出棧操作】ElemtypepopLstack(slStacktype*top){//從鏈棧top中刪除棧頂元素slStacktype*p;Elemtypex;if(top==NULL)returnNULL;//空棧p=top;top=top->next;x=p->data;free(p);returnx;}數(shù)據(jù)結構復習題：棧和隊列填空題1、在具有n個單元、順序存儲的循環(huán)隊列中，隊滿時共有___n-1___個元素。2、棧和隊列的區(qū)別僅在于____刪除運算的不同____。3、通常元素進棧的操作是________。4、通常元素退棧的操作是________。5、一個棧的輸入序列是12345,則棧的輸出序列432512是__________。6、一個棧的輸入序列是12345,則棧的輸出序列12345是________。7、設有一個順序棧S,元素s1,s2,s3,s4,s5,s6依次進棧,如果6個元素的出棧順序為s2,s3,s4,s6,s5,s1,則順序棧的容量至少應為________。8、設棧采用順序存儲結構,若己知i-1個元素進棧,則將第i個元素進棧時,進棧算法的時間復雜度為________。9、若用不帶頭結點的單鏈表來表示鏈棧S,則創(chuàng)建一個空棧所要執(zhí)行的操作是___S==null_____。10、從環(huán)形隊列中插入一個元素時,通常的操作是________。11、在具有n個單元的環(huán)形隊列(共有MaxSize個單元)中,隊滿時共有___MaxSize-1_____個元素。12、在鏈表qu中,判定只有一個結點的條件是____qu->front==qu->rear&&qu->front!=NULL____。13、設棧S和隊列Q的初始狀態(tài)為空,元素a1,a2,a3,a4,a5,a6,a7和a8依次通過棧S,一個元素出棧后立即進入隊列Q,若8個元素出隊列的順序是a3,a6,a7,a5,a8,a4,a2,a1,則棧S的容量至少應該是多少(即至少應該容納多少個元素)?14、設有算術表達式x+a*(y-b)-c/d,該表達式的前綴表達為____-+x*a-yb/cd____。后綴表示為______。15、棧是一種具有______特性的線性表。16、順序棧和鏈棧的區(qū)別僅在于___存儲結構___的不同。17、如果棧的最大長度難以估計,則最好使用______。18、一個棧的輸入序列是12345,則棧的輸出序列12345是______。19、設棧采用順序存儲結構,若己知i-1個元素進棧,則將第i個元素進棧時,進棧算法的時間復雜度為______。20、表達式23+((12*3-2)/4+34*5/7)+108/9的后綴表達式是______。21、若用不帶頭結點的單鏈表來表示鏈棧1st,則創(chuàng)建一個空棧所要執(zhí)行的操作是______。22、對于鏈棧1st,進棧操作在___鏈棧頭___端進行,出棧操作在__鏈棧頭___端進行。23、將遞歸算法轉(zhuǎn)換為非遞歸算法時,通常使用___棧___這種數(shù)據(jù)結構。24、有如下遞歸算法:voidprint(intw){inti;if(w!=0){print(w-1);for(i=1;i<=w;i++)printf("%3d",w);printf("\n");}}調(diào)用語句printf(4)的結果是______。122333444425、有如下遞歸過程:voidreverse(intm){printf("%d",n%10);if(n/10!=0)reverse(n/10);}調(diào)用語句reverse(582)的結果是______。26、求順序存儲的集合的長度的時間復雜度為____________。27、求鏈接存儲的集合的長度的時間復雜度為______O(n)______。28、設集合S的長度為n，則判斷x是否屬于集合Ｓ的時間復雜度為____________31、在稀疏矩陣的順序存儲中，利用一個數(shù)組來存儲非零元素，該數(shù)組的長度應______大于等于______對應三元組線性表的長度。數(shù)據(jù)結構復習題：棧和隊列問答題試述棧的基本性質(zhì)?解答：由棧的定義可知，這種結構的基本性質(zhì)綜述如下：(1)集合性。棧是由若干個元素集合而成，當沒有元素的空集合稱為空棧；(2)線性結構。除棧底元素和棧頂元素外，棧中任一元素均有唯一的前驅(qū)元素和后繼元素；(3)受限制的運算。只允許在棧頂實施壓入或彈出操作，且棧頂位置由棧指針所指示；(4)數(shù)學性質(zhì)。當多個編號元素依某種順序壓入，且可任意時刻彈出時，所獲得的編號元素排列的數(shù)目，恰好滿足卡塔南數(shù)列的計算，即：Ｃn＝Ｃn2n/(n＋1)其中，n為編號元素的個數(shù)，Cn是可能的排列數(shù)目。何謂隊列的上溢現(xiàn)象?解決它有哪些方法，且分別簡述其工作原理。解答：在隊列的順序存儲結構中，設隊頭指針為front,隊尾指針為rear,隊的容量（存儲空間的大小）為m。當有元素要加入隊列時，若rear＝m（初始時reat＝0），則發(fā)生隊列的上溢現(xiàn)象，該元素不能加入隊列。這里要特別注意的是：隊列的假溢出現(xiàn)象，隊列中還有空余的空間，但元素不能進隊列。造成這種現(xiàn)象的原因是由于隊列的操作方式所致。解決隊列的上溢有以下幾種方法：(1)建立一個足夠大的存儲空間，但這樣做往往會造成空間使用的效率低。(2)當出現(xiàn)假溢出時，可采用以下幾種方法：①采用平移元素的方法。每當隊列中加入一個元素時，隊列中已有的元素向隊頭移動一個位置（當然要有空余的空間可移）；②每當刪去一個隊頭元素時，則依次序移隊中的元素，始終使front指針指向隊列中的第一個位置；③采用循環(huán)隊列方式。把隊頭隊尾看成是一個首尾相鄰的循環(huán)隊列，雖然物理上隊3、假定用一個循環(huán)單鏈表表示隊列（稱此為循環(huán)鏈隊），該隊列只設一個隊尾指針，不設隊首指針，試編寫下列算法：(1)向循環(huán)鏈隊插入一個元素為x的結點。(2)從循環(huán)鏈隊中刪除一個結點（假定不需要保留被刪除結點的值和不需要回收結點）。解答：(1)解答:statusinsert(Rear,x){//假定Rear為循環(huán)鏈隊的隊尾指針，x為待插入的元素(1)malloc(p);p->data＝x;//建立值為x的新結點p＾(2)if(Rear＝nil){Rear＝p;Rear->next＝p;}else{p->next＝Rear->next;Rear->next＝p;Rear＝p;}//若條件成立則建立循環(huán)鏈隊的第一個結點，否則在隊尾插入p＾結點}(2)解答:statusdelete(Rear){if(Rear＝nil)error('underflow');if(Rear->next==Rear)Rear＝nil;elseRear->next＝Rear->next->next;}//Rear＾.next所指向的結點為循環(huán)鏈隊的隊首結點為什么說棧是一種后進先出表?棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數(shù)為零時稱為空棧。插入一般稱為進棧（PUSH），刪除則稱為退棧（POP）。棧也稱為后進先出表（LIFO--LastINFirstOut表）。對于一個棧,給出輸入項A,B,C。如果輸入項序列由A,B,C所組成,試給出全部可能的輸出序列。AＢＣ，ＢＡＣ，ＣＢＡ有字符串次序為3*y-a/y↑2,試利用棧給出將次序改變?yōu)?y-*ay2↑/-的操作步驟。(可用X代表掃描該字符串函數(shù)中順序取一字符進棧的操作,用S代表從棧中取出一個字符加到新字符串尾的出棧的操作)。例如:ABC變?yōu)锽CA,則操作步驟為XXSXX。X:進棧S:出棧XSXXXSSSXXSXXSXXSSSS7、跟蹤以下代碼,顯示每次調(diào)用后隊列中的內(nèi)容。InitQueue(qu);EnQueue(qu,'A');EnQueue(qu,'B);EnQueue(qu,'C);EnQueue(qu,x;EnQueue(qu,x;EnQueue(qu,'D);EnQueue(qu,'E);EnQueue(qu,'F);EnQueue(qu,x)EnQueue(qu,'G);EnQueue(qu,X)EnQueue(qu,X)EnQueue(qu,X)解答：InitQueue(qu);隊列為空EnQueue(qu,'A');隊列為AEnQueue(qu,'B);隊列為ABEnQueue(qu,'C);隊列為ABCEnQueue(qu,x;隊列為ABCxEnQueue(qu,x;隊列為ABCxxEnQueue(qu,'D);隊列為ABCxxDEnQueue(qu,'E);隊列為ABCxxDEEnQueue(qu,'F);隊列為ABCxxDEFEnQueue(qu,x)隊列為ABCxxDEFxEnQueue(qu,'G);隊列為ABCxxDEFxGEnQueue(qu,X)隊列為ABCxxDEFxGXEnQueue(qu,X)隊列為ABCxxDEFxGXXEnQueue(qu,X)隊列為ABCxxDEFxGXXX8、假設Q[0..10]是一個線性隊列,初始狀態(tài)為front=rear=0,畫出做完下列操作后隊列的頭尾指針的狀態(tài)變化情況,若不能入隊,請指出其元素,并說明理由。d,e,b,g,h入隊d,e出隊i,j,k,l,m入隊n,o,p入隊解答：d,e,b,g,h入隊d e b g h Frd,e出隊b g h