数据结构章课后题答案市公开课一等奖百校联赛获奖课件.pptx

数据结构课后部分习题数据结构课后部分习题答案提醒答案提醒讲课教师：耿国华 教授西北大学可视化技术研究所第1页西北大学可视化技术研究所第一章：绪论n1.2判断题（在各题后填写判断题（在各题后填写“”或或“”）：）：（1）线性结构只能用次序结构来存放，非线性 结构只能用非次序结构来存放。（）（2）算法就是程序。（）（3）在高级语言（如C或 PASCAL）中，指针类型是原子类型。（）西北大学可视化技术研究所第2页西北大学可视化技术研究所n1.3填空题：填空题：（1）变量作用域是指 变量有效范围 （2）抽象数据类型含有 数据抽象 、信息隐蔽 特点。（3）一个抽象类型包含 数据对象 、结构关系 和 基本操作 。西北大学可视化技术研究所第3页西北大学可视化技术研究所 （4）当需要用一个形式参数直接改变对应实参值时，该形式参数应说明为 指针类型 。（5）数据结构逻辑结构分为 集合结构 、线性结构 、树形结构 和 图结构 四种。（6）数据结构存放结构分为 次序存放结构 和 链式存放结构 两种。西北大学可视化技术研究所第4页西北大学可视化技术研究所（7）在线性结构、树形结构和图结构中，数据元素之间分别存在着 一对一 、一对多 和 多对多 联络。（8）算法是规则有限集合，是为处理特定问题而要求 操作序列 。（9）算法含有 有限性 、确定性、可行性 、输入 、输出五大特征。西北大学可视化技术研究所第5页西北大学可视化技术研究所n1.4 1.4 选择题选择题（1）若需要利用形式参数直接访问修改实参值，则应将形参说明为 A 参数。A.指针 B.值参数西北大学可视化技术研究所第6页西北大学可视化技术研究所（2）执行下面程序段时间复杂度为 C 。for(int i=0;im;i+)for(int j=0;jn;j+)aij=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)西北大学可视化技术研究所第7页西北大学可视化技术研究所n(3)执行下面程序段时，语句S执行次数为 C 。for(int i=0;i=n;i+)for(int j=0;j=i;j+)S;A.n2 B.n2/2 C.(n+1)(n+2)/2 D.n(n+1)/2西北大学可视化技术研究所第8页西北大学可视化技术研究所n5.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值。第一步：西北大学可视化技术研究所第9页西北大学可视化技术研究所n第二步:计算结果 第10页西北大学可视化技术研究所n6.6.编写算法，求一元多项式：算法描述：void dxs(int a,int n,int x)int temp=x;/temp保留x幂次方 int sum=0;/sum保留多项式计算结果 int i,j,k;int bn;/bi保留多项式每一项带全值 for(j=0;j=n;j+)bj=1;b0=a0;/x0次方与x0次方系数乘积 b1=a1*x;/x1次方与x1次方系数乘积n 西北大学可视化技术研究所第11页西北大学可视化技术研究所 for(j=2;j=n;j+)/从x2次方开始，到xn次方结束 for(k=2;k=j;k+)temp=temp*x;/保留xm次方 bj=aj*temp;/xm次方与xm次方系数乘积 temp=x;for(i=0;i=n;i+)sum=sum+bi;cout多项式值是：sumnext=P-next;A.P-next=S;b.在P结点前插入S结点语句序列是：H.Q=P;L.P=L;I.while(P-next!=Q)P=P-next;西北大学可视化技术研究所第16页西北大学可视化技术研究所 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;。第17页西北大学可视化技术研究所供选择语句有：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;第18页西北大学可视化技术研究所 （3）某线性表中最惯用操作是存取序号为i元素和在最终进行插入和删除运算，则采取 D 存放方式 时间性能最好。A双向链表 B双向循环链表 C单向循环链表 D次序表 （4）以下选项中，D 项是链表不含有特点。A插入和删除运算不需要移动元素 B所需要存放空间与线性表长度成正比 C无须事先预计存放空间大小 D能够随机访问表中任意元素第19页西北大学可视化技术研究所 (5)在链表中最惯用操作是删除表中最终一个结点和在最终一个结点之后插入元素，则采取 C 最节约时间。A.头指针单向循环链表 B双向链表 C带尾指针单向循环链表 D带头指针双向循环链表 (6)在线性表中最惯用操作是存取第i个元素及其前趋值，可采取 A 存放方式。A次序表 B单向链表 C双向循环链表 D单向循环链表第20页西北大学可视化技术研究所n5.写一个算法，从次序表中删除自第i个元素开始k个元素。算法描述：以待移动元素下标m为中心，计算应移入位置：for(m=i1+k;mlast;m+)Lelem mk =Lelem m;第21页西北大学可视化技术研究所n8.假设两个按元素值递增有序排列线性表A和B，均以单链表作为存放结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列线性表C，并要求利用原表（即A表和B表）结点空间存放表C。第22页西北大学可视化技术研究所n 算法描述：要求利用现有表A和B中结点空间来建立新表C，可经过更改结点next域来重新建立新元素之间线性关系。为确保新表递减有序能够利用头插法建立单链表方法，只是新建表中结点不用malloc，而只需要从A和B中选择适当点插入到新表C中即可。第23页西北大学可视化技术研究所合并两个有序单链表算法演示 LinkList MergeLinkList(LinkList A,LinkList B)/*将递增有序单链表A和B合并成一个递减有序单链表C*/Node*pa,*pb,*smaller;LinkList C;/*将C初始置为空表，pa和pb分别指向两个单链表A和B中第一个结点，r初值为C*/pa=A-next;pb=B-next;C=A;C-next=NULL;/*初始化操作*/第24页西北大学可视化技术研究所/*当两个表中均未处理完时，比较选择将较大值结点插入到新表C中。*/while(pa!=NULL&pb!=NULL)if(pa-datadata)smaller=pa;pa=panext;smallernext=cnext;/*头插法头插法*/cnext=smaller;else smaller=pb;pb=pbnext;smallernext=cnext;cnext=smaller;if(pa)/*若表A未完，将表A中后续元素链到新表C表*/smaller=pa;pa=panext;smallernext=cnext;cnext=smaller;/*不然将表B中后续元素链到新表C表尾*/else smaller=pb;pb=pbnext;smallernext=cnext;cnext=smaller;return(C);第25页西北大学可视化技术研究所n10.已知有单链表表示线性表中含有三类字符数据元素（如字母字符，数字字符和其它字符），试编写算法来结构三个以循环链表表示线性表，使每个表中只含同一类字符，且利用原表中结点空间作为这三个表结点空间，头结点可另辟空间。第26页西北大学可视化技术研究所n 算法描述:只要新建三个头结点，然后在原来单链表中依次查询，找到一类字符结点时，就摘下此结点链接到对应头结点指明新链表中就能够实现题目标要求。n 算法提醒：设已建立三个带头结点空循环链表 A,B,C.第27页西北大学可视化技术研究所nvoid DivideList(LinkList L,LinkList A,LinkList B,LinkList C)ListNode*p=L-next,*q;ListNode*a=A,ListNode *b=B;ListNode *c=C;while(p)if(p-data=a&p-datadata=A&p-datanext;/指向下一结点 else if(p-data=0&p-datanext;b-next=q;q-next=B;b=b-next;else /分出其它字符结点 q=p;p=p-next;c-next=q;q-next=C;c=c-next;/结束第29页西北大学可视化技术研究所第三章 限定性线性表-栈和队列n1、按书上图3.1（b）所表示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：（1）如进站车厢序列为123，则可能得到出站车厢序列是什么？答案：123 132 213 231 321（2）如进站车厢序列为123456，能否得到435612和135426出站序列，并说明原因。（即写出以“S”表示进站，以“X”表示出站栈操作序列）。第30页西北大学可视化技术研究所n答案：435612不能够 原因 （1）S：1234 X：43 （2）S：5 X:5 （3）S：6 X:6 （4）X：21 135426 能够 原因（1）S：1 X：1 （2）S：23 X:3 （3）S：45 X:54 （4）X：2 （5）S：6 X:6 第31页西北大学可视化技术研究所n3、给出栈两种存放结构形式名称，在这两种栈存放结构中怎样判断栈空和栈满？答案：链栈和次序栈 链栈：栈空：头指针为空：即if（head-next=NULL）栈满：结点存放空间申请失败 次序栈：栈空：栈下标小于零：即 if（stack-toptopMAX）第32页西北大学可视化技术研究所n4、按照四则运算加、减、乘、除和幂（）运算优先关系通例，画出对以下算术表示式求值时运算数栈和运算符栈改变过程：A-B*C/D+E F 答案：第33页西北大学可视化技术研究所n ABC-*/=optr(*)T(1)=B*C+=optr(/)T(2)=T(1)/DA-DT(1)/AT(2)-T(3)FE+=optr(-)T(3)=A-T(2)+右边界右边界#=optr()T(4)=EFT(3)T(4)+右边界右边界#rear%MAXSIZE=q-front&tag=1)/*队列已满 return(FALSE);q-elementq-rear=x;/*装元素*/q-rear=(q-rear+1)%MAXSIZE;if(q-rear%MAXSIZE=q-front)/*判断并设置 标志位tag*/tag=1;return(true);第36页西北大学可视化技术研究所出队操作：Int deletequeue(seqqueue*q,element*x)if(q-front=q-rear&tag=0)return(FALSE);*x=q-elementq-front;q-front=(q-front+1)%MAXSIZE;if(q-front=q-rear)tag=0;/*设标志tag*/return（true）；第37页西北大学可视化技术研究所9、设4个元素1、2、3、4依次进栈，而出栈操作可随时进行（进出栈可任意交织进行，但要确保进栈不破环1、2、3、4相对次序，）请写出全部不可能和可能出栈次序。全部可能：1234 1243 1324 1432 2134 2143 2314 2341 2431 3214 3241 3421 4321 全部不可能：1342 1423 2413 3124 3142 3412 4312 4213 4231 4123 4132 第38页西北大学可视化技术研究所n12、简述以下算法功效（其中栈和队列元素类型均为int）(1)Void pro_1(stack s)int I,n,a255;n=0;while(!EmptyStack(s)n+;Pop(&s,&an);for(i=1;i=n;i+)Push(&s,ai);功效：将栈S中数据逆置第39页西北大学可视化技术研究所（2）void pro_2(Stack s,int e)Stack T;int d;initStack(&T);while(!EmptyStack(s)Pop(&s,&d);if(d!=e)Push(&T,d);While(!EmptyStack(T)Pop(&T,&d);Push(&s,d);功效：在栈中找到元素e，并利用其它栈，让e后元素依次前移 第40页西北大学可视化技术研究所nvoid proc_3(queue*q)Stack S;int d;InitStack(&s);While(!EmptyQueue(*q)Deletequeue(q,&d);Push(&s,d);While(!EmptyStack(s)Pop(&s,&d);EnterQueue(q,d);功效：利用栈将队列逆置第41页