递增的次序进行就地排序.【中科院计算所 1999 五、1（10分）】
7. 设 Listhead为一单链表的头指针，单链表的每个结点由一个整数域DATA和指针域NEXT组成，整数在单链表中是无序的。编一PASCAL过程，将 Listhead链中结点分成一个奇数链和一个偶数链，分别由P,Q指向，每个链中的数据按由小到大排列。程序中不得使用 NEW过程申请空间。【山东大学1993六( 15分)】
类似本题的另外叙述有：
（1）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。【北京理工大学 2000 四、2（4分）】
(2) 设L为一单链表的头指针，单链表的每个结点由一个整数域 data和指针域NEXT组成，整数在单链表中是无序的。设计算法，将链表中结点分成一个奇数链和一个偶数链，分别由P，Q指向，每个链中的数据按由小到大排列，算法中不得申请新的结点空间。【青岛海洋大学 1999 三（12分）】
(3) 将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。 1) 写出其类型定义： 2) 写出算法。【山东大学 1998 九 (9分)】 【山东工业大学 2000 九（9分）】
8. 已知线性表（a1 a2 a3 ?an）按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x ?x）变为（-x,-x,-x?x,x,x）。
【东北大学 1998 二 (15分)】
类似本题的另外叙述有：
（1）设有一元素为整数的线性表L=(a1,a2,a3,?,an),存放在一维数组A[N]中,设计一个算法,以表中an作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于an,右半部分每个元素都大于an, an位于分界位置上(要求结果仍存放在A[N]中)。【北京理工大学 1999 八（6分）】
（2）顺序存储的线性表A,其数据元素为整型,试编写一算法,将A拆成B和C两个表,使A中元素值大于等于0的元素放入B,小于0的放入C中.. 要求:
1）表B和C另外设置存储空间;
2）表B和C不另外设置,而利用A的空间.【山东大学 2001 九、1 (12分)】 （3）知线性表（a1, a2,a3,?,an）按顺序存储，且每个元素都是整数均不相同，设计把所有奇数移到所有偶数前边的算法。（要求时间最少，辅助空间最少）【东北大学 1997 三 (15分)】
(4) 编写函数将一整数序列中所有负数移到所有正数之前，要求时间复杂度为O（n）
【南京航空航天大学 2001 八（10分）】
(5) 已知一个由n（ 设n=1000）个整数组成的线性表，试设计该线性表的一种存储结构，并用标准pascal语言描述算法，实现将n个元素中所有大于等于19的整数放在所有小于19的整数之后。要求算法的时间复杂度为O(n),空间复杂度O(1)。【西安交通大学 1996 六（11分）】
9. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。void delete（Linklist &L）
【北京理工大学 2001 九、3 （8分）】
10. 已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。【北京航空航天大学 2001 四（10分）】
11. 已知p指向双向循环链表中的一个结点，其结点结构为data、llink、rlink三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。【首都经贸大学 1997 二、2（15分）】
12. 线性表(a1,a2,a3,?,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法完成： （1） 用最少时间在表中查找数值为x的元素。 （2） 若找到将其与后继元素位置相交换。
（3） 若找不到将其插入表中并使表中元素仍递增有序。【东北大学 1996 三 ( 12分)】
13. 设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。写出算法dc(h,n),判断该链表的前n个字符是否中心对称。例如 xyx, xyyx都是中心对称。【首都经贸大学1998三、9（15分）】 14. 已知两个单链表A和B,其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。
【中国矿业大学 2000 三（10分）】
类似本题的另外叙述有：
（1）h1、h2为两个链表的表头指针，结点结构为data和link两个域组成。写出算法inde(h1,h2,i,j,l),将链表h1
从第i个结点起的l个结点删除，并插入到h2表的第j个结点之前。
【首都经贸大学 1998 三、10（20分）】
15. 设线性表存于A[1..size]的前num各分量中，且递增有序。请设计一个算法，将x插入到线性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。
【西安电子科技大学 1999计应用 1997 二 （10分）】
类似本题的另外叙述有：
(1) 试编制在线性表L={12,13,21,24,28,30,42,}中插入数据元素26的程序。（要求该程序用turbo Pascal语言编制并能在计算机上运行，结点类型为链式结构）【大连海事大学 1996 二、1 (16分)】
16. 假设一个单循环链表，其结点含有三个域pre、data、link。其中data为数据域；pre为指针域，它的值为空指针（NIL）；link为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。
【西安电子科技大学 1999软件 五（10分）】
17. 已知递增有序的单链表A,B分别存储了一个集合，请设计算法以求出两个集合A和B 的差集A-B（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。
【西安电子科技大学2000计应用1997 二 （10分）】
18. 已知一个单链表中每个结点存放一个整数，并且结点数不少于2，请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture，否则返回false.
【西安电子科技大学2000软件1997 二（10分）】
19．两个整数序列A=a1,a2,a3,?,am和B=b1,b2,b3,?,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。【东北大学 1999 二 (10分)】
20．L1与L2分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个字母。设计把L1中与L2中数据相同的连续结点顺序完全倒置的算法。【东北大学 1997 四 (１５分)】
L1acabdad?例：
L2abd?
类似本题的另外叙述有：
(1) 知L为链表的头结点地址，表中共有m(m>3)个结点，从表中第i个结点(1 L ama1a1 【东北大学 1998 三 (15分)】 21. 请写一个算法将顺序存储结构的线性表（a1...an）逆置为(an...a1)。【大连海事大学1996八(６分)】 类似本题的另外叙述有： (1) 设有一带头结点的单链表,编程将链表颠倒过来.要求不用另外的数组或结点完成. 【南京航空航天大学 1999 八 （10分）】 (2) 设有一个带头结点的单向链表，数据项递减有序。写一算法，重新排列链表，使数据项递增有序，要求算法时间复杂度为O（n）。（注：用程序实现）【南京航空航天大学 1997 七 （12分）】 (3) 试编写求倒排循环链表元素的算法。【南京航空航天大学 1995 十二 （10分）】 (4) 请设计算法将不带头结点的单链表就地逆置。【北方交通大学 2001 三 （12分）】 (5) 试编写算法 ，将不设表头结点的、不循环的单向链表就地逆转。【北方交通大学1997五（10分）】 (6) 有一个单链表L（至少有1个结点），其头结点指针为head，编写一个过程将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。【燕山大学 2001 四、2（8分）】 22．设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法： （1）找出最小值结点，且打印该数值； （2）若该数值是奇数，则将其与直接后继结点的数值交换； （3）若该数值是偶数，则将其直接后继结点删除。【东北大学 2000 二 (15分)】 23．已知L为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符或数字字符或其它字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符。（要求用最少的时间和最少的空间）【东北大学 2002 三(15分)】 24．在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使 表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70），分析算法的时间复杂度。【北京工业大学 1996 三 (15分)】 25．在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。 顺序存储结构的线性表描述为： CONST maxlen={线性表可能达到的最大长度}； TYPE sqlisttp=RECORD elem:array[1..maxlen] of integer; last :0..maxlen END; VAR L: sqlisttp;【同济大学 1998 二 (12分 )】 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. 编写一个算法来交换单链表中指针P所指结点与其后继结点，HEAD是该链表的头指针，P指向该链表中某一结点。【吉林大学 2001 二、1 (7分)】 类似本题的另外叙述有： (1) 已知非空线性链表第一个结点由List指出，请写一算法，交换p所指的结点与其下一个结点在链表中的位置(设p指向的不是链表最后那个结点)。【北京航空航天大学 1999 五 （10分）】 (2) 已知任意单链表如图所示(编者略去图)。Head为表头指针，指向表的第一个元素，p为指向表中任意结点的指针，试设计一个算法，将p指向的结点和其后面结点交换位置（可采用任何高级语言描述算法）。 【山东大学 1992 二 ( 12分)】 28．设键盘输入n个英语单词，输入格式为n, w1, w2, ?,wn,其中n表示随后输入英语单词个数，试编一程序，建立一个单向链表，实现：（10分） （1）如果单词重复出现，则只在链表上保留一个。（单考生做）。 （2）除满足（1）的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k<=n)个单词（统考生做）。【南京航空航天大学 1998 九 （10分）】 29．已知一双向循还链表，从第二个结点至表尾递增有序，（设a1 【北京航空航天大学 2000 五（10分）】 31．设民航公司有一个自动预订飞机票的系统，该系统中有一张用双重链表示的乘客表，表中结点按乘客姓氏的字母序相链。例如，下面是张某个时刻的乘客表。试为该系统写出一个当任一乘客要订票时修改乘客表的算法。 序号 data Llink Rlink 1 Liu 6 5 2 Chan 4 9 3 Wang 5 7 4 Bao 0 2 5 Mai 1 3 6 Dong 8 1 7 Xi 3 0 8 Deng 9 6 9 Cuang 2 8 【北方交通大学 2000 六（17分）】 32．设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针），data（数据）和next （后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。【清华大学 1997 二 （10分）】 33．给定(已生成)一个带表头结点的单链表，设head为头指针，结点的结构为(data,next),data为整型元素，next为指针，试写出算法:按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。(要求;不允许使用数组作辅助空间)【华中理工大学 2000 八、2 （13分）】 34．已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n和p分别为三个表的长度。【清华大学 1995 一 （15分）】 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第二章线性表(4)在线全文阅读。
相关推荐：