1、计算机专业基础综合数据结构（线性表）历年真题试卷汇编 2 及答案解析(总分：98.00，做题时间：90 分钟)一、综合题(总题数：12，分数：24.00)1.线性表的顺序存储结构具有三个弱点：第一，在作插入或删除操作时，需要移动大量元素；第二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；第三，表的容量难以扩充。试问，线性表的链式存储结构是否一定能够克服上述三个弱点?请简述之。【北京师范大学 2003 二、4(6 分)】（分数：2.00）_2.线性结构包括_、_、_和_。线性表的存储结构分成_和_。【华北计算机系统工程研究所 1999 一、2(10 分)】（分数：2.0
2、0）_3.线性表(a 1 ，a 2 ，a n )用顺序映射表示时，a i 和 a i+1 (1in n )的物理位置相邻吗?链接表示时呢?【东南大学 1996 一、1(5 分)】（分数：2.00）_4.设 LS 是一个线性表，LS=(a 1 ，a 2 ，a n )，若采用顺序存储结构，则在等概率的前提下，插入一个元素需要平均移动的元素个数是多少?若元素插在 a i 与 a i+1 之间(0in 一 1)的概率为(n 一 i)n * (n+1)2)，则插入一个元素需要平均移动的元素个数又是多少?【西安电子科技大学 2001 软件二、3(5 分)】（分数：2.00）_5.说明在线性表的链式存储结构
3、中，头结点与首元结点的关系。 【厦门大学 2000 五、1(143 分)】（分数：2.00）_6.在单链表和双向链表中，能否从当前结点出发访问到任何一个结点? 【西安电子科技大学 1999 计算机应用一、1(5 分)】（分数：2.00）_7.如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表? 【中国人民大学2001 二、4(2 分)】（分数：2.00）_8.设双向循环链表中结点的数据域、前驱和后继指针域分别为 data、pre 和 next，试写出在指针 P 所指结点之前插入一 S 结点的 C 语言描述语句。【北京科技大学 2001 一、3(2 分)】（分数：2.00）_
4、9.现有一无表头结点的单链表 L，p、q、r 为 Lnode 类型的指针。请阅读下列算法并给出算法的功能描述：aa(Lnode *L) p=L；q=NULL； while(P!=NULL) r=p 一next；p 一next=q；q=p；p=r；) L=q； 【北京理工大学 2006 六、7(507 分)】（分数：2.00）_10.请简要说明下列函数的主要功能。 void func(LinkList L1，LinkList L2) LNode*p， *q， *r； q=L2 一next； while(q) P*L1； while(p 一next) if(p 一next-data=q 一data
5、) (r=P 一next；P 一next=r 一next；free(r)； P=P 一next； q=q 一next； return； 【北京理工大学2006 十一、2(5 分)】（分数：2.00）_11.阅读下面的算法，说明算法实现的功能。 node*1ink(node *headl， *head2) node*p， *q; p=headl； while(p 一next!=headl)p=p 一next; q=head2； while(q 一next!=head2) q=q 一next； P 一next=head2； q 一next=headl； return(headl)； 【东华大学 2
6、004 二、1(10 分)】（分数：2.00）_12.线性表的双向链表的存储结构为： Typedef struct DNode TElem info； structDNode*left； struct DNode*right； ；并假设己建立头指针为 head 的双向链表，p 指向其中某个结点，写一个程序段，从该循环链表中删除 p 所指向结点的前一个结点(假设该结点存在)。【华南理工大学 2005 二、1(4分)】（分数：2.00）_二、设计题(总题数：37，分数：74.00)13.已知一个带有表头结点的单链表，结点结构为(data，link)，假设该链表只给出了头指针 list。在不改变链表
7、的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点(k 为正整数)，若查找成功，算法输出该结点的 data 域的值，并返回 1；否则，只返回 0，要求：(1)描述算法的基本设计思想；(2)描述算法的详细实现步骤；(3)根据设计思想和实现步骤，采用程序设计语言描述算法(使用C 或 C+或 Java 语言实现)，关键之处请给出简要注释。【2009 年全国试题 42(15 分)】（分数：2.00）_14.设将 n(n1)个整数存放到一维数组 R 中。试设计一个在时间和空间两方面都尽可能高效的算法，将 R中保存的序列循环左移 P(00 0，X 1，X n-1)变换为(X P2，
8、X P+1，X n-1，X 0，X 1，X P-1)。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。 【2010 年全国试题 42(13 分)】（分数：2.00）_15.一个长度为 L(L1)的升序序列 S，处在第L2个位置的数称为 S 的中位数。例如列S1=(11，13，15，17，19)，则 S1 中的中位数是 15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 92=(2，4，6，8，20)，则S1 和 S2 的中位数是 11。现有两个等长升序序
9、列 A 和 B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度【2011 年全国试题 42(15)分】（分数：2.00）_16.假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如下图所示。 设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 （分数：2.00）_17.用单链表保
10、存 m 个整数，结点的结构为(data，link)，且data 要求： (1)给出算法的基本思想。 (2)使用 C 或 C+语言，给出单链表结点的数据类型定义。 (3)根据设计思想，采用 C 或 C+语言描述算法，关键之处给出注释。 (4)说明所涉及算法的时间复杂度和空间复杂度。（分数：2.00）_18.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学 1998 三、1(5 分)】【厦门大学 2006 1(3)(203 分)】（分数：2.00）_19.已知 L
11、1、L2 分别为两循环单链表的头结点指针，m、n 分别为 L1、L2 表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。【东北大学 1996 二(12 分)】（分数：2.00）_20.设有两个链表，ha 为单向链表，hb 为单向循环链表。编写算法，将两个链表合并成一个单向链表，要求算法所需时间与链表长度无关。【南京航空航天大学 1997 四(8 分)】（分数：2.00）_21.已知三个带头结点的线性链表 A、B 和 C 中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点)，编写算法对 A 表进行如下操作：使操作后的链表 A 中仅留下三个表中均包含
12、的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为 O(m+n+p)，其中 m、n 和p 分别为三个表的长度。【清华大学 1995 一(15 分)】（分数：2.00）_22.顺序结构线性表 LA 与 LB 的结点关键字为整数。LA 与 LB 的元素按非递减有序，线性表空间足够大。试用类 Pascal 语言给出一种高效算法，将 LB 中元素合并到 LA 中，使新 LA 的元素仍保持非递减有序。高效指最大限度地避免移动元素。【北京工业大学 1997 一、2(12 分)】（分数：2.00）_23.已知长度为 n 的线性表 A 采用顺序存储结构，请写一时间复杂度为 O(n
13、)、空间复杂度为 O(1)的算法，该算法删除线性表中所有值为 item 的数据元素。(O(1)表示算法的辅助空间为常量)。【北京航空航天大学 2000 五(10 分)】【天津大学 2005 八(10 分)】（分数：2.00）_24.已知消费总金额，请设计一个发票打印程序，打印输出的发票金额单位为：千百十元。【南京航空航天大学 2004 三、3(8 分)】（分数：2.00）_25.写算法将单链表 L1 拆成两个链表，其中以 L1 为头的链表保持原来向后的链接，另一个链表的头为L2，其链接方向与 L1 相反，L1 包含原链表的奇数序号的结点，L2 包含原链表的偶数序号的结点。【东华大学 2004
14、三(10 分)】（分数：2.00）_26.试编写在带头结点的单链表中删除(一个)最小值结点的(高效)算法 void delete(LinklistL)。【北京理工大学 2001 九、3(8 分)】（分数：2.00）_27.用类 CC+设计算法，判断一个带表头结点的双向循环链表 DL(DuIJnkList)是否对称相等。 (比如，表(25，34，34，25)和表(25，3，25)为对称的。)【南京理工大学 2005 三(5 分)】其中结点结构为：struct NodeE1emType data； ElemType 代表某种抽象数据类型 Node*Llink， *R1ink；（分数：2.00）_2
15、8.已知两个单链表 A 和 B，其头指针分别为 heada 和 headb，编写一个过程从单链表 A 中删除自第 i 个元素起的共 len 个元素，然后将单链表 A 插入单链表 B 的第 j 个元素之前。【中国矿业大学 2000 三(10 分)】（分数：2.00）_29.假设一个单循环链表，其结点含有三个域 pre、data、link。其中 data 为数据域；pre 为指针域，它的值为空指针(NIL)；link 为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。 【西安电子科技大学 1999 软件五(10 分)】（分数：2.00）_30.已知一个单链表中每个结点存放一个整数，并且
16、结点数不少于 2，请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回 ture，否则返回 false。 【西安电子科技大学 2000 软件二(10 分)】（分数：2.00）_31.两个整数序列 A=a1，a2，a3，am 和 B=b1，b2，b3，bn 已经存入两个单链表中，设计一个算法，判断序列 B 是否是序列 A 的子序列。【东北大学 1999 二(10 分)】（分数：2.00）_32.L1 与 L2 分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个字母。设计把 L1 中与L2 中数据相同的连续结点顺序完全倒置的算法。【东北大学 19
17、97 四(15 分)】例： （分数：2.00）_33.已知 L 为链表的头结点地址，表中共有 m(m3)个结点，从表中第 i 个结点(1im)起到第 m 个结点构成一个循环部分链表，设计将这部分循环链表中所有结点顺序完全倒置的算法。【东北大学 1998 三(15分)】 （分数：2.00）_34.请写一个算法将顺序存储结构的线性表(a 1 a n )逆置为(a n a 1 )。【大连海事大学 1996 八(6分)】（分数：2.00）_35.写出一个从表尾到表头的逆向建立单链表的算法。【中科院研究生院 2004 三(7 分)】（分数：2.00）_36.已知一带头结点的递增有序单链表，请在原结点上将
18、其倒序。【南京航空航天大学 2004 二、4(12 分)】（分数：2.00）_37.试编写求倒排循环链表元素的算法。【南京航空航天大学 1995 十二(10 分)】（分数：2.00）_38.已知 p 是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表(a 1 ，a 2 ，a n-1 ，a n )改造为(a 1 ，a 2 ，a n-1 ，a n ，a n-1 ，a 2 ，a 1 )。【北京理工大学2005 十四、1(5 分)】（分数：2.00）_39.编写逆向输出不带头结点的单向链表中数据域的递归算法。设表中有 4 个结点，从表头至表尾其数据域分别为 10，30，20，4
19、0，作图表示出该算法的执行过程。设该链表的结点的数据类型的名称为 list，结点的数据域和指针域的名称分别为 data 和 next，不必写出 list 的定义。【中南大学 2005 四、3(10 分)】（分数：2.00）_40.在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：(7，10，10，21，30，42，42，42，51，70)将变作(7，10，21，30，42，51，70)，分析算法的时间复杂度。【北京工业大学 1996 三(15 分)】（分数：2.00）_41.已知带头结点的单链表有 data 和 nex
20、t 两个域，设计一个算法，将该链表中的重复元素结点删除。【北京邮电大学 2005 五、2(10 分)】【苏州大学 2005 三(15 分)】（分数：2.00）_42.设有一个正整数序列组成的有序单链表(按递增次序有序，且允许有相等的整数存在)，试编写能实现下列功能的算法：(要求用最少的时间和最小的空间。)(1)确定在序列中比正整数 x 大的数有几个(相同的数只计算一次，如序列20，20，17，16，15，15，11，10，8，7，7，5，4中比 10 大的数有 5 个)；(2)在单链表中将比正整数 x 小的数按递减次序排列；(3)将正整数(比)x 大的偶数从单链表中删除。【东北大学 2001
21、二(17 分)】（分数：2.00）_43.编写一个算法来交换单链表中指针尸所指结点与其后继结点，HEAD 是该链表的头指针，P 指向该链表中某一结点。【吉林大学 2001 二、1(7 分)】（分数：2.00）_44.设键盘输入 n 个英语单词，输入格式为 n，w 1 ，w 2 ，w n ，其中 n 表示随后输入英语单词的个数，试编一程序，建立一个单向链表，实现：(1)如果单词重复出现，则只在链表上保留一个(单考生做)。(2)除满足(1)的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前 k(kn)个单词(统考生做)。【南京航空航天大学 1998 九(10 分
22、)】（分数：2.00）_45.已知一双向循环链表，从第二个结点至表尾递增有序(设 a 1 xa n )(x 是第一个结点的值， “第二个结点至表尾”指 a 1 a n ，因篇幅所限，编者略去图)。试编写程序，将第一个结点删除并插入表中适当位置，使整个链表递增有序。【南京航空航天大学 1998 八(10 分)】（分数：2.00）_46.设民航公司有一个自动预订飞机票的系统，该系统中有一张用双重链表示的乘客表，表中结点按乘客姓氏的字母序相链接。例如，下面是张某个时刻的乘客表。试为该系统写出一个当任一乘客要订票时修改乘客表的算法。【北方交通大学 2000 六(17 分)】 （分数：2.00）_47.
23、设有一头指针为 L 的带有表头结点的非循环双向链表，其每个结点中除有 pred(前驱指针)、data(数据)和 next(后继指针)域外，还有一个访问频度域 freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次 Locate(L，x)运算时，令元素值为 x 的结点中 freq 域的值增 1，并使此链表中结点保持按访问频度非增(递减)的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的 Locate(L，x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。【清华大学 1997 二(10 分)】【苏州大学 200
24、4 四(15 分)】【江苏大学 2006 四、2(13 分)】（分数：2.00）_48.给定(已生成)一个带表头结点的单链表，设 head 为头指针，结点的结构为(dam，next)，dam 为整型元素，next 为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。(要求：不允许使用数组作辅助空间。)【华中理工大学 2000 八、2(13 分)】（分数：2.00）_49.编写程序，要求完成：(1)建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的 data 域存放一个二进制位。(2)在此链表上实现对二进制数加 1 的运算，并输出运算结果。【西
25、北大学2002 七(10 分)】（分数：2.00）_计算机专业基础综合数据结构（线性表）历年真题试卷汇编 2 答案解析(总分：98.00，做题时间：90 分钟)一、综合题(总题数：12，分数：24.00)1.线性表的顺序存储结构具有三个弱点：第一，在作插入或删除操作时，需要移动大量元素；第二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；第三，表的容量难以扩充。试问，线性表的链式存储结构是否一定能够克服上述三个弱点?请简述之。【北京师范大学 2003 二、4(6 分)】（分数：2.00）_正确答案：(正确答案：一般说链式存储结构克服了顺序存储结构的三个弱点。首先，插入、
26、删除不需移动元素，只修改指针，时间复杂度为 O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储结构的缺点。)解析：2.线性结构包括_、_、_和_。线性表的存储结构分成_和_。【华北计算机系统工程研究所 1999 一、2(10 分)】（分数：2.00）_正确答案：(正确答案：线性表、栈、队列、串；顺序存储结构、链式存储结构。)解析：3.线性表(a 1 ，a 2 ，a n )用顺序映射表示时，a i 和 a i+1 (1in n )的物理位置相邻吗?链接表示时呢?【东南大学 1996 一
27、、1(5 分)】（分数：2.00）_正确答案：(正确答案：顺序映射时，a i 与 a i+1 的物理位置相邻；链表表示时，a i 与 a i+1 的物理位置不要求相邻。)解析：4.设 LS 是一个线性表，LS=(a 1 ，a 2 ，a n )，若采用顺序存储结构，则在等概率的前提下，插入一个元素需要平均移动的元素个数是多少?若元素插在 a i 与 a i+1 之间(0in 一 1)的概率为(n 一 i)n * (n+1)2)，则插入一个元素需要平均移动的元素个数又是多少?【西安电子科技大学 2001 软件二、3(5 分)】（分数：2.00）_正确答案：(正确答案：等概率(后插)时，插入位置 0
28、n，则平均移动元素个数为 n2。若不等概率，则平均移动的元素个数为 )解析：5.说明在线性表的链式存储结构中，头结点与首元结点的关系。 【厦门大学 2000 五、1(143 分)】（分数：2.00）_正确答案：(正确答案：首元结点也就是第一元素结点，它是头结点后边的第一个结点。)解析：6.在单链表和双向链表中，能否从当前结点出发访问到任何一个结点? 【西安电子科技大学 1999 计算机应用一、1(5 分)】（分数：2.00）_正确答案：(正确答案：在单链表中不能从当前结点(若当前结点不是第一结点)出发访问到任何一个结点。因为链表运算只能从头指针开始，访问到链表中每个结点。在双链表中从当前结点反
29、向可以到第一结点，正向可以到最后结点，因而从当前结点出发可以访问到链表中任何一个结点。)解析：7.如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表? 【中国人民大学2001 二、4(2 分)】（分数：2.00）_正确答案：(正确答案：设该链表带头结点，将头结点摘下，并将其指针域置空。然后从第一元素结点开始，直到最后一个结点为止，依次前插入头结点的后面，实现了链表的逆置，即将单向链表变成一个与原来链接方向相反的单向链表。)解析：8.设双向循环链表中结点的数据域、前驱和后继指针域分别为 data、pre 和 next，试写出在指针 P 所指结点之前插入一 S 结点的 C 语言
30、描述语句。【北京科技大学 2001 一、3(2 分)】（分数：2.00）_正确答案：(正确答案：在指针 p 所指结点前插入结点 s 的语句如下：s 一pre=p 一pre； s 一next=p； p 一pre 一next=s； p 一pre=s；)解析：9.现有一无表头结点的单链表 L，p、q、r 为 Lnode 类型的指针。请阅读下列算法并给出算法的功能描述：aa(Lnode *L) p=L；q=NULL； while(P!=NULL) r=p 一next；p 一next=q；q=p；p=r；) L=q； 【北京理工大学 2006 六、7(507 分)】（分数：2.00）_正确答案：(正确答
31、案：算法的功能是将无表头结点的单链表 L 逆置。)解析：10.请简要说明下列函数的主要功能。 void func(LinkList L1，LinkList L2) LNode*p， *q， *r； q=L2 一next； while(q) P*L1； while(p 一next) if(p 一next-data=q 一data) (r=P 一next；P 一next=r 一next；free(r)； P=P 一next； q=q 一next； return； 【北京理工大学2006 十一、2(5 分)】（分数：2.00）_正确答案：(正确答案：算法实现集合的差运算 C=A-B。将链表 L2 中的元素依次到链表 L1 中查找，有则从 L1 中删除。)解析：11.阅读下面的算法，说明算法实现的功能。 node*1ink(node *headl， *head2) node*p， *q; p=headl； while(p 一next!=headl)p=p 一next; q=head2； while(q 一next!=head2) q=q 一next； P 一next=head2； q 一next=headl； return(headl)； 【东华大学 20
