数据结构复习知识点教程.doc

第一章：概论 知识点： 数据结构的基本概念：数据、数据元素、数据项等之间的区和联系。 数据的逻辑结构，数据的存储结构、数据的逻辑结构和存储结构各有哪些基本类型、数据的基本逻辑结构有什么特点。 我们所学的几种常见的数据结构中（顺序表、链表、队列、栈、串、树、图等），哪些是线性数据结构，哪些是非线性数据结构？ 算法复杂性的概念、内容和算法复杂性的计算。 简单算法复杂性的判断： (1)sum=0; for(i=1;i=n;i++) sum=sum+i; 其中i=1,2,3,…,k, 需频度k=n，所以复杂性为O(n) (2)i=1; while(i=n) i=i+2; 其中i=1,3,5,…,(2k-1),需2k-1=n，则频度k=(n+1)/2，复杂性为O(n) (3)i=1; while(i=n) i=i*3; 其中i=1,3,32,…,3k, 需3k=n，则频度k=log3n，复杂性为O(log3n) (4)i=1; while(i*i=n) i++; 其中i=1,2,3,…,k，需k2=n，则频度k=n1/2，复杂性为O(n1/2) 习题： 1、填空题 （1）数据的逻辑结构包括： 、 、 、 ； （2）存储结构包括： 、 、 、 。 （3）数据结构中评价算法的两个重要指标是 （4）下面程序段中带下划线的语句的执行次数的数量级是： i=1；while( in) i=i*2; （5）计算机执行下面的语句时，语句s的执行次数为 _______ 。 for(i=l；in-l；i++) for(j=n;j=i;j--) s; （6）下面程序段的时间复杂度为________。(n1) sum=1； for (i=0;sumn;i++) sum+=1; 2、选择题 （1）算法的计算量的大小称为计算的（ ）。 A．效率 B. 复杂性 C. 现实性 D. 难度 （2）算法的时间复杂度取决于（ ） A．问题的规模 B. 待处理数据的初态 C. A和B （3）计算机算法指的是（ ），它必须具备（ ） 这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 （4）从逻辑上可以把数据结构分为（ ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 （5）以下数据结构中，哪一个是线性结构（ ）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 （6）在下面的程序段中，对x的赋值语句的频度为（ ） for(i=1;i=n;i++) for(j=1;j=n;j++) x=x+1 A． O(2n) B．O(n) C．O(n2) D．O(log2n) （7）程序段 for(i=n;i=1;i--) for(j=1;j=n;j++) IF A[j]A[j+1] THEN A[j]与A[j+1]对换； 其中 n为正整数，则最后一行的语句频度在最坏情况下是（ ） A. O（n） B. O(nlogn) C. O(n3) D. O(n2) （8）以下数据结构中，（ ）是非线性数据结构 A．树 B．字符串 C．队 D．栈 （9）连续存储设计时，存储单元的地址（ ）。 A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 3、问答题 （1）数据元素之间的关系在计算机中有几种表示方法？各有什么特点？ （2）数据的逻辑结构有哪些基本类型？ （3）数据的存储结构由哪四种基本的存储方法实现？ 第二章：线性表 知识点： 线性表的基本概念和两种存储方式：顺序存储、链式存储 顺序表的概念、数据结构、存储，插入、删除运算及其时间复杂度；顺序表的特点：随机存储 单链表的存储、插入、删除运算特点？是否可以随机存取？访问、增加或者删除结点时的时间复杂度？ 单链表中插入结点和删除结点的基本步骤？头指针与头结点之间的根本区别，头结点与首元结点的关系？在链表里面，引入头