1、计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编 3及答案与解析一、单项选择题1 已知 Head(Tail(Head(S)，Head(Tail(Tail(S)=a，广义表 S 满足上式，则 s 为( )(其中，方括号表示广义表，圆括号表示函数，如a，b表示由 a，b 构成的广义表，而 Head()表示取广义表的头部)。【中国科学技术大学 1995 十四、5(2 分)】（A）a，6，b，a（B） b，a，a，b（C） a，a，b，b（D）b ，a ，a，b E：a ，b ，b，a Fb，b，a，a2 广义表()的表头是( )，表尾是( )。【电子科技大学 2003 一、4(208 分)
2、】（A）O（B） NIL（C） (O)（D）(O)3 将线性表的数据元素进行扩充，允许是带结构的线性表的是( )。【电子科技大学 2001 一、8(1 分) 】（A）串（B）树（C）广义表（D）栈4 下面说法不正确的是( )。【南京理工大学 2001 一、3(15 分)】【江苏大学2006 一、1(2 分) 】（A）广义表的表头总是一个广义表（B）广义表的表尾总是一个广义表（C）广义表难以用顺序存储结构（D）广义表可以是一个多层次的结构5 下面说法不正确的是( )。【电子科技大学 2008 一、5(1 分)】（A）广义表的表尾总是一个广义表（B）广义表难以用顺序存储结构（C）广义表的表头总是一
3、个广义表（D）广义表可以上是一个递归结构二、填空题6 设有一个 10 阶对称矩阵 A 采用压缩存储方式(以行为主序存储：a 11=1)，则 a85 的地址为_。 【西安电子科技大学 1999 软件一、3(2 分)】7 所谓稀疏矩阵指的是_。 【厦门大学 2001 一、2(145 分)】8 对矩阵压缩是为了_。【北京理工大学 2000 二、3(2 分)】9 上三角矩阵压缩的下标对应关系为_。【福州大学 1998 二、6(2 分)】10 广义表的表尾是指除第一个元素之外，_。【中山大学 1998 一、7(1分)】【 北京邮电大学 2006 一、7(2 分)】11 广义表简称表，是由零个或多个原子或
4、子表组成的有限序列，原子与表的差别仅在于 (1)。为了区分原子和表，一般用(2) 表示表，用(3)表示原子。一个表的长度是指(4)，而表的深度是指 (5) 。【山东工业大学 2000 一、3(3 分)】【山东大学1998 一、2(3 分) 】12 广义表(A，B，C，D)的表尾是_。【中南大学 2005 二、2(2 分)】13 设有广义表 LS=(a，b，c)，(d,e ，f)，取出原子 e 的运算是_。【北京交通大学 2005 二、6(2 分)】14 广义表 A(b，A) 的长度为 (1) ，深度为 (2) 。 【电子科技大学 2005 二、4(1 分)】15 设有广义表 A=(c，(a ，
5、b)，(x ，(a，b)，y)，则运算 head(taead(tail(A)的结果是_。【东南大学 2005 数据结构部分二、4(1 分)】16 广义表(O，(a)，(b ，(c，d)f)的深度为_ 。【电子科技大学 2014 一、2(1 分)】17 设广义表 L=(O，O) ，则 llead(L)是(1)；tail(L)是(2)；L 的长度是(3)；深度是(4)。【中科院计算所 1998 一、2(4 分)】【中国科技大学 1998 一、2(4 分)】18 已知广义表 A=(9，7，(8，10，(99)，12)，试用求表头和表尾的操作 head()和tail()将原子元素 99 从 A 中取出
6、来_。【西安交通大学 1996 四、5(5 分)】19 广义表(a，(a，b)，e，(i，j，k) 的长度是(1)，深度是(2) 。【山东大学 2001 三、9(2 分)】【哈尔滨工业大学 2001 一、2(2 分) 】20 广义表 A=(a，b)，(c ，d,e) ，取出 A 中的原子 e 的操作是：_。【合肥工业大学 1999 三、5(2 分)】21 设有广义表 A=(a，b)，x)，(a)，(b)，(c ，(d(y)，得到 y 的对广义表 A 的操作序列是_。【北京交通大学 2004 二、6(2 分)】22 TailTailHead(a，b) ，(c)，(d，(e，f)的运算结果是_，其
7、中“，是函数的符号。 【北京邮电大学 2004 二、3(2 分)】23 已知广义表 A=(a，b)，(c)，(d,e)，head(tail(tail(head(A)的结果是_。【合肥工业大学 2001 三、5(2 分)】24 利用广义表的 GetHead 和 GetTail 操作，从广义表 L=(apple，pear)，(banana，orange)中分离出原子 bananad 的函数表达式是_。【山东大学200l 三、6(2 分) 】25 下列程序段 search(a， n，k)在数组 a 的前 n(n1)个元素中找出第 k(1kn)小的值。这里假设数组 a 中各元素的值都不相同。#defi
8、ne MAXN 100int aMAXN，n，k；int qearchc(int a， int n， int k)int low，high， i， j， m ， t；k一，; low=0；high=n 一 1；doi=low； j=high；t=alow；dowhile(i=ai) i+if(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)
9、；S=S 一val-pt：2=tp；s 一tag=1；s 一Val ptrtp=NULL ；s 一valptrhp=h；(4)elseq=(glist：)malloc(sizeof(gnode)jq 一tag=1;q 一Tal ptrtp=NULL；(5);return(q)；【上海大学 2002 六、3(10 分)】27 完善下列程序，每小题在 Pascal 语言(a)和 C 语言(b)中任选一题。下面的程序将数列 1，2，3，n*n 依次按蛇型方式存放在二维数组 A1.n，1.n中(示意图编者略)。#deflne NMAX 10#include“stdioh”main()int i，J，n
10、，k，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) 处理原子 (2)h：reverse(p 一val ptrhp) 处理表头 (3)(p-valptr tp) 产生表尾的逆置广义表 (4)s-valptr=tp ：t； 连接 (5)q-valptr=hp：h 头结点指向广义表27 【正确答案】 本题要求将 1，2，n*n 个自然数，按蛇形方式存放在二位数组 Ann中。“蛇形”方式，即是按“副对角线” 平行的各
11、对角线，从左下到右上，再从右上到左下，存放 n2 个整数。对角线共 2，2 一 1 条，在副对角线上方的对角线，题目中用 k 表示第 k 条对角线(最左上角 k=1)，数组元素的 x 和 y 方向坐标之和为 k+1(即题目中的 i+j=k+1)。副对角线下方第 k 条对角线与第 2nk 条对角线对称，其元素的下标等于其对称元素的相应坐标各加(k-n)。(1)k=n 修改副对角线下方的下标 i 和 j(5)m+；或 m=m+1 为填下个数作准备，m 变化范围 1n*n本题解法的另一种思路见本章算法设计题第 9 题。28 【正确答案】 若第 n 件物品能放入背包，则问题变为能否再从 n 一 1 件物品中选出若干件放入背包(这时背包可放入物品的重量变为 swn)。若第 n 件物品不能放入背包，则考虑从 n 一 1 件物品选若干件放入背包(这时背包可放入物品仍为s)。若最终 s=0，则有一解；否则，若 s0 但物品数 n1，则无解。(1)sWn，n 一 1 Knap(sWn，n 一 1)=true(2)S，n 一 1 Knap*-Knap(s ，n 一 1)29 【正确答案】 (1)n (2)j=n (3)nj三、判断题30 【正确答案】 A31 【正确答案】 A32 【正确答案】 B
