算法与数据结构（C 语言版）（冯广慧第2版）课后习题答案 第1--4章.docx

习题答案1

选择题

ADDACC

填空题

（1）树形结构、（2）图形结构

（1）确定性、（2）输出

（1）时间复杂度、（2）空间复杂度

（1）1:1、（2）1:n、（3）n:n

判断题

1-4错错对对

习题答案2

选择

1-10：ADBACABDAD

填空

1、（a）元素的存储位置（b）指针

2、p-next!=NULL

3、L-next==L或L-prior==L或L-prior==LL-next==L…或L-next==L-next…..

（a）O(1)（b）O(n)

判断

1-6：对错错错错错

四、应用

1、在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。

2、选顺序存储结构。顺序表可以随机存取，时间复杂度为O（1）。

3、链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储结构的缺点。

4、参见2.6节

5、单循环链表往往只设尾指针而不设头指针，用一个指向尾结点的尾指针来标识单循环链表，好处是既方便查找表尾结点又方便查找头结点，因为通过尾结点的指针域很容易找到头结点。若使用头指针查找表尾结点需要从头遍历链表，时间复杂度是O(n)。

五、算法设计题

1、SeqListRearrange(SeqLista)

{ inti,j,t;

i=0;j=a.Last-1;//i,j为工作指针(下标)

t=a.data[0];//暂存枢轴元素。

while(ij)

{ while(ija.data[j]=0)j--; //j指针前移找小于0的元素

if(ij)a.data[i++]=a.data[j]; //将负数前移

while(ija.data[i]0)i++;//i指针后移找大于等于0的元素

if(ij)a.data[j--]=a.data[i]; //正数后移

}

a.data[i]=t; //将原第一元素放到最终位置

returna;

}

2、

(1)LinkedListDelSame（LinkedListla）

{ pre=la-next； ∥pre是p所指向的前驱结点的指针

p=pre-next； ∥p是工作指针，设链表中至少有一个结点

while（p）

if（p-data==pre-data）∥相同元素值,释放结点

{u=p；pre-next=p-next;p=p-next；free（u）；}

else

{pre=p；p=p-next；} ∥元素值不同

returnla;

}

(2)算法时间复杂度O(n)

3、DLinkedListDInsert(DLinkedListla,ElemTypex)

{ p=la-next; ∥p指向第一元素

∥MaxElemType是和x同类型的机器最大值，用做监视哨

la-data=MaxElemType;

while(p-datax) ∥寻找插入位置

p=p-next?;

s=(DLNode*)malloc(sizeof(DLNode));∥申请结点空间

s-data=x;

s-prior=p-prior; ∥将插入结点链入链表

s-next=p;

p-prior-next=s;

p-prior=s;

}

4、（1）①分别求出str1和str2所指的两个链表的长度m和n；②将两个链表以表尾对齐：即长的链表将指针移到|m-n+1|,短链表的指针指向链表的第一个字母；=3\*GB3③两个链表进行模式匹配：对应字母比较，从最后遇到两个链表结点值相等，直至到表尾对应结点值都相等为止。要注意处理虽然首次遇到对应结点值相等，但有后续结点值不等的情况,即在匹配中，并非一遇到对应字母相等，就结论后边是共同后缀。

（2）求用单链表表示的两个单词的共同后