线性表部分习题

《线性表部分习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、线性表习题2/32本节重点复习要点单项选择题综合应用题3/32线性表-复习要点（1）1.线性表的概念线性表的定义和特点线性表的基本操作2.线性表的存储表示顺序表的定义及基本运算的实现单链表的定义及基本运算的实现3.线性表的特殊链接表示循环链表的特殊遍历方式双向链表的方向性4/32线性表-复习要点（2）4.线性表的应用（1）在一维数组上的算法，如原地逆置、非零元素压缩、成块元素移动等。在一维数组上的递归算法，如求和平均值等。在顺序表上的查找、插入、删除、合并、求交等算法及性能分析。在单链表上的迭代求

2、解算法及性能，包括统计链表结点个数、在链表中寻找与给定值x匹配的结点、在链表中寻找第i个结点、链表逆转等。5/32线性表-复习要点（3）4.线性表的应用（2）带表头结点的单链表上的迭代算法，包括统计链表结点个数、在链表中寻找与给定值x匹配的结点、在链表中寻找第i个结点、两个有序链表的合并等。单链表的递归算法，包括统计链表结点个数、在链表中寻找与给定值x匹配的结点、在链表中寻找第i个结点、求链表各结点值的和、平均值等。循环链表的迭代算法、双向链表的迭代算法。5.多项式的建立，两个多项式的相加，两个多

3、项式的相乘算法6/32单项选择题7/32单项选择题8/32单项选择题9/32单项选择题10/32单项选择题11/32单项选择题例11若在长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度是（）。A.O(n)B.O(1)C.O(n2)D.O(log2n)【解答】B。在有n个元素的顺序表的表尾插入一个新元素，可直接在表的第n+1个位置插入，渐进时间复杂度为O(1)。12/32综合应用题此题还有其他做法13/32复习要点（1）1.栈的定义及特点栈的定义、栈顶与栈底概念栈的基本运算，包括进栈、出栈、判空

4、栈、置空栈等2.栈的存储表示顺序栈的实现及基本操作链式栈的实现及基本操作3.队列的定义及特点队列的定义、先进先出特点队列的基本运算，包括进队、出队、判队空、置空队14/32复习要点（2）4.队列的存储表示队列的顺序存储及基本操作队列的链式存储及基本操作5.栈的应用栈在递归过程中作为工作栈的使用，栈在表达式计算中从中缀表示转后缀表示，栈在括号配对中的应用，栈在数制转换中的应用双栈共用一个数组的进栈、退栈、置空栈算法及栈满、栈空条件，使用两个栈模拟一个队列时的进队列和出队列算法。15/32复习要点（3

5、）6.队列的应用队列在分层处理中的使用，包括二叉树、树、图等层次遍历过程中的使用队列在对数据循环处理过程中的使用，例如约瑟夫问题、归并排序队列在调度算法中的使用16/32单项选择题例1为解决计算机主机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区。主机将要打印输出的数据依次写入缓冲区，而打印机则依次从该缓冲区中取出数据，该缓冲区的逻辑结构应该是（）。A、栈B、队列C、树D、图【解答】B。通常用于输入输出的缓冲区都是采用先入先出的队列。17/32单项选择题例2设栈S和队列Q的初始状态都为空

6、，元素a,b,c,d,e,f,g依次进入栈S.如果每个元素出栈后立即进入队列Q，且7个元素出队的顺序为b,d,c,f,e,a,g,则栈S的容量至少是__;A.1B.2C.3D.4【解答】C。队列的特点是先进先出，出队顺序和入队顺序一致，即与出栈顺序一致。如果用S表示进栈，用X表示出栈，则进栈/出栈序列为下图。由图知，栈中最多时有3个元素，所以栈的容量最少为3。18/32单项选择题例3假设一个循环队列Q[maxSize]的队头指针为front，队尾指针为rear，队列的最大容量为maxSize，除此

7、之外，该队列再没有其他数据成员，则该队列的队满条件是__。A.Q.front==Q.rearB.Q.front+Q.rear>=maxSizeC.Q.front==(Q.rear+1)%maxSizeD.Q.rear==(Q.front+1)%maxSize【解答】C。既然不能附加任何其他数据成员，只能采用牺牲一个队列元素的整除取余的方式区分队空和队满的条件，因此选项C是合理的，选项A是判断队列是否为空的条件，其他都是干扰项。19/32综合应用题例1铁路进行列车调度时，常把站台设计成栈式结构的站台

8、，如右图所示。试问：（1）设有编号为1，2，3，4，5，6的六辆车，顺序开入栈式结构的站台，则可能的出栈序列有多少种？（2）若进站的六辆列车顺序如上所述，那么是否能够得到435612，325641，154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到（即写出“进站”或“出站”的序列）。20/32综合应用题编号大的车开出后，编号比其小的车反序开出，即编号大的车开出后，编号比其小的车只能由大到小依次开出（中间可以插入编号更大的车，但此车后面编号比其小的车