前三章大题前三章大题.doc

(1) 评价算法的标准很多，通常是以执行算法所需要的 和所占用的 来判别一个算法的优劣。时间 空间 (2) 任何一个算法的设计取决于选定的 ，而算法的实现依赖于采用的 。 逻辑结构 存储结构 (3) 算法时间复杂度的分析通常有两种方法，即 和 的方法，通常我们对算法求时间复杂度时，采用后一种方法。事后统计，事前估计 6． (1)在树型结构中，树根结点没有 结点，其余每个结点的有且只有 个前趋驱结点；叶子结点没有 结点；其余每个结点的后续结点可以 。前趋，一，后继，多 (2)在图型结构中，每个结点的前趋结点数和后续结点数可以 。有多个 三、判读题（对的打“√”，错的打“×”。） (√)1. 数据的逻辑结构与数据元素本身的内容和形式无关 。 (√)2. 算法可以没有输入，但是必须有输出 。 (×)3. 线性结构只能用顺序结构存放，非线性结构只能用链表存放。 (√)4. 抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。 四、应用题 设ｎ为正整数，试确定下列程序段中语句“x++;”的频度。 (1)for (i=1;i=n;i++) for (j=1;j=i;j++) x++; 参考答案： 语句频度=1+2+…+n=。 (2)i=0; j=1; while (i+j=n){ x++; if (ij) j++; else i++; } 参考答案： 语句频度＝ｎ。 (3)for (i=1;i=n;i++) for (j=1;j=i;j++) for (k=1;k=n;k++) x++; 参考答案： 语句频度=。 (4)x=0;y=n; //n是不小于1的常数 while (y=(x+1)*(x+1)){ x++; } 参考答案： 语句频度=。 (5)设n为正整数，试确定如下程序段中if语句的频度。 x=91; y=100; while(y0){ if (x100){x-=10;y--;} else x++; } 参考答案： 语句频度=1100 二、应用题 1．线性表(a1,a2,…,an)，采用带头结点的单链表存储，头指针为H，每个结点中存放线性表中的一个元素，现要求查找某个元素值等于X的结点。分别写出下面三种情况的查找语句，要求时间尽量少。 (1)线性表中元素无序。(2)线性表中元素按递增有序。(3)线性表中元素按递减有序。 参考答案： 单链表带头结点，设工作指针p初始化为p=H-next; (1) while(p!=null p-data!=X) p=p-next; if(p= =null) return(null);∥查找失败 else return(p);∥查找成功 (2) while(p!=null p-dataX ) p=p-next; if(p==null || p-dataX) return(null);∥查找失败 else return(p); (3) while(p!=null p-dataX) p=p-next; if(p==null || p-dataX) return(null); ∥查找失败 else return(p); ∥查找成功 2．按照下列题目中的算法功能说明，将算法描述片段中的错误改正过来。 (1)下面的算法描述片段用于在双链表中删除指针变量p所指的结点： p-next = p-prior-next; p-prior= p-next-prior; free(p); 参考答案： 前两个语句改为：p-prior-next= p-next; p-next-prior= p-prior; (2)下面的算法描述片段用于在双链表中指针变量p所指结点后插入一个新结点： q=(dlinklist *)malloc(sizeof(dlinklist)); q- prior =p; p- next =q; q- next =p- next; q = p- next - prior; 参考答案： 后三个语句序列应改为： q-next =p-next; p-next-prior =q; p-next =q; 3．一线性表存储在带头结点的双向循环链表中，L为头指针。如下算法： void unknown (Dlinkli