第一章
第1章作业：1.1,1.2,1.6 (1) (3) 1.8
1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 ● 数据：指能够被计算机识别、存储和加工处理的信息载体。
● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。
● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。
● 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。
● 逻辑结构：指数据元素之间的逻辑关系。
● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.
● 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。 ● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。
1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。
答：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。
这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。
在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。
1.6 设n为正整数，利用大\记号，将下列程序段的执行时间表示为n的函数。
(1) i=1; k=0; while(i while(i 由以上列出的各语句的频度，可得该程序段的时间消耗： T(n)=1+1+n+(n-1)+(n-1)=3n 可表示为T(n)=O(n) (3) i=1; j=0; while(i+j<=n) { if (i>j) j++; else i++; } 分析： 通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，所以该程序段的执行时间为： T(n)=O(n) 1.8 按增长率由小至大的顺序排列下列各函数：2100, (3/2)n，(2/3)n， nn ,n0.5 , n! ，2n ，lgn ,nlgn, n(3/2) 答：常见的时间复杂度按数量级递增排列,依次为:常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。 先将题中的函数分成如下几类： 常数阶：2 对数阶：lgn K次方阶：n、n 0.5 (3/2) 100 指数阶 (按指数由小到大排)：nlgn、(3/2)n、2n、 n!、 nn 注意：(2/3)^n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。 根据以上分析按增长率由小至大的顺序可排列如下：(2/3)n < 2100 < lgn < n0.5 < n(3/2) < nlgn < (3/2)n < 2n < n! < nn 第二章 第二章作业：2.2，2.6,2.9,2.13 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之， 若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。 2.6 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是无头结点单链表 ListNode *Q,*P; if(L&&L->next){ Q=L;L=L->next;P=L; while (P->next) P=P->next; P->next=Q; Q->next=NULL; } return L; }// Demo 答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。 2.7 设线性表的n个结点定义为(a0,a1,...an-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList. 解：算法如下: #define ListSize 100 // 假定表空间大小为100 typedef int DataType;//假定DataType的类型为int型 typedef struct{ DataType data[ListSize];// 向量data用于存放表结点 int length; // 当前的表长度 } Seqlist; //以上为定义表结构 void InsertList ( Seqlist *L, Datatype x, int i) { //将新结点x插入L所指的顺序表的第i个结点ai的位置上，即插入的合法位置为：0<=i<=L->length int j; if ( i < 0 || i > L -> length ) Error(“position error”);// 非法位置，退出， if ( L->length>=ListSize ) Error(“overflow\ for ( j=L->length-1 ; j >= i ; j --) L->data[ j+1]=L->data [ j ]; L->data[ i ]=x ; L->length++ ; } 2.9 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。 答：因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。 算法如下： //顺序表存储结构如题2.7 void InsertIncreaseList( Seqlist *L , Datatype x ) { int i; if ( L->length>=ListSize) Error(“overflow\ for ( i=L -> length ; i>0 && L->data[ i-1 ] > x ; i--) L->data[ i ]=L->data[ i ] ; // 比较并移动元素 L->data[ i ] =x; L -> length++; } 2.13 设 A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。 解：根据已知条件，A和B是两个递增有序表，所以可以先取A表的表头建立空的C表。然后同时扫描A表和B表，将两表中最大的结点从对应表中摘下，并作为开始结点插入C表中。如此反复，直到A表或B表为空。最后将不为空的A表或B表中的结点依次摘下并作为开始结点插入C表中。这时，得到的C表就是由A表和B表归并成的一个按元素值递减有序的单链表C。并且辅助空间为O(1)。 算法如下： LinkList MergeSort ( LinkList A , LinkList B ) {// 归并两个带头结点的递增有序表为一个带头结点递减有序表 ListNode *pa , *pb , *q , *C ; pa=A->next;//pa指向A表开始结点 C=A;C->next=NULL;//取A表的表头建立空的C表 pb=B->next;//pb指向B表开始结点