数据结构校本教程课后习题.docxVIP

1.4 总结与提高1.4.1 主要知识点（1）数据类型、数据结构等基本概念。（2）几种基本数据结构的逻辑结构及常用的几种存储结构。（3）算法的概念、算法的表示、算法的时间性能和空间性能评价方法。练习题目一、选择题1.从逻辑上可以把数据结构分为（ ）两大类。 A. 线性结构、非线性结构 B .初等结构、构造型结构 C. 顺结构、链式结构 D.动态结构、静态结构2.采用顺序存储结构表示数据时，相邻的数据元素的存储地址（ ）。A. 一定不连续 B . 一定连续 C. 不一定连续 D. 部分连续，部分不连续3.在发生非法操作时，算法能够做出适当处理的特性称为（ ）。A. 健壮性 B . 可读性 C. 正确性 D. 可移植性4.执行下面程序段的时间复杂度为（ ）。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的执行次数为（ ）。For(int i=0i=n;i++) For(int j=0;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．可随机访问任一结点 B． 插入删除不需要移动元素C．不必事先估计存储空间 D．所需空间与其长度成正比2．带头结点的单链表head为空的判定条件是（ ）A．head= =NULL B．head-next= =NULLC．head-next= =head D．head!=NULL3．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（ ）存储方式最节省运算时间。A．单链表 B．给出表头指针的单循环链表C．双链表 D．带头结点的双循环链表4．需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（ ）A．单链表 B ．静态链表 C．线性链表 D．顺序存储结构5．与单链表相比，双链表的优点之一是（ ）A．插入、删除操作更简单 B． 可以进行随机访问C．可以省略表头指针或表尾指针 D．顺序访问相邻结点更灵活6．在一个单链表中的p所指结点之前插入结点s，可执行如下的操作：s-next= ① ;p-next=s;t=p-data;p-data= ② ;s-data= ③ ;练习题目1.下面是将不带头结点的链表L逆置的程序，请将程序补充完整：void invert(Node *L){Node *p,*q,*r;p=L;q=p-next;while(q!=NULL) { p=q; q=r;}L-next=NULL;L=p; }2.线性表中有n个元素，以下算法中，（ ）在顺序表上实现比在链表上实现效率更高。A．输出第i(0≤i≤n-1)个元素 B．交换第0个元素与第1个元素的值C．顺序输出这n个元素的值 D．输出与给定值x相等的元素在线性表中的序号3.单链表中，增加一个头结点的目的是为了( )。 A．使单链表至少有一个结点 B．标识表结点中首结点的位置 C．方便运算的实现 D．说明单链表是线性表的链式存储4.在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行（ ）。A．q-next = p-next ; p-next = q;B．p-next = q-next; q = p;C．q-next = p-next; p-next = q;D．p-next = q-next ; q-next = p;5.不带头结点的单链表head为空的判定条件是（ ）A．head= =NULL B．head-next= =N