全国自考数据结构导论（线性表）模拟试卷1

33． 设有一个循环单链表head，编写算法，实现结点指针域指向其直接前趋的操作。

34． 设有一循环双链表，但初始时每个结点的前域指针prior是空的。编写算法，使每个结点的前域指针prior指向其直接前趋。

32． 有一个单链表(不同结点的数据域值可能相同)，其头指针为head，编写一个函数计算数据域为x的结点个数。

31． 试分别以顺序表和单链表作存储结构，各写一个实现线性表的自身(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a₁，a₂，…a_n)逆置为(a_n，…a₂，a₁)。

30． 设有线性表A=(a₁，a₂，…a_m)，B=(b₁，b₂，…b_n)。试写一合并A、B为线性表C的算法，使得

假设A．B均以单链表为存储结构(并且m、n显式保存)。要求C也以单链表为存储结构并利用单链表A、B的结点空间。

29． 编写一个函数，从给定的顺序表A中删除元素值在x到y(x≤y)之间的所有元素，要求以较高的效率实现。

26． 已知一个有序单链表(从小到大排列)，表头指针为head，编写一个函数向该单链表中插入一个元素为x的节点，使插入后该单链表仍有序。

27． 已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数，删除向量中多余的值相同的元素。

28． 有一个单链表，其结点的元素值以非递减有序排列，编写一个函数删除该单链表中余的元素值相同的结点。

24． 叙述以下概念的区别：头指针变量、头指针、头结点、首结点，并说明头指针变量和头结点的作用。

25． 设有一个顺序表A，其中的元素按值非递减有序排列，编写一个函数插入一个元素x后持该向量仍按递减有序排列。

23． 在一个单链表中，已知q所指结点是p所指结点的前趋结点，若在q和p之间插入s结点，则执行________。

22． 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动_______个元素。

19． 已知顺序表中每个元素占用3个存储单元，第13个元素的存储地址为336，则顺序表的首地址为______。

20． 线性表所含______称线性表的表长，表长为0的线性表称为_______

21． 线性表的链式存储结构主要有_____、_______和________。

16． 在双链表中，每个结点有两个指针域，一个指向_______，另一个指向________--。

17． 在一个单链表中删除p所指结点时，应执行以下操作： q=p一>next； p一>data=p一>next一>data； p一>next=_______； free(q)；

18． 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动_____个元素。

14． 对于一个具有n个结点的单链表，在p所指结点后插入一个新结点的时间复杂度为_______；在给定值为x的结点后插入一个新结点的时间复杂度为_______。

15． 单链表是_______的链接存储表示。

12． 非空的循环单链表head的尾结点(由P所指向)满足______。

13． 在循环双链表的P所指缩点之后插入。所指结点的操作是_______。

10． 带头结点的单链表head为空的判断条件是__________。

9． 在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入s结点，则执行______操作。

11． 不带头结点的单链表head为空的判定条件是______。

7． 单链表中，增加头结点的目的是为了__________。

8． 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行_____。

6． 双向链表具有对称性，是指_________

4． 在单链表中，删除p所指结点的直接后继的操作是_____。

5． 以下有关链表的说法中，错误的是_________。

3． 从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较_______个结点。

2． 若线性表采用顺序存储结构，每个元素占用2个存储单元，第1个元素存储地址为100，则第5个元素的存储地址是_____。

1． 线性表的________元素没有直接后继。