数据结构期末复习提纲（2012级）
A、总体要求：
1、掌握数据结构的基本概念、基本原理和基本方法。
2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度和空间复杂度的分析。
3、能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C语言和C++语言设计与实现算法的能力。
一、基本概念
1、数据结构、数据元素、数据项、数据类型、抽象数据类型、算法、算法的时间复杂度、算法的空间复杂度、算法的评价标准。
2、数据结构的逻辑结构和存储结构及分类。
3、线性表的定义及特点。
4、顺序表、单链表、双向链表、循环链表的存储结构。
5、栈和队列的定义及特点。
6、顺序栈、链栈、顺序队列、链队列的存储结构。
7、字符串的定义及特点。
8、顺序串和链串的存储结构。
9、数组的定义及特点。
10、数组的按行存储与按列存储。
11、对称矩阵、三角矩阵的压缩存储。
12、二叉树的定义、一般术语及特点。
13、二叉树的五个基本性质。
14、完全二叉树与满二叉树的概念。
15、二叉树的顺序存储结构。
16、二叉树的二叉链表与三叉链表存储结构。
17、二叉树的四种遍历方式及特点。
18、线索二叉树的存储结构及特点。
19、树和森林的概念。
20、树的双亲链表和孩子兄弟链表存储结构。
21、树和森林的二种遍历方式。
22、图的定义、一般术语及特点。
23、图的邻接矩阵、邻接表、逆邻接表存储结构。
24、图的二种遍历方式及特点、优先遍历生成树的概念。
25、图的连通性、连通图、连通分量的概念。
26、有向无环图的概念及特点。
27、查找、查找表、关键字的概念。
28、顺序查找、折半查找的概念。
29、二叉排序树和平衡二叉树的定义及特点，平衡因子的概念。
30、B_树的定义及存储结构特点。
31、哈希函数、哈希表、哈希冲突、哈希查找的概念。
32、哈希表装填因子的定义及作用。
33、内部排序、外部排序、排序方法、排序方法的稳定性概念。
34、希尔排序、快速排序、堆排序、归并排序、基数排序的概念。
二、数据结构的基本操作算法
1、顺序表与单链表的创建、查找、插入、删除、遍历操作算法。
2、顺序栈的创建、初始化、取栈顶元素、出栈、入栈操作算法。
3、顺序队列和循环队列的创建、初始化、取队头元素、出队、入队操作算法。
4、二叉树的先序、中序、后序遍历的递归算法。
5、中序线索二叉树的创建和遍历操作算法。
6、树和森林的孩子兄弟链表结构的先序和后序遍历操作算法。
7、图的邻接矩阵和邻接表结构的创建操作算法。
8、图的深度优先和广度优先遍历算法。
9、有序顺序表的折半查找算法。
10、二叉排序树的创建、查找、插入、删除算法。
11、传统的插入、选择、交换排序算法。
12、一趟快速排序、归并排序的算法。
三、基本方法
1、简单程序的算法时间复杂度和空间复杂度的分析。
2、比较顺序表与链表、单链表、双向链表、循环链表的应用特点。
3、顺序栈的简单应用。
4、循环队列和双端队列的特点及简单应用。
5、二维、三维数组的按行、按列展开的地址计算及转换。
6、二叉树基本性质的应用及简单计算。
7、已知二叉树的遍历，求二叉树的形态。
8、已知二叉树，画出线索二叉树。
9、森林与二叉树的转换方法。
10、哈夫曼树的构造和编码方法。
11、图的邻接矩阵和邻接表结构及逆邻接表结构的转换方法。
12、连通分量、强连通分量的求解方法。
13、深度优先和广度优先遍历最小生成树的求解方法。
14、最小生成树的求解方法。
15、应用栈或队列的拓扑排序的求解方法。
16、关键路径的求解方法。
17、平衡二叉树的构造方法、平衡因子的计算。
18、线性探测再散列和链地址法解决冲突的哈希表构造方法，并计算平均查找长度。
19、B_树的构造和查找方法。
20、希尔排序、快速排序、堆排序、归并排序、基数排序的方法。
21、排序方法的时间性能、空间性能及稳定性的比较。
四、算法应用设计
1、有序顺序表应用，如：合并、查找、排序、消除重复元素等。
2、链表应用，如：链表的合并、排序、查找、删除等。
3、二叉链表二叉树的遍历应用，如：查找、求高度和宽度等。
4、三叉链表的二叉树的非递归遍历算法。
5、图的邻接矩阵和邻接表结构及逆邻接表结构的转换算法。
6、图的深度优先和广度优先遍历的应用算法，如：查找、求解通路和最短路径等。
7、有向无环图的拓扑排序的应用算法。
8、习题集算法例题举例：
2.15、2.20、2.29、2.37、6.39、6.41、6.44、6.48、6.52、7.22、7.27、7.34、7.35
B、试题举例：
数据结构试题（2011级）
一、单选题（每小题2分）
1．抽象数据类型ADT的三个组成部分是
A．数据对象、数据关系和基本操作
B．数据元素、逻辑结构和存储结构
C．数据项、数据元素和数据类型
D．数据元素、数据结构和数据类型
2. 在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是
A. 对顺序表中元素进行排序
B. 插入第i个元素
C. 删除第i个元素
D. 访问第i个元素的前驱
3．设p指向单链表中的一个结点，s指向单链表表外待操作的结点，则下述程序段的功能是：s->next=p->next; p->next=s; t=p->data; p->data=s ->data; s->data=t; A．删除结点p
B．插入结点s
C．在结点p之后插入结点s
D．结点p与插入结点s的数据域互换
4．如果入栈序列是1,3,5，…，97,99，且出栈序列的第1个元素为99，则出栈序列中第30个元素是
A．39 B．41
C．43 D．45
5．用一个大小为1000的数组来实现循环队列，当前的队头和队尾指针分别为4和996，若要达到队列满的条件，可以继续入队的元素个数是
A．5 B．6
C．7 D．8
6．多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为
A．数组的元素处在行和列两个关系中
B．数组的元素必须从左到右顺序排列
C．数组的元素之间存在次序关系
D．数组是多维结构，内存是一维结构
7. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该二叉树与所对应的孩子兄弟链
表表示的二叉树的高度相比
A. 前者比后者低
B. 前者比后者高
C. 前者与后者相同
D. 不易确定
8. 假设一棵完全二叉树中的第6层上有24个叶子结点，则该二叉树的结点个数最多为
A. 55
B.79
C. 81
D.127
9．设某棵二叉树的中序遍历序列为ABCDE，后序遍历序列为BADEC，则该二叉树的层次遍历序列为
A．BADCE B．BCDAE
C．CAEBD D．CBDAE
10.如果某图的邻接矩阵是非对称矩阵，则此图一定不．是
A. 有环图
B. 有向无环图
C. 强连通图
D. 上述答案有错
11. 若一个具有N个顶点和K条边的无向图（N>K）是一个森林，则该森林的数目一定是
A．K B．N
C．N-K D．1
12. 已知哈希表的存储空间为T[0..18]，哈希函数H（key）= key%17,并用线性探测再散列
法处理冲突。哈希表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是
A. T[2]
B. T[4]
C. T[8]
D. T[10]
13．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字为w的过程中，先后进行比较的关键字依次为
A．f,r,s,t B．f,s,g,q
C．g,q,s,t D．g,d,q,s
14．对关键字序列（5，1，4，3，7）进行堆排序时，输出第2个元素后的系列结果为A．（1，3，4，5，7） B．（7，3，5，4，1）
C．（1，4，3，5，7） D．（7，4，5，3，1）
15．下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlogn)的是
A. 归并排序
B. 冒泡排序
C. 直接选择排序
D. 快速排序
二、应用题（每小题6分）
16. 双端队列是一种插入和删除仅在线性表的两端都可进行的线性表。若允许一端进行插入和删除，另一端只允许删除的双端队列为输入受限的双端队列。假设输入序列为1，2，3，4。双端队列的左端为单输入端。
试求：（1）画出输入受限的双端队列的示意图。
（2）给出单输入端的输出端口不可能得到的输出序列。（至少5种）
（1-4-2-3，2-4-1-3，3-4-1-2，3-1-4-2，3-1-2-4,4-1-2-3,4-1-3-2,4-2-1-3,4-2-3-1,4-3-1-2共10种）17. 已知带有双亲指针域的二叉树的结点类型PTNnde逻辑结构如下所示：
试求：（1）给出该二叉树的存储结构定义。
（2）说明在非递归且不使用栈的中序遍历中，Parent域的作用。
18.已知一个无向带权图的边结点结构为（顶点1，顶点2，权值），顶点集V和边集E分别
为：V={1,2,3,4,5};E={<1,2,2>,<1,4,6>,<2,3,8>,<2,4,3>,<3,5,5>,<3,4,2>,<4,5,9>}。试求：（1）画出该图的邻接矩阵存储结构示意图。
（2）采用普利姆算法，求最小生成树，画出求解过程，给出最小代价的结果。
19．已知一组初始记录关键字序列为(3，9，51，8，4，7，2，52)。
试求：（1）给出该序列的快速排序的前三趟结果。
（2）举例说明快速排序的不稳定性。
（1） 3 9 51 8 4 7 2 52
第1趟 2 3 518 4 7 9 52
第2趟 2 3 4 51 8 7 9 52
第3趟 2 3 4 51 52 7 8 9
（2）若排序序列为：51 52 3 4
排序前51 < 52 51 领先52
排序后序列为： 3 4 52 51
512 < 51 52 领先51
所以，快速排序为不稳定排序
20. 已知一组初始记录关键字序列为(35，20，33，48，59，47，62，50，48)。其哈希函数
为H(key)=key%13，处理冲突的方法为链地址法。
试求：（1）设计哈希表。
（2）在等概率查找时查找成功的平均查找长度。
成功时平均查找长度=（5*1+2*2+3*1）/8=1.5
三、算法阅读与分析题（本题10分）
已知SqList为顺序表类型，阅读下列算法，回答问题。
void Sq_F(SqList &L {
1. for(i=j=0;i 2. if(L.elem[i]>=0){ 3. if(i!=j) //注释（1） 4. L. elem [j]= L.elem[i]; 5. j++; //注释（2） 6. }//if 7. }//for 8. L.length=j; 9. }// Sq_F 试求：（1）说明算法的功能。 （2）在语句3和语句5后面加上注释。 （3）若初始顺序表L=(19，-8，49，-56，-10，10，0，20，-50)，给出算法执行后L 的结果。 （1）删除顺序表中的负值元素，将非负元素调整到表的前部。 （2）注释（1）：在i下标之前不存在负值元素，无需向前移动元素 注释（2）：记录当前非负元素个数。 （3）L=(19，49，10，0，20)， 四、算法设计题（本题10分） 已知LinkList为单链表类型，L为带头结点的单链表的头指针。指针p为当前访问的结点指针，pre为p的前驱结点指针。结点Lnode的结构为（data,next）。设计算法，从任意给定位置开始，将指针p右边的k个结点置逆。 函数原型定义如下：void shift_right_k(LinkList &L, LinkList p,LinkList pre,int k) 试求：（1）算法描述。 （2）算法实现。 int shift_right_k(LinkList &L, LinkList p,LinkList pre,int k){ //将指针p右移的k个结点置逆。若置逆成功，返回1，否则，返回0。. int count=0; for(q=p;count<=k;count++,q=q->next);//判断是否有K个结点 if(count else{//将p右侧的k个元素置逆 t=p;pre=p;p=p->next;count=0; while(p&& count<=k){ q=p->next; count++; p->next=pre;pre=p;p=q; }// while t->next=p;//链接后继元素 return 1; }// else }// shift_right_k 五、算法设计题（本题10分） 已知二叉树T的结点BNode的逻辑结构示意图如下： BNode 试求：设计算法，求二叉树中单分支结点的个数。 函数原型定义如下：void Snode_T(BNode* &T,int &count) void Snode_T(BNode* &T,int &count){ if(T){ //初始调用，count为0 if(T->Lchild&&!T->Rchild|| !T->Lchild&&T->Rchild) //判断单分支结点count++;//计数器加1 Snode_T(T->Lchild ,count); //遍历左子树 Snode_T(T->Rchild ,count); //遍历右子树 }//if }// Snode_T 六、算法设计题（本题10分） 已知图的邻接矩阵结构定义如下： #define MaxNum 20 typedef int AdjMatrix[MaxNum][MaxNum]; typedef struct { ElenType Vexs[MaxNum];//顶点数组 AdjMatrix arcs;//邻接矩阵 int n,e;//图中当前的顶点数和边数 } MGraph;//邻接矩阵图 栈的一些基本操作定义如下： void InitStack(SqStack &S) // void Push(SqStack &S,ElemType e)// void Pop(SqStack &S,ElemType &e)// int StackEmpty(SqStack S)// void GetTop(SqStack S,ElemType &e)// 试求：设计邻接矩阵图的拓扑排序算法。（可以使用栈的基本操作） 函数原型定义如下：int Topo_G(MGraph G,SqStack S) int Topo_G(MGraph G,SqStack S){ //邻接矩阵图的拓扑排序算法 int indegree[maxsize]; //定义求入度数组 int i, count, k; FindID(G, indegree); //求各顶点入度 InitStack(S); //初始化辅助栈 for(i=0; i if(indegree[i]==0) Push(S, i);//将入度为0的顶点入栈 count=0; while(!StackEmpty(S)) { Pop(S, i);//出栈 printf( G.vexs[i]); count++; //输出i号顶点并计数 for(j=0;j if(G.arcs[i][j]){ indegree[j]--; // i号顶点的每个邻接点的入度减1 if(indegree[j]==0) Push(S,j); //若入度减为0，则入栈 } } //while if (count return 0; //该有向图含有回路 else return 1; } // Topo_G 习题集算法例题举例： 2-20、删除元素递增排列的链表L中所有值相同的元素 Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素{ p=L->next;q=p->next; //p,q指向相邻两元素 while(p->next) { if(p->data!=q->data) { p=p->next;q=p->next; //当相邻两元素不相等时,p,q都向后推一步 } else { while(q->data==p->data) { t=q; q=q->next; free(t); } p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素 }//else }//while }//Delete_Equal 2-37、对L=（a1,a2,a3……,.a n）按L=（a1,a3,a……a n,a n-1..a4,a2）的顺序重排双向循环链表L 中的所有结点 void OEReform(DuLinkedList &L)//按规定顺序重排双向循环链表L中的所有结点 { p=L.next; while(p->next!=L&&p->next->next!=L) { p->next=p->next->next; p=p->next; } //此时p指向最后一个奇数结点 if(p->next==L) p->next=L->pre->pre; else p->next=L->pre; p=p->next; //此时p指向最后一个偶数结点 while(p->pre->pre!=L) { p->next=p->pre->pre; p=p->next; } p->next=L; //按题目要求调整了next链的结构,此时pre链仍为原状 for(p=L;p->next!=L;p=p->next) p->next->pre=p; L->pre=p; //调整pre链的结构 }//OEReform 6-41、求先序遍历中第k个结点的值。 int c,k; //这里把k和计数器c作为全局变量处理 void Get_PreSeq(Bitree T)//求先序序列为k的结点的值 { if(T) { c++; //每访问一个子树的根都会使前序序号计数器加1 if(c==k) { printf("Value is %d\n",T->data); exit (1); } else { Get_PreSeq(T->lchild); //在左子树中查找 Get_PreSeq(T->rchild); //在右子树中查找 } }//if }//Get_PreSeq 6-52、求一棵二叉树的"繁茂度" 。 typedef struct{ BTNode node; int layer; } BTNRecord; //包含结点所在层次的记录类型 int FanMao(Bitree T)//求一棵二叉树的"繁茂度" { int countd[]; //count数组存放每一层的结点数 InitQueue(Q); //Q的元素为BTNRecord类型 EnQueue(Q,{T,0}); while(!QueueEmpty(Q)) { DeQueue(Q,r); count[https://www.doczj.com/doc/da1161092.html,yer]++; if(r.node->lchild) EnQueue(Q,{r.node->lchild,https://www.doczj.com/doc/da1161092.html,yer+1}); if(r.node->rchild) EnQueue(Q,{r.node->rchild,https://www.doczj.com/doc/da1161092.html,yer+1}); } //利用层序遍历来统计各层的结点数 h=https://www.doczj.com/doc/da1161092.html,yer; //最后一个队列元素所在层就是树的高度 for(maxn=count[0],i=1;count[i];i++) if(count[i]>maxn) maxn=count[i]; //求层最大结点数 return h*maxn; }//FanMao 7-27、判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径 int visited[MAXSIZE]; int exist_path_len(ALGraph G,int i,int j,int k)//判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径 { if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { l=p->adjvex; if(!visited[l]) if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else return 0; //没找到 }//exist_path_len 7-34、对有向无环图的顶点重新编号，若顶点i指向顶点j，则应编号i { int indegree[MAXSIZE]; //本算法就是拓扑排序 FindIndegree(G,indegree); Initstack(S); for(i=0;i if(!indegree[i]) Push(S,i); count=0; while(!stackempty(S)) { Pop(S,i);new[i]=++count; //把拓扑顺序存入数组的对应分量中 for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(!(--indegree[k])) Push(S,k); } }//while if(count return OK; }//TopoSeq 数据结构设计与技巧讲义 【考查目标】 1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3.能够选择合适的数据结构和方法进行问题求解。 一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的概念 （二）二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 （三）树、森林 1.书的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 （四）树的应用 1.等价类问题 2.哈夫曼（Huffman）树和哈夫曼编码 四、图 （一）图的概念 （二）图的存储及基本操作 1.邻接矩阵法 2.邻接表法 （三）图的遍历 1.深度优先搜索 2.广度优先搜索 （四）图的基本应用及其复杂度分析 1.最小（代价）生成树 2.最短路径 3.拓扑排序 4.关键路径 五、查找 （一）查找的基本概念 （二）顺序查找法 （三）折半查找法 （四）B-树 （五）散列（Hash）表及其查找 （六）查找算法的分析及应用 六、内部排序 （一）排序的基本概念 （二）插入排序 1.直接插入排序 2.折半插入排序 （三）气泡排序（bubble sort） （四）简单选择排序 （五）希尔排序（shell sort） （六）快速排序 （七）堆排序 （八）二路归并排序（merge sort） （九）基数排序 （十）各种内部排序算法的比较 （十一）内部排序算法的应用 【知识点解析】 1.线性表 线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、线性表的实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链式存储结构，特别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本应用。 2.栈、队列和数组 栈和队列是两种特殊的线性表，在这方面，要求我们掌握栈和队列的基本概念，以及他们之间的区别。对于栈和队列的存储结构(包括顺序存储结构、链式存储结构)要有较深的理解，对于栈和队列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。 判断： 1.线性表的链式存储结构优于顺序存储错误 2.单链表的每个节点都恰好包含一个指针域错误 3.线性表中的元素都可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因 此属于同一数据对象正确 4.在线性表的顺序存储结构中，逻辑上相邻的两个元素在屋里位置上并不一定紧邻。错 误 5.在线性表的数据结构中，插入和删除元素时，移动元素的个数和该元素的位置有关。正 确 6.顺序存储的线性表可以实现随机存取正确 7.栈一定是顺序存储的线性结构错误 8.一个栈的输入序列为A，B,C,D，可以得到输入序列为C,A,B,D 错误 9.队列是一种后进先出的线性表错误 10.树结构中每个节点最多只有一个直接前驱正确 11.二叉树的前序遍历中，任意一个节点均处于其子树节点的前面正确 12.在栈空的情况下，不能做出出栈操作，否则产生溢出正确 13.在前序遍历二叉树的序列中，任何节点的子树的所有节点都是直接跟在该节点之后正 确 填空： 1.在N个节点的顺序表中删除一个节点平均需要移动（（N-1）/2）个节点，具体的移 动次数取决于（表长N和删除位置） 2.在单链表中除首节点外，任意节点的存储位置都由（直接前驱）节点中的指针指示 3.树中节点的最大层次称为树的（度） 4.由一颗二叉树的前序序列和（中）序列可唯一确定这棵二叉树 5.哈弗曼树的带权路径长度（最小）的二叉树 6.二插排序树任意节点的关键字值（大于）其左子树中各节点的关键字值（小于）其 右子树中的各节点关键字值 7.二分查找法，表中元素必须按（关键字有序）存放 选择： 1.用单链表方式存储的线性表，储存每个节点需要两个域，一个数据域，另一个是（B 指针域） 2.设A1，A2，A3为三个节点；P，10，,2代表地址，则如下的链表存储结构称为（B 单链表） 3.单链表的存储密度（C 小于1） 4.在线性表中（B 中间元素）只有一个直接前驱和一个直接后续 5.两个指针P和Q，分别指向单链表的两个元素P所指元素时Q所指元素前驱的条 件是（D P==Q） 6.在栈中存取数据的原则是（B 后进先出） 7.顺序栈判空的条件是（C top==-1） 8.串是一种特殊的线性表，其特殊性体现在（B 数据元素是一个字符） 9.求字符串T和字符串S中首次出现的位置的操作为（C 串的模式匹配） 10.深度为H的二叉树至多有（B 2H-1）个节点 试题一 一、单项选择题分)2分，共40（本大题共20小题，每小在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。）B 1. 数据库系统的核心是（ ．数据库管理系统B A．数据库 ．软件工具D C．数据模型 ）2. 下列四项中，不属于数据库系统的特点的是（C ．数据由统一管理和控制．数据结构化BA ．数据独立性高．数据冗余度大DC ）概念模型是现实世界的第一层抽象，这一类模型中最著名的模型是（D 3. ．关系模型B．层次模型 A -联系模型D．实体C．网状模型4. ）数据的物理独立性是指（ C ．数据库与数据库管理系统相互独立A ．用户程序与数据库管理系统相互独立B ．用户的应用程序与存储在磁盘上数据库中的数据是相互独立的C ．应用程序与数据库中数据的逻辑结构是相互独立的D A ）．要保证数据库的逻辑数据独立性，需要修改的是（5 B．模式与内模式之间的映象A．模式与外模式之间的映象D．三级模式 C．模式 ）关系数据模型的基本数据结构是（D 6．．关系C．索引 D A．树B．图 有一名为“列车运营”实体，含有：车次、日期、实际发车时间、实际抵7．）达时间、情况摘要等属性，该实体主码是（ C ．日期BA．车次+情况摘要日期D．车次C．车次+ ）S等价于（ B 和己知关系RS，R∩8. B. () A. () D. () C. () 学校数据库中有学生和宿舍两个关系：9． 宿舍（楼名，房间号，床位号，学号）学生（学号，姓名）和 假设有的学生不住宿，床位也可能空闲。如果要列出所有学生住宿和宿舍分配）的情况，包括没有住宿的学生和空闲的床位，则应执行（ A B. 全外联接A. 左外联接1 / 13 自然联接D. 右外联接C. 10．用下面的语句建立一个基本表：( (4) ,(8) ,(2),) D ）可以插入到表中的元组是（21 ，刘祥'，A. '5021'，'刘祥'，男， 21 B. ，''，，，男，C. '5021'，21 D. '5021'，'刘祥 C ）11. 把对关系的属性的修改权授予用户李勇的语句是（' A. .. ;.. 第一章 概论 1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算 2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系 可以用一组数据（结点集合K ）以及这些数据之间的 一组二元关系（关系集合R ）来表示：(K, R) 结点集K 是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据 关系集R 是定义在集合K 上的一组关系，其中每个关系r （r ∈R ）都是K ×K 上的二元关系 3.数据类型 a.基本数据类型 整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型（char ）、指针类型（pointer ） b.复合数据类型 复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型 4.数据结构的分类：线性结构（一对一）、树型结构（一对多）、图结构（多对多） 5.四种基本存储映射方法：顺序、链接、索引、散列 6.算法的特性：通用性、有效性、确定性、有穷性 7.算法分析：目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化 8.渐进算法分析 a ．大Ο分析法：上限，表明最坏情况 b ．Ω分析法：下限，表明最好情况 c ．Θ分析法：当上限和下限相同时，表明平均情况 第二章 线性表 1.线性结构的基本特征 a.集合中必存在唯一的一个“第一元素” b.集合中必存在唯一的一个“最后元素” c.除最后元素之外，均有唯一的后继 d.除第一元素之外，均有唯一的前驱 2.线性结构的基本特点:均匀性、有序性 3.顺序表 a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度 b. 线性表中任意元素的存储位置：Loc(ki) = Loc(k0) + i * L （设每个元素需占用L 个存储单元） c. 线性表的优缺点： 优点：逻辑结构与存储结构一致；属于随机存取方式，即查找每个元素所花时间基本一样 缺点：空间难以扩充 d.检索：ASL=【Ο（1）】 e .插入：插入前检查是否满了，插入时插入处后的表需要复制【Ο（n ）】 f.删除：删除前检查是否是空的，删除时直接覆盖就行了【Ο（n ）】 4.链表 4.1单链表 a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等 b.带头结点的怎么判定空表：head 和tail 指向单链表的头结点 c.链表的插入（q->next=p->next; p->next=q;）【Ο（n ）】 d.链表的删除（q=p->next; p->next = q->next; delete q;）【Ο（n ）】 e.不足：next 仅指向后继，不能有效找到前驱 4.2双链表 a.增加前驱指针，弥补单链表的不足 b.带头结点的怎么判定空表:head 和tail 指向单链表的头结点 c.插入：（q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;） d.删除：（p->prev->next = p->next; p->next->prev = p->prev; p->prev = p->next = NULL; delete p;） 4.3顺序表和链表的比较 4.3.1主要优点 a.顺序表的主要优点 没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利 b.链表的主要优点 无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合 经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相 比其比例较大时，应该慎重选择 第三章 栈与队列 1.栈 a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种 b.应用： 1）数制转换 while (N) { N%8入栈； N=N/8;} while (栈非空){ 出栈； 输出；} 2）括号匹配检验 不匹配情况：各类括号数量不同；嵌套关系不正确 算法： 逐一处理表达式中的每个字符ch ： ch=非括号：不做任何处理 ch=左括号：入栈 ch=右括号：if (栈空) return false else { 出栈，检查匹配情况， if (不匹配) return false } 如果结束后，栈非空，返回false 3）表达式求值 3.1中缀表达式： 计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右 3.2后缀表达式： <表达式> ::= <项><项> + | <项> <项>－|<项> <项> ::= <因子><因子> * |<因子><因子>/|<因子> <因子> ::= <常数> ? <常数> ::= <数字>|<数字><常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.3中缀表达式转换为后缀表达式 InfixExp 为中缀表达式，PostfixExp 为后缀表达式 初始化操作数栈OP ，运算符栈OPND ；OPND.push('#'); 读取InfixExp 表达式的一项 操作数：直接输出到PostfixExp 中； 操作符： 当‘（’：入OPND; 当‘）’：OPND 此时若空，则出错；OPND 若非空，栈中元 素依次弹出，输入PostfixExpz 中，直到遇到‘（’为止；若 为‘（’，弹出即可 当‘四则运算符’：循环（当栈非空且栈顶不是‘（’&& 当前运算符优先级>栈顶运算符优先级），反复弹出栈顶运 算符并输入到PostfixExp 中，再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP ； while （表达式没有处理完) { item = 读取表达式一项; 操作数：入栈OP ； 运算符：退出两个操作数， 计算，并将结果入栈} c.递归使用的场合：定义是递归的；数据结构是递归的；解决问题的方法是递归的 2.队列 a.若线性表的插入操作在一端进行，删除操作在另一端进行，则称此线性表为队列 b.循环队列判断队满对空： 队空：front==rear ；队满：(rear+1)%n==front 第五章 二叉树 1.概念 a. 一个结点的子树的个数称为度数 b.二叉树的高度定义为二叉树中层数最大的叶结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶结点的层数 d.如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树 e.如果一颗二叉树最多只有最下面的两层结点度数可以小于2；最下面一层的结点都集中在该层最左边的位置上，则称此二叉树为完全二叉树 f.当二叉树里出现空的子树时，就增加新的、特殊的结点——空树叶组成扩充二叉树，扩充二叉树是满二叉树 外部路径长度E ：从扩充的二叉树的根到每个外部结点（新增的空树叶）的路径长度之和 内部路径长度I ：扩充的二叉树中从根到每个内部结点（原来二叉树结点）的路径长度之和 2.性质 a. 二叉树的第i 层（根为第0层，i ≥0）最多有2^i 个结点 b. 深度为k 的二叉树至多有2k+1-1个结点 c. 任何一颗二叉树，度为0的结点比度为2的结点多一个。n0 = n2 + 1 d. 满二叉树定理：非空满二叉树树叶数等于其分支结点数加1 e. 满二叉树定理推论：一个非空二叉树的空子树(指针)数目等于其结点数加1 f. 有n 个结点（n>0）的完全二叉树的高度为?log2(n+1)?，深度为?log2(n+1)?? g. 对于具有n 个结点的完全二叉树，结点按层次由左到右编号，则有： 1) 如果i = 0为根结点；如果i>0，其父结点编号是 (i-1)/2 2) 当2i+1 数据结构以及C语言常问与难点 1.序言 2.常问与难点，为避免重复发帖，特设此帖并置顶，以供浏览查阅。 3.内容主要是将本版的好帖子收集起来，并加以整理，仅给出知识点分析与问题解答，并不给出原帖链接，致歉。 4.本版中的好东西会慢慢添加进来（各位版主齐心协力，每天添加一个知识点，用不了多久就会很强大），本帖观点只 是各位版主和我个人的分析，不一定尽善尽美，但一定是尽心尽力。各位热心研友如有修正和补充，请在回复中说明。 5.特代表研友感谢各位版主的辛勤奉献，代表版主感谢热心研友对王道的支持（呵呵）。特别地，祝备考10的研友们一 切顺利，考上理想的学校。珍惜时间，努力才是王道。 1.目录，共占用一个代码区 2. 3. 1.如下结构体定义的全部细节解释，附有完整程序。涉及知识点：结构体定义，typedef，指针使用的部分知识。 4.typedef struct LNode{ 5. ElemType data; 6. struct LNode *next; 7.} LNode, *LinkList; 8. 9. 2.符号&的含义，指针进阶。涉及知识点：引用机制，实参与形参，C语言中地址与指针（以及指向指针的指针），指 针的传递（暂不涉及数组与指针的知识，将在以后介绍）。 10. 11. 3.如下方式动态分配内存的全部细节解释。涉及知识点：动态分配内存，define，强制类型转换，malloc()，顺序 表存储结构，顺序表与数组，链表结点的内存分配，指针细节，附完整程序。 12.L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); 复制代码 1.正文，每个问题占用一个代码区 复制代码 1. 1.如下结构体定义的全部细节解释，附有完整程序。涉及知识点：结构体定义，typedef，指针使用的部分知识。 2.typedef struct LNode{ 3. ElemType data; 4. struct LNode *next; 5.} LNode, *LinkList; 6. 7.如下是一个最简单的结构体定义： 1.什么是最小生成树？简述最小生成树的Prime算法的思想。 答：最小生成树就是构造一棵生成树，使得树上各边的代价之和最小。 普里姆算法(Prim)的基本思想： 从连通网络N = { V, E }中的某一顶点u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 2.简述AOV网络中为何不能出现回路，如何判断AOV网络是否有回路？ 答：在AOV网络中，如果活动vi必须在vj之前进行，则称为存在有向边；在AOV网络中不能出现有向回路，如果出现了，则意味着某项活动应以自己作为先决条件。 如何检查AOV网是否存在有向环： 检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。（1）这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 （2）如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV 网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。 3.为何需要采用循环队列？n个空间的循环队列，最多存储多少个元素？为什 么？ 答：循环队列以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用，所以采用循环队列。 n个空间的循环队列，最多存储n-1个元素，那是为了区别循环队列的队空和队满的条件。队空的条件是Q.front==Q.rear，而队满的条件是(Q.rear+1)%N==Q.front(N是数组中单元的总数)，因此，Q.rear所指向的数组单元处于未用状态。所以说，N个单元的数组所存放的循环队列最大长度是N-1。 4.简述堆的删除算法，其删除的是那个值？ 答：堆的删除算法：首先，移除根节点的元素（并把根节点作为当前结点）比较当前结点的两个孩子结点的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的孩子结点作为当前结点，并再比较当前结点的孩子的大小，以此循环，直到最后一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数，则退出循环。最后把最后叶子结点的元素移给当前结点。 在堆的算法里面，删除的值为根值。 5.线索二叉树中，什么是线索，它是否唯一？可有根据什么顺序得到？ 数据库期末考试复习题库(非常全面) 第一部分 第一章： 一选择题： 1．在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。在这几个阶段中，数据独立性最高的是阶段。 A．数据库系统 B．文件系统 C．人工管理 D．数据项管理答案：A 2．数据库的概念模型独立于。 A．具体的机器和DBMS B．E-R图C．信息世界 D．现实世界答案：A 3．数据库的基本特点是。 A．(1)数据可以共享(或数据结构化) (2)数据独立性(3)数据冗余大，易移植(4)统一管理和控制 B．(1)数据可以共享(或数据结构化) (2)数据独立性(3)数据冗余小，易扩充(4)统一管理和控制 C．(1)数据可以共享(或数据结构化) (2)数据互换性(3)数据冗余小，易扩充(4)统一管理和控制 D．(1)数据非结构化 (2)数据独立性(3)数据冗余小，易扩充(4)统一管理和控制答案：B 4. 是存储在计算机内有结构的数据的集合。 A．数据库系统 B．数据库C．数据库管理系统 D．数据结构答案：B 5．数据库中存储的是。 A．数据 B．数据模型C．数据以及数据之间的联系 D．信息答案：C 6. 数据库中，数据的物理独立性是指。 A．数据库与数据库管理系统的相互独立B．用户程序与DBMS的相互独立 C．用户的应用程序与存储在磁盘上数据库中的数据是相互独立的 D．应用程序与数据库中数据的逻辑结构相互独立答案：C 7. ．数据库的特点之一是数据的共享，严格地讲，这里的数据共享是指。 A．同一个应用中的多个程序共享一个数据集合 B．多个用户、同一种语言共享数据 C．多个用户共享一个数据文件 D．多种应用、多种语言、多个用户相互覆盖地使用数据集合答案：D 8.据库系统的核心是。 A．数据库B．数据库管理系统C．数据模型D．软件工具答案：B 9. 下述关于数据库系统的正确叙述是。 A．数据库系统减少了数据冗余 B．数据库系统避免了一切冗余 C．数据库系统中数据的一致性是指数据类型一致 D．数据库系统比文件系统能管理更多的数据答案：A 一、是非题 1.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运 算三个方面。.......................( T ) 2.线性表的逻辑顺序与物理顺序总是一致的........( F ) 3.线性表中的每个结点最多只有一个前驱和一个后继。......( T ) 4.线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存 储。.......................( F ) 5.栈和队列逻辑上都是线性表。..........................( T ) 6.单链表从任何一个结点出发，都能访问到所有结点........( F ) 7.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后 一个结点。.................................................( T ) 8.在用单链表表示的链式队列中，队头在链表的链尾位置。....( F ) 9.多维数组是向量的推广。..............................( T ) 10.栈是一种先进先出的线性表。....( F ) 11.凡是递归定义的数据结构都可以用递归算法来实现它的操作。......( T ) 12.设串S的长度为n,则S的子串个数为n(n+1)/2。...........( F ) 13.一般树和二叉树的结点数目都可以为0。................( F ) 14.按中序遍历二叉树时，某结点的直接后继是它的右子树中第1个被访问的结 点。....( T ) 15.后序序列和中序序列能唯一确定一棵二叉树。....( T ) 16.对于一棵具有n个结点，其高度为h的二叉树，进行任—种次序遍历的时间复杂 度为O(n) .............( T ) 17.网络的最小代价生成树是唯一的。...( T ) 18.图的拓扑有序序列不是唯一的。...( T ) 19.进行折半搜索的表必须是顺序存储的有序表。...( T ) 二、单选题 1.算法指的是（ D ） A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 2.线性表采用链式存储时，结点的存储地址（B ） A．必须是不连续的 B．连续与否均可 C．必须是连续的 D．和头结点的存储地址相连续 3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C ） A．O（1） B．O（n） C．O（m） D．O（m+n） 4.在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为( B )。 A．O(n) B．O(1) C．O(n2) D．O(log2n)T 5.线性表L在( B )情况下适用于使用链式结构实现。 A.需经常修改Ｌ中的结点值 B.需不断对Ｌ进行删除插入 C.L中含有大量的结点 D.L中结点结构复杂 6.设单链表中结点的结构为(data，1ink)。已知指针q所指结点是指针p所指结点 的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作?( B ) A．s一>1ink=p一>1ink；p一>1ink＝s B．q一>1ink＝s；s一>link=p C．p一>link＝s一>1ink；s一>1ink＝p 2018考研计算机：数据结构重难点及 复习建议 新东方在线推荐： 一、重难点解析和复习建议 数据结构的考查目标定位为掌握数据结构的基本概念、基本原理和基本方法，掌握数据的逻辑结构、存储结构以及基本操作的实现;能够对算法进行基本的时间复杂度和空间复杂度的分析;能够运用数据结构的基本原理和方法进行问题的分析求解，具备采用C、C++或JAVA语言设计程序与实现算法的能力。 当然，考生也不必因此而专门复习一遍C或C++程序设计，毕竟复习时间有限，而且数据结构要求的重点在于算法设计的能力，而不是编写代码的能力，因此，只要能用类似伪代码的形式把思路表达清楚就行，不用强求写出一个没有任何语法错误的程序。 下面我们来解析一下知识点： 线性表这一章里面的知识点不多，但要做到深刻理解，能够应用相关知识点解决实际问题。链表上插入、删除节点时的指针操作是选择题的一个常考点，诸如双向链表等一些相对复杂的链表上的操作也是可以出现在综合应用题当中的。 栈、队列和数组可以考查的知识点相比链表来说要多一些。最基本的，是栈与队列FILO和FIFO的特点。比如针对栈FILO的特点，进栈出栈序列的问题常出现在选择题中。其次，是栈和队列的顺序和链式存储结构，这里一个常考点是不同存储结构下栈顶指针、队首指针以及队尾指针的操作，特别是循环队列判满和判空的2种判断方法。再次，是特殊矩阵的压缩存储，这个考点复习的重点可以放在二维矩阵与一维数组相互转换时，下标的计算方法，比如与对角线平行的若干行上数据非零的矩阵存放在一维数组后，各个数据点相应的下标的计算。这一章可能的大题点，在于利用堆栈或队列的特性，将它们作为基础的数据结构，支持实际问题求解算法的设计，例如用栈解决递归问题，用队列解决图的遍历问题等等。 树和二叉树：这一章中我们从顺序式的数据结构，转向层次式的数据结构，要掌握树、二叉树的各种性质、树和二叉树的不同存储结构、森林、树和二叉树之间的转换、线索化二叉树、二叉树的应用(二叉排序树、平衡二叉树和Huffman树)，重点要熟练掌握的，是森林、树以及二叉树的前中后三种遍历方式，要能进行相应的算法设计。这一部分是数据结构考题历来的重点和难点，复习时要特别关注。一些常见的选择题考点包括：满二叉树、完全二叉树节点数的计算，由树、二叉树的示意图给出相应的遍历序列，依据二叉树的遍历序列还原二叉树，线索化的实质，计算采用不同的方法线索化后二叉树剩余空指针域的个数，平衡二叉树的定义、性质、建立和四种调整算法以及回溯法相关的问题。常见的综合应用题考点包括：二叉树的遍历算法，遍历基础上针对二 第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长 数据库系统概论期末复习重点 重点在一到七章，考试内容三大类：基本概念，SQL语言和数据库的设计与应用第一章.绪论 (一)数据、数据库、数据库管理系统和数据库系统相关概念： 1.数据（Data）：描述事物的符号记录。数据与其语义密不可分。（P4） 2.数据库（DataBase，简称DB）：数据库是长期存储在计算机内、有组织、可共享的大量数据的集合。因此，永久存储、有组织、可共享是数据库的三个基本特点。（P4） 3.数据库管理系统（DataBase Management System，简称DBMS）：数据库管理系统是位于用户与操作系统之间的一层数据管理软件，其任务是科学、高效地管理数据库中的数据。（P5）数据库管理系统的主要功能有： 1)数据定义功能 2)数据操纵功能 3)数据组织、存储和管理 4)数据库的事务管理和运行管理 5)数据库的简历和维护功能 6)其他功能：如DBMS与网络中其他软件系统的通信功能、异构数据库之间的互访和互操作功能、多个DBMS之间的数据转换功能等。 4.数据库系统（DataBase System，DBS）：在计算机系统中引入数据库后的系统，由数据库、数据库管理系统（及其开发工具）、应用系统、数据库管理员（DataBase Administrator，DBA）构成。 (二)数据管理技术的发展：（P7） 1.人工管理阶段：主要出现于20世纪50年代中期以前，数据处理方式为批处理。其特点为： 1)数据不保存 2)应用程序管理数据 3)数据不共享 4)数据不具有独立性 2.文件系统阶段：20世纪50年代后期到60年代中期，其特点是： 1)数据可以长期保存 2)由专门的软件系统（文件系统）管理数据 但文件系统仍然存在以下不足：数据共享性差、冗余度大、数据独立性差 3.数据库系统阶段：20世纪60年代至今。其特点是： 1)数据结构化 2)数据的共享性高，冗余度低，易扩充 3)数据的独立性高 4)数据由DBMS同一管理和控制 二、数据模型：（概念） (一)两类数据模型：第一类是概念模型，第二类是逻辑模型和物理模型。（P12） (二)数据模型的三大组成要素：（P13） 1.数据结构数据结构设计与技巧
数据结构期末考试复习笔记
数据库期末考试复习题及复习资料
大学数据结构期末知识点重点总结(考试专用)
数据结构以及C语言常问与难点
数据结构 期末考试复习题及答案
数据库期末考试复习题库(非常全面)
2010级数据结构期末复习题(E)
2018考研计算机：数据结构重难点及复习建议
数据结构复习资料,java数据结构期末考试
数据库系统概论期末复习大纲
相关主题
文本预览