1、计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编 2及答案与解析一、单项选择题1 对 n 阶对称矩阵作压缩存储时，需要表长为( )的顺序表。【华中科技大学 2006一、2(2 分) 】（A）n2（B） n22（C） n(n+1)2 （D）n(n-1)22 有一个 100*90 的稀疏矩阵，非 0 元素有 10 个，设每个整型数占 2 字节，则用三元组表示该矩阵时，所需的字节数是( )。【南京理工大学 1999 二、8(2 分)】（A）60（B） 66（C） 18000 （D）333 数组 A04，一 1-3，57中含有元素的个数( )。【中山大学 1998 二、5(2 分)】（A）5
2、5（B） 45（C） 36 （D）164 用数组 r 存储静态链表，结点的 next 域指向后继，工作指针 j 指向链中结点，使j 沿链移动的操作为( ) 。 【南京理工大学 2001 一、1 6(15 分)】（A）j=rfnext（B） j=1+1（C） j=f 一next （D）j=rj一next5 一个非空广义表的表尾( )。【北京交通大学 2004 一、2(2 分)】（A）不能是子表（B）只能是子表（C）只能是原子（D）是原子或子表6 广义表(a)，(b ，(c) ，(e(e ，f) ，o)的深度是( )。【华中科技大学 2007 一、7(2 分)】（A）2（B） 3（C） 4 （D）
3、57 广义表(a，(b ，(c，d(e ，f) ，g)的深度为( ) 。【北京邮电大学 2005 一、4(2 分)】（A）3（B） 4（C） 5 （D）68 广义表(a，b)，c，(d，(e)的表尾是( )。【华中科技大学 2006 一、4(2 分)】（A）(d ，(e)（B） (d(e)（C） e （D）(c，(d(e)9 已知广义表(O，(a)，(b，c，(d，(d,f) ，则以下说法正确的是( )。【华南理工大学 2006 一、7(2 分)1（A）表长为 3，表头为空表，表尾为(a)，(b，c，(d)，(d,f)（B）表长为 3，表头为空表，表尾为(b，c，(d， (d,f)（C）表长为
4、 4，表头为空表，表尾为(d,f)（D）表长为 3，表头为(O)，表尾为(a)，(b，C，(d)，(d,f)10 已知广义表 LS=(a，b，c)，(d,e ，f)，运用 head 和 tail 函数取出 LS 中原子 e 的运算是( ) 。 【西安电子科技大学 2001 应用一、3(2 分)】（A）head(tail(LS)（B） tail(head(LS)（C） head(tail(head(tail(LS)（D）head(tail(tail(head(LS)11 广义表 A=(a，b，(c ，d，(e ，(f,g) ，则下面式子 Head(Tail(Head(Tail(Tail(A)的值
5、为( ) 。 【北京邮电大学 1999 一、2(2 分) 】【烟台大学 2007 一、10(2 分)】（A）(g)（B） (d)（C） Cc （D）d12 设广义表 L=(a，b，0)，则 GetTail(GetTail(L)的结果是( )。【北京理工大学2006 九、8 (1 分) 】（A）(0)（B） 0（C） (b，0)（D）都不是13 广义表 A=(a，b，c，(d(e，f) ，则下面式子 Head(Tail(Tail(Tail(A)的值为( )。(Head 与 Tail 分别是取表头和表尾的函数。)【华南理工大学 2005 一、1(2 分)】（A）(d(e，f)（B） d（C） f
6、（D）(e，f)14 某字符串满足：concat(head(s)，head(tail(tail(s)=“ac”，(head，tail 的定义同广义表)，则 s=( )。【中国科学技术大学 1992 八、6(1 分)】（A）aabc（B） acba（C） accc （D）acac15 广义表(a，(b，c)，d,e)的表头为( )。【中山大学 1998 二、6(2 分)】（A）a（B） a，(b ， c)（C） (a，(b，c)（D）(a)二、填空题16 已知二维数组 A110，09】中每个元素占 4 个单元，在按行优先方式将其存储到起始地址为 1000 的连续存储区域时，A5，9的地址是_。【
7、厦门大学 2002 六、5(4 分)】17 用一维数组 B 与列优先存放带状矩阵 A 中的非零元素 Ai，f(1i ，i-2i+2)，B 中的第 8 个元素是 A 中的第 (1) 行，第 (2) 列的元素。【北京邮电大学 2001 二、3(4 分)】18 设数组 A08，110，数组中任一元素 Ai，j 均占内存 48 个二进制位，从首地址 2000 开始连续存放在主内存里，主内存字长为 16 位，那么(1)存放该数组至少需要的单元数是_；(2)存放数组的第 8 列的所有元素至少需要的单元数是_；(3)数组按列存储时，元素 A5，8 的起始地址是_。【中国矿业大学2000 一、4(4 分) 】
8、19 有一个 10 阶对称矩阵 A，采用压缩存储方式(以行序为主序存储，且 A00=1)，则 A85的地址为_。【北京交通大学 2005 二、3(2 分)】20 已知三对角矩阵 A19，19的每个元素占 2 个单元，现将其三条对角线上的元素逐行存储在起始地址为 1000 的连续的内存单元中，则元素 A7，8的地址为_。【合肥工业大学 2000 三、4(2 分)】三、判断题21 广义表的长度是指广义表中的原子个数。( )【北京邮电大学 2006 二、5(1 分)】（A）正确（B）错误22 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。( )【合肥工业大学 2000 二、3(1
9、分)】（A）正确（B）错误23 广义表中原子个数即为广义表的长度。( )【中国海洋大学 2007 二、6(1 分)】（A）正确（B）错误24 若一个广义表的表头为空表，则此广义表亦为空表。( )【中国海洋大学 2006二、4(1 分) 】【 中科院软件所 1997 一、8(1 分) 】【长沙铁道学院 1998 一、8(1 分)】（A）正确（B）错误25 任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广义表。( )【中国海洋大学 2006 二、5(1 分)】（A）正确（B）错误26 广义表是由零或多个原子或子表所组成的有限序列，所以广义表可能为空表。( )【中国海洋大学 2006
10、二、6(1 分)】（A）正确（B）错误27 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。( )【南京航空航天大学 1996 六、2(1 分)】（A）正确（B）错误28 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。( )【合肥工业大学 2000 二、3(1 分)】（A）正确（B）错误29 所谓取广义表的表尾就是返回广义表中最后一个元素。( )【合肥工业大学2001 二、3(1 分) 】（A）正确（B）错误30 广义表的同级元素(直属于同一个表中的各元素)具有线性关系。( )【华南理工大学 2002 一、9(1 分) 】（A）正确（B）错误计算机专业基础综合数
11、据结构（数组和广义表）历年真题试卷汇编 2答案与解析一、单项选择题1 【正确答案】 C2 【正确答案】 B【试题解析】 三元组的每个元素包括行值、列值和元素值，10 个非零元素占 60字节。加上三元组表中行数、列数和总的非零元素个数所占的 6 字节，故选 B。3 【正确答案】 B4 【正确答案】 A5 【正确答案】 B6 【正确答案】 C7 【正确答案】 C8 【正确答案】 D9 【正确答案】 A10 【正确答案】 C11 【正确答案】 D12 【正确答案】 A13 【正确答案】 A14 【正确答案】 C15 【正确答案】 A二、填空题16 【正确答案】 119617 【正确答案】 第 1 行
12、第 3 列，这是一个五对角矩阵。18 【正确答案】 (1)270 (2)27 (3)220419 【正确答案】 4120 【正确答案】 1038 三对角矩阵按行序存储的地址公式：k=2(i 一 1)+j(1i，jn)三、判断题21 【正确答案】 B22 【正确答案】 B23 【正确答案】 B24 【正确答案】 B【试题解析】 广义表的表头是广义表的第一个元素。只有非空广义表才能取表头。25 【正确答案】 A26 【正确答案】 A27 【正确答案】 B【试题解析】 广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。28 【正确答案】 B【试题解析】 广义表中元素可以是原子，也可以是表(包括空表和非空表)。29 【正确答案】 B【试题解析】 广义表的表尾，指去掉表头元素后，剩余元素所组成的表。30 【正确答案】 A
