计算机专业基础综合数据结构(数组和广义表)历年真题试卷汇编5

1、以行序优先顺序存储数组A[5][5]；假定A[0][0]的地址为1000, 每个元素占4个字节，下标变量A[4][3]的地址是____。

A.1069B.1092C.1023D.1046正确答案：B2、数组a[1．．6][1．．5] （无0行0列）以列序优先顺序存储，第一个元素a[1][1]的地址为1000，每个元素占2个存储单元，则a[3][4]的地址是____。

A.1040B.1026C.1046D.1038正确答案：A3、设有一个5行4列的矩阵A，采用行序优先存储方式，A[0][0]为第一个元素，其存储地址为1000，A[2][2]的地址为1040，则A[3][0]的地址为_________。

A.1048B.1024C.1096D.1060正确答案：A4、设有一个10行10列的矩阵A，采用行序优先存储方式，存储全部数据需要400个字节的空间。

如果A[0][0]为第一个元素，其存储地址为1000，则A[3][6]的地址为_________。

A.1036B.1144C.1014D.10565、设有一个10行10列的矩阵A，采用行序优先存储方式。

如果A[0][0]为第一个元素，其存储地址为1000，A[2][3]的存储地址为1069，则存储一个元素需要的单元数是_________。

A.4B.1C.2D.3正确答案：D6、不能够对数据元素进行随机访问的物理结构是_________。

A.三元组顺序表B.对称矩阵的压缩存储C.三对角矩阵的压缩存储D.数组的顺序存储正确答案：A7、对特殊矩阵采用压缩存储的目的主要是_________。

A.表达变得简单B.去掉矩阵中的多余元素C.对矩阵元素的存储变得简单D.减少不必要的存储空间正确答案：D8、对n*n的对称矩阵进行压缩存储，需要保存的数据元素的个数是_________。

A.nB.n(n+1)/2C.n2D.n(n+1)9、设10*10的对称矩阵下三角保存SA[1．．55]中，其中A[1][1]保存在SA[1]中，A[5][3] 保存在SA[k]中，这里k等于_________。

开放大学数据结构(本科)单元5数组和广义表单元测试题含答案试题1一维数组A采用顺序存储结构，每个元素占用4个字节，第8个元素的存储地址为120，则该数组的首地址是（）。

选择一项：A.88B.92C.32D.90反馈正确答案是：92试题2稀疏矩阵采用压缩存储的目的主要是（）。

选择一项：A.对矩阵元素的存取变得简单B.表达变得简单C.去掉矩阵中的多余元素D.减少不必要的存储空间的开销反馈正确答案是：减少不必要的存储空间的开销试题3一个非空广义表的表头（）。

选择一项：A.只能是子表B.可以是子表或原子C.不可能是原子D.只能是原子反馈正确答案是：可以是子表或原子试题4常对数组进行的两种基本操作是（）。

选择一项：A.索引与、和修改B.查找与索引C.查找和修改D.建立与删除反馈正确答案是：查找和修改试题5在二维数组A[8][10]中，每一个数组元素A[i][j] 占用3个存储空间，所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储空间是（）。

选择一项：A.80B.270C.240D.100反馈正确答案是：240试题6设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A10,8在一维数组B 中的下标是（）。

选择一项：A.18B.53C.45D.58反馈正确答案是：53试题7广义表((a))的表尾是（）。

选择一项：A.((a))B.(a)C.0D.a反馈正确答案是：0试题8设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A8,5在一维数组B中的下标是（）。

选择一项：A.32B.85C.41D.33反馈正确答案是：33试题9设广义表类（(a,b,c)），则L的长度和深度分别为（）。

选择一项：A.2和3B.1和2C.1和1D.1和3反馈正确答案是：1和2试题10广义表( a , a ,b , d , e ,( (i ,j ) ,k ) )的表头是________。

计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编4(总分：60.00，做题时间：90分钟)一、综合题(总题数：13，分数：26.00)1.简述广义表属于线性结构的理由。

【西北大学2000一、5(3分)】（分数：2.00）__________________________________________________________________________________________ 2.数组、广义表与线性表之间有什么样的关系?【西北工业大学1998一、2(4分)】（分数：2.00）__________________________________________________________________________________________ 3.什么是广义表?请简述广义表和线性表的主要区别。

【北京大学1997二、2(5分)】（分数：2.00）__________________________________________________________________________________________4.求下列广义表的运算结果。

【南京航空航天大学1998三(10分)】(1)CAR(CDR(((a，b)，(c，d，(e，f)))(2)CDR(CAR(((a，6b)，(c，d，(e，f)))(3)CAR(CDR[(CAR(((a，b)，(e，f))))(4)CDR(CAR(CDR(((a，b)，(e，f))))(5)CDR(CDR(CAR(((a，b)，(e，f))))注：CAR运算相当于有些教材中的Head运算，CDR运算相当于Tail运算。

（分数：2.00）__________________________________________________________________________________________ 5.画出下列广义表的存储结构图，并利用取表头和取表尾的操作分离出原子e。

第五章数组和广义表答案部分答案解释如下。

1. 错误。

对于完全二叉树，用一维数组作存储结构是效率高的（存储密度大）。

4. 错误。

数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。

因此，可以说数祖是元素值和下标构成的偶对的有穷集合。

5. 错误。

数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。

6. 错误。

稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。

8. 错误。

广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。

9. 错误。

广义表的表头就是广义表的第一个元素。

只有非空广义表才能取表头。

10. 错误。

广义表中元素可以是原子，也可以是表（包括空表和非空表）。

11. 错误。

广义表的表尾，指去掉表头元素后，剩余元素所组成的表。

三、填空题1. 顺序存储结构2.（1）9572（2）12283.（1）9174（2）87884. 11005. 1164 公式：LOC(a ijk)=LOC(a000)+[v2*v3*(i-c1)+v3*(j-c2)+(k-c3)]*l (l为每个元素所占单元数)6. 2327. 13408. 11969. 第1行第3列10. (1)270 (2)27 (3)2204 11. i(i-1)/2+j (1<=i,j<=n)12. (1)n(n+1)/2 (2)i(i+1)/2 (或j(j+1)/2) (3)i(i-1)/2+j (4)j(j-1)/2+i (1<=i,j<=n)13. 1038 三对角矩阵按行存储：k=2(i-1)+j (1<=i,j<=n)14. 33 (k=i(i-1)/2+j) (1<=i,j<=n)15. 非零元很少(t<<m*n)且分布没有规律 16. 节省存储空间。

17. 上三角矩阵中，主对角线上第r(1≤r≤n) 行有n-r+1个元素，a ij所在行的元素数是j-i+1。

数据结构考试试题库含答案解析数据结构习题集含答案⽬录⽬录 (1)选择题 (2)第⼀章绪论 (2)第⼆章线性表 (4)第三章栈和队列 (6)第四章串 (7)第五章数组和⼴义表 (8)第六章树和⼆叉树 (8)第七章图 (11)第⼋章查找 (13)第九章排序 (14)简答题 (19)第⼀章绪论 (19)第⼆章线性表 (24)第三章栈和队列 (26)第四章串 (28)第五章数组和⼴义表 (29)第六章树和⼆叉树 (31)第七章图 (36)第⼋章查找 (38)第九章排序 (39)编程题 (41)第⼀章绪论 (41)第⼆章线性表 (41)第三章栈和队列 (52)第四章串 (52)第五章数组和⼴义表 (52)第六章树和⼆叉树 (52)第七章图 (52)第⼋章查找 (52)第⼀章绪论1.数据结构这门学科是针对什么问题⽽产⽣的？（A ）A、针对⾮数值计算的程序设计问题B、针对数值计算的程序设计问题C、数值计算与⾮数值计算的问题都针对D、两者都不针对2.数据结构这门学科的研究内容下⾯选项最准确的是（D ）A、研究数据对象和数据之间的关系B、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3.某班级的学⽣成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下⾯关于数据对象、数据元素、数据项描述正确的是（C ）A、某班级的学⽣成绩表是数据元素，90分是数据项B、某班级的学⽣成绩表是数据对象，90分是数据元素C、某班级的学⽣成绩表是数据对象，90分是数据项D、某班级的学⽣成绩表是数据元素，90分是数据元素4.*数据结构是指（A ）。

A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5.数据在计算机存储器内表⽰时，物理地址与逻辑地址不相同，称之为（C ）。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6.算法分析的⽬的是（C ）A、找出数据的合理性B、研究算法中的输⼊和输出关系C、分析算法效率以求改进D、分析算法的易懂性和⽂档型性7.算法分析的主要⽅法（A ）。

计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编3(总分：66.00，做题时间：90分钟)一、综合题(总题数：20，分数：48.00)1.数组A[1．．8，一2．．6，0．．6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A[4，2，3]的存储首地址。

【厦门大学1998五、1(5分)】__________________________________________________________________________________________ 正确答案：(正确答案：元素A[4，2，3]的存储首地址为958。

三维数组以行为主序存储，其元素地址公式为：LOC(A ijk )=LOC(A c1c2c3 )=(3A c1c2c3 )+[(i-c 1 )V 2 V 3 +(j—c 2 )V 3 +(k-c 3 )]*L其中，c i，d i 是各维的下界和上界，V i =d i一c i +1是各维元素个数，L是一个元素所占的存储单元数。

)2.数组A中，每个元素A[i，f]的长度均为32个二进位，行下标从一1到9，列下标从1到11，从首地址S开始连续存放在主存储器中，主存储器字长为16位。

求：(1)存放该数组所需多少单元?(2)存放数组第4列所有元素至少需多少单元?(3)数组按行存放时，元素A[7，4]的起始地址是多少?(4)数组按列存放时，元素A[4，7]的起始地址是多少?【大连海事大学1996四、1(6分)】__________________________________________________________________________________________ 正确答案：(正确答案：每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。

(1)242 (2)22 (3)S+182 (4)S+142)3.假设按低下标优先存储整型数组A(一3：8，3：5，一4：0，0：7)时，第一个元素的字节存储地址是100，每个整数占4字节，问A(0，4，一2，5)的存储地址是什么? 【清华大学1996三】__________________________________________________________________________________________ 正确答案：(正确答案：1784 (公式：Loc(A ijkl )=100(基地址)+[(i-c 1 )v 2 v 3 v 4 +一c 2 )v 3 v 4 +(k-c3 )v4 +(l一c 4 )]*4))4.设有五对角矩阵A=(a ij ) 20*20，按特殊矩阵压缩存储的方式将其五条对角线上的元素存于数组A[-10：m]中，计算元素A[15，16]的存储位置。

习题五数组和广义表一、单项选择题1．常对数组进行的两种基本操作是（）A.建立与删除B. 索引与修改C. 查找与修改D. 查找与索引2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定.A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*kB.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*kC.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*kD.Loc[i,j]=[(n+1)*i+j]*k3．稀疏矩阵的压缩存储方法是只存储 ( )A.非零元素B. 三元祖（i,j, aij）C. aijD. i,j4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

A. 1175B. 1180C. 1205D. 12105. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。

A. i（i-1）/2+jB. j（j-1）/2+iC. i（j-i）/2+1D. j（i-1）/2+16. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。

A. j=r[j].nextB. j=j+1C. j=j->nextD. j=r[j]-> next7. 对稀疏矩阵进行压缩存储目的是（）。

A．便于进行矩阵运算 B．便于输入和输出C．节省存储空间 D．降低运算的时间复杂度8. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。

A. head(tail(LS))B. tail(head(LS))C. head(tail(head(tail(LS)))D. head(tail(tail(head(LS))))9. 广义表（（a,b,c,d））的表头是（），表尾是（）。

计算机专业基础综合数据结构（排序）历年真题试卷汇编5(总分：66.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.已知关键字序列5，8，12，19，28，20，15，22是小根堆(最小堆)，插入关键字3，调整后得到的小根堆是( )。

【2009年全国试题9(2分)】A.3，5，12，8，28，20，15，22，19 √B.3，5，12，19，20，1 5，22，8，28C.3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，1 5，22，19首先按所给关键字序列画出完全二叉树，关键字3插入结点22的后边。

沿结点3到根的路径调整堆，直到满足堆的定义为止。

2.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是( )。

【2009年全国试题10(2分)】A.起泡排序B.插入排序√C.选择排序D.二路归并排序起泡排序的特点是待排序元素相邻两两比较，逆序交换，每趟有一个最大元素到达底部(或一个最小元素到达顶部)；插入排序的特点是先假定第一个元素有序，从第二个元素起，每趟将未排序元素的第一个元素插入的前面有序子文件中；选择排序的特点是第一趟在待排序元素中选最小(或最大)元素和第一个元素交换，第二趟在未排序元素中选次小(或次大)和第二个元素交换；二路归并排序是两两归并，再四四归并，等等。

3.采用递归方式对顺序表进行快速排序。

下列关于递归次数的叙述中，正确的是( )。

【2010年全国试题10(2分)】A.递归次数与初始数据的排列次序无关B.每次划分后，先处理较长的分区可以减少递归次数C.每次划分后，先处理较短的分区可以减少递归次数D.递归次数与每次划分后得到的分区的处理顺序无关√快速排序和数据的初始排列次序相关。

每次划分后，先处理较短分区可以减少递归深度，递归次数和先处理哪个分区无关。

4.对一组数据(2，12，1 6，88，5，10)进行排序，若前三趟排序结果如下：第一趟排序结果：2，12，16，5，10，88 第二趟排序结果：2，12，5，10，16，88 第三趟排序结果：2，5，10，12，16，88则采用的排序方法可能是( )。

沈阳师范大学教育技术学院862计算机学科专业基础综合（数据结构、操作系统）历年考研真题汇编附答案最新资料，WORD格式，可编辑修改！目录第一部分沈阳师范大学教育技术学院862计算机学科专业基础综合（数据结构、操作系统）历年考研真题汇编......................................................................2014年沈阳师范大学教育技术学院867计算机学科专业基础综合（数据结构、操作系统）考研真题........................................................................2013年沈阳师范大学教育技术学院867计算机学科专业基础综合（数据结构、操作系统）考研真题........................................................................ 第二部分全国硕士研究生入学统一考试408计算机学科专业基础综合历年真题及详解........2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题..................2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解............2011年全国硕士研究生入学统一考试408计算机学科专业基础综合真题..................2011年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解............2010年全国硕士研究生入学统一考试408计算机学科专业基础综合真题..................2010年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解............2009年全国硕士研究生入学统一考试408计算机学科专业基础综合真题..................2009年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解............说明：沈阳师范大学2012年之前参加全国统考408计算机学科专业基础综合，2013年开始自主命题，科目改为867计算机学科专业基础综合（数据结构、操作系统），2015年科目代码改为862。

[考研类试卷]计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编5一、综合题1 简述广义表属于线性结构的理由。

【西北大学2000一、5(3分)】2 数组、广义表与线性表之间有什么样的关系?【西北工业大学1998一、2(4分)】3 什么是广义表?请简述广义表和线性表的主要区别。

【北京大学1997二、2(5分)】4 求下列广义表的运算结果。

【南京航空航天大学1998三(10分)】(1)CAR(CDR(((a，b)，(c，d，(e，f)))(2)CDR(CAR(((a，6b)，(c，d，(e，f)))(3)CAR(CDR[(CAR(((a，b)，(e，f))))(4)CDR(CAR(CDR(((a，b)，(e，f))))(5)CDR(CDR(CAR(((a，b)，(e，f))))注：CAR运算相当于有些教材中的Head运算，CDR运算相当于Tail运算。

5 画出下列广义表的存储结构图，并利用取表头和取表尾的操作分离出原子e。

(a，(0，b)，(((e)))【清华大学1995二(10分)】6 画出下列广义表的两种存储结构图(0，A，B，(C，D)，(E,F)。

【南京航空航天大学1999三(10分)】7 知广义表A=(((a))，(b)，c，(a)，(((d,e))))(1)画出其一种存储结构图；(2)写出表的长度与深度；(3)用求头部、尾部的方式求出e。

【东北大学1997一、2(5分)】8 画出具有共享结构广义表(((b，c)，d，(a)，((a)，((b，c)，d)，e，0)的存储表示。

【北京工业大学1996一、3(6分)】9 已知下图为广义表的存储结构图，写出该图表示的广义表，并求该广义表的长度和深度。

【中国海洋大学2007一、1(8分)】10 已知下图为广义表的头尾链表存储结构图，请给出该图表示的广义表。

【北京理工大学2005三、1(4分)】11 给出下列所示的三元多项式的广义表表示(分别以X1，X2，X3第一到第三层变元。