[自考类试卷]全国自考数据结构导论（线性表）模拟试卷1及答案与解析.doc

1、全国自考数据结构导论（线性表）模拟试卷 1 及答案与解析一、单项选择题1 线性表的_元素没有直接后继。（A）第一个（B）最后一个（C）所有（D）没有2 若线性表采用顺序存储结构，每个元素占用 2 个存储单元，第 1 个元素存储地址为 100，则第 5 个元素的存储地址是_。（A）100（B） 108（C） 110（D）1203 从具有 n 个结点的单链表中查找值等于 x 的结点时，在查找成功的情况下，平均需比较_个结点。（A）n（B） n2（C） (n 一 1)2（D）(n+1) 24 在单链表中，删除 p 所指结点的直接后继的操作是_。（A）p 一next=p 一next 一next；（B）

2、 p=p 一next ；p 一next=p 一next 一next ；（C） p 一next=p 一next：；（D）p=p 一next 一next；5 以下有关链表的说法中，错误的是_。（A）对单链表来说，寻找结点的后继比较容易（B）对循环链表来说，从任一结点出发，都可以遍历整个链表（C）对双链表来说，寻找结点的前趋和后继都比较容易（D）对于静态链表来说，可以随机存取结点中的数据6 双向链表具有对称性，是指_（A）p 一prlOr 一next=p=p 一next 一next（B） p 一prior 一next=p=p 一next 一prior（C） p 一prior 一prior=p=p 一

3、next 一prior（D）p 一prior 一prior=p= 一 p 一next 一next7 单链表中，增加头结点的目的是为了_。（A）方便运算的实现（B）用于标识单链表（C）使单链表中至少有一个结点（D）用于标识起始结点的位置8 在一个单链表中，若 p 所指结点不是最后结点，在 p 之后插入 s 所指结点，则执行_。（A）s 一next=p；p 一next=s；（B） s 一next=p 一next；p 一next=s；（C） s 一next=p 一next，p=s，（D）p 一next=s ；s 一next=p；9 在一个单链表中，已知 q 所指结点是 p 所指结点的直接前趋，若在

4、p，q 之间插入 s 结点，则执行_操作。（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；10 带头结点的单链表 head 为空的判断条件是_ 。（A）head=NULL（B） head 一next=NULL（C） head 一next=head（D）head!=NULL11 不带头结点的单链表 head 为空的判定条件是_ 。（A）head=NULL（B） head 一next=NULL（C） head 一next=head

5、（D）head!=NULL12 非空的循环单链表 head 的尾结点(由 P 所指向)满足_。（A）p=head（B） p=NULL（C） P 一next=head（D）P 一next=NULL13 在循环双链表的 P 所指缩点之后插入。所指结点的操作是_。（A）P 一next=s s 一prior=p；P 一next 一prior=s；s 一next=p 一next ；（B） P 一next=s P 一next 一prior=s；S 一prior=p；s 一next=p 一next：（C） S 一prior=p；s 一next=p 一next；P 一next=s P 一next 一prior

6、=s：（D）s 一prior=p；S 一next=p 一next ；P 一next 一prior=s；P 一next=s；二、填空题14 对于一个具有 n 个结点的单链表，在 p 所指结点后插入一个新结点的时间复杂度为_；在给定值为 x 的结点后插入一个新结点的时间复杂度为_。15 单链表是_的链接存储表示。16 在双链表中，每个结点有两个指针域，一个指向_，另一个指向_-。17 在一个单链表中删除 p 所指结点时，应执行以下操作：q=p 一next；p 一data=p 一next 一data；p 一next=_；free(q)；18 向一个长度为 n 的向量的第 i 个元素(1in+1)之前

7、插入一个元素时，需向后移动_个元素。19 已知顺序表中每个元素占用 3 个存储单元，第 13 个元素的存储地址为 336，则顺序表的首地址为_。20 线性表所含_称线性表的表长，表长为 0 的线性表称为_21 线性表的链式存储结构主要有_、_和_。22 向一个长度为 n 的向量中删除第 i 个元素(1in)时，需向前移动_个元素。23 在一个单链表中，已知 q 所指结点是 p 所指结点的前趋结点，若在 q 和 p 之间插入 s 结点，则执行_。三、应用题24 叙述以下概念的区别：头指针变量、头指针、头结点、首结点，并说明头指针变量和头结点的作用。25 设有一个顺序表 A，其中的元素按值非递减有

8、序排列，编写一个函数插入一个元素 x 后持该向量仍按递减有序排列。26 已知一个有序单链表(从小到大排列)，表头指针为 head，编写一个函数向该单链表中插入一个元素为 x 的节点，使插入后该单链表仍有序。27 已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数，删除向量中多余的值相同的元素。28 有一个单链表，其结点的元素值以非递减有序排列，编写一个函数删除该单链表中余的元素值相同的结点。29 编写一个函数，从给定的顺序表 A 中删除元素值在 x 到 y(xy)之间的所有元素，要求以较高的效率实现。30 设有线性表 A=(a1，a 2，a m)，B=(b 1，b 2，b n)。试写一

9、合并 A、B 为线性表C 的算法，使得 假设 AB 均以单链表为存储结构(并且 m、n 显式保存)。要求 C 也以单链表为存储结构并利用单链表A、B 的结点空间。31 试分别以顺序表和单链表作存储结构，各写一个实现线性表的自身(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a 1，a 2，a n)逆置为(an， a2，a 1)。32 有一个单链表(不同结点的数据域值可能相同)，其头指针为 head，编写一个函数计算数据域为 x 的结点个数。33 设有一个循环单链表 head，编写算法，实现结点指针域指向其直接前趋的操作。34 设有一循环双链表，但初始时每个结点的前域指针 p

10、rior 是空的。编写算法，使每个结点的前域指针 prior 指向其直接前趋。全国自考数据结构导论（线性表）模拟试卷 1 答案与解析一、单项选择题1 【正确答案】 B【知识模块】 线性表2 【正确答案】 B【试题解析】 第 5 个元素的地址=100+2*(5 一 1)=108【知识模块】 线性表3 【正确答案】 D【试题解析】 最好情况下只需比较 1 次，最坏情况下需比较 n 次，所以平均比较次数为(1+2+3+n)n=(n+1)2【知识模块】 线性表4 【正确答案】 A【试题解析】 删除 p 的直接后继后， p 的直接后继的直接后继成为 p 的新的直接后继，所以应将新的直接后继的地址存入 p

11、 的指针域中。【知识模块】 线性表5 【正确答案】 D【知识模块】 线性表6 【正确答案】 B【知识模块】 线性表7 【正确答案】 A【试题解析】 作为单链表来说，是用头指针来对其进行标识的。头指针可以指向头结点，也可以指向起始结点，所以没有必要用头结点来标识起始结点。而一个单链表允许是空的，不一定非要保证单链表中至少有一个结点，因此 B，C ，D 答案都是错误的。之所以要引入头结点，目的就是为了方便单链表上运算的实现。【知识模块】 线性表8 【正确答案】 B【知识模块】 线性表9 【正确答案】 B【试题解析】 按题意画如下图。在本题中，因为相关的三个结点分别被三个指针所指向，所以图中的操作步

12、骤可以对调。【知识模块】 线性表10 【正确答案】 B【试题解析】 带头结点的空单链表如下图所示。 所以其判断条件可表示为 head 一 next=NULL。如果单链表不带头结点，则其判空的条件是 head=NULL。【知识模块】 线性表11 【正确答案】 A【知识模块】 线性表12 【正确答案】 C【试题解析】 不管循环单链表是否带有头结点，其尾结点的指针域一定指向头指针 head 的目标，所以有 P 一next=head。【知识模块】 线性表13 【正确答案】 D【试题解析】 循环双链表上的插入、删除操作，关键是指针操作的先后顺序不能出错，否则会失去某些结点的地址。建议画一个图，标出指针的

13、先后操作顺序，如图下所示。【知识模块】 线性表二、填空题14 【正确答案】 O(1) O(n)【试题解析】 在指定结点后插人一个结点，无须查找插入位置，故其时间复杂度是 O(1)；而对给定值的结点，因为不知道它的存放位置，所以需要从表头处开始查找，故其时间复杂度是 O(n)。【知识模块】 线性表15 【正确答案】 线性表【知识模块】 线性表16 【正确答案】 前趋结点 后继结点【知识模块】 线性表17 【正确答案】 p 一next 一next【知识模块】 线性表18 【正确答案】 ni+1【知识模块】 线性表19 【正确答案】 300【试题解析】 第 13 个元素的地址(336)=首地址+3*

14、(131)，从而得到首地址为300。【知识模块】 线性表20 【正确答案】 结点的个数 空表【知识模块】 线性表21 【正确答案】 单链表 双向链表 循环链表【知识模块】 线性表22 【正确答案】 ni【知识模块】 线性表23 【正确答案】 q 一nex=s ；s 一next=p；【知识模块】 线性表三、应用题24 【正确答案】 头指针变量：指该交量的值是指向单链表的第一个结点的指针。因此，它是用于存放头指针的变量。头指针：指向单链表的第一个结点的指针。头结点：链表的首结点之前附设的一个结点，称为头结点。首结点：指用于存储线性表中第一个数据元素的结点。头指针变量的作用：对单链表中任一结点的访问

15、必须首先根据头指针变量中存放的头指针找到第一个结点，再按各结点链域存放的指针顺序依次往下找，直到找到(或找不到) 。头指针变量具有标识单链表的作用，故用头指针变量来命名单链表。头结点的作用：该结点的数据域中不存储数据元素，其作用是为了对链表进行操作时，将对第一个结点的处理和对其他结点的处理统一起来。【知识模块】 线性表25 【正确答案】 非递减有序序列是一个按值从小到大进行排序的序列，而且该序列中可能存在值相同的元素。本题的算法思想是：先找到适当的位置，然后后移元素空出一个位置，再将 x 插入。实现本题功能的函数如下：void insert(Sqlist *查找插入位置 i*for(j=njj

16、=i；j 一一)Aj+1=Aj ； *移出插入 x 的位置*Ai=x；n+； *将 x 插入，向量长度增 1*【知识模块】 线性表26 【正确答案】 本题的算法思想：先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置，最后插入该结点。实现本题功能的函数如下：node*insert(node*head，int x)node*s，*p，*q；s=(node*)malloc(sizeof(node)；*建立一个待插入的结点*s 一data=x；s 一next=NULL；if(head=NULL|xdata)*若单链表为空或 x 小于第一个结点的 data 域*s

17、一next=head； *把 s 结点插入到表头后面*head=s；elseq=head； *为 s 寻找插入位置，p 为待比较的结点，q 为 p 的前趋结点*p=A 一headwhile(p!=NULLxp 一data)*若 x 小于 p 所指结点的 data 域值*则退出 while 循环*if(xp 一data)( q=p；p=p 一next；s 一next=p； *将 s 结点插入到 q 和 p 之间*A 一next=s ；【知识模块】 线性表27 【正确答案】 本题的算法思想：由于向量中的元素按元素值非递减有序排列，值相同的元素必为相邻的元素，因此依次比较相邻两个元素，若值相等，则删

18、除其中一个，否则继续向后查找。实现本题功能的函数如下：voiddelete(SqList *若 A 表不空将 A 表连接到 C 表* else p 一next=B ； *若 B 表不空将 B 表连接到 C 表* 【知识模块】 线性表31 【正确答案】 (1)顺序表作存储结构。扫描顺序表 A 的前半部分元素，对于元 Adatai(onext ； *取原表表头结点*A 一next=NULL ； *设 A 为逆置表表头*while(p!=NuLL)u=p； p=p 一next ； *p 后移*u 一next=A 一neXtj *插入到头结点之后*A 一next=u：【知识模块】 线性表32 【正确答

19、案】 本题是遍历通过该链表的每个结点，每遇到一个结点，结点个数加 1，结点个数存储在变量 n 中。实现本题功能的函数如下：int count(node*head)node* p；int n=0；p=head；while(p!=NULL)if(p 一data=x)n+ ；p=p 一next；return(n)；【知识模块】 线性表33 【正确答案】 本算法的功能是将下图(a)所示的循环单链表，变换成下图(b)所示的循环单链表。 本题的算法思想是：设置三个指针从头到尾扫描循环单链表，将 a1 的指针域指向 an，a 2的指针指向 a1，依此类推，直到最后。但要注意当判断条件 r!=head 成立时

20、，还要将最后两个结点的指针域分别指向它们的直接前趋。实现本题功能的函数如下： void invert(Linklisthead) P=head； q=head 一next； r=q 一next； while(r!=head) q 一next=p； p=q； q=r； r=r 一next； q 一next=p； r 一next=q； 【知识模块】 线性表34 【正确答案】 本题与上一题有相同之处，但是不必改变每个结点后域指针 next的值。用两个指针从头到尾扫描循环双链表，让每个结点的 prior 域指向其直接前趋。实现本题功能的函数如下：voidinvert_dlist(dlklisthead)P=head 一next；q=head；while(p!=head)P 一prior=q；q=p；P=P 一next；head 一prior=q；【知识模块】 线性表