资源描述
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)。 ( )
展开阅读全文