1、计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编2 及答案解析(总分：64.00，做题时间：90 分钟)一、单项选择题(总题数：5，分数：10.00)1.已知 Head(Tail(Head(S)，Head(Tail(Tail(S)=a，广义表 S 满足上式，则 s 为( )(其中，方括号表示广义表，圆括号表示函数，如a，b表示由 a，b 构成的广义表，而 Head()表示取广义表的头部)。【中国科学技术大学 1995 十四、5(2 分)】（分数：2.00）A.a，6，b，aB.b，a，a，bC.a，a，b，bD.b，a，a，b E：a，b，b，a Fb，b，a，a2.广义表()的表头
2、是( )，表尾是( )。【电子科技大学 2003 一、4(208 分)】（分数：2.00）A.OB.NILC.(O)D.(O)3.将线性表的数据元素进行扩充，允许是带结构的线性表的是( )。【电子科技大学 2001 一、8(1 分)】（分数：2.00）A.串B.树C.广义表D.栈4.下面说法不正确的是( )。【南京理工大学 2001 一、3(15 分)】【江苏大学 2006 一、1(2 分)】（分数：2.00）A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C.广义表难以用顺序存储结构D.广义表可以是一个多层次的结构5.下面说法不正确的是( )。【电子科技大学 2008 一、5(1
3、 分)】（分数：2.00）A.广义表的表尾总是一个广义表B.广义表难以用顺序存储结构C.广义表的表头总是一个广义表D.广义表可以上是一个递归结构二、填空题(总题数：24，分数：48.00)6.设有一个 10 阶对称矩阵 A 采用压缩存储方式(以行为主序存储：a 11 =1)，则 a 85 的地址为_。 【西安电子科技大学 1999 软件一、3(2 分)】（分数：2.00）_7.所谓稀疏矩阵指的是_。 【厦门大学 2001 一、2(145 分)】（分数：2.00）_8.对矩阵压缩是为了_。【北京理工大学 2000 二、3(2 分)】（分数：2.00）_9.上三角矩阵压缩的下标对应关系为_。【福州
4、大学 1998 二、6(2 分)】（分数：2.00）_10.广义表的表尾是指除第一个元素之外，_。【中山大学 1998 一、7(1 分)】【北京邮电大学2006 一、7(2 分)】（分数：2.00）_11.广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于 (1)。为了区分原子和表，一般用(2)表示表，用(3)表示原子。一个表的长度是指(4)，而表的深度是指 (5) 。【山东工业大学 2000 一、3(3 分)】【山东大学 1998 一、2(3 分)】（分数：2.00）_12.广义表(A，B，C，D)的表尾是_。【中南大学 2005 二、2(2 分)】（分数：2.00）
5、_13.设有广义表 LS=(a，b，c)，(d,e，f)，取出原子 e 的运算是_。【北京交通大学 2005 二、6(2 分)】（分数：2.00）_14.广义表 A(b，A)的长度为 (1) ，深度为 (2) 。【电子科技大学 2005 二、4(1 分)】（分数：2.00）_15.设有广义表 A=(c，(a，b)，(x，(a，b)，y)，则运算 head(taead(tail(A)的结果是_。【东南大学 2005 数据结构部分二、4(1 分)】（分数：2.00）_16.广义表(O，(a)，(b，(c，d)f)的深度为_。【电子科技大学 2014 一、2(1 分)】（分数：2.00）_17.设广
6、义表 L=(O，O)，则 llead(L)是(1)；tail(L)是(2)；L 的长度是(3)；深度是(4)。【中科院计算所 1998 一、2(4 分)】【中国科技大学 1998 一、2(4 分)】（分数：2.00）_18.已知广义表 A=(9，7，(8，10，(99)，12)，试用求表头和表尾的操作 head()和 tail()将原子元素 99从 A 中取出来_。【西安交通大学 1996 四、5(5 分)】（分数：2.00）_19.广义表(a，(a，b)，e，(i，j，k)的长度是(1)，深度是(2)。【山东大学 2001 三、9(2 分)】【哈尔滨工业大学 2001 一、2(2 分)】（分
7、数：2.00）_20.广义表 A=(a，b)，(c，d,e)，取出 A 中的原子 e 的操作是：_。【合肥工业大学 1999三、5(2 分)】（分数：2.00）_21.设有广义表 A=(a，b)，x)，(a)，(b)，(c，(d(y)，得到 y 的对广义表 A 的操作序列是_。【北京交通大学 2004 二、6(2 分)】（分数：2.00）_22.TailTailHead(a，b)，(c)，(d，(e，f)的运算结果是_，其中“，是函数的符号。【北京邮电大学 2004 二、3(2 分)】（分数：2.00）_23.已知广义表 A=(a，b)，(c)，(d,e)，head(tail(tail(hea
8、d(A)的结果是_。【合肥工业大学 2001 三、5(2 分)】（分数：2.00）_24.利用广义表的 GetHead 和 GetTail 操作，从广义表 L=(apple，pear)，(banana，orange)中分离出原子 bananad 的函数表达式是_。【山东大学 200l 三、6(2 分)】（分数：2.00）_25.下列程序段 search(a，n，k)在数组 a 的前 n(n1)个元素中找出第 k(1kn)小的值。这里假设数组 a 中各元素的值都不相同。 #define MAXN 100 int aMAXN，n，k； int qearchc(int a， int n， int k
9、) int low，high， i， j， m， t； k一，; low=0；high=n 一 1； doi=low； j=high；t=alow； dowhile(i=ai) i+ if(i_26.完善下列程序，每小题在 Pascal 语言(a)和 C 语言(b)中任选一题。下面是一个将广义表逆置的过程。例如，原来广义表为(a，b)，c，(d,e)，经逆置后为(e，d)，c，(b，a)。 typedef：ruct glist：node int：tag； 8truct：glistnode*next； unionchar data； structstruct glstnode*hp， *tp；)
10、ptr； val； *gli8t，gnode； glist reverse(p) glist：p； glist q，h，t，s； if(p=NULL) q=NuLL； else if (1) q=(gli8t)malloc(szeof(gnode)；q 一tag=0； q 一Valdata=p-va1data； else(2) if(3) t=reVerse(p 一Talpt：rtp)；8=t； while(8一Talpt：rtp!=NULL) S-“S 一valp 七 rtp； 8 一valptrtp=(glist：)malloc(sizeof(gnode)； S=S 一val-pt：2=t
11、p；s 一tag=1；s 一Valptrtp=NULL； s 一valptrhp=h；(4) elseq=(glist：)malloc(sizeof(gnode)jq 一tag=1; q 一Talptrtp=NULL；(5); return(q)； 【上海大学 2002 六、3(10 分)】（分数：2.00）_27.完善下列程序，每小题在 Pascal 语言(a)和 C 语言(b)中任选一题。下面的程序将数列1，2，3，n*n 依次按蛇型方式存放在二维数组 A1.n，1.n中(示意图编者略)。#deflne NMAX 10 #include“stdioh” main() int i，J，n，k
12、，P，q，m； int aNMAXNMAX； scanf(“d”， k+) if(k：1 j j 一一) (3 分) (ak=j； if( (2) ) (3 分) printf(”d=d”? a0， a1)； for(i=2；itag=0； q 一Valdata=p-va1data； else(2) if(3) t=reVerse(p 一Talpt：rtp)；8=t； while(8一Talpt：rtp!=NULL) S-“S 一valp 七 rtp； 8 一valptrtp=(glist：)malloc(sizeof(gnode)； S=S 一val-pt：2=tp；s 一tag=1；s 一
13、Valptrtp=NULL； s 一valptrhp=h；(4) elseq=(glist：)malloc(sizeof(gnode)jq 一tag=1; q 一Talptrtp=NULL；(5); return(q)； 【上海大学 2002 六、3(10 分)】（分数：2.00）_正确答案：(正确答案：逆置广义表的递归模型如下： )解析：27.完善下列程序，每小题在 Pascal 语言(a)和 C 语言(b)中任选一题。下面的程序将数列1，2，3，n*n 依次按蛇型方式存放在二维数组 A1.n，1.n中(示意图编者略)。#deflne NMAX 10 #include“stdioh” mai
14、n() int i，J，n，k，P，q，m； int aNMAXNMAX； scanf(“d”， k+) if(k=n 修改副对角线下方的下标 i 和 j (5)m+；或m=m+1 为填下个数作准备，m 变化范围 1n*n 本题解法的另一种思路见本章算法设计题第 9 题。)解析：28.设有一个背包可以放入的物品重量为 S，现有 n 件物品，重量分别为 W 1 ，W 2 ，W n 。问能否从这 n 件物品中选择若干件放入背包，使得放入的重量之和正好是 S。设布尔函数 Knap(S，n)表示背包问题的解，W(i=1，2，n)均为正整数，并已顺序存储在数组 W 中。请在下列算法的下划线处填空，使其正
15、确求解背包问题。 Knap(S，n) 若 S=0 则 Knaptrue 否则若(S0 且 n_正确答案：(正确答案：若第 n 件物品能放入背包，则问题变为能否再从 n 一 1 件物品中选出若干件放入背包(这时背包可放入物品的重量变为 swn)。若第 n 件物品不能放入背包，则考虑从 n 一 1 件物品选若干件放入背包(这时背包可放入物品仍为 s)。若最终 s=0，则有一解；否则，若 s0 但物品数 n解析：29.对于正整数 n，输出其和等于 n 且满足以下限制条件的所有正整数的和式，组成和式的数字自左至右构成一个非递增的序列，如 n=4，程序输出为； 4=4 4=3+1 4=2+2 4=2+1
16、+1 4=1+1+1+1 test 是实现该功能的 C 程序段，请将未完成的部分补足，使之完整。test 函数为一递归函数，参数 n 为被分解和式的数，k 为当前的分解深度。算法思想是对 n 的所有合理的和式分解，将分解出的数(称为和数)存于数组 a中。当其中一个分解已不再需要进一步进行时，即找到一个解，将存于 a中的一个完整和式的和数输出。当还需要进一步分解的数及分解时，以要进一步分解的数及分解深度为参数，递归调用 test 函数。 #define MAXN 100 int aMAXN；test(Int n， lnt K int i，j； for(j= (1) i j：1 j j 一一) (
17、3 分) (ak=j； if( (2) ) (3 分) printf(”d=d”? a0， a1)； for(i=2；i=k；i+) prin 七 f(“+d”， ai)； printf(“n”)； else test(3);k+1)； (4 分) main()( test(4， 1)； )【中国科学技术大学 1997 三、1(10 分)】（分数：2.00）_正确答案：(正确答案：(1)n (2)j=n (3)nj)解析：三、判断题(总题数：3，分数：6.00)30.对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。( )【华南理工大学 2002 一、10(1 分)】（分数：2.00）A.正确 B.错误解析：31.一个广义表可以为其他广义表所共享。( )【山东大学 2001 一、2(1 分)】（分数：2.00）A.正确 B.错误解析：32.广义表(a，b，c)，d,e，f)的长度是 4。( )【北京交通大学 2004 三、10(2 分)】（分数：2.00）A.正确B.错误 解析：
