2022年线性表编程练习题 .pdf

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

1、. . 1、假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。输入: 1 2 5 6 8 3 4 7 9 10 输出: 10 9 8 7 6 5 4 3 2 1 测试数据输入： 7 9 10 11 8 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 8 2 5 7 9 输出: 1 2 5 6 7 8 9 测试数据输入： 7 9 10 11 8 9 10 11 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - . . 输出： 7 8 9 10 11 3. 知 L1、L2 分别为两循环单链表的头结点指针，m,n分别为 L1、L2表中数据结点个数。 要求设计一算法， 用最快速度将两表合并成一个带头结点的循环单链表。4. 顺序结构线性表LA与

3、LB的结点关键字为整数。 LA 与 LB 的元素按非递减有序，线性表空间足够大。试用类PASCAL 语言给出一种高效算法，将 LB中元素合到 LA中，使新的 LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。5. 已知不带头结点的线性链表list，链表中结点构造为（data 、link ） ，其中 data 为数据域， link为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。6. 设 L 为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。

4、7. 设 Listhead为一单链表的头指针，单链表的每个结点由一个整数域 DATA 和指针域 NEXT 组成， 整数在单链表中是无序的。 编一 PASCAL过程，将 Listhead链中结点分成一个奇数链和一个偶数链，分别由名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - . . P,Q指向，每个链中的数据按由小到大排列。程序中不得使用 NEW过程申请空间。8. 已知线性表（ a1 a2 a3 an）按顺序存于内存，每个元素都

5、是整数，试设计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x x）变为（ -x,-x,-xx,x,x ） 。9. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。 void delete（Linklist &L）10. 已知非空线性链表由list指出，链结点的构造为（data,link） .请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。【北京航空航天大学 2001 四（10 分） 】11. 已知 p 指向双向循环链表中的一个结点，其结点结构为data、llink、rlink三个域，写出

6、算法change(p), 交换 p 所指向的结点和它的前缀结点的顺序。12. 线性表 (a1,a2,a3,an) 中元素递增有序且按顺序存储于计算机内。要求设计一算法完成：（1） 用最少时间在表中查找数值为x 的元素。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - . . （2） 若找到将其与后继元素位置相交换。（3） 若找不到将其插入表中并使表中元素仍递增有序。【东北大学1996 三 ( 12分)】13. 设单链表的表头指针

7、为h， 结点结构由 data 和 next 两个域构成，其中 data 域为字符型。写出算法dc(h,n),判断该链表的前 n 个字符是否中心对称。例如 xyx, xyyx都是中心对称。14. 已知两个单链表 A和 B,其头指针分别为 heada和 headb， 编写一个过程从单链表 A中删除自第 i 个元素起的共 len 个元素，然后将单链表 A插入到单链表 B的第 j 个元素之前。15. 设线性表存于A1.size的前 num各分量中，且递增有序。请设计一个算法， 将 x 插入到线性表的适当位置上， 以保持线性表的有序性， 并在设计前说明设计思想， 最后说明所设计算法的时间复杂度。16.

8、假设一个单循环链表，其结点含有三个域pre 、data、link 。其中 data 为数据域； pre 为指针域，它的值为空指针（NIL） ；link为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。17. 已知递增有序的单链表A,B 分别存储了一个集合， 请设计算法以求出两个集合 A和 B 的差集 A-B （即仅由在 A中出现而不在 B中出现名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - . . 的元素所构成的集

9、合） ，并以同样的形式存储，同时返回该集合的元素个数。18. 已知一个单链表中每个结点存放一个整数，并且结点数不少于 2，请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture ，否则返回 false. 19 两个整数序列 A=a1,a2,a3, ,am 和 B=b1,b2,b3, ,bn 已经存入两个单链表中，设计一个算法，判断序列B是否是序列 A的子序列。【东北大学 1999 二 (10分) 】20已知三个带头结点的线性链表A、B 和 C 中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编写算法对A 表进行如下操作：使操作

10、后的链表A 中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O （m+n+p） ，其中 m、n 和 p 分别为三个表的长度。21. 请写一个算法将顺序存储结构的线性表（a1.an ）逆置为(an.a1)。 【大连海事大学 1996八(分)】22设有一个由正整数组成的无序（向后）单链表，编写完成下列功名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - . . 能的算法：（1）找出

11、最小值结点，且打印该数值；（2）若该数值是奇数，则将其与直接后继结点的数值交换；（3） 若该数值是偶数，则将其直接后继结点删除。【东北大学 2000 二(15 分) 】23已知 L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符， 该字符可能是英文字母字符或数字字符或其它字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符。 （要求用最少的时间和最少的空间）24在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表， 设计算法去掉数值相同的元素，使表中不再有重复的元素。例如： （7，10，10，21，30，42，42，42，51，

12、70）将变作（ 7，10，21，30，42，51，70） ，分析算法的时间复杂度。25在输入数据无序的情况下， 建立一个数据值为整型的递增有序的顺序存储线性表 L，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。顺序存储结构的线性表描述为： CONST maxlen=线性表可能达到的最大长度； TYPE sqlisttp=RECORD 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - . . ele

13、m:array1.maxlen of integer; last :0.maxlen END; VAR L: sqlisttp; 26设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在） ，试编写能实现下列功能的算法： （要求用最少的时间和最小的空间）(1) 确定在序列中比正整数x 大的数有几个（相同的数只计算一次，如序列 20,20,17,16,15,15,11,10,8,7,7,5,4中比 10 大的数有5个） ；(2) 在单链表将比正整数x 小的数按递减次序排列；(3) 将正整数（比）x 大的偶数从单链表中删除。【东北大学 2001 二(17 分) 】27. 编写

14、一个算法来交换单链表中指针P 所指结点与其后继结点，HEAD 是该链表的头指针， P指向该链表中某一结点。【吉林大学 2001 二、1 (7 分)】28设键盘输入 n 个英语单词，输入格式为n, w1, w2, ,wn, 其中n 表示随后输入英语单词个数，试编一程序，建立一个单向链表，实现： （10 分）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - . . （1）如果单词重复出现，则只在链表上保留一个。（单考生做）。（2）除

15、满足（1）的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k=n) 个单词（统考生做） 。 【南京航空航天大学 1998 九 （10分） 】29已知一双向循还链表，从第二个结点至表尾递增有序，（设a1xan）如下图 (“第二个结点至表尾”指a1.an ，因篇幅所限，编者略去图 )。试编写程序， 将第一个结点删除并插入表中适当位置，使整个链表递增有序。【南京航空航天大学1998 八（10 分） 】30. 已知长度为 n 的线性表 A采用顺序存储结构， 请写一时间复杂度为 0(n) 、空间复杂度为0(1) 的算法，该算法删除线性表中所有值为item 的数据

16、元素。（O （1）表示算法的辅助空间为常量） 。31设民航公司有一个自动预订飞机票的系统，该系统中有一张用双重链表示的乘客表，表中结点按乘客姓氏的字母序相链。例如，下面是张某个时刻的乘客表。 试为该系统写出一个当任一乘客要订票时修改乘客表的算法。序号 data Llink Rlink 1 Liu 6 5 2 Chan 4 9 3 Wang 5 7 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - - - - . . 4 Bao 0 2 5

17、Mai 1 3 6 Dong 8 1 7 Xi 3 0 8 Deng 9 6 9 Cuang 2 8 32设有一头指针为 L 的带有表头结点的非循环双向链表，其每个结点中除有 pred（前驱指针），data（数据）和 next（后继指针） 域外，还有一个访问频度域freq 。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元素值为x 的结点中freq 域的值增 1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为

18、函数过程，返回找到结点的地址，类型为指针型。33给定(已生成 ) 一个带表头结点的单链表，设head 为头指针，结点的结构为 (data,next),data为整型元素， next 为指针，试写出算法: 按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。 (要求; 不允许使用数组作辅助空间) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - . . 34已知三个带头结点的线性链表A、B和 C中的结点均依元素值自小

19、至大非递减排列（可能存在两个以上值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O （m+n+p ） ，其中 m 、n 和 p 分别为三个表的长度。35试编写算法将线性表就地逆置。分别以顺序存储结构和链式存储结构实现。36己知两个线性表A ，B 均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。 设计算法求出 A 与 B 的交集 C， 要求 C另开辟存储空间，要求C 同样以元素值的递增序的单链表形式存贮，并计算算法的时间复杂度。37. 已知不带头结点的线性链表list，链

20、表中结点构造为 （data、 link） ，其中 data为数据域， link 为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。38. 设键盘输入 n 个英语单词，输入格式为n, w1, w2, ,wn,其中 n表示随后输入英语单词个数， 试编一程序，建立一个单向链表， 实现：（1）如果单词重复出现，则只在链表上保留一个。（单考生做）。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 11 页 -

21、- - - - - - - - . . （2）除满足（1）的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k=n)个单词（统考生做） 。39两个整数序列 A=a1,a2,a3, ,am 和 B=b1,b2,b3, ,bn 已经存入两个单链表中，设计一个算法，判断序列B 是否是序列 A 的子序列。40设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法：（1）找出最小值结点，且打印该数值；（2）若该数值是奇数，则将其与直接后继结点的数值交换；（3）若该数值是偶数，则将其直接后继结点删除。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -