數(shù)據(jù)結(jié)構(gòu)試題庫教材

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

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

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