1、线性表模拟试卷 2 及答案与解析一、单项选择题1 下面程序段中带下画线的语句的执行次数的数量级是( )。i=l； WHILE in DO i=i*2；（A）O(n)（B） O(log2n)（C） O(n2)（D）O(nlog 2n)2 算法的时间复杂度取决于( )。（A）问题的规模（B）待处理数据的初态（C） A 和 B（D）以上都不正确3 一个算法应该是( ) 。（A）程序（B）问题求解步骤的描述（C）要满足 5 个基本特性（D）A 和 C4 下面说法错误的是( )。算法原地工作的含义是指不需要任何额外的辅助空间在相同的规模 n 下，复杂度 O(n)的算法在时间上总是优于复杂度 D(2n)的
2、算法所谓时间复杂度，是指在最坏情况下，估算算法执行时间的一个上界同一个算法，实现语言的级别越高，执行效率就越低（A）（B） 、（C） 、（D）5 从逻辑上可以把数据结构分为( )两大类。（A）动态结构、静态结构（B）顺序结构、链式结构（C）线性结构、非线性结构（D）初等结构、构造型结构6 以下与数据的存储结构无关的术语是( )。（A）循环队列（B）链表（C）哈希表（D）栈7 以下数据结构中，( )是线性数据结构。（A）广义表（B）二叉树（C）稀疏矩阵（D）串8 以下数据结构中，( )是非线性数据结构。（A）树（B）字符串（C）队（D）栈9 连续存储设计时，存储单元的地址( )。（A）一定连续（
3、B）一定不连续（C）不一定连续（D）部分连续，部分不连续10 以下属于逻辑结构的是( )。（A）顺序表（B）哈希表（C）线性表（D）单链表11 下面关于线性表的叙述中，错误的是( )。（A）线性表采用顺序存储，必须占用一片连续的存储单元（B）线性表采用顺序存储，便于进行插入和删除操作（C）线性表采用链式存储，不必占用一片连续的存储单元（D）线性表采用链式存储，便于插入和删除操作12 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插人和删除运算，则利用( ) 存储方式最节省时间。（A）顺序表（B）双链表（C）带头结点的双循环链表（D）单循环链表13 若某表最常用的操作是在最后一个结点
4、之后插入一个结点或删除最后一个结点。则采用( )存储方式最节省运算时间。（A）单链表（B）双链表（C）单循环链表（D）带头结点的双循环链表14 静态链表中指针表示的是( )。（A）内存地址（B）数组下标（C）下一元素地址（D）左、右孩子地址15 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为( )(1in+1)。（A）O(O)（B） O(1)（C） O(n)（D）O(n 2)16 线性表(a 1，a 2， n)以链式存储方式存储时，访问第 i 位置元素的时间复杂度为( )。（A）O(i)（B） O(1)（C） O(n)（D）O(i 一 1)17 非
5、空的循环单链表 head 的尾结点 p 满足( )。（A）p 一next=head（B） p-next=NULL（C） p=NULL（D）p=head18 双向链表中有两个指针域，即 prior 和 next，分别指回前驱及后继，设 p 指向链表中的一个结点，q 指向一个待插入结点，现要求在 p 前插入 q，则正确的插入为( )。（A）p 一prior=q；q-next=p；p 一prior 一next=q；q 一prior=p 一prior；（B） q-prior=p-prior； p-prior 一next=q；q 一next=p；p-prior=q-next；（C） q-next=p；p
6、 一next=q；p-prior 一next=q；q-next=p；（D）p-prior 一next=q； q-next=p；q-prior=p 一prior；p-prior=q ；19 在单链表指针为 p 的结点之后插入指针为 s 的结点，正确的操作是 ( )。（A）p-next=s；s-next=p 一next；（B） s-next=p-next；p-next=s：（C） p-next=s：p-next=s-next；（D）p-next=s 一next；p 一next=s：20 对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是 ( )。（A）head=NULL（B）
7、head 一next=NULL（C） head 一next=head（D）head!=NULL二、综合题21 运算是数据结构的一个重要方面。举例说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同，因而两个数据结构具有显著不同的特性，是两个不同的结构。22 将下列函数，按它们在 n时的无穷大阶数，从小到大排序。 n，n 一n3+7n5，nlog 2n，2 n/2，n 3，log 2n，n 1/2+log2n，(3 2)n，n! ，n 2+log2n23 在单链表、双链表和单循环链表中，若仅知道指针 p 指向某结点，不知道头指针，能否将结点*p 从相应的链表中删去?若可以，其时间
8、复杂度各为多少?24 设有集合 A 和集合 B，要求设计生成集合 C=AB 的算法，其中集合 A、集合B 和集合 C 用链式存储结构表示。25 已知单链表 L 是一个递增有序表，试写一高效算法，删除表中值大于 min 且小于 max 的结点( 若表中有这样的结点) ，同时释放被删结点的空间，这里 min 和max 是两个给定的参数。26 试写出在单链表中搜索元素 x 的算法。若 x 存在链表中，则输出它在表中的序号，否则将 x 插到表尾。27 设有一个双链表，每个结点中除有 prior、data 和 next 这 3 个域外，还有一个访问频度域 freq，在链表被启用之前，其值均初始化为零。每
9、当在链表进行一次L0CateNode(L，x)运算时，令元素值为 x 的结点中 freq 域的值加 1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的 L,oCateNode 运算的算法。28 两个整数序列：A=a 1， a2，a 3，a m 和 B=b1，b 2，b 3，b n，已经存入两个单链表中，设计一个算法，判断序列 B 是否是序列 A 的子序列。29 已知 3 个带头结点的线性链表 A、线性链表 B 和线性链表 C 中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点)，编写算法对链表 A 进行如下操作：使操作后
10、的链表 A 中仅留下 3 个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为 D(m+n+p)，其中 m、n 和 p 分别为 3 个表的长度。线性表模拟试卷 2 答案与解析一、单项选择题1 【正确答案】 B【知识模块】 线性表2 【正确答案】 C【试题解析】 此题考查的知识点是算法时间复杂度的定义。算法的时间复杂度取决于输入问题的规模和待处理数据的初态，所以选 C、A 和 B 都不全面。【知识模块】 线性表3 【正确答案】 B【试题解析】 此题考查的知识点是算法的定义。一个算法应该是问题求解步骤的描述，所以选 B。算法必须有结束，而程序不一定，所以 A
11、 错，C 描述的是算法的特征不是定义，也错，D 自然错了。【知识模块】 线性表4 【正确答案】 C【试题解析】 此题考查的知识点是算法时间复杂度的理解。算法原地工作的含义是指需要额外的辅助空间为常量，所以 I 错，D(n)运行时间比 D(2n)好，所以是正确的，算法的执行效率与语言级别无关，所以是错误的，描述的是时间复杂度的上限定义，正确。根据题意选 C。【知识模块】 线性表5 【正确答案】 C【试题解析】 此题考查的知识点是基本的数据结构。从逻辑上可以把数据结构分为线性数据结构、非线性数据结构两大类，所以选 C。A 、B 描述的均为物理结构，而 D 描述的不是数据结构的内容。【知识模块】 线
12、性表6 【正确答案】 D【试题解析】 此题考查的知识点是数据结构和存储结构的理解。A 、B 、C 描述的均为物理结构即数据的存储结构，D 是逻辑结构，所以选 D。【知识模块】 线性表7 【正确答案】 D【试题解析】 此题考查的知识点是线性结构的定义。线性结构的定义可简单地理解为元素只有一个前导，一个后继，而 A、B、C 有多个后继，均错，所以选 D。【知识模块】 线性表8 【正确答案】 A【试题解析】 此题考查的知识点是非线性数据结构的定义。A 是层次结构，为非线性数据结构；B、C、D 均为线性数据结构，所以选 A。【知识模块】 线性表9 【正确答案】 A【试题解析】 此题考查的知识点是存储单
13、元问题。连续的存储单元一定连续，所以选 A。B、C、D 都错。【知识模块】 线性表10 【正确答案】 C【试题解析】 此题考查的知识点是对数据结构的逻辑结构理解。数据结构的逻辑结构是指数据之间的逻辑关系，不涉及存储结构。A 、B 、D 都是存储结构、C 是逻辑结构，所以选 C。【知识模块】 线性表11 【正确答案】 B【试题解析】 此题考查的知识点是线性表的存储结构及基本操作。线性表的顺序存储必须占用一片连续的存储单元，不利于进行插入和删除操作，A 描述正确，B不正确；而链式存储不一定占连续的存储单元，利于插入和删除操作，所以 C、D描述正确。根据题意选 B。【知识模块】 线性表12 【正确答
14、案】 A【试题解析】 此题考查的知识点是线性表的存储结构对基本操作的时间影响。根据题意用 B、C、D 三种方法存储，在存取任一指定序号的元素时，要从头向后找，在最后进行插入和删除运算，B、D 可以直接操作， C 也要从头找。而 A 两种操作都可以直接操作，最省时间。所以选 A。【知识模块】 线性表13 【正确答案】 B【试题解析】 此题考查的知识点是线性表的存储结构对基本操作的时间影响。A、B、D 每次都要从头向后找到相应结点，而 C 就标识在最后一个结点，所以选C。【知识模块】 线性表14 【正确答案】 B【试题解析】 此题考查的知识点是静态链表的定义。静态链表存储结构实际就是结构体数组，所
15、以其指针表示的就是数组下标。A 、C 、D 描述的不准确，所以选B。【知识模块】 线性表15 【正确答案】 C【试题解析】 此题考查的知识点是线性表基本操作的时间复杂性。顺序存储的线性表插入元素时需要从插入位置开始向后移动元素，腾出位置以便插入，平均移动次数为(n+1) 2，所以复杂性为 D(n)，选 C。【知识模块】 线性表16 【正确答案】 C【试题解析】 此题考查的知识点是线性表基本操作的时间复杂度。链式存储的线性表访问第 i 个位置的元素时需要从头开始向后查找，平均查找次数为 (n+1)2，所以复杂性为 D(n)，选 C。【知识模块】 线性表17 【正确答案】 A【试题解析】 此题考查
16、的知识点是循环单链表的存储定义。非空的循环单链表的尾结点的指针指向头结点，所以选 A。B、C、D 均不能构成非空的循环单链表。【知识模块】 线性表18 【正确答案】 A【试题解析】 此题考查的知识点是双向链表的插入操作。在 p 前插入要修改 p的 prior 指针，p 的 prior 所指结点的 next 指针，所以选 A。B、C、D 都将使地址丢失，连接失败。【知识模块】 线性表19 【正确答案】 B【试题解析】 此题考查的知识点是单链表的插入操作。要先保存 p 的后继结点，再连人 s 结点，所以选 B。A、C、D 都将使地址丢失，连接失败。【知识模块】 线性表20 【正确答案】 B【试题解
17、析】 此题考查的知识点是带头结点的单链表操作。带头结点的单链表空的时候表示只有一个结点存在，但没有存信息。所以选 B。A 表示没有结点，C 表示循环单链表，D 表示有一个指针不为空，所以都不对。【知识模块】 线性表二、综合题21 【正确答案】 栈和队列的逻辑结构相同，其存储表示也可相同(顺序存储和链式存储)，但由于其运算集合不同而成为不同的数据结构。【试题解析】 此问题考查的知识点是数据结构的逻辑结构、物理结构的意义。【知识模块】 线性表22 【正确答案】 从小到大排列为：log2n，n 1/2+log2n，n，nlog 2n，n 2+log2n，n 3，nn 3+7n3，2 n/2，(32)
18、 n，n!。【试题解析】 此问题考查的知识点是算法时间复杂度的表示。其中常量阶对数阶线性阶指数阶幂次阶阶乘阶。【知识模块】 线性表23 【正确答案】 单链表不可以，其他可以。双链表时间复杂度为 0(1)，单循环链表时间复杂度为 0(n)。【试题解析】 此问题考查的知识点是各类链表的基本操作。需要了解各类链表的存储结构，单链表只知 P 结点地址，无法知道其前驱地址，无法删除；双链表可以找到前驱地址为 p 一prior，能删除；循环链表可以循环找到 P 的前驱，也能删除。【知识模块】 线性表24 【正确答案】 typedef struct node int data；struct node * n
19、ext；lklist；void intersection(1klist * ha，lklist * hb，lklist * &hc)lklist * P，* q，* t；for(P=ha，hc：NULL ；P!=NULL；P=p 一next) for(q=hb；q!=NULL；q=q-next)if(q-data=p-data)break；if(q!=NULL)t=(1klist * )malloc(sizeof(1klist)；t-data=p-data；t 一next=hc ；hc=t ；【试题解析】 顺序扫描在链表 A 和链表 B 中找出相同元素，逐个插入到链表 C中。【知识模块】 线性
20、表25 【正确答案】 truct nodeDatatype data；struct node * next：ListNode；typedef ListNode * LinkList；void DeleteList(LinkList L，DataType min，DataType max)ListNode * P， * q， * h；P=L 一next；采用代表头结点的单链表while(P&p 一datanext；P=q； 保存这个元素位置while(q&q 一datanext：while(p-next!=q)h=p-next：P=P 一next；free(h)；释放空间p-next=q；把断点
21、链上【试题解析】 首先想到的是拿链表中的元素一个个地与 max 和 min 比较，然后删除这个结点。其实因为已知其是有序链表，所以只要找到大于 min 的结点的直接前趋结点，再找到小于 max 的结点，然后一并把中间的全部摘掉就可以了。【知识模块】 线性表26 【正确答案】 typedef struct nodeint data；node * next；node；void locate(node * l，int x)int P=1，found=0；node * q， * t；q=l：while(q-next!=null)if(q 一data=x)coutnext；p+ ；if(!found)t
22、=new node；t-data=X；t 一next=null：q 一next=t： locate【试题解析】 顺序扫描单链表，找到返回，否则在尾部申请结点插入。【知识模块】 线性表27 【正确答案】 DList locate(DList L，ElemType x)L 是带头结点的按访问频度递减的双向链表DList P=L 一next，q； P ：为 L 表的工作指针，q 为 P 的前驱，用于查找插入位置while(P&p 一data!=x)P：p-next； 查找值为 x 的结点if(!P)printf(“不存在所查结点 n”)；exit(0) ；elsep 一freq+； 令元素值为 x
23、的结点的 freq 域加 1p 一next 一pred=p 一pred； 将 P 结点从链表上摘下p 一pred 一next=p 一next；q=p 一pred； 以下查找 P 结点的插入位置while(q!=L&q 一freqfreq)q=q 一pred ；p 一next=q 一next；q 一：next 一pred=P；将 P 结点插入p-pred=q； q 一next=P ；return(P)； 返回值为 x 的结点的指针算法结束【试题解析】 在算法中先查找数据 x，查找成功时结点的访问频度域增 1，最后将该结点按频度递减插入链表中【知识模块】 线性表28 【正确答案】 int Patt
24、ern(LinkedList A，B)A 和 B 分别是数据域为整数的单链表，本算法判断链表 B 是否是链表 A 的子序列。如是，返回 1；否则，返回 0 表示失败。P=A； p 为链表 A 的工作指针，本题假定链表 A 和链表 B 均无头结点pre=P； pre 记住每趟比较中链表 A 的开始结点q=B； q 是链表 B 的工作指针while(P&q)if(p-data=q-data) P=p-next；q=q-next；elsepre：pre-next ；P=pre； 链表 A 新的开始比较结点q=B；q 从链表 B 第一结点开始。if(q=null)return(1)； 链表 B 是链表
25、 A 的子序列else return(0)； 链表 B 不是链表 A 的子序列算法结束【试题解析】 本题实质上是一个模式匹配问题，这里匹配的元素是整数而不是字符。因两整数序列已存入两个链表中，操作从两链表的第一个结点开始，若对应数据相等，则后移指针；若对应数据不等，则链表 A 从上次开始比较结点的后继开始，链表 B 仍从第一结点开始比较，直到链表 B 到尾表示匹配成功。链表 A 到尾链表 B 未到尾表示失败。操作中应记住链表 A 每次的开始结点，以便下趟匹配时好从其后继开始。【知识模块】 线性表29 【正确答案】 LinkedList Common(LinkedList A，B，C)链表 A、
26、链表 B 和链表 c 是三个带头结点且结点元素值非递减排列的有序表。本算法使链表 A 仅留下三个表均包含的结点，且结点值不重复，释放所有结点pa=A-next；pb=B-next；pc：C-next；pa、pb 和 pe 分别是链表 A、B 和 c 的工作指针。pre=A；pre 是链表 A 中当前结点的前驱结点的指针while(pa&pb&pc)当链表 A、B 和 c 均不空时，查找三链表共同元素while(pa&pb)if(pa 一datadata)U=pa；pa=pa-next ；free(U)； 结点元素值小时，后移指针else if(pa-datapb-data)pb=pb-next
27、；else if(pa&pb)处理链表 A 和 B 元素值相等的结点while(pc&pc 一datadata)pc=pc-next；if(pc)if(pc 一datapa 一data) pc 当前结点值与 pa 当前结点值不等，pa 后移指针u=pa；pa=pa-next；free(u) ；elsepc 、pa 和 pb 对应结点元素值相等if(pre=A)pre-next=pa；pre=pa；pa=pa-next 结果表中第一个结点else if(pre-data=pa 一data)(处理)重复结点不链人链表 Au=pa；pa=pa-next；free(u) ；elsepre-next=p
28、a；pre=pa；pa=pa-next ；将新结点链人链表 Apb=pb-next；pc=pc-next；链表的工作指针后移else pc、pa 和 pb 对应结点元素值相等if(pa=null)pre-next=null；原链表 A 已到尾，置新链表 A 表尾else处理原链表 A 未到尾而链表 B 或链表 c 到尾的情况pre-next=null；置链表 A 表尾标记while(pa!=null)删除原链表 A 剩余元素u=pa；pa=pa 一next；free(u) ； 【试题解析】 留下 3 个链表中的公共数据，首先查找链表 A 和链表 B 中公共数据，再去链表 c 中找有无该数据。要消除重复元素，应记住前驱，要求时间复杂度O(m+n+p)，在查找每个链表时，指针不能回溯。算法实现时，链表 A、链表 B 和链表 C 均从头到尾(严格地说链表 B、链表 C 中最多一个到尾)遍历一遍，算法时间复杂度符合 O(m+n+p)。算法主要有while(pa&pb&pc)。【知识模块】 线性表
