最新清华大学严蔚敏版数据结构考研要点(精华版)
1、数据(Data) ：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素(Data Element)：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。
一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。
数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C={‘A’,’B’,’C,…} 。
数据结构(Data Structure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型，如图1-3所示。
①集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。
②线性结构：结构中的数据元素之间存在一对一的关系。
③树型结构：结构中的数据元素之间存在一对多的关系。
④图状结构或网状结构：结构中的数据元素之间存在多对多的关系。
2、顺序结构：数据元素存放的地址是连续的；
链式结构：数据元素存放的地址是否连续没有要求。
数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。
3、C语言中用带指针的结构体类型来描述
typedef struct Lnode
{ ElemType data; /*数据域，保存结点的值*/
struct Lnode *next; /*指针域*/
}LNode; /*结点的类型*/
4、循环队列为空：front=rear 。
循环队列满：(rear+1)%MAX_QUEUE_SIZE =front。
5、性质1：在非空二叉树中，第i层上至多有2i-1个结点(i≧1)。
性质2：深度为k的二叉树至多有2k-1个结点（k≧1) 。
性质3：对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。
一棵深度为k且有2k-1个结点的二叉树称为满二叉树(Full Binary Tree)。
完全二叉树的特点：若完全二叉树的深度为k ，则所有的叶子结点都出现在第k层或k-1
层。对于任一结点，如果其右子树的最大层次为l，则其左子树的最
大层次为l或l+1。
性质4：n个结点的完全二叉树深度为：?㏒2n? +1。
性质5：若对一棵有n个结点的完全二叉树(深度为└㏒2n┘+1)的结点按层（从第1层到
第?㏒2n?+1层)序自左至右进行编号,则对于编号为i（1≦i≦n)的结
点：
⑴若i=1：则结点i是二叉树的根，无双亲结点；否则，若i>1，则其双亲结点编号是?i/2?。
⑵如果2i>n：则结点i为叶子结点，无左孩子；否则，其左孩子结点编号是2i。
⑶如果2i+1>n：则结点i无右孩子；否则，其右孩子结点编号是2i+1。
6、线索二叉树：设一棵二叉树有n个结点，则有n-1条边(指针连线)，而n个结点共有
2n个指针域(Lchild和Rchild) ，显然有n+1个空闲指针域未用。则可以利
用这些空闲的指针域来存放结点的直接前驱和直接后继信息。
7、Huffman树：具有n个叶子结点(每个结点的权值为w i) 的二叉树不止一棵，但在所有的
这些二叉树中，必定存在一棵WPL值最小的树，称这棵树为Huffman树(或
称最优树) 。
8、完全无向图：对于无向图，若图中顶点数为n ，用e表示边的数目，则e ∈[0，n(n-1)/2] 。
具有n(n-1)/2条边的无向图称为完全无向图。
完全有向图：对于有向图，若图中顶点数为n ，用e表示弧的数目，则e∈[0，n(n-1)] 。具有n(n-1)条边的有向图称为完全有向图。
生成树、生成森林：一个连通图(无向图)的生成树是一个极小连通子图，它含有图中全部n 个顶点和只有足以构成一棵树的n-1条边，称为图的生成树
关于无向图的生成树的几个结论：
1) 一棵有n个顶点的生成树有且仅有n-1条边；
2) 如果一个图有n个顶点和小于n-1条边，则是非连通图；
3) 如果多于n-1条边，则一定有环；
4) 有n-1条边的图不一定是生成树。
9、最小生成树(Minimum Spanning Tree) ：带权连通图中代价最小的生成树称为最小生成树。最小生成树在实际中具有重要用途，如设计通信网。设图的顶点表示城市，边表示两个城市之间的通信线路，边的权值表示建造通信线路的费用。n个城市之间最多可以建n′(n-1)/2条线路，如何选择其中的n-1条，使总的建造费用最低?
10、工程完成最短时间：从起点到终点的最长路径长度(路径上各活动持续时间之和) 。长度最长的路径称为关键路径，关键路径上的活动称为关键活动。关键活动是影响整个工程的
关键。
11、查找方法比较
12、在随机情况下，二叉排序树的平均查找长度ASL 和㏒(n)(树的深度)是等数量级的。 二叉排序树(Binary Sort Tree 或Binary Search Tree) 的定义为：二叉排序树或者是空树，或者是满足下列性质的二叉树。
(1) ：若左子树不为空，则左子树上所有结点的值(关键字)都小于根结点的值； (2) ：若右子树不为空，则右子树上所有结点的值(关键字)都大于根结点的值； (3) ：左、右子树都分别是二叉排序树。
结论：若按中序遍历一棵二叉排序树，所得到的结点序列是一个递增序列。
13、平衡二叉树或者是空树，或者是满足下列性质的二叉树。 ⑴：左子树和右子树深度之差的绝对值不大于1； ⑵：左子树和右子树也都是平衡二叉树。 顺序查找 折半查找 分块查找 ASL 最大
最小 两者之间 表结构
有序表、无序表 有序表
分块有序表 存储结构
顺序存储结构
线性链表
顺序存储结构
顺序存储结构
线性链表
平衡因子(Balance Factor) ：二叉树上结点的左子树的深度减去其右子树深度称为该结点的平衡因子。
平衡二叉排序树上进行查找的平均查找长度和㏒2n是一个数量级的，平均时间复杂度为O(㏒2n)。
四种平衡化旋转，其正确性容易由“遍历所得中序序列不变”来证明。并且，无论是哪种情况，平衡化旋转处理完成后，形成的新子树仍然是平衡二叉排序树，且其深度和插入前以a为根结点的平衡二叉排序树的深度相同。所以，在平衡二叉排序树上因插入结点而失衡，仅需对失衡子树做平衡化旋转处理。
14、一棵m阶B_树，或者是空树，或者是满足以下性质的m叉树：
⑴根结点或者是叶子，或者至少有两棵子树，至多有m棵子树；
⑵除根结点外，所有非终端结点至少有ém/2ù棵子树，至多有m棵子树；
⑶所有叶子结点都在树的同一层上；
⑷每个结点应包含如下信息：
(n，A0，K1，A1，K2，A2，… ，K n，A n)
其中K i(1≤i≤n)是关键字，且K i 根据m阶B_树的定义，第一层上至少有1个结点，第二层上至少有2个结点；除根结点外，所有非终端结点至少有ém/2ù棵子树，…，第h层上至少有ém/2ùh-2个结点。在这些结点中：根结点至少包含1个关键字，其它结点至少包含ém/2ù-1个关键字，设s=ém/2ù，则总的关 键字数目n满足： 因此有：h≦1+ ㏒s((n+1)/2)=1+㏒ém/2ù((n+1)/2) 即在含有n个关键字的B_树上进行查找时，从根结点到待查找记录关键字的结点的路径上所涉及的结点数不超过1+ ㏒ém/2ù((n+1)/2) 。 15、m阶B+树。它与B_树的主要不同是叶子结点中存储记录。在B+树中，所有的非叶子结点可以看成是索引，而其中的关键字是作为“分界关键字”，用来界定某一关键字的记录所在的子树。一棵m阶B+树与m阶B_树的主要差异是： ⑴若一个结点有n棵子树，则必含有n个关键字； ⑵所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针，而且叶子结点按关键字的大小从小到大顺序链接； ⑶所有的非叶子结点可以看成是索引的部分，结点中只含有其子树的根结点中的最大(或最小)关键字。 16、哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。可写成：addr(a i)=H(k i) ，其中i是表中一个元素，addr(a i)是a i的地址，k i是a i的关键字。 哈希表：应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。 哈希查找(又叫散列查找)：利用哈希函数进行查找的过程叫哈希查找。 例1 ：设散列表长为7，记录关键字组为：15, 14, 28, 26, 56, 23，散列函数：H(key)=key MOD 7，冲突处理采用线性探测法。 解：H(15)=15 MOD 7=1 H(14)=14 MOD 7=0 H(28)=28 MOD 7=0 冲突H1(28)=1 又冲突H2(28)=2 H(26)=26 MOD 7=5 H(56)=56 MOD 7=0 冲突H1(56)=1 又冲突 H2(56)=2 又冲突H3(56)=3 H(23)=23 MOD 7=2 冲突H1(23)=3 又冲突 H3(23)=4 各种散列函数所构造的散列表的ASL如下： 17、排序的稳定性 若记录序列中有两个或两个以上关键字相等的记录：K i =K j(i≠j，i, j=1, 2, … n)，且在排序前R i先于R j(i 排序的分类 待排序的记录数量不同，排序过程中涉及的存储器的不同，有不同的排序分类。 ①待排序的记录数不太多：所有的记录都能存放在内存中进行排序，称为内部排序； ②待排序的记录数太多：所有的记录不可能存放在内存中，排序过程中必须在内、外存之间进行数据交换，这样的排序称为外部排序。 18、插入排序采用的是以“玩桥牌者”的方法为基础的。即在考察记录R i之前，设以前的所有记录R1, R2,…., R i-1已排好序，然后将R i插入到已排好序的诸记录的适当位置。 ============================================================================ 最基本的插入排序是直接插入排序(Straight Insertion Sort) 。 ⑴最好情况：若待排序记录按关键字从小到大排列(正序)，算法中的内循环无须执行，则一趟排序时：关键字比较次数1次，记录移动次数2次 ⑵最坏情况：若待排序记录按关键字从大到小排列(逆序)，则一趟排序时：算法中的内循环体执行i-1，关键字比较次数i次，记录移动次数i+1。 一般地，认为待排序的记录可能出现的各种排列的概率相同，则取以上两种情况的平均值，作为排序的关键字比较次数和记录移动次数，约为n2/4，则复杂度为O(n2) 。 算法实现 void straight_insert_sort(Sqlist *L) { int i, j ; for (i=2; i<=L->length; i++) { L->R[0]=L->R[i]; j=i-1; /* 设置哨兵*/ while( LT(L->R[0].key, L->R[j].key) ) { L->R[j+1]=L->R[j]; j--; } /* 查找插入位置*/ L->R[j+1]=L->R[0]; /* 插入到相应位置*/ } } ===============================================================================折半插入排序 当将待排序的记录R[i] 插入到已排好序的记录子表R[1…i-1]中时，由于R1, R2,…, R i-1已排好序，则查找插入位置可以用“折半查找”实现，则直接插入排序就变成为折半插入排序。 从时间上比较，折半插入排序仅仅减少了关键字的比较次数，却没有减少记录的移动次数，故时间复杂度仍然为O(n2) 。 排序示例： 设有一组关键字30, 13, 70, 85, 39, 42, 6, 20，采用折半插入排序方法排序的过程 ⑴算法实现 void Binary_insert_sort(Sqlist *L) { int i, j, low, high, mid ; for (i=2; i<=L->length; i++) { L->R[0]=L->R[i]; /* 设置哨兵*/ low=1 ; high=i-1 ; while (low<=high) { if ( LT(L->R[0].key, L->R[mid].key) ) high=mid-1 ; else low=mid+1 ; } /* 查找插入位置*/ for (j=i-1; j>=high+1; j--) L->R[j+1]=L->R[j]; L->R[high+1]=L->R[0]; /* 插入到相应位置*/ }} ============================================================================== 2-路插入排序 路插入排序的过程 排序示例：设有初始关键字集合{49, 38, 65, 13, 97, 27, 76} ，采用2- 例：设有关键字集合{49, 38, 65, 97, 76, 13, 49} ，采用表插入排序的过程 希尔排序(Shell Sort，又称缩小增量法)是一种分组插入排序方法。 排序示例 设有10个待排序的记录，关键字分别为9, 13, 8, 2, 5, 13, 7, 1, 15, 11，增量序列是5, 3, 1，希尔排序的过程： 算法实现 先给出一趟希尔排序的算法，类似直接插入排序。 void shell_pass(Sqlist *L, int d) /* 对顺序表L进行一趟希尔排序, 增量为d */ { int j, k ; for (j=d+1; j<=L->length; j++) { L->R[0]=L->R[j] ; /* 设置监视哨兵*/ k=j-d ; while (k>0&<(L->R[0].key, L->R[k].key) ) {L->R[k+d]=L->R[k] ; k=k-d ; } L->R[k+j]=L->R[0] ; } } void shell_sort(Sqlist *L, int dk[], int t) /* 按增量序列dk[0 … t-1],对顺序表L进行希尔排序*/ { int m ; for (m=0; m<=t; m++) shll_pass(L, dk[m]) ; } ===============================================================================冒泡排序 排序示例： 设有9个待排序的记录，关键字分别为23, 38, 22, 45, 23, 67, 31, 15, 41，冒泡排序的过程： void Bubble_Sort(Sqlist *L) { int j ,k , flag ; for (j=0; j { flag=TRUE ; for (k=1; k<=L->length-j; k++) /* 一趟排序*/ if (LT(L->R[k+1].key, L->R[k].key ) ) { flag=FALSE ; L->R[0]=L->R[k] ; L->R[k]=L->R[k+1] ; L->R[k+1]=L->R[0] ; } if (flag==TRUE) break ; } } 算法分析: 时间复杂度: 最好情况(正序)：比较次数：n-1；移动次数：0； 最坏情况(逆序)： 故时间复杂度：T(n)=O(n2) 空间复杂度：S(n)=O(1) ===============================================================================快速排序的平均时间复杂度是：T(n)=O(n㏒2n) 从所需要的附加空间来看，快速排序算法是递归调用，系统内用堆栈保存递归参数，当每次划分比较均匀时，栈的最大深度为[㏒2n]+1 。 ∴快速排序的空间复杂度是：S(n)=O(㏒2n) 从排序的稳定性来看，快速排序是不稳定的。 一趟排序示例 设有6个待排序的记录，关键字分别为29, 38, 22, 45, 23, 67，一趟快速排序的过程 算法实现 ⑴一趟快速排序算法的实现 int quick_one_pass(Sqlist *L , int low, int high) L->R[0]=L->R[i] ; /* R[0]作为临时单元和哨兵*/ do { while (LQ(L->R[0].key, L->R[j].key)&&(j>i)) j-- ; if (j>i) { L->R[i]=L->R[j] ; i++; } while (LQ(L->R[i].key, L->R[0].key)&&(j>i)) i++ ; if (j>i) { L->R[j]=L->R[i] ; j--; } } while(i!=j) ; /* i=j时退出扫描*/ L->R[i]=L->R[0] ; return(i) ; } 递归算法 void quick_Sort(Sqlist *L , int low, int high) { int k ; if (low { k=quick_one_pass(L, low, high); quick_Sort(L, low, k-1); quick_Sort(L, k+1, high); } /* 序列分为两部分后分别对每个子序列排序*/ } 非递归算法 # define MAX_STACK 100 void quick_Sort(Sqlist *L , int low, int high) { int k , stack[MAX_STACK] , top=0; do { while (low { k=quick_one_pass(L,low,high); stack[++top]=high ; stack[++top]=k+1 ; /* 第二个子序列的上,下界分别入栈*/ high=k-1 ; } if (top!=0) { low=stack[top--] ; high=stack[top--] ; } }while (top!=0&&low } ============================================================================== 简单选择排序(Simple Selection Sort ，又称为直接选择排序) 排序示例 例：设有关键字序列为：7, 4, -2, 19, 13, 6，直接选择排序的过程 算法实现 void simple_selection_sort(Sqlist *L) { int m, n , k; for (m=1; m { k=m ; for (n=m+1; n<=L->length; n++) if ( LT(L->R[n].key, L->R[k].key) ) k=n ; if (k!=m) /* 记录交换*/ { L->R[0]=L->R[m]; L->R[m]=L->R[k]; L->R[k]=L->R[0]; } } } 算法分析 整个算法是二重循环：外循环控制排序的趟数，对n个记录进行排序的趟数为n-1趟；内循环控制每一趟的排序。 进行第i趟排序时，关键字的比较次数为n-i，则： ∴时间复杂度是：T(n)=O(n2) 空间复杂度是：S(n)=O(1) 从排序的稳定性来看，直接选择排序是不稳定的。 =============================================================================== 堆的定义 是n个元素的序列H={k1, k2 , … k n} ，满足： 堆的性质 ①堆是一棵采用顺序存储结构的完全二叉树，k1是根结点； ②堆的根结点是关键字序列中的最小(或最大)值，分别称为小(或大)根堆； ③从根结点到每一叶子结点路径上的元素组成的序列都是按元素值(或关键字值)非递减(或非递增)的； (4)堆中的任一子树也是堆。 利用堆顶记录的关键字值最小(或最大)的性质，从当前待排序的记录中依次选取关键字最小(或最大)的记录，就可以实现对数据记录的排序，这种排序方法称为堆排序。 堆排序思想 ①对一组待排序的记录，按堆的定义建立堆； ②将堆顶记录和最后一个记录交换位置，则前n-1个记录是无序的，而最后一个记录是有序的； ③堆顶记录被交换后，前n-1个记录不再是堆，需将前n-1个待排序记录重新组织成为一个堆，然后将堆顶记录和倒数第二个记录交换位置，即将整个序列中次小关键字值的记录调整(排除)出无序区； ④重复上述步骤，直到全部记录排好序为止。 结论：排序过程中，若采用小根堆，排序后得到的是非递减序列；若采用大根堆，排序后得到的是非递增序列。 堆排序算法实现 堆的根结点是关键字最小的记录，输出根结点后，是以序列的最后一个记录作为根结点，而原来堆的左、右子树都是堆，则进行一次筛选就可以成为堆。 void Heap_Sort(Sqlist *H) { int j ; for (j=H->length/2; j>0; j--) Heap_adjust(H, j , H->length) ; /* 初始建堆*/ for (j=H->length/2; j>=1; j--) { H->R[0]=H->R[1] ; H->R[1]=H->R[j] ; H->R[j]=H->R[0] ; /* 堆顶与最后一个交换*/ Heap_adjust(H, 1, j-1) ; } } 堆排序的比较次数的数量级为：T(n)=O(n㏒2n)；而附加空间就是交换时所用的临时空间，故空间复杂度为：S(n)=O(1) ===============================================================================归并(Merging) ：是指将两个或两个以上的有序序列合并成一个有序序列。若采用线性表(无论是那种存储结构)易于实现，其时间复杂度为O(m+n) 。 归并排序的算法 开始归并时，每个记录是长度为1的有序子序列，对这些有序子序列逐趟归并，每一趟归并后有序子序列的长度均扩大一倍；当有序子序列的长度与整个记录序列长度相等时，整个记录序列就成为有序序列。算法是： void Merge_sort(Sqlist *L, RecType DR[]) { int d=1 ; while(d { Merge_pass(L->R, DR, d, L->length) ; Merge_pass(DR, L->R, 2*d, L->length) ; d=4*d ; } } 具有n个待排序记录的归并次数是㏒2n，而一趟归并的时间复杂度为O(n)，则整个归并排序的时间复杂度无论是最好还是最坏情况均为O(n㏒2n)。在排序过程中，使用了辅助向量DR，大小与待排序记录空间相同，则空间复杂度为O(n)。归并排序是稳定的。 ===============================================================================各种内部排序的比较: 各种内部排序按所采用的基本思想(策略)可分为：插入排序、交换排序、选择排序、归并排序和基数排序，它们的基本策略分别是： 1 插入排序：依次将无序序列中的一个记录，按关键字值的大小插入到已排好序一个子序列的适当位置，直到所有的记录都插入为止。具体的方法有：直接插入、表插入、2-路插入 和shell排序。 2 交换排序：对于待排序记录序列中的记录，两两比较记录的关键字，并对反序的两个记录进行交换，直到整个序列中没有反序的记录偶对为止。具体的方法有：冒泡排序、快速排序。 3 选择排序：不断地从待排序的记录序列中选取关键字最小的记录，放在已排好序的序列的最后，直到所有记录都被选取为止。具体的方法有：简单选择排序、堆排序。 4 归并排序：利用“归并”技术不断地对待排序记录序列中的有序子序列进行合并，直到合并为一个有序序列为止。 5 基数排序：按待排序记录的关键字的组成成分(“位”)从低到高(或从高到低)进行。每次是按记录关键字某一“位”的值将所有记录分配到相应的桶中，再按桶的编号依次将记录进行收集，最后得到一个有序序列。 各种内部排序方法的性能比较如下表。 文件的基本概念 ⑴数据项(Item或field) ：数据文件中最小的基本单位，反映实体某一方面的特征—属性的数据表示。 ⑵记录(Record) ：一个实体的所有数据项的集合。用来标识一个记录的数据项集合(一个或多个)称为关键字项(Key) ，关键字项的值称为关键字；能唯一标识一个记录的关键字称为主关键字(Primary Key)，其它的关键字称为次关键字(Secondary Key) 。 利用外存对数据文件进行排序称为外部排序。 算法部分： 素数的判断算法。 Void prime( int n) /* n是一个正整数*/ { int i=2 ; while ( (n% i)!=0 && i*1.0< sqrt(n) ) i++ ; if (i*1.0>sqrt(n) ) printf(“&d 是一个素数\n” , n) ; else printf(“&d 不是一个素数\n” , n) ; } ---------------------------------------------------------------------- 冒泡排序法。 Void bubble_sort(int a[]，int n) { change=false; for (i=n-1; change=TURE; i>1 && change; --i) for (j=0; j if (a[j]>a[j+1]) { a[j] ←→a[j+1] ; change=TURE ; } } –最好情况：0次 –最坏情况：1+2+3+?+n-1=n(n-1)/2 –平均时间复杂度为：O(n2) --------------------------------------------------------------------------------- 算法说明：算法中pa ，pb分别是待考察的两个链表的当前结点，pc是合并过程中合并的链表的最后一个结点。 LNode *Merge_LinkList(LNode *La，LNode *Lb) /* 合并以La, Lb为头结点的两个有序单链表*/ { LNode *Lc, *pa , *pb , *pc, *ptr ; Lc=La ; pc=La ; pa=La->next ; pb=Lb->next ; while (pa!=NULL && pb!=NULL) { if (pa->data { pc->next=pa ; pc=pa ; pa=pa->next ; } /* 将pa所指的结点合并，pa指向下一个结点*/ if (pa->data>pb->data) { pc->next=pb ; pc=pb ; pb=pb->next ; } /* 将pa所指的结点合并，pa指向下一个结点*/ if (pa->data==pb->data) { pc->next=pa ; pc=pa ; pa=pa->next ; ptr=pb ; pb=pb->next ; free(ptr) ; } /* 将pa所指的结点合并，pb所指结点删除*/ } if (pa!=NULL) pc->next=pa ; else pc->next=pb ; /*将剩余的结点链上*/ free(Lb) ; return(Lc) ; } 采用静态顺序栈方式实现 void conversion(int n , int d) /*将十进制整数N转换为d(2或8)进制数*/ { SqStack S ; int k, *e ; S=Init_Stack(); while (n>0) { k=n%d ; push(S , k) ; n=n/d ; } /* 求出所有的余数，进栈*/ while (S.top!=0) /* 栈不空时出栈，输出*/ { pop(S, e) ; printf(“%1d” , *e) ; } } 求转置矩阵的算法如下： void TransMatrix(TMatrix a , TMatrix b) { int p , q , col ; b.rn=https://www.wendangku.net/doc/ca8198172.html, ; https://www.wendangku.net/doc/ca8198172.html,=a.rn ; b.tn=a.tn ; /* 置三元组表b.data的行、列数和非0元素个数*/ if (b.tn==0) printf(“ The Matrix A=0\n” ); else { q=0; for (col=1; col<=https://www.wendangku.net/doc/ca8198172.html, ; col++) /* 每循环一次找到转置后的一个三元组*/ for (p=0 ;p /* 循环次数是非0元素个数*/ if (a.data[p].col==col) { b.data[q].row=a.data[p].col ; b.data[q].col=a.data[p].row ; b.data[q].value=a.data[p].value; q++ ; } } } 先序遍历的递归算法 void PreorderTraverse(BTNode *T) { if (T!=NULL) { visit(T->data) ; /* 访问根结点*/ PreorderTraverse(T->Lchild) ; PreorderTraverse(T->Rchild) ; } } 非递归算法 设T是指向二叉树根结点的指针变量，非递归算法是： 若二叉树为空，则返回；否则，令p=T； ⑴访问p所指向的结点； ⑵q=p->Rchild ，若q不为空，则q进栈； ⑶p=p->Lchild ，若p不为空，转(1)，否则转(4)； ⑷退栈到p ，转(1)，直到栈空为止。 算法实现： #define MAX_NODE 50 void PreorderTraverse( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T, *q ; int top=0 ; if (T==NULL) printf(“ Binary Tree is Empty!\n”) ; else { do { visit( p-> data ) ; q=p->Rchild ; if ( q!=NULL ) stack[++top]=q ; p=p->Lchild ; if (p==NULL) { p=stack[top] ; top-- ; } } while (p!=NULL) ; } } ==============================================================================中序遍历的递归算法 void InorderTraverse(BTNode *T) { if (T!=NULL) { InorderTraverse(T->Lchild) ; visit(T->data) ; /* 访问根结点*/ InorderTraverse(T->Rchild) ; } } 非递归算法 设T是指向二叉树根结点的指针变量，非递归算法是： 若二叉树为空，则返回；否则，令p=T ⑴若p不为空，p进栈，p=p->Lchild ； ⑵否则(即p为空)，退栈到p，访问p所指向的结点； ⑶p=p->Rchild ，转(1)； 直到栈空为止。 算法实现： #define MAX_NODE 50 void InorderTraverse( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T ; int top=0 , bool=1 ; if (T==NULL) printf(“ Binary Tree is Empty!\n”) ; else { do { while (p!=NULL) { stack[++top]=p ; p=p->Lchild ; } if (top==0) bool=0 ; else { p=stack[top] ; top-- ; visit( p->data ) ; p=p->Rchild ; } } while (bool!=0) ; } } =============================================================================== 后序遍历的递归算法 void PostorderTraverse(BTNode *T) { if (T!=NULL) { PostorderTraverse(T->Lchild) ; PostorderTraverse(T->Rchild) ; visit(T->data) ; /* 访问根结点*/ } } 非递归算法 在后序遍历中，根结点是最后被访问的。因此，在遍历过程中，当搜索指针指向某一根结点时，不能立即访问，而要先遍历其左子树，此时根结点进栈。当其左子树遍历完后再搜索到该根结点时，还是不能访问，还需遍历其右子树。所以，此根结点还需再次进栈，当其右子树遍历完后再退栈到到该根结点时，才能被访问。 因此，设立一个状态标志变量tag ：0 ：结点暂不能访问 1 ：结点可以被访问 其次，设两个堆栈S1、S2，S1保存结点，S2保存结点的状态标志变量tag 。S1和S2共用一个栈顶指针。 设T是指向根结点的指针变量，非递归算法是： 若二叉树为空，则返回；否则，令p=T； ⑴第一次经过根结点p，不访问： p进栈S1 ，tag 赋值0，进栈S2，p=p->Lchild 。 ⑵若p不为空，转(1)，否则，取状态标志值tag ： ⑶若tag=0：对栈S1，不访问，不出栈；修改S2栈顶元素值(tag赋值1) ，取S1栈顶元素 的右子树，即p=S1[top]->Rchild ，转(1)； ⑷若tag=1：S1退栈，访问该结点； 直到栈空为止。 算法实现： #define MAX_NODE 50 void PostorderTraverse( BTNode *T) { BTNode *S1[MAX_NODE] ,*p=T ; int S2[MAX_NODE] , top=0 , bool=1 ; if (T==NULL) printf(“Binary Tree is Empty!\n”) ; else { do {while (p!=NULL) { S1[++top]=p ; S2[top]=0 ; p=p->Lchild ; } if (top==0) bool=0 ; else if (S2[top]==0) { p=S1[top]->Rchild ; S2[top]=1 ; } else { p=S1[top] ; top-- ; visit( p->data ) ; p=NULL ; /* 使循环继续进行而不至于死循环*/ } } while (bool!=0) ; } } ===============================================================================设T是指向根结点的指针变量，层次遍历非递归算法是： 若二叉树为空，则返回；否则，令p=T，p入队； ⑴队首元素出队到p； ⑵访问p所指向的结点； ⑶将p所指向的结点的左、右子结点依次入队。直到队空为止。 #define MAX_NODE 50 void LevelorderTraverse( BTNode *T) { BTNode *Queue[MAX_NODE] ,*p=T ; int front=0 , rear=0 ; if (p!=NULL) { Queue[++rear]=p; /* 根结点入队*/ while (front { p=Queue[++front]; visit( p->data ); if (p->Lchild!=NULL) Queue[++rear]=p; /* 左结点入队*/ if (p->Rchild!=NULL) Queue[++rear]=p; /* 左结点入队*/ } } } ===============================================================================利用层次遍历算法可以直接求得二叉树的深度。 算法实现： #define MAX_NODE 50 int search_depth( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T; int front=0 , rear=0, depth=0, level ; /* level总是指向访问层的最后一个结点在队列的位置*/ if (T!=NULL) { Queue[++rear]=p; /* 根结点入队*/ level=rear ; /* 根是第1层的最后一个节点*/ while (front { p=Queue[++front]; if (p->Lchild!=NULL) Queue[++rear]=p; /* 左结点入队*/ if (p->Rchild!=NULL) Queue[++rear]=p; /* 左结点入队*/ if (front==level) /* 正访问的是当前层的最后一个结点*/ { depth++ ; level=rear ; } 清华大学研究生院2007年招收硕士生入学试题 考试科目：结构力学（包含结构动力学基础） 题号：0901 一．计算图1所示珩架指定杆的轴力 (10分) ()12,N N 二．结构仅在ACB 部分温度升高t 度，并且在D 处作用外力偶M 。试求图示刚架A,B 两点间水平向的相对位移。已知：各杆的EI 为常值，为线膨胀系数，h 为截面高度。 α（20分） 三．用力法分析图3所示结构，绘M 图。计算时轴力和剪力对位移的影响略去不计。各杆的EI 值相同。 （20分）半圆弧 积分表：2211sin sin 2,cos sin 22424 x x xdx x xdx x =-=+??四．试用位移法求解图4所示刚架并绘M 图。计算时不考虑轴力变形时对位移的影响。（20分） 杆端力公式： ,21,08f f AB BA ql M M =-=53,88 f f AB BA ql ql Q Q ==- 一．试用力矩分配法计算图5所示连续梁并绘M 图。（10分） 二．求图示结构的自振频率和主振型，并作出振型图。已知： ，忽略阻尼影响。 （20分） 122,,m m EI m m ===常数 清华大学研究生院2008年招收硕士生入学试题考试科目：结构力学（包含结构动力学基础） 题号：0901 一．选择题：在正确答案处画“√”。每题4分。 1．图示平面体系的几何组成性质是： A.几何不变且无多余联系的 B.几何不变且有多余联系的 C.几何可变的 D.瞬变的 2．图示结构A截面的剪力为： A. –P B. P C. P/2 D. –P/2 3.图示珩架内力为零的杆为： A.3根 B.6根 C.8根 D.7根 第一章绪论 1、数据结构是计算机中存储、组织数据的方式。精心选择的数据 结构可以带来最优效率的算法。 2、程序设计= 算法+数据结构 3、解决问题方法的效率： ●跟数据的组织方式有关 ●跟空间的利用效率有关 ●跟算法的巧妙程度有关 4、数据：所有能输入到计算机中,且被计算机处理的符号的集合， 是计算机操作对象的总称； 是计算机处理的信息的某种特定的符号表示形式。 5、数据元素：数据中的一个“个体”,数据结构中讨论的基本单 位。相当于“记录”,在计算机程序中通常作为一个整体考 虑和处理。 6、数据项: 相当于记录的“域”, 是数据的不可分割的最小单位, 如学号。数据元素是数据项的集合。 7、数据对象：性质相同的数据元素的集合. 例如: 所有运动员的记录集合 8、数据结构：是相互间存在某种关系的数据元素集合。 9、数据结构是带结构的数据元素的集合。 10、不同的关系构成不同的结构。 11、次序关系： { 第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据 类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 第七章数据结构作业答案 第七章图 选择题 1．设无向图的顶点个数为n，则该图最多有（ B ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 2．一个n个顶点的连通无向图，其边的个数至少为（ A ）。 A．n-1 B．n C．n+1 D．nlogn； 3．一个有n个结点的图，最少有（ B ）个连通分量，最多有（ D ）个连通分量。 A．0 B．1 C．n-1 D．n 4．在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。 A．1/2 B．2 C．1 D．4 5．下列哪一种图的邻接矩阵是对称矩阵？（ B ） A．有向图 B．无向图 C．AOV网 D．AOE网 6．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（ B ）。 A．∑ = n i j i A 1 ] ,[ B． [] ∑ = n 1 j j,i A C． ∑ = n i i j A 1 ] , [ D． ∑ = n i j i A 1 ] ,[ + [] ∑ = n 1 j i,j A 7．下面哪一方法可以判断出一个有向图是否有环（回路）：( B ) A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 广度优先遍历 8. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( B )。 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 9. 求解最短路径的Floyd算法的时间复杂度为( D )。 A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n） 10．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（ A ）。 A．存在 B．不存在 11．一个有向无环图的拓扑排序序列（ B ）是唯一的。 A．一定 B．不一定 12. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ D ）。 A．G中有弧 清华大学 2014年攻读硕士学位入学考试试题 考试科目： 结构力学（含动力学基础） 试题编号 804 （注：答案必须写在答题纸上，写在试题上无效） 一 、填空题（9小题，共计32分） 1 在一个体系上增加或去掉____，不改变体系的几何不变性或可变性。（2分） 2 具有基本部分和附属部分的结构，进行受力分析的次序是：先计算____部分，后计算____部分。（2分） 3 若三铰拱的跨度、拱上竖向荷载给定不变，则拱愈扁平，拱的水平推力愈____（大或小）。（2分） 4 图示刚架D 截面的剪力F QDB =____、弯矩M DB =____ (内侧受拉为正)。（6分） D 10 kN/m 5 m B 5 m 5 图示桁架中杆a 、b 的轴力分别为F Na =____，F Nb =____。（6分） F P a F P b L 4L 6 图乘法的应用条件是：①杆段是________杆段；②两个弯矩图中至少有一个是____图形。（4分） 7 图示静定梁在移动荷载作用下，截面C 的弯矩影响线方程为M C =_______（0≤x ≤2m ）；M C =_____（2m ≤x ≤6m ）。（4分） 8 荷载移动到某个位置使研究量达到最大值，则此荷载位置称为移动荷载的____1 P F x C m 2m 2m 2 位置。（2分） 9 用位移法计算有侧移刚架时，基本未知量包括结点____位移和____位移。 （4分） 二 、选择题（4小题，共计18分） 1 图示多跨静定梁截面C 的弯矩M C =____ 。（5分） F P F P a C a a a 2a (A) )(4下拉a F P (B) )(下拉2a F P (C) )(下拉43a F P (D) )(上拉4 a F P 2 图示桁架中K 型结点处，杆 b 轴力为F Nb =____。（5分） F P a F P b a F P a a a (A) 0 (B) P F 22- (C) P F 2 (D) P F 2- (E) P F 22 3 图示结构用力法计算时，不能选作基本结构的是______。 (A) (B) (C) (D) 4 图示对称结构在对称荷载作用下取半边结构计算时，其等代结构为图____。 (A) (B) (C) (D) 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系 时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是 ___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插 入元素的时间复杂度为____________。 5. 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ， 则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 6. 6.广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 7.7.二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结点的度的 总和是_____________。 8.8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由算术表 达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。 李春葆编著：数据结构（C语言篇）――习题与解析（修订版） 清华大学出版社 一、绪论 选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。 1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。 A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面是2。 1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.正确性和简单性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。 A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。 A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表 C.栈的操作方式是先进先出 D.队列的操作方式是先进后出 10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。 A.正确 B.不正确 填空题 1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。 2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3.在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结点；叶子结点没有结点，其余每个结点的后续可以。 1-1什么是数据? 它与信息是什么关系? 【解答】 什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。 什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。 1-2什么是数据结构? 有关数据结构的讨论涉及哪三个方面? 【解答】 数据结构是指数据以及相互之间的关系。记为：数据结构= { D, R }。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 有关数据结构的讨论一般涉及以下三方面的内容： ①数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构； ②数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构； ③施加于该数据结构上的操作。 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。 1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、 队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？ 【解答】 线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后继。例如，一维数组、线性表等就是典型的线性结构 非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如，树、图或网络等都是典型的非线性结构。 1-4．什么是抽象数据类型？试用C++的类声明定义“复数”的抽象数据类型。要求 (1) 在复数内部用浮点数定义它的实部和虚部。 (2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。 (3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。 严蔚敏 数据结构C 语言版答案详解 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 附录习题参考答案 习题1参考答案 1.1.选择题 (1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.) A. 1.2.填空题 (1). 数据关系 (2). 逻辑结构物理结构 (3). 线性数据结构树型结构图结构 (4). 顺序存储链式存储索引存储散列表（Hash）存储 (5). 变量的取值范围操作的类别 (6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系 (7). 关系网状结构树结构 (8). 空间复杂度和时间复杂度 (9). 空间时间 (10). Ο(n) 1.3 名词解释如下： 数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。 数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。 数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。 数据类型：是指变量的取值范围和所能够进行的操作的总和。 算法：是对特定问题求解步骤的一种描述，是指令的有限序列。 1.4 语句的时间复杂度为： (1) Ο(n2) (2) Ο(n2) (3) Ο(n2) (4) Ο(n-1) (5) Ο(n3) 1.5 参考程序： main() { int X,Y,Z； scanf(“%d, %d, %d”,&X,&Y,Z)； if (X>=Y) if(X>=Z) if (Y>=Z) { printf(“%d, %d, %d”,X,Y,Z);} else { printf(“%d, %d, %d”,X,Z,Y);} 清华大学 2013年攻读硕士学位入学考试试题 考试科目： 结构力学（含动力学基础） 试题编号 804 （注：答案必须写在答题纸上，写在试题上无效） 一、选择题（每题5分，共25分） 1．图示结构位移法最少未知量个数为（）。 A. 1； C.2；B.3； D.4。 2．图示超静定刚架以去除C 支座加向上的反力为基本体系，各杆EI 等于常数，δ11和Δ1P 为()。 A.EIδ11＝288；EI Δ1P ＝8640； B. EIδ11＝216；EI Δ1P ＝8640； C.EIδ11＝288；EI Δ1P ＝－8640; D. EIδ11＝216；EI Δ1P ＝－8640。 3.超静定结构影响线的外形为（ ）。 A.一定为曲线； B.一定为折线； C 可能为曲线，也可能为直线； D ．一定为直线。 4、在位移法中，将铰接端的角位移，滑动支撑端的线位移作为基本未知量：A,绝对不可； B.一定条件下可以；C.可以，但不必； D.必须。 () 5、图示体系为：A.几何不变无多余约束 B.几何不变有多余约束C.几何常变 D. 几何瞬变 20kN A B C 10kN/m 6m 二、判断题（每题2分，18分） 1、三刚片用三个铰两两相联必成为几何不变体系。（） 2、对静定结构，支座移动或温度改变会产生内力。（） 3、力法的基本体系必须是静定的。（） 4、任何三铰拱的合理拱轴都是二次抛物线。（） 5、图乘法可以用来计算曲杆。（） 6、静定结构的影响线全部都由直线段组成。（） 7、多跨静定梁若附属部分受力，则只有附属部分产生内力。（） 8、功的互等定理成立的条件是小变形和线弹性。（） 9、力法方程中，主系数恒为正，副系数可为正、负或零。（） 三、填空题（每空2分，共42分） 1、在梁、刚架、拱、桁架四种常见结构中，主要受弯的是和，主要承受轴力的是和。 2、选取结构计算简图时，一般要进行杆件简化、简化、简化和简化。 3、分析平面杆件体系的几何组成常用的规律是两刚片法则、和二元体法则。 4、建筑物中用以支承荷载的骨架部分称为，分为、和三大类。 5、一个简单铰相当于个约束。 6、静定多跨梁包括部分和部分，内力计算从部分开始。 9-12章数据结构作业答案 第九章查找 选择题 1、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A ) A．（n+1）/2 B. n/2 C. n D. [（1+n）*n ]/2 2. 下面关于二分查找的叙述正确的是 ( D ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储 3. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2)C ）时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）A) 个链表。 这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C) （1） A．17 B. 13 C. 16 D. 任意 （2） A．0至17 B. 1至17 C. 0至16 D. 1至16 判断题 1．Hash表的平均查找长度与处理冲突的方法无关。 (错) 2. 若散列表的负载因子α<1，则可避免碰撞的产生。（错） 3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（错） 填空题 1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20， 需做的关键码比较次数为 4 . 算法应用题 1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长 为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10解决冲突。要求：对该关 键字序列构造哈希表，并计算查找成功的平均查找长度。 2. 已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲 突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在 等概率情况下查找成功时的平均查找长度。 ３、对长度为20 的有序表进行二分查找，试画出它的一棵判定树，并求等概率情况下的平均 查找长度。 ４、设散列表的长度为15，散列函数H（K）=K%13，给定的关键字序列为20，16，29，82，37，02，06，28，55，39，23，10，试写出分别用拉链法和线性探测法解决冲突时所构造的散 列表，并求出在等概率情况下，这两种方法查找成功时的平均查找长度。 数据结构复习题集 一、判断题 1.线性表的长度是线性表所占用的存储空间的大小。( F ) 2.双循环链表中，任意一结点的后继指针均指向其逻辑后继。( F ) 3.在对链队列做出队操作时，不会改变front指针的值。( F ) 4.如果两个串含有相同的字符，则说它们相等。( F ) 5.如果二叉树中某结点的度为1，则说该结点只有一棵子树。(T ) 6.已知一棵树的先序序列和后序序列，一定能构造出该树。( F ) 7.图G的一棵最小代价生成树的代价未必小于G的其它任何一棵生成树的代价。(T ) 8.图G的拓扑序列唯一，则其弧数必为n-1（其中n为顶点数）。( F ) 9.对一个堆按层次遍历，不一定能得到一个有序序列。(T ) 10.直接选择排序算法满足：其时间复杂度不受数据的初始特性影响，为O(n2)。(T ) 11. 线性表的逻辑顺序与物理顺序总是一致的。( F ) 12. 线性表的顺序存储表示优于链式存储表示。( F ) 13.线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。(T ) 14. 二维数组是其数组元素为线性表的线性表。( F ) 15. 每种数据结构都应具备三种基本运算：插入、删除和搜 索。(T ) 16.（101，88，46，70，34，39，45，58，66，10）是堆；(T ) 17.将一棵树转换成二叉树后，根结点没有左子树；( F ) 18.对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同；(F) 19.哈夫曼树是带权外部路径长度最短的树，路径上权值较大的结点离根较近( T ) 20.用一组地址连续的存储单元存放的元素一定构成线性表。(F) 21.堆栈、队列和数组的逻辑结构都是线性表结构。( T ) 22.给定一组权值，可以唯一构造出一棵哈夫曼树。( F) 23.相对于索引文件的基本数据，索引表包含的信息量相对少得多，因此。索引表可以常驻内存。( T) 24.在平均情况下，快速排序法最快，堆积排序法最节省空间。( T) 25.快速排序法是一种稳定性排序法。( F ) 二.选择题: 1.一个栈的输入序列为12345，则下列序列中是栈的输出序列的是（A）。 A.23415 B.54132 C.31245 D.1425 3 2．设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为（D）。 A.r-f B.r-f+1 C.(r-f) mod n +1 D.(r-f+n) mod n 3．二叉树在线索化后，仍不能有效求解的问题是（D）。 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 第一章 1. 怎样理解“算法+数据结构=程序”这个公式？举例说明。 算法是语句序列解决特定问题的固有程序片段。数据结构是确定数据间的关系。从具体问题抽象出一个合适的数学模型、然后设计一个解决此数学模型的算法，最后编写出程序。寻求数学模型的是指就是数据结构要完成的工作。参看书p1前两段的描述。 2. 数据结构的概念，它包含哪三方面的内容？ 数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间饿关系和操作的学科。参看书p3 包含三方面的内容:1、数据之间的逻辑关系2、数据在计算机中的存储方式3、在数据上定义的运算的集合。 3. 数据、数据元素、数据项的基本概念。举例说明数据元素和数据项的联系与区别。 数据：描述客观事物的数字、字符以及所有能直接输入到计算机中并被计算机程序处理的符号的集合。 数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑或处理。 数据项：数据项是具有独立含义的最小标识单位，是数据元的一个具体值，是数据记录中最基本的、不可分的有名数据单位。 例1：class A { int c[123]; int i; }; class B { A a; } B b; b.a是数据项，B是数据元素 例2：一本书的数目信息为一个数据元素，而数目信息中每一项（如书名、作者名等）为一个数据项 4. 从逻辑结构来看，数据结构有哪四种基本结构，各自的特点是什么？ 1、集合（数据元素之间同属于一个集合，再无其他关系） 2、线性结构（数据元素之间存在一对一的关系） 3、树形结构（数据元素之间一对多的关系） 4、图状结构或网状结构（数据元素之间多对多的关系） 5. 从物理结构来看，数据结构有哪两种基本结构，各自的特点是什么？ 1、顺序存储结构 特点：借助元素在存储器中的相应位置来表示数据元素之间的逻辑关系。 2、链式存储结构 特定：借助元素在存储地址的指针表示数据元素之间的逻辑关系。 6. 算法的5个特征，4个评价标准是什么？ 特征:有穷性、确定性、可行性、输入、输出。 评价标准：正确性、可读性、健壮性、效率与低存储量需求。 7. 描述时间复杂度。 2010年《数据结构》期终考试试卷（A） 班级学号姓名 一、简答题（每小题6分，共30分） (1) 假设一个线性链表的类名为linkedList，链表结点的类名为ListNode，它包含两个数据成员data和link。data存储该结点的数据，link是链接指针。下面给定一段递归打印一个链表中所有结点中数据的算法： void PrintList (ListNode *L) { if ( L != NULL ) { cout << L->data << endl; PrintList ( L->link ); } } 试问此程序在什么情况下不实用？给出具体修改后的可实用的程序？ (1) 此程序在内存容量不足时不适用。因为需要一个递归工作栈。当链表越长，递归工作栈的深度越深，需要的存储越多。可采用非递归算法节省存储。 void PrintList (ListNode *L) { while ( L != NULL ) { cout << L->data << endl; L = L->link; } } (2) 如果每个结点占用2个磁盘块因而需要2次磁盘访问才能实现读写，那么在一棵有n个关键码的2m阶B树中，每次搜索需要的最大磁盘访问次数是多少？ (2) 在2m阶B树中关键码个数n与B树高度h之间的关系为h≤log m ((n+1)/2)+1，那么每次搜索最大磁盘访问次数为2h max = 2log m ((n+1)/2)+2。 (3) 给定一棵保存有n 个关键码的m 阶B 树。从某一非叶结点中删除一个关键码需要的最大磁盘访问次数是多少？ (3) 在m 阶B 树中关键码个数n 与B 树最大高度h 的关系为h = log ?m/2?((n+1)/2)+1。若设寻找被删关键码所在非叶结点读盘次数为h ’，被删关键码是结点中的k i ，则从该结点的p i 出发沿最左链到叶结点的读盘次数为h -h ’。当把问题转化为删除叶结点的k 0时，可能会引起结点的调整或合并。极端情况是从叶结点到根结点的路径上所有结点都要调整，除根结点外每一层读入1个兄弟结点，写出2个结点，根结点写出1个结点，假设内存有足够空间，搜索时读入的盘块仍然保存在内存，则结点调整时共读写盘3(h -1)+1。总共的磁盘访问次数为 h ’+(h -h ’)+3(h -1)+1 = 4h -2 = 4(log ?m/2?((n+1)/2)+1)-2 = = 4log ?m/2?((n+1)/2)+2 (4) 给定一个有n 个数据元素的序列，各元素的值随机分布。若要将该序列的数据调整成为一个堆，那么需要执行的数据比较次数最多是多少？ (4) 设堆的高度为h = ?log 2(n+1)?，当每次调用siftDown 算法时都要从子树的根结点调整到叶结点，假设某子树的根在第i 层（1≤i ≤h -1），第h 层的叶结点不参加比较。从子树根结点到叶结点需要比较h -i 层，每层需要2次比较：横向在两个子女里选一个，再纵向做父子结点的比较。因此，在堆中总的比较次数为 )i h j ( 2j 2 2j 22 2j 2 2)i h (221 h 1 j j 1 -h 1 h 1 j j -1 h 1 h 1 j 1 -j -h 1h 1 i 1-i -=??=??=?=-∑ ∑∑∑-=-=--=-=代换 因为 2h-1 ≤n ≤2h -1，且∑-=∞ →=1 h 1j j h 22j lim ，则n 42n 22 j 221 h 1j j 1 h =??≤??∑-=- 清华大学研究生院2019年 考试科目：结构力学 题号：0901 一．计算图1所示珩架指定杆的轴力()12,N N (10分) 二．结构仅在ACB 部分温度升高t 度，并且在D 处作用外力偶M 。试求图示刚架A,B 两点间水平向的相对位移。已知：各杆的EI 为常值，α为线膨胀系数，h 为截面高度。 （20分） 三．用力法分析图3所示结构，绘M 图。计算时轴力和剪力对位移的影响略去不计。各杆的EI 值相同。 （20分） 积分表：2211sin sin 2,cos sin 22424 x x xdx x xdx x =-=+?? 四．试用位移法求解图4所示刚架并绘M 图。计算时不考虑轴力变形时对位移的影响。（20分） 杆端力公式： 一． 试用力矩分配法计算图5所示连续梁并绘M 图。（10分） 二． 求图示结构的自振频率和主振型，并作出振型图。已知：122,,m m EI m m ===常数，忽略阻尼影响。 （20分） 清华大学研究生院2019年招收硕士生入学 试题 考试科目：结构力学（包含结构动力学基础） 题号：0901 一． 选择题：在正确答案处画“√”。每题4分。 1．图示平面体系的几何组成性质是： A.几何不变且无多余联系的 B.几何不变且有多余联系的 C.几何可变的 D.瞬变的 2．图示结构A截面的剪力为： A. –P B. P C. P/2 D. –P/2 3.图示珩架内力为零的杆为： A.3根 B.6根 C.8根 D.7根 3．图示结构的超静定次数为： A．6次 B．4次 C ． 5次 D ． 7次 4． 图示梁当EI ＝常数时，B 端的转角是： A. 35/48ql EI (顺时针) B. 35/48ql EI (逆时针) C. 37/48ql EI (逆时针) D. 39/48ql EI (逆时针) 二．计算题 1． 已知图示结构的M 图，做Q.N 图。 （10分） 2． 若P=1在梁AB 上移动，试绘出C M 的影响线。当AB 梁上端布满均布竖向移动荷载q 时，C M 等于多少？ 三．图示珩架各杆EA 相同，不考虑质量m 水平运动时求体系的自振频率。（此句话为真题上原述，个人认为缺了个标点符号。） （20分） 四．图示结构是超静定几次的？试用力法分析该结构并绘M 图，设EA ＝10EI （21m ）。 （20分） 五．右图所示结构用位移法分析时有几个独立的基本未知量？试用位移法分析该结构并绘M 图。设各杆的EI 值相同。 （20分） 清华大学研究生院2009年招收硕士生入学 试题 考试科目：结构力学（包含结构动力学基础） 题号：0901 第一章绪论 1、数据结构就是计算机中存储、组织数据得方式。精心选择得数 据结构可以带来最优效率得算法。 2、程序设计= 算法+数据结构 3、解决问题方法得效率： ●跟数据得组织方式有关 ●跟空间得利用效率有关 ●跟算法得巧妙程度有关 4、数据：所有能输入到计算机中,且被计算机处理得符号得集合， 就是计算机操作对象得总称； 就是计算机处理得信息得某种特定得符号表示形式。 5、数据元素：数据中得一个“个体”,数据结构中讨论得基本单 位。相当于“记录”,在计算机程序中通常作为一个整体考 虑与处理。 6、数据项: 相当于记录得“域”, 就是数据得不可分割得最小单 位,如学号。数据元素就是数据项得集合。 7、数据对象：性质相同得数据元素得集合、 例如: 所有运动员得记录集合 8、数据结构：就是相互间存在某种关系得数据元素集合。 9、数据结构就是带结构得数据元素得集合。 10、不同得关系构成不同得结构。 11、次序关系： { ○1集合； ○2线性结构：结构中数据元素之间存在一对一得关系； ○3树形结构：结构中数据元素之间存在一对多得关系； ○4图状结构或网状结构：结构中数据元素之间存在多对多得关系。 17、C语言得优点：C语言可以直接操作内存。 18、每个节点都由两部分组成：数据域与指针域。 19、链接存储结构特点： ●比顺序存储结构得存储密度小 (每个节点都由数据域与指针域组成)。 ●逻辑上相邻得节点物理上不必相邻。 ●插入、删除灵活 (不必移动节点，只要改变节点中得指针)。 20、数据类型就是一个值得集合与定义在此集合上得一组操作 得总称。 21、ADT 有两个重要特征:数据抽象与数据封装。 22、抽象数据类型(Abstract Data Type 简称ADT)：就是指一个 数学模型以及定义在此数学模型上得一组操作。 23、抽象数据类型有：数据对象〈数据对象得定义〉、数据关 系〈数据关系得定义〉、基本操作〈基本操作得定义〉。24、数据类型得定义与含义。 定义：数据类型就是一个值得集合与定义在这个值集上得一清华大学结构力学2007-2011真题
数据结构 清华大学出版社 严蔚敏吴伟民编著
严蔚敏版数据结构课后习题答案-完整版
数据结构(C语言版)第7章练习 答案 清华大学出版社
2014年清华大学804结构力学结构力学++真题
清华大学数据结构试题及答案
李春葆数据结构习题与解析(修订版)知识分享
数据结构课后习题答案清华大学出版社殷人昆
严蔚敏数据结构题集(C语言版)完整
数据结构(C语言版)第三版__清华大学出版社_习题参考答案
2013年清华大学804结构力学真题
数据结构(C语言版)9-12章练习 答案 清华大学出版社
严蔚敏版数据结构复习题
数据结构习题集答案解析_清华大学版
数据结构老师给的复习要点(严蔚敏版)
《数据结构》期终考试试卷(A)-清华大学
清华大学研究生院结构力学2019-2019考研真题-9页文档资料
数据结构,清华大学出版社,严蔚敏吴伟民编著
- 【盛世清北】2021清华980结构力学考研备考资料及如何有效复习
- 清华大学结构力学(一)
- 清华大学结构力学上—叶康生葵花宝典
- 清华大学836普通物理考研参考书目、考研真题、复试分数线
- 清华大学627艺术设计基础考研参考书目、考研真题、复试分数线
- 清华大学824工程力学考研参考书目、考研真题、复试分数线
- 清华大学813结构力学基础考研参考书目、考研真题、复试分数线
- 2013年清华大学804结构力学考研真题
- 2013年清华大学804结构力学真题
- 清华大学历年结构力学考研真题
- 清华大学611马克思主义基本原理考研参考书目、考研真题、复试分数线
- 《结构力学Ⅰ》考研2021考研结构力学真题库
- 2021清华大学804结构力学考研经验-清华考研辅导班
- 清华大学611马克思主义基本原理考研参考书目、考研真题、复试分数线新
- 清华大学结构力学2018年考研真题
- 清华大学1995年结构力学试卷
- 清华大学结构力学共38页
- 清华大学考研结构力学2016-2020考研真题
- 2014年清华大学804结构力学结构力学++真题
- 清华大学结构力学2007-2011真题