(题)数据结构复习题.docx
Ch2数组（共23题，其中14道算法设计题）一、填空题1、填空题（每小空1分，共5分）一维数组的逻辑结构是（），存储结构是（）。对于二维数组，有（）和（）两种 不同的存储方式。对于一个二维数组Am n,若采取按行存储的方式，则任一数组元素Aij 相对于A00的地址为（）。Key：税性结构顺序存储表示行优先顺序列优先顺序 n * i + j二、判断题2、判断卜.列叙述的对错。如果正确，在题前的括号内填入“寸，否则填入“X”。（x）线性表的逻辑顺序与物理顺序总是一致的。（x）线性表的顺序存储表示优于链式存储表示。（寸）线性表若采用链式存储表示时所有存储单元的地址可连续可不连续。（x）二维数组是其数组元素为线性表的线性表。（ID每种数据结构都应具备三种基本运算：插入、删除和搜索。三、简答题3,顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下，对有127个元 素的顺序表进行插入，平均需要挪移多少个元素。删除一个元素，又平均甯要挪移多少个元素，Key：插入时平均挪移元素个数AMN二-所以平均挪移63.5个元素删除时平均挪移元素个数AMN二-所以平均挪移63个元素4、设有一个10x10的对称矩阵A10i0.采取按行压缩存储的方式存放于一个一维数组B中，则数组B的容员应有多大？若设A00为第一个元素，存放于B0,旦数组A口的每一个数组元素在数组B口中占一个数组元素位置，则A8 5在数组B中的地址是多少？Key： 1)数组B共应有1二55个元素。2)对于上三角矩阵，A8 5=A5 85卜)=43对于下三角矩阵，A815='打=415、设有三对角矩阵Ann,将其三条对角线中的元素逐行存储到一维数组B3n-2中，使 得Bk=Aij« 试求：(1)用1, J表示k的地址转换公式：(2)用k表示1, j的地址转换公式：Key： 1)在一维数组B中在第1行，它前面有3*1-1个非零元素，在本行第j列前 面有 j-i+1个，所以元素Ai j在B中的位置为k=2*i+jo2) 1=(k+1) /3j= k-2*i6、上三角矩阵Ann,将其上三角元素逐行存储到一维数组使得Bk:Ai 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八>» A2 2存放位置在676 g,每一 个元素占一个空间，问A4 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”设带状炬阵Ann是nxn阶的方阵，其中所有的非零元XAXX Q素都在由主对角线及主对角线上下各b条对角线构成的带状|区域内，其它都为零元素。试问：11U)该带状矩阵中有多少个非零元素？& 'J(2)若用一个一维数组B按行顺序存放各行的非零5条对角元素，且设存放在B0中，请给出一个公式，计算任一非零元素"维数组3中的存放位 置。四、算法设计题10.己知整数数组A中有n个兀素，试设计一个算法，求数组中所有兀素值的和。Key： intsuinariay (array* n)hit array, n：(inr i» sum = 0：for (i=0： i<n： i+)Isum += anayi:)pi iiitf ("the sum of array is sum):11、己知整数数组A口中有n个元素，试设计一个算法，求数组中所有元素值的平均值。Key： mr sumanay (array , n)mt cinay» n；inti. sum = 0：float ave：for (i=0： i<n： i+)sum += anayi:ave = ( float) (suinii):pnntf ("the ave of array is %fn" ， ave )：)12、设有一个线性表(eo, ei,，en-2» 5)存放在一个一维数组AanaySize+的 前n个数组元素 位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个地址的内容置换为(ez, en- 2.，ei. eo)。(见题库chi六)Key： void inverse (datan,pe A. mtn)(data_type tiup：for (i=0： i<= (n-1) /2； i+)(tmp =Ai: Ai =An-i-l : Au-i-l =tinp： j)13、假定数组AanaySize中有多个零元素，试写出一个函数，将A中所有的非零元素依 次移到 数组 A 的前端 Ai (0W 1 -anaySize )。Key： void compact (data_type A» mt AiiaySize >inr free =0, i：非零元素存放地址检测整个数组发现非零元素for (1=0； i<AiiaySize； i+) iif (Ai != 0 )(if ( i!=free )(afiee =ai；ai =0； free+： ) !)14、已知An为整数数组.试写出实现卜.列运算的递归算法:(1)求数组A中的最大整数。(2)求n个整数的和。(3)求11个整数的平均值Key： hit max aiTay( aiiay, n)mr *anay：mt n：(int temp；if (n=l)1 eturn anay0：elsejtemp =max_aiiay (may, n-l )：if (arrayn-1 > lemp)return aiTayn-1：elsereturn temp；mrsum anay (array n)m( *anay：intn；(if (111)rerurn array。:elseletuin (an ayu-l +sum_airay( arniy, n-1):)float ave_aiTay( array» n)m( *cinay：hit n：(float temp：if (n1)letuin (float) anay0；elseletuin (float) ( aiiayn-l + aveariay( array n-l) *( n-1) /n；)15、若矩阵中的某一元一元j是第i行中的最小值,同时又是第j列中的最大值,则称此元素为该矩阵的一个单戈点。假设以二维数组存放矩阵试编写一个函数，确定鞍点在数组中的位置（若鞍点存在时），并分析该函数的时间复杂度。16、己知一个顺序表中的元素按元素值非递减有序罗列，试定义顺序表的存储表示，并编写一个 函数.删除表中值相同的多余元素。17、设有两个整数类型的顺序表A （有址个元素）和B （有n个元素），其元素均以从小到 大 的升序罗列。试编写一个函数，将这两个顺序表合并成一个顺序表C,要求C的兀素也 以从小到 大的升序罗列。（见题库chi六（2）18、试编写一个函数计算工*2。的值.其结果存放于数组AairaySize的第n个数组元素中， OWnvarr<iySizeo若设计算机41允许的整数的最大值为imxlnl.则当门'aySize或者对于 某一个 k （0Wk<n）,使得k'*2k > niaxlnt时，应按出错姓理。一种出错处理方式是在算法实现时用返回 粮数函数值0, 1来区别是正常返回还是错误返回。试利用这种方式来实现函数。19、试编写一个函数，将一个有n个非零元素的整数一维数组An拆分为两个一维数组，使得A 口中大于零的元素存放在B口中，小于零的元素存放在C中。20、设定整数数组的数据在行、列方向上都按从小到大的顺序排序，旦整型变量x 中的数据在B中存在。试设计一个算法，找出一对满足=x的i, j值。要求 比较次数不超过 m+i io21、己知在一维数组知m+n中挨次存放着两个顺序表<ai. az.,a.）和（b , b?）&）o试编写一个函数，将数组中两个顺序表的位置互换即将（也，b2, b（1）放在（ai, a?. .» ）的前面。22、试编写一个函数，以不多于3n/2的平均比较次数.在一个有n个整数的顺序表A中找出具有 最大值和最小值的整数。（见题库chi六（2）23、设入二（an a2. aJ和日二（bP b2.成）均为顺序表，&和B,分 别是除去最大公共前缀后的 子表。如人:（b. e. i, j, i, n, g ） . B= （ b, e,i, f, a. n, g ),则两者的最大公共前缀为b, e, i,在两个顺序表中除去最大公共前缀后的子表 分别为 A, = ( j. i» 11, g ),= ( f. a. n, g )。若 A' 二 B ;空表，则八二13：若A,二空表旦B洋 空表，或者两者均不空且A的第一个元索值小于8的第一个元 素的值，则AB：否则A>B.试编写一个函数根据上述方法比较A和B的大小。
