线性表编程练习题.pdf

《线性表编程练习题.pdf》由会员分享，可在线阅读，更多相关《线性表编程练习题.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-1、假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。输入:1 2 5 6 83 4 7 9 10输出:10 9 8 7 6 5 4 3 2 1测试数据输入：7 9 10 118 12 13 14输出：14 13 12 11 10 9 8 7链表翻转2.带头结点且头指针为 ha 和 hb 的两线性表 A 和 B 分别表示两个集合。两表中的元素皆为递增有序。请写一算法求 A 和 B 的并集 AUB。要求该并集中的元素仍保持递增有序。且要利用 A 和 B 的原有结点空间。输

2、入:1 2 5 6 82 5 7 9输出:1 2 5 6 7 8 9测试数据输入：7 9 10 118 9 10 11输出：7 8 9 10 11.z.-3.知 L1、L2 分别为两循环单链表的头结点指针，m,n 分别为 L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。4.顺序构造线性表 LA 与 LB 的结点关键字为整数。LA 与 LB 的元素按非递减有序，线性表空间足够大。试用类 PASCAL 语言给出一种高效算法，将 LB 中元素合到 LA 中，使新的 LA 的元素仍保持非递减有序。高效指最大限度的防止移动元素。5.不带头结点的线性链表 lis

3、t，链表中结点构造为 data、link，其中data 为数据域，link 为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新。要求过程中不得使用除该链表以外的任何链结点空间。6.设 L 为单链表的头结点地址，其数据结点的数据都是正整数且无一样的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。7.设 Listhead 为一单链表的头指针，单链表的每个结点由一个整数域 DATA 和指针域 NE*T 组成，整数在单链表中是无序的。编一PASCAL 过程，将 Listhead 链中结点分成一个奇数链和一个偶数链，分别由 P,Q 指向，每个链中的数据按由小到大排列。程

4、序中不得使用NEW 过程申请空间。8.线性表a1 a2 a3 an按顺序存于存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法：例：*,-*,-*,*,*,-*变为-*,-*,-*,*,*。.z.-9.试编写在带头结点的单链表中删除一个最小值结点的高效算法。voiddeleteLinklist&L10.非空线性链表由 list 指出，链结点的构造为data,link.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。【航空航天大学 2001 四10 分】11.p 指向双向循环链表中的一个结点，其结点构造为 data、

5、llink、rlink三个域，写出算法 change(p),交换 p 所指向的结点和它的前缀结点的顺序。12.线性表(a1,a2,a3,an)中元素递增有序且按顺序存储于计算机。要求设计一算法完成：1 用最少时间在表中查找数值为*的元素。2 假设找到将其与后继元素位置相交换。3 假设找不到将其插入表中并使表中元素仍递增有序。【东北大学 1996 三(12 分)】13.设单链表的表头指针为 h，结点构造由 data 和 ne*t 两个域构成，其中 data 域为字符型。写出算法 dc(h,n),判断该链表的前 n 个字符是否中心对称。例如*y*,*yy*都是中心对称。14.两个单链表 A 和 B

6、,其头指针分别为 heada 和 headb，编写一个过程从单链表 A 中删除自第 i 个元素起的共 len 个元素，然后将单链表A 插入到单链表 B 的第 j 个元素之前。15.设线性表存于 A1.size的前 num 各分量中，且递增有序。请设计一个算法，将*插入到线性表的适当位置上，以保持线性表的有序性，.z.-并在设计前说明设计思想，最后说明所设计算法的时间复杂度。16.假设一个单循环链表，其结点含有三个域 pre、data、link。其中data 为数据域；pre 为指针域，它的值为空指针NIL；link 为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。17.递增有序的

7、单链表 A,B 分别存储了一个集合，请设计算法以求出两个集合 A 和 B 的差集 A-B即仅由在 A 中出现而不在 B 中出现的元素所构成的集合，并以同样的形式存储，同时返回该集合的元素个数。18.一个单链表中每个结点存放一个整数，并且结点数不少于 2，请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，假设满足则返回ture，否则返回 false.19 两个整数序列 A=a1,a2,a3,am 和 B=b1,b2,b3,bn 已经存入两个单链表中，设计一个算法，判断序列B 是否是序列 A 的子序列。【东北大学 1999 二(10 分)】20三个带头结点的线性链表A

8、、B 和 C 中的结点均依元素值自小至大非递减排列可能存在两个以上值一样的结点，编写算法对 A 表进展如下操作：使操作后的链表 A 中仅留下三个表中均包含的数据元素的结点，且没有值一样的结点，并释放所有无用结点。限定算法的时间复杂度为 Om+n+p，其中m、n 和 p 分别为三个表的长度。21.请写一个算法将顺序存储构造的线性表a1.an逆置为(an.a1)。【海事大学 1996 八(分)】22设有一个由正整数组成的无序向后单链表，编写完成以下功.z.-能的算法：1找出最小值结点，且打印该数值；2假设该数值是奇数，则将其与直接后继结点的数值交换；3 假设该数值是偶数，则将其直接后继结点删除。【

9、东北大学 2000二(15 分)】23L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符或数字字符或其它字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符。要求用最少的时间和最少的空间24在一个递增有序的线性表中，有数值一样的元素存在。假设存储方式为单链表，设计算法去掉数值一样的元素，使表中不再有重复的元素。例如：7，10，10，21，30，42，42，42，51，70将变作7，10，21，30，42，51，70，分析算法的时间复杂度。25在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表 L，

10、且要求当输入一样数据值时，线性表中不能存在数据值一样的数据元素，试写出其算法。顺序存储构造的线性表描述为：CONSTma*len=线性表可能到达的最大长度；TYPEsqlisttp=RECORDelem:array1.ma*len of integer;last:0.ma*lenEND;.z.-VAR L:sqlisttp;26设有一个正整数序列组成的有序单链表按递增次序有序，且允许有相等的整数存在，试编写能实现以下功能的算法：要求用最少的时间和最小的空间(1)确定在序列中比正整数*大的数有几个一样的数只计算一次，如序列20,20,17,16,15,15,11,10,8,7,7,5,4中比 1

11、0 大的数有 5 个；(2)在单链表将比正整数*小的数按递减次序排列；(3)将正整数 比*大的偶数从单链表中删除。【东北大学 2001 二(17分)】27.编写一个算法来交换单链表中指针 P 所指结点与其后继结点，HEAD 是该链表的头指针，P 指向该链表中*一结点。【大学 2001 二、1(7 分)】28设键盘输入 n 个英语单词，输入格式为 n,w1,w2,wn,其中 n表示随后输入英语单词个数，试编一程序，建立一个单向链表，实现：10 分1如果单词重复出现，则只在链表上保存一个。单考生做。2除满足1的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前 k

12、(k=n)个单词统考生做。【航空航天大学 1998 九 10 分】29一双向循还链表，从第二个结点至表尾递增有序，设 a1*an如以下图(“第二个结点至表尾指 a1.an，因篇幅所限，编者略去图)。试编写程序，将第一个结点删除并插入表中适当位置，使整个.z.-链表递增有序。【航空航天大学 1998 八10 分】30.长度为 n 的线性表 A 采用顺序存储构造，请写一时间复杂度为0(n)、空间复杂度为 0(1)的算法，该算法删除线性表中所有值为 item的数据元素。O1表示算法的辅助空间为常量。31设民航公司有一个自动预订飞机票的系统，该系统中有一用双重链表示的乘客表，表中结点按乘客姓氏的字母序

13、相链。例如，下面是*个时刻的乘客表。试为该系统写出一个当任一乘客要订票时修改乘客表的算法。序号dataLlinkRlink1Liu652Chan493Wang574Bao025Mai136Dong817*i308Deng969Cuang2832设有一头指针为 L 的带有表头结点的非循环双向链表，其每个结点中除有 pred前驱指针，data数据和 ne*t后继指针域外，还有一个访问频度域 freq。在链表被起用前，其值均初始化为零。每当在链表中进展一次 Locate(L,*)运算时，令元素值为*的结点中 freq.z.-域的值增 1，并使此链表中结点保持按访问频度非增递减的顺序排列，同时最近访问

14、的结点排在频度一样的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,*)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。33给定(已生成)一个带表头结点的单链表，设head 为头指针，结点的构造为(data,ne*t),data 为整型元素，ne*t 为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。(要求;不允许使用数组作辅助空间)34三个带头结点的线性链表A、B 和 C 中的结点均依元素值自小至大非递减排列可能存在两个以上值一样的结点，编写算法对 A 表进展如下操作：使操作后的链表 A 中仅留下三个表中

15、均包含的数据元素的结点，且没有值一样的结点，并释放所有无用结点。限定算法的时间复杂度为 Om+n+p，其中m、n 和 p 分别为三个表的长度。35试编写算法将线性表就地逆置。分别以顺序存储构造和链式存储构造实现。36己知两个线性表 A，B 均以带头结点的单链表作存储构造，且表中元素按值递增有序排列。设计算法求出 A 与 B 的交集 C，要求 C另开辟存储空间，要求 C 同样以元素值的递增序的单链表形式存贮，并计算算法的时间复杂度。37.不带头结点的线性链表 list，链表中结点构造为data、link，其中 data 为数据域，link 为指针域。请写一算法，将该链表按结点数据域的值的大小从小

16、到大重新。要求过程中不得使用除该链表以外的任.z.-何链结点空间。38.设键盘输入 n 个英语单词，输入格式为n,w1,w2,wn,其中 n 表示随后输入英语单词个数，试编一程序，建立一个单向链表，实现：1如果单词重复出现，则只在链表上保存一个。单考生做。2除满足1的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前 k(k=n)个单词统考生做。39 两个整数序列 A=a1,a2,a3,am 和 B=b1,b2,b3,bn 已经存入两个单链表中，设计一个算法，判断序列 B 是否是序列 A 的子序列。40设有一个由正整数组成的无序向后单链表，编写完成以下功能的算法：1找出最小值结点，且打印该数值；2假设该数值是奇数，则将其与直接后继结点的数值交换；3假设该数值是偶数，则将其直接后继结点删除。.z.