(题)数据结构复习题

Ch2数组（共23题，其中14道算法设计题）一、填空题1、填空题（每小空1分，共5分）一维数组的逻辑结构是（①），存储结构是（②）。对于二维数组，有（③）和（④）两种不同的存储方式。对于一个二维数组A[m][n],若采取按行存储的方式，则任一数组元素A[i][j]相对于A[0][0]的地址为（⑤）。Key：①税性结构②顺序存储表示③行优先顺序④列优先顺序⑤n*i+j二、判断题2、判断卜.列叙述的对错。如果正确，在题前的括号内填入“寸’，否则填入“X”。（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行。因此在下三角区域中各有n(n+1)/2个元素。另设有一个二维数组C,它有n行站1歹I」。试设计一个方案，将两个矩阵A和B中的卜三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的.上三角区域中。并给出计算A的矩阵元素axj和B的矩阵元素坨在C中的存放位置下标的公式。9”设带状炬阵A[n][n]是nxn阶的方阵，其中所有的非零元 \XAXX\QTOC\o"1-5"\h\z素都在由主对角线及主对角线上下各b条对角线构成的带状 |区域内，其它都为零元素。试问： 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：〃非零元素存放地址〃非零元素存放地址〃检测整个数组〃发现非零元素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来区别是正常返回还是错误返回。试利用这种方式来实现函数。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）