内容发布更新时间 : 2024/5/14 5:02:30星期一 下面是文章的全部内容请认真阅读。

计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇

编4

(总分：60.00，做题时间：90分钟)

一、 综合题(总题数：13，分数：26.00)

1.简述广义表属于线性结构的理由。 【西北大学2000一、5(3分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：广义表是元素为原子或子表的有限序列，满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一个元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构，只是元素可以是原子，也可以是子表。) 解析：

2.数组、广义表与线性表之间有什么样的关系?【西北工业大学1998一、2(4分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：数组是具有相同性质的数据元素的集合，同时每个元素又由唯一下标限定，可以说数组是值和下标偶对的有限集合。n维数组中的每个元素，处于n个关系之中，每个关系都是线性的，且n维数组可以看作其元素是n一1维数组的一个线性表。而广义表与线性表的关系，见上面21题的解释。) 解析：

3.什么是广义表?请简述广义表和线性表的主要区别。【北京大学1997二、2(5分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：线性表中的元素可以是各种各样的，但必须具有相同性质，属于同一数据对象。广义表中的元素可以是原子，也可以是子表。其他请参见21题。) 解析：

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(CDR(((a，b)，(e，f))))(5)CDR(CDR(CAR(((a，b)，(e，f))))注：CAR运算相当于有些教材中的Head运算，CDR运算相当于Tail运算。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：(1) (c，d) (2)(6) (3)6 (4)(f) (5)()) 解析：

5.画出下列广义表的存储结构图，并利用取表头和取表尾的操作分离出原子e。(a，(0，b)，(((e)))【清华大学1995二(10分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：head(head(head(head(tail(tail(L))))))解析：

6.画出下列广义表的两种存储结构图(0，A，B，(C，D)，(E,F)。【南京航空航天大学1999三(10分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：广义表的第一种存储结构的理论基础是，非空广义表可唯一分解成表头和表尾两部分，而由表头和表尾可唯一构成一个广义表。这种存储结构中，原子和表采用不同的结点结构(“异构”，

) 即结点域个数不同)。原子结点两个域：标志域tag=0表示原子结点，域DATA表示原子的值；子表结点三个域：tag=1表示子表，hp和tp分别是指向表头和表尾的指针。在画存储结构时，对非空广义表不断进行表头和表尾的分解，表头可以是原子，也可以是子表，而表尾一定是表(包括空表)。下面是本题的第一种存储结构图。广义表的第二种存储结构的理论基础是，非空广义表最高层元素间具有逻辑关系：第一个元素无前驱有后继，最后一个元素无后继有前驱，其余元素有唯一前驱和唯一后继。有人将这种结构看作扩充线性结构。这种存储结构中，原子和表均采用三个域的结点结构(“同构”)。结点中都有一个指针域指向后继结点。原子结点中还包括标志域tag=0和原子值域DATA；子表结点还包括标志域tag=1和指向子表的指针hp。在画存储结构时，从左往右一个元素一个元素地画，直至最后一个元素。下面是本题的第二种存储结构图。解析：

7.知广义表A=(((a))，(b)，c，(a)，(((d,e))))(1)画出其一种存储结构图；(2)写出表的长度与深度；(3)用求头部、尾部的方式求出e。【东北大学1997一、2(5分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：表的长度为5，深度为

4(3)head(tail(laead(head(1aead(tail(tail(tail(tail(A)))))))))) 解析：

8.画出具有共享结构广义表(((b，c)，d，(a)，((a)，((b，c)，d)，e，0)的存储表示。【北京工业大学1996一、3(6分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：共享结构广义表A=(((b，c)，d)，(a)，((a)，((b，c)，d))，e，())的存储表示：

) 解析：

9.已知下图为广义表的存储结构图，写出该图表示的广义表，并求该广义表的长度和深度。【中国海洋大学2007一、1(8分)】（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：广义表的第一种存储结构：LIST=(C墨(X)(Y)，(()，()，(Z)))；广义表长度2，深度3。) 解析：

10.已知下图为广义表的头尾链表存储结构图，请给出该图表示的广义表。【北京理工大学2005三、1(4分)】 ) （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：LIST=(()，(a，(b，c)))) 解析：

11.给出下列所示的三元多项式的广义表表示(分别以X 1 ，X 2 ，X 3 第一到第三层变元。)P(X 1 X 2 X 3 )=X

1

X 2 X 3 +2X 1 X 2 X 3 +5X 1 X 2 X 3 +3X 1 X 2 X 3 +X 2 X 3 +6【华南理工大学2001一、2(4

5353342

分)】

（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：P(X 1 X 2 X 3 )=2X 1 X 2 X 3 +5X 1 X 2 X 3 +3X 1 X 2 X 3 +(X 1 +X )+X 3 +6 3

5

2

4

5

3

3

4

2

5

2

) 解析：

12.设某表H如下： 其中A，B，C为子表名，a 1 ，a 2 ，b 1 ，c 1 ，c 2 ，x为其元素。 (1)试用

广义表形式表示H，并写出运算HEAD㈣和TAIL㈣函数从日中取出单元素a2的运算； (2)画出表H的链式存储结构。【北京科技大学1998三(10分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：(1)H(A(a 1 ，a 2 )，B(b 1 )，C(c 1 ，c 2 ,x)，HEAD(TAlL(HEAD(H)))=a 2) 解析：

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(30／7分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：唯一对应一棵二又树的有(2)、(3)和(5)。唯一对应的条件：空表，或只有一个元素的表，或每个子表个数是零或是2的表。) 解析：

二、 设计题(总题数：14，分数：34.00)

二项式(a+b) 展开式的系数为C(n，0)=1，C(n，n)=1，对于n≥0;C(n，k)=C(n一1，k)+C(n一1，k-1)，对于0 （分数：6.00）

(1).试写一个递归算法，根据以上公式生成C(n，k)。(6分)（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：int BiForm(int n，int k) ／／二项式展开式的系数的递归算法 (if(n<0｜｜k=n){cout<<“参数错误”< 解析：

(2).试画出计算C(6，4)的递归树。(4分)（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：c(6，4)的递归树：解析：

(3).试写一个非递归算法，既不用数组也不用栈，对于任意的0≤k≤n计算C(n，k)。(6分)【清华大学1999五(16分)】（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：计算C(n，k)(0≤k≤n)的非递归算法： int cnk(int n，int k) {int i； long x=1，y=1； for(i=1 ； i<=k；i++) x*=i； for(i=n—k+1；i<=n；i++) y*=i； return(y／x) }／／cnk) 解析：

14.设计将数组A[n]中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为O(n)。【 哈尔滨工业大学2002十(8分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：在数组首尾设两个指针i和j，i自小至大搜索到奇数停止，j自大至小搜索到偶数停止。然 后f和／所指数据交换，继续以上过程，直到坷为止。 while(i

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

) n

五(15分)1997五(15分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：设n个元素存放在数组A[1..n]中。设S初始为空集，可依次将数组A的每一个元素并入S，产生了含一个元素的若干集合，再以含一个元素的集合为初始集合，依次将A的第二个元素并入S，形成了含两个元素的若干集合，如此下去，直至A[i]的全部元素并入。 void powerset(set S，int num) {outset(s)；／／输出集合S for(int i=num+1；i<=n，i++) powerset(S+[A[i\\]\\]，i)； }／／调用本函数时，参数S为空集[]，num为0) 解析：

16.编写算法打印出由指针Hm指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意：行、列及总表头结点的形式为：表的表头。【上海大学1998五(16分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：本题实质是循环链表的计数问题，重点是掌握十字链表的结点结构，设rch是行列表头指针，则rch一>right==rch时该行无非零元素，用i记行号，用一维数组元素A[i]记第i行非零元素个数。当rch=Hm时各行非零元素计算完毕。核心语句段如下： while(rch!=Hm) ／／初值rch=Hm一>uval．nex，循环完各行列表头 {p：rch一>right ; num=0； ／／P是稀疏矩阵行内工作指针，num记该行非零个数 while(p!=rch) ／／完成行内非零元素的查找 {printf(“M[％d][％d]=％d”，p一>row，p一>col，p一>uval.e)； num++；p=P一>right；printf C＼n”)；／／指针后移 } A[i++]=num； ／／数组A记各行非零元个数，i记行号 rch=rch一>uval．next； ／／移到下一行列表头 }) 解析：

17.试编写建立广义表存储结构的算法，要求在输入广义表的同时实现判断、建立。设广义表按如下形式输入：(a 1 ，a 2 ，a 3 ，…，a n )，n≥0，其中a t 或为单字母表示的原子或为广义表，n=0时为只含空格字符的空表。【北京工业大学1998十(15分)】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：广义表可以看作是扩充的线性表：其元素是原子或表。在读入广义表“表达式”时，遇到左括号‘(’就递归地构造子表；否则，若是原子，就建立原子结点；若读入逗号‘，’，就递归 构造后续子表；直到碰到输入结束符号(‘≠}’)。设广义表的形式定义如下： typedef struct node {int tag； ／／tag=0为原子，tag=l为子表 struct node*link； ／／指向后继结点的指针 union f struct node*slink； ／／指向子表的指针 char data； ／／原子 }element； }Glist； 算法核心语句段如下： cin>>ch； if(ch==…)gh=null； else{gh=new(Glist)； if(ch==\一>tag=l； ／／子表 gh

一>element.slink=creat()；} ／／递归构造子表 else(gh一>tag=0；gh一>element．data=ch；} ／／原子结点 } cin>>ch； if(gh!=null) if(ch==\一>link=creat()； ／／递归构造后续广义表 else gh->link=null； 需要指出，题中“n=0时为只含空格字符的空表一叙述有误。n=0表示广义表是空表。 空表长度为0，不含任何元素，而不是“只含空格字符的空表”。) 解析：

数组研1：1000中存放着1000个大小不同的正整数。（分数：4.00）

(1).选择一分类算法使能最快地得到其中10个最大的数，简要说明理由；（分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：在n个正整数中，选出k(k<

(2).编写一程序seek()，执行该程序时，在命令行中提供两个参数。seek a n表示需打印H[]中n个最大数。seek i n表示需打印H[]中n个最小数。【浙江大学1994八(1 8分)】（分数：2.00）

它们已用val域链接成循环链表。非零元的结点形式也同上，

每一行(列)的非零元由right(down)域把它们链接成循环链表，该行(列)的表头结点即为该行(列)循环链