习题和实验指导解答2.pdf

《习题和实验指导解答2.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章习题、思考题和上机题解答2.1习题2解答1.算法或程序阅读题（1）阅读下列程序，将其中函数（算法）Del_k，其功能是从线性表的第i个元素起，删除连续的k个元素，改为一个正确而高效的函数(算法):#includeconstintMaxSize=100;voidDel_k(inta[],int&length,inti,intk){//a[0]~a[length-1]存放线性表元素,删除从第i个元素起的k个元素if(i<0

2、

3、i>length-1

4、

5、k<0

6、

7、length>MaxSize

8、

9、i+k>length+

10、1){cout<<"error"<i+1;j--)a[j-1]=a[j];length=length-1;}}}voidmain(){inta[9]={1,2,3,4,5,6,7,8,9};intlength=9;inti=2;intk=3;Del_k(a,length,i,k);for(intj=0;j

11、,j;for(count=0;counti+1;j--)a[j-1]=a[j];length=length-1;}改为：for(intj=i+k;jvoidDifference(LinkList&A,Linkl

12、istB){Node*pre,*p,*q=B.first;while(q!=NULL){pre=A.first,p=pre->next;1--while(p!=NULL&&p->data!=q->data){pre=p;p=p->next;}if(p!=NULL&&p->data==q->data){pre->next=p->next;deletep;p=pre->next;}q=q->next;}}试用集合A为{1,3,5,6}，B为{3,6}，执行该算法，给出结果。并将该算法改写成自然语言描写的伪代码形式。【解答】用集

13、合A为{1,3,5,6}，B为{3,6}，执行该算法的结果是{1,5}。该算法的自然语言描写的伪代码形式为：两集合单链表表示下差算法Difference伪代码1.将q指针初始化指向B的第一个结点2.只要q不为空，执行2.1指针pre和p分别初始化指向A的头结点和第一个结点2.2只要p!=NULL且p->data!=q->data，pre和p分别向前移动扫描一步2.3若p!=NULL且p->data==q->data,则将p结点从A中删除2.4q指针向前移动扫描一步2.论述题（1）试论顺序表、顺序存储、顺序存取以及随机存取之间的区别。【

14、解答】顺序表是指将线性表逻辑相邻元素映射在物理位置上也相邻的内存中的一种存储结构的统称，通常用数组来具体实现。顺序存储指的顺序表实现中的存储方式。顺序存储指的是访问表中某个元素必须先顺次由前往后扫描完其前面的所有元素，或顺次由后往前扫描完其后面的所有元素之后，才能访问该元素的一种访问方法。随机存取指的是访问某个数据元素时直接定位访问而不需扫描其它元素的一种访问方法。(2)试给出单链表的头指针、头结点、第一个结点的区别，并说明头指针和头结点的作用。【解答】头指针指的是链表访问的入口地址。头结点往往是指在单链表中实际存放数据元素的第一个结

15、点之前虚设的一个结点。第一个结点又称开始结点或始结点，是存放第一个数据元素的结点。其最大区别是，头指针是指针，而头结点和第一个结点都指的是结点。头指针的作用是帮助标识单链表的入口，对单链表结点的访问都从头指针开始。头结点的作用是使得头指针始终不为空，减少某些操作进行之前判断头指针是否为空的判断，使得在带头结点的单链表，不管是空表还是非空表，不同位置上，插入、删除等操作达到统一，从而代码得以简化。(3)有哪些链表可由一个尾指针唯一确定？即从尾指针出发能访问表上任何一个结点。【解答】循环单链表、双链表和循环双链表都可通过设置尾指针唯一确定

16、对应的链表，且能从尾指针出发访问表上任何一个结点。3.填空题(1)等概率情况下，在顺序表中插入和删除一个元素平均都分别需约移动______个元素。在______处插入元素不需要移动元素,而在处插入元素需要移动全部元素。【