问答题

假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998三、1(5分)】【厦门大学2006 1(3)(20／3分)】

答案：正确答案：pla一>next ； q=lb一>next；／／p，q分别是链表1a和1b的工作指针 la一>next：n...

你可能感兴趣的试题

已知一个带有表头结点的单链表，结点结构为(data，link)，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)，若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0，要求：(1)描述算法的基本设计思想；(2)描述算法的详细实现步骤；(3)根据设计思想和实现步骤，采用程序设计语言描述算法(使用C或C++或Java语言实现)，关键之处请给出简要注释。【2009年全国试题42(15分)】

答案：正确答案：“倒数”和“正数”是相对概念。如战士站队报数从1到10，排头1若从反向报数则是10。本题设指针q指向链表，指针...

一个长度为L(L≥1)的升序序列S，处在第[L／2]个位置的数称为S的中位数。例如列S1=(11，13，15，17，19)，则S1中的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若92=(2，4，6，8，20)，则．S1和S2的中位数是11。现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度【2011年全国试题42(15)分】

答案：正确答案：中位数是指长度为L(L≥1)的序列S，在排序后处在第[L／2]个位置的数。一般的叙述是：不用全部排序，找出第j...

假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如下图所示。
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为
。请设计一个时间上尽可能高效的算法，找出由str1和str2所指的两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度。[2012年全国试题42(13分)】

答案：正确答案：找两个单词的共同后缀，应从两个单词的词尾向前找，找到最前边那个相同的字母，就找到了共同后缀。由于本题中单词以单...

用单链表保存m个整数，结点的结构为(data，link)，且｜data｜要求： (1)给出算法的基本思想。 (2)使用C或C++语言，给出单链表结点的数据类型定义。 (3)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。 (4)说明所涉及算法的时间复杂度和空间复杂度。

答案：正确答案：算法思想是，若按常规从第一个结点找到最后一个结点，把和第一个结点数据绝对值相同的删除，再删除和第二个结点数据绝...

假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998三、1(5分)】【厦门大学2006 1(3)(20／3分)】

答案：正确答案：pla一>next ； q=lb一>next；／／p，q分别是链表1a和1b的工作指针 la一>next：n...

已知L1、L2分别为两循环单链表的头结点指针，m、n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。【东北大学1996二(12分)】

答案：正确答案：循环单链表L1和L2数据结点个数分别为m和n，将二者合成一个循环单链表时，需要将一个循环链表的结点(从第一元素...

设有两个链表，ha为单向链表，hb为单向循环链表。编写算法，将两个链表合并成一个单向链表，要求算法所需时间与链表长度无关。【南京航空航天大学1997四(8分)】

答案：正确答案：将单向链表ha和单向循环链表hb合并成一个单向链表，要求算法所需时间与链表长度无关，只有使用带尾指针的循环单链...

已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点)，编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O(m+n+p)，其中m、n和p分别为三个表的长度。【清华大学1995一(15分)】

答案：正确答案：要求留下三个链表中的公共数据，首先查找两表A和B中的公共数据，再去C中查找有无该数据。要消除重复元素，应记住前...

已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。(O(1)表示算法的辅助空间为常量)。【北京航空航天大学2000五(10分)】【天津大学2005八(10分)】

答案：正确答案：在顺序表上删除元素，要大量移动元素。为满足时间复杂度为O(n)，设头尾两个指针(i=0， j=n一1)，从两端...

顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性表空间足够大。试用类Pascal语言给出一种高效算法，将LB中元素合并到LA中，使新LA的元素仍保持非递减有序。高效指最大限度地避免移动元素。【北京工业大学1997一、2(12分)】

答案：正确答案：顺序表的插入的时间复杂度为O(n)，平均移动近一半的元素。设两线性表的长度各为m和n，应从线性表的最后一个元素...

已知消费总金额，请设计一个发票打印程序，打印输出的发票金额单位为：千百十元。【南京航空航天大学2004三、3(8分)】

答案：正确答案：这里要用整除(／)得到千、百、十、元等数据。设总金额N，则i=N／1000得到千的个数，j=(N-i*1000...

写算法将单链表L1拆成两个链表，其中以L1为头的链表保持原来向后的链接，另一个链表的头为L2，其链接方向与L1相反，L1包含原链表的奇数序号的结点，L2包含原链表的偶数序号的结点。【东华大学2004三(10分)】

答案：正确答案：现给出核心语句段如下： int i=0； L2：new(LNode)；／／i表示结点序号，增加一个表头结点L...

试编写在带头结点的单链表中删除(一个)最小值结点的(高效)算法void delete(Linklist＆L)。【北京理工大学2001九、3(8分)】

答案：正确答案：1ist一>link； pre=1ist；／／p指向待处理结点，pre指向最小值结点的前驱 q=p；／／q...

用类C／C++设计算法，判断一个带表头结点的双向循环链表DL(DuIJnkList)是否对称相等。 (比如，表(25，34，34，25)和表(25，3，25)为对称的。)【南京理工大学2005三(5分)】其中结点结构为：struct Node{E1emType data；／／ElemType代表某种抽象数据类型NodeLlink， R1ink；}；

答案：正确答案：while(p!=q&&P一>Rlink!=q) if(p一>data==q一>data){p=p一>Rlin...

已知两个单链表A和B，其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入单链表B的第j个元素之前。【中国矿业大学2000三(10分)】

答案：正确答案：将链表A第i一1个结点的指针域指向第i+len个结点，从第i个结点起，逐个回收空间。继续查到A的尾结点，得到删...

假设一个单循环链表，其结点含有三个域pre、data、link。其中data为数据域；pre为指针域，它的值为空指针(NIL)；link为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。【西安电子科技大学1999软件五(10分)】

答案：正确答案：循环链表的处理要保证每个结点处理一次且仅一次。核心语句段如下： while(1a一>link一>pre==nu...

已知一个单链表中每个结点存放一个整数，并且结点数不少于2，请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture，否则返回false。【西安电子科技大学2000软件二(10分)】

答案：正确答案：判断结点的元素值是否等于其序号的平方减去其前驱的值，主要技术问题是结点的序号和前驱及后继指针的正确指向。核心语...

两个整数序列A=a1，a2，a3，…，am和B=b1，b2，b3，…，bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。【东北大学1999二(10分)】

答案：正确答案：操作从两链表的第一个结点开始，若对应数据相等，则后移指针；若对应数据不等，则A链表从上次开始比较结点的后继开始...

L1与L2分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个字母。设计把L1中与L2中数据相同的连续结点顺序完全倒置的算法。【东北大学1997四(15分)】例：

答案：正确答案：应先找出链表L2在链表L1中的出现，然后将L1中的L2倒置过来。设L2在L1中出现时第一个字母结点前驱的指针为...

已知L为链表的头结点地址，表中共有m(m>3)个结点，从表中第i个结点(1＜i＜m)起到第m个结点构成一个循环部分链表，设计将这部分循环链表中所有结点顺序完全倒置的算法。【东北大学1998三(15分)】

答案：正确答案：查第i个结点，记下第i个结点的指针。然后从第i+1个结点起，直至第m(1

请写一个算法将顺序存储结构的线性表(a ₁ …a _n )逆置为(a _n …a ₁ )。【大连海事大学1996八(6分)】

答案：正确答案：for(i=0 ; i<=(n一1)／2 ; i++)a[i](一->a [n一1一i];

写出一个从表尾到表头的逆向建立单链表的算法。【中科院研究生院2004三(7分)】

答案：正确答案：while(P!：null) ／／head是链表头结点的指针，P初值指向第一元素结点 {r=P一>next ；...

试编写求倒排循环链表元素的算法。【南京航空航天大学1995十二(10分)】

答案：正确答案：题是循环链表的逆置。与逆置单链表有两点不同。一是初始化成循环链表而不是空链表；二是判断链表尾不用空指针而用链表...

已知一带头结点的递增有序单链表，请在原结点上将其倒序。【南京航空航天大学2004二、4(12分)】

答案：正确答案：while(P!：null) ／／head是链表头结点的指针，P初值指向第一元素结点 {r=P一>next ；...

编写逆向输出不带头结点的单向链表中数据域的递归算法。设表中有4个结点，从表头至表尾其数据域分别为10，30，20，40，作图表示出该算法的执行过程。设该链表的结点的数据类型的名称为list，结点的数据域和指针域的名称分别为data和next，不必写出list的定义。【中南大学2005四、3(10分)】

答案：正确答案：void Output(LinkedList list)／／本算法逆序输出链表list各结点的值 {if(1i...

已知p是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表(a ₁ ，a ₂ ，…，a _n-1 ，a _n )改造为(a ₁ ，a ₂ ，…，a _n-1 ，a _n ，a _n-1 ，…，a ₂ ，a ₁ )。【北京理工大学2005十四、1(5分)】

答案：正确答案：题的结果链表是以a_n为对称的。由尾指针p找到第一元素结点，复制结点并插入原尾结点的后面。...

在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：(7，10，10，21，30，42，42，42，51，70)将变作(7，10，21，30，42，51，70)，分析算法的时间复杂度。【北京工业大学1996三(15分)】

答案：正确答案：非递减有序(原题称为递增有序)单链表删除重复元素的核心语句段如下： while(p) ／／pre是P所指向结点...

已知带头结点的单链表有data和next两个域，设计一个算法，将该链表中的重复元素结点删除。【北京邮电大学2005五、2(10分)】【苏州大学2005三(15分)】

答案：正确答案：本题并未说单链表有序，因此要依次从每个结点出发，遍历整个链表，删除重复元素。删除结点要记住被删结点的前驱，不能...

设有一个正整数序列组成的有序单链表(按递增次序有序，且允许有相等的整数存在)，试编写能实现下列功能的算法：(要求用最少的时间和最小的空间。)(1)确定在序列中比正整数x大的数有几个(相同的数只计算一次，如序列{20，20，17，16，15，15，11，10，8，7，7，5，4}中比10大的数有5个)；(2)在单链表中将比正整数x小的数按递减次序排列；(3)将正整数(比)x大的偶数从单链表中删除。【东北大学2001二(17分)】

答案：正确答案：确定比正整数x大的数有几个属于计数问题，相同数只计一次，要求记住前驱，前驱和后继值不相等时移动前驱指针，进行计...

编写一个算法来交换单链表中指针尸所指结点与其后继结点，HEAD是该链表的头指针，P指向该链表中某一结点。【吉林大学2001二、1(7分)】

答案：正确答案：单链表中查找任何结点，都必须从头指针开始。将指针P所指结点与其后继结点交换，必须先找到P的前驱结点的指针。核心...

设键盘输入n个英语单词，输入格式为n，w₁，w₂，…，w_n，其中n表示随后输入英语单词的个数，试编一程序，建立一个单向链表，实现：(1)如果单词重复出现，则只在链表上保留一个。(2)除满足(1)的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k(k≤n)个单词。

答案：

已知一双向循环链表，从第二个结点至表尾递增有序(设a ₁ ＜x＜a _n )(x是第一个结点的值， “第二个结点至表尾”指a ₁ …a _n ，因篇幅所限，编者略去图)。试编写程序，将第一个结点删除并插入表中适当位置，使整个链表递增有序。【南京航空航天大学1998八(10分)】

答案：正确答案：将第一个结点先从链表中摘下，查找插入位置。核心语句段如下：s=1a：／／s暂存第一结点的指针，链表无头结点 p...

设民航公司有一个自动预订飞机票的系统，该系统中有一张用双重链表示的乘客表，表中结点按乘客姓氏的字母序相链接。例如，下面是张某个时刻的乘客表。试为该系统写出一个当任一乘客要订票时修改乘客表的算法。【北方交通大学2000六(17分)】

答案：正确答案：本题所用数据结构是静态双向链表，其结构定义为： typedef struct node {char data[...

【简答题】设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针）、data（数据）和next（后继指针）域外，还有一个访问频度域freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate（L，x）运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate（L，x）运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。

答案：正确答案：先查找x，若失败，则在链表尾插入；若查找成功，则域freq增1。将该结点暂从链表上摘下，按域freq值向前查找...

给定(已生成)一个带表头结点的单链表，设head为头指针，结点的结构为(dam，next)，dam为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间。(要求：不允许使用数组作辅助空间。)【华中理工大学2000八、2(13分)】

答案：正确答案：对链表进行遍历，在每趟遍历中查找出整个链表的最小值元素，输出并释放结点所占空间；再查次最小值元素，输出并释放空...

编写程序，要求完成：(1)建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。(2)在此链表上实现对二进制数加1的运算，并输出运算结果。【西北大学2002七(10分)】

答案：正确答案：为处理方便，结点数据为字符型，用带头结点的双循环链表存储。用尾插法建立链表。实现二进制数加1的运算时，若尾结点...

设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移P(0＜0 0，X₁，…，X_n-1)变换为(X_P2，X_P+1，…，X_n-1，X₀，X₁，…，X_P-1)。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。【2010年全国试题42(13分)】

答案：正确答案：一次左移一位，循环尼次；设置另一数组，按要求复制到该数组；这里推荐按照下标0到p—1、p到n—1、0到n一1的...