《数据结构》(C语言版)习题答案.doc

《《数据结构》(C语言版)习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题1一、选择题1.B2.D3.D4.A5.C6.A7.B8.D9.C10.A二、简答题1.答：数据的逻辑结构通常有四种，即集合、线性结构、树形结构和图状结构。存储结构主要有顺序存储结构和链式存储结构。2.答：比如一分通讯录，记录了相关人员的电话号码，将其按姓名一人占一行构成表，这个表就是一个数据结构。每一行是一个记录，对于整个表来说，只有一个开始结点和一个终端结点，其它结点也只有一个前驱和一个后继。这几个关系就确定了表的逻辑结构。3.答：算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有有穷性、确定性、可行性、输

2、入和输出5个特性。4.答：它是一种树型结构，可以用二元组描述为：A={K,R}K={a,b,c,d,e,f,g,h,i}R={(a,b),(a,c),(c,d),(c,e),(d,f),(d,g),(e,h),(f,i)}5.答：(1)A对应的逻辑图形如下图左，它是一种线性结构。abcdefghabcdefgh(2)B对应的逻辑图形如上图右所示，它是一种树型结构。(3)C对应的逻辑图形如下图所示，它是一种图型结构。123465三、计算题解：(1)O(n)；(2)O(n)；(3)O(n1/2)；（4）略。习题2一、选择题1.A2.B3.B4.D5.A6.C7.B

3、8.A9.C10.C二、简答题1.答：线性表是具有n个数据元素的一个有限序列。线性表的特点是：数据元素之间是一对一的关系。除第一个元素外，每个元素有且只有一个直接前驱；除最后一个元素外，每个元素有且只有一个直接后继。2.答：头指针是链表的一个标识，它用来指向带头结点的链表中的头结点。头结点是在链表的第一个数据元素之前附加的一个结点，它的作用是使对第一个结点的操作和其它结点一致，表空与非空时处理一致，不需要特殊处理，简化了操作。3.答：顺序表的特点是逻辑位置相邻的数据元素其物理位置也相邻，因此可以进行随机存储，是一种随机存储结构。其插入和删除操作的时间复杂度均为

4、O(n)。链表中的数据元素使用一组任意的存储单元存储，不要求逻辑位置相邻的数据元素物理位置也相邻，而是采用附加的指针表示元素之间的逻辑关系。链表的插入和删除结点均不需要移动其他结点，但是，其查找运算必须从头指针开始顺序查找，其时间复杂度为O(n)。4.答：算法如下voidConvert(SqList&L){inti,j,temp;j=L.length-1;i=0;while(i

5、SqListLb){inti,j,k;i=0;j=0;while(iLb.elem[j])j++;elseListDelete_Sq(La,i+1,k);}}6.答：算法如下voidInvertList(LinkList&L){LinkListp,q,r;p=L->next;q=p->next;p->next=NULL;while(q!=NULL){r=q->next;q->next=p;p=q;q=r;}L->nex

6、t=p;}7.答：算法如下voidMergeOrder(LinkListLa,LinkListLb){LinkListpa,pb,Lc,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}if(!pa)pc->next=pb;elsepc->next=pa;}8.答略。9.答：算法如下intLength(LinkListL){inti

7、=0;LinkListp;p=L->next;while(p){p=p->next;i++;}returni;}习题3一、选择题1.C2.B3.A4.D5.B6.A7.C8.A9.B10.B二、简答题1.答：栈是限定在表的一端进行插入和删除操作的线性表。队列是只允许在表的一端进行插入，而在另一端进行删除元素的线性表。栈的操作是按照后进先出原则进行的，因此又称作后进先出的线性表。队列的操作是按照先进先出原则进行的，因此又称作先进先出的线性表。2.答：当front¹0，rear=M时，再有元素入队发生溢出，称之为“假溢出”，存储空间还有剩余。为了改进这种状况，可以

8、将顺序队列想象为一个首尾相接的环状空间