当前位置： >
设头指针为head，并设带头结点的单链表中的数据元素递增有序，编写算法将数据元素x插入到适当位置上，要求插入后保持单链表数据元素的递增有序。
所属学科：
试题类型：主观题
所属知识点：
试题分数：10.0 分
暂未组卷。
暂无学习笔记。
&&&&&&&&&&&&&&&希赛网 版权所有 & &&数据结构课程设计分类题目
线性表 顺序表： 1、设有一元素为整数的线性表L=(a1,a2,a3,?,an),存放在一维数组A[N]中,设计一个算法,以表中an作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于an,右半部分每个元素都大于an, an位于分界位置上(要求结果仍存放在A[N]中)。 2、设线性表存于A[1..size]的前num各分量中，且递增有序。请设计一个算法，将x插入到线性表的适当位置上，以保持线性表的有序性。 3、线性表(a1,a2,a3,?,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法完成： （1） 用最少时间在表中查找数值为x的元素。 （2） 若找到将其与后继元素位置相交换。 （3） 若找不到将其插入表中并使表中元素仍递增有序。 4、已知数组A[0:n-1]的元素类型为int，试设计算法将其调整为左右两个部分，左边所有元素为奇数，右边所有元素为偶数。 5、设计一个算法从顺序表L中删除所有值为x的元素 6、设计一个算法从顺序表L中删除所有值为x到y之间（x<=y）的元素 链表： 1、假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。 2、已知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。 3、设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，设计一个将该链表整理成数据递增的有序单链表的算法。 5、设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。 6、试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。 7、设L为单链表的头结点地址，请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。 8、已知两个单链表A和B,其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。 9、已知递增有序的单链表A,B分别存储了一个集合，请设计算法以求出两个集合A和B 的差集A-B（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。 10、 已知一个单链表中每个结点存放一个整数，并且结点数不少于2，请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture，否则返回false.
11、两个整数序列A=a1,a2,a3,?,am和B=b1,b2,b3,?,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。 12、已知p指向双向循环链表中的一个结点，其结点结构为data、llink、rlink三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。 13、设有一个由正整数组成的无序单链表，编写完成下列功能的算法： （1）找出最小值结点，且打印该数值； （2）若该数值是奇数，则将其与直接后继结点的数值交换； （3）若该数值是偶数，则将其直接后继结点删除。 14、在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70）。 15、设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法 ：（要求用最少的时间和最小的空间） (1)确定在序列中比正整数x大的数有几个（相同的数只计算一次，如序列{20,20,17,16,15,15,11,10,8,7,7,5,4}中比10大的数有5个）； (2) 在单链表将比正整数x小的数按递减次序排列； (3) 将正整数（比）x大的偶数从单链表中删除。 16、编写一个算法来交换单链表中指针P所指结点与其后继结点，HEAD是该链表的头指针，P指向该链表中某一结点。 17、．已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n和p分别为三个表的长度。
栈和队列 1、 设计一个算法，利用栈的基本运算将指定栈中的内容逆转。 2、 设计一个算法，利用栈的基本运算返回指定栈中栈底元素。 3、设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。 4、设从键盘输入一整数的序列：a1, a2, a3，?，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。 4、设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。)
5、 从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$ 6、写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。 7、设计一个算法，判断一个算术表达式中的括号是否配对。算术表达式保存在带头结点的单循环链表中，每个结点有两个域：ch和link，其中ch域为字符类型。 8、请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列； dequeue:删除一个元素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释） 9、 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，如图所示（编者略），请写出相应的入队列和出队列算法。 10、如果允许在循环队列的两端都可以进行插入和删除操作。要求： （1）写出循环队列的类型定义；（2）写出“从队尾删除”和“从队头插入”的算法。 11、在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针域next），请给出这种队列的入队和出队操作的实现过程。 12、已知Q是一个非空队列，S是一个空栈。仅用队列和栈的操作编写一个算法，将队列Q中的所有元素逆置。
13、已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若n等于零，则返回m；第二步：若m小于n，则m与n相互交换；否则，保存m，然后将n送m，将保存的m除以n的余数送n。
（1）将上述过程用递归函数表达出来（设求x除以y的余数可以用x MOD y 形式表示）。 （2）写出求解该递归函数的非递归算法。 14、试将下列递归过程改写为非递归过程。
scanf(x)；
if(x=0) sum=0 else {test(sum); sum+=x;}
printf(sum)；
树和二叉树 1、二叉树用二叉链表存储，写一个算法将二叉树中的叶子结点按从右至左的顺序建立一个单链表。 2、知二叉树用二叉链表存储，写出求二叉树宽度的算法。所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。 3、叉树用二叉链表存储，写一个算法交换各结点的左右子树。 4、二叉树用二叉链表存储，若结点的左孩子的数据域的值大于右孩子数据域的值，则交换其左右子树。 5、 叉树用二叉链表存储，编写一算法，判别给定的二叉树是否为完全二叉树。 6、 个结点的完全二叉树以一维数组为存储结构，编写一非递归算法实现对该树的先序遍历。 7、编写一算法，在二叉树中查找值为x的结点，并打印值为x的结点的所有祖先结点。 8、编写中序遍历二叉树的非递归算法。 9、编写先序遍历二叉树的非递归算法。 10、编写后序二叉树的非递归算法。 11、叉树用二叉链表存储，任给一个二叉树表示的四则运算表达式，编写算法，由该二叉树输出该表达式，若原表达式有括号亦加上。 12、有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树 ，根由tree指向。 13、二叉树排序方法如下： （1）将第一个数据放在树根。
（2）将随后读入的数据与树根中的数据相比较，若比树根大，则置于右子树，反之则置于左子树，建成一棵二叉树； （3）利用中序遍历打印排序结果。 用C语言编写二叉树的排序程序。 14、二叉树结点的平衡因子（bf）定义为该结点的左子树高度与右子树高度之差。编写算法计算二叉树中各个结点的平衡因子。 15、设计算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数目。 16、已知二叉树以二叉链表存储，编写算法完成：对于树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 17、试编写算法，对一棵以孩子―兄弟链表表示的树统计叶子的个数。 18、设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组pre[1..n ]和mid[1..n ]中，试遍写算法建立该二叉树的二叉链表。 19、试设计一个算法打印出由根结点出发到达叶结点的所有路径。 20、试写出算法，求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。 21、给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为huffman 树。编写构造huffman 树 的算法。 22、已知一中序线索二叉树,写一算法完成对它的中序扫描。 23、已知中序线索二叉树T右子树不空。设计算法，将S所指的结点作为T的右子树中的一个叶子结点插入进去，并使之成为T的右子树的（中序序列）第一个结点（同时要修改相应的线索关系）。 24、写出算法，求出中序线索二叉树中给定值为x的结点之后继结点，返回该后继结点的指针。线索树中结点结构为：（ltag,lc,data,rc,rtag）。其中，data存放结点的值；lc，rc为指向左、右孩子或该结点前驱或后继的指针；ltag，rtag为标志域，各值为：0，则lc，rc为指向左、右孩子的指针；值为1，则lc，rc为指向某前驱后继结点的指针 25、设后序线索树中结点构造为(Ltag,Lchild,Data,Rchild,Rtag)。其中:Ltag,Rtag 值为0时,Lchild、Rchild 分别为儿子指针；否则分别为直接前驱,直接后继的线索。请写出在后序线索树上找给定结点p^ 的直接前驱q 的算法。
联系客服：cand57</数据结构练习第二章_线性表-海文库
全站搜索：
您现在的位置：&>&&>&其它考试
数据结构练习第二章_线性表
数据结构练习 第二章 线性表一、选择题
1. 下面关于线性表的叙述错误的是（
）。A.线性表采用顺序存储必须占用一片连续的存储空间B. 线性表采用链式存储不必占用一片连续的存储空间C. 线性表采用链式存储便于插入和删除操作的实现D. 线性表采用顺序存储便于插入和删除操作的实现2. 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（
）。A.q=p-&next；p-&data=q-&data；p-&next=q-&next；free(q)；B. q=p-&next；q-&data=p-&data；p-&next=q-&next；free(q)；C. q=p-&next；p-&next=q-&next；free(q)；D. q=p-&next；p-&data=q-&data；free(q)；3. 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（
）。A. O(n)
B. O(nlog2n)
D. O(n2)4．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（
）。2A. O(log2n)
D. O(n)5．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（
）。A. head==0 B.head-&next==0C. head-&next==head
D.head!=06．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（
）。A. head==0
B. head-&next==0C. head-&next==head
D. head!=07．建立一个长度为n的有序单链表的时间复杂度为（
D. O(log2n)8．设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（
）个元素。A. n-i
D. i9．设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（
）。A. p-&right=s； s-&left=p； p-&right-&left=s； s-&right=p-&right；B. s-&left=p；s-&right=p-&right；p-&right=s； p-&right-&left=s；C. p-&right=s； p-&right-&left=s； s-&left=p； s-&right=p-&right；D. s-&left=p；s-&right=p-&right；p-&right-&left=s； p-&right=s；10．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（
）存储方式最节省运算时间。A. 单向链表
B .单向循环链表C. 双向链表
D. 双向循环链表111．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（
）。A. s-&next=p-&next；p-&next=-s； B. q-&next=s； s-&next=p；C. p-&next=s-&next；s-&next=p；
D. p-&next=s；s-&next=q；12．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从后向前依次后移（
）个元素。A．n-i
D．i13．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（
）。A. q-&next=p-&p-&next=q;B. p-&next=q-&q=p;C. q-&next=p-&p-&next=q;D. p-&next=q-&q-&next=p;14．在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（
）A.直接前趋
B.直接后继 C.开始结点
D.终端结点15．将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（
B.2n-1 C.2n
D.n216．线性表采用链式存储结构时，要求内存中可用存储单元的地址(
)A. 必须是连续的
B. 必须是部分连续的C. 一定是不连续的
D. 连续和不连续都可以17．设h是指向非空带表头结点的循环链表的头指针，p是辅助指针。执行程序段p=h;while (p-&next-&next!=h)p=p-&p-&next=h;后（其中，p-&next为p指向结点的指针域），则(
)A. p-&next指针指向链尾结点
B. h指向链尾结点C. 删除链尾前面的结点
D. 删除链尾结点18．设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为(
D.24519．设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为(
D.920．设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示p指针所指向结点的表达式是(
)A.p→llink
B.p→rlinkC.p→llink→llink
D.p→llink→rlink21．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元 2素的存储地址是(
D. 12022．关于存储相同数据元素的说法中正确的是（
）A．顺序存储比链式存储少占空间B.顺序存储比链式存储多占空间C.顺序存储和链式存储都要求占用整块存储空间D.链式存储比顺序存储难于扩充空间23．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（
）A．q→next=s；p→next=s； B.q→next=s；s→next=p；C.q→next=s；q→next=p；
D.q→next=s；s→next=q；24．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（
）A．O(n) B.O(1)C.O(log2n)
D.O(n2)25．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（
）A.单链表
B.仅有头指针的单循环链表C.双链表
D.仅有尾指针的单循环链表26．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（
D.i27．对于长度为n的顺序表执行删除操作，则其结点的移动次数（
）A.最少为0，最多为n B.最少为1，最多为nC.最少为0，最多为n-1 D.最少为1，最多为n-128．在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是（
）A. p-&next=q B. p-&next=q-&nextC. p=q-&next D. p-&next=q-&next-&next29．在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（
）A．O（1）
B．O（n）C．O（nlog2n）
D．O(n2)30．顺序存储的线性表（a1,a2,?,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（
B．n/2C．n+1
D．(n+1)/231．设单链表中指针p指向结点A，若删除A后的结点存在，则需要修改指针的操作为（
）。A．p-&next=p-&next-&next
B．p=p-&nextC．p=p-&next-&next
D．p-&next=p32．线性表的链式存储实现有利于（
）运算。A．插入
B．读表元C．查找
D．定位33．从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动（
） 3个元素。A．n-i
B．n-i+1C．n-i-1
D．i34．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动（
）个元素。A．n-i
B．n-i+1C．n-i-1
D．i35．在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则需执行（
）。A．s-&next=p-& p-&next=s;
B．q-&next=s; s-&next=p;C．p-&next=s-& s-&next=p;
D．p-&next=s; s-&next=q;36．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（
）。A.HL =
p-&next = HL;B.p-&next = HL;
HL =C.p-&next = HL;
p = HL;D.p-&next = HL-&
HL-&next =37．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（
）。A.p = q-&
p-&next = q-&B.p = q-&
q-&next =C.p = q-&
q-&next = p-&D.q-&next = q-&next-&
q-&next =38．线性表采用链式存储时，其地址（
）。A．必须是连续的
B．部分地址必须是连续的C．一定是不连续的
D．连续与否均可以39．在一个长度为n的线性表中插入第i个元素的操作中，i的取值范围是A．1≤i≤n
B．0≤i≤n
C．1≤i≤ n+1
D．1≤i≤n-140．如果要查找单链表中的第i个元素，应该从（
）开始进行查找。A．第i个结点
B． 头结点
C． 尾结点
D． 任意一个结点41．在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为（
C. (n+1)/2
D. (n-1)/242．在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行（
）。A.q-&next = p-&
p-&next =B.p-&next = q-&
q =C.q-&next = p-&
p-&next =D.p-&next = q-&
q-&next =43. 在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行(
s→link=p→
p→link=s;
p→link=s;
s→link=q;C . p→link=s→
s→link=p;
q →link=s;
s→link =p;44. 线性链表不具有的特点是（
）。4A．随机访问
B．不必事先估计所需存储空间大小C．插入与删除时不必移动元素
D．所需空间与线性表长度成正比45. 下述哪一条是顺序存储结构的优点？（
插入运算方便
B．可方便地用于各种逻辑结构的存储表示C．存储密度大
D．删除运算方便46. 下面关于线性表的叙述中，错误的是哪一个？（
）。A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。47. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（
）存储方式最节省时间。A．顺序表
C．带头结点的双循环链表
D．单循环链表48．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（
）存储方式最节省运算时间。A. 单链表
B. 仅有头指针的单循环链表C. 双链表
D. 仅有尾指针的单循环链表49．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(
)最节省时间。A. 带头结点的双循环链表
B.单循环链表C. 带尾指针的单循环链表
D. 单链表50．若线性表最常用的操作是存取第I个元素及其前驱和后继元素的值，为节省时间应采用的存储方式(
)。A.单链表
B.双向链表
C.单循环链表
D.顺序表51．静态链表中指针表示的是(
)A.下一元素的地址
B.内存储器的地址C.下一元素在数组中的位置
D.左链或右链指向的元素的地址52．在n个结点的线性表的数组实现中，算法的时间复杂性是O(1)的操作是(
)A. 访问第i个结点(1≤i&=n)和求第i个结点的直接前驱(2≤i&=n)B. 在第i个结点后插入一个新结点(1≤i&=n)C. 删除第i个结点(1≤i&=n)D. 以上都不对53．(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是（
）。A．（1），（2）
C．（1），（2）,(3)
D.（2）54．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（
）。A．O(n)
D. O(1) O(1)
555．单链表中，增加一个头结点的目的是为了(
）。A．使单链表至少有一个结点
B．标识表结点中首结点的位置C．方便运算的实现
D．说明单链表是线性表的链式存储56．对于双向循环链表,在p指针所指的结点之后插入s指针所指结点的操作应为（
）。A．p-&right= s-&left=p;
p-&right-&left= s-&right=p-&B．p-&right= p-&right-&left= s-&left=p;
s-&right=p-&C．s-&left=p;
s-&right=p-& p-&right=
p-&right-&left= ;D．s-&left=p;
s-&right=p-& p-&right-&left=
p-&right=57．对于一个线性表既要求能够进行较快速的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用(
顺序存储方式
B. 链式存储方式
C. 散列存储方式
D. 以上均可以58．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（
）。A．p-&next=s;s-&next=p-&
B． s-&next=p-&p-&next=s;C．p-&next=s;p-&next=s-&
D． p-&next=s-&p-&next=s;59．线性表的顺序存储结构是一种（
）。A. 随机存取的存储结构
B. 顺序存取的存储结构C. 索引存取的存储结构
D. Hash存取的存储结构60．顺序表是线性表的（B
）A、链式存储结构
B、顺序存储结构
C、索引存储结构
D、散列存储结构61．带头结点的单链表head为空的条件是（
B ）A、head=NULL
B、head-&next=NULL
C、head-&next=head
D、head!=NULL62．链表不具有的特点是（
）A．插入、删除不需要移动元素
B．可随机访问任一元素C．不必事先估计存储空间
D．所需空间与线性长度成正比63．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（
）存储方式最节省时间。A．顺序表
B．双链表C．带头结点的双循环链表
D．单循环链表64．下面关于线性表的叙述中，错误的是哪一个？（
）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。
二、填空题1．设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_______个数据元素；删除第i个位置上的数据元素需要移动表中_______个元素。n+1-i，n-i2. 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。p&llink-&rlink=p-& p-&rlink-&llink=p-&rlink63．设指针变量p指向单链表中结点A，则删除结点A的语句序列为：q=p-&next；p-&data=q-&data；p-&next=___________；feee(q)；q-&next4．在带头结点的单链表L中, 第一个元素所对应的结点的指针表达式是_____________。L-&next5．在双向循环链表中，在结点*Ｐ之前插入结点*Ｓ的语句序列是：S-& prior = P-&
S-&next=P;
P-&prior=S;
__________________。S-& prior-&next=S;6．在有n个元素的链队列中，入队和出队操作的时间复杂度分别为_____O(1)____和______O(1)____。7．在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向_
。前驱、后继8．在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为_ 。_(rear+1)%n=front9．下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。typedef struct node { struct node *}void lklistcreate(_____________ *&head ){for (i=1;i&=n;i++){p=(lklist*)malloc(sizeof(lklist));scanf(“%d”,&(p-&data));p-&next=0;if(i==1)head=q=p;else {q-&next=p;____________;}}}lklist，q=p10．设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：1) s-&next=___________；2) p-&next=s；3) t=p-&data；4) p-&data=___________；5) s-&data=t；p-&next，s-&data11．设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s-&next=p-& _________________;。p-&next=s12．设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_________和head=__________（设结点中的两个指针域分别为llink和rlink）。head-&rlink，p-&llink13．设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_________=p；s-&right=p-&right；__________=s； p-&right-&left=s；（设结点中的两个指针域分别为left和right）。s-&left=p，p-&right14．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为__________________________（设结点的指针域为 7next）。s-&next=p-& p-&next=s15．在一个单链表HL 中，若要向表头插入一个由指针p指向的结点，则应执行语句：
。p-&next=HL; HL=p;16．在采用独立结点构成的双向链表中，设p和q 分别是具有Dnode * 类型的指针变量。若双向链表中p结点之后插入一个q结点，其操作步骤为：
；q-&right=p-&if (p-&right) p-&right-&left=q;q-&left=p;p-&right=q;17．对于一个顺序存储的线性表，在表头插入元素的时间复杂度为____________,在表尾插入元素的时间复杂度为________________。O(n)
O(1)18．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动___n-i+1_____个元素。19．设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，指针s指向双链表中的一个结点（该结点既非头结点，也非尾结点），则删除s指针所指向结点的操作为“s-&tl-&r1=s-&r1；”和“__s-&rl-&tl=s-&tl_______”。20．设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“p→next=head；”和“__head=p________”。21．单链表中逻辑上相邻的两个元素在物理位置上_____不一定_____相邻。22．在一个长度为n的数组中删除第i个元素（1≤i≤n）时，需要向前移动的元素的个数是_____n-i_____。23．在顺序表上读表元算法的时间复杂度为___O（1）____。24．双链表中前驱指针为prior，后继指针为next，在指针P所指结点前插入指针S所指的结点，需执行下列语句：S→next=P;S→prior=P→P→prior=S;__p-&prior-&next=s_____;
25．设某非空双链表，其结点形式为q所若要删除指针指向的结点，则需执行下述语句段：q-&prior-&next＝q-& _q-&next-&prionr=p-&prior____。26．对长度为n的顺序表执行删除操作，其删除算法在最坏情况下的时间复杂性为__O（n）。27．在一个长度为n的顺序表中插入一个元素，最少需要移动
元素，最多需要移动
元素，0，n;28．双向循环链表的优点是
既可以方便的找到后继结点又可以方便的找到前驱结点。29．在一个长度为n的顺序表中删除一个元素，最少需移动
个元素，最多需移动________个元素。0
n－130．在长度为n的顺序表中插入第i个元素（假设i值可操作），要将元素从第
（前或后）移动。
后31．将指向单链表中的某个结点的指针p移动到该结点的后继结点表示为
p=p-&next32．在线性表的单链接存储结构中，每个结点包含有两个域，一个叫
域，另一个叫
域。元素值、指针33．在下面数组a中链接存储着一个线性表，表头指针为a[0].next，则该线性表为
( 38 , 56 , 25 , 60 , 42 , 74 )34．对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为
，在表尾插入元素的时间复杂度为
。O(n)、O(1)35．对于一个长度为n的单链接存储的线性表，在表头插入元素的时间复杂度为
，在表尾插入元素的时间复杂度为
。O (1)、O(n)36．在线性表的顺序存储中，若一个元素的下标为i，则它的前驱元素的下标为
，后继元素的下标为
。i-1、i+137．在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为
，若假定p为一个数组a中的下标，则其后继结点的下标为
。p-&next 、a[p].next38．在循环单链表中，最后一个结点的指针指向
结点。表头39．在双向链表中每个结点包含有两个指针域，一个指向其
结点，另一个指向其
结点。前驱、后继40．在循环双向链表中表头结点的左指针域指向
结点，最后一个结点的右指针域指向
结点。表尾、表头41．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为
。HL-&next = = NULL
、HL-&next = = HL42．队列的插入操作在
进行，删除操作在
进行。队尾、队首43．栈又称为
表，队列又称为
表。后进先出(LIFO)、先进先出(FIFO)44．向一个顺序栈插入一个元素时，首先使
后移一个位置，然后把待插入元素
到这个位置上。栈顶指针、存储45．从一个栈中删除元素时，首先取出
，然后再前移一位
。栈顶元素、栈顶指针46．在一个循环顺序队列Q中，判断队空的条件为
，判断队满的条件为
。front = = rear 、(rear+1)%QueueMaxSize = = front47．在一个顺序栈中，若栈顶指针等于
，则为空栈；若栈顶指针等于
，则为满栈。C1 、StackMaxSize-148．在一个链栈中，若栈顶指针等于NULL，则为
；在一个链队中，若队首指针与队尾指针的值相同，则表示该队列为
或该队列为
9空、空队、队列只有一个元素49．在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为_________________________________________________。
8data next
（38，56，25，60，42，74）；50．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为________________和____________________。HL→next =NULL；
HL=HL→next；51．用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的___________，该循环队列的最大长度为__________。前一个位置；
n-1；52．当堆栈采用顺序存储结构时，栈顶元素的值可用―――――――表示；当堆栈采用链接存储结构时，栈顶元素的值可用_______________表示。S.stack[S.top];
HS→53．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______； ______;【华中理工大学 2000 一.4（2分）】py-&next=px-& px-&next=py54．在一个长度为n的顺序表中第i个元素（1&=i&=n）之前插入一个元素时，需向后移动________个元素。【北京工商大学 2001 二.4（4分）】n-i+155．在单链表中设置头结点的作用是________。【哈尔滨工业大学 2000 二.1（1分）】有头结点后，插入元素和删除元素的算法统一了，不再需要判断是否在第一个元素之前插入和删除第一个元素。另外，不论链表是否为空，链表指针不变。56．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。【哈尔滨工业大学 2001 一.1（2分）】
O(1)，O(n)57．在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、_______、_______、________。【中国矿业大学 2000 一.1（3分）】f-&next=p-& f-&prior=p; p-&next-&prior=f; p-&next=f;58．顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。【北京理工大学 2001 七.2 （2分）】物理上相邻
指针59．在单链表L中，指针p所指结点有后继结点的条件是：________【合肥工业大学 2001 三.3 （2分）】p-&next!=null60. 单链表与多重链表的区别是
。链域数目不同
三、判断题
）线性表的顺序存储结构比链式存储结构更好。F2．(
)线性表就是顺序存储的表。×3．（
）线性表中的所有元素都有一个前驱元素和后继元素。F4．（
）非空的双向循环链表中任何结点的前驱指针均不为空。T5．（
）不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。T6．(
)对链表进行插入和删除操作时不必移动链表中结点。T7．(
)线性表只能用顺序存储结构实现。×8．(
)如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。×9．(
)进栈操作时，必须判断栈是否已满。×10．(
)进栈、出栈操作的时间复杂度是O(n)。×11．(
)采用链式结构存储线性表时，其地址可以是不连续的。√12．(
)线性表中的每个元素都有一个前驱元素和后继元素。×13．(
)采用顺序结构存储线性表时，其地址可以是不连续的。×14．（
）如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。√15．（
）线性表的唯一存储形式就是链表。×16．（
）线性表不能采用链式存储。×17．（
）在单链表中插入结点主要通过移动元素实现。×18．(
)所谓静态链表就是一直不发生变化的链表。×19．(
)集合与线性表的区别在于是否按关键字排序。×20．（
）用头部插入结点的方法建立单链表时，插入元素的顺序和链表中的元素顺序相同。×21．（
）线性表中的每个元素都有一个前驱元素和后继元素。
）线性表中每个元素都有一个直接前驱和一个直接后继。×23．（ ）线性表采用顺序存储表示时，必须占用一片连续的存储单元。√24．(
)数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。×25．(
)数据的逻辑结构是指数据的各数据项之间的逻辑关系。×26．(
)算法的优劣与算法描述语言无关，但与所用计算机有关。×27．(
)健壮的算法不会因非法的输入数据而出现莫名其妙的状态。√28．（
）算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。×29．(
)数据的物理结构是指数据在计算机内的实际存储形式。√30．(
)数据结构的抽象操作的定义与具体实现有关。×31．(
)数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。√32．（
）算法独立于具体的程序设计语言，与具体的计算机无关。√33．（
）Huffman树、平衡二叉树都是数据的逻辑结构。√34．（
）抽象数据类型与计算机内部表示和实现无关。√35．（
）在一个设有头指针和尾指针的单链表中,执行删除该单链表中最后一个元素的操作与链表的长度无关。×36．(
)顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。×
）顺序存储方式只能用于存储线性结构。×38．(
) 线性表只能用顺序方式存放。X39．(
) 在带表头结点的双循环链表中，每个结点的前趋和后继指针均不为空。√40．（ ）顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。×41．( )顺序存储方式的优点是存储密度大，且插入、删除运算效率高。×42．（
）在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。×43. （ ）在单链表中，要取得某元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。×四、简答题1．线性结构与非线性结构的差别前驱与后继之间通常为一对多或多对多的关系。2．比较顺序表与单链表的优缺点。顺序表优点：随机查找，存储密度大顺序表缺点：插入、删除不便，静态分配，表长固定单链表优点：插入、删除方便，动态分配，表长灵活单链表缺点：查找不便，存储密度小3．简要说明算法与程序的区别。算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实现，与具体的计算机语言有关。4．说明以下三个概念的关系：头指针，头结点，首元素结点。头指针指向头结点，头结点的后继域指向首元素结点。5．设有编码为A，B，C，D的4列火车，依次进入一个栈式结构的站台，试写出这4列火车开出站台的所有可能的顺序。根据栈的数学性质，n个元素的出栈序列数目恰好符合卡塔南数列。Cn=C2nn/(n+1)=1/n+1*(2n)!/n!(2n-n)!这里:1/n+1*(2n)!/n!(2n-n)!=1/5*8!/(4!*4!)=14ABCD
DCBA分析解答：6．写出在双向链表中，在指针p所指结点前插入一个结点*S的语句序列。答：答：（1）S-&prior=P-&
（2）P-&prior-&next=S;
（3）S-&next=P;（4）P-&prior=S;
7．试叙述一维数组与有序表的异同。一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中的元素按值排列（非递增或非递减），而一维数组中的元素没有按元素值排列顺序的要求。8．试比较顺序存储和链式存储的优缺点。顺序存储查找效率高，插入和删除效率低；链式存储插入和删除效率高，查找效12率低。9．写出线性表(26,45,12,20,30)采用快速排序算法排序后，第一趟排序过程及结果。20 12 26 45 30。10．试说明单链表采用头结点的优点。解决单链表的“第一个结点问题”，使头指针变量不为空。11. 画出带头结点的单链表、单循环链表和双向循环链表的示意图，并归纳三者的不同之处。
?? 单链表：只有从头结点出发，才能访问到所有结点。单循环链表：从任意一结点出发，均可访问到其他结点。双向循环链表：既可以方便的找到前趋结点，又可方便的找到后继结点。12．有五个数依次进栈：1，2，3，4，5。在各种出栈的序列中，以3，4先出的序列有哪几个。（３在４之前出栈）。【解答】34215
3452113．铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：1，2，3，4，5，6， 那么是否能够得到435612， 325641， 5426的出站序列，如果不能，说明为什么不能； 如果能， 说明如何得到(即写出&进栈&或&出栈&的序列)。【解答】输入序列为123456，不能得出4623。不能得到435612的理由是，输出序列最后两元素是12，因为前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。 得到325641的过程如下：1 2 3顺序入栈，32出栈，得到部分输出序列32；然后45入栈，5出栈，部分输出序列变为325；接着6入栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。14．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？【解答】2和 415．设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过 13栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4，e6，e2，e1，则栈S的容量至少应该是多少？【解答】 416．循环队列的优点是什么，如何判断“空”和“满”。【解答】循环队列解决了常规用0--m-1的数组表示队列时出现的“假溢出”（即队列未满但不能入队）。在循环队列中，我们仍用队头指针等于队尾指针表示队空，而用牺牲一个单元的办法表示队满：即当队尾指针加1（求模）等于队头指针时，表示队列满。也有通过设标记以及用一个队头或队尾指针加上队列中元素个数来区分队列的“空”和“满”的。17．设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队的时间如何？若只设尾指针呢？【解答】若只设头指针，则入队的时间为O(n），出队的时间为O(1)。若只设尾指针，则入队和出队的时间均为O(1)。18．试将下列递推过程改写为递归过程。void ditui(int n){i=n;while(i&0) printf(i--);}【解答】void digui(int n){if(n&0){printf(n);digui(n-1);}}19．写出下列中缀表达式的后缀表达式：(1)A*B*C
(2)(A+B)*C-D
(3)A*B+C/(D-E) (4)(A+B)*D+E/(F+A*D)+C 解答】(1)ABC**(2)AB+C*D-(3)AB*CDE-/+(4)AB+D*EFAD*+/+C+20．线性表的顺序存储结构具有三个弱点：第一，在作插入或删除操作时，需要移动大量元素；第二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；第三，表的容量难以扩充。试问，线性表的链式存储结构是否一定能够克服上述三个弱点？请简述之。【北京师范大学2003二.4(6分)】 链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储结构的缺点。21．说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。
【厦门大学 2000 五.1 （14%/3分）】在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。有头结点后，对在 14第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。22.
如何通过改链的方法，把一个单向链表变成一个与原来链接方向相反的单向链表？【中国人民大学 2001 二.4 （2分）】本题是链表的逆置问题。设该链表带头结点，将头结点摘下，并将其指针域置空。然后从第一元素结点开始，直到最后一个结点为止，依次前插入头结点的后面，则实现了链表的逆置。23．已知L是一个数据类型linkedlist的单循环链表，pa和pb是指向L中结点的指针。简述下列程序段的功能。【山东科技大学 2001 一.2 （5分）】 TYPE linkedlist=↑node=RECORDdata: next:linkedlistEND;PROC
Mp(pa,pb:linkedlist);PROC
subp(s,q: linkedlist);p:=s;WHILE
p↑.next&&q
p:=p↑.p↑.next:=sENDP;subp(pa,pb);subp(pb,pa);ENDP;mp是一个过程，其内嵌套有过程subp。subp(s,q)的作用是构造从s到q的循环链表。subp(pa,pb)调用结果是将pa到pb的前驱构造为循环链表。subp(pb,pa)调用结果是将pb到pa的前驱（指在L链表中，并非刚构造的pa循环链表中）构造为循环链表。总之，两次调用将L循环链表分解为两个。第一个循环链表包含从pa到pb的前驱,L中除刚构造的pa到pb前驱外的结点形成第二个循环链表。24．阅读下面的算法，说明算法实现的功能
【东华大学2004二.1(10分)】 a)
node *link(node
*head2){node
p=head1;while (p-&next!=head1)
p=p-&q=head2;while (q-&next!=head2)
q=q-&p-&next=head2;
q-&next=head1;return(head1);}本算法功能是将两个无头结点的循环链表合并为一个循环链表。head1最后一个结点的链域指向head2， head2最后一个结点的链域指向head1，head1为结果循环链表的指针。五、应用题151．在下面的每个程序段中，假定线性表La的类型为List，元素类型ElemType为int，并假定每个程序段是连续执行的，试写出每个程序段执行后所得到的线性表La。(1) InitList(La);int a[]={48,26,57,34,62,79};for(i=0; i&6; i++)
InsertFront(La,a[i]);TraverseList(La);
(2) InitList(La);for(i=0; i&6; i++)
Insert(La,a[i]);TraverseList(La);
(3) ClearList(La);for(i=0; i&6; i++)
InsertRear(La,a[i]);Delete(La, a[5]);Sort(La);Insert(La,a[5]/2);TraverseList(La);(1) ( 79 , 62 , 34 , 57 , 26 , 48 )(2) ( 26 , 34 , 48 , 57 , 62 , 79 )(3) ( 26, 34 , 39 , 48 , 57 , 62 )2．写出下面函数被调用执行后，得到的以HL为表头指针的单链表中的数据元素序列。void
AA(LNode * & HL){InitList(HL);InsertRear(HL,30);InsertRear(HL,50);int
a[5] = {15,8,9,26,12};for ( int
i++ )InsertFront(HL,a[i]);}（12，26，9，8，15，30，50）3．执行下面函数调用后得到的输出结果是什么？void
AF(Queue & Q){InitQueue(Q);int
a[4] = { 5,8,12,15 };for ( int
QInsert(Q,a[i]);
QInsert(Q,QDelete(Q));QInsert(Q,30);QInsert(Q,QDelete(Q)+10);while ( ! QueueEmpty(Q) ) cout
&&QDelete(Q)&&’ ‘;16}12
18六、程序填空题（或算法阅读题）1．LinkList mynote(LinkList L){//L是不带头结点的单链表的头指针if(L&&L-&next){q=L；L=L－&next；p=L；S1：
while(p－&next) p=p－&next；S2：
p－&next=q；q－&next=NULL；}return
L；}请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2, ?,an）,写出算法执行后的返回值所表示的线性表。（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,?,an,a1）2．说明下面递归的功能void unknown(ListNode *f，Type &x) {//指针f 是带表头结点的单链表的表头指针，数值x是给定值。ListNode *If (f?link!=NULL) {While(f?link?data= =x) {Temp= f? f?link= temp?}unknown(f?link , x);}}在单链表中删除所有值为x的结点。3．void AD(Lnode* & HL){Insert(HL,30);Insert(HL,50);Delete(HL,26);Delete(HL,55);}
假定调用该算法时以HL为表头指针的单链表中的内容为（15，26，48，55），则调用返回后该单链表中的内容为：（15，30，48，50）______________________________。4．int AA(LNode *HL , ElemType x)17{int n=0;LNode *p=HL;while (p!=NULL){if (p-&data= =x) n++;p=p-&}}
对于结点类型为LNode的单链表，以上算法的功能为：统计单链表中结点的值等于给定值x的结点数。5．void CC( Stack &S){Pop(S);Push(S,50);Push(S,45);Peek(S);}假定调用算法时栈S 中已有2个元素（23，16）的栈，其中23时栈底，调用后得到的栈内容为（从栈底开始排列）：栈内容为（从栈底开始排列）：23，50，45。6．void AA (LNode * HL,const ElemType & item){LNode * newptr=new Lnewptr-&data=LNode *p=HL;while
( p-&next!=HL )p=p-&newptr-&next=HL;p-&next=}
对于结点类型为LNode的单链表，以上算法的功能为：向单链表的末尾添加一个元素。7．void BB(List &L){int i=0;while (i&L.size){int j=i+1;while (j&L.size){18if(L.list[j] = =L.list){for (int k=j+1;k&L.k++) L.list[k-1]=L.list[k];L.size--;}else
j++;}i++;}}以上算法的功能为：删除线性表中所有重复的元素。8．利用单链表进行数据排序。void LinkSort (ElemType a[ ],int n) {LNode * head=new LNInitList (head);for (i=0;i&n;i++)Insert(head, a[i]);LNode * p=head-&i=0; while (
) {a[i++]=p-&}ClearList (head);}p!=NULLp=p-&9．void BB( LNode *& HL){LNode *p=HL;HL=NULL;while (p!=NULL){LNode *q=p;p=p-&q-&next=HL;HL=q;19}}
对于结点类型为Lnode的单链表，以上算法的功能为：将一个单链表按逆序链接。10．void BB(List &La){InitList(La);int a[]={78,26,56,27,34,42};for(i=0; i&3; i++)InsertFront(La,a[i]);for(i=3; i&6; i++)InsertRear(La,a[i]);TraverseList(La);}该算法执行后得到的线性表La为：（56，26，78，27，34，42）11. 在单链表（表头指针为head）的元素中找出最后一个值为e的元素，返回其指针；如果找不到，返回NULL。完成以下程序。(6分)typedef srruct LinkNode {struct LinkNode *} N
Node *search_link(Node *head, int e) {Node *p, *q;
for(p=p=p-&next) {if(p-&data = = e) {
}}}2．NULL;p!=NULL;q=p;12. 已知QUEUE表示循环队列的数据结构，函数leavequeue是将对头元素的值放入变量e，然后删除对头元素，操作成功返回1，否则返回0。完成以下程序。（4分）typedef struct{int data[100];} QUEUE;
20leavequeue (QUEUE *Q, int *e){
) {return 0;}*e = Q-&data[Q-&front]; Q-front =
return 1;}1．Q-&front == Q-&(Q-&front+1)%100;13. 已知一个单链表的表头指针为h，每个结点含元素值data和下一个结点的地址next。链表一共有5个结点，其元素值分别为100,200,300,400,500，经过下列语句后，输出什么结果？。（3分）for (p=h;p-&data&300;p=p-&next) {p-&next = p-&next-&}printf(“%d”,p-&data);3．30014. 指出下面程序段的功能是什么？(1)
void demo1(SeqStack S){int i，arr[64]，n=0;while(!StackEmpty(S)) arr[n++]=Pop(S);for(i=0;i&n;i++) Push(S，arr[i]);}【解答】程序段的功能是实现了栈中元素的逆置。
void demo2(SeqStack S，int m)∥设栈中元素类型为int型{SeqStack T;StackInit(T);while(!StackEmpty(S))if((x=Pop(S))!=m) Push(T，x);while(!(StackEmpty(T)) {x=Pop(T); Push(S，x);}}【解答】程序段的功能是删除了栈中值为m的元素。
void demo3(SeQueue Q，int m)∥设队列中元素类型为int型 {SeqStack S;StackInit(S);while(!QueueEmpty(Q)){x=QueueOut(Q); Push(S，x);}while(!StackEmpty(S)){x=Pop(s); QueueIn(Q，x);}}【解答】程序段的功能是实现了队列中元素的逆置。15. 假定从键盘上输入一批整数，依次为：78
C1，请写出输出结果。# include & iostream.h&21# include & stdlib.h &consst int stackmaxsize = 30;struct stack {elemtype stack [stackmaxsize];};# include “stack.h”Void
main ( ){initstack(a);cin &&x;while (x! = -1) {push (a, x );cin &&x;}while (!stackempty (a))cout &&pop (a) &&”” ;cout &&end1;}该算法的输出结果为：__________________________________________________________.该算法的输入结果是：34
7816. 设有一个带表头结点的双向循环链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次 L.Locate (x)操作时，令元素值x的结点的访问频度freq加1，并将该结点前移，链接到现它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。函数中有些语句缺失，请将它们补上。（每一个空2分，共10分）template& class Type&void DblList&Type& ：： Locate ( Type & x) {DblNode&Type&*p=first-&While (p ! = frist &&
)p = -&If (p ! =first){
//链表中存在x
//该结点的访问频度加lDblNode&Type&*current=p;
//从链表中摘下这个结点Current ?prior?next = current ?Current ?next?prior = current ?P=current?
//寻找重新插入的位置While (p !=first &&
③ )22P=p ?Current ?next=
//插入在p之后Current ?prior=P ?next ?prior=P ?next=
⑤}else cout&&”Sorry.Not find! \n”;
//没找到}缺失的内容为：①②③④⑤①p?data!=x②p?freq++③current?freq&p?freq④p?next⑤current17. 已给如下关于单链表的类型说明：TYPElist=^node=RECORDdata:
next:END;以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性（升序），这里两链表的头指针分别为p和q.PROCEDURE mergelink(VAR p,q:list):VAR h,r:BEGIN（1）______h^.next:= NIL; r:=h;WHILE((p&&NIL) AND (q&&NIL))
DOIF (p^.data&=q^.data)THEN
（2）___； r:=p; p:=p^.next；
（3）____； r:=q; q:=q^.
END;IF (p=NIL)
r^.next:=q;（4）__；p:=h^. dispose(h);END;【厦门大学 2000 三.2 （8分）】(1)new(h);∥生成头结点，以便于操作。
(2)r^.next:=p;(3) r^.next:=q;
(4) IF q=NIL THEN r^.next:=p;18. 已知双链表中结点的类型定义为：TYPE dpointer=^23list=RECORDdata: left,right:END;如下过程将在双链表第i个结点（i&=0）之后插入一个元素为x的结点，请在答案栏给出题目中______处应填入的语句或表达式，使之可以实现上述功能。 PROCEDURE
insert(VAR head:i,x:integer);VAR s,p:
j:BEGINnew(s); s^.data:=x; IF(i=0)THEN BEGIN s^.right:= (1)___ head:=s END{如果i=0,则将s结点插入到表头后返回} ELSE BEGIN p:= (2)_______；{在双链表中查找第i个结点,由p所指向} WHILE ((p&&NIL) AND (j&i)) DO
j:=j+1; (3) _ END;IF p&&NIL THENIF （p^.right=NIL） THEN BEGIN p^.right:=s; s^.right:=NIL; (4) __END ELSE BEGIN s^.right:=p^. (5) _;p^.right:=s; (6)
writeln(‘can not find node!’)ENDEND;【厦门大学 2002 二 （12分）】(1)head^.left:=s
∥head的前驱指针指向插入结点(2)j:=1;(3)p:=p^.right
∥工作指针后移(4)s^.left:=p(5)p^.right^.left:=s;
∥p后继的前驱是s(6)s^.left:=p;19. 阅读以下算法，填充空格，使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中，删除所有值相等的多余元素。CONST
maxlen=30TYPE sqlisttp=RECORDelem:ARRAY[1..maxlen] OFlast:0..maxlenEND;PROC exam21(VAR L:sqlisttp);j:=1;
i:=2; WHILE (1)______ DO [ IF
L.elem[i]&&L.elem[j]
THEN [ (2)_______; (3)______];i:=i+1] (4) ________;ENDP;【同济大学 2000 二.1 (10分)】(1)i&=L.last
∥L.last 为元素个数(2)j:=j+1
∥有值不相等的元素24(3)L.elem[j]:=L.elem[i]
∥元素前移(4)L.last:=j
∥元素个数20. 对于给定的线性链表head , 下面的程序过程实现了按结点值非降次序输出链表中的所有结点，在每次输出一个结点时，就把刚输出的结点从链表中删去。请在划线处填上适当的内容，使之成为一个完整的程序过程，每个空框只填一个语句。TYPE
nodeptr =^ nodetype；nodetype = RECORDdata : integer；link : nodeptrEND;VAR
head : nodeptr；PROCEDURE
sort_output_delete (head : nodeptr);VAR p,q,r,s:BEGIN
WHILE head && NIL
p:= NIL ；q:= head；r:= q ；s:=q^.link ；WHILE
s^.data & q^.data THEN
(1)__; (2)___ END ； r:= s ；
(3)___END；write(q^.data : 5) ； IF p=NIL THEN
(5)____ ；dispose (q) ；END；writelnEND；【复旦大学 1996 七 （20分） 1995 一（12分）与本题相似】(1)p:=r;∥r指向工作指针s的前驱，p指向最小值的前驱。(2)q:=s;∥q指向最小值结点，s是工作指针(3)s:=s^.link∥工作指针后移(4)head:=head^.∥第一个结点值最小；(5)p^link:=q^.∥跨过被删结点（即删除一结点）21. 循环链表a和b的结点值为字母，其中a表非递减有序，下面的程序欲构造一个递增有序的循环链表c，其中结点的值为同时在a，b两链表中出现的字母，且c中字母不重复，请补上程序中空缺的部分，并估计算法的时间复杂度。（设a，b的结点数分别为m，n）TYPElink=^node=RECORDkey:
next:linkEND;PROC
jj(a,b: VAR
c:link);VAR
p,q,r,s:BEGINnew(c);c^.next:=c;
p:=a^.WHILE
p&&a DO25[（1）___；WHILE
p^.key=p^.next^.key
p=p^.next];｛跳过相同字母｝ r:=b^. （2）_____;WHILE
r^.key &&p^.key DO r:=r^.IF
THEN[ s:=p;
q^.next:=p^.
（3）s^.next:=c^.
c^.next:=s;
c:=s ]ELSE [ q:=p;
p:=p^.next ]];
c:=c^.next；END;算法时间复杂度为O（4）___
【北京工业大学 2000 四 (15分)】(1)a^.key:=’@’∥a的头结点用作监视哨，取不同于a链表中其它数据域的值(2)b^.key:=p^.key∥b的头结点起监视哨作用(3)p:=p^.next∥找到a,b表中共同字母，a表指针后移(4)0(m*n)22. 下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针，试在空缺处填入适当的语句。void
reverse（linklist &L）{p=null；q=L；while（q！=null） { (1)
q-&next=p；p=q；(2)___ } (3)_____;}【北京理工大学 2001 九.1 （6分）】(1)L=L-&
∥暂存后继(2)q=L;
∥待逆置结点(3)L=p;
∥头指针仍为L23. 下面程序段是逆转单向循环链表的方法，p0 是原链表头指针，逆转后链表头指针仍为p0。（可以根据需要增加标识符）p:= p0;
q0:=NIL;WHILE （1）________ DOBEGIN
（2）________; （3）________;（4）______;（5）________
END; p^.next:= q0;
p0 ^.next:=p;
p0:=p;【中国人民大学2000二.1(4分)】(1) p^.next&&p0
(2)r:= p^.next
(3) p^.next:= q0;(4) q0:=
(5) p:=r24. 一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef ，指数域exp和指针域 next；现对链表求一阶导数 ，链表的头指针为ha，头结点的exp域为 C1。derivative(ha){ q=
pa=ha-& while( (1)_______) { if ( (2)____) { ( (3)__); free(pa);
pa= ( (4) _);
}26else{ pa-&coef ( (5) ___); pa-&exp( (6)___); q=( (7) __);} pa=( (8)________);}}【南京理工大学 2000 三.3（10分）】(1)pa!=ha
∥或pa-&exp!=-1(2)pa-&exp==0
∥若指数为0，即本项为常数项(3)q-&next=pa-&next
∥删常数项(4)q-&next
∥取下一元素(5)=pa-&coef*pa-&exp(6)--
∥指数项减1(7)pa
∥前驱后移,或q-&next(8)pa-&next
∥取下一元素25. 对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。typedef struct node{
struct node *}linknode,*void Insertsort(link L){ link p,q,r,u; p=L-&
(1)______; while((2)________){ r=L;
q=L-& while((3)________&& q-&data&=p-&data) {r=q; q=q-&} u=p-&
(4)______;
(5)______;
p=u;}}【北京科技大学 2001 二 （10分）】(1)L-&next=null
∥置空链表,然后将原链表结点逐个插入到有序表中(2)p!=null
∥当链表尚未到尾(3)q!=null
∥查p结点在链表中的插入位置，这时q是工作指针。(4)p-&next=r-&next ∥或p-&next=q
将p结点链入链表中(5)r-&next=p
∥r是q的前驱，u是下个待插入结点的指针。26. 下面是一个求两个集合A和B之差C=A-B的程序，即当且仅当e是A的一个元素，但不是B中的一个元素时，e才是C中的一个元素。集合用有序链表实现，初始时，A，B集合中的元素按递增排列，C为空；操作完成后A，B保持不变，C中元素按递增排列。下面的函数append(last,e)是把值为e的新结点链接在由指针last指向的结点的后面，并返回新结点的地址；函数difference(A,B)实现集合运算A-B，并返回表示结果集合C的链表的首结点的地址。在执行A-B运算之前，用于表示结果集合的链表首先增加一个附加的表头结点，以便新结点的添加，当A-B运算执行完毕，再删除并释放表示结果集合的链表的表头结点。 typedef struct node{
struct node *}NODE;NODE
*A，*B，*C;NODE
*append (NODE *last,int e)27{last-&link=(NODE*) malloc (sizeof(NODE));last-&link-&element=e;return(last-&link);}NODE *difference(NODE *A,NODE *B){NODE *C,*C=last=(NODE*) malloc (sizeof(NODE)); while (1)___if (A-&element&B-&element) { last=append(last,A-&element);
if (2) ___ { A=A-&
(3) ___ ; while (4) __ { last=append(last,A-&element); A=A-&
} (5) ___;
free (last);return (C);}/*call form:C=difference(A,B);*/【上海大学 2000 一.4 （10分）】(1)(A!=null && B!=null)
∥两均未空时循环(2)A-&element==B-&element
∥两表中相等元素不作结果元素(3)B=B-&link
∥向后移动B表指针(4)(A!=null)
将A 表剩余部分放入结果表中(5)last-&link=null
∥置链表尾27. 判断带头结点的双向循环链表L是否对称相等的算法如下所示，请在划线处填上正确的语句。 【华南师范大学 2000年 五.1 ( 9分)】FUNCTION
equal(l:pointer) :VAR p,q:
result: BBEGIN result:= p:= l^. q:=l^. WHILE (p&&q) AND ((1)_______)DO
p^.data=q^.data THEN BEGIN (2)___; (3)____; END；ELSE
result:=return(result);END;(1)
(3) q:=q^.pre （（２）（３）顺序可变）2. 28. LinkList exam2(LikeList l){ //L是无头结点的的单链表ListNode *P,*Q;if (L && L-&next){ Q=L; L=L-& P=L;while ( P-&next )
P=P-&28P-&next=Q; Q-&next=NULL;}//ifreturn L;}//exam2程序段2 的功能是将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针；（根据答题情况酌情给分）
七、算法设计题1．统计出单链表HL中结点的值等于给定值X的结点数。int CountX(LNode* HL,ElemType x)nt CountX(LNode* HL,ElemType x){
int i=0; LNode* p=HL;//i为计数器while(p!=NULL){ if (P-&data==x) i++;p=p-&}//while, 出循环时i中的值即为x结点个数}//CountX
2. 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。typedef struct node { struct node *}void intersection(lklist *ha,lklist *hb,lklist *&hc){lklist *p,*q,*t;for(p=ha,hc=0;p!=0;p=p-&next){
for(q=q!=0;q=q-&next) if (q-&data==p-&data)if(q!=0){ t=(lklist *)malloc(sizeof(lklist));t-&data=p-&t-&next= hc=t;}}}3．设计在单链表中删除值相同的多余结点的算法。typedef struct node { struct node *} void delredundant(lklist *&head){lklist *p,*q,*s;for(p=p!=0;p=p-&next){for(q=p-&next,s=q;q!=0; )if (q-&data==p-&data) {s-&next=q-& free(q);q=s-&}
29else {s=q,q=q-&}}}4．设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。ttypedef struct node { struct node *} void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) {lklist *p; ha=0,hb=0,hc=0;for(p=p!=0;p=head){head=p-& p-&next=0;if (p-&data&='A' && p-&data&='Z') {p-&next= ha=p;}else if (p-&data&='0' && p-&data&='9') {p-&next= hb=p;} else {p-&next= hc=p;}}}5．设计两个有序单链表的合并排序算法。void mergelklist(lklist *ha,lklist *hb,lklist *&hc){lklist *s=hc=0;while(ha!=0 && hb!=0)if(ha-&data&hb-&data){if(s==0) hc=s= else {s-&next= s=};ha=ha-&}else {if(s==0) hc=s= else {s-&next= s=};hb=hb-&}
if(ha==0) s-&next= else s-&next=}6．设计将所有奇数移到所有偶数之前的算法。void quickpass(int r[], int s, int t){int i=s,j=t,x=r[s];while(i&j){while (i&j && r[j]%2==0) j=j-1;
if (i&j) {r[i]=r[j];i=i+1;}
while (i&j && r[i]%2==1) i=i+1;
if (i&j) {r[j]=r[i];j=j-1;}
}r[i]=x;}7．设计判断单链表中元素是否是递增的算法。int isriselk(lklist *head){if(head==0||head-&next==0) return(1);else30for(q=head,p=head-& p!=0; q=p,p=p-&next)if(q-&data&p-&data) return(0);return(1);8．编写向类型为List的线性表L中第i个元素位置插入一个元素的算法，假定不需要对i的值进行有效性检查，同时不需要检查存储空间是否用完。Void Insert(List& L，int i,
ElemType x)评分标准：请根据编程情况酌情给分。vioid Insert(List& L,int i,ElemType x){for(int j=L.size-1;j&=i-1;j--)L.list[j+1]=L.list[j];L.list[i-1]=x;L.size++;}9．编写算法，求不带头结点的单链表的表表长。（7分）已知单链表结点数据结构如下：typedef struct node{struct node *} LNode, *LinkL
int length_LinkList(LinkList L){LNode *p=L;int j = 0while(p-&next != NULL) {p = p-&++j;}}
10．编写算法，删除顺序表第i个元素。（8分）已知顺序表的数据结构如下：typedef struct{int data[100];} SeqL
int delete_SeqList(SeqList *L,int i){31if (i &1 || i&L-&last+1) {printf(“不存在第i个元素”);return 0;}
for (j=i; j&=L-&L-& ++j) {l-&data[j-1] = L-&data[j];}L-&last--;return 1;}
11．编写算法查找不带头结点的单链表中的第i个结点，如找到返回1，否则返回0。（7分）已知单链表结点数据结构如下：typedef struct node{struct node *} LNode, *LinkLLNode
*Get_LinkList(inkList L, int i){LNode *p = L;int j = 0;while(p-&next != NULL && j & i) {p = p-&++j;}
if (j == i) {}else {return NULL;}}12．编写算法，将任意十进制数转换成其他进制，要求写出完整代码，可采用顺序栈或链栈实现。（12分）#define Maxsize 100typedef struct{int data[Maxsize];32}SeqSSeqStack *Init_SeqStack(){SeqStack *s;s=(SeqStack *)malloc(sizeof(SeqStack));
s-&top=-1;}/*入栈*/int Push_Seqstack(SeqStack *s,int x) {if(s-&top==Maxsize-1)return 0;
else{s-&top++;s-&data[s-&top]=x;return 1;}}/*出栈*/int Pop_SeqStack(SeqStack *s,int *x) {if(Empty_SeqStack(s)) return 0;
else{*x=s-&data[s-&top];s-&top--;return 1;}}/*判空栈*/int Empty_SeqStack(SeqStack *s){if(s-&top==-1) return 1;else return 0;}void conversion(int N,int r){SeqStack *p;p=Init_SeqStack();while(N){if(Push_Seqstack(p,N%r)==1)
}else33}while(!Empty_SeqStack(p)){Pop_SeqStack(p,&y);printf(&%d&,y);}}
void main(){int M,t;printf(&please input a number:\n&);scanf(&%d&,&M);printf(&please input t:\n&);scanf(&%d&,&t);conversion(M,t);getch();}13．编写一算法完成瑟夫生死者游戏。（8分）瑟夫生死者游戏的描述：N个旅客同乘一条船，因为严重超载，加上风浪大，危险万分；因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免遇难。无奈，大家只得同意这种办法，并拟定N个人围成一圈，由第一个人数起，依次报数，数到第r人，便把他投入海中，然后再从他的下一个人数起，数到第r人，再将他仍进海里，如此循环的进行，直到剩下N/2个乘客为止。问哪些位置是将被扔下大海的位置。
typedef struct node{struct node *}ListNode,*LinkLLinkList CreateList(int n);void DeleteNode(LinkList L,int n,int k);void PrintList(LinkList L);main(){int n,k;LinkList H;printf(&请输入总人数：&);scanf(&%d&,&n);printf(&请输入报数上限:&);scanf(&%d&,&k);H=CreateList(n);34DeleteNode(H,n,k);PrintList(H);getch();}
LinkList CreateList(int n){LinkList L=NULL;ListNode *s,*R=NULL;for(i=1;i&=n;i++){s=(ListNode *)malloc(sizeof(ListNode));
s-&data=i;if(L==NULL) L=s;else R-&next=s;R=s;}if(L!=NULL) R-&next=L;return L;}
void DeleteNode(LinkList L,int n,int k){int i,j=0;ListNode *q,*p=L;printf(&不幸投入大海的有：&);for(i=1;i&=n/2;i++){for(j=1;j&k-1;j++)p=p-&q=p-&p-&next=q-&printf(&%4d&,q-&data);if(i%10==0) printf(&\n&);free(q);p=p-&}printf(&\n&);L=p;}
void PrintList(LinkList L){35ListNode *p=L;int i=1;printf(&有幸逃生的有：&);while(p-&next!=L){printf(&%4d&,p-&data);if(i%10==0) printf(&\n&);p=p-&}printf(&%4d&,p-&data);}14．有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大升序排列。要求写出完整代码。（12分）1．#define MAXSIZE 20typedef struct{datatype data[MAXSIZE];}SeqL
SeqList *init_SeqList();void input(SeqList *L);void output(SeqList *L);
void merge(SeqList *A,SeqList *B,SeqList *C);main(){SeqList *A,*B,*C;int i,n;A=init_SeqList();B=init_SeqList();C=init_SeqList();input(A);input(B);merge(A,B,C);output(C);getch();}SeqList *init_SeqList(){36SeqList *L;L=(SeqList *)malloc(sizeof(SeqList));L-&last=-1;return L;}void merge(SeqList *A,SeqList *B,SeqList *C){int i,j,k;i=0;j=0;k=0;while(i&=A-&last&&j&=B-&last)if(A-&data[i]&B-&data[j])C-&data[k++]=A-&data[i++];elseC-&data[k++]=B-&data[j++];while(i&=A-&last)C-&data[k++]=A-&data[i++];while(j&=B-&last)C-&data[k++]=A-&data[j++];C-&last=k-1;}
void input(SeqList *L){printf(&input numbers(less than 20):\n&);for(n=0;;n++){scanf(&%d&,&L-&data[n]);if(L-&data[n]==0)L-&last=n;}}
void output(SeqList *L){for(n=0;n&=L-&n++)printf(&%d\t&,L-&data[n]);}15．对于List类型的线性表，编写出下列每个算法。(1) 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若线性表为空则显示出错信息并退出运行。(2) 从线性表中删除第i个元素并由函数返回。(3) 向线性表中第i个元素位置插入一个元素。37(4) 从线性表中删除具有给定值x的所有元素。(1) ElemType
DMValue( List & L ) {if ( ListEmpty(L) )
// 空线性表cerr
Empty!”&&exit(1);}ElemT
// x存放最小元素x = L.list[0];int
// k存放最小元素的下标for
// 查找最小元素if
( L.list[i] & x ) {
x = L.list[i] ;
}L.list[k] = L.list[L.size-1];
// 最后一个元素填补最小元素位置L.size--;
// 线性表长度减1
// 返回最小元素}(2)ElemType
Delete( List & L, int
( i&1 || i&L.size ) {
// 判断i的合法性cerr
range!”&&exit(1);}ElemType
x = L.list[i-1];
// 保存被删除元素for
j&L.size-1;
// 元素向前移动
L.list[j] = L.list[j+1];L.size--;
// 长度减1
// 返回被删元素}(3)void
Insert( List & L, int
i, ElemType
( i&1 || i&L.size+1 ) {
// 判断i的合法性cerr
range!”&&exit(1);}if
( L.size == MaxSize ) {
// 判断线性表满cerr
overflow!”&&exit(1);}for
j = L.size-1 ;
// 元素后移，产生插入位置L.list[j+1] = L.list[j];L.list[i-1] =
// 元素插入L.size++;
// 长度加1}(4) void
Delete( List & L, ElemType
i = 0;38while
( i&L.size )if
( L.list[i] == x ) {
// 删除x元素for
j++ )L.list[j-1] = L.list[j];L.size--;}else
// 寻找下一个x元素的位置}16．对于结点类型为LNode的单链表，编写出下列每个算法。(1) 删除单链表中的第i个结点。(2) 在有序单链表中插入一个元素x的结点。(3) 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息并停止运行。(4)统计出单链表中结点的值等于给定值x的结点数。
Delete( LNode
* & HL, int
i ) {if ( i&1 || HL==NULL ) {
// 判断i的合法性或空链表cerr
range!”&&exit(1);}LNode
* ap , *ap = NULL ;
// cp指向当前结点，ap指向其前驱结点int
j = 1;while
( cp != NULL )
// 查找第i个结点if
( j == i )
// 找到第i个结点
// cp指向的结点即为第i个结点else
// 继续向后寻找ap =cp = cp-&j++;}if
( cp == NULL ) {
// 没有找到第i个结点cerr
range!”&&exit(1);}if
( ap == NULL )
// 删除第1个结点（即i=1）
HL = HL-&nextlelseap-&next = cp-&
// 删除第i个结点
// 释放被删除结点的空间
Insert( LNode * & HL, const
& x ) {LNode * newptr = new
// 申请一个新结点39if
( newptr == NULL ) {
// 分配失败cerr
&&”Memory
allocation
failare!”&&exit(1);}newptr-&data =if
( HL == NULL || x&HL-&data ) {
// 空表 或 x小于表头结点，newptr-&next = HL;
// 作为新表头结点插入HL =}// 查找插入位置LNode
* cp = HL-&
// 用cp指向当前结点（即待查结点）LNode
* ap = HL;
// 用ap作为指向当前结点的前驱结点指针while
( cp != NULL )if
( x&cp-&data) // 找到插入位置else
// 继续查找插入位置newptr-&next =
ap-&next =
// 插入新结点
}(3)ElemType
MaxValue( LNode
* HL ) {if
( HL == NULL ) {
// 空表cerr
&&”Linked
empty!”&&exit(1);}ElemType
max = HL-&LNode * p = HL-&while
( p != NULL )
// 寻找最大值if
( max & p-&data )
max = p-&p = p-&}}(4)int
Count( LNode * HL , ElemType
n = 0;LNode
* p = HL;while
( p != NULL ) {if
( p-&data == x )
n++;p = p-&}}4017．裴波那契(Fibonacci)数列的定义为：它的第1项和第2项均为1，以后各项为其前两项之和。若裴波那契数列中的第n项用Fib(n)表示，则计算公式为：
(n=1或2)Fib(n)=?? Fib(n-1)+Fib(n-2)
(n&=2)试编写出计算Fib(n)的递归算法和非递归算法，并分析它们的时间复杂度和空间复杂度。递归算法：long
( n==1 || n=2 )
// 终止递归条件return
1;elsereturn
Fib(n-1)+Fib(n-2);}非递归算法：long
// c代表当前项，a和b分别代表当前项前面的第2项和第1项a = b = 1;if
( n == 1 || n == 2 )return
i++ ) {c = a+b;
// 求当前项a =
// 产生第2项b =
// 产生第1项}
// 返回所求的第n项}递归算法的时间复杂度为 O(2n)，空间复杂度为 O(n)；非递归算法的时间复杂度为 O(n)，空间复杂度为 O(1)。18．编写算法，将一个结点类型为Lnode的单链表按逆序链接，即若原单链表中存储元素的次序为a1，??an-1，an，则逆序链接后变为, an，an-1，??a1。Void
contrary (Lnode * & HL)根据编程情况，酌情给分。{Lnode *P=HL;HL=NULL;While (p!=null){Lnode*q=p;P=p→q→next=HL;HL=q;41}}19．一个一维整数数组A[m]中有n (n≤m)个非空整数，它们相继存放于数组的前端并已按非递减顺序排列，针对下列三种情况，分别编写相应的函数。（1）在数组A[ ]中插入一个新的整数x ，并使得插入后仍保持非递减有序。要求x 插在值相等的整数后面。（5分）void InsertSort (int A[ ], int m , int & n , int x){
}插入函数如下：void InsertSort (int A[ ], int m , int & n , int x) {if (n&m) {int I,for (i=0 ; i&n&&A[i]&= ; i++ ;)for (j=n-1 ; j&=I ; j-- )A[j+1] = A[ j ] ;A[ I ]=n++;}else{cerr&&”数组已满，不能插入！”&& exit () ; }}（2）将数组中所有整数原地逆置，即利用原数组空间将数组中全部元素反转。（5分）void reverse (int A [ ], int n ){
}逆置函数如下：void reverse (int A [ ], int n ) {int mid=n/2 , I,for ( i=0 ; i& i++ ){temp=A[i] ; A[i]=A[n-i-1] ;A[n-i-1]= }}（3）删除数组中多余的值相等的整数（只保留第一次出现的那个整数）。（5分）Void delDuplicate (int A [ ] , int & n){
}删除函数如下：Void delDuplicate (int A [ ] , int & n) {Int i=0 , j ,42While (i&n-1 ) {J = I + 1 ;While (j&n) {If (A[i]= =A[j]) {For ( k=j+1 ; k& k++ )A[k-1]=A[k] ;n-- ;}else j++;}i++}}
20．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998三.1(5分)】【厦门大学)(20/3分)】[题目分析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。LinkedList Union(LinkedList la,lb)∥la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列∥本算法将两链表合并成一个按元素值递减次序排列的单链表{ pa=la-& pb=lb-&∥pa，pb分别是链表la和lb的工作指针
∥la作结果链表的头指针，先将结果链表初始化为空while(pa!=null && pb!=null) ∥当两链表均不为空时作if(pa-&data&=pb-&data){ r=pa-&
∥将pa 的后继结点暂存于rpa-&next=la-&
∥将pa结点链于结果表中，同时逆置 la-&next=pa=r;
∥恢复pa为当前待比较结点}else{r=pb-&
∥ 将pb 的后继结点暂存于rpb-&next=la-& ∥将pb结点链于结果表中，同时逆置la-&next=pb=r;
∥恢复pb为当前待比较结点}if(pa) pb=
∥避免再对pa写下面的while语句
while(pb!=null){r=pb-& pb-&next=la-& la-&next= pb=r; }
}∥算法Union结束43［算法讨论］上面两链表均不为空的表达式也可简写为while(pa&&pb),两递增有序表合并成递减有序表时，上述算法是边合并边逆置。也可先合并完，再作链表逆置。后者不如前者优化。算法中最后while语句将尚未到尾的表逆置到结果表中。21．已知两个链表A和B分别表示两个集合，其元素递增排列。编一函数，求A与B的交集，并存放于A链表中。【南京航空航天大学 2001 六（10分）】[题目分析]本题是求交集，即只有同时出现在两集合中的元素才出现在结果表中。其核心语句段如下：pa=la-&pb=lb-&∥设工作指针pa和pb；pc=
∥结果表中当前合并结点的前驱的指针while(pa&&pb)if(pa-&data==pb-&data)∥交集并入结果表中{ pc-&next=pc=pa=pa-&u=pb=pb-&free(u);}else if(pa-&data&pb-&data) {u=pa=pa-&free(u);} ∥释放结点空间 else {u= pb=pb-& free(u);}while(pa){ u= pa=pa-& free(u);}∥释放结点空间while(pb) {u= pb=pb-& free(u);}∥释放结点空间pc-&next=∥置链表尾标记。free(lb);
∥注： 本算法中也可对B表不作释放空间的处理22．己知两个线性表A ，B均以带头结点的单链表作存储结构，且表中元素按值递增有序排列。设计算法求出A与B的交集C，要求C另开辟存储空间，要求C同样以元素值的递增序的单链表形式存贮。【西北大学 2000 五 ( 8分)】[题目分析]本题要求结果表要另辟空间。LinkedList Union(LinkedList A,B)∥线性表A和B以带头结点的单链表作为存储结构。本算法求A和B的交集C，C另辟空间{pa=A-&pb=B-&∥pa、pb是两链表的工作指针pc=C=(LinkedList)maloc(sizeof(LNode)); pc-&data=MaxElemType ∥监视哨while(pa&&pb)if(pa-&data&pb-&data) pa=pa-&
∥pa指针后移
else if(pa-&data&pb-&data) pb=pb-& ∥pb指针后移
∥处理交集元素if(pc-&data==pa-&data){pa=pa-&pb=pb-&} ∥删除重复元素
else{ p=(LinkedList)maloc(sizeof(LNode));p-&data=pa-&pc-&next=p;pc=p;pa=pa-&pb=pb-&} ∥交集元素并入结果表pc-&next=
∥置结果链表尾return C;}
4423．设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。【北京理工大学 2000 四.2（4分）】[题目分析]带头结点的链表分解为数据值小于0和大于0的两个链表，其类C算法如下。void DisCreat1(LinkedList A)∥本算法将带头结点的单链表A分解成数据域值小于零和大于零的两个单链表B和C{B=A;C=(LinkedList )malloc(sizeof(LNode));∥为C申请结点空间
C-&next=null
∥C初始化为空表p=A-&
∥p为工作指针B-&next=
∥B表初始化while(p!=null){r=p-&
∥暂存p的后继if(p-&data&0)∥小于0的放入B表{p-&next=B-& B-&next=p; }∥将小于0的结点链入B表
else {p-&next=C-& C-&next=p; }p=r;∥p指向新的待处理结点}}∥算法结束[算法讨论]因为本题并未要求链表中结点的数据值有序，所以算法中采取最简单方式：将新结点前插到头结点后面（即第一元素之前）。另外，表C中包括值为0的结点。24．试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。void
delete（Linklist
&L） 【北京理工大学2001九.3(8分)】[题目分析]在单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。LinkedList Delete（LinkedList L）∥L是带头结点的单链表，本算法删除其最小值结点{p=L-&next；
∥p为工作指针。指向待处理的结点。假定链表非空 pre=L；
∥pre指向最小值结点的前驱q=p；
∥q指向最小值结点，初始假定第一元素结点是最小值结点 while（p-&next）{if（p-&next-&data&q-&data）{pre=p；q=p-&next；}
∥查最小值结点
p=p-&next；
∥指针后移}pre-&next=q-&next；∥从链表上删除最小值结点free（q）；return L;∥释放最小值结点空间}∥结束算法delete[算法讨论] 算法中函数头是按本教材类C描述语言书写的。原题中void
delete（linklist &L），是按C++的“引用”来写的，目的是实现变量的“传 45址”，克服了C语言函数传递只是“值传递”的缺点。25．已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。【北京航空航天大学 2001 四（10分）】[题目分析] 本题要求将链表中数据域值最小的结点移到链表的最前面。首先要查找最小值结点。将其移到链表最前面，实质上是将该结点从链表上摘下（不是删除并回收空间），再插入到链表的最前面。LinkedList
delinsert（LinkedList
list）∥list是非空线性链表，链结点结构是（data，link），data是数据域，link是链域∥本算法将链表中数据域值最小的那个结点移到链表的最前面{p=list-&link；∥p是链表的工作指针pre=list；
∥pre指向链表中数据域最小值结点的前驱q=p；
∥q指向数据域最小值结点，初始假定是第一结点while （p-&link）{if（p-&link-&data&q-&data）{pre=p；q=p-&link；} ∥找到新的最小值结点p=p-&link；}if(q!=list-&link)
∥若最小值是第一元素结点，则不需再操作{pre-&link=q-&link；
∥将最小值结点从链表上摘下q-&link= list-&link；∥将q结点插到链表最前面list-&link=q；}}∥算法结束[算法讨论] 算法中假定list带有头结点，否则，插入操作变为q-&link=list；list=q。26．已知两个单链表A和B,其头指针