lblink

算法设计题打印部份

假设有两个按元素值递增顺序排列的线性表均以单链表形

式存储。请编写算法将这两个单链表归并为一个按元素值递

减顺序排列的单链表并要求利用原先两个单链表的结点寄

存归并后的单链表。【北京大学1998三、15分】类似

此题的另外表达有1设有两个无头结点的单链表头指针别

离为hahb链中有数据域data链域next两链表的数据都按递

增序寄存现要求将hb表归到ha表中且归并后ha仍递增序归

并中ha表中已有的数据假设hb中也有那么hb中的数据不归

并到ha中hb的链表在算法中不许诺破坏。【南京理工大学

1997四、315分】PROCEDUREmergehahb2已知头指针别

离为la和lb的带头结点的单链表中结点按元素值非递减有

序排列。写出将la和lb两链表归并成一个结点按元素值非

递减有序排列的单链表其头指针为lc并计算算法的时刻复

杂度。【燕山大学1998五20分】2.图编者略中带头结

点且头指针为ha和hb的两线性表A和B别离表示两个集

合。两表中的元素皆为递增有序。请写一算法求A和B的并

集AUB。要求该并集中的元素仍维持递增有序。且要利用A

和B的原有结点空间。【北京邮电大学1992二15分】类

似此题的另外表达有1已知递增有序的两个单链表AB别

离存储了一个集合。设计算法实现求两个集合的并集的运算

A:A∪B【合肥工业大学1999五、18分】2已知两个链表

A和B别离表示两个集合其元素递增排列。编一函数求A与

B的交集并寄存于A链表中。【南京航空航天大学2001六

10分】3设有两个从小到大排序的带头结点的有序链表。

试编写求这两个链表走运算的算法即L1∩L2。要求结果链表

仍是从小到大排序但无重复元素。【南京航空航天大学1996

十一10分】4己知两个线性表AB均以带头结点的单链表

作存储结构且表中元素按值递增有序排列。设计算法求出A

与B的交集C要求C另开辟存储空间要求C一样以元素值

的递增序的单链表形式存贮。【西北大学2000五8分】5

已知递增有序的单链表AB和C别离存储了一个集合设计算

法实现AA∪B∩C并使求解结构A2仍维持递增。要求算法

的时刻复杂度为OABC。其中A为集合A的元素个数。【合

肥工业大学2000五、18分】3.知L一、L2别离为两循

环单链表的头结点指针mn别离为L一、L2表中数据结点个

数。要求设计一算法用最快速度将两表归并成一个带头结点

的循环单链表。【东北大学1996二12分】类似此题的另

外表达有1试用类Pascal语言编写进程PROCjoinVAR

lalinklblink实现连接线性表la和lblb在后的算法要求其时

刻复杂度为01占用辅助空间尽可能小。描述所用结构。【北

京工业大学1997一、18分】2设有两个链表ha为单向链

表hb为单向循环链表。编写算法将两个链表归并成一个单

向链表要求算法所需时刻与链表长度无关。【南京航空航天

大学1997四8分】4.顺序结构线性表LA与LB的结点关

键字为整数。LA与LB的元素按非递减有序线性表空间足够

大。试用类PASCAL语言给出一种高效算法将LB中元素合

到LA中使新的LA的元素仍维持非递减有序。高效指最大

限度的幸免移动元素。【北京工业大学1997一、212分】

5.已知不带头结点的线性链表list链表中结点构造为data、

link其中data为数据域link为指针域。请写一算法将该链表

按结点数据域的值的大小从小到大从头链接。要求链接进程

中不得利用除该链表之外的任何链结点空间。【北京航空航

天大学1998五15分】6.设L为单链表的头结点地址其数

据结点的数据都是正整数且无相同的试设计利用直接插入

的原那么把该链表整理成数据递增的有序单链表的算法。

【东北大学1996六14分】类似此题的另外表达有1设

一单向链表的头指针为head链表的记录中包括着整数类型

的key域试设计算法将此链表的记录依照key递增的顺序进

行当场排序.【中科院计算所1999五、110分】7.设

Listhead为一单链表的头指针单链表的每一个结点由一个整

数域DATA和指针域NEXT组成整数在单链表中是无序的。

编一PASCAL进程将Listhead链中结点分成一个奇数链和

一个偶数链别离由PQ指向每一个链中的数据按由小到大排

列。程序中不得利用NEW进程申请空间。【山东大学1993

六15分】类似此题的另外表达有1设计算法将一个带头

结点的单链表A分解为两个具有相同结构的链表B、C其中

B表的结点为A表中值小于零的结点而C表的结点为A表

中值大于零的结点链表A的元素类型为整型要求B、C表利

用A表的结点。【北京理工大学2000四、24分】2设L

为一单链表的头指针单链表的每一个结点由一个整数域

data和指针域NEXT组成整数在单链表中是无序的。设计算

法将链表中结点分成一个奇数链和一个偶数链别离由PQ指

向每一个链中的数据按由小到大排列算法中不得申请新的

结点空间。【青岛海洋大学1999三12分】3将一个带头

结点的单链表A分解为两个带头结点的单链表A和B使得

A表中含有原表中序号为奇数的元素而B表中含有原表中序

号为偶数的元素且维持其相对顺序不变。1写出其类型概

念2写出算法。【山东大学1998九9分】【山东工业大

学2000九9分】8.已知线性表a1a2a3�6�7an按顺序存

于内存每一个元素都是整数试设计用最少时刻把所有值为

负数的元素移到全数正数值元素前边的算法例x-x-xxx-x

�6�7x变成-x-x-x�6�7xxx。【东北大学1998二15分】

类似此题的另外表达有1设有一元素为整数的线性表

La1a2a3�6�7an寄存在一维数组AN中设计一个算法以表中

an作为参考元素将该表分为左、右两部份其中左半部份每一

个元素小于等于an右半部份每一个元素都大于anan位于分

界位置上要求结果仍寄存在AN中。【北京理工大学1999八

6分】2顺序存储的线性表A其数据元素为整型试编写一算

法将A拆成B和C两个表使A中元素值大于等于0的元素

放入B小于0的放入C中..要求:1表B和C另外设置存储

空间2表B和C不另外设置而利用A的空间.【山东大学

2001九、112分】3知线性表a1a2a3�6�7an按顺序存储

且每一个元素都是整数均不相同设计把所有奇数移到所有

偶3数前边的算法。要求时刻最少辅助空间最少【东北大

学1997三15分】4编写函数将一整数序列中所有负数移

到所有正数之前要求时刻复杂度为On【南京航空航天大学

2001八10分】5已知一个由n设n1000个整数组成的线

性表试设计该线性表的一种存储结构并用标准pascal语言描

述算法实现将n个元素中所有大于等于19的整数放在所有

小于19的整数以后。要求算法的时刻复杂度为On空间复杂

度O1。【西安交通大学1996六11分】9.试编写在带头

结点的单链表中删除一个最小值结点的高效算法。void

deleteLinklistampL【北京理工大学2001九、38分】10.已

知非空线性链表由list指出链结点的构造为datalink.请写一

算法将链表中数据域值最小的那个链结点移到链表的最前

面。要求不得额外申请新的链结点。【北京航空航天大学

2001四10分】11.已知p指向双向循环链表中的一个结点

其结点结构为data、llink、rlink三个域写出算法changep互

换p所指向的结点和它的前缀结点的顺序。【首都经贸大学

1997二、215分】12.线性表a1a2a3�6�7an中元素递增有

序且按顺序存储于运算机内。要求设计一算法完成1用最

少时刻在表中查找数值为x的元素。2假设找到将其与后

继元素位置彼此换。3假设找不到将其插入表中并使表中

元素仍递增有序。【东北大学1996三12分】13.设单链

表的表头指针为h结点结构由data和next两个域组成其中

data域为字符型。写出算法dchn判定该链表的前n个字符是

不是中心对称。例如xyxxyyx都是中心对称。【首都经贸

大学1998三、915分】14.已知两个单链表A和B其头指

针别离为heada和headb编写一个进程从单链表A中删除自

第i个元素起的共len个元素然后将单链表A插入到单链表

B的第j个元素之前。【中国矿业大学2000三10分】类

似此题的另外表达有1h一、h2为两个链表的表头指针结点

结构为data和link两个域组成。写出算法indeh1h2ijl将链表

h1从第i个结点起的l个结点删除并插入到h2表的第j个结

点之前。【首都经贸大学1998三、1020分】15.设线性

表存于A1..size的前num各分量中且递增有序。请设计一个

算法将x插入到线性表的适当位置上以维持线性表的有序性

并在设计前说明设计思想最后说明所设计算法的时刻复杂

度。【西安电子科技大学1999计应用1997二10分】类

似此题的另外表达有1试编制在线性表L2中插入数据元素

26的程序。要求该程序用turboPascal语言编制并能在运算

机上运行结点类型为链式结构【大连海事大学1996二、116

分】16.假设一个单循环链表其结点含有三个域pre、data、

link。其中data为数据域pre为指针域它的值为空指针NILlink

为指针域它指向后继结点。请设计算法将此表改成双向循环

链表。【西安电子科技大学1999软件五10分】17.已

知递增有序的单链表AB别离存储了一个集合请设计算法以

求出两个集合A和B的差集A-B即仅由在A中显现而不在

B中显现的元素所组成的集归并以一样的形式存储同时返回

该集合的元素个数。【西安电子科技大学2000计应用1997

二10分】18.已知一个单链表中每一个结点寄存一个整数

而且结点数很多于2请设计算法以判定该链表中第二项起的

每一个元素值是不是等于其序号的平方减去其前驱的值假

设知足那么返回ture不然返回fal.【西安电子科技大学

2000软件1997二10分】19两个整数序列Aa1a2a3�6�7am

和Bb1b2b3�6�7bn已经存入两个单链表中设计一个算法判

定序列B是不是是序列A的子序列。【东北大学1999二10

分】20L1与L2别离为两单链表头结点地址指针且两表中

数据结点的数据域均为一个字母。设计把L1中与L2中数据

相同的持续结点顺序完全倒置的算法。【东北大学1997四

分】例acabdadadbL1L24类似此题的另外表达有1知L

为链表的头结点地址表中共有mmgt3个结点从表中第i个结

点1ltiltm起到第m个结点组成一个循环部份链表设计将这部

份循环链表中所有结点顺序完全倒置的算法。【东北大学

1998三15分】21.请写一个算法将顺序存储结构的线性

表a1...an逆置为an...a1。【大连海事大学1996八分】类似

此题的另外表达有1设有一带头结点的单链表编程将链表

倒置过来.要求不用另外的数组或结点完成.【南京航空航天

大学1999八10分】2设有一个带头结点的单向链表数据

项递减有序。写一算法从头排列链表使数据项递增有序要求

算法时刻复杂度为On。注用程序实现【南京航空航天大学

1997七12分】3试编写求倒排循环链表元素的算法。【南

京航空航天大学1995十二10分】4请设计算法将不带头

结点的单链表当场逆置。【北方交通大学2001三12分】5

试编写算法将不设表头结点的、不循环的单向链表当场逆

转。【北方交通大学1997五10分】6有一个单链表L至

少有1个结点其头结点指针为head编写一个进程将L逆置

即最后一个结点变成第一个结点原先倒数第二个结点变成

第二个结点如此等等。【燕山大学2001四、28分】22设

有一个由正整数组成的无序向后单链表编写完成以下功能

的算法1找出最小值结点且打印该数值2假设该数值是奇

数那么将其与直接后继结点的数值互换3假设该数值是偶

数那么将其直接后继结点删除。【东北大学2000二15分】

23已知L为没有头结点的的单链表中第一个结点的指针每

一个结点数据域寄存一个字符该字符可能是英文字母字符

或数字字符或其它字符编写算法构造三个以带头结点的单

循环链表表示的线性表使每一个表中只含同一类字符。要求

用最少的时刻和最少的空间【东北大学2002三15分】24

在一个递增有序的线性表中有数值相同的元素存在。假设存

储方式为单链表设计算法去掉数值相同的元素使表中再也

不有重复的元素。例如725170将变作7分析算法的时刻复

杂度。【北京工业大学1996三15分】25在输入数据无

序的情形下成立一个数据值为整型的递增有序的顺序存储

线性表L且要求当输入相同数据值时线性表中不能存在数据

值相同的数据元素试写出其算法。顺序存储结构的线性表

描述为CONSTmaxlen线性表可能达到的最大长度TYPE

sqlisttpRECORDelem:array1..maxlenofintegerlast:0..maxlen

ENDVARL:sqlisttp【同济大学1998二12分】26设有

一个正整数序列组成的有序单链表按递增顺序有序且许诺

有相等的整数存在试编写能实现以下功能的算法要求用最

少的时刻和最小的空间1确信在序列中比正整数x大的数有

几个相同的数只计算一次如序列中比10大的数有5个2在

单链表将比正整数x小的数按递减顺序排列3将正整数比x

大的偶数从单链表中删除。【东北大学2001二17分】27.

编写一个算法来互换单链表中指针P所指结点与其后继结点

HEAD是该链表的头指针P指向该链表中某一结点。【吉林

大学2001二、17分】类似此题的另外表达有1已知非

空线性链表第一个结点由List指出请写一算法互换p所指的

结点与其下一个结点在链表中的位a1a1amL5置设p指向的

不是链表最后那个结点。【北京航空航天大学1999五10

分】2已知任意单链表如下图编者略去图。Head为表头指

针指向表的第一个元素p为指向表中任意结点的指针试设计

一个算法将p指向的结点和其后面结点互换位置可采纳任何

高级语言描述算法。【山东大学1992二12分】28设键

盘输入n个英语单词输入格式为nw1w2�6�7wn其中n表

示随后输入英语单词个数试编一程序成立一个单向链表实

现10分1若是单词重复显现那么只在链表上保留一个。单

考生做。2除知足1的要求外。链表结点还应有一个计数域

记录该单词重复显现的次数然后输出显现次数最多的前

kkltn个单词统考生做。【南京航空航天大学1998九10分】

29已知一双向循还链表从第二个结点至表尾递增有序设

a1ltxltan如以下图“第二个结点至表尾”指a1..an因篇幅所限

编者略去图。试编写程序将第一个结点删除并插入表中适当

位置使整个链表递增有序。【南京航空航天大学1998八10

分】30.已知长度为n的线性表A采纳顺序存储结构请写

一时刻复杂度为0n、空间复杂度为01的算法该算法删除线

性表中所有值为item的数据元素。O1表示算法的辅助空间

为常量。【北京航空航天大学2000五10分】31设民航

公司有一个自动预订飞机票的系统该系统中有一张用双重

链表示的乘客表表中结点按乘客姓氏的字母序相链。例如下

面是张某个时刻的乘客表。试为该系统写出一个当任一乘客

要订票时修改乘客表的算法。序号dataLlinkRlink1Liu65

2Chan493Wang574Bao025Mai136Dong817Xi30

8Deng969Cuang28【北方交通大学2000六17分】32

设有一头指针为L的带有表头结点的非循环双向链表其每一

个结点中除有pred前驱指针data数据和next后继指针域外

还有一个访问频度域freq。在链表被起用前其值均初始化为

零。每当在链表中进行一次LocateLx运算时令元素值为x的

结点中freq域的值增1并使此链表中结点维持按访问频度非

增递减的顺序排列同时最近访问的结点排在频度相同的结

点的最后以便使频繁访问的结点老是靠近表头。试编写符合

上述要求的LocateLx运算的算法该运算为函数进程返回找

到结点的地址类型为指针型。【清华大学1997二10分】33

给定已生成一个带表头结点的单链表设head为头指针结点

的结构为datanextdata为整型元素next为指针试写出算法:按

递增顺序输出单链表中各结点的数据元素并释放结点所占

的存储空间。要求不许诺利用数组作辅助空间【华中理工大

学2000八、213分】34已知三个带头结点的线性链表A、

B和C中的结点均依元素值自小至大非递减排列可能存在两

个以上值相同的结点编写算法对A表进行如下操作使操作

后的链表A中仅留下三个表中均包括的数据元素的结点且

没有值相同的结点并释放所有无用结点。限定算法的时刻复

杂度为Omnp其中m、n和p别离为三个表的长度。【清华

大学1995一15分】6栈和队列1.设有两个栈S1S2都

采纳顺序栈方式而且共享一个存储区O..maxsize-1为了尽可

能利用空间减少溢出的可能可采纳栈顶相向迎面增加的存

储方式。试设计S1S2有关入栈和出栈的操作算法。【哈尔

滨工业大学2001七12分】2.设从键盘输入一整数的序

列a1a2a3�6�7an试编写算法实现用栈结构存储输入的整

数当ai≠-1时将ai进栈当ai-1时输出栈顶整数并出栈。算法

应付异样情形入栈满等给出相应的信息。【南京航空航天

大学1998六10分】3.设表达式以字符形式已存入数组

En中‘’为表达式的终止符试写出判定表达式中括号‘’和‘’是

不是配对的C语言描述算法EXYXE注算法中可挪用栈操作

的大体算法。【北京科技大学2001九、110分】4.从键

盘上输入一个逆波兰表达式用伪码写出其求值程序。规定逆

波兰表达式的长度不超过一行以符作为输入终止操作数之

间用空格分隔操作符只可能有、-、、/四种运算。例如234342

【山东师范大学1999七10分】5.假设以I和O别离表

示入栈和出栈操作。栈的初态和终态均为空入栈和出栈的操

作序列可表示为仅由I和O组成的序列称能够操作的序列为

合法序列不然称为非法序列。1下面所示的序列中哪些是合

法的A..