1、计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编 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(C
2、DR(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 一、
3、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，X 2，X 3 第一到第三层变元。)P(X 1X2X3)=X15X23X3+2X1X2X3+5X15X23X33+3X1X24X32+X2X3
4、+6【华南理工大学 2001 一、2(4 分) 】12 设某表 H 如下：其中 A，B，C 为子表名， a1，a 2，b 1，c 1，c 2，x 为其元素。(1)试用广义表形式表示 H，并写出运算 HEAD和 TAIL函数从日中取出单元素 a2 的运算；(2)画出表 H 的链式存储结构。【北京科技大学 1998 三(10 分)】13 下列广义表，可以唯一对应一棵二叉树的有( )，并归纳出唯一对应的条件。(1)(A(B(D，E)，C(F) (2)(A(B(D，E，C) (3)(A)(4)(A(B(C，D(E) (5)0【电子科技大学 2003 二、4(307 分)】二、设计题13 二项式(a+b
5、) n 展开式的系数为 C(n，0)=1，C(n，n)=1，对于 n0;C(n，k)=C(n 一1，k)+C(n 一 1，k-1)，对于 014 试写一个递归算法，根据以上公式生成 C(n，k)。(6 分)15 试画出计算 C(6，4)的递归树。(4 分)16 试写一个非递归算法，既不用数组也不用栈，对于任意的 0kn 计算 C(n，k)。(6 分)【清华大学 1999 五(16 分) 】17 设计将数组 An中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为 O(n)。 【哈尔滨工业大学 2002 十(8 分)】18 若 S 是 n 个元素的集合，则 S 的幂集 P(S)定义
6、为 S 所有子集的集合。例如，S=(a，b，c)，P(S)=0，(a)，(b)，(c)，(a，b)，(b， c)，(b，c)，(a，b，c)。给定S，写一递归算法求 P(S)。【东南大学 1993 五(15 分)1997 五(15 分) 】19 编写算法打印出由指针 Hm 指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意：行、列及总表头结点的形式为：它们已用 val 域链接成循环链表。非零元的结点形式也同上，每一行(列) 的非零元由 right(down)域把它们链接成循环链表，该行(列)的表头结点即为该行(列) 循环链表的表头。【上海大学 1998 五(16 分)】20
7、试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入：(a 1，a 2，a 3，a n)， n0，其中 at 或为单字母表示的原子或为广义表，n=0 时为只含空格字符的空表。【北京工业大学 1998 十(15 分)】20 数组研 1：1000 中存放着 1000 个大小不同的正整数。21 选择一分类算法使能最快地得到其中 10 个最大的数，简要说明理由；22 编写一程序 seek()，执行该程序时，在命令行中提供两个参数。seek a n表示需打印 H中 n 个最大数。 seek i n表示需打印 H中 n 个最小数。【浙江大学 1994 八(1 8 分
8、) 】23 已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入前一个数组序列中，完成后两个数组中的数分别有序(非降序)并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。例如，第一个数组为：4，12，28 第二个数组为：1，7，9，29，45 输出结果为：1，4，7一第一个数组 9，12，28，29，45-一第二个数组【上海大学 1998 四(20 分)】24 设数组 A1N中，An 一 2k+1,n 一 k和 An 一 k+1.n中元素各自从小到大排好序，试设计一个算法使 An 一 2k+1n
9、按从小到大次序排好序。并分析算法所需的计算时间。【福州大学 1998 四、3(10 分)】25 设 A1100 是一个记录构成的数组， B1 100是一个整数数组，其值介于 1100 之间，现要求按 B1100的内容调整 A 中记录的次序，比如当 B1=11 时，则要求将 A1的内容调整到 A11中去。规定可使用的附加空间为 O(1)。【中科院计算所 2000 七(15 分)】26 给定有 m 个整数的递增有序数组 a1m 和有 n 个整数的递减有序数组b1n，试写出算法：将数组 a 和 b 归并为递增有序数组 c1 一m+n。(要求：算法的时间复杂度为 O(m+n)。)【华中理工大学 200
10、0 八、1(10 分) 】27 设 A 和 B 均为下三角矩阵，每一个都有 n 行 n 列。因此在下三角区域中各有n(n+1)2 个元素。另设有一个二维数组 C，它有 n 行 n+1 列。试设计一个方案，将两个矩阵 A 和 B 中的下三角区域元素存放于同一个 C 中。要求将 A 的下三角区域中的元素存放于 C 的下三角区域中，B 的下三角区域中的元素转置后存放于 C的上三角区域中。并给出计算 A 的矩阵元素 aij 和 B 的矩阵元素 bij 在 C 中的存放位置下标的公式。【东北大学 2003 一、3(5 分)】28 设稀疏矩阵 Mm 中有 f 个非零元素，用三元组顺序表的方式存储。请设计一
11、个算法，计算矩阵 M 的转置矩阵 N，要求转置算法的时间复杂度为 O(n+t)。【苏州大学 2005 四(20 分) 】【中南大学 2004 三、4(10 分) 】【兰州大学 2002 八(10 分)】29 已知一个 nn 的上三角矩阵口的上三角元素已按行主序连续存放在数组 b 中，请设计一个函数 trans 将 b 中元素按列主序连续存放至数组 c 中。例：设 n=5b=(1，2，3，4，5，6，7，8，9，10，11，12，13，14，15) c=(1，2，6，3，7，10，4，8，11，1 3，5，9，12，14，15)【中国科学技术大学1997 四、1(1 5 分) 】30 试写出算法
12、(C 函数或 C 程序)：输入 m 行 n 列整数矩阵 a，若存在 4 个相邻的元素相同，即有 aij=aij+1=ai+1j=ai+1j+1 (1i=n)coutright=rch 时该行无非零元素，用 i 记行号，用一维数组元素 Ai记第 i 行非零元素个数。当 rch=Hm 时各行非零元素计算完毕。核心语句段如下：while(rch!=Hm) 初值 rch=Hm 一uvalnex，循环完各行列表头p： rch 一right ; num=0； P 是稀疏矩阵行内工作指针，num 记该行非零个数while(p!=rch) 完成行内非零元素的查找printf(“Md d=d”，p 一row ，
13、p 一col，p 一uval.e)；num+；p=P 一right；printf Cn”) ；指针后移Ai+=num； 数组 A 记各行非零元个数， i 记行号rch=rch 一uval next； 移到下一行列表头20 【正确答案】 广义表可以看作是扩充的线性表：其元素是原子或表。在读入广义表“表达式 ”时，遇到左括号 (就递归地构造子表；否则，若是原子，就建立原子结点；若读入逗号， ，就递归 构造后续子表；直到碰到输入结束符号()。设广义表的形式定义如下：typedef struct nodeint tag； tag=0 为原子， tag=l 为子表struct node*link； 指向
14、后继结点的指针union f struct node*slink； 指向子表的指针char data； 原子element；Glist；算法核心语句段如下：cinch；if(ch=)gh=null；elsegh=new(Glist)；if(ch=()gh 一tag=l； 子表gh 一element.slink=creat() ； 递归构造子表else(gh 一tag=0；gh 一elementdata=ch； 原子结点cinch；if(gh!=null)if(ch=-)gh 一link=creat()； 递归构造后续广义表else gh-link=null；需要指出，题中“n=0 时为只含空格
15、字符的空表一叙述有误。n=0 表示广义表是空表。空表长度为 0，不含任何元素，而不是“只含空格字符的空表” 。21 【正确答案】 在 n 个正整数中，选出 k(km)(printf(“参数错误 n”)；exit(0) ；) m=1000 是要求数for(i=0；ir i； 输入 1000 个大小不同的正整数if(augv1a) 输出 n 个最大数，要求建立大根堆for(i=m2；i0 ；i 一一)sift(r，i，m，1)； sift(r，i ，m ，1)是建堆，1 是大小堆sift(r，1， i 一 1，1) ；) 调堆else(augv1：=i) 要求建立小根堆 输出 n 个最小数23 【
16、正确答案】 设两个数组分别是 A 和 B，各有 m 和 n 个元素。结果要求第一个数组的最后一个数 Am 一 1不大于第二个数组的第一个数 B0。由于要求将第二个数组的数插入第一个数组中。因此比较 Am 一 1和 B0，如 Aim 一 1B0，则交换。交换后仍保持 A 和 B 有序。重复以上步骤，直到 Am 一 1B0为止。核心语句段如下：while(Am-1B0)x=Am 一 1；Am 一 1=B0； 交换 Am 一 1和 B0在 0m 一 2 间折半查找 Am 一 1的插入位置，并插入在 1n 一 1 间折半查找 x 的插入位置，并插入24 【正确答案】 数组 A 的相邻两段分别有序，要求
17、将两段合并为一段有序。由于要求附加空间为 O(1)，所以将两段最后一个元素比较，若正序，则后段指针前移；若逆序则交换，并调整前段有序。重复以上过程直到正序为止。最佳情况出现在数组第二段值最小元素 An 一 k+1大于等于第一段值最大元素 An 一 k，只比较 k次无须交换，时间复杂度为 O(n)。最差情况出现在第一段的最小值大干第二段的最大值，两段数据间发生了 k 次交换，而且每次段交换都在段内发生了平均(k-1)次交换，时间复杂度为 O(n2)。25 【正确答案】 题目要求按 B 数组内容调整 A 数组中记录的次序，可以从 i=1 开始，检查是否 Bi=i。如是，则 Ai恰为正确位置，不需再
18、调；否则，Biki，则将 Ai和 Ak对调，Bi和 BK对调，直到 Bi=i 为止。核心语句段如下：while(i=0)if(ai=0)ck+=bj 一一 ；若不允许另辟空间，结果在 A 数组(空间足够大)，则初始 k=m+n 一 1，请参见第2 章算法设计题第 18 题。27 【正确答案】 将，z 阶方阵的下三角 A 复制到 C，B 逆置后复制到 C。核心语句段如下： for(i=0 ； i ij 和 B 的矩阵元素 bij 在 C 中的存放位置下标的公式： Aij=Cij； 0i28 【正确答案】 转置可按转置矩阵的三元组表中的元素顺序进行，即按稀疏矩阵的列序。这种方法时间复杂度是 O(n
19、*t)，当 t 和 m*n 同量级时，时间复杂度为O(n2)。另一种转置方法称作快速转置，使时间复杂度降为 O(m*n)。需要求出每列非零元素个数和每列第一个非零元素在转置矩阵三元组表中的位置，因此设置了两个附加向量。快速转置的核心语句段如下： Nm=M.n； N n=Mm； Nlen=M1en； if(Mlen) (for(j：1 ； j=Mn；j+)numbj=0； 矩阵 M每一列非零元素初始化为零 for(t=1；t29 【正确答案】 nn 的上三角矩阵以行序为主存储在一维数组 b 中，其位置 kl 和元素在矩阵中的下标 i 和 j 有确定关系：kl=(i 木(2n 一 i+3)2+(广
20、 f+1)=i(2ni 一1)2+j (ij，0i，j 2 和元素在下三角矩阵中的下标 i 和 j 也有确定关系： k2=i(i+1)2+j (ji) (222) 得 i=(一 3+sqrt(9+8*k)2 l 和 j=k-i(i+1)2。 从(222)式，对每个 k2(其值域为 1kn(n+1)2)，计算出 i 和 j，然后，用求出的 i 和 j，i 和 j 互换，代入(22 一 1)式，计算出 k2，该 k2 位置的值就应存入 k2 中。 for(k=0；k(n*(n+1)2；k+) (i=(int)(一 3+sqrt(9+8*k)2+09) ； 计算元素ck在矩阵中的下标 i 和 j j=k-i*(i+1)2； k1=j*(2*nj 一 1)2+i； 矩阵中下标 i 和 j 的元素在数组 b 中的序号 Ck=bk1; 30 【正确答案】 将矩阵的行列下标平移，设矩阵行 0m 一 1，列 0n 一 1。把首尾行(0 和 m 一 1)、列 (0 和 n 一 1)看做相邻，则核心语句段如下：for(i=0，im；i+)for(J=0; jn;j+)if(aij=ai(j+1)n&ai(j+1)n=a(i+1)mj&a(i+1)mj=a(i+1)m(j+1)n)cout“True”；cout“False”：
