1、计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编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、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。(a，(0，b)，(e)【清华大学 1995 二(10 分)】（分数：2.00）_6.画出下列广义表的两种存储结构图(0，A，B，(C，D)，(E,F)。【南京航空航天大学 1999 三(10 分)】（分数：2.00
3、）_7.知广义表 A=(a)，(b)，c，(a)，(d,e)(1)画出其一种存储结构图；(2)写出表的长度与深度；(3)用求头部、尾部的方式求出 e。【东北大学 1997 一、2(5 分)】（分数：2.00）_8.画出具有共享结构广义表(b，c)，d，(a)，(a)，(b，c)，d)，e，0)的存储表示。【北京工业大学1996 一、3(6 分)】（分数：2.00）_9.已知下图为广义表的存储结构图，写出该图表示的广义表，并求该广义表的长度和深度。【中国海洋大学 2007 一、1(8 分)】 （分数：2.00）_10.已知下图为广义表的头尾链表存储结构图，请给出该图表示的广义表。【北京理工大学
4、2005 三、1(4分)】 （分数：2.00）_11.给出下列所示的三元多项式的广义表表示(分别以 X 1 ，X 2 ，X 3 第一到第三层变元。)P(X 1 X 2 X 3 )=X 1 5 X 2 3 X 3 +2X 1 X 2 X 3 +5X 1 5 X 2 3 X 3 3 +3X 1 X 2 4 X 3 2 +X 2 X 3 +6【华南理工大学2001 一、2(4 分)】（分数：2.00）_12.设某表 H 如下： （分数：2.00）_13.下列广义表，可以唯一对应一棵二叉树的有( )，并归纳出唯一对应的条件。(1)(A(B(D，E)，C(F) (2)(A(B(D，E，C) (3)(A)
5、(4)(A(B(C，D(E) (5)0【电子科技大学 2003 二、4(307 分)】（分数：2.00）_二、设计题(总题数：14，分数：34.00)二项式(a+b) n 展开式的系数为 C(n，0)=1，C(n，n)=1，对于 n0;C(n，k)=C(n 一 1，k)+C(n 一 1，k-1)，对于 0 （分数：6.00）(1).试写一个递归算法，根据以上公式生成 C(n，k)。(6 分)（分数：2.00）_(2).试画出计算 C(6，4)的递归树。(4 分)（分数：2.00）_(3).试写一个非递归算法，既不用数组也不用栈，对于任意的 0kn 计算 C(n，k)。(6 分)【清华大学199
6、9 五(16 分)】（分数：2.00）_14.设计将数组 An中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为 O(n)。 【哈尔滨工业大学 2002 十(8 分)】（分数：2.00）_15.若 S 是 n 个元素的集合，则 S 的幂集 P(S)定义为 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 分)】（分数：2.00）_16.编写算法打印出由指针 Hm 指向总表头的以十字链表形式存储的稀疏矩阵
7、中每一行的非零元的个数。注意：行、列及总表头结点的形式为： （分数：2.00）_17.试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入：(a 1 ，a 2 ，a 3 ，a n )，n0，其中 a t 或为单字母表示的原子或为广义表，n=0 时为只含空格字符的空表。【北京工业大学 1998 十(15 分)】（分数：2.00）_数组研 1：1000 中存放着 1000 个大小不同的正整数。（分数：4.00）(1).选择一分类算法使能最快地得到其中 10 个最大的数，简要说明理由；（分数：2.00）_(2).编写一程序 seek()，执行该程序时，在命令行
8、中提供两个参数。seek a n 表示需打印 H中 n 个最大数。seek i n 表示需打印 H中 n 个最小数。【浙江大学 1994 八(1 8 分)】（分数：2.00）_18.已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入前一个数组序列中，完成后两个数组中的数分别有序(非降序)并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。例如，第一个数组为：4，12，28 第二个数组为：1，7，9，29，45 输出结果为：1，4，7一第一个数组9，12，28，29，45-一第二个数组【上海大学
9、1998 四(20 分)】（分数：2.00）_19.设数组 A1N中，An 一 2k+1,n 一 k和 An 一 k+1.n中元素各自从小到大排好序，试设计一个算法使 An 一 2k+1n按从小到大次序排好序。并分析算法所需的计算时间。【福州大学 1998 四、3(10 分)】（分数：2.00）_20.设 A1100是一个记录构成的数组，B1100是一个整数数组，其值介于 1100 之间，现要求按 B1100的内容调整 A 中记录的次序，比如当 B1=11 时，则要求将 A1的内容调整到 A11中去。规定可使用的附加空间为 O(1)。【中科院计算所 2000 七(15 分)】（分数：2.00）
10、_21.给定有 m 个整数的递增有序数组 a1m和有 n 个整数的递减有序数组 b1n，试写出算法：将数组 a 和 b 归并为递增有序数组 c1 一m+n。(要求：算法的时间复杂度为 O(m+n)。)【华中理工大学2000 八、1(10 分)】（分数：2.00）_22.设 A 和 B 均为下三角矩阵，每一个都有 n 行 n 列。因此在下三角区域中各有 n(n+1)2 个元素。另设有一个二维数组 C，它有 n 行 n+1 列。试设计一个方案，将两个矩阵 A 和 B 中的下三角区域元素存放于同一个 C 中。要求将 A 的下三角区域中的元素存放于 C 的下三角区域中，B 的下三角区域中的元素转置后存
11、放于 C 的上三角区域中。并给出计算 A 的矩阵元素 a ij 和 B 的矩阵元素 b ij 在 C 中的存放位置下标的公式。【东北大学 2003 一、3(5 分)】（分数：2.00）_23.设稀疏矩阵 M m 中有 f 个非零元素，用三元组顺序表的方式存储。请设计一个算法，计算矩阵 M 的转置矩阵 N，要求转置算法的时间复杂度为 O(n+t)。【苏州大学 2005 四(20 分)】【中南大学 2004 三、4(10 分)】【兰州大学 2002 八(10 分)】（分数：2.00）_24.已知一个 nn 的上三角矩阵口的上三角元素已按行主序连续存放在数组 b 中，请设计一个函数 trans将 b
12、 中元素按列主序连续存放至数组 c 中。例：设 n=5 （分数：2.00）_25.试写出算法(C 函数或 C 程序)：输入 m 行 n 列整数矩阵 a，若存在 4 个相邻的元素相同，即有 aij=aij+1=ai+1j=ai+1j+1 (1iright=rch 时该行无非零元素，用 i 记行号，用一维数组元素 Ai记第 i 行非零元素个数。当 rch=Hm 时各行非零元素计算完毕。核心语句段如下： while(rch!=Hm) 初值 rch=Hm 一uvalnex，循环完各行列表头 p：rch 一right ; num=0； P 是稀疏矩阵行内工作指针，num 记该行非零个数 while(p!
13、=rch) 完成行内非零元素的查找 printf(“Mdd=d”，p 一row，p一col，p 一uval.e)； num+；p=P 一right；printf Cn”)；指针后移 Ai+=num； 数组 A 记各行非零元个数，i 记行号 rch=rch 一uvalnext； 移到下一行列表头 )解析：17.试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入：(a 1 ，a 2 ，a 3 ，a n )，n0，其中 a t 或为单字母表示的原子或为广义表，n=0 时为只含空格字符的空表。【北京工业大学 1998 十(15 分)】（分数：2.00）_正确答
14、案：(正确答案：广义表可以看作是扩充的线性表：其元素是原子或表。在读入广义表“表达式”时，遇到左括号(就递归地构造子表；否则，若是原子，就建立原子结点；若读入逗号，就递归 构造后续子表；直到碰到输入结束符号()。设广义表的形式定义如下： typedef struct node int tag； tag=0 为原子，tag=l 为子表 struct node*link； 指向后继结点的指针 union f struct node*slink； 指向子表的指针 char data； 原子 element； Glist； 算法核心语句段如下： cinch； if(ch=)gh=null； elseg
15、h=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 时为只含空格字符的空表一叙述有误。n=0 表示广义表是空表。 空表长度为 0，不含任何元素，而不是“只含空格字符的空表”。)解析：数组研 1：1000 中存放着 1000 个大小不同的正整数。（分数
16、：4.00）(1).选择一分类算法使能最快地得到其中 10 个最大的数，简要说明理由；（分数：2.00）_正确答案：(正确答案：在 n 个正整数中，选出 k(km)(printf(“参数错误n”)；exit(0)；)m=1000 是要求数 for(i=0；ir i； 输入 1000 个大小不同的正整数 if(augv1“a“) 输出 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个最小数)解析：1
17、8.已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入前一个数组序列中，完成后两个数组中的数分别有序(非降序)并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。例如，第一个数组为：4，12，28 第二个数组为：1，7，9，29，45 输出结果为：1，4，7一第一个数组9，12，28，29，45-一第二个数组【上海大学 1998 四(20 分)】（分数：2.00）_正确答案：(正确答案：设两个数组分别是 A 和 B，各有 m 和 n 个元素。结果要求第一个数组的最后一个数 Am 一 1不大于第二
18、个数组的第一个数 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 的插入位置，并插入 )解析：19.设数组 A1N中，An 一 2k+1,n 一 k和 An 一 k+1.n中元素各自从小到大排好序，试设计一个算法使 An 一 2k+1n按从小到大次序排好序
19、。并分析算法所需的计算时间。【福州大学 1998 四、3(10 分)】（分数：2.00）_正确答案：(正确答案：数组 A 的相邻两段分别有序，要求将两段合并为一段有序。由于要求附加空间为O(1)，所以将两段最后一个元素比较，若正序，则后段指针前移；若逆序则交换，并调整前段有序。重复以上过程直到正序为止。最佳情况出现在数组第二段值最小元素 An 一 k+1大于等于第一段值最大元素An 一 k，只比较 k 次无须交换，时间复杂度为 O(n)。最差情况出现在第一段的最小值大干第二段的最大值，两段数据间发生了 k 次交换，而且每次段交换都在段内发生了平均(k-1)次交换，时间复杂度为O(n 2 )。)
20、解析：20.设 A1100是一个记录构成的数组，B1100是一个整数数组，其值介于 1100 之间，现要求按 B1100的内容调整 A 中记录的次序，比如当 B1=11 时，则要求将 A1的内容调整到 A11中去。规定可使用的附加空间为 O(1)。【中科院计算所 2000 七(15 分)】（分数：2.00）_正确答案：(正确答案：题目要求按 B 数组内容调整 A 数组中记录的次序，可以从 i=1 开始，检查是否Bi=i。如是，则 Ai恰为正确位置，不需再调；否则，Biki，则将 Ai和 Ak对调，Bi和 BK对调，直到 Bi=i 为止。核心语句段如下： while(i解析：21.给定有 m 个
21、整数的递增有序数组 a1m和有 n 个整数的递减有序数组 b1n，试写出算法：将数组 a 和 b 归并为递增有序数组 c1 一m+n。(要求：算法的时间复杂度为 O(m+n)。)【华中理工大学2000 八、1(10 分)】（分数：2.00）_正确答案：(正确答案：数组 A 和 B 的元素分别有序，欲将两数组合并到 C 数组，使 C 仍有序，应将 A 和B 复制到 C，只要注意 A 和 B 数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到 C 中即可。核心语句段如下： i=0； j=n1 ； k=0；i，j，k 分别是数组 A，B 和 C 的下标，下标从 0 开始 while
22、(i=0) if(ai=0)ck+=bj 一一； 若不允许另辟空间，结果在 A 数组(空间足够大)，则初始 k=m+n 一 1，请参见第 2 章算法设计题第 18 题。)解析：22.设 A 和 B 均为下三角矩阵，每一个都有 n 行 n 列。因此在下三角区域中各有 n(n+1)2 个元素。另设有一个二维数组 C，它有 n 行 n+1 列。试设计一个方案，将两个矩阵 A 和 B 中的下三角区域元素存放于同一个 C 中。要求将 A 的下三角区域中的元素存放于 C 的下三角区域中，B 的下三角区域中的元素转置后存放于 C 的上三角区域中。并给出计算 A 的矩阵元素 a ij 和 B 的矩阵元素 b
23、ij 在 C 中的存放位置下标的公式。【东北大学 2003 一、3(5 分)】（分数：2.00）_正确答案：(正确答案：将，z 阶方阵的下三角 A 复制到 C，B 逆置后复制到 C。核心语句段如下： for(i=0 ； i ij 和 B 的矩阵元素 bij在 C 中的存放位置下标的公式： Aij=Cij； 0i)解析：23.设稀疏矩阵 M m 中有 f 个非零元素，用三元组顺序表的方式存储。请设计一个算法，计算矩阵 M 的转置矩阵 N，要求转置算法的时间复杂度为 O(n+t)。【苏州大学 2005 四(20 分)】【中南大学 2004 三、4(10 分)】【兰州大学 2002 八(10 分)】
24、（分数：2.00）_正确答案：(正确答案：转置可按转置矩阵的三元组表中的元素顺序进行，即按稀疏矩阵的列序。这种方法时间复杂度是 O(n*t)，当 t 和 m*n 同量级时，时间复杂度为 O(n 2 )。另一种转置方法称作快速转置，使时间复杂度降为 O(m*n)。需要求出每列非零元素个数和每列第一个非零元素在转置矩阵三元组表中的位置，因此设置了两个附加向量。快速转置的核心语句段如下： Nm=M.n； Nn=Mm； Nlen=M1en； if(Mlen) (for(j：1 ； j=Mn；j+)numbj=0； 矩阵 M 每一列非零元素初始化为零 for(t=1；t=Mlen；t+)numbMdat
25、atcol+； 求矩阵 M 每一列的非零元素个数pos1=1； 第 1 列第一个非零元素在转置后的三元组中下标是 1 for(j=2；J=Mn；j+) 求Mdata 第 J 列第一个非零元素在 Ndata 中的序号 posc01=poscol 一 1+numbcol 一 1; for(p=1；p=M1en;p+) 求转置矩阵 N 的三元组表 J=Mdatapcol；q=posj； Ndataqrow=Mdatapcol；Ndataqcol=Mdataprow； Ndataqe=Mdatape；posj+； 同列下一非零元素位置 )解析：24.已知一个 nn 的上三角矩阵口的上三角元素已按行主序
26、连续存放在数组 b 中，请设计一个函数 trans将 b 中元素按列主序连续存放至数组 c 中。例：设 n=5 （分数：2.00）_正确答案：(正确答案：nn 的上三角矩阵以行序为主存储在一维数组 b 中，其位置 kl 和元素在矩阵中的下标 i 和 j 有确定关系：kl=(i 木(2n 一 i+3)2+(广 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
27、+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; )解析：25.试写出算法(C 函数或 C 程序)：输入 m 行 n 列整数矩阵 a，若存在 4 个相邻的元素相同，即有 aij=aij+1=ai+1j=ai+1j+1 (1im，1jn)则输出信息“True”，aij的值和这四个元素的下标值(找出一组同值元素即可)；否则输出信息“False”。分析算法的时间复杂度。【华中科技大学2006 五、1(15 分)】（分数：2.00）_正确答案：(正确答案：将矩阵的行列下标平移，设矩阵行 0m 一 1，列 0n 一 1。把首尾行(0 和 m一 1)、列(0 和 n 一 1)看做相邻，则核心语句段如下： for(i=0，i“False”：)解析：
