例题讲解0609.pptxVIP

第一章 概述例题1：分析以下程序段的时间复杂度。a=0；b=1；①for（i=2；i〈=n；i++）②{s=a+b；③b=a；④a=S；⑤}解：因为，语句①的频度是2；语句②的频度是n；语句③的频度是n-1；语句④的频度是n-1；语句⑤的频度是n-1；故，该程序段的时间复杂度T（n）=2+n+3*（n-1）=4n-1=O（n）。 例题2：分析以下程序段的时间复杂度。inti，j，k；For（i=0；i〈n；i++〉①For（j=0；j〈n；j++〉②{c[i][j]=0；③for（k=0；k〈n；k++〉④c[i][j]=c[i][j]+a[i][k]+b[k][j]；⑤}解：语句①的循环控制变量i要增加到n，测试到i=n成立才会终止，故它的频度为n+1；语句②作为语句①循环体内的语句应该执行n次，但语句②本身要执行n+1次，故语句②的频度是 n （n+1）；同理可得语句③、④和⑤的频度分别是n2，n2（n+1）和n3。该程序段所有语句的频度之和为： T（n）=2n3+3n2+2n+1其复杂度为O（n3）。第二章 线性表及其顺序存储例题1：已知一个顺序表中的元素按元素值非递减有序排列，编写一个函数删除表中多余的值相同的元素。解： 本题的算法思想是：由于顺序表中元素已按元素值非递减有序排列，值相同的元素比为相邻的元素，因此依次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找，直到最后一个元素。实现本题功能的函数如下：voiddel ( seqlist*a ){int i=0, j;while ( ia-length) if ( a-data[i]!= a-data[i+1])i++; else { for ( j=i; ja-length; j++) a-data[j]=a-data[j+1]; a-length--; }}例题2：利用栈的基本操作，写一个返回栈中结点个数的算法int StackSize (SeqStackS)，并说明S为何不用作为指针参数？解：根据题意，设一变量count来统计栈中结点的个数，从栈顶元素出发，循环执行出栈运算，直到栈空。实现本题功能的函数如下：intStackSize (SeqStackS){intcount=0;while (!StackEmpty (S)) {conut++;Pop (s);}}说明：依据题意，该算法只需统计栈中结点个数，执行完函数后不能修改实参栈的内容。所以，在该函数中，S不能用作指针参数。第三章 线性表及其链式存储单选题1、下列4种基本的逻辑结构中，数据元素之间关系最弱的是( ? ???)。A．集合B．线性结构C．树状结构D．图(网)状结构2.线性表采用链式存储结构时，内存中可用存储单元的地址（ ） A.必须是连续的B.部分地址必须是连续的 C.一定是不连续的D.连续或不连续都可以3. 以下关于链式存储结构的叙述中，不正确的是（ ）。A．结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B．逻辑上相邻的结点物理—不必邻接C．可以通过计算直接确定第i个结点的存储地址D．插入、删除运算操作方便，不必移动结点4. 下面叙述正确的是( )A．在顺序存储的线性表中，逻辑上相继的两个数据元素在物理位置并不一定紧邻 B．链式存储的线性表可以随机存取 C．顺序存储的线性表可以随机存取 D．在线性表的顺序存储结构中，插入和删除元素时，移动元素的个素仅与元素的位置有关5.若已知一个栈的入栈序列是1，2，3，…，n， 则其不可能的输出序列为为 （ ） Ａ．4, 3 ,2 ,1Ｂ．1, 2, 3, 4 Ｃ．1, 3, 2,4Ｄ．1, 4, 2,36.数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为 Ａ.r－f;Ｂ.（n＋f－r）% n; Ｃ.n＋r－f;Ｄ.（n＋r－f）% n7.用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为 A. 1和 5 B. 2和4 C. 4和2 D. 5和1 8.带头结点的循环链表head为空的判定条件全( )。A．head＝；NULL B．Head—＞next＝NULＬC．head—＞next＝＝head D．Head!＝NULL9、从栈顶指针为Top的链栈中删除一个结点，并将被删节点的值保存到x中，其操作步骤为（ ） A、x=Top-info; Top=Top-next B、Top=Top-next; x=Top-info C、x=Top; T