数据结构复习要点带答案
算法的五大特性：（有零个或多个输入）、（有一个或多个输出）、（有穷性）、（确定性）、（可行性）。
算法指的是（）。
A 对特定问题求解步骤的一种描述，是指令的有限序列；算法分析的目的是（分析算法的效率以求改
进），算法分析的两个主要方面是（空间性能和时间性能）。
1.算法质量的标准：时间复杂度是测量一个算法优劣的重要标准。
时间复杂度的计算：设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（Ο(1)），若为n*log25n，则表示成数量级的形式为（Ο(nlog2n)）。
【分析】：用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。
2.数据、数据元素、数据项的关系：（数据元素）是数据的基本单位，在计算机程序中通常作为一个整体
进行考虑和处理；（数据项）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。
【分析】数据结构指的是数据元素以及数据元素之间的关系。
3.设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。
试画出其逻辑结构图并指出属于何种结构。
【解答】其逻辑结构图如图1-3所示，它是一种图结构。
4.栈的特性：栈是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一段叫做栈顶，另一
端叫做栈底，不含任何数据元素的栈叫做空栈。（栈）可作为实现递归函数调用的一种数据结构。
【分析】递归函数的调用和返回正好符合后进先出性。
栈的特点是先进后出，即：进去的早，出来的晚！
54321进栈，5在栈底，1在栈顶！
出一次栈，则栈顶的1先出来，2成为新的栈顶。
ABCD入栈，D成为新的栈顶。
全部出栈：D C B A 2 3 4 5
综上，所有元素退栈顺序为：1 D C B A 2 3 4 5
5.入栈：template
V oid SeqStack::Push(T x)
{
if ( top==StackSize-1) throw “上溢”;
top++;
data[top]=x;
}
6.出栈的指针的操作：template
T SeqStack::Pop()
{
if ( top== -1) throw “下溢”;
x=data[top--];
return x;
}顺序栈基本操作时间复杂度为O（1）.
设顺序栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2n-1，…，a1，要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，请设计算法实现该操作，要求空间复杂度和时间复杂度均为O(n)。
【解答】操作步骤为：
①将所有元素出栈并入队；
②依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，则入栈；
③将奇数结点出栈并入队；
④将偶数结点出队并入栈；
⑤将所有元素出栈并入队；
⑥将所有元素出队并入栈即为所求。
7.循环队列队空队满的判断条件：①在添加元素前，队列头指针等于队列尾指针，则队列为空；②在添
加元素前，队列头指针！= 队列尾指针，但是当想要添加时，将队列尾指针加1试试，与队列头指针相等了，则队列满。此处是指，（队列尾指针+ 1 == 队列头指针）这样的判断
出队：
入队指针的操作：
若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（n-i+1 ）8.对称矩阵地址的计算：
设有三对角矩阵An×n（行、列下标均从0开始），将其三条对角线上的元素逐行存于数组B[3n-2]中，使
得B[k]=aij求：
⑴用i, j表示k的下标变换公式；
⑵用k表示i, j的下标变换公式。
【解答】⑴要求i, j表示k的下标变换公式，就是要求在k之前已经存储了多少个非零元素，这些非零元素的个数就是k的值。元素aij求所在的行为i，列为j，则在其前面的非零元素的个数是；k=2 + 3(i－1)+( j －i + 1)= 2i+ j。
⑵因为k和i, j之间是一一对应的关系，k+1是当前非零元素的个数，整除即为其所在行号，取余表示当前行中第几个非零元素，加上前面零元素所在列数就是当前列号，即
1一个n×n的对称矩阵，按行优先或列优先进行压缩存储，则其存储容量为（n(n+1)/2 ）
2设n行n列的下三角矩阵A（行列下标均从1开始）已压缩到一维数组S[1]~S[n(n+1)/2]中，若按行优先存储，则A[i][j]在数组S中的存储位置是（i×(i-1)/2+j ）。
一个稀疏矩阵如图4-4所示，写出对应的三元组顺序表和十字链表存储表示
对应的三元组顺序表如图4-5所示，十字链表如图4-6所示
已知两个n×n的对称矩阵按压缩存储方法存储在已维数组A和B中，编写算法计算对称矩阵的乘积。
【解答】对称矩阵采用压缩存储，乘积矩阵也采用压缩存储。注意矩阵元素的表示方法
9.二叉链表：一棵二叉树的第i（i≥1）层最多有（2i-1 ）个结点；一棵有n（n>0）个结点的满二叉树
共有（(n+1)/2 ）个叶子结点和（(n-1)/2 ）个非终端结点。
设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。---
深度为k的二叉树中，所含叶子的个数最多为（2k-1）；
设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（2h -1），最小值是（2h-1）
10.树转换成二叉树的特点：树是n个结点的有限集合或者由m个不相交的子树组成
二叉树是n个结点的有限集合或者一个结点和2个左右子树二叉树组成
深度为k的完全二叉树至少有（2k-1 ）个结点，至多有（2k -1 ）个结点，具有n个结点的完全二叉树按层序从1开始编号，则编号最小的叶子的序号是（2k-2+1）。
11.二叉树的遍历方法：
前序遍历：+A*BC（A+B*C）
中序遍历：A+B*C
后序遍历：ABC*+
某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（CDBGFEA ）。
【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来
12.1．证明：对任一满二叉树，其分枝数B＝2(n0-1) 。（其中，n0为终端结点数）
【解答】因为在满二叉树中没有度为1的结点，所以有：
n=n0+n2
设B为树中分枝数，则
n=B+1
所以
B=n0 +n2-1
再由二叉树性质：
n0=n2+1
代入上式有：
B=n0+n0-1-1=2(n0-1)
2.已知二叉树的中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，试构造该二叉树。
【解答】二叉树的构造过程如图5-12 所示。
13.哈夫曼树的构造，
对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。
【解答】构造的哈夫曼树如图5-13所示
树的带权路径长度WPL为：
WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2
=120
14.哈夫曼树的特点：它是带权路径长度WPL最小的二叉树！
15.哈夫曼编码，前缀编码，
最小生成树：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图联通的最少的边。
Prim算法：
求最小生成树的谱里姆算法
#include
using namespace std;
const int n=6;
const int e=10;
class edgeset
{public :
int front;
int end;
int weight;};
class tree
{public :
int s[n+1][n+1]; edgeset ct[n+1];
void prim(tree &t)
{
int i,j,k,min,t1,m,w;
for(i=1;i {t.ct[i].front=1; t.ct[i].end=i+1; t.ct[i].weight=t.s[1][i+1];} for(k=2;k<=n;k++) {min=32767; m=k-1; for(j=k-1;j if(t.ct[j].weight m=j;} edgeset temp=t.ct[k-1]; t.ct[k-1]=t.ct[m]; t.ct[m]=temp; j=t.ct[k-1].end; for(i=k;i {t1=t.ct[i].end; w=t.s[j][t1]; if(w {t.ct[i].weight=w; t.ct[i].front=j;}}}} }; void main () {int j,w;tree t; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j)t.s[i][j]=0; else t.s[i][j]=32767; for(int k=1;k<=e;k++) {cout<<"输入一条边及边上的权值"; cin>>i>>j>>w; cout< t.s[i][j]=w; t.s[j][i]=w;} t.prim(t); for(i=1;i {cout< } 克鲁斯卡尔算法：#include #include #define MAXEDGE 30 /*MAXEDGE为最大的边数*/ struct edges /*边集类型,存储一条边的起始顶点bv、终止顶点tv和权w*/ { int bv,tv,w; }; typedef struct edges edgeset[MAXEDGE]; int seeks(int set[],int v) { int i=v; while (set[i]>0) i=set[i]; return(i); } kruskal(edgeset ge,int n,int e) /*ge表示的图是按权值从小到大排列的*/ { int set[MAXEDGE],v1,v2,i,j; for (i=1;i<=n;i++) set[i]=0; /*给set中的每个元素赋初值*/ i=1; /*i表示待获取的生成树中的边数,初值为1*/ j=1; /*j表示ge中的下标,初值为1*/ while (j v1=seeks(set,ge[i].bv); /*确定顶点v所在的连通集*/ v2=seeks(set,ge[i].tv); if (v1!=v2) /*当v1,v2不在同一顶点集合,确定该边应当选入生成树*/ { printf("(%d,%d)\n",ge[i].bv,ge[i].tv); //cout<< < set[v1]=v2; j++; } i++; } } void main() { int n=7,e=10; edgeset mx; mx[1].bv=4;mx[1].tv=6;mx[1].w=30; mx[2].bv=2;mx[2].tv=5;mx[2].w=40; mx[3].bv=4;mx[3].tv=7;mx[3].w=42; mx[4].bv=3;mx[4].tv=7;mx[4].w=45; mx[5].bv=1;mx[5].tv=2;mx[5].w=50; mx[6].bv=4;mx[6].tv=5;mx[6].w=50; mx[7].bv=3;mx[7].tv=4;mx[7].w=52; mx[8].bv=1;mx[8].tv=3;mx[8].w=60; mx[9].bv=2;mx[9].tv=4;mx[9].w=65; mx[10].bv=5;mx[10].tv=6;mx[10].w=70; printf("最小生成树边集:\n "); kruskal(mx,n,e); } 16.邻接矩阵、邻接表：1图的存储结构主要有两种，分别是（邻接矩阵）和（邻接表）。 2已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（Ｏ(n+e)）【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 3对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（Ｏ(n2) ），利用Kruskal算法求最小生成树的时间复杂度为（Ｏ(elog2e) ）。 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集 数组做存储结构，适合于求稀疏图的最小生成树。 证明：生成树中最长路径的起点和终点的度均为１。 4【解答】用反证法证明。 设v1, v2, …, vk是生成树的一条最长路径，其中，v1为起点，vk为终点。若vk的度为2，取vk的另一个邻接点v，由于生成树中无回路，所以，v在最长路径上，显然v1, v2, …, vk , v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。 同理可证起点v1的度不能大于1，只能为1 17.最短路径 18.图6-7所示是一个无向带权图，请分别按Prim算法和Kruskal算法求最小生成树。 19. 20.【解答】按Prim算法求最小生成树的过程如下： 21. 22. 23.按Kruskal算法求最小生成树的过程如下： 24. 25. 26.9．对于图6-8所示的带权有向图，求从源点v1到其他各顶点的最短路径。 【解答】从源点v1到其他各顶点的最短路径如下表所示。 源点终点最短路径长度 v 1 v7 v1 v7 7 v1 v5 v1 v5 11 v1 v4 v1 v7 v4 13 v1 v6 v1 v7 v4 v6 16 v1 v2 v1 v7 v2 22 v1 v3 v1 v7 v4 v6 v3 25 在一个具有n 个顶点的有向完全图中包含有（n(n-1)）条边 拓扑排序及特点: 某图的表示意如下，按拓扑排序算法，写出电脑输出的拓扑排序结果 0: ->5->2->1^ 1: ->4->3->2^ 2: ->3^ 3: ->4^ 4: ^ 5: ->4^ 解：拓扑排序说白了就是依次遍历没有前驱节点的节点。 分析：这6个节点中，最早是0没有前驱，所以先遍历0； 去掉0节点和他的指针向量后，发现1和5都没有前驱，这个时候看你的程序怎么写了，不过就此题来说，你可以随便取一个，1也行，5也行，我先取1吧； 去掉1和他的指针向量，发现2和5都没前驱，同上，我选2； 照上面一次做下去，最后得到： 0-1-2-3-5-4 当然：0-1-5-2-3-4 0-1-2-5-3-4 0-5-1-2-3-4也都对。 27.顺序查找技术适合于存储结构为（顺序存储和链接存储）的线性表，而折半查找技术适用于存储结构为（顺序存储）的线性表，并且表中的元素必须是（按关键码有序） 27.折半查找的条件：顺序查找技术适合于存储结构为（顺序存储和链接存储）的线性表，而折半查找技 术适用于存储结构为（条件1顺序存储）的线性表，并且表中的元素必须是（条件2按关键码有序） 28.查找成功或失败的查找次数：平均查找长度为O（log2 n） 29.在散列技术中，处理冲突的两种主要方法是（开放定址法）和（拉链法） ⑷长度为20的有序表采用折半查找，共有（4）个元素的查找长度为3。 【解答】【分析】在折半查找判定树中，第3层共有4个结点。 30.排序算法的稳定性：直接插入排序、起泡排序、简单选择排序和归并排序是稳定的排序方法；希尔排 序和快速排序、堆排序是最不稳定的排序方法。 下述排序方法中，比较次数与待排序记录的初始状态无关的是（C ）。 A插入排序和快速排序B归并排序和快速排序 C选择排序和归并排序D插入排序和归并排序 【分析】选择排序在最好、最坏、平均情况下的时间性能均为O(n2)，归并排序在最好、最坏、平均情况下的时间性能均为O(nlog2n)。 31.快速排序一次划分：如果待排序记录中只有一组具有相同关键码的记录，而选择的轴值恰好是这组相 同关键码的一个，这时快速排序是稳定的 32.堆排序、归并排序：时间复杂度都是O（nlog2 n） 1对初始状态为递增有序的序列进行排序，最省时间的是（B ），最费时间的是（C）。已知待排序序列中每个元素距其最终位置不远，则采用（B）方法最节省时间。 A 堆排序B插入排序C快速排序D 直接选择排序 【分析】待排序序列中每个元素距其最终位置不远意味着该序列基本有序。 2当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（A ），就平均时间而言，（D ）最佳。 A 直接插入排序 B 起泡排序C简单选择排序D快速排序 3设有5000个元素，希望用最快的速度挑选出前10个最大的，采用（B堆排序）方法最好。 A快速排序B堆排序C希尔排序D 归并排序 33.散列技术处理冲突的方法：链表法和开放地址法 产生冲突的原因：散列地址不同的结点争夺同一个后继散列地址的现象称为聚集或堆积(Clustering)。 这将造成不是同义词的结点也处在同一个探查序列之中，从而增加了探查序列的长度，即增加了查找时间 34.用链接法处理冲突及平均查找长度的计算： 已知关键码序列为（Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空间为0~16，设散列函数为H(x)=，其中i为关键码中第一个字母在字母表中的序号，采用线 性探测法和链地址法处理冲突，试分别构造散列表，并求等概率情况下查找成功的平均查找长度。 【解答】H(Jan)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Jun)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用线性探测法处理冲突，得到的闭散列表如下： 平均查找长度=(1+1+1+1+2+4+5+2+3+5+6+1)/12=32/12 采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=(1×7+2×4+3×1)/12=18/12 36所有的实验代码 在数组中求最小值算法： int ArrayMin(int a[],int n) { Min=a[0]; For (i=1;i If(a[i] Return min; } 顺序查找算法： Int Find(int A[],int n ,int k) { Count=0; For(i=0;i If (++count&&A[i]==k)break; Cout<<”比较次数为”< Return i; } 汉诺塔算法Hanoi： V oid Hanoi(int A,int B,int C) { if(n==1)cout<<”A→C”; else{ Hanoi(n-1,A,C,B); cout<<”A→C”; Hanoi(n-1,B,A,C); } } 二叉树前序遍历递归算法： Template V oid PreOrder(TNode { if(root==NULL)return; else{ cout< PreOrder(root->firstchaild); PreOder(root->rightsib); } } 二叉树叶子结点个数算法： V oid CountLeaf(BiNode if(root!=NULL) { if( root->lchild==NULL&&root->rchild ==NULL) count++; Countleaf(root->lchild,count); Count leaf(root->rchild,count); } 二叉树的构造函数算法BiTree Template BiTree::BiTree(BiNode { root=creat(); } template BiNode { cin>>ch; if(ch==’#’)return NULL; else{ root=new BiNode(T); root->data=ch; root->lchild=Creat(); root->rchild=Creat(); } } 填空题 1.文件可按其记录的类型不同而分成两类，即( 操作系统文件 )和( 数据库 )文件。 2.数据库文件按记录中关键字的多少可分成( 单关键字文件 )和( 多关键字文件 )两种文件。 3.文件由( 记录 )组成，记录由( 数据项 )组成。 4.从用户观点看，文件的逻辑结构通常可以区分为两类：一类是如dBASE中数据库文件那样的文件组织结构，称为( 数据库 )文件；另一种是诸如用各种文字处理软件编辑成的文本文件，称为( 文本 )文件。 从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即( 顺序组织 )、 ( 随机组织 )、( 链组织 )。 B+树适用于组织( 随机组织 )的索引结构， m阶B+树每个结点至多有( m ) 除根结点外每个结点至少有( (m/2)向上取整 )个儿子，根结点至少有( 2 )个儿子，有k个儿子的结点必有( k )个关键码。 5.物理记录之间的次序由指针相链表示的顺序文件称为( 串联文件) 6.顺序文件中，要存取第I个记录，必须先存取( 第I-1 )个记录。 7.索引顺序文件既可以顺序存取，也可以( 随机 )存取。 8.建立索引文件的目的的( 提高查找速度 )。 9.索引顺序文件是最常用的文件组织之一，通常用( 树 )结构来组织索引。 10.倒排文件的主在优点在于( 检索记录块 )。 11.检索是为了在文件中满足一定条件的记录而设置的操作。检索可以按( 关 键字 )检索，也可以按( 记录号 ) 检索； 按( 记录号 ) 检索又可以有( 顺序 ) 检索和( 直接 ) 检索。 12.哈希检索的技术的关键是( 构造哈希函数 )和( 解决冲突的方法 )。结构来组织索引。 13.VSAM系统是由( 索引集 )、( 顺序集 ) 、( 数据集 )构成的。 14.VSAM( 虚拟存储存取方法 )文件的优点是：动态地( 分配和释放存储空间 ) ，不需要文件进行( 重组 ) ，并能较快地( 对插入的记录 ) 进行查找。 一～五章选择题 一 1.学习数据结构的主要目的是( C )。 A．处理数据计算问题 B．研究程序设计技巧 C．选取合适数据结构，写出更有效的算法 D．是计算机硬件课程的基础2.数据结构是一门研究非数值计算的程序设计问题中计算机的逻辑存储以及 它们之间的( B )和运算的科学。 A．结构 B．关系 C．运算 D．算法 3.在计算机中存储一个数据元素的位串称为 ( A ) 。 A. 结点 B. 数据项 C. 数据字段 D. 字符串 4.算法指的是( C ) A.计算机程序 B.排序算法 C.解决问题的有限运算序列 D.解决问题的计算方法 5.( D )是数据不可分割的最小单位。 A．数据结构 B．数据对象 C．数据元素 D．数据项 6.数据结构有 ( D ) 种基本逻辑结构。 A. 1 B. 2 C. 3 D. 4 7.在数据结构中，从逻辑上可以把数据结构分成( C )。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 8.通常所说的时间复杂度是指( B )。 框架结构毕业设计任务书和指导书 1 2020年4月19日 毕业设计基本要求 1目的 （1）综合运用所学专业理论知识与设计技能，处理建筑设计中有关方针、政策、功能、经济、安全、美观等方面的问题。解决总体、单体、空间等关系，以创造富有时代气息的优美建筑形象与环境。依据建筑设计完成结构体系的布置、结构在各种荷载工况下的计算、构造和施工图。 （2）掌握一般建筑工程的设计思路，进而举一反三熟悉有关建筑工程的设计、施工、预算等建设过程。为即将走上工作岗位奠定基础。 （3）学以致用，学习科学技术和技能的目的是应用。一个工程师在设计、建设实际工程中应具备的知识，都是我们在毕业设计中应予以加强的。因此深切领悟总体概念设计、掌握具体理论设计和实际工程技术处理措施的结合作为重点来训练。 （4）树立正确的设计思想，全面对待建筑与结构的关系， 2 2020年4月19日 培养勤奋、严谨、认真的工作作风及分析解决一般工程技术问题的能力。 （5）掌握调查研究、理论联系实际的学习方法，养成既能独立思考，又能相互配合密切合作的工作态度。 （6）使学生对一般工业与民用建筑的土建设计的内容和构成有比较全面的了解，并熟悉有关设计标准、规范、手册和工具书，增强毕业后到生产第一线工作的适应能力。 2成果形式及要求 （1）计算书和说明书： 字数应不少于1万字，书写要工整，字迹要清楚，可采用计算机打印。计算书内容要阐明设计依据或标准，方案构思、特点、必要的经济指标，结构选型、构造处理、材料特点及计算上的主要问题，还应包括结构计算全过程，计算要正确、完整、思路清晰、简图明了。计算书格式：应严格按照毕业设计手册中的要求。 （2）图纸： 3 2020年4月19日 .. ;.. 第一章 概论 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 数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。 《数据结构》期末考试题型及分值 （1）简答题6题*5分=30分简要回答要点 （2）分析题6题*5分=30分给出结果 （3）设计题1题*10分=10分设计思想及结果 （4）编程题1题*10分=10分完整代码 （5）综合题1题*20分=20分抽象数据类型的定义、表示、实现、算法分析{定义=功能（ADT）表示=存储结构体实现=算法（基本操作）算法分析=时间、空间复杂度} 考试概念有：1.数据结构{一、线性表（栈-队-列-串-数组-广义表-逻辑结构-存储结构-运算结构） 二、非线性表（集合-树-图）} 2.抽象数据类型数据对象-数据关系-基本操作 3.算法性质-要求（设计）-效率（度量） 4.实例查找：高效查找算法 排序：高效的排序算法 分析题考试题目参考 （1）1-2-3-4-5-6顺序建BBST （2）6-5-4-3-2-1顺序建BBST 简答题实例 设计题： （1） （2） 数据结构试卷（一） 三、计算题（每题6分，共24分） 1. 在如下数组A 中链接存储了一个线性表，表头指针为A[0].next ，试写出该线性表。 A01234567 dat a 60 50 78 90 34 40 nex t 3 5 7 2 0 4 1 线性表为：（78，50，40，60，34，90）??????? ?????????01110 10 1 11101 11010101110 2. 请画出下图的邻接矩阵和邻接表。 3. 已知一个图的顶点集V 和边集E 分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20 4.画出向小根堆中加入数据4,2,5,8,3时，每加入一个数据后堆的变化。见图12 图12 图11 四、阅读算法（每题7分，共14分） 4 4 4 4 4 2 2 2 5 5 5 2 2 8 8 4 3 5 2 8 3 4 框架结构设计步骤及要点 1. 结构设计说明： 主要是设计依据，抗震等级，人防等级，地基情况及承载力，防潮抗渗做法，活荷载值，材料等级，施工中的注意事项，选用详图，通用详图或节点，以及在施工图中未画出而通过说明来表达的信息。如混凝土的含碱量不得超过3kg/m3等等。 2. 各层的结构布置图：包括: (1).预制板的布置(板的选用、板缝尺寸及配筋)。标注预制板的块数和类型时, 不要采用对角线的形式。因为此种方法易造成线的交叉, 宜采用水平线或垂直线的方法, 相同类型的房间直接标房间类型号。应全楼统一编号，可减少设计工作量，也方便施工人员看图。板缝尽量为40, 此种板缝可不配筋或加一根筋。布板时从房间里面往外布板, 尽量采用宽板, 现浇板带留在靠窗处, 现浇板带宽最好≥200(考虑水暖的立管穿板)。如果构造上要求有整浇层时, 板缝应大于60。整浇层厚50, 配双向φ6250, 混凝土C20。纯框架结构一般不需要加整浇层。构造柱处不得布预制板。地下车库由于防火要求不可用预制板。框架结构不宜使用长向板，否则长向板与框架梁平行相接处易出现裂缝。建议使用PMCAD的人工布板功能布预制板，自动布板可能不能满足用户的施工图要求，仅能满足定义荷载传递路线的要求。 (2).现浇板的配筋(板上、下钢筋，板厚尺寸)。板厚一般取120、140、160、180四种尺寸或120、150、180三种尺寸。尽量用二级钢包括直径φ10（目前供货较少）的二级钢，直径≥12的受力钢筋，除吊钩外，不得采用一级钢。钢筋宜大直径大间距，但间距不大于200，间距尽量用200。(一般跨度小于6.6米的板的裂缝均可满足要求)。跨度小于2米的板上部钢筋不必断开，钢筋也可不画，仅说明钢筋为双向双排钢筋多少上下钢筋间距宜相等，直径可不同，但钢筋直径类型也不宜过多。顶层及考虑抗裂时板上筋可不断，或50%连通，较大处附加钢筋，拉通筋均应按受拉搭接钢筋。板配筋相同时，仅标出板号即可。一般可将板的下部筋相同和部分上部筋相同的板编为一个板号，将不相同的上部筋画在图上。当板的形状不同但配筋相同时也可编为一个板号。应全楼统一编号。当考虑穿电线管时，板厚≥120，不采用薄板加垫层的做法。电的管井电线引出处的板，因电线管过多有可能要加大板厚至180（考虑四层32的钢管叠加）。宜尽量用大跨度板，不在房间(尤其是住宅)加次梁。说明分布筋为φ8200。板顶标高不同时，板的上筋应分开或倾斜通过。现浇挑板阳角加辐射状附加筋(包括墙上的阳角)。现浇挑板阴角的板下宜加斜筋。顶层应建议甲方采用现浇楼板，以利防水，并加强结构的整体性及方便装饰性挑沿的稳定。外露的挑沿、雨罩、挑廊应每隔10～15米设一10mm的缝，钢筋不断。尽量采用现浇板，不采用予制板加整浇层方案。卫生间做法可为70厚+10高差(取消垫层)。8米以下的板均可以采用非预应力板。L、T或十字形建筑平面的阴角处附近的板应现浇并加厚，双向双排配筋，并附加45度的4根16的抗拉筋。现浇板的配筋建议采用PMCAD软件自动生成，一可加快速度，二来尽量减小笔误。自动生成楼板配筋时建议不对钢筋编号，因工程较大时可能编出上百个钢筋号，查找困难，如果要编号，编号不应出房间。配筋计算时，可考虑塑性力重分布，将板上筋乘以0.8~0.9的折减系数，将板下筋乘以1.1~1.2的放大系数。值得注意的是，按弹性计算的双向板钢筋是板某几处的最大值，按此配筋是偏于保守的，不必再人为放大。支承在外圈框架梁上的板负筋不宜过大，否则将对梁产生过大的附加扭距。一般：板厚>150时采用φ10200；否则用φ8200。PMCAD生成的板配筋图应注意以下几点：1.单向板是按塑性计算的，而双向板按弹性计算，宜改成一种计算方法。 2.当厚板与薄板相接时，薄板支座按固定端考虑是适当的，但厚板就不合适，宜减小厚板支座配筋，增大跨中配筋。 3.非矩形板宜减小支座配筋， .资料. . . 一、是非题 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 第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（） 框架结构设计的技术措施探析 摘要：钢筋混凝土的框架结构由四部门组成，分别是楼板、柱、梁以及基础承重构件。在允许的高度情况下，框架结构的设计需要提供较大的空间，来适合多种使用功能的要求。被人们广泛的应用于工业多层厂房以及仓库中。本文从现浇板截面及配筋、人工调整框架节点配筋及填充墙、框架柱模板结构设计、强化建筑物框架结构设计的管理措施、框架结构设计中的其他问题五个方面进行了框架结构设计技术的探析说明。 关键词：框架；结构设计；技术探析 abstract: the reinforced concrete frame structure composed by four departments, respectively is floor, column, beam and foundation bearing component. at the height of the allowed, frame structure design need to provide larger space, to suit a variety of use function requirements. is widely used in the industry of multi-story factory buildings and warehouse. this paper, from the site casting integrated section and reinforcement, artificial adjustment framework node reinforcement and fill walls, frame column template structure design, strengthen the building of the frame structure design management measures, frame structure design of the other problem five on the frame structure design technology analysis shows.数据结构复习题总结
框架结构毕业设计任务书和指导书范本
大学数据结构期末知识点重点总结(考试专用)
(完整版)非常实用的数据结构知识点总结
数据结构期末考试复习总结,DOC
框架结构设计步骤及要点
2010级数据结构期末复习题(E)
数据结构复习要点(整理版).docx
《数据结构》期末考试题带答案(99%能过)
框架结构设计的技术措施
相关主题
文本预览