数据结构复习要点
A —熟练掌握
B —理解
C —了解
第一章：绪论
1. 基本概念：
包括数据的逻辑结构、数据的存储结构和数据的相关运算。C 四类数据组织结构：集合、线性表、树形、图状结构 C 数据的存储方式：顺序存储和链式存储。B 2.算法和分析
算法的特征、时间复杂度的分析和常见的时间复杂度增长率排序、空间复杂度 B 本章重点：分析算法时间复杂度
例1. 下面关于算法说法错误的是（ ）
A ．算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性
D. 以上几个都是错误的 D
例2. 以下那一个术语与数据的存储结构无关？（ ）
A ．栈 B. 哈希表 C. 线索树 D. 双向链表 A ．
例3.． 求下段程序的时间复杂度：
void mergesort(int i, int j){ int m; if(i!=j){ m=(i+j)/2; mergesort(i,m); mergesort(m+1,j); merge(i,j,m);} }
其中mergesort()用于对数组a[n]归并排序，调用方式为mergesort(0,n-1);，merge()用于两个有序子序列的合并，是非递归函数，时间复杂度为()O n 。 解：分析得到的时间复杂度的递归关系：
(1)
1()2(/2)()1O n t n t n O n n =?=?
+>?
()O n 为merge （）所需的时间，设为cn （c 为常量）。因此
222()2(/2)2(2(/2)/2)2(/2)2....2(/2)k k t n n cn t n cn cn
t n cn t n kcn
=+=++=+==+
令
12
k n
=，有2log k n = 有2log 222()2
(1)log log (log )n
t n O cn n n cn n O n n =+=+=
第二章：线性表
1.线性表的基本运算：….. C
2.线性表的顺序存储（利用静态数组或动态内存分配）。相应的表示与操作 A
3.线性表的链式存储。相应的表示与操作。包括循环链表、双向链表。 A
4.顺序存储与链式存储的比较：基于时间的考虑--分别适用于静态的和动态的操作：比如静态查找和插入删除）；基于空间的考虑-- ……. B
这也适用于后面用两种方式存储的其他数据结构。
★本章重点：很熟悉顺序表，单链表、双链表，循环链表的基本操作；并学会在各种链表上进行一些算法设计（与基本操作类似的操作或组合），请仔细复习。
例4．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
[题目分析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。
void Union(LinkList la, LinkList lb)
∥la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将两链表合并成一个按元素值递减次序排列的单链表。
{ pa=la->next; pb=lb->next;∥pa，pb分别是链表la和lb的工作指针
la->next=null; ∥la作结果链表的头指针，先将结果链表初始化为空。
while(pa!=null && pb!=null) ∥当两链表未访问结束
if(pa->data<=pb->data)
{ q=pa->next; ∥将pa 的后继结点暂存于q。
pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。
la->next=pa;
pa=q; ∥恢复pa为当前待比较结点。
}
else{
q=pb->next;∥将pb 的后继结点暂存于q。
pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。
la->next=pb;
pb=q; ∥恢复pb为当前待比较结点。
}
while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。
{q=pa->next; pa->next=la->next; la->next=pa; pa=q; }
while(pb!=null)
{q =pb->next; pb->next=la->next; la->next=pb; pb=q; }
}∥算法Union结束。
注意：
（1）此处q用作暂存后继结点，操作后pa或pb还回原指向位置；这与我们原来不改变pa 或pb的指向，增加一个q=pa或pb作为摘取结点进行添加操作起到的作用一样。
（2）此处要完成逆序插入操作故用头插法（基于头指针la或lb），注意尾插法（附设一个尾指针，基于该指针插入）的可完成顺序插入。（注意：逆序另一种方式也要掌握！）
练习：
练习题2 编程1——6
7.判断带头结点双向循环链表L是否对称相等.
8. 设计一个算法判断单链表（带头结点）是否是递增的（注意比排序算法应该简单，链表排序也要会实现）
9. 设计一个算法判断有序表A是否是有序表B的子集（即表A中的元素在B中）。（思考：如果递归程序怎么写？）
第三章：栈与队列
1.两种特殊线性表：分别有后进先出、先进先出的特性。B
2.栈的顺序表示与实现（利用静态数组或动态内存分配） A
注意栈顶指针的初始位置不同，进出栈，栈空栈满的实现语句有差别！
举例：
若定义
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;//当前栈能使用的最大容量
} SqStack;
SqStack s;
top的初始值指向栈底，即top=base；
栈空条件：s. top ==s. base 此时不能出栈
栈满条件：s.top-s.base>=s.stacksize
进栈操作：*s.top++=e; 或*s.top=e; s.top++;
退栈操作：e=*--s.top；或s.top--；e=*s.top
若定义：
typedef struct {
SElemType base[MAXSIZE];
int top;
}SqStack;
SqStack s;
top的初始值为0时:
栈空条件：s. top ==0 此时不能出栈
栈满条件：s.top >= MAXSIZE
进栈操作：s.base[s.top++]=e;
退栈操作：e=s.base[--s.top]
top的初始值为-1时:
栈空条件：s. top == -1 此时不能出栈
栈满条件：s.top >= MAXSIZE-1
进栈操作：s.base[++s.top]=e;
退栈操作：e=s.base[s.top--]
3.栈的链式表示与实现 B (对比顺序栈，实质不带头结点的链表在头指针处插入和删除)
4.队列的顺序表示与实现—循环队列 A
设两个指针：Q.front 指向队列头元素；Q.rear 指向队列尾元素的下一个位置
注意队中若Q.rear 指向队列尾元素，进出队，实现语句有差别！
初始状态（空队列）：Q.front = Q.rear=0
队头指针进1: Q.front = (Q.front + 1)% MAXSIZE
队尾指针进1: Q.rear = (Q.rear + 1)% MAXSIZE;
队列初始化：Q.front = Q.rear = 0;
队空条件：Q.front == Q.rear;
队满条件：(Q.rear + 1) % MAXSIZE == Q.front
队列长度：(Q.rear-Q.front+MAXSIZE)%MAXSIZE
6.队列的链式表示与实现 B
本章重点：顺序栈的初始条件、操作，循环队列的初始条件、操作
本章难点：栈的设计与使用，队列的设计与使用（主要结合后面树和图中的应用复习）
例5．链栈与顺序栈比起来优势在于。
没有预设容量的限制
例6．计算算术表达式的值时，可用两个栈作辅助工具。对于给出的一个表达式，从左向右扫描它的字符，并将操作数放入栈S1中，运算符放入栈S2中，但每次扫描到运算符时，要把它同S2的栈顶运算符进行优先级比较，当扫描到的运算符的优先级不高于栈顶运算符的优先级时，取出栈S1的栈顶和次栈顶的两个元素，以及栈S2的栈顶运算符进行运算将结果放入栈S1中（得到的结果依次用T1、T2等表示）。为方便比较，假设栈S2的初始栈顶为?（?运算符的优先级低于加、减、乘、除中任何一种运算）。现假设要计算表达式：
例7．将两个栈存入数组V[1..m]应如何安排最好？这时栈空、栈满的条件是什么？，入栈和出栈的操作是什么？
分析：为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的栈底分别设在内存空间的两端，这样只有当两栈顶指针相邻（即值之差的绝对值为1时才产生溢出。
设栈S1和栈S2共享向量V[1..m]，初始时，栈S1的栈顶指针top0=0，栈S2的栈顶指针top1=m+1，当top0=0为栈S1空，top1=m+1为栈S2空；当top0=0并且top1=m+1时为两栈全空。当top1-top0=1时为栈满。
入栈核心操作S1: V[++top0]=x1; S2: V[--top1]=x2
出栈核心操作S1: x1=V[top0--]; S2: x2=V[top1++]
例8．如果用一个循环数组base[0..MAX-1]表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。
（1）编写实现队列的三个基本运算：判空、入队、出队
（2）队列中能容纳元素的最多个数是多少
typedef struct
{ ElemType base[MAX];
int front,count; //front是指向队头元素针，count是队列中元素个数。
}CQueue; //定义类型标识符。
(1)判空：int Empty(CQueue q) //q是CQueue类型的变量
{if(q.count==0) return(1)；
else return(0); //空队列
}
入队: int EnQueue(CQueue q，ElemType x)
{if(q.count==MAX){printf(“队满\n”)；exit(0); }
q.base[(q.front+q.count)%MAX]=x; //x入队
q.count++; return(1); //队列中元素个数增加1,入队成功。
}
出队: int DelQueue(CQueue q, ElemType &x)
{if (q.count==0){printf(“队空\n”)；return(0);}
x=q.base[q.front];
q.front=(q.front+1)%MAX; //计算新的队头指针
q.count--;
return(1);
}
(2) 队列中能容纳的元素的个数为MAX。
第四章：串
1.串的基本概念 C
2.串的顺序表示与实现（两种存储方式） A 特别的模式匹配算法之KMP算法B
本章重点：串的定长顺序存储和堆分配存储、掌握一些常规的串操作（自己会用和会编写）本章难点：串的模式匹配快速算法（KMP）
例9. 串的定长顺序存储缺点在于存在情况。
截断
例10．已知u=‘xyxyxyxxyxy’；t=‘xxy’；
ASSIGN（s，u）；
ASSIGN（v，SUBSTR（s，INDEX（s，t），LEN（t）+1））；
ASSIGN（m，‘ww’）
求REPLACE（ｓ，ｖ，m）= ________。
‘xyxyxywwy’
例11．14．设字符串S=‘aabaabaabaac'，P=‘aabaac'
（1）给出S和P的next值和nextval值；
（2）若S作主串，P作模式串，试给出利用BF算法和KMP算法的匹配过程。
．（1）（1）p的next与nextval值分别为012123和002003。
（2）利用BF算法的匹配过程：
第一趟匹配： aabaabaabaac
aabaac(i=6,j=6)
第二趟匹配： aabaabaabaac
aa(i=3,j=2)
第三趟匹配： aabaabaabaac
a(i=3,j=1)
第四趟匹配： aabaabaabaac
aabaac(i=9,j=6)
第五趟匹配： aabaabaabaac
aa(i=6,j=2)
第六趟匹配： aabaabaabaac
a(i=6,j=1)
第七趟匹配： aabaabaabaac
利用KMP算法的匹配过程：
第一趟匹配：aabaabaabaac
aabaac(i=6,j=6,nextval(j)=3)
第二趟匹配：aabaabaabaac
(aa)baac (i=9,j=6)
第三趟匹配：aabaabaabaac
(成功) (aa)baac(i=13,j=7)
例12．一般串定位函数Index(S,T,pos), 设S的串长为n，T的串长为m,则最坏时间复杂度；而改进的Index_KMP(S,T,pos) 时间复杂度为。
(
O
m
O)n
)
m
*
(n
第五章：数组和广义表
1.数组的存储结构：以行为主序、以列为主序的地址映像函数 B
2矩阵的压缩存储：
（1）特殊阵：包括对称阵、三角阵、带状阵（利用其特性压缩存储到一维数组）B
（2）稀疏阵利用的是三元组顺序表来表示B 用十字链表表示C（本次考试不做要求）3.广义表定义与存储表示 B （本次考试不做要求）
本章重点：地址映像函数的计算（包括数组和特殊矩阵）
例13．已知n阶下三角矩阵A（即当i 答：n阶下三角矩阵元素A[i][j]（1<=i,j<=n,i>=j）。第1列有n个元素，第j列有n-j+1个元素，第1列到第j-1列是等腰梯形，元素数为(n+(n-j+2)(j-1)/2，而a ij在第j列上的位置是为i-j+1。所以n阶下三角矩阵A按列存储，其元素a ij在一维数组B中的存储位置k与i和j的关系为： k=(n+(n-(j-1)+1)(j-1)/2+(i-j+1)=(2n-j)(j-1)/2+i 第六章：二叉树与树 1.二叉树的定义和性质：B 几个特殊的二叉树：满二叉树、完全二叉树、二叉排序树、平衡二叉树 B 2.二叉树的顺序存储： C 3.二叉树的链式存储：用二叉链表表示与实现 A 4.二叉树的遍历：先（中、后）序遍历及应用，相应递归算法和非递归算法 A 5.线索化二叉树（利用二叉链表n+1空指针域来存放某遍历下指向该结点的直接前驱或直接后继，使得蕴含更多信息） B 6.二叉树的应用：算术表达式，霍夫曼树（最优二叉树），判定树 B 7.树的定义和存储表示：….. B 8.树和森林和二叉树的转换 B 9.树与森林的遍历 B ★本章重点：很熟悉二叉树（在二叉链表表示下）的基本操作的递归算法和遍历的非递归算法，请仔细复习。 本章难点：二叉树（含排序树、平衡树）的递归算法和非递归算法。 线索化二叉树及相应操作，重在理解，不考编程！ 例14．引入二叉线索树的目的是（） A．将非线性序列转化成某种线性序列；加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 A 例15．二叉链表在线索化后，仍不能有效求解的问题是（）。 A．前（先）序线索二叉树中求前（先）序后继 B．中序线索二叉树中求中序后继C．中序线索二叉树中求中序前驱 D．后序线索二叉树中求后序后继 D 例16．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A 的左孩子的平衡因子为-1右孩子的平衡因子为0,则应作( ) 型调整以使其平衡。（平衡因子=左子树深度-右子树深度） A. LL （单向右旋） B. LR （先左后右双向旋转） C. RL （先右后左双向旋转） D. RR （单向左旋） B 例17．一棵非空的二叉树其先序序列和后序序列正好相反，画出这棵二叉树的形状。 先序序列是“根左右”后序序列是“左右根”，可见对任意结点，若至多只有左子女或至多只有右子女，均可使前序序列与后序序列相反，图示如下： 例18：已知二叉树结点结构如下： 用C语言表示 typedef struct BiNode｛ ElemType data; struct BiNode *lchild,*rchild; int val; ｝BiNode,*BiTree; 其中val域表示该结点的子孙（含孩子结点）的个数。开始时，val域值均为0，T为指向某二叉树根结点的指针。请写算法填写该二叉树中每个结点的val域。 递归算法如下： int writeVal(BiNode *root) {if(root==NULL) root->val=0; else if(root->lchild==NULL&&root->rchild==NULL) root->val=1; else root->val=writeVal(root->lchild)+writeVal(root->rchild); return root->val; } 例19．编写一个算法，将指针S所指的结点插入到根结点指针为T的二叉排序树中，若已存在则不再插入返回0；否则返回1。（递归的算法见教材） int Insert_BST( BiTree &T, BiTNode S ) { BiTree p, q; //p指向当前访问的结点 if(!T) T=S; else {p=T; while ( p ) {q = p; //q指向p结点的双亲结点 if (S->data.key < p->data.key) p = p->lchild; else if(S->data.key > p->data.key) p = p->rchild; else p=NULL; } if (S->data.key == q->data.key) return 0; if (S->data.key < q->data.key) q->lchild = S; else q->rchild = S; } return 1; } 例20．编写一个算法，计算平衡二叉树中所有结点的平衡因子 解：计算一个结点＊bt的bf的值递归模型如下： f(bt): bt->bf不存在当bt==NULL f(bt): bt->bf=0 当bt->lchild==NULL&&bt->rchild=NULL f(bt): bt->bf=bt的右子树的高度－左子树的高度其它情况 可选用先序的方式统计出各个结点的平衡因子 如何求高度呢？递归模型如下： f(bt): ０不存在当bt==NULL f(bt): １当bt->lchild==NULL&&bt->rchild=NULL f(bt):bt的左子树和右子树的高度的最大值＋１其它情况 int Height(BSTNode *bt){//求树的高度 int max1,max2; if(bt==NULL) return 0; else if(bt->lchild==NULL&&bt->rchild=NULL) return 1; else{ max1=Height(bt->lchild); max2=Height(bt->rchild); return max1>max2?max1+1:max2+1; } } void Countbf(BSTNode *&bt){ //求所有结点的bf if(bt!=NULL){ if(bt->lchild==NULL&&bt->rchild=NULL){ bf->bf=0; } else{ Countbf(bt->lchild); Countbf(bt->rchild); bt->bf= Height(bt->rchild)-Height(bt->lchild); } } } 实质上可以将上面求bf和求高度合二为一。 int Countbf1(BSTNode *&bt){//求所有结点的bf,返回对应结点高度值 int max1,max2; if(bt==NULL) return 0; if(bt->lchild==NULL&&bt->rchild=NULL){ bf->bf=0; return1; } else{ max1=Height(bt->lchild); max2=Height(bt->rchild); bt->bf= max2-max1; return max1>max2?max1+1:max2+1; } } 例21．设给出一段报文：CAST CAST SAT AT A TASA；字符集合是{ C, A, S, T }，各个字符出现的频度(次数)是W＝{ 2, 7, 4, 5 }；试设计赫夫曼编码，画出赫夫曼树。若给每个字符以等长编码A : 00 T : 10 C : 01 S : 11；试说明赫夫曼编码比此方案的优越之处。(编码最短) 解答见ppt 练习 1．设计一个算法，删除该二叉树，释放所有结点 2．设计一算法判断二叉链表存储的二叉树是否结构对称（左右子树结点结构对称相同）3．试写出复制一棵二叉树的算法。二叉树采用标准链接结构。 4．习题六编程（除打星号的部分） 5. 设计一个算法，寻找二叉树中满足特定数值x的第一个结点(相应的变形：寻找最小值，寻找父结点，寻找兄弟) 6. 设计一个算法，统计二叉树中满足特定数值x结点的个数（相应的变形：统计度为0，1，2的结点） 第七章图 1.图的定义、基本概念： B 2.图的存储方式：邻接矩阵和邻接表 A 3.图的遍历深度优先和广度优先 A 4.图的连通性和生成树B 带权图的最小生成树及算法 B 5.图的最短路径问题 B 6.拓扑排序、AOE网中的关键路径 B 本章重点：熟悉邻接矩阵和邻接表的表示方法，学会编写遍历算法深度优先和广度优先遍历算法以及一些遍历算法的应用。请仔细复习。 本章难点：图的一些算法（如最小生成树、最短路径、关键路径；这部分重在理解算法思想和设计过程） 例22．将邻接矩阵g装换为邻接表G (邻接表的表示方法) void MatToList(MGragh g,ALGLink &G){ int i,j, N=g.n;//N表示顶点数 ArcNode *p; G=(ALGraph*)malloc(sizeof(ALGraph)); for(i=0;i G->vertices[i].data=g.vexs[i]; G->vertices[i].firstedge=NULL; } for(i=0;i for(j=N-1;j>=0;j--)//对第i个顶点进行建立链表（由后向前添加） if(g.edges[i][j]!=0){ p=(ArcNode *)malloc(sizeof(ArcNode));//新建结点 p->adjvex=j; p->info=g.edges[i][j];//存放边的权值 p->next=G->vertices[i].firstedge;//前插 G->vertices[i].firstedge=p; } G->n=N; G->e=g.e; } 例23．试利用深度优先遍历DFS判断该图（在邻接表存储下）是否是连通的，若是连通的返回１，若是不连通的返回图的连通分量个数，空图则返回０。(图的遍历) int visted[MAXNUM]; //全局数组 void DFS (ALGraph* G, int i){/*以Vi为出发点对邻接表图进行DFS */ ArcNode *p; printf("visit data:%d\n",G->vertices[i].data);//访问顶点Vi visited[i]=1; //标记Vi已访问，标志为１ p= G->vertices[i].firstarc; //取Vi边表的头指针 while(p) { //依次搜索Vi的邻接点Vj， if (!visited[p->adjvex]) //若Vj尚未访问，则以Vj为出发点向纵深搜索 DFS (G,p->adjvex); p=p->next; } } /*判断无向图是否连通，若连通返回1*/ int Connects(ALGraph*G){ int i,flag=1; //flag为标记是否连通 for (i=0;i visited[i]=0 ; //标志向量visted[]初始化，标志为０DFS(g,0); for (i=0;i if (visited[i]==0) { //还有vi未访问过，修改标记flag量 flag=0;break; } return flag; } 例24．下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（ 1 ），下面步骤重复n-1次: a：（ 2 ）；b：（ 3 ）；最后：（ 4 ）。 （1）．A．VT，ET为空 B．VT为所有顶点，ET为空 C．VT为网中任意一点，ET为空 D．VT为空，ET为网中所有边（2）．A. 选i属于VT，j不属于VT，且（i，j）上的权最小 B．选i属于VT，j不属于VT，且（i，j）上的权最大 C．选i不属于VT，j不属于VT，且（i，j）上的权最小 D．选i不属于VT，j不属于VT，且（i，j）上的权最大 （3）．A．顶点i加入VT，（i,j）加入ET B. 顶点j加入VT，（i,j）加入ET C. 顶点j加入VT，（i,j）从ET中删去 D．顶点i,j加入VT，（i,j）加入ET （4）．A．ET 中为最小生成树 B．不在ET中的边构成最小生成树 C．ET中有n-1条边时为生成树，否则无解 D．ET中无回路时，为生成树，否则无解 C A B A 例25．P182 算法7.12（思考：用邻接矩阵存储怎么实现？） 练习 1.假设有向图以邻接表存储，计算Vi顶点的出度和入度。 2.在有向无环图中，试利用深度优先遍历DFS求出一个拓扑排序序列。 提示：由某点出发进行深度优先遍历，退出DFS函数调用时记录此时顶点序号，最先退出DFS函数的顶点是拓扑序列中的最后一个顶点，依次下去…..得到一个逆向拓扑有序序列；再将此顶点序号反向输出即可。 3.设计一个深度优先搜索算法，以判断用邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj（i≠j）的路径。 第八章查找 基本概念 C 静态查找表中常用的方法：顺序查找、折半查找、分块查找（分别适用于一般、有序、分块有序的表）相应算法和性能分析 A 动态查找表：二叉排序树的建立、查找、删除；A 二叉平衡树Ｂ 哈希表：哈希函数的构造和冲突处理方法Ｂ 本章重点：查找树的建立和查找（含静态折半查找、动态查找树）、哈希函数和冲突方法 本章难点：二叉排序树删除；平衡排序树的插入 例26．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为________。 6,9,11,12 例27．设散列表为HT [0..12],即表的大小为m=13。现采用双散列法解决冲突。散列函数和再散列函数分别为： H0(key)=key % 13; 注:%是求余数运算(=mod) H i=(H i-1+REV(key+1)%11+1) % 13; i=1,2,3,…,m-1 其中，函数REV（x）表示颠倒10进制数x的各位，如REV（37）=73，REV（7）=7等。若 插入的关键码序列为(2,8,31,20,19,18,53,27)。 (1)试画出插入这8个关键码后的散列表；(2)计算搜索成功的平均搜索长度ASL。(1） （2）ASL suss =11/8 第九章内排序 稳定/不稳定排序，内排序和外排序 C 插入排序方法：直接插入排序、折半插入排序、希尔插入排序算法与性能分析 A 交换排序方法：冒泡排序、快速排序 A 选择排序方法：简单选择排序、堆排序 A 二路归并排序、基数排序 B 本章重点：各种排序方法的实现、性能比较与选择 例28.某内排序方法的稳定性是指( )。 A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法 D．以上都不对 B 例29. 对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。 A. 选择 B. 快速 C. 希尔 D. 冒泡 若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的是（）排序。 A．选择 B. 堆 C. 直接插入 D. 冒泡 C C 例30. 有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( )（按递增序）。 A．下面的B，C，D都不对。 B．9，7，8，4，-1，7，15，20 C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20 A 说明：请针对性的仔细看书和ppt的内容；另外一些经典算法的时间复杂度分析应该不要忽略。 A类在所有的题型中体现（要求：熟练掌握）； B类在选择、填空、简答中体现（要求：理解）； C类在选择、填空中体现（要求：了解）。 一、数据管理的发展阶段 1、人工管理阶段 2、文件系统阶段 3、数据库管理阶段 注意了解各阶段的背景和特点 二、数据库系统的特点 1、面向全组织的复杂的数据结构 2、数据的冗余度小，易扩充 3、具有较高的数据和程序的独立性：数据独立性 数据的物理独立性 数据的逻辑独立性 三、数据结构模型三要素 1、数据结构 2、数据操作 3、数据的约束性条件 四、数据模型反映实体间的关系 1、一对一的联系(1：1) 2、一对多的联系(1：N) 3、多对多的联系(M：N) 五、数据模型： 是数据库系统中用于提供信息表示和操作手段的形式构架。 数据库结构的基础就是数据模型。数据模型是描述数据(数据结构)、数据之间的联系、数据语义即数据操作，以及一致性(完整性)约束的概念工具的集合。 概念数据模型：按用户的观点来对数据和信息建模。ER模型 结构数据模型：从计算机实现的观点来对数据建模。层次、网状模型、关系 六、数据模型的类型和特点 1、层次模型： 优点：结构简单，易于实现 缺点：支持的联系种类太少，只支持二元一对多联系 数据操纵不方便，子结点的存取只能通过父结点来进行 2、网状模型： 优点：能够更为直接的描述世界，结点之间可以有很多联系 具有良好的性能，存取效率高 缺点：结构比较复杂 网状模型的DDL、DML复杂，并且嵌入某一种高级语言，不易掌握，不易使用 3、关系模型： 特点：关系模型的概念单一；（定义、运算） 关系必须是规范化关系； 在关系模型中，用户对数据的检索操作不过是从原来的表中得到一张新的表。 优点：简单，表的概念直观，用户易理解。 非过程化的数据请求，数据请求可以不指明路径。 数据独立性，用户只需提出“做什么”，无须说明“怎么做”。 坚实的理论基础。 缺点：由于存储路径对用户透明，存储效率往往不如非关系数据模型 4、面向对象模型 5、对象关系模型 七、三个模式和二级映像 1、外模式(Sub-Schema)：用户的数据视图。是数据的局部逻辑结构，模式的子集。 2、模式(Schema)：所有用户的公共数据视图。是数据库中全体数据的全局逻辑结构和特性的描述。 3、内模式(Storage Schema)：又称存储模式。数据的物理结构及存储方式。 4、外模式/模式映象：定义某一个外模式和模式之间的对应关系，映象定义通常包含在各外模式中。当模式改变时，修改此映象，使外模式保持不变，从而应用程序可以保持不变，称为逻辑独立性。 5、模式/内模式映象：定义数据逻辑结构与存储结构之间的对应关系。存储结构改变时，修改此映象，使模式保持不变，从而应用程序可以保持不变，称为物理独立性。 八、数据视图 数据库管理系统的一个主要作用就是隐藏关于数据存储和维护的某些细节，而为用户提供数据在不同层次上的抽象视图，即不同的使用者从不同的角度去观察数据库中的数据所得到的结果—数据抽象。 九、规范化 1、几个概念 候选码（候选关键字）：如果一个属性（组）能惟一标识元组，且又不含有其余的属性，那么这个属性（组）称为关系的一个候选码(候选关键字)。 码（主码、主键、主关键字）：从候选码中选择一个唯一地标识一个元组候选码作为码 主属性：任何一个候选码中的属性（字段） 非主属性：除了候选码中的属性 外码：关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码，简称外码。 2、函数依赖 （1）设R(U)是一个属性集U上的关系模式，X和Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称“X函数确定Y”或“Y函数依赖于X”，记作X→Y。X称为这个函数依赖的决定属性集(Determinant)。Y=f(x) 一、解答题（满分3０分，每小题5分) 1. 怎样理解数据挖掘和知识发现的关系?请详细阐述之 首先从数据源中抽取感兴趣的数据，并把它组织成适合挖掘的数据组织形式;然后,调用相应的算法生成所需的知识;最后对生成的知识模式进行评估，并把有价值的知识集成到企业的智能系统中。 知识发现是一个指出数据中有效、崭新、潜在的、有价值的、一个不可忽视的流程，其最终目标是掌握数据的模式。流程步骤:先理解要应用的领域、熟悉相关知识，接着建立目标数据集，并专注所选择的数据子集;再作数据预处理，剔除错误或不一致的数据；然后进行数据简化与转换工作；再通过数据挖掘的技术程序成为模式、做回归分析或找出分类模型；最后经过解释和评价成为有用的信息。 2.时间序列数据挖掘的方法有哪些，请详细阐述之 时间序列数据挖掘的方法有: １)、确定性时间序列预测方法:对于平稳变化特征的时间序列来说，假设未来行为与现在的行为有关，利用属性现在的值预测将来的值是可行的。例如，要预测下周某种商品的销售额，可以用最近一段时间的实际销售量来建立预测模型。 ２）、随机时间序列预测方法：通过建立随机模型,对随机时间序列进行分析,可以预测未来值。若时间序列是平稳的,可以用自回归(Auto Ｒegressiｖe，简称AR)模型、移动回归模型(Ｍovｉng Ａveｒage,简称ＭＡ）或自回归移动平均(Aｕto Regrｅssive Moｖiｎg Aｖeraｇe，简称AＲMＡ)模型进行分析预测。 3)、其他方法:可用于时间序列预测的方法很多,其中比较成功的是神经网络。由于大量的时间序列是非平稳的,因此特征参数和数据分布随着时间的推移而变化。假如通过对某段历史数据的训练，通过数学统计模型估计神经网络的各层权重参数初值，就可能建立神经网络预测模型,用于时间序列的预测。 近几年交大结力真题分析~（个人总结）一：平面体系的几何组成分析，经常与桁架一起出题，顺便求其内力 二：已知受力，绘制弯矩剪力图 三：静定结构位移计算，一般加有弹簧或者移动支座四：力法，一般都是对称的图形，让你利用对称性五：位移法，还是对称，一般都有条黑线（EI无限大），难点就在于刚体只能平动和转动，而转动的时候会引起转角……还得靠你自己去练习，掌握了一点都不难。 六：影响线，不多说了，送分题 七：直接画出某超静定结构的内力图，表面上是画图，其实是多次利用力矩分配法，对刚结点的弯矩多次分配，画出简图，看似容易的题，其实是得分率最低的题，因此，大家必须多练习，熟练掌握力矩分配法！ 好多欲考土建的研友都纠结与结构力学该如何复习，下面我将自己的经历写下来，希望对土建人有所帮助，尤其是跨考土建的同学。 一、谈谈跨考土建。 我是跨考土建，而且跨度较大，之前只学过材料力学。我想考的专业要求是结构力学，对于这个没接触过的学科真的有些发憷，但是我觉得这不是问题，各位应该有同样的感觉吧——本科课程都是一周就可以突击考试，上课也不听，所以自学完全可以达到预期效果，只是付出要多一些。 二、结构力学的学习 接触一门从未有印象的学科，克服心理上的障碍最重要，当时把指定书目（李廉锟版）结构力学认真学了一遍，发现什么都不会，例题勉强看的懂，课后习题干脆都不会，我也想过是否继续，为了心仪的专业，就豁出去了。第一遍学校课本用了2个月，期间困难很大，到本校的土木学院找老师帮忙，结构力学老师居然退休了。。。我靠，整个学校没有结构力学老师，我日！没办法，硬头皮自学。 6月份时发生了一个转折点，那就是选到了一遍优秀的练习册。我当时想买一本练习册， 第1章数据库系统概述 1.数据库的概念 1）数据库是存储在计算机存储设备上的: 数据库是存在于计算机存储设备上的一个或多个(数据库)文件组成的统一体，是可感知的数据库形体。 2）数据库是按一定的组织方式存储在一起的：数据库中的数据是 以结构化的形式存储的，这种结构化形式实质上就是数据库的数据模型，是不可感知的数据库形体。 3）数据库是相关的数据集合：数据库中的数据既有某特定应用领域涉及的各种基本数据，也有反映这些数据之间联系的数据，也是不可感知的数据库形体之一。 DBMS的概念 数据库管理系统（DBMS）是建立、管理和维护数据库的软件系统，是一种 位于应用软件和操作系统之间，实现数据库管理功能的系统软件。 2.DBMS的主要功能 定义、操纵、控制、维护数据库并有通信功能 3.数据库应用系统概念成 以计算机为开发和应用平台， 以OS、DBMS、某种程序语言和实用程序等为软件环境， 以某一应用领域的数据管理需求为应用背景， 采用数据库设计技术建立的一个可实际运行的， 按照数据库方法存储和维护数据的， 并为用户提供数据支持和管理功能的应用软件系统。 4.三个世界对数据的描述 现实世界是存在于人们头脑之外的客观世界。可狭义地将现实世界看作为各个事物、各个现象、各个单位的实际情况。 计算机世界——数据世界对数据和信息的处理 信息世界是现实世界在人们头脑中的反映和解释，是现实世界的概念化。 5.数据模型的概念及组成 数据模型是现实世界中的各种事物及各事物之间的联系用数据及数据间的联系来表示的一种方法。一个数据库的数据模型实际上给出了在计算机系统上进行描述和动态模拟现实世界信息结构及其变化的方法。 是一组面向计算机的概念集合， 由数据结构 、数据操作 、数据约束三部分组成 6.层次模型、是一种用树型（层次）结构来组织数据的数据模型。 树中的每个结点代表一种记录类型。 网状模型（1）至少有一个结点多于一个双亲结点； （2）至少有一个结点无双亲结点。 一、填空题 1.Web挖掘可分为、和3大类。 2.数据仓库需要统一数据源，包括统一、统一、统一和统一数据特征 4个方面。 3.数据分割通常按时间、、、以及组合方法进行。 4.噪声数据处理的方法主要有、和。 5.数值归约的常用方法有、、、和对数模型等。 6.评价关联规则的2个主要指标是和。 7.多维数据集通常采用或雪花型架构，以表为中心，连接多个表。 8.决策树是用作为结点，用作为分支的树结构。 9.关联可分为简单关联、和。 10.B P神经网络的作用函数通常为区间的。 11.数据挖掘的过程主要包括确定业务对象、、、及知识同化等几个步 骤。 12.数据挖掘技术主要涉及、和3个技术领域。 13.数据挖掘的主要功能包括、、、、趋势分析、孤立点分析和偏 差分析7个方面。 14.人工神经网络具有和等特点，其结构模型包括、和自组织网络 3种。 15.数据仓库数据的4个基本特征是、、非易失、随时间变化。 16.数据仓库的数据通常划分为、、和等几个级别。 17.数据预处理的主要内容(方法)包括、、和数据归约等。 18.平滑分箱数据的方法主要有、和。 19.数据挖掘发现知识的类型主要有广义知识、、、和偏差型知识五种。 20.O LAP的数据组织方式主要有和两种。 21.常见的OLAP多维数据分析包括、、和旋转等操作。 22.传统的决策支持系统是以和驱动，而新决策支持系统则是以、建 立在和技术之上。 23.O LAP的数据组织方式主要有和2种。 24.S QL Server2000的OLAP组件叫，OLAP操作窗口叫。 25.B P神经网络由、以及一或多个结点组成。 26.遗传算法包括、、3个基本算子。 27.聚类分析的数据通常可分为区间标度变量、、、、序数型以及混合 类型等。 28.聚类分析中最常用的距离计算公式有、、等。 29.基于划分的聚类算法有和。 第一章 数据库系统概述 数据库的基本概念：DB、DBMS、DBS、DBA 数据管理的发展:人工管理、文件系统和数据库系统 数据库管理系统功能数据库定义功能；数据组织、存储和管理；数据操纵功能。 据库事务和运行管理；数据库的建立和维护功能。 数据库系统的结构数据库系统三级模式结构：模式、内模式和外模式 数据库系统的三级模式结构 模式（逻辑模式） 数据库中全体数据的逻辑结构和特征的描述；所有用户的公共数据视图，综合了所有用户的需求； 一个数据库只有一个模式 内模式（存储模式）：是数据物理结构和存储方式的描述；是数据在数据库内部的表示方式 一个数据库只有一个内模式 外模式（子模式或用户模式）：数据库用户使用的局部数据的逻辑结构和特征的描述 数据库用户的数据视图，是与某一应用有关的数据的逻辑表示 一个数据库可以有多个外模式。 数据库系统的二级映象 三级模式是对数据的三个抽象级别，二级映象在DBMS内部实现这三个抽象层次的联系和转换 外模式／模式映象 1. 定义外模式与模式之间的对应关系 2. 保证数据的逻辑独立性 模式／内模式映象 1. 定义了数据全局逻辑结构与存储结构之间的对应关系。 2. 保证数据的物理独立性 数据库系统的特点数据结构化数据的共享性高，冗余度低，易扩充数据独立性高 数据由DBMS统一管理和控制 数据模型的分两类：概念模型、逻辑模型和物理模型 数据模型的三要素：数据结构、数据操作、数据的完整性约束 三种主要数据模型：关系模型、层次模型、网状模型 第二章 关系模型由关系数据结构、关系操作和关系完整性约束三部分组成。 关系数据结构 关系二维表，属性是列，元组是行 关系模式对关系的描述R(U,F) 关系数据库关系的集合 关系的码 候选码（CK）关系中能唯一标识一个元组的属性组，称为该关系的候选码 简单情况: 候选码只包含一个属性。 极端情况: 关系的所有属性是关系模式的候选码，称为全码（All-key） 主码（Pk）若一个关系有多个候选码，则选定其中一个为主码 候选码的诸属性称为主属性。 不包含在任何侯选码中的属性称为非主属性。 外码（FK）设F是关系R的一个或一组属性，但不是关系R的码。如果F与关系S的主码Ks相对应，则称F是关系R的外码 关系R称为参照关系关系S称为被参照关系 选修关系的“学号” 与学生关系的主码“学号”相对应 一、何为分布式数据库系统？一个分布式数据库系统有哪些特点？ 答案：分布式数据库系统通俗地说，是物理上分散而逻辑上集中的数据库系统。分布式数据库系统使用计算机网络将地理位置分散而管理和控制又需要不同程度集中的多个逻辑单位连接起来，共同组成一个统一的数据库系统。因此，分布式数据库系统可以看成是计算机网络与数据库系统的有机结合。一个分布式数据库系统具有如下特点： 物理分布性，即分布式数据库系统中的数据不是存储在一个站点上，而是分散存储在由计算机网络连接起来的多个站点上，而且这种分散存储对用户来说是感觉不到的。 逻辑整体性，分布式数据库系统中的数据物理上是分散在各个站点中，但这些分散的数据逻辑上却构成一个整体，它们被分布式数据库系统的所有用户共享，并由一个分布式数据库管理系统统一管理，它使得“分布”对用户来说是透明的。 站点自治性，也称为场地自治性，各站点上的数据由本地的DBMS管理，具有自治处理能力，完成本站点的应用，这是分布式数据库系统与多处理机系统的区别。 另外，由以上三个分布式数据库系统的基本特点还可以导出它的其它特点，即：数据分布透明性、集中与自治相结合的控制机制、存在适当的数据冗余度、事务管理的分布性。 二、简述分布式数据库的模式结构和各层模式的概念。 分布式数据库是多层的，国分为四层： 全局外层：全局外模式，是全局应用的用户视图，所以也称全局试图。它为全局概念模式的子集，表示全局应用所涉及的数据库部分。 全局概念层：全局概念模式、分片模式和分配模式 全局概念模式描述分布式数据库中全局数据的逻辑结构和数据特性，与集中式数据库中的概念模式是集中式数据库的概念视图一样，全局概念模式是分布式数据库的全局概念视图。分片模式用于说明如何放置数据库的分片部分。分布式数据库可划分为许多逻辑片，定义片段、片段与概念模式之间的映射关系。分配模式是根据选定的数据分布策略，定义各片段的物理存放站点。 局部概念层：局部概念模式是全局概念模式的子集。局部层：局部模式 局部模式是分布式数据库中关于物理数据库的描述，类同集中式数据库中的模式，但其描述的容不仅包含只局部于本站点的数据的存储描述，还包括全局数据在本站点的存储描述。 三、简述分布式数据库系统中的分布透明性，举例说明分布式数据库简单查询的 各级分布透明性问题。 分布式数据库中的分布透明性即分布独立性，指用户或用户程序使用分布式数据库如同使用集中式数据库那样，不必关心全局数据的分布情况，包括全局数据的逻辑分片情况、逻辑片段的站点位置分配情况，以及各站点上数据库的数据模型等。即全局数据的逻辑分片、片段的物理位置分配，各站点数据库的数据模型等情况对用户和用户程序透明。 数据挖掘考试题 LG GROUP system office room 【LGA16H-LGYY-LGUA8Q8-LGA162】 数据挖掘考试题 一．选择题 1. 当不知道数据所带标签时，可以使用哪种技术促使带同类标签的数据与带其他标签的数据相分离( ) A.分类 B.聚类 C.关联分析 D.主成分分析 2. ( )将两个簇的邻近度定义为不同簇的所有点对邻近度的平均值，它是一种凝聚层次聚类技术。 (单链) (全链) C.组平均方法 3.数据挖掘的经典案例“啤酒与尿布试验”最主要是应用了( )数据挖掘方法。 A 分类 B 预测 C关联规则分析 D聚类 4.关于K均值和DBSCAN的比较，以下说法不正确的是( ) 均值丢弃被它识别为噪声的对象，而DBSCAN一般聚类所有对象。 均值使用簇的基于原型的概念，DBSCAN使用基于密度的概念。 均值很难处理非球形的簇和不同大小的簇，DBSCAN可以处理不同大小和不同形状的簇 均值可以发现不是明显分离的簇，即便簇有重叠也可以发现，但是DBSCAN会合并有重叠的簇 5.下列关于Ward’s Method说法错误的是：( ) A.对噪声点和离群点敏感度比较小 B.擅长处理球状的簇 C.对于Ward方法，两个簇的邻近度定义为两个簇合并时导致的平方误差 D.当两个点之间的邻近度取它们之间距离的平方时，Ward方法与组平均非常相似 6.下列关于层次聚类存在的问题说法正确的是：( ) A.具有全局优化目标函数 B.Group Average擅长处理球状的簇 C.可以处理不同大小簇的能力 D.Max对噪声点和离群点很敏感 7.下列关于凝聚层次聚类的说法中，说法错误的事：( ) A.一旦两个簇合并，该操作就不能撤销 B.算法的终止条件是仅剩下一个簇 C.空间复杂度为()2m O D.具有全局优化目标函数 8.规则{牛奶，尿布}→{啤酒}的支持度和置信度分别为：( ) 9.下列( )是属于分裂层次聚类的方法。 Average 10.对下图数据进行凝聚聚类操作，簇间相似度使用MAX计算，第二步是哪两个簇合并：( ) A.在{3}和{l,2}合并 B.{3}和{4,5}合并 C.{2,3}和{4,5}合并 D. {2,3}和{4,5}形成簇和{3}合并 二．填空题： 1.属性包括的四种类型：、、、。 2.是两个簇的邻近度定义为不同簇的所有点对邻近度的平均值。 3. 基本凝聚层次聚类算法空间复杂度，时间复杂度，如果某个簇到其他所有簇的距离存放在一个有序表或堆中，层次聚类所需要的时间复杂度将为。 4. 聚类中，定义簇间的相似度的方法有（写出四 个）：、、、。 5. 层次聚类技术是第二类重要的聚类方法。两种层次聚类的基本方 法：、。 6. 组平均是一种界于和之间的折中方法。 建筑物和工程设施中承受、传递荷载而起骨架作用的部分称为工程结构，简称为结构。 从几何角度来看，结构可分为三类，分别为：杆件结构、板壳结构、实体结构。 结构力学中所有的计算方法都应考虑以下三方面条件： ①力系的平衡条件或运动条件。 ②变形的几何连续条件。 ③应力与变形间的物理条件（或称为本构方程）。 结点分为：铰结点、刚结点。 铰结点：可以传递力，但不能传递力矩。 刚结点：既可以传递力，也可以传递力矩。 支座按其受力特质分为：滚轴支座、铰支座、定向支座、固定支座。 在结构计算中，为了简化，对组成各杆件的材料一般都假设为：连续的、均匀的、各向同性的、完全弹性或弹塑性的。 荷载是主动作用于结构的外力。 狭义荷载：结构的自重、加于结构的水压力和土压力。 广义荷载：温度变化、基础沉降、材料收缩。 根据荷载作用时间的久暂，可以分为：恒载、活载。 根据荷载作用的性质，可以分为：静力荷载、动力荷载。 结构的几何构造分析 在几何构造分析中，不考虑这种由于材料的应变所产生的变形。 杆件体系可分为两类： 几何不变体系------在不考虑材料应变的条件下，体系的位置和形状是不能改变的。 几何可变体系------在不考虑材料应变的条件下，体系的位置和形状是可以改变的。 自由度：一个体系自由度的个数，等于这个体系运动时可以独立改变的坐标的个数。 一点在平面内有两个自由度（横纵坐标）。 一个刚片在平面内有三个自由度（横纵坐标及转角）。 凡是自由度的个数大于零的体系都是几何可变体系。 一个支杆（链杆）相当于一个约束。可以减少一个自由度。 一个单铰（只连接两个刚片的铰）相当于两个约束。可以减少两个自由度。一个单刚结（刚性结合）相当于三个约束，可以减少三个自由度。 如果在一个体系中增加一个约束，而体系的自由度并不因而减少，则此约束称为多余约束。增加了约束，计算自由度会减少。因为w=s-n . 瞬变体系：本来是几何可变、经微小位移后又成为几何不变的体系称为瞬变体系。 实铰：两个刚片（地基也算一个刚片），如果用两根链杆给链接上，并且两根链杆能在其中一个刚片上交于一点，所构成的铰就叫实铰。 瞬铰：两个刚片（地基也算一个刚片），如果用两根链杆给链接上，两根链杆在两刚片间没有交于一点，而是在两根链杆的延长线上交于一点，从瞬时微小运动来看，这就是瞬铰了。两根链杆所起的约束作用等效于在链杆交点处上面放了一个单铰的约束作用。通常所起作用为转动。 截面上应力沿杆轴切线方向的合力，称为轴力。轴力以拉力为正。 截面上应力沿杆轴法线方向的合力称为剪力。剪力以绕微段隔离体顺时针转者为正。 截面上应力对截面形心的力矩称为弯矩。在水平杆件中，当弯矩使杆件下部受拉时，弯矩为正。 作轴力图和剪力图要注明正负号。作弯矩图时，规定弯矩图的纵坐标应画在受拉纤维一边，不注明正负号。 通常在桁架的内力计算中，采用下列假定： ①桁架的结点都是光滑的铰结点； ②各杆的轴线都是直线并通过铰的中心； ③荷载和支座反力都作用在结点上。 根据几何构造的特点，静定平面桁架可分为三类：简单桁架，联合桁架，复杂桁架。 在单杆的前提下，当结点无荷载作用时，单杆的内力必为零。此单杆称为零杆。 由链杆和梁式杆组成的结构，称为组合结构。 链杆只受轴力作用；梁式杆除受轴力作用外，还受弯矩和剪力作用。 三铰拱受力特点： ①在竖向荷载作用下，梁没有水平反力，而拱则有推力。 ②由于推力的存在，三铰拱截面上的弯矩比简支梁的弯矩小。弯矩的降低，使拱能更充分地发挥材料的作用。 ③在竖向荷载作用下，梁的截面内没有轴力，而拱的截面内轴力较大，且一般为压力。 合理拱轴线：在固定荷载作用下使拱处于无弯矩、无剪力、而只有轴力作用的轴线。 合理轴线：通常指具有不同高跨比的一组抛物线。 影响线 内力影响线：表示单位移动荷载作用下内力变化规律的图形。无论在剪力、弯矩、支座反力的影响线图中都需要标上正负号。影响线是研究移动荷载最不利位置和计算内力最大值（或最小值）的基本工具。 荷载：特定单位移动荷载P=1 固定、任意荷载最不利位置：如果荷载移动到某个位置，使某量Z达到最大值，则此荷载位置称为最不利位置。 影响线的一个重要作用，就是用来确定荷载的最不利位置。 定出荷载最不利位置判断的一般原则是：应当把数量大、排列密的荷载放在影响线竖距较大的部位。 计算结构的位移目的有两个： ①一个目的是验算结构的刚度，即验算结构的位移是否超过允许的位移限值。 ②另一个目的是为超静定结构的内力分析打下基础。 产生位移的原因主要有下列三种： ①荷载作用②温度变化和材料胀缩③支座沉降和制造误差 一组力可以用一个符号P表示，相应的位移也可用一个符号Δ表示，这种夸大了的力和位移分别称为广义力和广义位移。 图乘法的应用条件：①杆段应是等截面直杆段。②两个图形中至少应有一个是直线，标距y0 应取自直线图中。 互等定理包括四个普遍定理：①功的互等定理②位移互等定理 ③反力互等定理④位移反力互等定理。 3、对称结构就是指： ①结构的几何形式和支承情况对某轴对称。 ②杆件截面和材料性质也对此轴对称。（因而杆件的截面刚度EI对此轴对称） 4、对称荷载：对称荷载绕对称轴对折后，左右两部分的荷载彼此重合（作用点相对应、数值相等、方向相同） 反对称荷载：反对称荷载绕对称轴对折后，左右两部分的荷载正好相反（作用点相对应、数值相等、方向相反） 超静定结构有一个重要特点，就是无荷载作用时，由于其他因素（如：支座移动、温度改变、材料收缩、制造误差）的作用也可以产生内力。 超静定结构：由于其他因素（如：支座移动、温度改变、材料收缩、制造误差）的作用可以产生位移也可以产生内力。 静定结构：由于其他因素（如：支座移动、温度改变、材料收缩、制造误差）的作用可以产生位移但不能产生内力。 力法：多余未知力静定结构变形协调（位移相等） 位移法：结构独立结点位移（角、线位移）超静定单杆（是用位移表示的）平衡方程 2、系数EAi /Li是使杆端产生单位位移时所需施加的杆端力，称为杆件的刚度系数。 体系的自由度指的是确定物体位置所需要的最少坐标数目。 拱的基本特点是在竖向荷载作用下会产生水平支座反力。 .静定结构的特性：（1）静定结构的全部约束反力与内力都可以用静力平衡方程求得。（2）温度变化、支座位移不引起静定结构的内力。3)当一个平衡力系作用在静定结构的某一自身几何不变的杆上时，静定结构只在该力系作用的杆段内产生内力。(4).作用在静定结构的某一自身为几何不变的杆 段上的某一荷载，若用在该段上的一个等效 力系来代替，则结构仅在该段上的内力发生 变化，其余部分内力不变。 1.平面杆件结构分类？ 梁、刚架、拱、桁架、组合结构。 2.请简述几何不变体系的俩刚片规则。 两刚片用一个铰和一根不通过该铰链中心的链杆或不全交于一点也不全平行的三根链杆相联，则组成的体系是几何不变的，并且没有多余约束。 3.请简述几何不变体系的三刚片规则。 三刚片用不共线的三个铰两两相联或六根链杆两两相联，则组成的体系是几何不变体系，且没有多余约束。 4.从几何组成分析上来看什么是静定结构，什么是超静定结构？(几何特征) 无多余约束的几何不变体系是静定结构，有多余约束的几何不变体系是超静定结构，有几个多余约束，即为几次超静定。 5.静定学角度分析说明什么是静定结构，什么是超静定结构？ 只需要利用静力平衡条件就能计算出结构全部支座反力和构件内力的结构称为静定结构；全部支座反力和构件内力不能只用静力平衡条件确定的结构称为超静定结构。 6.如何区别拱和曲梁 杆轴为曲线且在竖向荷载作用下能产生水平推力的结构，称为拱；杆轴为曲线，但在竖向荷载作用下无水平推力产生，称为曲梁。 7.合理拱轴的条件？ 在已知荷载作用下，如所选择的三铰拱轴线能使所有截面上的弯矩均等于零，则此拱轴线为合理拱轴线。 仅供学习与参考 《数据库原理与应用》复习提要 题型 填空题： 单项选择题： 判断题： 简答题： 模式设计： 论述题： 第一章绪论 一、知识点分类如下: 1. 需要了解的:数据管理技术的产生和发展过程、数据库系统的优点和好处、层次数据模型及网状数据模 型的基本概念、数据库系统的组成、DBA的职责、数据库技术的主要研究领域等。 2. 需要牢固掌握的：概念模型的基本概念及其主要建模方法——E－R方法;关系数据模型的相关概念、数 据库系统三级模式和两层映像的体系结构，数据库系统的逻辑独立性和物理独立性等。 3. 需要举一反三的：通过E-R方法描述现实世界的概念模型。 4. 难点：数据模型及数据库系统的体系结构。 二、具体内容 1．数据管理技术的发展阶段：人工管理阶段、文件系统阶段、数据库阶段，各阶段主要特点。 2．概念:数据、DB、DBMS、DBS、数据库系统 ３．数据模型 数据模型的概念：数据模型是现实世界数据特征的抽象。 数据模型的组成要素：数据结构、数据操作、数据完整性约束 常用数据模型：层次、网状、关系三种模型。上述三种模型各自的特点。 数据描述的三个领域：现实世界、信息世界和机器世界。 信息世界中的几个概念：实体(即客观存在可以相互区别的事物)、实体集(同类实体的集合)、属性(实体的特性)、码(唯一标识实体的属性(集))、域、联系。 机器世界中的四个概念：字段、记录、文件、键(主码)。 E-R图的设计: E-R图三要素：实体（型）、属性、联系 联系的种类：1:1、1:n、m:n 如何将E-R图转化成各种数据模型 ４．数据库的体系结构 三级结构模式：外模式、模式、内模式 模式也称为逻辑模式，是数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图(与数据模型相对应)。 外模式也称子模式(subschema)或用户模式，它是数据库用户(包括应用程序员和最终用户)能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。内模式也称存储模式(Storage Schema)，一个数据库只有一个内模式。它是数据物理结构和存储方式的描述，是数据在数据库内部的表示方式。 二级映象：模式/内模式、外模式/模式，二级映象保证了数据库系统中的数据能够具有较高的逻辑独立性和物理独立性。 第二章关系数据库 一、知识点分类如下: 数据挖掘考试题目——关联分析 一、10个选择 1.以下属于关联分析的是（） A．CPU性能预测B．购物篮分析 C．自动判断鸢尾花类别D．股票趋势建模 2.维克托?迈尔-舍恩伯格在《大数据时代：生活、工作与思维的大变革》一书中，持续强调了一个观点：大数据时代的到来，使我们无法人为地去发现数据中的奥妙，与此同时，我们更应该注重数据中的相关关系，而不是因果关系。其中，数据之间的相关关系可以通过以下哪个算法直接挖掘（） A．K-means B．Bayes Network C．C4.5 D．Apriori 3.置信度(confidence)是衡量兴趣度度量（）的指标。 A．简洁性B．确定性 C．实用性D．新颖性 4.Apriori算法的加速过程依赖于以下哪个策略（） A．抽样B．剪枝 C．缓冲D．并行 5.以下哪个会降低Apriori算法的挖掘效率（） A．支持度阈值增大B．项数减少 C．事务数减少D．减小硬盘读写速率 6.Apriori算法使用到以下哪些东东（） A．格结构、有向无环图B．二叉树、哈希树 C．格结构、哈希树D．多叉树、有向无环图 7.非频繁模式（） A．其置信度小于阈值B．令人不感兴趣 C．包含负模式和负相关模式D．对异常数据项敏感 8.对频繁项集、频繁闭项集、极大频繁项集的关系描述正确的是（）[注：分别以1、2、3代表之] A．3可以还原出无损的1 B．2可以还原出无损的1 C．3与2是完全等价的D．2与1是完全等价的 9.Hash tree在Apriori算法中所起的作用是（） A．存储数据B．查找 C．加速查找D．剪枝 10.以下不属于数据挖掘软件的是（） A．SPSS Modeler B．Weka C．Apache Spark D．Knime 二、10个填空 1.关联分析中表示关联关系的方法主要有：和。 2.关联规则的评价度量主要有：和。 3.关联规则挖掘的算法主要有：和。 4.购物篮分析中，数据是以的形式呈现。 5.一个项集满足最小支持度，我们称之为。 6.一个关联规则同时满足最小支持度和最小置信度，我们称之为。 文档 结构力学重难点复习资料 第二章结构的几何构成分析 1、首先必须深刻理解几个基本概念，这几个概念层层递进。 ●几何不变体系：不计材料应变情况下，体系的位置和形状不变。 在几何构成分析中与荷载无关，各个杆件都是刚体。 ●刚片：形状不变的物体，也就是刚体。 在几何构成分析中，刚片的选取非常重要，也非常灵活，可大可小，小至一根杆，大至地基基础，皆可视为刚片。 ●自由度：体系运动时可以独立改变的坐标的数目。 在平面，一点有2个自由度，一刚片有3个自由度。 ●约束：减少自由度的装置。 一根链杆（或链杆支座）相当于1个约束； 一个铰（或铰支座）相当于2个约束，注意两根链杆和一个铰在约束方面的功能完 全可等同，可根据几何构成分析的需要相互转换，另外注意瞬铰的概念，两根链杆 直接铰接在一点，该点可视为实铰，两根链杆延长后相交在一点，该点则是瞬铰，一个瞬铰也相当于2个约束，两根链杆若平行，瞬铰在平行方向的无穷远处； 一个刚结点（或固定端）相当于3个约束。 ●多余约束：增加一个约束，体系的自由度并不减少，该约束就是多余约束。 注意一个约束是否多余约束，必须视必要约束而定。只有必要约束确定后才能确定多余约束，不能直接说哪个约束是多余约束。 2、必须深刻理解几何不变体系的组成规律。 教材上列出4个规律，其实基本的规律只有一个，就是三角形规律，即小学数学就传授的“三角形是稳定的”。 片法则、三刚片法则中“三铰不共线”、“三链杆不互相平行或相交于一点”的条件，若不满足，则为瞬变体系。 3、给大家推荐几何构成分析的基本思路和步骤 ●若有基础，首先看基础以外部分与基础的联系数：等于3，则只分析基础以外部分， 若几何不变，则整体几何不变，若几何可变，则整体几何可变；不等于3，则须将 忠告：要认真看一看，否则连考试题目都看不懂。 15-16-1数据库复习 分数分布：1、简答；2、填空；3、问答----70分；///// 4、应用30分 答题须知：评分原则：没有错误，才可得分。简化的答案0分。 简单事实 （对应：简答and填空///分色对应于A卷和B卷） 数据库理论部分 *在系统分析阶段中，业务流程的分析结果一般用数据流图表示 * E-R模型转换成关系模型是在数据库设计阶段中的逻辑设计阶段。 *概念模型独立于DBMS *概念模型 概念模型可以看成是现实世界到机器世界的一个过渡的中间层次。概念模型是一种高度抽象的模型，与具体的数据模型无关。 *物理设计 在数据库设计的各个阶段中，与存储结构与存取方法有关的部分是物理设计。用户对性能的需求以及技术的具体发展都会对物理设计产生强烈的影响。 *A数据模型（B数据模型及其种类） 具有联系的相关数据按一定的方式组织排列，并构成一定的结构，这种结构即数据模型。常见的数据模型有层次模型、网状模型和关系模型。 *A数据库（B数据库的定义） 数据库是以—定的组织结构保存在辅助存储器（如：硬盘）中的数据的集合。数据的组织结构包含两个方面，一个是数据模型，另一个是在数据模型基础上所表达的逻辑相关性。 *A关系数据库（B关系数据库及其形态） 关系数据库是以关系模型为基本结构而形成的数据集合。关系数据库最终要建立在具体的关系数据库管理系统上，完成从逻辑结构到物理结构的转换。 *A逻辑设计（B逻辑设计及其特点） 在数据库设计中，将E-R图转换成关系数据模型的过程属于逻辑设计阶段。逻辑设计的特点是平台无关性或者跨平台性。（解释：ORACLE、SQL、ACCESS的关系模型是一致的） *A表关系（B数据表之间的关系） 关系数据库中的数据表既相对独立，又相互联系。一个表对应着一个关系且依从于一个主键而独立。表之间的关系则对应着现实世界中实体之间的联系。 分布式数据库技术在大数据中的应用 分布式数据库技术在大数据中的应用 摘要随着当前运营商对数据管理和应用需求的不断增加，分布式数据库技术得到极大的发展。在本文中首先对当前大数据环境下的分布式数据库技术进行介绍，然后分析分布式数据库技术在大数据中的具体应用。 关键词分布式数据库；数据管理；数据处理 中图分类号 TP3 文献标识码 A 文章编号 1674-6708（2016）165-0108-01 随着当前移动互联网技术的迅猛发展，数据的种类和数量呈现快速的增长，传统的处理方式逐渐的不能够适应当前的发展需要，基于此种背景下，分布式数据库技术需要得到更快的发展，以达到对大数据的存储、管理以及分析等处理要求。 1 大数据中发展分布式数据库的意义 在面对当前的大数据时代，传统的集中式数据库已经逐渐的不能够满足人们的使用要求，需要找到新的处理方式来进行更新，分布式数据库就是在这样的背景下逐渐的被发展和应用。分布式数据库在使用中有着许多传统集中式数据库不具备的优点：第一，分布式数据库有着极为强大的扩展能力，这是传统数据库所不具备的，在数据的存储方面表现出巨大的优势；第二，来自于成本上的优势。 在大数据中，如果仍旧采用原有的数据库，在进行扩容的时候，会花费大量的资金，使得成本上花费巨大，而且所取得的效果也是有限的。分布式数据库则只需要较少的资金就能够完成扩容处理，占据着特别大的优势[1]；第三，分布式数据库在用户上有着很大的优势，分布式数据库让人们对大数据的存储、分析和处理变得容易和快捷。 2 分布式数据库技术分析 在大数据中，分布式数据库技术得到极大的发展，也正是由于分布式数据库技术表现出来的先进性能，才使得分布式数据库得到广泛的使用。在分布式数据库中，其由很多个并行的处理单元组成，而且每个处理单元都是一个完整的系统，其中包括数据的存储，数据的分析等，对于每一个处理单元来说，其所处的位置和作用都是对等的，而且是相对独立的。混合存储技术：突破传统行存的限制，实现行列混合存储。该项技术对于分布式数据库的性能有着很大的提升，使得分布式数据库在运行速度和运行的灵活性上都有很大的提高。再就是智能索引技术，该种技术所占用的空间减少，并且能够很好的解决后面数据库慢的问题，不会对后面的索引数据造成影响[2]。除此之外，分布式数据库中还具有许多先进的技术，如并行处理技术、高效透明压缩技术等，都是传统数据库中所不具备 一、解答题（满分30分，每小题5分） 1. 怎样理解数据挖掘和知识发现的关系？请详细阐述之 首先从数据源中抽取感兴趣的数据，并把它组织成适合挖掘的数据组织形式；然后，调用相应的算法生成所需的知识；最后对生成的知识模式进行评估，并把有价值的知识集成到企业的智能系统中。 知识发现是一个指出数据中有效、崭新、潜在的、有价值的、一个不可忽视的流程，其最终目标是掌握数据的模式。流程步骤：先理解要应用的领域、熟悉相关知识，接着建立目标数据集，并专注所选择的数据子集；再作数据预处理，剔除错误或不一致的数据；然后进行数据简化与转换工作；再通过数据挖掘的技术程序成为模式、做回归分析或找出分类模型；最后经过解释和评价成为有用的信息。 2. 时间序列数据挖掘的方法有哪些，请详细阐述之 时间序列数据挖掘的方法有： 1）、确定性时间序列预测方法:对于平稳变化特征的时间序列来说，假设未来行为与现在的行为有关，利用属性现在的值预测将来的值是可行的。例如，要预测下周某种商品的销售额，可以用最近一段时间的实际销售量来建立预测模型。 2）、随机时间序列预测方法:通过建立随机模型，对随机时间序列进行分析，可以预测未来值。若时间序列是平稳的，可以用自回归(Auto Regressive，简称AR)模型、移动回归模型(Moving Average，简称MA)或自回归移动平均(Auto Regressive Moving Average，简称ARMA)模型进行分析预测。 3）、其他方法:可用于时间序列预测的方法很多，其中比较成功的是神经网络。由于大量的时间序列是非平稳的，因此特征参数和数据分布随着时间的推移而变化。假如通过对某段历史数据的训练，通过数学统计模型估计神经网络的各层权重参数初值，就可能建立神经网络预测模型，用于时间序列的预测。 基础知识 表3.2 Oracle数据类型 表3.3 XSB的表结构 操作表 创建表 CREATE TABLE [schema.] table_name ( column_namedatatype [DEFAULT expression] [column_constraint][,…n] 一、填空 分布式数据库系统按局部数据库管理系统的数据模型分类，可以分为和两类。 同构型DDBS 异构型DDBS 分布式数据库系统按全避控制系统类型分类，可以分为、 和三类。 全局控制集中型DDBS 全局控制分散型DDBS 全局控制可变型DDBS 分布式数据库是分布式数据库系统中各站点上数据库的逻辑集合，它由和组成。 应用数据库描述数据库 数据分片的三种基本方法是：、和三类。 水平分片垂直分片混合分片 《 分布式数据库中的数据分布策略有：、、 和四层。 集中式分割式复制式混合式 分布式数据库是多层模式结构，一般划分为、、 和四层。 全局外层全局概念层局部概念层局部内层 一个分布式数据库管理系统一般应包括、、 和四个基本功能模块。 查询处理模块完整性处理模块调度处理模块可靠性处理模块 分布透明性包括、和三个层次。 ， 分片透明性位置透明性局部数据模型透明性 分布式数据库系统的创建方法，大致可分为和两种。 组合法重构法 集中式数据库设计一般包括：需求分析，概念设计，逻辑设计和物理设计四个阶段，分布式数据库设计除了上述四个阶段外，还需增加一些个新的阶段，它位于和之间。 分布设计逻辑设计物理设计 水平分片的方法可归为和两种。 初级分片导出分片 DATAID-D相对于DATAID-1增加了和两个阶段。 分布要求分析分布设计 》 DATAID-D中的分布设计分成、、 和四个阶段。 分片设计非冗余分配冗余分配局部模式的重新构造 分布式查询优化的准则是。通信费用和响应时间最短 在分布式系统中，查询代价QC＝。I/O代价+CPU代价+通信代价 在分布式环境下，查询可分为、和三种类型。 局部查询远程查询全局查询 分布式查询处理可以分为、、和四层。 【 查询分解数据本地化全局优化局部优化一个分布式事务通常是由和组成。 主事务子事务 事务的四个特性是：、、和。原子性一致性隔离性耐久性 控制分布式事务所执行的控制模型有：、和。主从模型三角模型层次模型 分布式数据库系统中，通信故障可以分为和两种。 报文故障网络分割故障 事务恢复主要是依靠来实现的。 日志 , 并发控制机制可以为和两种类型。 悲观并发控制法乐观并发控制法 常用的基本封锁算法有：、、和。 简单的分布式封锁方法主站点封锁法主副本封锁法快照方法 预防死锁的方法有和两种类型。 非占先权方法占先权方法 检测分布式死锁的三种方法是、和。 集中式层次式分布式 二、[ 三、简答题 分布式数据库系统的特点是什么 答：物理分布性：数据不是存放在一个站点上 逻辑整体性：是与分散式数据库系统的区别 站点自治性：是与多处理机的系统的区别 数据分布透明性 集中与自治相结合 存在适当的数据冗余度 事务管理的分布性 / 分布式数据库中数据分片的规则是什么 答：（1）完备性原则：必须把全局关系的所有数据映射到各自片段中，绝不允许有属于全局关系的数据却不发球它的任何一个片段。空间数据库期末复习重点总结
《数据挖掘》试题与标准答案
结构力学复习要点教案资料
(完整word版)《数据库原理与应用》北师珠必备复习重点
数据挖掘考试题库【最新】
数据库系统概论复习要点
分布式大数据库系统复习题
数据挖掘考试题
结构力学知识点复习过程
数据库复习(重点)
最新数据挖掘考试题目——关联分析资料
结构力学重难点完美复习资料
数据库原理与应用复习重点讲述
分布式数据库技术在大数据中的应用复习过程
《数据挖掘》试题与答案
Oracle数据库期末复习知识点整理
分布式数据库系统_复习