设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在)，试编写能实现下列

设有一个由正整数组成的无序(向后)单链表，编写完成下列功能的算法：1)找出最小值结点，且打印该数值。2)若该数值是奇数，则将其与直接后继结点的数值交换。3)若该数值是偶数，则将其直接后继结点删除。

设有n个元素的向量，逐个输入其中的元素值，建立一个有序单链表的时间复杂度是(51)。

A．O(1)

B．O(n)

C．O(n2)

D．O(nlog2n)

单链表

实验目的：

(1)熟练掌握线性表的单链式存储结构及在其上实现线性表的各种基本运算的方法。

(2)掌握和理解本实验中出现的一些基本的C语言语句。

(3)体会算法在程序设计中的重要性。

实验内容：

(1)设计一算法，逆置带头结点的动态单链表head。要求利用原表的结点空间，并要求用尽可能少的时间完成。

(2)设有两个按元素值递增有序的单链表A和B，编一程序将A表和B表归并成一个新的递增有序的单链表C(值相同的元素均保留在C表中)，并要求利用原表的空间存放C。

使C为A和B的交集，且C中元素也递增有序。

试设计一个算法，对其进行二路归并排序，要求不移动结点中的元素，只改各链结点中的指针，排序后r仍指示结果链表的第一个结点。(提示：先对待排序的单链表进行一次扫描，将它划分为若干有序的子链表，其表头指针存放在一个指针队列中。当队列不空时重复执行，从队列中退出两个有序子链表，对它们进行二路归并，结果链表的表头指针存放到队列中。如果队列中退出一个有序子链表后变成空队列，则算法结束。这个有序子链表即为所求)。

需要移动(58 )个元素;若采用单链表存储，则平均需要移动(59 )个元素。

A.1

B.(n-l)/2

C.logn

D.N

A.O(1)

B.O(n)

C.O(n^2)

D.O(nlog2n)

栈是一种按“后进先出”原则进行插入和删除操作的数据结构，因此， （9） 必须用栈。

A.函数或过程进行递归调用及返回处理

B.将一个元素序列进行逆置

C.链表结点的申请和释放

D.可执行程序的装入和卸载

A.227

B.226

C.228

D.229