还剩6页未读,继续阅读
文本内容:
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个元素
4、设有一个10x10的对称矩阵A
[10][i0].采取按行压缩存储的方式存放于一个一维数组B□中,则数组B□的容员应有多大?若设A
[0]
[0]为第一个元素,存放于B
[0]旦数组A口□的每一个数组元素在数组B口中占一个数组元素位置,则A
[8]
[5]在数组B□中的地址是多少?Key1数组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用1J表示k的地址转换公式2用k表示1j的地址转换公式Key1在一维数组B中在第1行,它前面有3*1-1个非零元素,在本行第j列前面有j-i+1个,所以元素A[i][j]在B中的位置为k=2*i+jo21=k+1/3」j=k-2*i
6、上三角矩阵A[n][n]将其上三角元素逐行存储到一维数组使得B[k]:A[i][j]且k=f]i+f2j+Co试推导出函数f」⑴、f=j和常数C要求f】⑴和GJ中不包含常数项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行因此在下三角区域中各有nn+1/2个元素另设有一个二维数组C它有n行站1歹I」试设计一个方案,将两个矩阵A和B中的卜三角区域元素存放于同一个C中要求将A的下三角区域中的元素存放于C的下三角区域中,B的下三角区域中的元素转置后存放于C的.上三角区域中并给出计算A的矩阵元素axj和B的矩阵元素坨在C中的存放位置下标的公式9”设带状炬阵A[n][n]是nxn阶的方阵,其中所有的非零元\XAXX\Q素都在由主对角线及主对角线上下各b条对角线构成的带状|区域内,其它都为零元素试问11U该带状矩阵中有多少个非零元素?J2若用一个一维数组B□按行顺序存放各行的非零5条对角元素,且设存放在B
[0]中,请给出一个公式,计算任一非零元素维数组3中的存放位置
四、算法设计题
10.己知整数数组A□中有n个兀素,试设计一个算法,求数组中所有兀素值的和Key intsuinariayarray*nhitarray[]n inri»sum=0fori=0in i++Isum+=anay[i]:piiiitfthesumofarrayissum:
11、己知整数数组A口中有n个元素,试设计一个算法,求数组中所有元素值的平均值Key mrsumanayarraynmtcinay[]»n;inti.sum=0floatave fori=0in i++{sum+=anay[i]:ave=floatsuinii:}pnntftheaveofarrayis%f\n,ave
12、设有一个线性表eoei…,en-2»5存放在一个一维数组A[anaySize]+的前n个数组元素位置请编写一个函数将这个线性表原地逆置,即将数组的前n个地址的内容置换为ezen-
2.…,ei.eo见题库chi六⑴Key voidinversedatanpeA[].mtndata_typetiup fori=0i=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-anaySizeKey voidcompactdata_typeA[]»mtAiiaySizeinrfree=0i for1=0;iAiiaySize;i++iifA[i]!=0ifi!=freea[fiee]=a[i];a[i]=0;}free++!
14、已知A[n]为整数数组.试写出实现卜.列运算的递归算法:1求数组A中的最大整数2求n个整数的和3求11个整数的平均值Key hitmaxaiTayaiiaynmr*anay mtninttemp;ifn=l1eturnanay
[0]elsejtemp=max_aiiaymayn-l ifarray[n-1]lempreturnaiTay[n-1]elsereturntemp;mrsumanayarraynm*anay intn;if11—1rerurnarray]]:elseletuinanay[u-l]+sum_airayarniyn-1:floatave_aiTayarray»nm*cinay hitnfloattemp ifn—1letuinfloatanay
[0];elseletuinfloataiiay[n-l]+aveariayarray•n-l*n-1/n;
15、若矩阵中的某一元一元][j]是第i行中的最小值同时又是第j列中的最大值则称此元素为该矩阵的一个单戈点假设以二维数组存放矩阵•试编写一个函数,确定鞍点在数组中的位置(若鞍点存在时),并分析该函数的时间复杂度
16、己知一个顺序表中的元素按元素值非递减有序罗列,试定义顺序表的存储表示,并编写一个函数.删除表中值相同的多余元素
17、设有两个整数类型的顺序表A(有址个元素)和B(有n个元素),其元素均以从小到大的升序罗列试编写一个函数,将这两个顺序表合并成一个顺序表C要求C的兀素也以从小到大的升序罗列(见题库chi六
(2))
18、试编写一个函数计算工*2的值.其结果存放于数组A[airaySize]的第n个数组元素中,OWnvarriySizeo若设计算机41允许的整数的最大值为imxlnl.则当门aySize或者对于某一个k(0Wkn)使得k*2kniaxlnt时,应按出错姓理一种出错处理方式是在算法实现时用返回粮数函数值01来区别是正常返回还是错误返回试利用这种方式来实现函数
19、试编写一个函数,将一个有n个非零元素的整数一维数组A[n]拆分为两个一维数组,使得A口中大于零的元素存放在B口中,小于零的元素存放在C[]中
20、设定整数数组的数据在行、列方向上都按从小到大的顺序排序,旦整型变量x中的数据在B中存在试设计一个算法,找出一对满足==x的ij值要求比较次数不超过m+iio
21、己知在一维数组知m+n]中挨次存放着两个顺序表ai.az.…a.)和(b]b))o试编写一个函数,将数组中两个顺序表的位置互换即将(也,b2b
(1)放在(aia....»
①)的前面
22、试编写一个函数,以不多于3n/2的平均比较次数.在一个有n个整数的顺序表A中找出具有最大值和最小值的整数(见题库chi六
(2))
23、设入二(ana
2.aJ和日二(bPb
2.成)均为顺序表,和B分别是除去最大公共前缀后的子表如人:(b.e.ijing).B=(beifa.ng则两者的最大公共前缀为bei在两个顺序表中除去最大公共前缀后的子表分别为A=j.i»11g=f.a.ng若A二B;空表,则八二13若A二空表旦B洋空表,或者两者均不空且A的第一个元索值小于8的第一个元素的值,则A〈B否则AB..试编写一个函数•根据上述方法比较A和B的大小。