数据结构（C语言版）期末复习汇总
第一章绪论
数据结构：是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。
数据结构分为：逻辑结构、物理结构、操作三部分
逻辑结构：集合、线性结构、树形结构、图（网）状结构
物理结构（存储结构）：顺序存储结构、链式存储结构
算法：是为了解决某类问题而规定的一个有限长的操作序列。
算法五个特性：有穷性、确定性、可行性、输入、输出
评价算法优劣的基本标准（4个）：正确性、可读性、健壮性、高效性及低存储量
语句频度的计算。
算法的时间复杂度：
常见有：O(1)，O(n)，O(n2)，O(log2n)，O(nlog2n)，O(2n)
第二章线性表
线性表的定义和特点：
线性表：由n(n≥0)个数据特性相同的元素构成的有限序列。线性表中元素个数n(n≥0)定义为线性表的长度，n=0时称为空表。
非空线性表或线性结构，其特点：
（1）存在唯一的一个被称作“第一个”的数据元素；
（2）存在唯一的一个被称作“最有一个”的数据元素；
（3）除第一个之外，结构中的每个数据元素均只有一个前驱；
（4）除最后一个之外，结构中的每个数据元素均只有一个后继。
顺序表的插入：共计n个元素，在第i位插入，应移动（n-i+1）位元素。
顺序表的删除：共计n个元素，删除第i位，应移动（n-i）位元素。
线性表的两种存储方式：顺序存储、链式存储。
顺序存储
概念：以一组连续的存储空间存放线性表；
优点：逻辑相邻，物理相邻；可随机存取任一元素；存储空间使用紧凑；
缺点：插入、删除操作需要移动大量的元素；预先分配空间需按最大空间分配，利用不充分；表容量难以扩充；
操作：查找、插入、删除等
查找：
ListSearch(SqlList L,ElemType x,int n)
{
int i;
for (i=0;i {if(x==L .elem[i]) break; } if(i==n) return(0); else return(i+1); }//ListSearch 删除： ListDelete(SqlList &L,int i,ElemType &e) { if (i<1||i>L.length) return ERROR; //i值不合法 p=&(L.elem[i-1]); //p为被删除元素的位置 e=*p; //被删除元素的值赋给e q=L.elem+L.length-1 //表尾元素的位置 for(++p;p<=q;++p) *(p-1)=*p; //被删除元素之后的元素左移 --L.length; //表长减1 return e; }//ListDelete 插入： ListInsert(SqlList &L, int i, ElemType e) { if (i<1||i>L.length+1) return ERROR; //i值不合法。 if (L.length>=Listsize) //当前存储空间已满，增加分配 { newbase=(ElemType*)realloc(L.elem,(L.Listsize+LISTINCREMENT)*sizeof(ElemType)); //realloc(void * p,unsigned size)该函数将p所指出的已分配内存区的大小改为size, size可以比原来分配的空间大或小// If (!newbase) exit(OVERFLOW); //存储分配失败 L.elem=newbase; //新基址 L.Listsize+=LISTINCREMENT; );//增加存储容量 } q=&(L.elem[i-1]); //q为插入位置 for(p=&L. elem[L.length-1];p>=q;- - p) *(p+1)=*p; //插入位置之后的元素右移 *q=e; //插入e ++L.length; //表长增加1 return OK; }//ListInsert 单链表——线性表的链式存储结构之一 概念：线性链表又称单链表，结点：数据域，指针域；头指针，头结点。 单链表特点： 用指针表示数据之间的逻辑关系（逻辑相邻的元素物理位置不一定相邻）。 它是一种动态结构，不需预先分配空间； 不足：指针占用额外存储空间；不能随机存取，查找速度慢。 节点定义：“数据+ 指针” typedef struct LNode { DataType data; struct LNode *next; } LNode, *LinkList; 单链表的插入： 元素x 结点应预先生成： S=(test*)malloc(m); S->data=x; S->next=p->next p->next=s 单链表删除： q = p->next; //保存b 的指针，靠它才能指向c p->next=q->next; //a 、c 两结点相连 free(q) ； //删除b 结点，彻底释放 线性表的应用： (1)：用单链表结构存放26个英文字母组成的线性表（a ，b ，c ，…，z ）,请写出C 语言程序。 #include /*将全局变量及函数提前说明：*/ typedef struct liu{ char data; struct liu *next; }test; test *p,*q,*head; //一般需要3个指针变量 int n ; // 数据元素的个数 int m=sizeof(test); /*结构类型定义好之后，每个变量的长度就固定了，m 求一次即可*/ void build( ) //字母链表的生成。要一个一个链入 { int i; p=(test*)malloc(m); //m=sizeof(test) 前面已求出 head =p; //头指针，没有头结点 for(i=1;i<26;i++) //因尾结点要特殊处理，故i≠26 { p->data=i+‘a’-1; // 第一个结点值为字符a p->next=(test*)malloc(m); //为后继结点开新空间！ p=p->next；//让指针变量P改为指向后继结点 } p->data=i+‘a’-1; //最后一个元素要单独处理 p->next=NULL ; //单链表尾结点的指针域要置空！ } void display()/*字母链表的输出*/ { p=head; while (p) /* 只要没到最后一个元素，就不停地“顺藤摸瓜”输出*/ { printf("%c",p->data); p=p->next; } } （2）线性表的合并：(顺序储存结构) 算法2.1：LA=(7,5,3,11) LB=(2,6,3) 合并后LA=(7,5,3,11,2,6) 算法思想：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。只要从线性表LB中依次取得每个数据元素，并依值在线性表LA中进行查访，若不存在，则插入之。 void union(List &LA, List &LB)//主函数，参数为两个线性表 { La_len = ListLength(LA); // 求得线性表LA 的长度 while (!ListEmpty(LB)) // 依次处理LB 中元素直至LB 为空表止 { ListDelete(LB,1,e); // 从LB 中删除第1个数据元素并赋给e if (!LocateElem(LA,e,equal( )) ListInsert(LA,++La_len,e); // 当LA中不存在和 e 值相同的数据元素时进行插入 } // DestroyList(LB);// 销毁线性表LB } // union 第三章栈和队列 栈的类型定义： 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。 假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。即，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。 栈的进栈（push）操作： Status Push(Stack &S, SElemType e){ //插入元素e为新的栈顶元素 if (S.top-S.bottom>=S.stacksize){//栈满，追加存储空间 S.bottom=(SElemType)realloc(S.bottom,(S.stacksize+STACKINCREMENT)*sizeof(ElemType)); if (!S.bottom) exit(overflow); //存储分配失败 S.top=S.bottom+S.stacksize; //设置新栈的栈顶 S.stacksize+=STACKINCREMENT;} //设置新栈的大小 *S.top++=e; //先赋值，后加1 Return OK; }//Push 出栈（pop）操作： Status Pop(Stack &S, SElemType &e){ //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if (S.top==S.bottom) Return ERROR; S.top-- ; e=*S. top ; Return OK; }//Pop 进栈、出栈顺序： 对于一个栈，给出输入项A、B、C，如果输入项序列由ABC组成，试给出所有可能的输出序列。 A进A出B进B出C进C出ABC A进A出B进C进C出B出ACB A进B进B出A出C进C出BAC A进B进B出C进C出A出BCA A进B进C进C出B出A出CBA 不可能产生输出序列CAB 栈的应用：数值转换 算法思想：首先将按照上述计算过程中得到的八进制数的各位依次进栈，然后将栈中的八进制数依次出栈输出，输出结果就是该是十进制数转换得到的八进制数。 N=(N div d)×d + N mod d （其中：div 为整除运算，mod 为求余运算） 例如(1348)10=(2504)8，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 算法：void conversion(int n , int d) /*将十进制整数N转换为d(2或8)进制数*/ { SqStack S ; int k, *e ; //建立堆栈S S=Init_Stack(); //堆栈S初始化 while (n>0) { k=n%d ; push(S , k) ; n=n/d ; } /* 求出所有的余数，进栈*/ while (S.top!=0) /* 栈不空时出栈，输出*/ { pop(S, e) ; printf(“%1d” , *e) ; } } 队列的类型定义： 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)：允许插入的一端 队头(front)：允许删除的一端 队列特点：先进先出 ( FIFO ) 队列储存结构：顺序队、链队 顺序队列操作： 插入： insertseq(Sequeue *q,Elemtype x) {/*将元素x 插入到队列q 中，作为q 的新队尾，即入队操作*/ if (q->rear>Maxsize-1) return FALSE; /*队列满*/ else { q->data[q->rear]=x; //先插入数据 q->rear++; //再移动指针 return TRUE; } }//insertseq 删除： Elemtype deleteseq(Sequeue *q) {/*若队列q 不为空，则删除队头元素，即出队列操作*/ Elemtype x; //定义数据元素变量，存放删除元素 if (q->rear= =q->front) return NULL; //队列空 else { x=q->data[q->front]; //先删除数据 q->front++; //再移动指针 return x; } }//deleteseq 循环顺序队插入、删除分析： (c) BC 入队 front (b) A 入队 front front (a) 初始状态 front=rear=0 (d) A 出队 (f) DEFG 入队 第四章 串 串的类型定义：串是字符串的简称。它是一种在数据元素的组成上具有一定约束条件的线性 表，即要求组成线性表的所有数据元素都是字符，所以，人们经常又这样定义串：串是一个有穷字符序列。 串一般记作： s= “a1a2...an” (n≥0) 其中，s 是串的名称，用双引号“”括起来的字符序列是串的值；ai 可以是字母、数字或其他字符；串中字符的数目n 被称作串的长度。当n=0时，串中没有任何字符，其串的长度为0，通常被称为空串，由空格组成的字符串叫空白串。 子串、主串：串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。 串操作： StrAssign(&T, chars) // 串赋值，生成值为chars 的串T StrCompare(S,T) // 串比较，若S>T ，返回值大于0… StrLength(S) // 求串长，即返回S 的元素个数 Concat(&T, S1, S2) // 串连接，用T 返回S1＋S2的新串 SubString(&Sub, S, pos, len) // 求S 中pos 起长度为len 的子串 Index(S, T, pos) // 返回子串T 在pos 之后的位置 Replace(&S, T,V) // 用子串V 替换子串T 第五章 树和二叉树 树的定义： 树(tree)是n(n≥0)个结点的有限集T ，其中： 有且仅有一个特定的结点，称为树的根(root)； 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm ，其中每一个集合本身又是一棵树，称为根的子树(subtree)。 特点： 树中至少有一个结点：根 树中各子树是互不相交的集合 结点(node) ：表示树中的元素，包括数据元素及若干指向其子树的分支 结点的度(degree) ：结点拥有的子树数 树的度：一棵树中最大的结点度数 叶子(leaf) ：度为0的结点（终端结点） 孩子(child) ：结点子树的根称为该结点的~~ 双亲(parents) ：孩子结点的上层结点叫该结点的~~ 兄弟(sibling) ：同一双亲的孩子 子孙：以某结点为根的子树中的所有结点都被称为是该结点的~~ 祖先：从根结点到该结点路径上的所有结点 堂兄弟：双亲在同一层的结点互为~~ 结点的层次(level) ：从根结点算起，根为第一层，它的孩子为第二层…… 深度(depth) ：树中结点的最大层次数 森林(forest) ：棵互不相交的树的集合 有序树、无序树：如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树 二叉树的定义： 二叉树是n(n≥0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。 特点 每个结点至多有二棵子树(即不存在度大于2的结点)； 二叉树的子树有左、右之分，且其次序不能任意颠倒。 二叉树的性质： 性质1：在二叉树的第i层上最多有2i-1个结点（i≥1）； 性质2：深度为K的二叉树最多有2K-1个结点（K≥1）； 性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1；完全二叉树 定义：一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1~n的结点位置一一对应，则称这棵二叉树为完全二叉树。 特点： 叶子结点只可能在层次最大的两层上出现; 对任一结点，若其右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L或L+1。 （其中，?log2n?的结果是不大于log2n 性质4：具有n个结点的完全二叉树的深度为?log2n?+1。 的最大整数。） 性质5：对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号， 则对任意一个结点i （1≤i≤n），都有： （1）如果i=1，则结点i是这棵完全二叉树的根，没有双亲。否则其双亲结点的编号为?i/2?；（2）如果2i>n，则结点i没有左孩子。否则其左孩子结点的编号为2i； （3）如果2i+1>n，则结点i没有右孩子。否则其右孩子结点的编号为2i+1。 二叉树遍历： 先序遍历：先访问根结点,然后分别先序遍历左子树、右子树【包络法】 中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树【垂直映射法】 后序遍历：先后序遍历左、右子树，然后访问根结点Array例： 先序遍历：a b d e g h c f 中序遍历：d b g h e a f c 后序遍历：d h g e b f c a 层次遍历：a b c d e f g h 根据遍历结果恢复二叉树的条件（先序加中序或者中序加后序） 输出二叉树的节点 DLR( x *root ) { if (root !=NULL) //非空二叉树 { printf(“%d”,root->data); //访问D, printf可以为其他函数 DLR(root->lchild); //递归遍历左子树 DLR(root->rchild); //递归遍历右子树 } return(0); } 输出二叉树的叶子节点： DLR(x *root ) /* 先序遍历输出叶子结点*/ { if (root!=NULL) /*root为指向二叉树根结点的指针*/ { if (root ->lchild==NULL && root ->rchild==NULL) pri ntf(“%d”,root->data); /* 输出叶子结点*/ DLR(root ->lchild); /* 先序遍历左子树*/ DLR(root ->rchild); /* 先序遍历右子树*/ } } 统计二叉树叶子节点数： DLR(x *root) //采用先序遍历的递归算法 { if ( root!=NULL ) //非空二叉树条件，还可写成if(root) { if(!root->lchild&&!root->rchild) //是叶子结点则统计并打印 sum++; //统计叶子节点数 DLR(root->lchild); //递归遍历左子树，直到叶子处； DLR(root->rchild); } //递归遍历右子树，直到叶子处； } return(0); } 霍夫曼树、霍夫曼编码: 例：W={ 5，29，7，8，14，23，3，11 } 第六章图 图的定义：图(Graph)：图G是由两个集合V(G)和VR(G)组成的,记为：G=(V,VR) 其中：V(G)是顶点的非空有限集；VR(G)是边的有限集合，边是顶点的无序对或有序对。 有向图，无向图 顶点的度：无向图中，顶点的度为与每个顶点相连的边数； 有向图中，顶点的度分成入度与出度 入度：以该顶点为头的弧的数目 出度：以该顶点为尾的弧的数目 路径：路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)∈E 或 回路：第一个顶点和最后一个顶点相同的路径叫~ 简单路径：序列中顶点不重复出现的路径叫~ 简单回路：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫~ 连通：从顶点V到顶点W有一条路径，则说V和W是连通的 连通图：图中任意两个顶点都是连通的叫~ 连通分量：非连通图的每一个连通部分叫~ 强连通图：有向图中，如果对每一对Vi,Vj∈V, Vi∈Vj,从Vi到Vj 和从Vj到Vi都存在路径， 则称G是~ 邻接矩阵、邻接表： A B C D E 图的深度遍历： 方法：从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。 必须说明，若不给定存储结构，深度优先遍历的结果不唯一 。因为哪个顶点是第一邻接点未确定。给定存储结构后，深度优先遍历的结果是唯一的。 图的广度遍历： 方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。广度遍历：V1? V2 ?V3 ? V4 ?V5 ?V6 ?V7 ?V8 最小生成树： 同一个连通网的最小生成树可能是不唯一的，但其代价都是最小(唯一的)。 克鲁斯卡尔算法： 普里姆算法： 注意：拓扑排序的结果不一定是唯一的。如： ACBDE也是以上 DAG图的拓扑有序序列。AOE网，关键路径 AOE 网(活动在边上) ，边代表活动或任务，顶点代表事件。 事件i发生后，其后继活动a(i,*)都可以开始；只有所有先导活 动a(*,j)都结束后，事件j才发生。 关键路径算法 问题：a) 整个工程完工需要多长时间？b) 哪些活动影响工程的进度？求关键路径。 事件(顶点) i：最早发生时间ve(i)，最晚发生时间vl(i)； 活动(边) a(i,j)：最早开始时间e(i,j)，最晚开始时间l(i,j)。 于是，整个工程完工的时间就是终点的最早发生时间；关键路径就是路径长度最长的路径。例：某工程的AOE网如下，求1) 整个工程完工需要多长时间，2) 关键路径。 (a) 无向网 (b)-(e) 克鲁斯卡尔算法计算最小生成树 (g) 另一个可能的最小生成树 (f) 得到的最小生成树 分析：按照拓扑有序排列顶点，然后“从前往后”计算事件的最早发生时间得到总时间，再“从后往前”计算事件的最晚发生时间，最后计算活动的最早和最晚开始时间得到关键活动和关键路径。 (1) 工程完工需要时间14， (2) 关键路径是有3条：1→2→5→8→9，1→2→5→7→9，1→4→6→8→9。 最短路径：迪杰斯特拉算法 求一个顶点到其他各顶点的最短路径。 例：用迪杰斯特拉算法求下图中A 到其余顶点的最短路径。 第八章排序 排序主要做的工作:比较+ 移动 直接插入排序: 【13】, 6, 3, 31, 9, 27, 5, 11 【6, 13】, 3, 31, 9, 27, 5, 11 【3, 6, 13】, 31, 9, 27, 5, 11 【3, 6, 13，31】, 9, 27, 5, 11 【3, 6, 9, 13，31】, 27, 5, 11 【3, 6, 9, 13，27, 31】, 5, 11 【3, 5, 6, 9, 13，27, 31】, 11 【3, 5, 6, 9, 11，13，27, 31】 冒泡排序: 初态：21，25，49，25*，16，08 第1趟21，25，25*，16，08 ，49 第2趟21，25，16，08 ，25*，49 第3趟21，16，08 ，25，25*，49 第4趟16，08，21，25，25*，49 第5趟08，16，21，25，25*，49 快速排序： 原始序列：4938 65 97 76 13 27 49 一趟排序：2738 13 497697 65 49 二趟排序：13 2738 49 49 65 7697 三趟排序：13 27 38 49 49 65 76 97 “数据结构”期末考试试题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均 框架结构毕业设计任务书和指导书 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 框架结构设计步骤及要点 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.在线性表的顺序存储结构中，逻辑上相邻的两个元素在屋里位置上并不一定紧邻。错 误 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）个节点 《数据结构与算法》复习题 一、选择题。 1在数据结构中，从逻辑上可以把数据结构分为 C 。 A ?动态结构和静态结构B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2?数据结构在计算机内存中的表示是指_A_。 A .数据的存储结构B.数据结构 C .数据的逻辑结构 D .数据元素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的A结构。 A .逻辑 B .存储C.逻辑和存储 D .物理 4.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_C A .数据的处理方法 B .数据元素的类型 C.数据元素之间的关系 D .数据的存储方法 5.在决定选取何种存储结构时，一般不考虑A A .各结点的值如何C.对数据有哪些运算 B .结点个数的多少 D .所用的编程语言实现这种结构是否方 6.以下说法正确的是D A .数据项是数据的基本单位 B .数据元素是数据的最小单位 C.数据结构是带结构的数据项的集合 D .一些表面上很不相同的数据可以有相同的逻辑结构 7.算法分析的目的是 C ，算法分析的两个主要方面是 A 。 (1) A .找出数据结构的合理性B.研究算法中的输入和输出的关系 C .分析算法的效率以求改进C.分析算法的易读性和文档性 (2) A .空间复杂度和时间复杂度B.正确性和简明性 &下面程序段的时间复杂度是0( n2) s =0; for( I =0; i 框架结构设计的技术措施探析 摘要：钢筋混凝土的框架结构由四部门组成，分别是楼板、柱、梁以及基础承重构件。在允许的高度情况下，框架结构的设计需要提供较大的空间，来适合多种使用功能的要求。被人们广泛的应用于工业多层厂房以及仓库中。本文从现浇板截面及配筋、人工调整框架节点配筋及填充墙、框架柱模板结构设计、强化建筑物框架结构设计的管理措施、框架结构设计中的其他问题五个方面进行了框架结构设计技术的探析说明。 关键词：框架；结构设计；技术探析 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. 数据结构复习重点归纳 （适于清华严版教材） 一、数据结构的章节结构及重点构成 数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。 对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。 按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为：概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。 线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型算法设计题。如果有，也是与其它章节内容相结合。 栈和队列：基础章节，容易出基本概念题，必考内容之一。而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。 串：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的是根据KMP进行算法分析。 多维数组及广义表：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可选单元”或“侯补单元”。一般如果要出题，多数不会作为大题出。数组常与“查找，排序”等章节结合来作为大题考查。 树和二叉树：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。 图：重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。 查找：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。 排序：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。在基本概念的考查中，尤爱考各种排序算法的优劣比较此类的题。算法设计大题中，如果作为出题，那么常与数组结合来考查。 二、数据结构各章节重点勾划： 第0章概述本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意以下几点：数据结构的基本概念，时间和空间复杂度的概念及度量方法，算法设计时的注意事项。本章考点不多，只要稍加注意理解即可。 第一章线性表作为线性结构的开篇章节，线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念。 总体来说，线性表一章可供考查的重要考点有以下几个方面： 1.线性表的相关基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念。 2.线性表的结构特点，主要是指：除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。 3.线性表的顺序存储方式及其在具体语言环境下的两种不同实现：表空间的静态分配和动态分配。静态链表与顺序表的相似及不同之处。 4.线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。其中，单链表的归并算法、循环链表的归并算法、双 向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。此外，近年来在不少学校中还多次出现要求用递归算法实现单链表输出（可能是顺序也可能是倒序）的问题。 在链表的小题型中，经常考到一些诸如：判表空的题。在不同的链表中，其判表空的方式是不一样的，请大家注意。 5.线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储 结构的各自好处。 第二章栈与队列栈与队列，是很多学习DS的同学遇到第一只拦路虎，很多人从这一章开始坐晕车，一直晕到现在。所以，理解栈与队列，是走向DS高手的一条必由之路，。 学习此章前，你可以问一下自己是不是已经知道了以下几点： 1.栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据（请注意包括：存和取两部分）的特点。 2.递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib数列问题，hanoi问题，背包问题，二叉树的递归和非递归遍历问 题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。 3.栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查此为题目的算法设计题不多。 4.循环队列中判队空、队满条件，循环队列中入队与出队算法。 如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不看书，并不是可以不作题哦。 第三章串经历了栈一章的痛苦煎熬后，终于迎来了串一章的柳暗花明。数据结构C语言版期末考试试题(有答案)
框架结构毕业设计任务书和指导书范本
大学数据结构期末知识点重点总结(考试专用)
框架结构设计步骤及要点
2010级数据结构期末复习题(E)
数据结构期末考试复习笔记
数据结构c语言版期末考试复习试题
框架结构设计的技术措施
数据结构复习重点归纳
相关主题
文本预览