(題)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題

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