《习题一线性结构部分习题剖析》由会员分享，可在线阅读，更多相关《习题一线性结构部分习题剖析（32页珍藏版）》请在金锄头文库上搜索。
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.多项式的建立，两个多项式的相加，两个多项式的相乘算法,6/32,单项选择题,7/32,单项选择题,8/32,单项选择题,9/32,单项选择题,10/32,单项选择题,11
3、/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.栈的定义及特点 栈的定义、栈顶与栈底概念 栈的基本运算，包括进栈、出栈、判空栈、置空栈等 2.栈的存储表示 顺序栈的实现及基本操作 链式栈的实现及基本操作 3.队列的定义及特点 队列的定义、先进先出特点 队列的基本运算，包括进队、出队、判队空、置空
4、队,14/32,复习要点（2）,4.队列的存储表示 队列的顺序存储及基本操作 队列的链式存储及基本操作 5.栈的应用 栈在递归过程中作为工作栈的使用，栈在表达式计算中从中缀表示转后缀表示，栈在括号配对中的应用，栈在数制转换中的应用 双栈共用一个数组的进栈、退栈、置空栈算法及栈满、栈空条件，使用两个栈模拟一个队列时的进队列和出队列算法。,15/32,复习要点（3）,6.队列的应用 队列在分层处理中的使用，包括二叉树、树、图等 层次遍历过程中的使用 队列在对数据循环处理过程中的使用，例如约瑟夫问题、归并排序 队列在调度算法中的使用,16/32,单项选择题,例1 为解决计算机主机与打印机之间速度不匹
5、配的问题，通常设置一个打印数据缓冲区。主机将要打印输出的数据依次写入缓冲区，而打印机则依次从该缓冲区中取出数据，该缓冲区的逻辑结构应该是（ ）。 A、栈 B、队列 C、树 D、图,【解答】 B。通常用于输入输出的缓冲区都是采用先入先出的队列。,17/32,单项选择题,例2 设栈S和队列Q的初始状态都为空，元素a,b,c,d,e,f,g依次进入栈S.如果每个元素出栈后立即进入队列Q，且7个元素出队的顺序为b,d,c,f,e,a,g,则栈S的容量至少是_; A.1 B.2 C.3 D.4,【解答】C。队列的特点是先进先出，出队顺序和入队顺序一致，即与出栈顺序一致。如果用S表示进栈，用X表示出栈，则
6、进栈/出栈序列为下图。由图知，栈中最多时有3个元素，所以栈的容量最少为3。,18/32,单项选择题,例3 假设一个循环队列QmaxSize的队头指针为front，队尾指针为rear，队列的最大容量为maxSize，除此之外，该队列再没有其他数据成员，则该队列的队满条件是_。 A . Q.front = Q.rear B. Q.front+Q.rear = maxSize C. Q.front = (Q.rear+1) % maxSize D. Q.rear = (Q.front+1) % maxSize,【解答】C。既然不能附加任何其他数据成员，只能采用牺牲一个队列元素的整除取余的方式区分队空
7、和队满的条件，因此选项C是合理的，选项A是判断队列是否为空的条件，其他都是干扰项。,19/32,综合应用题,例1 铁路进行列车调度时，常把站台设计成栈式结构的站台，如右图所示。试问： （1）设有编号为1，2，3，4，5，6的六辆车，顺序开入栈式结构的站台，则可能的出栈序列有多少种？ （2）若进站的六辆列车顺序如上所述，那么是否能够得到435612，325641，154623和135426的出站序列，如果不能，说明为什么不能；如果能，说明如何得到（即写出“进站”或“出站”的序列）。,20/32,综合应用题,编号大的车开出后，编号比其小的车反序开出，即编号大的车开出后，编号比其小的车只能由大到小依
8、次开出（中间可以插入编号更大的车，但此车后面编号比其小的车也要遵守此规则） 出栈序列种数：,当n=4时 Cn=14,出栈序列：4321 3421，3241，3214 2431，2341，2314，2143，2134 1432，1342，1324，1243，1234,21/32,综合应用题,22/32,综合应用题,例4 请综述栈的基本性质。,23/32,思想:,使用栈记录走过的路径,若当前位置不通，标记该位置，退栈，寻找新路径,若当前位置通，进栈，寻找新路径,综合应用题,例5 迷宫求解,24/32,迷宫算法描述,设入口位置为当前位置；,若当前位置可通，则将当前位置进栈；,若该位置是出口位置，则成
9、功；,否则置当前位置的东邻方块为新的当前位置；,否则，,若栈不空且栈顶位置上有其他方向未经探索，则置当前位置的下一相邻方块为新的当前位置。,若栈不空且栈顶位置的四周都不通，则栈顶出栈，标记不通；重新测试新的栈顶位置，直至找到一个可通的相邻块作为新的当前位置。,25/32,初始，1.1当前位置，可通，进栈,1.2当前位置，可通，进栈,1.3不通，2.2为当前位置，进栈,北,南,东,西,2.3不通，3.2为当前位置，进栈,3.3可通，进栈,3.4、4.3、3.2、2.3均不通,3.3出栈，3.2为新栈顶元素,3.3、4.2不通，3.1为当前位置，进栈,26/32,综合应用题,例6 写出将单链表逆置
10、的算法，即由单链表A产生单链表B，使得A的最后一个元素是B的第一个元素，依次类推。,27/32,单链表反转 （方法一：非递归算法）,struct ListNode EIEM element; ListNode *link; ; Typedef ListNode *ListPtr; ListPtr invert(ListPtr head) ListPtr middle,trail; middle=NULL; while(head) trail=middle; middle=head; head=head-link; middle-link=trail; return middle; ,28/32
11、,单链表反转 （方法二：递归算法）,class DLList public: DLList() head = tail = 0; void R() reverse( head ); DLLNode * tmp; tmp = head; head = tail; tail = tmp; tail - next = 0; void addtotail( int ,void DLList:reverse( DLLNode * n ) DLLNode * t1 = n, * t2 = n -next; if ( t2 -next != 0 ) reverse( t2 ); t2 - next = t1
12、; ,29/32,单链表反转 （方法三：借助栈实现）,30/32,综合应用题,例7 递归算法求： (1)求链表的结点个数 int List : Num(ListNode * f) if (f=0) return 0; return 1+Num(f-link); ,31/32,综合应用题,(2)求链表中的最大整数 int List : Max(ListNode * f) if (f-link=0) return f-data; /递归结束条件 /*在当前结点的后继链表中求最大值*/ int temp=Max(f-link); /*如果当前结点值大，返回当前结点值*/ if (f-data temp) return f-data; else return temp; /否则返回后继链表中的最大值 ,32/32,综合应用题,(3)求所有整数的平均值 float List : Avg (ListNode *f, int ,
