第一章：概论 知识点：
1、 数据结构的基本概念：数据、数据元素、数据项等之间的区和联系。
2、 数据的逻辑结构，数据的存储结构、数据的逻辑结构和存储结构各有哪些基本类型、数据的基本逻辑结构有什么特点。
我们所学的几种常见的数据结构中（顺序表、链表、队列、栈、串、树、图等），哪些是线性数据结构，哪些是非线性数据结构？ 3、 算法复杂性的概念、内容和算法复杂性的计算。 简单算法复杂性的判断： (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( i （5）计算机执行下面的语句时，语句s的执行次数为 _______ 。 for(i=l；i （6）下面程序段的时间复杂度为________。(n>1) sum=1； for (i=0;sum （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为正整数，则最后一行的语句频度在最坏情况下是（ ） 32 A. O（n） B. O(nlogn) C. O(n) D. O(n) （8）以下数据结构中，（ ）是非线性数据结构 A．树 B．字符串 C．队 D．栈 （9）连续存储设计时，存储单元的地址（ ）。 A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 3、问答题 （1）数据元素之间的关系在计算机中有几种表示方法？各有什么特点？ （2）数据的逻辑结构有哪些基本类型？ （3）数据的存储结构由哪四种基本的存储方法实现？ 第二章：线性表 知识点： 1、 线性表的基本概念和两种存储方式：顺序存储、链式存储 2、 顺序表的概念、数据结构、存储，插入、删除运算及其时间复杂度；顺序表的特点：随机存储 3、 单链表的存储、插入、删除运算特点？是否可以随机存取？访问、增加或者删除结点时的时间复杂度？ 4、 单链表中插入结点和删除结点的基本步骤？头指针与头结点之间的根本区别，头结点与首元结点的关系？在链表里面，引入头结点有什么作用？ 5、 有头结点、无头结点的单链表为空的条件分别是什么？ 有头结点：L->next == NULL，无头结点：L==NULL 习题： 1、选择题 （1）下述哪一条是顺序存储结构的优点？（ ） A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 （2）下面关于线性表的叙述中，错误的是哪一个？（ ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 （3）线性表是具有n个（ ）的有限序列（n>0）。 A3．表元素 B．字符 C．数据元素 D．数据项 E．信息项 （4）链表不具有的特点是（ ） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 （5） 下面的叙述不正确的是（ ） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 （6）若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。 2 A. O(0) B. O(1) C. O(n) D. O(n) （7）对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) （8）线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ） A．O（i） B．O（1） C．O（n） D．O（i-1） 2、填空 （1）当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用__ _____存储结构。 （2）线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是__ ______。 （3）在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动__ 1______个元素。 （4）在单链表中设置头结点的作用是_ ______。 （5）链接存储的特点是利用_______来表示数据元素之间的逻辑关系。 （6）顺序存储结构是通过_ ______表示元素之间的关系的;链式存储结构是通过______表示元素之间的关系的。 （7） 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 _____个，单链表为______个。 （8）在单链表L中，指针p所指结点有后继结点的条件是：__ （9）线性结构包括______、______、_____和______。线性表的存储结构分成_ ____和____ __。 3、应用题 （1）线性表有两种存储结构：一是顺序表，二是链表。试问： 如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？ 若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？ （2）说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。 （3）删除顺序表中所有的正数，要求移动次数小。 搜索顺序表，对每一个正数，先不删除，而是累计当前正数个数s，于 是，对每个非正数，将它一次性前移s位。算法复杂性为O（n）。 void dels(sqlist *L) { int s,i; s=0; //正数计数器 for(i=0;i if(L->data[i]>0 s++; //累计当前正数 else if(s>0) L->data[i-s]=l->data[i];//向前移动s位 L->n=L->n-s; //调整表长 } 还可以删除顺序表中所有的负数、字符等，主要是删除数据的条件不一样 （4） 单链表算法运用，如链表合并，将两个有序表合并为一个有序表 lklist purge(lklist A,lklist B) { pointer C,p,q,r; p=A->next;q=B->next; C=A;r=C; //取A头结点作C头结点 while(p!=NULL && q!=NULL) { if(p->data<=q->data) {r?>next=p;r=p;p=p->next;} else {r?>next=q;r=q;q=q->next;} } if(p!=NULL) r->next=p; //A表有剩余结点 else r->next=q; delete B; //释放B头结点 return C; } 第三章 栈、队列和串 知识点： 1、 栈的定义、栈顶、栈底、运算特点（先进后出），顺序实现和链接实现及其特点，栈的应用 2、 队列的概念，队头、队尾、运算特点（后进后出），顺序实现、循环队列、链队列 3、 串的概念和串长的计算 习题 1、 选择题 （1） 对于栈操作数据的原则是（ ）。
相关推荐：
loading