数据结构复习提纲
第二部分复习提纲(不分题型)
1．数据的三个层次是数据、数据元素和数据项。
2．四种基本存储方式的特点？什么时候逻辑关系可以由存储地址表示？什么时候由指针表示？什么时候存储地址与结点内容有关系？
答：
◆顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。
◆链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。
◆索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
◆散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。
3．四种基本逻辑结构是什么？逻辑结构与存储结构是否一一对应？逻辑结构与计算机是否有关？
逻辑结构：
答：
4．运算、算法含义？谁定义在存储结构上？谁定义在逻辑结构上？
答：运算是在数据逻辑结构上定义的操作算法。
所谓算法（Algorithm）是对问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。
所谓算法复杂度：
T (n) = O(f(n))
称T (n) 为算法的渐近时间复杂度（Asymptotic Time Complexity）,简称时间复杂度。O是数量级的符号。
下面我们探讨一下如何估算算法的时间复杂度
算法= 控制结构+ 原操作（固有数据类型的操作）
算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间
算法的执行时间与原操作执行次数之和成正比
5．运算可分为加工型和＿＿＿。
5．数据结构一般包括三个方面内容：逻辑结构、储存结构和运算。
6．算法的复杂性与计算机是否有关？
7．算法正确与否一般是用理论证明还是用算例检验？
答：用算例须考虑所有情况，用理论需要严谨的数学证明。
9．时间复杂性一般考虑平均时间复杂性和最坏时间复杂性。
10．程序设计的实质是＿＿＿＿＿＿和＿＿＿＿＿＿。
11．将2100、log2n、nlog2n、n n、n2、2n、n!等按增长率从低到高排列是＿＿＿＿＿＿。
答：2100 1．线性表每个结点都有一个前趋和后继吗？ 答：开始结点只有一个后继，终端结点只有一个前趋。 2．头结点有何作用？ 3．链表结点的物理地址一定不连续吗？－连续与否都可 4．单链表插入、删除结点的一般过程？（指针修改情况） 如果插入在链表开头：New NewNode; NewNode->Next=Pointer; HEAD->Next=NewNode; 如果插入在链表中间：NewNode->Next=Pointer->Next; Pointer->Next=NewNode; 如果插入在链表末端：NewNode->Next=Pointer->Next; Pointer->Next=NewNode; 如果删除在链表开头： Head->Next=Pointer->Next; free(Pointer); 如果删除在链表中间： Back-〉Next=Pointer-〉Next; free(Pointer); 如果删除在链表末端： Back-〉Next=Pointer-〉Next; free(Pointer); 5．顺序表、单链表优点缺点？是否可以（按值、按序号）随机存取？顺序存取？ 答：链表的优点是空间动态分配，插入和删除时不需要移动数据，缺点是不能随机访问。 顺序表的优点是能熟记存取数据元素可以按值随机存储，存取速度快，缺点：插入、删除操作需移动数据。 6．顺序表插入、删除时是否总引起结点的移动？ 答：只有插入、删除在表末，不会引起结点的移动。 7．分别对有头结点、无头结点的循环、非循环单链表，如何判断为空？如何判断某结点为尾结点？ 8．循环链表主要优点？用尾指针表示循环单链表有什么好处？ 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。 9．何为储存密度？ 10．例，输出无头结点的单链表中所有奇数。 解：设链表类型定义如下： typedef int datatype; //结点数据类型，假设为int typedef struct node * pointer; //一般结点指针类型 struct node { //结点结构 datatype data; pointer next; }; typedef pointer lklist; //头指针类型 void disp(lklist L) { pointer p; p=L; while(p!=NULL) { if(p->data%2==1) cout< p=p->next; } } 11．例，判断无头结点的链表中结点是否构成等差数列。 解：链表类型定义同上题。 int detect(lklist L) { pointer p,q; //以下用q表示p的前趋 datatype x; q=L;if(q==NULL) return 1; //链表为空 p=q->next;if(p==NULL) return 1; //链表只有1个结点 x=p->data-q->data; //初始结点差 while(p->next!=NULL) { q=p;p=p->next; if(p->data-q->data!=x) return 0; //不满足等差关系 } return 1; } 12．例，删除无头结点的链表中的第i个结点。 解：链表类型定义同上题。 void delete(lklist L,int i) { int k=0;pointer p=L,q; while(k!=i-1) { //找第i-1个结点 p=p->next;k++; } q=p->next;p->next=q->next;delete q; } 13．例，在无头结点的链表中的第i个结点前插入数据x。 解：链表类型定义同上题。 void insert(lklist L,int I,datatyoe x) { int k=0;pointer p=L,q; while(k!=i-1) { //找第i-1个结点 p=p->next;k++; } q=new node;q->data=x; q->next=p->next;p->next=q; } 1．何为假上溢？如何克服？ 2．循环队列如何实现？ 3．何为栈、队列？两者共同特点？ 答：栈是限定仅在表为进行插入或删除操作的线性表。队列是一种先进先出的线性表。 在数据结构上是相同的。 4．链队列、链栈是否都有必要设置头结点？有没有上溢、下溢、假溢出问题？ 5．例：三个点ABC依次进栈(在进栈的中间可能有出栈)。问ABC、BCA、CAB能否是可能的出栈序列？解：按先进后出的原则分析，ABC可行：即A进A出、B进B出、C进C出； BCA可行：即A进不出，B进B出、C进C出、A出； CAB不行：C出后，栈内有BA，应B先出。 6．循环队列A[m]中，已知头指针、尾指针与元素个数中的任意两个，求另一个？ len=(rear-front+m)%m; rear=(front+len)%m; front=(rear-len+m)%m; 7．循环队列A[m]空、满的条件？ 空：rear＝front 满：front=(rear+1)%m; 8．串、长度、子串、相等、子串定位等的概念； 答：串中字符的数目n称为串的长度。0个字符的串成为空串，它的长度为0。 串的串连是将一个串紧接着存放在另一个串的后面而成的一个新串。串的连接满足结合率，不满足交换率串的模式匹配问题：子串的定位操作通常称为串的模式匹配。通常思想是从主串S的第pos个字符起和模式的第一个字符比较，若相等则继续逐个比较后继字符，否则从主串的下一个字符起再重新和模式的字符比较。依此类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，函数值为和模式T中第一个字符相等的字符在主串S中的序号，否则称模式不匹配，函数值为0。 1．一维数组是否是顺序表？数组元素地址的计算？ 答：是， 2．多维数组的两种储存方式？C数组用哪一种？ 答：以行序位主序的存储方式和与列序为主的存储方式。 C数组用以行序为主。 3．三元组含义？一般矩阵按三元组存储能否节省空间？ 答：三元组表表示法：每一个非0元素对于一个三元组（row，col，val），row为非0元素的行下标，col 为非0元素的列下标，val为非0元素的值。显然，有N个非0元素的，只需要3N个存储单元。 4．何为稀疏矩阵、特殊矩阵？为什么要对矩阵压缩存储？ 答：稀疏矩阵：对于m*n的矩阵A中若有N个非0元，若N< 特殊矩阵（1）：对称矩阵由于对称性，只需存储上三角或下三角部分，如按行优先顺序存储对称矩阵A，则等价于压缩在一个一维数组B中。 LOC[a ij]=LOC[B[k]]=LOC（a11）+（k-1）*L 特殊矩阵（2）：上（下）三角矩阵以下三角为例，既当i 矩阵压缩的原因：在数值分析中经常出现一些阶数很高的矩阵，同时在矩阵中有许多值相同的元素或者是0元素。有时为了节省存储空间，可以对这类矩阵进行压缩储存。 1．二叉树顺序存储后逻辑关系通过什么表示？ 答：顺序存储结构：按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元依次自上而下、自 左至右存储完全二叉树上的结点元素，即将完全二叉树上的编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。 2．何时用树结构？树是否只能用链式存储？ 解：表示具有分支和层次关系的数据时用树。二叉树等特殊情况可用顺序存储。 3．已知二叉树的深度k，则其结点数范围？已知二叉树的结点数，则其深度k范围？ 4．只有3个结点的二叉排序树有几种形态？ 解：有5种，见下图所示。 5．完全二叉树有6个叶子，则结点总数就是11吗？ 解：已知叶子数的完全二叉树一般有两棵，结点数差1，见下图： A B C D E F G H I J K A B C D E F G H I J K L 一般，结点数n＝n0＋n1＋n2，而n0＝n2＋1(二叉树性质)，所以n＝2n0－1＋n1。完全二叉树树中度为1的结点最多只有1个，即n1＝1或0，所以n＝2n0或n＝2n0－1。 6．某完全二叉树有600个结点，则叶子数有多少？度1结点有多少？ 解：由层次编号规律，结点i的左孩子编号为2i，若结点i为叶子，则它没有左孩子，即2i>n，即i>n/2＝300的结点为叶子，叶子号为301，302，…,600，共300个。 由于n0=n2+1，现在n0=300，所以n2=299。另外，结点总数n=n0+n1+n2，所以n1＝600－300－299＝1 7．最优二叉树的构造过程？WPL计算？ 8．最优二叉树可否有100个结点？若有111个结点，则其中有多少个叶子？有没有度为1的结点？ 解：结点总数n=2n0-1，n0为叶子数，可见结点数为奇数。对111个结点，n0＝(n+1)/2=56。根据构造过程，每次两个结点合并，故结点的度要么为2（分支结点），要么为0（叶子），不会出现度1的结点。 9．二叉树的顺序存储结构、二叉链表的画法？二叉链表中有多少个空指针？ 10．如何由先序＋中序、后序＋中序还原出二叉树？ 解：由遍历方法以下几点是显然的： ①对前序序列，序列的第一个点就是整个二叉树的根； ②对后序序列，序列的最后一个点就是整个二叉树的根； ③对中序序列，以根为界，序列的前一部分结点在根的左子树中，后一部分结点在根的右子树中；并 且，由前一部分构成的子序列是左子树的中序序列，由后一部分构成的子序列是右子树的中序序列。 若给定了前序和中序序列，反复利用上面的①和③，就可获得结点完整的逻辑信息，即由前序序列找到根，由中序序列得到左、右子树；再在对每个子树由前序序列找到子树的根，由中序序列得到子树的左、右子树，等等类推，每次都可得到一个点(子树的根)，从而逐渐获得树的全部信息，也就可以还原和构造出该二叉树。这个过程参见下图。 中序遍历序列： 左子树根右子树 前序遍历序列： 左子树 根 右子树 根 根 ps pe is ie i 例：已知二叉树的中序和后序序列分别为：BCDAFEHJIG 、DCBFJIHGEA ，画出该二叉树。 解：由后序序列可知，整个二叉树的根为A ，再从中序序列找到结点A ，其左边为BCD ，对应A 的左子树，右边为FEHJIG ，对应根的右子树。对每个子树进行同样分析即可画出此二叉树。比如对左子树BCD ，从原后序序列可找到它对应的后根序列为DCB ，于是左子树的根为B ，然后再由中序序列BCD 可知B 的左子树为空，CD 在B 的右子树，等等继续下去，直到每个结点都画出来。 10． 树、森林与二叉树的相互转换？如何判断二叉树是树还是森林转换而来？树／森林的遍历与对应 二叉树的遍历之间有何关系？ 答：森林与二叉树的转换： 1． 保留所有结点与其左结点的链接 2． 连接所有兄弟结点（拥有同一父结点的子结点） 3． 打断所有结点原本与右子结点的链接 4． 将兄弟结点顺时针转45度。 图为。。。 树和森林的遍历：树结构定义可以引出两种次序遍历树的方法，先根次序和后根次序，而森林的两种方法分别是先序和后序，树和森林的具体遍历方法与二叉树的三种遍历方法类似。 11．树的孩子链表、双亲链表、孩子兄弟链表的画法？ 13．例：求二叉树的结点数。 解：设二叉树结点类型为bitree ，函数名为sum ，函数返回结点数。 int sum(bitree t) { int L,R; if(t==NULL) return 0; //当前树为空，递归出口 L=sum(t->lchild); //求左子树中结点数 R=sum(t->rchild) //求右子树中结点数 return L+R+1; //结点数=左子树中结点数+右子树中结点数+1 } 14．例：求二叉树的叶子结点数。 解：设二叉树结点类型为bitree ，函数名为leaf ，函数返回叶子数。 int leaf(bitree t) { int L,R; if(t==NULL) return 0; //当前树为空，递归出口 if(t->lchild==NULL && t->rchild==NULL) return 1;//当前点为叶子，递归出口 L=leaf(t->lchild); //求左子树中叶子数 R=leaf(t->rchild) //求右子树中叶子数 return L+R; //叶子数=左子树中叶子数+右子树中叶子数 } 15．例：求二叉树的高度。 解：设二叉树结点类型为bitree ，函数名为high ，函数返回高度。 int high(bitree t) { int L,R; if(t==NULL) return 0; //当前树为空，递归出口 L=high(t->lchild); //求左子树高度 R=high(t->rchild) //求右子树高度 return (L>R?L:R)+1; //高度=左、右子树高度较大者+1 } 1． 图的边数范围？连通图的边数范围？顶点度数之和与边数有何关系？ 答：无向图中最多有) 1(21 -n n 条边，若为有向图，最多有n （n-1）条边。连通图最少有n-1条边。 若一个图中有n 个顶点和e 条边，则图中所有顶点的度同边数e 满足：∑==n i vi D e 1 )(21 2．图的两种常用储存方式邻接表、邻接矩阵。 2． 有向图、无向图邻接表、邻接矩阵的画法？特点？在邻接表、邻接矩阵上求出度和入度？ 答：邻接矩阵：是表示顶点之间相邻关系的矩阵。在采用邻接矩阵表示图，对于无向图，边数即为矩阵中非0（或非max ）的个数除以2，对于有向图，边数即为矩阵中非0（或非max ）的个数；对于无向图，顶点v i 的度就是对应第i 行或第i 列上非0（或非max ）元素的个数，对于有向图，顶点v i 的出度就是对应第i 行上非0（或非max ）元素的个数，顶点v i 的入度就是对应第i 列上非0（或非max ）元素的个数。 邻接表：是对图中的顶点建立一个邻接关系的单链表，并把它们的表头指针用向量存储的一种图的表示方法。在图的邻接表中便于查找一个顶点的度（出度），这只要首先从表头向量中取出对应的表头指针， 然后从表头指针出发进行查找计算即可。但对于有向图的邻接表中查找一个顶点的入度，那就不方便了，它需要扫描所有的顶点邻接表中所有顶点邻接表中的边结点，因此专门建立一个逆邻接表，该表中的每个顶点的单链表示储存该顶点的所有入边的信息。 3．如何由输入的边信息画邻接表？如何在邻接表上进行DFS、BFS遍历？ 答：画邻接表：（1）for i:=1 to n do Begin Read(GL[i].data); {读入顶点vi的信息} GL[i].link:=nil; {表头指针域置空} End; （2）for k:=1 to e do begin Read(i,j); {读入一条边的两端点序号} New（s）；s^.adjvex:=j; {为vi邻接表生成一个出边邻接顶点} s^.next:=GL[i].link; GL[i].link:=s; { 把结点s^插入到vi邻接表的表头} end; DFS: Procedure dfs(i); Begin (1)write(i); (2)visited[i]:=true; {置vi结点已访问} (3)p:=GL[i].link; {取vi邻接表的表头指针} (4)while p<>nil do {依次搜索vi的邻接点} begin j:=p^.adjvex; {j为vi的一个临界点的符号} if not visited[j] then dfs(j); {如果vi的一个邻接点vj没有被访问，则从vj出发调用} p:=p^.next; {使用p指向vi的下一格邻接点所对应的边结点} end end; BFS: Procedure bfs(i); {从出发点vi出发广度优先搜索用邻接表GL表示的图} Begin Setnull(Q); {置队列空} Write(i); {访问处始点vi} Visited[i]:=true; {置vi已访问} Insert(Q,i); Repeat (1)k:=delete(Q); {队首元素出队，第一次执行时是把i赋给k} (2)p:=GL[k].link; {取vk邻接表的表头指针} (3)while p <> nil do {依次搜索vk的邻接点} begin j:=p^.adjvex; { vj为vk 的一个邻接表} if not visited then write(j); {访问点vj} visited[j]:=true; insert(Q,j); p:=p^.next {使p指向下一个邻接点对应的边结点} until empty(Q) end; 5．DFS的实现用到栈，BFS的实现用到队列。 5．DFS类似树的先根遍历，BFS类似树的层次遍历。 6．有向图顶点出度之和＝结点入度之和？ 答：顶点出度之和＝结点入度之和 7．连通分量含义？连通图有多少连通分量？ 答：在无向图G中，若从顶点v i到顶点v j有路径，则称v i和v j是连通的。若图中的任意两个顶点都连通，则称G为连通图，否则称为非连通图。无向图G的极大连通子图称为G的连通分量。显然，任何连通图的连通分量只有一个，即本身。 8．生成树、最小生成树的概念？如何求？唯一否？ 生成树：一个连通无向图的生成树是图的一个连通分量，它含有图的所有n个顶点以及连接这些顶点的n-1条边。不唯一。 最小生成树：具有权最小的生成树称为图的最小生成树。不唯一。Prim算法和Kruskal算法。 11．什么图可得到生成树，什么图可得到生成森林？ 解：连通图得到生成树，非连通图得到生成森林。 12．如何拓扑排序？有向图是否总可拓扑排序？唯一否？－无回路的有向图可以拓扑排序，不一定唯一13．例：在邻接矩阵M[n][n]上求顶点k的入度。 解：入度＝矩阵相应列中1的个数。 int in(int M[n][n],int n,int k) { int i,j=0; for(i=0;i return j; } 1．为什么要进行排序？－方便以后的查找 2．排序可分为插入排序、选择排序、交换排序、＿＿＿＿＿、＿＿＿＿＿。 3．当初始序列基本有序时，哪些排序方法较快？哪些排序方法反而变慢？ 4．哪些排序方法的效率与序列的初始状态基本无关？有关？ 6．关键字比较次数越少，排序就越快吗？快速排序在任何时候都最快吗？ 解：除了关键字比较，还有关键字移动问题。如果移动次数多、结点内容又多，则排序时间也会较长。特别地，基数排序不需比较，但执行时间并不一定比需要比较的排序快。 6．各种排序方法步骤如何？要会写每趟的结果。难点：快速排序、堆排序、希尔排序。 1．二分查找、顺序查找、分块查找对数据表有何要求？分块查找由哪2步组成？ 答：需要数据项有序，分块查找：先确定待查记录所在的块，可以用顺序查找也可以用折半查找；然后再块中顺序查找。 2．顺序查找的监视哨是否一定设在0号位置？ 不一定 3．何为二叉排序树？中序特点？其形态与什么有关？ 答：二叉排序树（binary sort tree）或者是一棵树，或者是具有下列性质的二叉树：（1）若它的左子树不为空，则左子树上所有结点的值均小于它根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）他的左、右子树也分别是二叉排序树。 4．二叉排序树的查找是否总比顺序表的查找快？ 5．何为平衡二叉树？唯一否？何为结点平衡因子？ 答：平衡二叉树又称AVL树，它或是一棵空树，或是具有下列性质的二叉树：他的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。 二叉树中每个结点的左子树高度减去右子树的高度定义为该结点的平衡因子。 6．散列表概念？何为冲突？何为同义词？ 答：散列同顺序、链接和索引一样，是存储线性表的另一种形式，因使用的数组空间是线性表进行散列存储的地址空间，所以称之为散列表。 一个待插入元素的散列地址单元已被占用，使得该元素无法直接存入到此单元中，我们把这种现象叫做冲突。 当散列地址的取值区间远比关键字的取值区间小，这样，当不同的关键字通过同一散列函数计算散列地址时，就可能出现具有相同散列地址的情况，若该地址中已经存入了一个元素，则具有相同散列地址的其他元素就无法直接存入进去，从而引起冲突，通常把这种具有不同关键字而具有相同的散列地址的元素称为“同义词”。 7．散列表既是一种存储方式，又是一种查找方法。 8．散列表要解决两个主要问题：散列函数的构造、冲突的处理。 9．开散列表查找效率一般比必散列表高？ 10． 散列表的查找是否就不需关键字的比较了？散列表的查找效率是否取决于数据的个数n ？ 答：需要关键字比较，效率取决于三个因素：哈希函数、处理冲突的方法和哈希表的填装因子。 11．在10000个结点中查找，肯定比在10个结点中查找的平均时间慢吗？ 提示：如果采用散列方法组织数据，查找效率不直接取决于数据个数n 。 12．例：在6个结点的有序表中进行二分查找，在等概率下查找成功和不成功时的平均查找长度如何？ 解：先画出6个结点二分查找的判定树，见右图。显然，如果要查找的点正好在第i 层，则经过i 次关键字的比较，对本题，每层的结点数分别为1、2、3个，所以查找成功时平均查找长度为 ASL ＝(1×1＋2×2＋3×3)／6＝14／6＝2.33 查找不成功时有图中虚线所示的7种情况 (即Key 注意这里指关键字比较，不包含空树的空指针比较。 13．例：已知关键字输入序列{10,17,6,9,20}，画出相应的二叉排序树，并求在等概率下查找成功和不成功时的平均查找长度。 解：对应的二叉排序树见右图(插入过程见课本)。查找成功时平均查找长度为 ASL=(1×1＋2×2＋3×2)／5=11／5＝2.2 查找不成功时有图中虚线所示的几种情况(即<6,6~9,9~10,10~17,17~20,>20)，所以平均 查找长度为 ASL un =(2×2＋3×4)／6=16／6＝2.67 注意这里指关键字比较，不包含空树的空指针比较。 14．例：对关键字序列{11,78,10,1,3,2,4,21}构造散列表，取散列地址为HT[0..10]，散列函数为H(K)＝K ％11，试用线性探查法冲突，画出相应的闭散列表，并分别求查找成功和不成功时的平均查找长度。 解：首先求出散列地址，见下图(a)，据此得到闭散列表见下图(b)。 查找成功的平均比较次数为： ASL ＝(1＋1＋2＋1＋3＋2＋8＋l)／8＝2.375 查找不成功的平均查找长度为： ASL unsucc ＝(8＋7＋6＋5＋4＋3＋2＋1＋1＋1＋9)／11≈4.273 15．例：对关键字序列{11,78,10,1,3,2,4,21}构造散列表，取散列地址为HT[0..10]，散列函数为H(K)＝K ％11，试用拉链法解决冲突，画出相应的开散列表，并分别求查找成功和不成功时的平均查找长度。 解：散列地址同上题，开散列表分别见下图(c)。 查找成功的平均比较次数为： ASL ＝(1×6＋2×2)／8＝l.25 查找不成功的平均查找长度为： ASL unsucc ＝(1＋2＋1＋1＋1＋0＋0＋0＋0＋0＋2)／11≈0.727 61710920 15 3 264 1 783成功比较次数11关键字 K 1010散列地址 K％11 11218231(a) (b) 34 56789101201110211散列表(c) 78 1243 1 2 4 10 21324 1234 56 789成功比较次数 101 21 1100000 2 21不成功比较次数 8 7 6 9 2 3 4 1 115 16．例：求二叉排序树中最大关键字。 解：由二叉排序特点，最大关键字在最右下位置（最小关键字在最左下位置）。设根结点指针类型为bitree ，一般结点指针类型为point ，函数名为fx ，函数返回最大关键字结点地址。 int high(bitree t) { pointer p; if(t==NULL) return NULL; //当前树为空 p=t; while(p->rchild!=NULL) p=p->rchild; //向右下搜索 return p; } 《数据库系统》实验报告 姓名： 班级： 学号： 日期： 课时一 实验1 数据库 【实验目的】 掌握交互式和脚本执行下列数据库操作： ?创建数据库 ?分离数据库 ?数据库文件备份 ?附加数据库 ?删除数据库 【实验内容】 1.1 创建数据库 1、交互式创建数据库：数据库名称为jxsk；并查看数据库属性；修改数据库参数；把数据库jxsk文件增长参数设置为4MB，文件最大大小参数设置为100MB。 2、使用SQL指定参数创建数据库，查看数据库属性，要求如下： 1)创建数据库，其名称为testbase1，其中包括： ?数据文件名为testbase1_dat.mdf，存储在“D:\MyDatabase”文件夹； ?事务日志文件名为testbase1_log.ldf，存储在“D:\MyDatabase”文件夹。 2)创建数据库，其名称为testbase2，其中包括： ?数据文件： 主文件组PRIMARY包括文件testbase2_prim_sub1_dat、testbase2_prim_sub2_dat； 次文件组Grouptest1包括文件testbase2_group1_sub1_dat、testbase2_group1_sub2_dat； 次文件组Grouptest2包括文件testbase2_group2_sub1_dat、testbase2_group2_sub2_dat； 所有数据文件都存储在“D:\MyDatabase”文件夹。 ?事务日志： 事务日志文件名为testbase2_log.ldf，存储在“D:\MyDatabase”文件夹，文件大小初始为20MB，增长量20MB，最大500MB。 数据结构（含课程设计），随堂 第一章绪论 1.(单选题) 计算机所处理的数据一般具备某种内在联系，这是指（）。 A、数据和数据之间存在某种关系 B.元素和元素之间存在某种关系 C元素内部具有某种结构 D.数据项和数据项之间存在某种关系 答题： A. B. C. D. （已提交） 参考答案：B 问题解析： 2.(单选题) 在数据结构中，与所使用计算机无关的是数据的（）结构. A.逻辑 B.存储 C.逻辑和存储 D. 物理 答题： A. B. C. D. （已提交） 参考答案：A 问题解析： 3.(单选题) 数据结构在计算机中的表示称为数据的（） A.存储结构 B.抽象数据类型 C.顺序结构 D.逻辑结构 答题： A. B. C. D. （已提交） 参考答案：A 问题解析： 4.(单选题) 在计算机中存储数据时，通常不仅要存储各数据元素的值，还要存储（）. A.数据的处理方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 答题： A. B. C. D. （已提交） 参考答案：C 问题解析： 5.(单选题) 在计算机的存储器中表示数据时，逻辑上相邻的两个元素对应的物理地址也是相邻的，这种存储结构称为（） A.逻辑结构 B.顺序存储结构 C.链式存储结构 D.以上都正确 答题： A. B. C. D. （已提交） 参考答案：B 问题解析： 6.(单选题) 当数据采用链式存储结构时，要求（）. A.每个结点占用一片连续的存储区域 B.所有结点占用一片连续的存储区域 C结点的最后一个数据域是指针类型 D.每个结点有多少个后继就设多少个指针域 答题： A. B. C. D. （已提交） 参考答案：A 问题解析： 7.(单选题) 以下关于算法的说法正确的是（）. A.算法最终必须由计算机程序实现 B.算法等同于程序 C算法的可行性是指指令不能有二义性 D.以上都是错误的 答题： A. B. C. D. （已提交） 华南理工大学考研历年真题解析 ——811结构力学 主编：弘毅考研 编者：無冕之王 弘毅教育出品 https://www.doczj.com/doc/4b8933166.html, 【资料说明】 《华工结构力学历年真题解析（专业课）》系华工大学优秀考研辅导团队集体编撰的“历年考研真题解析系列资料”之一。 历年真题是除了参考教材之外的最重要的一份资料，其实，这也是我们聚团队之力，编撰此资料的原因所在。历年真题除了能直接告诉我们历年考研试题中考了哪些内容、哪一年考试难、哪一年考试容易之外，还能告诉我们很多东西。 1.命题风格与试题难易 第一眼看到华工历年试题的同学，都觉得试题“简单”。其实，这也是很多学生选择华工的原因吧。华工的试题不偏、不怪，80% 的题目可以在课本上找到部分的答案。这不同于一些学校的试题，比如同济大学，理论性很强，怪题多，可能一点也答不上来。华工的试题，则相对简单多。 华工题目简单，但是不是每个人都拿140以上，很大程度上就是基本知识点没学透。其实这很像武侠小说中的全真教，招式看似平淡无奇，没有剑走偏锋的现象，但是如果没有扎实的基础和深厚的内功是不会成为大师的。我们只能说命题的风格是侧重考察基础的知识，但是，我们要答出亮点，让老师给你高分，这并不容易。 2.考试题型与分值 大家要了解有哪些题型，每个题型的分值。从最近五年看，华工的题目基本不变。可很多学生平时眼高手低，到考试的时候就会傻眼。所以平常一定要多动笔，多联系。 3.各章节的出题比重 华工的专业课没有考试大纲，因此没有重、难点的告知，但大家可以通过对历年真题的分析，掌握各个章节在整个考研中的重要地位。通过这些分析，就把握了复习的重点。 4.重要的已考知识点 考研专业课试卷中，很多考点会反复出现，一方面告诉大家这是重点，另一方面也可以帮助大家记忆重要知识点，灵活的掌握各种答题方法。比如一些刚架的形状，是否出现过无穷刚杆等。对于反复考查的知识点，一定不要局限于答案，而要对答案进行变化，考研是选拔高层次人才的考试，老师不会对一个问题反复让大家背书，因此对于灵活性的要求更高，需要大家养成良好的发散思维。 5.反复变化的出题方式 华南理工大学《人工智能》复习资料 Ch 2. 【状态空间表示】 S F G <>，， S ：初始状态的集合 F ：操作的集合 G ：目标状态的集合 例如：507{}{}{}Q a b c Q Q <>，，，，， 【状态空间图】 【状态空间图搜索使用的数据结构】 OPEN 表：已生成但没考察的节点(待考察节点) CLOSED 表：考察过的节点及节点间关系(搜索树) 【广度/深度优先搜索特点】 广度优先：完备的(一定能找到最优解)，搜索效率低，OPEN 表为队列结构 深度优先：不能保证找到最优解，OPEN 表为堆栈结构 有界深度优先搜索：即使能求出解，也不一定是最优 可变界深度优先搜索算法：深度可变，每次深度超过阈值 的点，都被当作待考察点(在CLOSED 表中) 【启发式搜索算法分类】 按选择范围分类： 全局择优搜索：考虑所有待考察节点 局部择优搜索：只考虑当前节点的子节点 【A*算法】 f （x ） ＝ g （x ）＋ h （x ） g(x)为当前点的代价 h(x)为距离目标的距离 A*对A 算法的改进： 对h(x)作限制，使其总是小于实际最小距离h （x ）≤ h* （x ）， 具有完备性 【与或图】 Q 与Q1，Q2与等价（即Q 可以分解为Q1+Q2） Q1与{Q1i},{Q1i’}或等价（即Q1可以转换为{Q1i}或{Q1i’}） 【与或图中的概念】 本原问题：直接可解的问题。 终止节点：本原问题对应的节点 端节点： 无子节点的节点 与节点： 子节点为与关系 或节点： 子节点为或关系 【与或图的广度/深度搜索】 Step1:S0放入OPEN 表 Step2:OPEN 表第一个点（记为N ）取出放入CLOSED 表，冠以编号n 。 Step3:若n 可扩展： (1)扩展N ，其子节点放入OPEN 表(深度:尾部，广度:首部) (2)考查这些节点是否终止节点。若是，放入CLOSED 表，标为可解节点，并对先辈点标示。若S0被标可解，得解。 (3)从OPEN 表删除具有可解先辈的节点。转Step2。 Step4:若N 不可扩展： (1)标示N 为不可解。 (2)标示先辈节。若S0被标不可解，失败。 (3)从OPEN 表删除具有不可解先辈的节点。转Step2。 华工数据库大作业超市管理（完整源文件） 一、超市管理数据库 超市需建立一个管理数据库存储以下信息： *超市信息包括超市代号，超市名，经理名及超市运营开销。 *一个超市内有多个部门，每个部门有部门号、部门主管姓名、地址，电话及每个月的部门运营开销。 *每个部门有多个员工，每个员工有员工号、姓名、年龄、性别，职位及月工资。 *每个部门销售多种商品，商品有商品号、商品名、规格，采购成本和零售价格、批发价格。 *商品采购自供货商，供货商有供货商号，供货商名，联系电话，联系地址。 *所有的商品存在商场或仓库中。 *商场有多个仓库，仓库有仓库号，仓库管理姓名、电话及仓库的运营成本。 应完成的主要功能：（1）基础信息管理功能，如超市信息的管理功能，包括录入、修改、查询、输出超市的信息；部门信息的管理功能，包括录入、修改、查询、输出部门的信息；还有员工，商品，采购商，仓库等的信息管理功能。（2）超市的进销存功能模块，包括进货，销售，库存以及超市盘点等常见功能。 (3)超市的利润统计功能，包括月利润和年利润统计。并能输出各种报表，如员工工资月报表，年报表；每个部门销售的商品数量的月报表；仓库存储商品数量的月报表；超市运营开销和部门运营开销的月报表等。 二、开发环境 数据库选用微软的SQL SERVER。开发环境可以选择：（1）Delphi; (2)Visual Basic; (3) C++ builder; (4) Visual C++;（5）Visual C#;(6)自选。只选择其中的一种软件开发工具实现即可。 三、基本要求 （1）完成上面所提及的所有需求 （2）要求撰写不少于2500字符的Word文档。 （3）文档中至少要包括：ER模型图、系统功能图、数据字典、表关系的详细说明。 1判断题 （对）1. 数据的逻辑结构与数据元素本身的内容和形式无关。 （错）2. 线性表的逻辑顺序与物理顺序总是一致的。 （对）3. 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。 （错）4. 对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。 （对）5. 最优二叉搜索树的任何子树都是最优二叉搜索树。 （对）6. 在二叉搜索树上插入新结点时，不必移动其它结点，仅需改动某个结点的指针，使它由空变为非空即可。 （对）7. 有n（n≥1）个顶点的有向强连通图最少有n条边。 （错）8. 连通分量是无向图中的极小连通子图。 （错）9. 二叉树中任何一个结点的度都是2。 （错）10. 单链表从任何一个结点出发，都能访问到所有结点。 二、单选题 1 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ B ）个元素。 A．8 B. 63.5 C. 63 D. 7 2 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，则A[3][3]在（ A ）位置，（10）表明用10进数表示。 A．692（10） B. 626（10） C. 709（10） D. 724（10） 3 N个顶点的连通图至少有（ A ）条边。 A．N－1 B. N C. N＋1 D. 0 4 下面程序的时间复杂度为（ C ）。 for(int i=0; i 数据库系统概论平时作业2 一、单项选择题 （本大题共20小题，每小题2分，共40分) 在每小题列出的四个备选项中只有一个是符合题目要 求的，错选、多选或未选均无分。 1. 下面列出的数据管理技术发展的三个阶段中，哪个（些）阶段没有专门的软件 对数据进行管理？（A ） Ⅰ.人工管理阶段 Ⅱ.文件系统阶段 Ⅲ.数据库阶段 A ．只有Ⅰ B ．只有Ⅱ C ．Ⅰ和Ⅱ D ．Ⅱ和Ⅲ 2. 在关系数据库中，表（table ）是三级模式结构中的（B ） A ．外模式 B ．模式 C ．存储模式 D ．内模式 第（3）至（5）题是基于如下两个关系，其中雇员信息表关系EMP 的主键是雇员号，部门信息表关系DEPT 的主键是部门号 3. 若执行下面列出的操作，哪个操作不能成功执行？（D ） A ．从EMP 中删除行(’010’, ’王宏达’, ’01’,1200) B ．在EMP 中插入行 (’102’, ’赵敏’, ’01’,1500) C ．将EMP 中雇员号=’056’的工资改为1600元 D ．将EMP 中雇员号=’101’的部门号改为’05’ 4． 若执行下面列出的操作，哪个操作不能成功执行？（C ） A ．从DEPT 中删除部门号=’03’的行 B ．在DEPT 中插入行（’06’,’计划部’,’6号楼’） C ．将DEPT 中部门号=’02’的部门号改为’10’ D ．将DEPT 中部门号=’01’的地址改为’5号楼’ 5． 在雇员信息表关系EMP 中，哪个属性是外键（foreign key ）？（C ） A．雇员号B．雇员名 C．部门号D．工资 6．在SQL语言的SELECT语句中，实现投影操作的是哪个子句？（A）。 A．select B．from C．where D．group by 7. SQL语言集数据查询、数据操纵、数据定义和数据控制功能于一体，语句 INSERT、DELETE、UPDATE实现哪类功能？（B）。 A. 数据查询 B.数据操纵 C.数据定义 D.数据控制 8.设关系R和关系S的基数分别是3和4，关系T是R与S的广义笛卡尔积，即： T=R×S，则关系T的基数是（C）。 A. 7 B. 9 C. 12 D. 16 9．设属性A是关系R的主属性，则属性A不能取空值（NULL）。这是（A）。 A.实体完整性规则 B.参照完整性规则 C. 用户定义完整性规则 D. 域完整性规则 10.在并发控制的技术中，最常用的是封锁方法。对于共享锁（S）和排他锁（X） 来说，下面列出的相容关系中，哪一个是不正确的？（B）。 A. X/X：TRUE B. S/S：TRUE C. S/X：FALSE D. X/S：FALSE 11.下面关于函数依赖的叙述中，不正确的是（B）。 A．若X→Y,X→Y,则X→YZ B．若XY→Z,则X→Z,Y→Z C．若X→Y,Y→Z,则X→Z D．若X→Y,Y′ Y,则X→Y′ 第（12）至（14）题基于以下的叙述：有关系模式A（C，T，H，R，S），基中各属性的含义是： C：课程T：教员H：上课时间R：教室S：学生 根据语义有如下函数依赖集： F={C→T，（H，R）→C，（H，T）→R，（H，S）→R} 12. 关系模式A的码是（D）。 A．C B．（H，R） C．（H，T）D．（H，S） 13．关系模式R的规范化程度最高达到（B）。 A．1NF B．2NF C．3NF D．BCNF 1. 评价一个好的算法，应该从哪几方面来考虑的？ 答：1、算法的正确性，2、算法的易读性，3、是算法的健壮性，4、是算法的时空效率（运行）。 2. 简述线性表的顺序和链式两种存储结构各自的主要特点。 答:1、顺序存储结构:存储单元地址连续，它以“物理位置相邻”来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。但它也使得插入和删除操作需移动大量的 数据元素。由于顺序表需要一组地址连续的存储单元，对于长度可变的线性表就需要预 分配足够的空间，有可能使一部分存储空间长期闲置不能充分利用。也可能由于估计不足，当表长超过预分配的空间而造成溢出，在这种情况下，又难于扩充连续的存储空间。 2、链式存储结构:存储单元地址为任意一组，它的存储单元可以是连续的，也可以是 不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和 物理次序不一定相同。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置)，这两部分信息组成数 据元素的存储映像，称为结点（node） 3. 有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,99}，如果采用折半查找法查找关键字为82 的元素时，请分析其比较次数和每次进行比较的元素。 答：4次比较后查找成功，分别和45、77、95、82进行比较首先和中间值45比较，82比45大选择右边，右边六个数和中间值77比较，82比77大选择右边，右边3个数选择中间值95进行比较，82比95小选择左边，左边1个数和82比较相等。 4. 有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C 第一个且D 第二个出栈）的次序有哪几个？ 答:有3 个: CDBAE, CDEBA, CDBEA 5. 一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为什么？ 答：CDBAE；CDBEA；CDEBA 6. 将整数序列（4，5，7，2，1，3，6）中的元素依次插入到一棵空的二叉排序树中，试构造相应的二叉排序树，要求用图形给出构造过程。 7.对于稠密图和稀疏图，采用邻接矩阵和邻接表哪个更好些？为什么？ 答：邻接矩形适合稠密图，因为邻接矩形占用的存储空间与边数无关；邻接表适合于稀疏图，因为邻接表占用的存储空间与边数有关 8.设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre 和next,试写出 第一章计算机系统概论·1.1 计算机的分类和应用 当前页有4题，你已做4题，已提交4题，其中答对4题。 1.大约（）年，计算机的运算速度提高10倍，成本降为原来的1/10. A、10~12 B、5~10 C、5~8 D、6~9 参考答案：C 2.计算机划为巨型机、大型机、中型机、小型机、微型计算机和单片机的依据是（） A、价格 2、体积 C、体系结构 D、整机性能 参考答案：D 问题解析： 3.第四代计算机的主要逻辑元件采用的是 A) 晶体管 B) 小规模集成电路 C) 电子管 D) 大规模和超大规模集成电路 参考答案：D 4.从第一台计算机诞生到现在的50多年中按计算机采用的电子元器件来划分，计算机发展经历了（）个阶段。 A. 4 B. 6 C. 7 D. 5 参考答案：D 第一章计算机系统概论·1.2 计算机的硬件 1.计算机硬件的五大基本构件包括：运算器、存储器、输入设备、输出设备和 A) 显示器 B) 控制器 C) 磁盘驱动器 D) 鼠标器 参考答案：B 2.通常所说的I/O设备指的是 A) 输入输出设备 B) 通信设备 C) 网络设备 D) 控制设备 参考答案：A 3.CPU要能与外设通信必须要有： A) 寄存器 B) 存储器 C) 接口电路 D) 网线 参考答案：C 4.现代计算机之所以严格地按照时间的先后顺序进行操作，主要因为有（）。 A.开关电路 B. 时序部件 C. 接口电路 D. 协处理器 参考答案：B 第一章计算机系统概论·1.3 计算机的软件 1.计算机软件系统一般包括（）。 A. 操作系统和应用软件 B. 系统软件和管理软件 C. 系统软件和应用软件 D. 操作系统、管理软件和各种工具软件 华工综合的高性能复习 题 2008 年11 月 1. 解释以下基本概念 HPC, HPCC, Distributed computing, Meta computing, Grid computing MIMD, SIMD, SISD PVP, SMP,MPP, DSM, Cluster, Constellation UMA, NUMA, CC_NUMA, CORMA, NORMA HPC:高性能计算是计算机科学的一个分支，研究并行算法和开发相关软件，致力于开发高性能计算机（High Performance Computer）。 计算密集型（Compute-Intensive）应用 数据密集型（Data-Intensive）应用 网络密集型（Network-Intensive）应用 HPCC：高性能计算和通信（High-Performance Computing and Communications：HPCC） 分布式高性能计算、高速网络和Internet的使用 分布式计算（Distributed Computing） 更着重于功能而不是性能的增加 网格计算（Grid Computing） 分布式高性能计算（Distributed, High Performance Computing： DHPC），或称元计算（Meta computing） 单指令单数据流：SISD 普及程度：MIMD > SIMD > MISD 单指令多数据流：SIMD 多指令单数据流：MISD 多指令多数据流：MIMD ?对称多处理（共享存储并行）机（SMP：Symmetric MultiProcessing）； ?分布共享存储多处理机（DSM：Distributed Shared Memory）； ?大规模并行机（MPP：Massively Parallel Processors）； ?工作站（微机）机群（COW：Cluster Of Workstation、Beowulf PC-Cluster）； ?并行向量多处理机（PVP：Parallel Vector Processors） 均匀访存模型（UMA：Uniform Memory Access） 非均匀访存模型（NUMA：Nonuniform Memory Access） Cache一致性非均匀访存模型（CC-NUMA：Coherent-Cache Nonuniform Memory Access） 分布式访存模型（DMA：Distributed Memory Access） 2. 试比较PVP、SMP、MPP、DSM 和Cluster 并行机结构的不同点，以典型系统举例说明。SMP：对称多处理器，共享存储，高速缓存一致性，低通信延迟，不可扩放性 华南理工大学数据库原理与设计大作业报告 专业：计算机科学与技术 班级： 2015春 学号： 20 学生姓名：陈亮 完成时间： 目录 目录 (2) 1、概述 (4) 2、需求分析 (6) 零售前台（POS）管理系统 (6) 后台管理系统 (7) 数据需求 (7) 3、数据库逻辑设计 (9) 概念结构设计 (9) 4、软件功能设计 (13) 逻辑结构设计 (13) 物理结构设计 (15) 完整性设计 (20) 安全性设计 (22) 5、界面设计 (24) 系统功能结构图 (24) 模块设计与实现（部分界面） (24) 6、结束语 (31) 7、参考文献 (33) 1、概述 超市管理信息系统是针对超级市场的销售而开发的。应用超市管理信息系统能够转变超市的工作方式，有效提高销售速度和服务水平，提高客户对超市的信任度和满意度，改善客户关系。运用超市管理信息系统，在销售商品时实行出口一次性付款，可以实现超市内部现代化管理，能够准确把握每一种商品的销售动态，防止商品断档或过量储备，商品开发方向、进货的适时化都可通过超市管理信息系统来完成。 超市管理信息系统将手工编制好的销售账目或根据原始超市销售记录直接在系统内制作超市销售信息，同时可对输入的超市销售信息进行修改、查询等操作。这种集约化的销售管理模式既便于对超市销售信息的收集、整理和加工，又便于操作员的需求信息在最短的时间内得到反馈，同时超市管理信息系统可自动分析各种商品销售变化规律，商品销售结构、居民消费变化等，从而为合理进货、经营、加工、库存、销售等提供科学的决策依据。 超市管理信息系统充分运用计算机管理信息技术，建立数据库，对超市的进销存过程进行详细分析，实现了对超市的进货、销售和库存的科学管理。 1.(单选题) 把一组具有相同数据结构和相同操作的对象的集合定义为类，此定义包括一组数据属性和在( )上的一组合法操作。 A．数据 B．属性 C．对象 D．消息 答题： A. B. C. D. （已提交） 参考答案：A 问题解析： 2.(单选题) 面向对象技术特别强调的是( )的数据结构。 A．数据库 B．数据 C．抽象类型 D．对象 答题： A. B. C. D. （已提交） 参考答案：D 问题解析： 3.(单选题) 在软件交付使用后，由于软件开发过程产生的错误没有完全彻底在测试阶段发现，必然有一部分隐含错误带到( )阶段。 A. 需求 B. 开发 C. 编码 D. 维护 答题： A. B. C. D. （已提交） 参考答案：D 问题解析： 4.(单选题) 软件维护的工作流程为用户提出( )、维护组织审查申请报告并安排维护工作、进行维护并做详细的维护记录和复审。 A. 维护报告 B. 维护申请 C. 维护文档 D. 维护说明 答题： A. B. C. D. （已提交） 参考答案：B 问题解析： 5.(单选题) 在需求( )中，开发人员要从用户那里解决的最重要的问题是软件应当做什么。 A. 设计 B. 代码 C. 分析 D. 结构 答题： A. B. C. D. （已提交） 参考答案：C 问题解析： 6.(单选题) 在统一过程中是采用用例驱动和架构优先的策略，并采用迭代增量建造方法，使（）“逐渐”被开发出来。 A．硬件 B．功能 C．软件 D．模型 答题： A. B. C. D. （已提交） 参考答案：C 问题解析： 7.(单选题) 软件工程学的一个重要目标是（）。 A．提高程序的执行效率 B．降低程序对存储空间的要求 C．提高软件的可理解性 D．提高软件的可维护性 答题： A. B. C. D. （已提交） 参考答案：D 问题解析： 8.(单选题) 软件工程的过程是将软件工程（）综合起来以达到合理、及时地进行计算机软件开发的目的。 A．方法 B．工具 C．方法和工具 D．过程 答题： A. B. C. D. （已提交） 参考答案：C 问题解析： 9.(单选题) ( )是以提高软件质量为目的的技术活动。 A、技术创新 B、测试 C、技术改造 D、技术评审 答题： A. B. C. D. （已提交） 参考答案：D 数据结构复习提纲 第二部分复习提纲(不分题型) 1．逻辑结构、存储结构、运算、算法、时空复杂性等哪些与计算机硬件有关？无关？ 逻辑结构： 存储结构：指数据的逻辑结构在计算机存储器中的实现，存储结构是依赖于计算机的。 运算：在数据逻辑结构上定义的操作。 ◆例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。 那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。 最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。 所谓算法（Algorithm）是对问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。 所谓算法复杂度： T (n) = O(f(n)) 称T (n) 为算法的渐近时间复杂度（Asymptotic Time Complexity）,简称时间复杂度。O是数量级的符号。 下面我们探讨一下如何估算算法的时间复杂度 算法= 控制结构+ 原操作（固有数据类型的操作） 算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间 算法的执行时间与原操作执行次数之和成正比 2．逻辑结构与存储结构是否一一对应？ 答：否。 华南理工大学《数据库》（研究生）复习题 1.基于锁的协议有几种？什么是基于时间标签的协议？什么是基于验证的协议？ 基于锁的协议即两段锁协议，是指指所有事务必须分两个阶段对数据项加锁和解锁。具体又分为：基本2PL、保守2PL 、严格2PL和精确2PL 基于时间标签的协议：事务被施加了一个基于时间戳的顺序要求并发控制器检查事务对每个DB对象的读写请求看是否能遵循基于时间戳的串行顺序。 以上这个原则性要求，可具体表达为：对任两事务Ti和Tj，若Ti先于Tj,即TS(Ti) 第二章几何组成分析·第二节几何不变体系的基本组成规则 随堂练习提交截止时间：2018-12-15 23:59:59 当前页有3题，你已做3题，已提交3题，其中答对2题。 1.(单选题) 图示体系为（） A．无多余约束的几何不变体系 B．有多余约束的几何不变体系 C．几何可变体系 D．几何瞬变体系 答题： A. B. C. D. （已提交） 参考答案：A 问题解析： 2.(单选题) 图示体系为（） A．无多余约束的几何不变体系 B．有多余约束的几何不变体系 C．几何可变体系 D．几何瞬变体系 答题： A. B. C. D. （已提交） 参考答案：C 问题解析： 3.(单选题) 图示体系为（） A．无多余约束的几何不变体系 B．有多余约束的几何不变体系 C．几何可变体系 D．几何瞬变体系 答题： A. B. C. D. （已提交） 参考答案：A 问题解析： 第二章几何组成分析·第三节瞬变体系的概念 随堂练习提交截止时间：2018-12-15 23:59:59 当前页有7题，你已做7题，已提交7题，其中答对7题。 1.(单选题) 图示体系为（） A．无多余约束的几何不变体系 B．有多余约束的几何不变体系 C．几何可变体系 D．几何瞬变体系 答题： A. B. C. D. （已提交） 参考答案：D 问题解析： 2.(单选题) 图示体系为（） A．无多余约束的几何不变体系 B．有多余约束的几何不变体系 C．几何可变体系 D．几何瞬变体系 答题： A. B. C. D. （已提交） 参考答案：B 问题解析： 3.(单选题) 图示体系为（） A．无多余约束的几何不变体系 B．有多余约束的几何不变体系 C．几何可变体系 D．几何瞬变体系 华南理工大学数据库期末考试卷考点整理第一章 1.DBMS功能 （1）数据定义功能 （2）数据组织、存储和管理 （3）数据操纵功能 （4）数据库的事务管理和运行管理 （5）数据库的建立和维护功能 （6）其它功能 2.数据库系统的特点 （1）数据结构化（与文件系统的本质区别） （2）数据的共享性高，冗余度低，易扩充 （3）数据独立性高 （4）数据由DBMS统一管理和控制 3.试述数据库系统的组成。 数据库系统一般由数据库，数据库管理系统（及其开发工具），应用系统，数据库管理员和用户构成。 3.两类数据模型 （1）概念模型 （2）逻辑模型（关系模型）和物理模型 4.数据模型的组成要素 （1）数据结构（静态特性） （2）数据操作（动态特性） （3）完整性约束 5.E-R图 （1）实体：矩形 （2）属性：椭圆 （3）联系：菱形 6.关系模型 ——关系的每一个分量必须是一个不可分的数据项，即不允许表中还有表 关系（表） 元组（行） 属性（列） 7.数据库系统结构 （1）三级模式——外模式（用户）、模式（逻辑）、内模式（存储） （2）二级映像——外模式/模式映像（逻辑独立性）、模式/内模式映像（物理独立性） 第三章 1.SQL特点 （1）综合统一 （2）高度非过程化 （3）面向集合的操作方式（非关系数据模型面向记录） （4）以同一种语法结构提供多种使用方式 （5）语言简洁，易学易用 定义功能：定义表、视图、索引。 分为：数据定义，数据查询，数据更新和数据控制4大部分。 2.定义模式 CREATE SCHEMA <模式名> AUTHORIZATION <用户名>[<表定义子句>|<视图定义子句>|<授权定义子句>] 3.删除模式 DROP SCHEMA <模式名> 数据结构（含课程设计）·数据结构课程作业提交方式：附件 二、简答题 1. 线性表可用顺序表或是链表存储，此两种存储表示各有哪些优缺点？ 答：顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或者直接存取（按下标）链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 优缺点： 顺序表：存取速度快，增删效率稍慢，且它的空间大小一经定义就不能扩大容量，不易扩充。 链表：存取慢，增删快，只要存储器中还有空间，就不会产生存储溢出问题。 2. 设有一个输入数据的序列是{46,25,78, 62, 12, 37, 70, 29}，试画出从空树起，逐个输入各个数据而生成的二叉搜索树。 答： 3.用广义表的带表头结点的存储表示法表示下列集合。 A = ( ) B = (6, 2) C = (‘a’,( 5, 3, ‘x’)) D = (B, C, A) E = (B, D) 答： 4.上图所示为一有向图，请给出该图的下述要求： （1）给出每个顶点的入度和出度； （2）以结点3为起始结点，分别画出该图的一个深度优先生成树和一个宽度优先生成树；（3）给出该图的邻接矩阵； （4）给出该图的邻接表； 答： （1）顶点入度出度 1 3 0 2 2 2 3 1 2 4 1 3 5 2 1 6 2 3 （2） 广度优先生成树 （3）邻接矩阵 （4）邻接表 5.对于如上图所示的有向图，试写出： (1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树； 答：（1） （2） 6.已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清，试构造出该二叉树。先序序列_BC_EF__ 中序序列BDE_AG_H 后序序列_DC_GH_A 答：后序最后一个是A，所以A是先序的第一个得到： 先序序列ABC_EF_ 中序序列BDE_AG_H 后序序列_DC_GH_A 先序的第二个元素是B，所以B是A的左子树根节点，有中序B在最前，知道其他 元素都在B的右子树上。 所以，后序序列为（DE_）B（B_H）A，对比已有的后序序列_DC_GH_A 得后序序列为：EDCBGHFA，中序序列为：BDECAGFH 先序序列ABD_EF_ 所以 结构力学（一）·随堂练习 2020秋华南理工大学网络教育答案第一章绪论 第二章平面体系的机动分析 1.(单选题) 计算自由度W是有意义的，若W＞0，则表示体系。 A.几何常变 B.几何瞬变 C.几何不变 D.几何可变 答题： A. B. C. D. （已提交） 参考答案：A 问题解析： 2.(单选题) 图示体系的几何组成为。 A.几何不变，无多余约束 B.几何不变，有一个多余约束 C.瞬变体系 D.几何不变，有2个多余约束 答题： A. B. C. D. （已提交） 参考答案：B 问题解析： 3.(判断题) 瞬变体系的计算自由度可能小于0。（） 答题：对. 错. （已提交） 参考答案：√ 问题解析： 4.(判断题) 图示体系为无多余约束的几何不变体系。（） 答题：对. 错. （已提交） 参考答案：√ 问题解析： 5.(单选题) 图示体系为。 A.几何常变体系 B.无多余约束的几何不变体系 C.瞬变体系 D.有多余联系的几何不变体系 答题： A. B. C. D. （已提交） 参考答案：C 问题解析： 6.(单选题) 图示体系为。 A.几何常变体系 B.无多余约束的几何不变体系 C.瞬变体系 D.有多余联系的几何不变体系 答题： A. B. C. D. （已提交） 参考答案：C 问题解析： 7.(判断题) 若体系计算自由度W≤0，则该体系几何不变。（）答题：对. 错. （已提交） 参考答案：× 问题解析： 8.(判断题) 下图的体系为几何不变体系。（） 答题：对. 错. （已提交） 参考答案：× 问题解析： 9.(单选题) 图示体系为。 A.几何常变体系 B.无多余约束的几何不变体系 C.瞬变体系 D.有多余联系的几何不变体系 答题： A. B. C. D. （已提交） 参考答案：B 问题解析： 10.(单选题) 下图所示正六边形体系为。 A.几何常变体系 B.无多余约束的几何不变体系 C.瞬变体系 D.有多余联系的几何不变体系 答题： A. B. C. D. （已提交） 参考答案：C 问题解析： 11.(判断题) 静定结构可以是瞬变体系。（）答题：对. 错. （已提交） 参考答案：× 目录 一．概述 (1) 1．开发背景 (1) 1．开发环境 (1) 二.系统分析设计 (1) 1．功能需求分析 (1) 2．数据库需求分析设计 (1) 3．软件功能分析设计 (4) （1）．公共模块设计 (4) （2）．登录模块设计 (5) （3）．成绩管理模块设计 (9) 三．心得体会 (10) 学生成绩管理系统 一.【概述】： 1.开发背景： 随着科学技术的不断提高，计算机科学日渐成熟，其强大的功能已为人们深刻认识，它已进入人类社会的各个领域并发挥着越来越重要的作用。作为计算机应用的一部分，使用计算机对学生成绩信息进行管理，有着手工管理所无法比拟的优点。 例如：检索迅速、查找方便、可靠性高、存储量大、保密性好、寿命长、成本低等。 这些优点能够极大地提高学生成绩管理的效率。因此，开发一套成绩管理系统成为很有必要的。 2.开发环境： 操作系统：Windows 8.1(x64) 开发环境支持平台：https://www.doczj.com/doc/4b8933166.html, Framework 4 开发环境：Visual Studio 2013 集成开发环境 开发数据库：Microsoft Sql Server 2012 开发语言：https://www.doczj.com/doc/4b8933166.html, 4.0 Web服务：IIS 8.5 浏览器：Internet Explorer 11.0及以上 二．【系统分析设计】 1 功能需求分析 学生成绩管理系统需要实现的功能包括：用户登录、管理学生个人信息、成绩信息查询和管理、课程信息查询和管理、班级信息查询和管理以及管理员信息的查询和是授权。 (1)管理员信息管理 普通管理员：可以管理学生信息、成绩、系部、班级、课程 超级管理员：具备普通管理员所有权限，还可以进行新的管理权限授权 (2)管理员登录和身份验证 所有操作都必须先登录方可进行，以此确保数据安全性 (3)成绩管理模块 登录后，可以添加，编辑，删除成绩信息 (4)系部管理模块 登录后，可以添加，编辑，删除系部信息 (5)班级管理模块 登录后，可以添加，编辑，删除班级信息 (6)学生信息管理模块 登录后，可以添加，编辑，删除学生信息华南理工数据库实验报告
数据结构·随堂练习2019春华南理工大学网络教育答案
华南理工大学811结构力学考研历年真题及答案
华南理工大学《人工智能》复习资料
超市管理数据库(华工完整大作业含源文件)
华工平时作业数据结构第一次作业
华南理工大学网络教育-数据库-2019秋-平时作业2答案
数据结构(含课程设计)平时作业2020秋华南理工大学网络教育答案
华南理工大学 计算机组成原理-随堂练习题汇总
华工综合的高性能复习题(考试复习用).
数据库大作业
(精选)华工2017《软件工程》随堂作业答案
华南理工大学数据结构复习提纲二
最新华南理工大学《数据库》(研究生)复习题
2018秋季华南理工大学网络学院结构力学(一)随堂练习答案
华南理工大学数据库期末考试卷考点整理_共6页
数据结构(含课程设计)作业 华工
《结构力学(一)》·随堂练习2020秋华南理工大学网络教育答案
华南理工大学-数据库课程设计报告(完整程序代码)
相关主题
文本预览