算法设计题打印部分.docx
- 文档编号:14452311
- 上传时间:2023-06-23
- 格式:DOCX
- 页数:7
- 大小:22.20KB
算法设计题打印部分.docx
《算法设计题打印部分.docx》由会员分享,可在线阅读,更多相关《算法设计题打印部分.docx(7页珍藏版)》请在冰点文库上搜索。
算法设计题打印部分
算法设计题打印部分
假设有两个按元素值递增次序排列的线性表均以单链表形式存储。
请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表并要求利用原来两个单链表的结点存放归并后的单链表。
【北京大学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.知L1、L2分别为两循环单链表的头结点指针mn分别为L1、L2表中数据结点个数。
要求设计一算法用最快速度将两表合并成一个带头结点的循环单链表。
【东北大学1996二12分】类似本题的另外叙述有1试用类Pascal语言编写过程PROCjoinVARlalinklblink实现连接线性表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.试编写在带头结点的单链表中删除一个最小值结点的高效算法。
voiddeleteLinklistampL【北京理工大学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分】类似本题的另外叙述有1h1、h2为两个链表的表头指针结点结构为data和link两个域组成。
写出算法indeh1h2ijl将链表h1从第i个结点起的l个结点删除并插入到h2表的第j个结点之前。
【首都经贸大学1998三、1020分】15.设线性表存于A1..size的前num各分量中且递增有序。
请设计一个算法将x插入到线性表的适当位置上以保持线性表的有序性并在设计前说明设计思想最后说明所设计算法的时间复杂度。
【西安电子科技大学1999计应用1997二10分】类似本题的另外叙述有1试编制在线性表L283042中插入数据元素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否则返回false.【西安电子科技大学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在一个递增有序的线性表中有数值相同的元素存在。
若存储方式为单链表设计算法去掉数值相同的元素使表中不再有重复的元素。
例如5170将变作25170分析算法的时间复杂度。
【北京工业大学1996三15分】25在输入数据无序的情况下建立一个数据值为整型的递增有序的顺序存储线性表L且要求当输入相同数据值时线性表中不能存在数据值相同的数据元素试写出其算法。
顺序存储结构的线性表描述为CONSTmaxlen线性表可能达到的最大长度TYPEsqlisttpRECORDelem:
array1..maxlenofintegerlast:
0..maxlenENDVARL:
sqlisttp【同济大学1998二12分】26设有一个正整数序列组成的有序单链表按递增次序有序且允许有相等的整数存在试编写能实现下列功能的算法要求用最少的时间和最小的空间1确定在序列中比正整数x大的数有几个相同的数只计算一次如序列204中比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设民航公司有一个自动预订飞机票的系统该系统中有一张用双重链表示的乘客表表中结点按乘客姓氏的字母序相链。
例如下面是张某个时刻的乘客表。
试为该系统写出一个当任一乘客要订票时修改乘客表的算法。
序号dataLlinkRlink1Liu652Chan493Wang574Bao025Mai136Dong817Xi308Deng969Cuang28【北方交通大学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..
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 设计 打印 部分