(数据结构基本概念.docVIP

第一章：数据结构 数据结构基本概念：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 数据结构涉及逻辑结构，物理结构，结构的运算三个问题 数据结构的存储结构主要有 顺序存储，链式存储，索引存储，散列存储 1.10 对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度 T(n)。 （1） i++; -----------0 （2） for(i=0;in;i++) ------------0（n） if (a[i]x) x=a[i]; （3）for(i=0;in;i++) ------------0（n2） for(j=0;jn;j++) printf(“%d”,i+j); （4）for (i=1;i=n-1;i++) ------------0（n） { k=i; for(j=i+1;j=n;j++) if(a[j]a[j+1]) k=j; t=a[k]; a[k]=a[i]; a[i]=t; } （5）for(i=0;in;i++) ------------0（n2） for(j=0;jn;j++) {++x;s=s+x;} 第二章：线性表 线性表基本概念：线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：k1,k2,…,kn，其中k1是开始结点，kn是终端结点。 两种方式：顺序存储，链式存储 栈：是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。 　　栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表。 栈可以用来在函数调用的时候存储断点，做递归时要用到栈！ 队列：队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。 　　在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。 队列空的条件：front=rear 队列满的条件： rear = MAXSIZE （1）表长为 n 的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时， 插入一个元素所需移动元素的平均个数为（ E ），删除一个元素所需移动元素的平均个数 为（ A ）。 A． ? 1）/2（nB．nC．n + 1D．n ? 1 E．n/2F．(n + 1)/2G．(n ? 2)/2 （2）设栈 S 和队列 Q 的初始状态为空，元素 e1、e2、e3、e4、e5 和 e6 依次通过栈 S， 一个元素出栈后即进入队列 Q，若 6 个元素出队的序列为 e2、e4、e3、e6、e5 和 e1，则栈 S 的容量至少应该为（ C ）。 A．6B．4C．3D．2 （3）设栈的输入序列为 1、2、3 … n，若输出序列的第一个元素为 n，则第 i 个输出的元素为 （B）。 A．不确定B．n ? i + 1C．iD．n ? i （4）在一个长度为 n 的顺序表中删除第 i 个元素（1 = i = n）时，需向前移动（ A ）个 元素。 A．n?iB．n ? i +1C．n ? i ? 1D．i （5）若长度