资源描述
1、 特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么?答:后者在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中,非零元素的分布是没有规律的,为了压缩存储,就将每一个非零元素的值和它所在的行、列号作为一个结点存放在一起,这样的结点组成的线性表中叫三元组表,它已不是简单的向量,所以无法用下标直接存取矩阵中的元素。2、二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M35的起始地址与M按列存储时元素( )的起始地址相同。 A、M24B、M34C、M35D、M443、设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为( )。A. 13 B. 33 C. 18 D. 404、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中,则在B中确定aij(ij)的位置k的关系为( )。A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i5、设A是n*n的对称矩阵,将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B1.n(n+1)/2中,对上述任一元素aij(1i,jn,且ij)在B中的位置为( )。A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-16、设二维数组A1. m,1. n(即m行n列)按行存储在数组B1. m*n中,则二维数组元素Ai,j在一维数组B中的下标为( )。A.(i-1)*n+j B.(i-1)*n+j-1 C. i*(j-1) D. j*m+i-17、有一个100*90的稀疏矩阵,非0元素有10个,设每个整型数占2字节,则用三元组表示该矩阵时,所需的字节数是( )。A. 60 B. 66 C. 18000 D. 33 8、已知广义表L=(x,y,z),a,(u,t,w),从L表中取出原子项t的运算是( )。A.head(tail(tail(L) B.tail(head(head(tail(L) C.head(tail(head(tail(L) D.head(tail(head(tail(tail(L)))9、下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构10、若采用按行优先顺序存储,试写出三维数组A323所有元素在内存中的存储次序。答:A000,A001,A002,A010,A011,A012,A100,A101,A102,A110,A111,A112,A200,A201,A202,A210,A211,A212 11、二维数组Amn采用按行存储,每个元素占k个存储单元,第一个元素的存储地址是LOC(A00),则Aij的存储地址是 。答:LOC(A00)+(n*i+j)*k12、三维数组a456(下标从0开始计,a有4*5*6个元素),每个元素的长度是2,则a234的地址是_。(设a000的地址是1000,数据以行为主方式存储) 答:1164 公式:LOC(aijk)=LOC(a000)+v2*v3*(i-c1)+v3*(j-c2)+(k-c3)*l (l为每个元素所占单元数)13、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中,则非零元素A9,9在B中的存储位置k=_。 ( 注:矩阵元素下标从1开始 )答:9314、设广义表L=(),(), 则head(L)是(1)_;tail(L)是(2)_;L的长度是(3)_;深度是 (4)_。答:(1)() (2)() (3)2 (4)215、广义表A=(a,b),(c,d,e),取出A中的原子e的操作是: _。答:head(tail(tail(head(tail(head(A)16、设对称矩阵A=(1)若将A中包括主对角线的下三角元素按列的顺序压缩到数组S中, 即S:1002300050下标: 1 2 3 4 5 6 7 8 9 10试求出A中任一元素的行列下标i,j(1=i,j=4)与S中元素的下标K之间的关系.(2)若将A视为稀疏矩阵时,画出其三元组表形式压缩存储表。答:(1)k=(2n-j+2)(j-1)/2+i-j+1 (当ij时,本题n=4)k=(2n-i+2)(i-1)/2+j-i+1 (当ij时,本题n=4) (2)稀疏矩阵的三元组表为:s=(4,4,6),(1,1,1),(1,4,2),(2,2,3),(3,4,5),(4,1,2),(4,3,5)。其中第一个三元组是稀疏矩阵行数、列数和非零元素个数。其它三元组均为非零元素行值、列值和元素值。17、设任意n个整数存放于数组A(1:n)中,试编写程序,将所有正数排在所有负数前面(要求算法复杂性为0( n))。 类似本题的另外叙述有:(1)已知数组A1.n的元素类型为整型,设计算法调整A,使其左边的所有元素小于零,右边的所有元素大于等于零。(要求算法的时间复杂度和空间复杂度均为0(n)(2)设计一个算法,把整数数组中所有的偶数放到所有的奇数之前。要求时间、空间效率尽可能高。(3)设一系列正整数存放在一个数组中,试设计算法,将所有奇数存放在数组的前半部分,将所有的偶数存放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。请试着分析你实现的算法的时间复杂度和空间复杂度。(4)设计算法将数组A1.n调整为左右两部分,使的左边所有的元素小于右边的所有元素,并给出这一划分的分界位置。要求算法的时间复度为O(n)。 答:题目分析本题属于排序问题,只是排出正负,不排出大小。可在数组首尾设两个指针i和j,i自小至大搜索到负数停止,j自大至小搜索到正数停止。然后i和j所指数据交换,继续以上过程,直到 i=j为止。void Arrange(int A,int n) /n个整数存于数组A中,本算法将数组中所有正数排在所有负数的前面 int i=0,j=n-1,x; /用类C编写,数组下标从0开始 while(ij)while(i0) i+;while(ij & Aj0) j-; if(i0)改为判偶数(Ai%2=0),将判负数(Aj0)改为(Aj%2!=0)。(3)同(2),只是要求奇数排在偶数之前。(4)利用快速排序思想,进行一趟划分。int Partition(int A,int n) /将n个元素的数组A调整为左右两部分,且左边所有元素小于右边所有元素,返回分界位置。int i=0,j=n-1,rp=A0; /设数组元素为整型 while(ij) while(i=rp) j-; while(ij &Ai=rp) i+; if(ij) x=Ai;Ai=Aj; Aj=x; Ai=rp; return(i); /分界元素/ Partition18、在数组 A1.n中有n个数据,试建立一个带有头结点的循环链表,头指针为h,要求链中数据从小到大排列,重复的数据在链中只保存一个。答:题目分析本题要求建立有序的循环链表。从头到尾扫描数组A,取出Ai(0=inext=h; /形成空循环链表for(i=0;inext; while(p!=h & p-datanext; /查找Ai的插入位置 if(p=h | p-data!=Ai) /重复数据不再输入 s=(LinkedList) malloc(sizeof(LNode); s-data=Ai; pre-next=s; s-next=p;/将结点s链入链表中/for return(h);/ creat19、编写程序,统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A-Z这26个字母和0-9这10个数字)。问题分析由于字母共26个,加上数字符号10个共36个,所以设一长36的整型数组,前10个分量存放数字字符出现的次数,余下存放字母出现的次数。从字符串中读出数字字符时,字符的ASCII代码值减去数字字符0的ASCII代码值,得出其数值(0.9),字母的ASCII代码值减去字符A的ASCII代码值加上10,存入其数组的对应下标分量中。遇其它符号不作处理,直至输入字符串结束。void Count()/统计输入字符串中数字字符和字母字符的个数int i,num36;char ch;for(i0;i36;i+)numi0;/ 初始化while(chgetchar()!=#) /#表示输入字符串结束if(0=ch=9)i=ch48;numi+; / 数字字符 elseif(A=ch=Z)i=ch-65+10;numi+;/ 字母字符for(i=0;i10;i+) / 输出数字字符的个数printf(“数字d的个数dn”,i,numi);for(i10;i36;i+)/ 求出字母字符的个数printf(“字母字符c的个数dn”,i55,numi);/算法结束7. 假设有二维数组A68,每个元素用相邻的6个字节存储,存储器按字节编址。已知A的起始存储位置(基地址)为1000,则数组A的体积(存储量)为 288 B ;末尾元素A57的第一个字节地址为 1282 ;若按行存储时,元素A14的第一个字节地址为 (8+4)6+1000=1192 ;若按列存储时,元素A47的第一个字节地址为 (674)61000)1276 。9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分别表示该元素的 行下标 、 列下标 和 元素值 。10.求下列广义表操作的结果:(1) GetHead【(a,b),(c,d)】= (a, b) ; /头元素不必加括号(2) GetHead【GetTail【(a,b),(c,d)】= (c,d) ;(3) GetHead【GetTail【GetHead【(a,b),(c,d)】= b ;(4) GetTail【GetHead【GetTail【(a,b),(c,d)】= (d) ;(A)4.01年计算机系考研题假设有60行70列的二维数组a160, 170以列序为主序顺序存储,其基地址为10000,每个元素占2个存储单元,那么第32行第58列的元素a32,58的存储地址为 。(无第0行第0列元素)16902 16904 14454 答案A, B, C均不对答:(57列60行31行)2字节10000=16902(B)5.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分(如下图所示)按行序存放在一维数组B 1, n(n-1)/2 中,对下三角部分中任一元素ai,j(ij), 在一维数组B中下标k的值是:i(i-1)/2+j-1 i(i-1)/2+j i(i+1)/2+j-1 i(i+1)/2+j解:注意B的下标要求从1开始。先用第一个元素去套用,可能有B和C;再用第二个元素去套用B和C,B=2而C3(不符);所以选B6.【91初程P78】 从供选择的答案中,选出应填入下面叙述 ? 内的最确切的解答,把相应编号写在答卷的对应栏内。有一个二维数组A,行下标的范围是0到8,列下标的范围是1到5,每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A0,1的第一个字节的地址是0。存储数组A的最后一个元素的第一个字节的地址是 A 。若按行存储,则A3,5和A5,3的第一个字节的地址分别是 B 和 C 。若按列存储,则A7,1和A2,4的第一个字节的地址分别是 D 和 E 。供选择的答案AE:28 44 76 92 108 116 132 176 184 188答案:ABCDE=8, 3, 5, 1, 67.【94程P12】 从供选择的答案中,选出应填入下面叙述 ? 内的最确切的解答,把相应编号写在答卷的对应栏内。有一个二维数组A,行下标的范围是1到6,列下标的范围是0到7,每个数组元素用相邻的6个字节存储,存储器按字节编址。那么,这个数组的体积是 A 个字节。假设存储数组元素A1,0的第一个字节的地址是0,则存储数组A的最后一个元素的第一个字节的地址是 B 。若按行存储,则A2,4的第一个字节的地址是 C 。若按列存储,则A5,7的第一个字节的地址是 D 。供选择的答案AD:12 66 72 96 114 120 156 234 276 282 (11)283 (12)288答案:ABCD=12, 10, 3, 92.已知二维数组Am,m采用按行优先顺序存放,每个元素占K个存储单元,并且第一个元素的存储地址为Loc(a11),请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢?解:公式教材已给出,此处虽是方阵,但行列公式仍不相同;按行存储的元素地址公式是: Loc(aij)= Loc(a11) + (i-1)*m+(j-1) * K按列存储的元素地址公式是: Loc(aij)= Loc(a11) + (j-1)*m+(i-1) * K3.【全国专升本资格考试】递归算法比非递归算法花费更多的时间,对吗?为什么?答:不一定。时间复杂度与样本个数n有关,是指最深层的执行语句耗费时间,而递归算法与非递归算法在最深层的语句执行上是没有区别的,循环的次数也没有太大差异。仅仅是确定循环是否继续的方式不同,递归用栈隐含循环次数,非递归用循环变量来显示循环次数而已。4.用三元组表表示下列稀疏矩阵: 解:三元素组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分别表示该元素的 行下标 、 列下标 和 元素值 。所以(1)可列表为: (2)可列表为:8866416-225943565353233685467858125.下列各三元组表分别表示一个稀疏矩阵,试写出它们的稀疏矩阵。 解:(1)为64矩阵,非零元素有6个,但其中一数下标有误?(2)为45矩阵,非零元素有5个1 0 0 0 00 0 0 9 00 8 0 0 60 0 7 0 00 2 0 0 12 0 0 0 改为2,1,123 0 0 0 0 0 0 4 0 0 6 0 16 0 0 0 1.二维数组在内存中存储可以有两种存储方式,一种是_行_优先存储,一种是 列 优先存储。2.设广义表L((),(),())。则head(L)是() ;tail(L)是((),()) ;L的长度是3 ;L的深度是 3 。3.设广义表L((a),(b),(c)) 则head(L)是_(a)_;tail(L)是_((b),(c))_。1.在C语言中,如果有数组定义int A89;假定每个整型数据占2字节,则数组元素A44的地址是( A )。A. A+80 B. A+76 C.A+82 D.以上都不对2.广义表A=(a,b,(c,d),(e,(f,g)),则下面式子的值为(D ); Head(Tail(Head(Tail(Tail(A)A(g) B.(d) C.c D.d1.在C语言中,多维数组的存储采取的是行优先的方式。( )2.广义表在本质上也是线性表。( )3.可以用三元组存储法来压缩存储稀疏矩阵。( )4.已知广义表A=(a,b,c),(d,e,f),从A中取出原子e的运算是head(tail(head(tail(A)。 ( )
展开阅读全文