1、全国自考数据结构导论（数组、矩阵和广义表）模拟试卷 1 及答案与解析一、单项选择题1 常对数组进行的两种基本操作是_。（A）建立与删除（B）索引与修改（C）查找与修改（D）查找2 设有一个 8 阶的对称矩阵 A，采用压缩存储方式，以行序为主序存储，每个元素占用一个存储单元，基址为 100，则 A63 的地址为 _。（A）118（B） 124（C） 151（D）1603 已知数组 A16，28在内存中以行序为主序存放，且每个元素占两个存储单元，则计算元素 Ai，j 地址的公式为 _。（A）LOC(Ai ，j)=LOC(A1，2)+(i 一 1)*7+(j 一 2)*2（B） LOC(Ai，j)=
2、LOC(A1，2)+(j 一 2)*6+(i 一 1)*2（C） LOC(Ai，j)=LOC(A1，2)+(i*8+j)*2（D）LOC(Ai ，j)=LOC(A1，2)+(j*6+i)*24 二维数组 A 的每个元素是由 6 个字符组成的串，其行下标 i=0，1，8，列下标 j=1， 2， ，10，且每个字符占一个字节。若 A 以行序为主序存放，元素A8，5的起始地址与当 A 以列序为主序存放时的元素_的起始地址相同。（A）A7 ，8（B） A6，5（C） A0，7（D）A3 ，105 对稀疏矩阵进行压缩存储的目的是_。（A）降低运算的时间复杂度（B）节省存储空间（C）便于存储（D）便于进行
3、矩阵运算6 以下有关广义表说法中不正确的是_。（A）广义表的表头总是一个原子（B）广义表的表尾总是一个广义表（C）广义表的元素可以是单个元素（D）广义表的元素可以是一个子表7 广义表 L=(a，(b，(c)， d)，()，e)的长度为_。（A）（B） 6（C） 4（D）38 广义表 L=(a)，则表尾为_。（A）a（B） ()（C）空表（D）(a)9 已知广义表 L=(a，b，c)，a ，(x，y，z) ，从 L 表中取出原子项 y 的运算是_。（A）head(tail(head(tail(L)（B） tail(head(head(tail(L)（C） head(tail(head(tail(
4、tail(L)（D）head(tail(tail(L)10 下列广义表是线性表的有_。（A）L=(a，(b，c)（B） L=(a， L)（C） L=(a， b)（D）L=(a，()二、填空题11 通常数组只有_和_两种运算，因此常采用_来存储数组。12 数组 A 中每个元素的长度是 3 个字节，行下标 i 从 1 到 8，列下标 j 从 1 到10，首地址 sT 开始连续存放在存储器中。若按行优先方式存储，元素 A85的起始地址为_；若按列先方式存储，元素 A85的起始地址为_。13 二维数组 M 的成员是 6 个字符(每个字符占一个存储单元 )组成的串，行下标 i的范围从 0 到 8，列下标
5、 j 的范围从 1 到 10，则存放 M 至少需要_个字节；M 的第 8 列和第 5 行共占_个字节；若 M 按行优先方式存储，元素 M85的起始地址与当 M 按列优先方式存储时的_元素的起始地址一致。14 下三角矩阵压缩存储的下标对应关系为_。15 已知数组 A38，26以列序为主序顺序存储，且每个元素占两个存储单元，则计算元素 Ai，j 地址的公式为 _。16 设有二维数组 int M1020，每个元素( 整数)占 2 个存储单元，数组的起始地址为 2000，元素 M510的存储位置为 _，M819的存储位置为_。17 所谓稀疏矩阵指的是_。18 稀疏矩阵 A= 的三元组表示为_ 。19
6、一个 54 矩阵可以看成是长度为 5 的线性表，表中每个元素是长度为_的线性表。20 广义表(a，(a)，d，e，(i，j) ，k)的长度是_，深度是_。21 已知广义表 A=()，(a ，(b)，c)，则 laead(tail(head(tail(head(A)等于_。22 当广义表中的每个元素都是原子时，广义表便成了_。23 广义表的表尾是指除第一个元素之外，_。三、应用题24 已知 56 数组 A 的每个元素占 2 个字节，数组的基址为 1000，求： (1)A 所占的字节数； (2)元素 a25 的地址； (3)按行和按列优先存储的 a34 地址。25 设有上三角矩阵(a ij)nn，
7、将其上三角元素逐行存于数组 B(1：m)中(m 充分大)，使得 Bk=aij，且 k=fi(i)+f2(j)+c。试推导出函数 f1，f 2 和常数 c(要求 f1 和 f2 中不含常数项)。25 设有三对角矩阵(a ij)nn，将其三条对角线上的元素逐行存于数组 B(1：3n 一 2)中，使得 Bk=aij，求：26 用 i，j 表示 k 的下标变换公式；27 用 k 表 i、j 的下标变换公式。28 已知稀疏矩阵 请给出矩阵 A 的三元组表示。29 已知某稀疏矩阵 A 的十字链表表示如下，请给出该矩阵。30 已知广义表 L=()，()，求 head(L)，tail(L) ，L 的长度，深度
8、各为多少?31 求下列广义表运算的结果：(1)head(i，i，k)； (2)tail(k，m，n)； (3)head(tail(a，b，c) ，(d) ；32 画出以下广义表的存储结构图示：(a)，b)， ()，d)，(e，f)33 已知广义表 L=(x，y，z)，a，(u ，t，w)，求：从 L 表中取出原子项 t 的运算。34 约瑟夫环问题：设有 n 个人围坐一圈，并按顺时针方向 1n 编号。从第 s 个人开始进行报数，报数到第 m 个人，此人出圈，再从他的下一个人重新开始从 1 到m 的报数进行下去，直到所有的人都出圈为止。void Josef(int A，int n，int s，in
9、t m)for(i=1;i=2;i 一一) s1=_; *计算出圈人 s1*if(s1=0)_；W=As1; *As1出圈*for(j=_)Aj=Aj+1；Ai=w；print f(“出圈序列为： ”)； *输出出圈序列*for(i=n；i=1；i 一一)print f(“d”，Ai)；print f(“n”)；35 编写算法：将稀疏矩阵转换为三元组的表示形式。36 编写算法，将自然数 1n 2 按“蛇形” 填入，nn 矩阵中。例(1 42)如下图所示。37 设 A1100是一个记录构成的数组， B1100)是一个整数数组，其值介于 1至 100 之间，现要求按 B1100的内容调整 A 中记
10、录的次序，比如当 B1=11 时，则要求将 A1的内容调整到 A11中去。规定可使用的附加空间为 O(1)。38 已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序(非降序) 并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意：不能另开辟数组，也不能对任意一个数组进行排序操作。例如：第一个数组为：4，12，28第二个数组为：1，7，9，29，45输出结果为：1，4，7(第一个数组)9，12，28，29，45(第二个数组)39 给定有 m 个整数的递增有序数组 a1m和有 n 个整数的递减有序数组
11、b1n，试写出算法：将数组 a 和 b 归并为递增有序数组 c1m+n。(要求：算法的时间复杂度为 O(m+n)。全国自考数据结构导论（数组、矩阵和广义表）模拟试卷 1 答案与解析一、单项选择题1 【正确答案】 C【试题解析】 对数组来讲，一旦建立起来后，数组中的元素个数是不能改变的，所以不能对数组施加插入、删除这些操作。而且通常是按行或列对数组进行顺序存储的，故也无需要对其建立索引。因此数组上最常见的操作是查找与修改。【知识模块】 数组、矩阵和广义表2 【正确答案】 B【知识模块】 数组、矩阵和广义表3 【正确答案】 A【知识模块】 数组、矩阵和广义表4 【正确答案】 D【知识模块】 数组、
12、矩阵和广义表5 【正确答案】 B【知识模块】 数组、矩阵和广义表6 【正确答案】 A【知识模块】 数组、矩阵和广义表7 【正确答案】 D【知识模块】 数组、矩阵和广义表8 【正确答案】 C【知识模块】 数组、矩阵和广义表9 【正确答案】 C【知识模块】 数组、矩阵和广义表10 【正确答案】 C【知识模块】 数组、矩阵和广义表二、填空题11 【正确答案】 读 写 顺序存储结构【知识模块】 数组、矩阵和广义表12 【正确答案】 ST+222 ST+117【试题解析】 按行优先方式存储时，A85的前面已经存放了 74(7*10+4=74)个元素，它们共占用了 74*3=222 个字节，所以 A85的
13、起始地址为 sT+222。按列优先方式存储时，A85的前面已经存放了 39(4*8+7=39)个元素，它们共占用了39*3=117 个字节，所以 A85的起始地址为 ST+117。【知识模块】 数组、矩阵和广义表13 【正确答案】 540 108 M310【试题解析】 按题意二维数组 M 共有 9 行(行号 08)，每行有 10 列(列号110) ，合计有 90 个元素，每个元素占 6 个字节，所以存放 M 至少需要906=540 个字节。 M 的第 8 列上若有 9 个元素，第 5 行上共有 10 个元素，合计有 19 个元素，但是其中有两个元素是重复的(M58)，故实际有 18 个元素，共
14、需占用 186=108 个字节。 元素 M85在数组中位于第 9 行的第 5 列，当按行优先方式存储时，在其前面已经存储了 810+4=84 个元素，因此 M85是顺序存储的第 85 个元素。而当按列优先方式存储时，第 85 个元素应该是位于第 10 列的第 3 行上(前 9 列共有 81 个元素，第 10 列有 4 个元素)，即元素 M310。【知识模块】 数组、矩阵和广义表14 【正确答案】 【知识模块】 数组、矩阵和广义表15 【正确答案】 LOC(Ai，j)=LOC(A3，2)+(j 一 2)*6+(i 一 3)*2【知识模块】 数组、矩阵和广义表16 【正确答案】 2198 2316
15、(设按行优先存储)【知识模块】 数组、矩阵和广义表17 【正确答案】 非零元很少(t=0) aij=k+；i+；j 一一；if(j=0)Aj+1=x；【试题解析】 由于两个数组定长，设其长度分别为 m 和 n，又知两个数组中的元素都非递减有序，重新排列元素后，第二个数组中所有元素都大于第一个数组中的所有元素。因此取第一个数组中的最后一个元素与第二个数组中的第一个元素进行比较，若第一个数组中的最后一个元素比第二个数组中的第一个元素小，则操作完毕，否则将第一个数组中的最后一个元素移到第二个数组的合适位置，将第二个数组中的第一个元素移到第一个数组的合适位置，重复上述过程，直到第二个数组中的第一个元素
16、大于第一个数组中的最后一个元素为止。算法描述如下。【知识模块】 数组、矩阵和广义表39 【正确答案】 void Merge(int A，int B，int&C，int m，int n) 将两个递增和递减的数组 A 和 B，合并成一个递增有序的数组 ci=0； j=n1；k=0；while(i=0)if(Ai=0ck+=Bj-；【试题解析】 由于两个数组都有序，但合并得到的新数组 C 的递增有序，则设两个变量 i 和 j，分别指向数组 A 的第一个元素和数组 B 的最后一个元素，将 Ai和Bj中的小者插入到数组 C 中，重复上述操作，直到将两个数组中的元素全部合并到数组 C 为止。算法描述如下。【知识模块】 数组、矩阵和广义表
