软件结构复习提纲以及复习题

软件技术基础以及数据的复习提纲：1. 语句频度和时间复杂度的求法，要求会计算两重循环的语句频度。2. 堆栈的出栈进栈的操作序列。6个元素的进栈出栈过程。3. 稀疏矩阵的存储矩阵的求解4. 单链表中节点的插入和删除算法。5. 二叉树的性质，三种遍历，排序二叉树的生成，利用某两种遍历序列构建原二叉树6. 能够根据给出的先根，中根，或者后根，中根序列，能够构建一个树7. 图的性质，图的存储。两种遍历结果8. 掌握四种排序算法的算方法思想，能够写出各种排序的输出序列。9. 冒泡算法10. 顺序查找算法1. 已知某算法有如下的代码:m=0;for i = 0; i n ; i + for j = 2*i; j n ; j+ m:=m+1;，试计算出该算法的关键语句的语句频度F（n）和时间复杂度T（n） = ？2. 已知某算法有如下的代码:m=0;for i = 0; i n ; i + for j = i; j n ; j+ m:=m+1;，试计算出该算法的关键语句的语句频度F（n）和时间复杂度T（n） = ？3. 如果输入序列为1 2 3 4 5 6, 允许中间出栈，但是每个元素只能入栈，出栈一次，试问能否通过栈结构得到以下两个出栈序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能或如何才能得到。4. 如果输入序列为6，5，4，3，2，1,允许中间出栈，但是每个元素只能入栈，出栈一次，试问能否通过栈结构得到以下两个出栈序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能或如何才能得到。5. 设矩阵0 0 0 20 0 8 00 4 0 01 0 5 0 A= 若将A视为稀疏矩阵写出对其压缩存储的存储矩阵?并计算出这样存储的效率？6. 设矩阵4 0 0 00 3 0 00 0 3 02 0 0 4 A= 若将A视为稀疏矩阵写出对其压缩存储的存储矩阵?7. 已知某有头结点的单链表L（链上节点的数据元素是a1,a2, ai, an），试写出删除第i个节点的算法void DeleteNode(Node* l, int i)：8. 已知有以下多项式:，请根据自己学习的数据结构的知识，将该多项式存储到内存中，以便后续数学处理。 void DeleteNode(Node* l, int i)9. 由下图给出的二叉树，求出先序，中序，后序遍历结点的序列10. 由下图给出的二叉树，求出先序，中序，后序遍历结点的序列11. 假设以行序为主序存储二维数组A=array1.100，1.100，设每个数据元素占2个存储单元，基地址为10，则LOC5,5=？12. 假设一个二叉树的两种遍历如下先根：ABHFDECKG，中根：HBDFAEKCG试画出该二叉树，并给出后根遍历序列？13. 已知有如下的图：试写出从节点C开始的深度遍历序列和广度遍历序列？14. 已知，有一数组iarray = 23，14，56，34，92，19，77，35，80请分别写出一趟冒泡排序，二趟快速后的输出序列，15. 学生成绩分别为75、65、56、88、67、90、87、70、77、72、91试以该顺序建立一棵二叉排序树，并写出该树的中序遍历序列？16. 1）已知用于排序的顺序表结构体采用如下的定义：typedef struct keytype key; / 关键值 elemtype;typedef struct elemtype dataMAXNUM; /最大容量 int length; / 实际存放的数据元素个数。 tabletype;tabletype *table; / 实际使用的待排数据表指针请写出采用该顺序表的冒泡算法的C语言程序来？算法原型声明如下：void bubble_sort( tabletype * table);2）已知某待排序的序列的关键字如下 34,67,21,67,89,65,78,12,66经过一趟冒泡算法的处理，得到的结果序列是什么？17. 已知待查找的顺序表的结构体定义如下：typedef struct keytype key; / 关键值 elemtype;typedef struct elemtype dataMAXNUM; /最大容量 int length; / 实际存放的数据元素个数。 tabletype;tabletype *table; / 实际使用的待检索数据表指针试写出书序查找关键字aK