(題)數據結構復習題

Ch2數組（共23題，其中14道算法設計題）一、填空題1、填空題（每小空1分，共5分）一維數組的邏輯結構是（①），存儲結構是（②）。對于二維數組，有（③）和（④）兩種不同的存儲方式。對于一個二維數組A[m][n],若采取按行存儲的方式，則任一數組元素A[i][j]相對于A[0][0]的地址為（⑤）。Key：①稅性結構②順序存儲表示③行優(yōu)先順序④列優(yōu)先順序⑤n*i+j二、判斷題2、判斷卜.列敘述的對錯。如果正確，在題前的括號內填入“寸’，否則填入“X”。（x）線性表的邏輯順序與物理順序總是一致的。（x）線性表的順序存儲表示優(yōu)于鏈式存儲表示。（寸）線性表若采用鏈式存儲表示時所有存儲單元的地址可連續(xù)可不連續(xù)。（x）二維數組是其數組元素為線性表的線性表。（ID每種數據結構都應具備三種基本運算：插入、刪除和搜索。三、簡答題3,順序表的插入和刪除要求仍然保持各個元素原來的次序。設在等概率情形下，對有127個元素的順序表進行插入，平均需要挪移多少個元素。刪除一個元素，又平均甯要挪移多少個元素，Key： 插入時平均挪移元素個數AMN二- 所以平均挪移 63.5個元素刪除時平均挪移元素個數AMN刪除時平均挪移元素個數AMN二-所以平均挪移 63個元素4、設有一個10x10的對稱矩陣A[10][i0].采取按行壓縮存儲的方式存放于一個一維數組B□中，則數組B□的容員應有多大？若設A[0][0]為第一個元素，存放于B[0],旦數組A口□的每一個數組元素在數組B口中占一個數組元素位置，則A[8][5]在數組B□中的地址是多少？Key：1)數組B共應有1｝二55個元素。2)對于上三角矩陣，A[8][5]=A[5][8]^——5卜)=43對于下三角矩陣，A[81[5]= '打=415、設有三對角矩陣A[n][n],將其三條對角線中的元素逐行存儲到一維數組B[3n-2]中，使得B[k]=A[i][j]?試求：(1)用1,J表示k的地址轉換公式：(2)用k表示1,j的地址轉換公式：Key：1)在一維數組B中在第1行，它前面有3*1-1個非零元素，在本行第j列前面有j-i+1個，所以元素A[i][j]在B中的位置為k=2*i+jo2)1= (k+1)/3」j=k-2*i6、上三角矩陣A[n][n],將其上三角元素逐行存儲到一維數組使得B[k]:A[i][j],且k=f](i)+f2(j)+Co試推導出函數f」⑴、f=(j)和常數C,要求f】⑴和G(J)中不包含常數項。Kev：若iWj,數組元素在數組B中的存放位置為u+<n-D+……+(n-i+1)+j-i即為：?…若Aj,數組元素在矩陣的下三角部份，在數組B中沒有存放，因此找它們的對稱元素即曰)以……7、設有一個二維數組A假設A設][0]存放位置在644八>?A[2][2]存放位置在676g,每一個元素占一個空間，問A[4][4]在什么位置.，下標”表示用10進數表示。8,設A和B均為卜三角矩陣，每一個都有n行。因此在下三角區(qū)域中各有n(n+1)/2個元素。另設有一個二維數組C,它有n行站1歹I」。試設計一個方案，將兩個矩陣A和B中的卜三角區(qū)域元素存放于同一個C中。要求將A的下三角區(qū)域中的元素存放于C的下三角區(qū)域中，B的下三角區(qū)域中的元素轉置后存放于C的.上三角區(qū)域中。并給出計算A的矩陣元素axj和B的矩陣元素坨在C中的存放位置下標的公式。9”設帶狀炬陣A[n][n]是nxn階的方陣，其中所有的非零元 \XAXX\QTOC\o"1-5"\h\z素都在由主對角線及主對角線上下各b條對角線構成的帶狀 |區(qū)域內，其它都為零元素。試問： 11U)該帶狀矩陣中有多少個非零元素？ &'J(2)若用一個一維數組B□按行順序存放各行的非零5條對角元素，且設存放在B[0]中，請給出一個公式，計算任一非零元素"維數組3中的存放位置。四、算法設計題10.己知整數數組A□中有n個兀素，試設計一個算法，求數組中所有兀素值的和。Key：intsuinariay(array*n)hitarray[],n：(inri?sum=0：for(i=0：i<n：i++)Isum+=anay[i]:)piiiitf("thesumofarrayissum):11、己知整數數組A口中有n個元素，試設計一個算法，求數組中所有元素值的平均值。Key：mrsumanay(array,n)mtcinay[]?n；inti.sum=0：floatave：for(i=0：i<n：i++){sum+=anay[i]:ave=(float)(suinii):}pnntf("theaveofarrayis%f\n"，ave)：)12、設有一個線性表(eo,ei,…，en-2?5)存放在一個一維數組A[anaySize]+的前n個數組元素位置。請編寫一個函數將這個線性表原地逆置，即將數組的前n個地址的內容置換為(ez,en-2.…，ei.eo)。(見題庫chi六⑴)Key：voidinverse(datan,peA[].mtn)(data_typetiup：for(i=0：i<=(n-1)/2；i++)(tmp=A[i]:A[i]=A[n-i-l]:A[u-i-l]=tinp：j)13、假定數組A[anaySize]中有多個零元素，試寫出一個函數，將A中所有的非零元素依次移到數組A的前端A[i](0W1-anaySize)。Key：voidcompact(data_typeA[]?mtAiiaySize>inrfree=0,i：〃非零元素存放地址〃非零元素存放地址〃檢測整個數組〃發(fā)現非零元素if(A[i]!=0)(if(i!=free)(a[fiee]=a[i]；a[i]=0；}free++：)!)14、已知A[n]為整數數組.試寫出實現卜.列運算的遞歸算法:(1)求數組A中的最大整數。(2)求n個整數的和。(3)求11個整數的平均值Key：hitmaxaiTay(aiiay,n)mr*anay：mtn：(inttemp；if(n=l)1eturnanay[0]：elsejtemp=max_aiiay(may,n-l)：if(array[n-1]>lemp)returnaiTay[n-1]：elsereturntemp；mrsumanay(arrayn)m(*anay：intn；(if(11—1)rerurnarray]。]:elseletuin(anay[u-l]+sum_airay(arniy,n-1)):)floatave_aiTay(array?n)m(*cinay：hitn：(floattemp：if(n—1)letuin(float)anay[0]；elseletuin(float)(aiiay[n-l]+aveariay(array?n-l)*(n-1))/n；)15、若矩陣中的某一元一元][j]是第i行中的最小值,同時又是第j列中的最大值,則稱此元素為該矩陣的一個單戈點。假設以二維數組存放矩陣?試編寫一個函數，確定鞍點在數組中的位置（若鞍點存在時），并分析該函數的時間復雜度。16、己知一個順序表中的元素按元素值非遞減有序羅列，試定義順序表的存儲表示，并編寫一個函數.刪除表中值相同的多余元素。17、設有兩個整數類型的順序表A（有址個元素）和B（有n個元素），其元素均以從小到大的升序羅列。試編寫一個函數，將這兩個順序表合并成一個順序表C,要求C的兀素也以從小到大的升序羅列。（見題庫chi六（2））18、試編寫一個函數計算工*2。的值.其結果存放于數組A[airaySize]的第n個數組元素中，OWnvarr<iySizeo若設計算機41允許的整數的最大值為imxlnl.則當門'aySize或者對于某一個k（0Wk<n）,使得k'*2k>niaxlnt時，應按出錯姓理。一種出錯處理方式是在算法實現時用返回糧數函數值0,1來區(qū)別是正常返回還是錯誤返回。試利用這種方式來實現函數。19、試編寫一個函數，將一個有n個非零元素的整數一維數組A[n]拆分為兩個一維數組，使得A口中大于零的元素存放在B口中，小于零的元素存放在C[]中。20、設定整數數組的數據在行、列方向上都按從小到大的順序排序，旦整型變量x中的數據在B中存在。試設計一個算法，找出一對滿足==x的i,j值。要求比較次數不超過m+iio21、己知在一維數組知m+n]中挨次存放著兩個順序表<ai.az.…,a.）和（b],b?）&）o試編寫一個函數，將數組中兩個順序表的位置互換即將（也，b2,b（1）放在（ai,a?....?①）的前面。22、試編寫一個函數，以不多于3n/2的平均比較次數.在一個有n個整數的順序表A中找出具有最大值和最小值的整數。（見題庫chi六（2））23、設入二（ana2.aJ和日二（bPb2.成）均為順序表，&和B,分別是除去最大公共前綴后的子表。如人:（b.e.i,j,i,n,g）