第一章
第1章作业：1.1,1.2,1.6 (1) (3) 1.8
1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。
● 数据：指能够被计算机识别、存储和加工处理的信息载体。
● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。
● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。
● 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。
● 逻辑结构：指数据元素之间的逻辑关系。
● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.
● 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。 ● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。
1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。
答：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。
这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。
在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。
1.6 设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
(1) i=1; k=0;
while(i<n)
{ k=k+10*i;i++;
}
分析：
i=1; //1
k=0; //1
while(i<n) //n
{ k=k+10*i; //n-1
i++; //n-1
}
由以上列出的各语句的频度，可得该程序段的时间消耗：
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、n0.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表开始结点
free(B);//回收B表的头结点空间
while ( pa && pb)
{
if ( pb->data <= pa->data )
{ // 当B中的元素小于等于A中当前元素时，将pa表的开始结点摘下
q=pa;pa=pa->next;
}
else
{// 当B中的元素大于A中当前元素时，将pb表的开始结点摘下
q=pb;pb=pb->next;}
q->next=C->next;C->next=q;//将摘下的结点q作为开始结点插入C表
}
//若pa表非空，则处理pa表
while(pa){
q=pa;pa=pa->next;
q->next=C->next;C->next=q;}
//若pb表非空，则处理pb表
while(pb){
q=pb;pa=pb->next;
q->next=C->next;C->next=q;}
return(C);
}
该算法的时间复杂度分析如下：
算法中有三个while 循环，其中第二个和第三个循环只执行一个。每个循环做的工作都是对链表中结点扫描处理。整个算法完成后，A表和B表中的每个结点都被处理了一遍。所以若A表和B表的表长分别是m和n，则该算法的时间复杂度O(m+n)
●练习2.1：写出在线性表中的查找运算算法。
即查找数据元素x在表中的位置，也就是数据元素下标值加1。
例如：若L.data[i]=x,则返回i+1;若不存在，则返回n+1
练习2.2：编写尾插法建立链表的算法。
练习2.3：若是带头指针的单链表，算法又是怎样？
若是两个链表，既知道头结点，又知道尾结点，算法又是怎样？
●练习2：按升序打印带头结点h的单链表中各节点的数据域值，并将打印完的节点从表中删除。
第三章
第三章作业：3.2, 3.3，3.4（2）， 3.6， 3.11
3.2 循环队列的优点是什么? 如何判别它的空和满?
答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。
3.3设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?
答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。
3.4 指出下述程序段的功能是什么?
(2) SeqStack S1, S2, tmp;
DataType x;
...//假设栈tmp和S2已做过初始化
while ( ! StackEmpty (&S1))
{
x=Pop(&S1) ;
Push(&tmp,x);
}
while ( ! StackEmpty (&tmp) )
{
x=Pop( &tmp);
Push( &S1,x);
Push( &S2, x);
}
(2)程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。 3.6 利用栈的基本操作，写一个将栈S中所有结点均删去的算法void ClearStack( SeqStack *S)，并说明S为何要作为指针参数
解：算法如下
void ClearStack (SeqStack *S)
{ // 删除栈中所有结点
S->Top = -1; //其实只是将栈置空
}
因为要置空的是栈S，如果不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响，系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。 3.8 设计算法判断一个算术表达式的圆括号是否正确配对。 (提示： 对表达式进行扫描，凡遇到‘(’就进栈，遇‘)’就退掉栈顶的‘(’，表达式被扫描完毕，栈应为空。
解：
根据提示，可以设计算法如下：
int PairBracket( char *SR)
{//检查表达式SR中括号是否配对
int i;
SeqStack S; //定义一个栈
InitStack (&s);
for (i=0; i<strlen(SR) ; i++)
{
if ( SR[i]==‘(’ ) Push(&S, SR[i]); //遇‘(’时进栈
if ( SR[i]==‘)’ ) //遇‘)’
if (!StackEmpty(S))//栈不为空时，将栈顶元素出栈
Pop(&s);
else return 0;//不匹配，返回0
}
if （EmptyStack(&s)） return 1;// 匹配，返回1
else return 0;//不匹配，返回0
} 6.12 若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。
(1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。
(2)已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。
(3)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉树。
解：
(1)已知二叉树的前序序列为ABDGHCEFI和中序序列GDHBAECIF，则可以根据前序序列找到根结点为A，由此，通过中序序列可知它的两棵子树包分别含有GDHB和ECIF结点，又由前序序列可知B和C分别为两棵子树的根结点...以此类推可画出所有结点：
○A
/ \
○B ○C
/ / \
○D ○E○F
/ \ /
○G ○H ○I
(2)以同样的方法可画出该二叉树：
○A
/ \
○B ○F
\ \
○C ○G
/ \ \
○D ○E ○H
(3)这两棵不同的二叉树为：
○A ○A
/ \
○B ○B
6.21 以二叉链表为存储结构， 写一算法交换各结点的左右子树。
答：要交换各结点的左右子树，最方便的办法是用后序遍历算法，每访问一个结点时把两棵子树的指针进行交换，最后一次访问是交换根结点的子树。
void ChangeBinTree(BinTree *T)
{ //交换子树
if(*T)
{ //这里以指针为参数使得交换在实参的结点上进行后序遍历
BinTree temp;
ChangeBinTree(&(*T)->lchild);
ChangeBinTree(&(*T)->rchild);
temp=(*T)->lchild;
(*T)->lchild=(*T)->rchild;
(*T)->rchild=temp;
}
}
9.11试写出二分查找的递归算法。
解：
int BinSearch(SeqList R，KeyType K，int low，int high)
{ //在有序表R[low..high]中进行二分查找，成功时返回结点的位置，失败时返回零
int mid； //置当前查找区间上、下界的初值
if (low<=high){ //当前查找区间R[low..high]非空
mid=(low+high)/2；
if(R[mid].key==K) return mid； //查找成功返回
if(R[mid].key>K)
return BinSearch( R，K,low，mid-1)//在R[low..mid-1]中查找
else
return BinSearch( R，K,mid+1，high)； //在R[mid+1..high]中查找
}
return 0； //当low>high时表示查找区间为空，查找失败
} //BinSeareh
10.7. 将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中，重写直接插入排序算法。
解：
重写的算法如下：
void InsertSort(SeqList R)
{//对顺序表中记录R[0..n-1]按递增序进行插入排序
int i,j;
for(i=n-2;i>=0;i--) //在有序区中依次插入R[n-2]..R[0]
if(R[i].key>R[i+1].key) //若不是这样则R[i]原位不动
{
R[n]=R[i];j=i+1; //R[n]是哨兵
do{ //从左向右在有序区中查找插入位置
R[j-1]=R[j]; //将关键字小于R[i].key的记录向右移
j++;
}while(R[j].key<R[n].key]);
R[j-1]=R[n]; //将R[i]插入到正确位置上
}//endif
}//InsertSort.
12.1 常见的文件组织方式有哪几种?各有何特点? 文件上的操作有哪几种? 如何评价文件组织的效率?
答：
常用的文件组织方式有：顺序文件、索引文件、散列文件和多关键字文件。
●顺序文件的特点是，它是按记录进入文件的先后顺序存放，其逻辑结构和物理顺序是一致的。
●索引文件的特点是，在主文件之外还另外建立了一张表，由这张表来指明逻辑记录和物理记录之间的一一对应关系。索引文件在存储器上分为两个区：索引区和数据区，前者存放索引表，后者存放主文件。
●散列文件是利用散列存储方式组织的，它类似于散列表，即根据文件中关键字的特点，设计一个散列函数和处理冲突的方法，将记录散列到存储设备上，对于散列文件，磁盘上的文件记录通常是成组存放的。
●多关键字文件则包含有多个次关键索引的，不同于前述几种文件，只含有一个主关键字。
文件的操作有两种：检索和维护 。
评价一个文件组织的效率，是执行文件操作(如查找、删除等)所花费的时间和文件组织所需的存储空间。