.
5 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)运算的算法,该运算为函数过程,返回找到结点的地址,类型为指针型。
33.给定(已生成)一个带表头结点的单链表,设head为头指针,结点的结构为(data,next),data为整型元素,next为指针,试写出算法:按递增次序输出单链表中各结点的数据元素,并释放结点所占的存储空间。(要求;不允许使用数组作辅助空间)
34.已知三个带头结点的线性链表A、B和C中的结点均依元素值自
.
.
小至大非递减排列(可能存在两个以上值相同的结点),编写算法对A表进行如下操作:使操作后的链表A中仅留下三个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为O(m+n+p),其中m、n和p分别为三个表的长度。
35.试编写算法将线性表就地逆置。分别以顺序存储结构和链式存储结构实现。
36.己知两个线性表A ,B均以带头结点的单链表作存储结构,且表中元素按值递增有序排列。设计算法求出A与B的交集C,要求C另开辟存储空间,要求C同样以元素值的递增序的单链表形式存贮,并计算算法的时间复杂度。
37. 已知不带头结点的线性链表list,链表中结点构造为(data、link),其中data为数据域,link为指针域。请写一算法,将该链表按结点数据域的值的大小从小到大重新。要求过程中不得使用除该链表以外的任何链结点空间。
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)若该数值是偶数,则将其直接后继结点删除。
.