数据结构校本教材各章习题及答案.docx

第一章 绪论1.4 总结与提高1.4.1 主要知识点（1）数据类型、数据结构等基本概念。（2）几种基本数据结构的逻辑结构及常用的几种存储结构。（3）算法的概念、算法的表示、算法的时间性能和空间性能评价方法。练习题目一、选择题1.从逻辑上可以把数据结构分为（ A ）两大类。 A. 线性结构、非线性结构 B .初等结构、构造型结构 C. 顺结构、链式结构 D.动态结构、静态结构2.采用顺序存储结构表示数据时，相邻的数据元素的存储地址（B ）。A. 一定不连续 B . 一定连续 C. 不一定连续 D. 部分连续，部分不连续3.在发生非法操作时，算法能够做出适当处理的特性称为（ A ）。A. 健壮性 B . 可读性 C. 正确性 D. 可移植性4.执行下面程序段的时间复杂度为（ C ）。For(int i=0;im;i++) For(int j=0;jn;j++)A[i][j]=i*j;A. O(m2) B . O(n2) C. O(m*n) D. O(m+n)5.执行下面程序段时，语句S的执行次数为（ D ）。For(int i=0i=n;i++) For(int j=1;j=i;j++) S;A. n2 B . n2/2 C. n(n+1) D. n(n+1)/2二、判断题1.算法就是程序。（ × ）2.算法必须有输入，但可以没有输出。（ × ）3.线性结构只能用顺序结构存储，非线性结构只能用非顺序结构存储。（ × ）4.顺序存储结构的特点是对于插入和删除操作的效率非常高。（ × ）5.算法的优劣与所用计算机的性能有关，与描述算法的语言无关。（ × ）三、简答题1.简述数据结构的含义。2.简述算法的时间复杂度。3.简述数据类型的概念。4.简述算法和程序的区别5.常见的逻辑结构有哪些？存储结构有哪些？各自的特点是什么？实验题目1．试着写一算法，自大至小依次输出读入的三个整数X,Y和Z的值。第二章 线性表2.5 总结与提高2.5.1 主要知识点1、顺序表和链表存储结构的描述方法；2、顺序表的查找、插入和删除算法；3、各种链表的查找、插入和删除算法。2.5.2 典型例题1、链表不具备的特点是（ A）A）可随机访问任一结点 B）插入删除不需要移动元素C）不必事先估计存储空间 D）所需空间与其长度成正比顺序表可随机访问任一结点，而链表必须从第1个数据结点出发逐一查找每个结点，答案为A。2、带头结点的单链表head为空的判定条件是（ B）A）head= =NULL B）head-next= =NULLC）head-next= =head D）head!=NULL在带头结点的单链表head中，head指向头结点，由头结点的next域指向第1个元素结点，head-next= =NULL表示该单链表为空，答案为B。3、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（ D ）存储方式最节省运算时间。A）单链表 B）给出表头指针的单循环链表C）双链表 D）带头结点的双循环链表在链表中插入或删除一个结点，需修改相邻结点的指针域。若不特别指明，则通常只给出链表第i个结点的地址，即头指针。其他结点的地址只能从它的前驱或后续结点得到。上述4种答案只有D能从头指针，经过最少的结点，获得最后一个结点的相邻结点的地址，答案为D。4、需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（ B ）A）单链表 B）静态链表 C）线性链表 D）顺序存储结构由于插入和删除不需要移动元素，所以不能是顺序表，只能是链表，但需要事先分配较大空间，所以为静态链表，答案为B。5、与单链表相比，双链表的优点之一是（ D ）A）插入、删除操作更简单 B）可以进行随机访问C）可以省略表头指针或表尾指针 D）顺序访问相邻结点更灵活在双链表中可以访问任一结点的相邻结点，而单链表中只能访问任一结点的下一个结点，答案为D。6、在一个单链表中的p所指结点之前插入结点s，可执行如下的操作：s-next= ① ;p-next=s;t=p-data;p-data= ② ;s-data= ③ ;采用的方法是在*p之后插入一个结点*s，然后将*p和*s结点的数据域进行交换。答案为①p-next ②s-data ③t练习题目1、下面是将不带头结点的链表L逆置的程序，请将程序补充完整：void invert(Node *L){Node *p,*q,*r;p=L;q=p-next;while(q!=NULL) { r=q-next; q-next=p; p=q; q=r;}L-next=NULL;L=p; }2、设线性表中有n个元素，以