数据结构1-3习题答案

回顾第一章知识要点：基本概论：数据、数据元素、数据项、数据对象数据结构(D,S)

逻辑结构：线性结构、树形结构、图形结构、集合结构

存储结构：顺序存储、链式存储、索引存储、散列存储

运算：初始化、查找、插入、删除、遍历等抽象数据类型（D,S,P）回顾第二章知识要点：算法定义及特性算法效率分析

时间复杂度：用语句频度总和的数量级描述空间复杂度：用占有存储空间的数量级描述回顾第三章知识要点：C语言重点内容：

参数传递、结构类型、指针递归直接递归、间接递归存储分配方式

静态分配（全局静态变量区）、动态分配（堆区）、自动分配（栈区）总结重点：了解数据、数据元素、数据对象、数据结构、数据结构的逻辑结构、数据的存储结构及抽象数据类型概念，熟悉C语言中指针、结构体，学会分析时间复杂度。

1-3章习题1.1-1.3见教材1.4试述数据的逻辑结构与存储结构之间的区别与联系。答：数据结构包括数据逻辑结构和数据物理结构两个层次，两者是密切相关、相辅相成的。数据的逻辑结构是对数据元素之间存在的逻辑关系的一种抽象描述；数据的物理结构则为其逻辑结构在计算机中的存储表示或实现。一种逻辑结构可映射成不同的存储结构，不同的存储实现方法其算法不同，实现的效率也不同。1.6什么是抽象数据类型？它有什么作用？答：抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。抽象数据类型是用户定义的数据类型，使得其使用和实现分类，提高软件的复用率。2.1试述算法和程序的区别。答：算法是指解决问题的一种方法或一个过程，即由若干条指令组成的有穷序列。程序是算法用某种程序设计语言的具体实现。算法中指令的执行必须是有穷性的，而程序可以不满足此要求。2.4判断下述计算过程是否是一个算法：Step1:开始Step2:n<=0;Step3:n=n+1;Step4:重复步骤3;Step5:结束;答：该计算过程不是一个算法，因为其不满足算法的有穷性。2.6分析下列程序段的时间复杂度：(1)voidmain(){inti=1,j=0,n;scanf(“%d”,&n);while(i+j<=n){if(i>j)i=i+1;elsej=j+1;}}T(n)=O(n)(2)Intrec(intn){if(n<=1)return1;elsereturnrec(n-1)*rec(n-1);}T(n)=O(2n)2.8在下面两列中，左侧是算法（关于问题规模）的执行时间，右侧是一些时间复杂度。请用连线的方式表示每个算法的时间复杂度。100n36n2-12n+11024n+2log2nn(n+1)(n+2)/62n+1+100nT(n)=O(n3)T(n)=O(n2)T(n)=O(1)T(n)=O(n)T(n)=O(n3)T(n)=O(2n)3.1试述你所理解的函数参数的“值传递”和“地址传递”。答：“值传递”即在函数参数传递时将实参赋给形参，而在函数体中对形参修改后不影响实参原来值；“地址传递”即在函数参数传递时传递的是实参的地址，在函数体中可通过地址直接对实参进行操作。3.3什么是指针？什么是指针的指针？它们之间有本质上的区别吗？答：一个变量的地址称为该变量的指针。指针的指针即指向指针的指针，它们的区别是：指针存放的是某一数据的存放地址，而指针的指针存放的是指针的存放地址，用的是一种“二级间址”方法。3.4试述你所理解的“递归”。答：递归即一种在函数/过程/子程序在运行过程序中直接或间接调用自身的编程方式。3.5简述动态存储分配和静态存储分配之间的区别。答：静态存储分配是指在程序运行前由编译器在编译时分配固定的存储空间，直到整个程序运行结束才释放存储空间，如全局变量存储空间分配；而动态存储分配则是在程序运行过程中根据需要进行动态的分配和释放存储空间。3.2试编写程序完成：有15个学生，每个学生的信息包括学号、姓名、性别、年龄、班级和3门课程成绩，从键盘输入15个学生的信息，要求打印出3门课程的总平均成绩，以及最高分的学生的信息（包括学号、姓名、性别、年龄、班级、3门课程成绩、平均分）。#include<iostream.h>typedefstruct{ intno; charname[8]; charsex[2]; intage; charcls[14]; intmath; intenglish; intchinese;}student;voidmain(){ studentst[15]; inti,j1=1,j2=1,j3=1,avg1=0,avg2=0,avg3=0,max1=0,max2=0,max3=0; for(i=0;i<154;i++) { cout<<endl<<"请依次输入第"<<i+1<<"位同学的学号、姓名、性别、年龄、班级、数学成绩、英语成绩、语文成绩："; cin>>st[i].no>>st[i].name>>st[i].sex>>st[i].age>>st[i].cls>>st[i].math>>st[i].english>>st[i].chinese;} for(i=0;i<15;i++) { avg1+=st[i].math;avg2+=st[i].english;avg3+=st[i].chinese; if(st[i].math>max1){max1=st[i].math;j1=i;} if(st[i].english>max2){max2=st[i].math;j2=i;} if(st[i].chinese>max3){max3=st[i].math;j3=i;} }

avg1=avg1/15;avg2=avg2/15;avg3=avg3/15; cout<<endl<<"数学课的平均成绩为："<<avg1; cout<<endl<<"该课程最高分同学信息为："<<st[j1].no<<""<<st[j1].name<<""<<st[j1].sex<<""<<st[j1].age<<""<<st[j1].cls<<""<<st[j1].math<<""<<st[j1].english<<""<<st[j1].chinese; cout<<endl<<"英语课的平均成绩为："<<avg2; cout<<endl<<"该课程最高分同学信息为："<<st[j2].no<<""<<st[j2].name<<""<<st[j2].sex<<""<<st[j2].age<<""<<st[j2].cls<<""<<st[j2].math<<""<<st[j2].english<<""<<st[j2].chinese; cout<<endl<<"语文课的平均成绩为："<<avg3; cout<<endl<<"该课程最高分同学信息为："<<st[j3].no<<""<<st[j3].name<<""<<st[j3].sex<<""<<st[j3].age<<""<<st[j3].cls<<""<<st[j3].math<<""<<st[j3].english<<""<<st[j3].chinese;}顺序存储：初始化、插入、删除、查找运算链式存储：初始化、插入、删除、查找运算单链表

静态链表

双向链表

循环链表线性表存储方式特点：能随机存取，但插入、删除数据元素移动量大特点：插入、删除无需移动数据元素，但不能随机存取，浪费存储空间第四章知识回顾重点：熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析难点：能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。课堂练习1、在什么情况下用顺序表比链表好?2、画出执行下列各行语句后各指针及链表的示意图。L=(LinkList)malloc(sizeof(LNode));//等价于L=newLNode;P=L;For(i=1;i<=4;i++){P->next=(LinkList)malloc(sizeof(LNode));P=P->next;P->data=i*2-1;}P->next=NULL;For(i=4;i>=1;i--)Ins_LinkList(L,i+1,i*2);For(i=1;i<=3;i++)Del_LinkList(L,i);湖北工业大学理学院173、已知L是带头结点的非空单链表的头指针，且P结点既不是首元结点，也不是尾元结点，试从提供的答案1-14中选择适当的语句系列填空。(1)删除p结点的直接后继结点的语句序列是()(2)删除p结点的直接前趋结点的语句序列是()(3)删除p结点的语句序列是()(4)删除首元结点的语句序列是()(5)删除尾元结点的语句序列是()第一章绪论一、选择题（下列各小题均有一个答案是正确的）A、问题的规模B、待处理数据的初态1、算法的时间复杂度取决于C、问题的规模和处理数据的初态（）A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构2、数据结构中，从逻辑上可以把数据结构分成（）A、找出数据结构的合理性B、分析算法的效率和时间复杂度C、研究算法的输入和输出的关系D、分析算法的易懂性和文档性3、算法分析的目的是（）A、T1（n）=nlog2n+1000log2nB、T2（n）=nlog23-1000log2nC、T3（n）=n2-1000log2nD、T4（n）=2nlog2n-1000log2n4、下列函数中渐近时间复杂度最小的是（）A、计算方法B、排序方法C、计算方法和排序方法D、解决问题的有限序列5、计算机算法是指（）CCBBD二、填空题（请用正确答案填充下列空白）1、数据的逻辑结构包括＿＿＿＿＿、＿＿＿＿＿和＿＿＿＿＿三种；2、从利用计算机资源角度看，评价算法的性能主要是从＿和＿＿＿方面进行分析和研究的；

3、数据类型是一个＿＿＿和定义在这个＿上的一组操作；

4、算法的五个特性是＿、可行性、输入和输出；5、数据结构是一门研究＿＿计算的程序设计问题中计算机的＿＿以及它们之间＿＿＿和运算等学科；

6、下面程序段的时间复杂度分别是＿＿＿＿＿。for(i=0;i<n;i++)i=1;for(j=0;j<m;j++)while(i<=n)A[i][j]=0;i=i*3;

线性结构、树形结构、图形结构和集合结构问题规模输入数据集合集合确定行、＿有穷性非数值操作的对象关系O(n2)、＿O(log3n)第二章线性表一、选择题（下列各小题均有一个答案是正确的）A、P==NullB、P->next==Null1、不带头结点的单链表P为空的判断条件是C、P->next=PD、P!=Null（）A、P->next=NullB、P==NullC、P->next=HeadD、P==Head2、非空循环单链表Head的尾结点（由P指向）满足（）A、n个结点B、n/2个结点C、(n-1)/2个结点D、(n+1)/2个结点3、在n个结点的单链表中查找等于X的结点，需平均比较（）A、P->next=p->next->nextB、P=P->next;P->next=p->next->nextC、P->next=P->nextD、P=P->next->next4、一个单链表中若删除P所指的后继结点，则执行（）A、S->next=P->next;P-next=S;B、P->next=S->next;S->next=PC、Q->next=S;S->next=PD、P->next=S;S->next=Q5、某单链表中Q是P的前趋，若Q和P之间插入结点S则（）ACDACA、必须是连续的B、部分地址必须是连续的6、线性表采用链式存储，要求所用的存储地址C、一定不是连续的D、连续与否都可以（）A、数据项B、数据对象C、数据元素D、表元素7、线性表是具有N个（）的有限序列（）A、O(1)B、O(n)C、O(n*n)D、O(log2n)8、在一有n个结点的有序单链表中插入一结点的时间复杂度（）A、数据项B、数据对象C、数据元素D、数据信息9、数据的最小单位是（）A、P->prior=P->next=P;B、P->prior=P;P->next=Null;C、P->prior=P->next=Null;D、P->prior=Null;P->next=P;10、双向循环链表P判断为空的条件是（）DCBAA二、填空题（请用正确答案填充下列空白）1、顺序表中插入或删除一个元素，需要平均移动＿＿＿元素，具体移动元素的个数与＿＿＿＿有关；

2、单链表中设置头结点的作用是＿＿＿＿；

3、在非空双向循环链表中的结点Q前插入结点P的过程如下，补充完整

P->prior=Q->prior;____P->next=Q;________________4、在单链表中首元结点外任一结点的存储位置是由＿＿指示的；5、链式存储结构既可以通过＿＿来实现也可以通过＿＿＿＿来实现；6、在双向链表中，每个结点都有两个指针域，其中一个指向＿＿＿另一个指向＿＿＿＿＿；6、程序段：i