(题)数据结构复习题.docx

《(题)数据结构复习题.docx》由会员分享，可在线阅读，更多相关《(题)数据结构复习题.docx（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Ch2数组（共23题，其中14道算法设计题）一、填空题1、填空题（每小空1分，共5分）一维数组的逻辑结构是（），存储结构是（）。对于二维数组，有（）和（）两种 不同的存储方式。对于一个二维数组Am n,若采取按行存储的方式，则任一数组元素Aij 相对于A00的地址为（）。Key：税性结构顺序存储表示行优先顺序列优先顺序 n * i + j二、判断题2、判断卜.列叙述的对错。如果正确，在题前的括号内填入“寸，否则填入“X”。（x）线性表的逻辑顺序与物理顺序总是一致的。（x）线性表的顺序存储表示优于链式存储表示。（寸）线性表若采用链式存储表示时所有存储单元的地址可连续可不连续。（x）二维数组是其数

2、组元素为线性表的线性表。（ID每种数据结构都应具备三种基本运算：插入、删除和搜索。三、简答题3,顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下，对有127个元 素的顺序表进行插入，平均需要挪移多少个元素。删除一个元素，又平均甯要挪移多少个元素，Key：插入时平均挪移元素个数AMN二-所以平均挪移63.5个元素删除时平均挪移元素个数AMN二-所以平均挪移63个元素4、设有一个10x10的对称矩阵A10i0.采取按行压缩存储的方式存放于一个一维数组B中，则数组B的容员应有多大？若设A00为第一个元素，存放于B0,旦数组A口的每一个数组元素在数组B口中占一个数组元素位置，则A8

3、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,

4、且k = f (i) +f2 (j) +Co试推导出函数f、f= (j)和常数C,要求f】和G(J)中不包含常数项。Kev：若iWj,数组元素在数组B中的存放位置为u+ 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的.上三角区域中。并给出计算

5、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

6、 (i=0： in： 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： in： i+)sum += anayi:ave = ( float) (suinii):pnntf (the ave of array is %fn ， ave )：)12、设有一个线性表(eo, ei,，en-2 5)存放在一个一维数组Aanay

7、Size+的 前n个数组元素 位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个地址的内容置换为(ez, en- 2.，ei. eo)。(见题库chi六)Key： void inverse (datan,pe A. mtn)(data_type tiup：for (i=0： iinr free =0, i：非零元素存放地址检测整个数组发现非零元素for (1=0； i lemp)return aiTayn-1：elsereturn temp；mrsum anay (array n)m( *anay：intn；(if (111)rerurn array。:elseletuin (an a

8、yu-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、己知一个顺序表中的元素按元素值非

9、递减有序罗列，试定义顺序表的存储表示，并编写一个 函数.删除表中值相同的多余元素。17、设有两个整数类型的顺序表A （有址个元素）和B （有n个元素），其元素均以从小到 大 的升序罗列。试编写一个函数，将这两个顺序表合并成一个顺序表C,要求C的兀素也 以从小到 大的升序罗列。（见题库chi六（2）18、试编写一个函数计算工*2。的值.其结果存放于数组AairaySize的第n个数组元素中， OWnvarriySizeo若设计算机41允许的整数的最大值为imxlnl.则当门aySize或者对于 某一个 k （0Wk niaxlnt时，应按出错姓理。一种出错处理方式是在算法实现时用返回 粮数函数值0, 1来区别是正常返回还是错误返回。试利用这种方式来实现函数。19、试编写一个函数，将一个有n个非零元素的整数一维数组An拆分为两个一维数组，使得A 口中大于零的元素存放在B口中，小于零的元素存放在C中。20、设定整数数组的数据在行、列方向上都按从小到大的顺序排序，旦整型变量x 中的数据在B中存在。试设计一个算法，找出一对满足=x的i, j值。要求 比较次数不超过 m+i io21、己知在一维数组知m+n中挨次存放着两个顺序表B.试编写一个函数根据上述方法比较A和B的大小。