数据结构(1,2,3章)课后题答案

数据结构课后部分习题答案提示授课教师：耿国华教授西北大学可视化技术研究所西北大学可视化技术研究所第一章：绪论1.2判断题（在各题后填写“√”或“×”）：（1）线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（×）（2）算法就是程序。（×）（3）在高级语言（如C或PASCAL）中，指针类型是原子类型。（√）西北大学可视化技术研究所西北大学可视化技术研究所1.3填空题：（1）变量的作用域是指变量的有效范围（2）抽象数据类型具有数据抽象、信息隐蔽的特点。（3）一种抽象类型包括数据对象、结构关系和基本操作。西北大学可视化技术研究所西北大学可视化技术研究所（4）当需要用一个形式参数直接改变对应实参的值时，该形式参数应说明为指针类型。（5）数据结构的逻辑结构分为集合结构、线性结构、树形结构和图结构四种。（6）数据结构的存储结构分为顺序存储结构和链式存储结构两种。西北大学可视化技术研究所西北大学可视化技术研究所（7）在线性结构、树形结构和图结构中，数据元素之间分别存在着一对一、一对多和多对多的联系。（8）算法是规则的有限集合，是为解决特定问题而规定的操作序列。（9）算法具有有限性、确定性、可行性、输入、输出五大特性。西北大学可视化技术研究所西北大学可视化技术研究所1.4选择题（1）若需要利用形式参数直接访问修改实参值，则应将形参说明为A参数。A.指针B.值参数西北大学可视化技术研究所西北大学可视化技术研究所（2）执行下面的程序段的时间复杂度为C。for(inti=0;im;i++)for(intj=0;jn;j++)a[i][j]=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)西北大学可视化技术研究所西北大学可视化技术研究所(3)执行下面程序段时，语句S的执行次数为C。for(inti=0;i=n;i++)for(intj=0;j=i;j++)S;A.n2B.n2/2C.(n+1)(n+2)/2D.n(n+1)/2西北大学可视化技术研究所西北大学可视化技术研究所5.计算下列程序段中x=x+1的语句频度：for(i=1;i=n;i++)for(j=1;j=i;j++)for(k=1;k=j;k++)x=x+1;思路:语句频度即为时间频度，拆分循环语句，先从后两个for循环开始思考，最后循环i值。第一步：西北大学可视化技术研究所1(1)123...2ijiiji西北大学可视化技术研究所第二步:计算结果2ni=111(1+i)i222nniiii22211(12...)(12...)22nn1(21)(1)1(1)()()2622nnnnn32623nnn西北大学可视化技术研究所6.编写算法，求一元多项式：算法描述：voiddxs(inta[],intn,intx){inttemp=x;//temp保存x的幂次方intsum=0;//sum保存多项式的计算结果inti,j,k;intb[n];//b[i]保存多项式的每一项的带全值for(j=0;j=n;j++)b[j]=1;b[0]=a[0];//x的0次方与x的0次方的系数的乘积b[1]=a[1]*x;//x的1次方与x的1次方的系数的乘积西北大学可视化技术研究所西北大学可视化技术研究所for(j=2;j=n;j++)//从x的2次方开始，到x的n次方结束{for(k=2;k=j;k++){temp=temp*x;//保存x的m次方}b[j]=a[j]*temp;//x的m次方与x的m次方的系数的乘积temp=x;}for(i=0;i=n;i++)sum=sum+b[i];cout多项式的值是：sumendl;}西北大学可视化技术研究所西北大学可视化技术研究所第二章线性表2.1填空题（1）在顺序表中插入或删除一个元素，需要平均移动n/2元素，具体移动的元素个数与插入或删除位置有关。（2）线性表有顺序存储结构和链式存储结构两种存储结构。在顺序表中，线性表的存储空间在数组定义时就已确定，是静态存储分配，在链式表中，整个链表由“头指针”来表示，单链表的存储空间在运行时可以动态变化，是动态存储分配。西北大学可视化技术研究所西北大学可视化技术研究所（3）顺序表中，逻辑上相邻的元素，其物理位置也相邻。在单链表中，逻辑上相邻的元素，其物理位置不一定相邻。（4）在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位置由头结点的next域指示，除首元素结点外，其它任一元素结点的存储位置由其直接前驱的next域指示。西北大学可视化技术研究所西北大学可视化技术研究所2.2选择题（1）在线性表中最常用的操作是存取第i个元素及其前趋的值，可采用A存储方式最省时间？A.顺序表B.带头结点的单向链表C.带头指针的双向循环链表D.带头指针的单向循环链表E.带尾指针的单向循环链表西北大学可视化技术研究所西北大学可视化技术研究所（2）已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。a.在P结点后插入S结点的语句序列是：E.S-next=P-next;A.P-next=S;b.在P结点前插入S结点的语句序列是：H.Q=P;L.P=L;I.while(P-next!=Q)P=P-next;西北大学可视化技术研究所西北大学可视化技术研究所E.S-next=P-next;A.P-next=S;c.在表首插入S结点的语句序列是F.S-next=L;M.L=S;。d.在表尾插入S结点的语句序列是：L.P=L;J.while(P-next!=NULL)P=P-next;A.P-next=S;G.S-next=NULL;。西北大学可视化技术研究所供选择的语句有：A.P-next=S;B.P-next=P-next-next;C.P-next=S-next;E.S-next=P-next;F.S-next=L;G.S-next=NULL;H.Q=P;I.while(P-next!=Q)P=P-next;J.while(P-next!=NULL)P=P-next;K.P=Q;L.P=L;M.L=S;N.L=P;西北大学可视化技术研究所（3）某线性表中最常用的操作是存取序号为i的元素和在最后进行插入和删除运算，则采用D存储方式时间性能最好。A．双向链表B．双向循环链表C．单向循环链表D．顺序表（4）下列选项中，D项是链表不具有的特点。A．插入和删除运算不需要移动元素B．所需要的存储空间与线性表的长度成正比C．不必事先估计存储空间大小D．可以随机访问表中的任意元素西北大学可视化技术研究所(5)在链表中最常用的操作是删除表中最后一个结点和在最后一个结点之后插入元素，则采用C最节省时间。A.头指针的单向循环链表B．双向链表C．带尾指针的单向循环链表D．带头指针双向循环链表(6)在线性表中最常用的操作是存取第i个元素及其前趋的值，可采用A存储方式。A．顺序表B．单向链表C．双向循环链表D．单向循环链表西北大学可视化技术研究所5.写一个算法，从顺序表中删除自第i个元素开始的k个元素。算法描述：以待移动元素下标m为中心，计算应移入位置：for(m=i－1+k;m=L－last;m++)L－elem[m－k]=L－elem[m];西北大学可视化技术研究所8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C。西北大学可视化技术研究所算法描述：要求利用现有的表A和B中的结点空间来建立新表C，可通过更改结点的next域来重新建立新的元素之间的线性关系。为保证新表递减有序可以利用头插法建立单链表的方法，只是新建表中的结点不用malloc，而只需要从A和B中选择合适的点插入到新表C中即可。西北大学可视化技术研究所合并两个有序的单链表算法演示LinkListMergeLinkList(LinkListA,LinkListB)/*将递增有序的单链表A和B合并成一个递减有序的单链表C*/{Node*pa,*pb,*smaller;LinkListC;/*将C初始置为空表，pa和pb分别指向两个单链表A和B中的第一个结点，r初值为C*/pa=A-next;pb=B-next;C=A;C-next=NULL;/*初始化操作*/西北大学可视化技术研究所/*当两个表中均未处理完时，比较选择将较大值结点插入到新表C中。*/while(pa!=NULL&&pb!=NULL){if(pa-data=pb-data){smaller=pa;pa=pa－next;smaller－next=c－next;/*头插法*/c－next=smaller;}else{smaller=pb;pb=pb－next;smaller－next=c－next;c－next=smaller;}if(pa)/*若表A未完，将表A中后续元素链到新表C表*/{smaller=pa;pa=pa－next;smaller－next=c－next;c－next=smaller;}/*否则将表B中后续元素链到新表C表尾*/else{smaller=pb;pb=pb－next;smaller－next=c－next;c－next=smaller;}return(C);}西北大学可视化技术研究所10.已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符，数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。西北大学可视化技术研究所算法描述:只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就可以实现题目的要求。算法提示：设已建立三个带头结点的空循环链表A,B,C.西北大学可视化技术研究所voidDivideList(LinkListL,LinkListA,LinkListB,LinkListC){ListNode*p=L-next,*q;ListNode*a=A,ListNode*b=B;ListNode*c=C;while(p){if(p-data='a'&&p-data='z'||p-data='A'&&p-data='Z'){q=p;//保存字母结点位置p=p-next;//指向下一结点}elseif(p-data='0'&&p-data='9'){//分出数字结点西北大学可视化技术研究所q=p;p=p-next;b-next=q;q-next=B;b=b-next;}else{//分出其他字符结点q=p;p=p-next;c-next=q;q-next=C;c=c-next;}}}//结束西北大学可视化技术研究所第三章限定性线性表-----栈和队列1、按书上图3.1（b）所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：（1）如进站的车厢序列为123，则可能得到的出站车厢序列是什么？答案：123132213231321（2）如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出以“S”表示进站，以“X”表示出站的栈操作序列）。西北大学可视化技术研究所答案：435612不可以原因（1）S：1234X：43（2）S：5X:5（3）S：6X:6（4）X：21135426可以原因（1）S：1X：1（2）S：23X:3（3）S：45X:54（4）X：2（5）S：6X:6西北大学可视化技术研究所3、给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判断栈空和栈满？答案：链