1、计算机专业基础综合数据结构（线性表）历年真题试卷汇编 5 及答案与解析一、综合题1 线性表的顺序存储结构具有三个弱点：第一，在作插入或删除操作时，需要移动大量元素；第二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；第三，表的容量难以扩充。试问，线性表的链式存储结构是否一定能够克服上述三个弱点? 请简述之。 【北京师范大学 2003 二、4(6 分)】2 线性结构包括_、_、_和_。线性表的存储结构分成_和_。【华北计算机系统工程研究所 1999 一、2(10 分 )】3 线性表(a 1，a 2，a n)用顺序映射表示时，a i 和 ai+1(1inn)的物理位置相邻吗
2、? 链接表示时呢? 【东南大学 1996 一、1(5 分) 】4 设 LS 是一个线性表，LS=(a 1，a 2，a n)，若采用顺序存储结构，则在等概率的前提下，插入一个元素需要平均移动的元素个数是多少?若元素插在 ai 与 ai+1 之间(0in 一 1)的概率为(n 一 i)n *(n+1)2)，则插入一个元素需要平均移动的元素个数又是多少? 【西安电子科技大学 2001 软件二、3(5 分)】5 说明在线性表的链式存储结构中，头结点与首元结点的关系。 【厦门大学 2000五、1(14 3 分) 】6 在单链表和双向链表中，能否从当前结点出发访问到任何一个结点? 【西安电子科技大学 19
3、99 计算机应用一、1(5 分)】7 如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表?【中国人民大学 2001 二、4(2 分)】8 设双向循环链表中结点的数据域、前驱和后继指针域分别为 data、pre 和 next，试写出在指针 P 所指结点之前插入一 S 结点的 C 语言描述语句。【北京科技大学2001 一、3(2 分) 】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 ；)
4、L=q；【北京理工大学 2006 六、7(507 分)】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 分)】11 阅读下面的算法，说明算法实现的功能。node*1ink(node *headl， *head2)node*p
5、， *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)；【东华大学 2004 二、1(10 分)】12 线性表的双向链表的存储结构为：Typedef struct DNodeTElem info； structDNode*left； struct DNode*right； ；并假设己建立头指针为 head 的双向链表，p 指向其中某个结点，写一个程序段，从该循环链表中删除 p 所指向结点的前一个结点
6、(假设该结点存在)。【华南理工大学 2005 二、1(4 分) 】二、设计题13 已知一个带有表头结点的单链表，结点结构为(data，link)，假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点(k 为正整数)，若查找成功，算法输出该结点的 data 域的值，并返回 1；否则，只返回 0，要求：(1)描述算法的基本设计思想；(2)描述算法的详细实现步骤；(3)根据设计思想和实现步骤，采用程序设计语言描述算法(使用 C 或 C+或 Java 语言实现)，关键之处请给出简要注释。【2009 年全国试题 42(15 分)】14
7、 设将 n(n1)个整数存放到一维数组 R 中。试设计一个在时间和空间两方面都尽可能高效的算法，将 R 中保存的序列循环左移 P(00 0，X 1，X n-1)变换为(XP2，X P+1，X n-1，X 0，X 1，X P-1)。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。 【2010 年全国试题 42(13 分)】15 一个长度为 L(L1)的升序序列 S，处在第L2个位置的数称为 S 的中位数。例如列 S1=(11，13，15，17，19)，则 S1 中的中位数
8、是 15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 92=(2，4，6，8，20)，则S1和 S2 的中位数是 11。现有两个等长升序序列 A 和 B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度【2011 年全国试题 42(15)分】16 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存
9、储映像如下图所示。设 str1和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 。请设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指的两个链表共同后缀的起始位置(如图中字符 i 所在结点的位置 p)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度。2012 年全国试题 42(13 分)】17 用单链表保存 m 个整数，结点的结构为(data， link)，且data要求：(1)给出算法的基本思想。(2) 使用 C 或 C+语言，给出单链表结点的数据类型
10、定义。(3)根据设计思想，采用 C 或 C+语言描述算法，关键之处给出注释。(4)说明所涉及算法的时间复杂度和空间复杂度。18 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学 1998 三、1(5 分)】【厦门大学2006 1(3)(203 分)】19 已知 L1、L2 分别为两循环单链表的头结点指针，m 、n 分别为 L1、L2 表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。【东北大学 1996 二(12 分)】20 设
11、有两个链表，ha 为单向链表， hb 为单向循环链表。编写算法，将两个链表合并成一个单向链表，要求算法所需时间与链表长度无关。【南京航空航天大学1997 四(8 分)】21 已知三个带头结点的线性链表 A、B 和 C 中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点)，编写算法对 A 表进行如下操作：使操作后的链表 A 中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为 O(m+n+p)，其中 m、n 和 p 分别为三个表的长度。【清华大学 1995 一(15 分)】22 顺序结构线性表 LA 与 LB 的结点关键字为整数。
12、 LA 与 LB 的元素按非递减有序，线性表空间足够大。试用类 Pascal 语言给出一种高效算法，将 LB 中元素合并到 LA 中，使新 LA 的元素仍保持非递减有序。高效指最大限度地避免移动元素。【北京工业大学 1997 一、2(12 分)】23 已知长度为 n 的线性表 A 采用顺序存储结构，请写一时间复杂度为 O(n)、空间复杂度为 O(1)的算法，该算法删除线性表中所有值为 item 的数据元素。(O(1) 表示算法的辅助空间为常量)。【北京航空航天大学 2000 五(10 分)】【天津大学 2005八(10 分 )】24 已知消费总金额，请设计一个发票打印程序，打印输出的发票金额单
13、位为：千百十元。【南京航空航天大学 2004 三、3(8 分)】25 写算法将单链表 L1 拆成两个链表，其中以 L1 为头的链表保持原来向后的链接，另一个链表的头为 L2，其链接方向与 L1 相反，L1 包含原链表的奇数序号的结点，L2 包含原链表的偶数序号的结点。【东华大学 2004 三(10 分)】26 试编写在带头结点的单链表中删除(一个)最小值结点的(高效)算法 void delete(LinklistL) 。【北京理工大学 2001 九、3(8 分)】27 用类 CC+设计算法，判断一个带表头结点的双向循环链表 DL(DuIJnkList)是否对称相等。 (比如，表(25，34，3
14、4，25)和表(25，3，25)为对称的。)【南京理工大学 2005 三(5 分) 】其中结点结构为：struct NodeE1emType data； ElemType 代表某种抽象数据类型Node*Llink， *R1ink；28 已知两个单链表 A 和 B，其头指针分别为 heada 和 headb，编写一个过程从单链表 A 中删除自第 i 个元素起的共 len 个元素，然后将单链表 A 插入单链表 B 的第 j 个元素之前。【中国矿业大学 2000 三(10 分)】29 假设一个单循环链表，其结点含有三个域 pre、 data、link。其中 data 为数据域；pre 为指针域，它的
15、值为空指针(NIL)；link 为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。 【西安电子科技大学 1999 软件五(10 分)】30 已知一个单链表中每个结点存放一个整数，并且结点数不少于 2，请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回 ture，否则返回 false。 【西安电子科技大学 2000 软件二(10 分)】31 两个整数序列 A=a1， a2，a3，am 和 B=b1，b2，b3，bn 已经存入两个单链表中，设计一个算法，判断序列 B 是否是序列 A 的子序列。【东北大学1999 二(10 分) 】32 L1 与
16、 L2 分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个字母。设计把 L1 中与 L2 中数据相同的连续结点顺序完全倒置的算法。【东北大学 1997 四(15 分) 】例：33 已知 L 为链表的头结点地址，表中共有 m(m3)个结点，从表中第 i 个结点(1im) 起到第 m 个结点构成一个循环部分链表，设计将这部分循环链表中所有结点顺序完全倒置的算法。【东北大学 1998 三(15 分)】34 请写一个算法将顺序存储结构的线性表(a 1an)逆置为(a na1)。【大连海事大学1996 八(6 分)】35 写出一个从表尾到表头的逆向建立单链表的算法。【中科院研究生院 2004
17、 三(7分)】36 已知一带头结点的递增有序单链表，请在原结点上将其倒序。【南京航空航天大学 2004 二、4(12 分) 】37 试编写求倒排循环链表元素的算法。【南京航空航天大学 1995 十二(10 分)】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 分)】39 编写逆向输出不带头结点的单向链表中数据域的递归算法。设表中有 4 个结点，从表头至表尾其数据域分别为 10，30，20，40，作图
18、表示出该算法的执行过程。设该链表的结点的数据类型的名称为 list，结点的数据域和指针域的名称分别为data 和 next，不必写出 list 的定义。【中南大学 2005 四、3(10 分)】40 在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：(7，10 ，10，21，30，42，42，42，51，70)将变作(7，10，21，30，42，51，70)，分析算法的时间复杂度。【北京工业大学 1996 三(15 分)】41 已知带头结点的单链表有 data 和 next 两个域，设计一个算法，将该链表中的重复元素结
19、点删除。【北京邮电大学 2005 五、2(10 分)】【苏州大学 2005 三(15 分)】42 设有一个正整数序列组成的有序单链表(按递增次序有序，且允许有相等的整数存在)，试编写能实现下列功能的算法：(要求用最少的时间和最小的空间。)(1)确定在序列中比正整数 x 大的数有几个(相同的数只计算一次，如序列20，20 ，17 ，16，15，15 ，11，10，8，7，7，5，4 中比 10 大的数有 5 个)；(2)在单链表中将比正整数 x 小的数按递减次序排列；(3)将正整数(比)x 大的偶数从单链表中删除。 【东北大学 2001 二(17 分)】43 编写一个算法来交换单链表中指针尸所指
20、结点与其后继结点，HEAD 是该链表的头指针，P 指向该链表中某一结点。 【吉林大学 2001 二、1(7 分) 】44 设键盘输入 n 个英语单词，输入格式为 n，w 1， w2，w n，其中 n 表示随后输入英语单词的个数，试编一程序，建立一个单向链表，实现：(1)如果单词重复出现，则只在链表上保留一个(单考生做)。(2) 除满足(1)的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前 k(kn)个单词(统考生做 )。【南京航空航天大学 1998 九(10 分)】45 已知一双向循环链表，从第二个结点至表尾递增有序(设 a1xa n)(x 是第一个结点的
21、值， “ 第二个结点至表尾 ”指 a1an，因篇幅所限，编者略去图 )。试编写程序，将第一个结点删除并插入表中适当位置，使整个链表递增有序。【南京航空航天大学 1998 八(10 分) 】46 设民航公司有一个自动预订飞机票的系统，该系统中有一张用双重链表示的乘客表，表中结点按乘客姓氏的字母序相链接。例如，下面是张某个时刻的乘客表。试为该系统写出一个当任一乘客要订票时修改乘客表的算法。【北方交通大学2000 六(17 分) 】47 设有一头指针为 L 的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针)、data( 数据 )和 next(后继指针)域外，还有一个访问频度域 fr
22、eq。在链表被起用前，其值均初始化为零。每当在链表中进行一次 Locate(L，x)运算时，令元素值为 x 的结点中 freq 域的值增 1，并使此链表中结点保持按访问频度非增(递减)的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的 Locate(L，x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。【清华大学 1997 二(10 分)】【苏州大学 2004 四(15 分)】【江苏大学 2006 四、2(13 分)】48 给定(已生成) 一个带表头结点的单链表，设 head 为头指针，结点的结构为(dam，next
23、) ，dam 为整型元素，next 为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。(要求：不允许使用数组作辅助空间。)【华中理工大学 2000 八、2(13 分)】49 编写程序，要求完成：(1)建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的 data 域存放一个二进制位。(2)在此链表上实现对二进制数加 1 的运算，并输出运算结果。【西北大学 2002 七(10 分)】计算机专业基础综合数据结构（线性表）历年真题试卷汇编 5 答案与解析一、综合题1 【正确答案】 一般说链式存储结构克服了顺序存储结构的三个弱点。首先，插入、删除不需
24、移动元素，只修改指针，时间复杂度为 O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储结构的缺点。2 【正确答案】 线性表、栈、队列、串；顺序存储结构、链式存储结构。3 【正确答案】 顺序映射时，a i 与 ai+1 的物理位置相邻；链表表示时，a i 与 ai+1 的物理位置不要求相邻。4 【正确答案】 等概率(后插)时，插入位置 0n，则平均移动元素个数为 n2。若不等概率，则平均移动的元素个数为 。5 【正确答案】 首元结点也就是第一元素结点，它是头结点后边的第一个结点。6 【
25、正确答案】 在单链表中不能从当前结点(若当前结点不是第一结点)出发访问到任何一个结点。因为链表运算只能从头指针开始，访问到链表中每个结点。在双链表中从当前结点反向可以到第一结点，正向可以到最后结点，因而从当前结点出发可以访问到链表中任何一个结点。7 【正确答案】 设该链表带头结点，将头结点摘下，并将其指针域置空。然后从第一元素结点开始，直到最后一个结点为止，依次前插入头结点的后面，实现了链表的逆置，即将单向链表变成一个与原来链接方向相反的单向链表。8 【正确答案】 在指针 p 所指结点前插入结点 s 的语句如下： s 一pre=p 一pre； s 一next=p ； p 一pre 一next=
26、s； p 一pre=s ；9 【正确答案】 算法的功能是将无表头结点的单链表 L 逆置。10 【正确答案】 算法实现集合的差运算 C=A-B。将链表 L2 中的元素依次到链表L1 中查找，有则从 L1 中删除。11 【正确答案】 本算法功能是将两个无头结点的循环链表合并为一个循环链表。headl 最后一个结点的链域指向 head2，head2 最后一个结点的链域指向headl，headl 为结果循环链表的指针。12 【正确答案】 q=p 一1eft；qleft 一right=q 一ri ght；(rright 一1eft=q一left； free(q) ；说明：因为是双向链表，答案不唯一。例如
27、，第三个语句可写为：p 一left=q 一left；。二、设计题13 【正确答案】 “ 倒数” 和 “正数”是相对概念。如战士站队报数从 1 到 10，排头 1若从反向报数则是 10。本题设指针 q 指向链表，指针 p 指向链表第一元素，q 是 p的前驱(广义)。p 向后移动七个结点后，p 和 q 相距 k 之后同步移动指针 p 和 q，到p=nuU 时，q 指向倒数第 k 个结点。另一算法是链表结点依次入栈，入栈完毕退栈，弹出第 k 个结点，不如前者性能好。算法的主要语句段如下：while(p p=p 一next ；) 奇数序号结点在 L1 中，pre 指向前驱else(s：p 一next；
28、 保存后继，避免断链p 一next：L2 一next;L2 一next=p ； 偶数序号结点逆置 (头插法)插入 L2中p：s；) 将保存的后继恢复成当前待处理结点p=s；; 将保存的后继恢复成当前待处理节点pre 一next：null ； L1 奇序号链表加上结尾标志，保证在结点个数为偶数时也正确26 【正确答案】 1ist 一link； pre=1ist； p 指向待处理结点，pre 指向最小值结点的前驱q=p； q 指向最小值结点，初始假定是第一结点while(p 一link)if(P 一link 一datadata)pre=p ；q=p 一 link；) 找到新的最小值结点p=p 一l
29、ink；)if(q=list 一link) 若最小值是第一元素结点，则不需再操作fpre 一link=q 一link； 将最小值结点从链表上摘下q 一link=list 一link ； 将 q 结点插到链表最前面1ist-link=q ；38 题是双向链表，设有头结点，插入最多涉及 4 条链的修改，核心语句段如下：q=d 一rlink； 设链表有头结点while(q)if(q 一datap 一data)p=q； P 记数据域值最大的结点，初始是第一结点q=q-rlink； P 一llink-rlink=p-rlink；p 一rlink 一1link=p 一11ink； 将 P 摘下p 一rli
30、nk=d 一rlink；p-llink=d；d 一rlink 一llink=p；d-rlink=p； 插入P 结点27 【正确答案】 while(p!=q ia n 一 1 一 i;35 【正确答案】 while(P!：null) head 是链表头结点的指针，P 初值指向第一元素结点r=P 一next ； 暂存 P 的后继p 一next=head 一next；head 一next=p ； 逆置p=r； 恢复待逆置结点36 【正确答案】 while(P!：null) head 是链表头结点的指针，P 初值指向第一元素结点r=P 一next ； 暂存 P 的后继p 一next=head 一nex
31、t；head 一next=p ； 逆置p=r； 恢复待逆置结点37 【正确答案】 题是循环链表的逆置。与逆置单链表有两点不同。一是初始化成循环链表而不是空链表；二是判断链表尾不用空指针而用链表头指针。核心语句段如下：while(P!=la) p 初始指向首元素后将 la 初始化成空循环链表r=p 一next； 暂存 P 的后继结点p 一next=la 一next ； 1a 一next=p ； 逆置p=r； )38 【正确答案】 题的结果链表是以 an 为对称的。由尾指针 p 找到第一元素结点，复制结点并插入原尾结点的后面。同样处理其他结点。要记住结点 a1 的指针，最后将尾指针 P 指向结点
32、a1，形成新的单向循环链表。核心语句段如下： q：p 一next; q 指向 a1 结点 t=new(LNode)；t 一data：q 一data；r=t； 申请并复制结点，r 记住 a1 结点的指针 t 一next=P 一next；P 一next ：t； 先将 a1 结点放到正确位置 q=q 一next； 从 a2 结点开始 while(q!=p) (s=q 一next；t 暂存后继，申请并复制结点 t 一next=p 一next；P 一next=t ；q=s ； 对称插入放置，恢复待处理结点 p=r；修改尾指针39 【正确答案】 void Output(LinkedList list)本算
33、法逆序输出链表 list 各结点的值if(1ist)Output(1ist 一next);coutdatadata=pre 一data) 处理相同元素值的结点u=p；p=p-next；delete(u)；) 释放相同元素值的结点elsepre 一next=p；pre=p；p=p-next;) 处理前驱，后继元素值不同pre 一next=p；2 链表尾。非常重要，可能最后都是重复元素41 【正确答案】 本题并未说单链表有序，因此要依次从每个结点出发，遍历整个链表，删除重复元素。删除结点要记住被删结点的前驱，不能断链。核心语句段如下：while(pre!=null) 用 pre 控制依次从每个结点
34、出发，初始指向第一元素m=pre 一data ；q=pre；p=pre 一next ；while(p!=null)if(p-data=m)u=p; p=p 一next；free(u); 删重复结点elseq 一next=p；q=p；p=p 一next；q 一next=p； 有可能链表尾结点值是 mpre=pre-next； 下一趟42 【正确答案】 确定比正整数 x 大的数有几个属于计数问题，相同数只计一次，要求记住前驱，前驱和后继值不相等时移动前驱指针，进行计数。将比正整数 x 小的数按递减排序，属于单链表的逆置问题。比正整数 x 大的偶数从表中删除，属于单链表中结点的删除，必须记住其前驱，
35、以使链表不断链。算法结束时，链表中结点的排列是：小于 x 的数按递减排列，接着是 x(若有的话)，最后是大干 x 的奇数。顺便指出，“ 递增有序” 是指后继元素大于前驱元素，不允许有相同值的元素。题中所给例子序列与题目的论述并不一致。43 【正确答案】 单链表中查找任何结点，都必须从头指针开始。将指针 P 所指结点与其后继结点交换，必须先找到 P 的前驱结点的指针。核心语句段如下：pre=HEAD；q=HEAD 一next；q 指向待处理结点， pre 指向 q 的前驱while(q!=null 1a-next=p；输出运算结果的核心语句段如下：while(p!=1a) 初值 p=1a 一next ；指向首元结点coutdata; P=p 一next ；)coutendl；
