课后作业部分第四章串
strcpy是串复制(copy)函数：char *strcpy(char to,char from); //该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。
void StrDelete(char *S, int i ,int m) { //串删除
char Temp[Maxsize];//定义一个临时串 if(i+m strcpy (Temp, &S[i+m]);//把删除的字符以后的字符保存到临时串中 strcpy( &S[i],Temp);//用临时串中的字符覆盖位置i之后的字符 } else if(i+m>=strlen(S)&& i strcpy(&S[i],\把位置i的元素置为'\\0'，表示串结束 } } 9 课后作业部分第五章数组和广义表 第五章数组和广义表 一. 填空 1. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288；末尾元素A57的第一个字节地址为1282；若按行存储时，元素A14的第一个字节地址为1072；若按列存储时，元素A47的第一个字节地址为1276。 2. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。。 3. 广义表((a), (((b),c)),(d))的长度是3，深度是4，表头是 (a) ，表尾是(((b),c)),(d) 。 4. 已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是 Head(Head(Tail(LS)))。 二. 选择题 1. 假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为( A )。（无第0行第0列元素） A 16902 B 16904 C 14454 D 答案A, B, C均不对 2. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[ 1, n(n-1)/2 ]中，下三角部分中任一元素ai,j(i≤j), 在一维数组B中下标k的值是：( B ) A i(i-1)/2+j-1 B i(i-1)/2+j C i(i+1)/2+j-1 Di(i+1)/2+j 3. 一个n*n的对称矩阵，用压缩存储方法处理其对称性质后存储，则其容量为：( C )。 An*n Bn*n/2 C (n+1)*n/2 D (n+1)*(n+1)/2 三. 计算题 1. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？写出计算过程。 (676-644)/1=32 A[2][2]的地址相对A[0][0]偏移量为32，则A[3][3]相较于A[0][0]的偏移量为32*3/2=48 A[3][3]地址为48+644=692 2. 设A[9][9]是一个10*10对称矩阵，采用压缩存储方式存储其下三角部分，已知每个元素占用两个存储单元，其第一个元素A[0][0]的存储位置在1000，求下面问题的计算过程及结果： 给出A[4][5]的存储位置。 10 课后作业部分第五章数组和广义表 A[4][5]是上三角部分，所以存在 A [5] [4] 若以行序为主序，则地址为1000+2（5（1+5）/ 2+4）=1036 若以列序为主序，则地址为1000+2（4（10+7）/ 2+5）=1062 给出存储位置为1080的元素下标。 i(i+1)/2+j或j(10+10-j+1)/2+i=40 得i=9，j=4或i=8 j=5，A [8] [5]或A [9] [4] 3. 一个稀疏矩阵如图所示，则对应的三元组线性表是什么？其对应的十字链表是什么？ 0 0 2 0 3 0 0 0 0 0 -1 5 0 0 0 0 4. 下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。 ?6?1??2?(1)?3?4??5??6 46?22??112??13? 44??36?116??0 2 0 0 120 0 0 3 0 0 0 0 0 0 4 0 06 0 160 00 11 课后作业部分第五章数组和广义表 四. 算法设计 1. 设计一个算法，计算一个三元组表表示的稀疏矩阵的对角线元素之和。 2. 若在矩阵A中存在一个元素ai,j（0≤i≤n-1，0≤j≤m-1），该元素是第i行元素中最小值且又是第j列元素中最大值，则称此元素为该矩阵的一个鞍点。假设以二维数组存储矩阵A，试设计一个求该矩阵所有鞍点的算法，并分析最坏情况下的时间复杂度 void Saddle(int A[m][n]) //A是m*n的矩阵,本算法求矩阵A中的马鞍点. {int max[n]={0}, //max数组存放各列最大值元素的行号,初始化为行号0; min[m]={0}, //min数组存放各行最小值元素的列号,初始化为列号0; i, j; for(i=0;i {if(A[max[j]][j]A[i][j]) min[i]=j; //修改第i行最小元素的列号. } for (i=0;i {j=min[i]; //第i行最小元素的列号 if(i==max[j])printf(“A[%d][%d]是马鞍点，元素值是%d”,i,j,A[i][j]); } } }// Saddle 分析算法，外层for循环共执行m次，内层第一个for循环执行n次，第二个for循环最坏情况下执行m次，所以，最坏情况下的时间复杂度为Ｏ(mn+mm)。 12 课后作业部分第六章树和二叉树 第六章树和二叉树 一. 填空题 1. 树是n（n≥0）结点的有限集合。在一棵空树中有0个元素；在一棵非空树中，有且仅有一个个根结点，其余的结点分成m（m＞0）个互不相交的集合，每个集合都是根结点的子树。 2. 一棵二叉树的第i（i≥1）层最多有2i-1个结点；一棵有n（n>0）个结点的满二叉树共有(n+1)/2个叶子结点和(n-1)/2个非终端结点。 3. 设深度为k的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是2k-1，最小值是2k-1。 4. 深度为k的二叉树中，所含叶子的个数最多为2k-1。 5. 在顺序存储的二叉树中编号为i和j的两个结点处在同一层的条件为： 二. 选择题 1. 前序遍历和中序遍历结果相同的二叉树是（ D）。 A 根结点无左孩子的二叉树 B 根结点无右孩子的二叉树 C 所有结点只有左子树的二叉树D 所有结点只有右子树的二叉树 2. 序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1] ~ A[n]中，结点A[i]若有左子树，则左子树的根结点是（D ）。 A A[2i-1] B A[2i+1] C A[i/2] D A[2i] 3. 完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（ C ）。 A h B h+1 C h或h+1 D 任意 4. 在线索二叉树中，一个结点是叶子结点的充要条件为（ C）。 A 左线索标志为0，右线索标志为1 B 左线索标志为1，右线索标志为0 C 左. 右线索标志均为0 D 左. 右线索标志均为1 5. 由权值为{3, 8, 6, 2, 5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（ C ）。 A 24B 48 C 53 D 72 三. 简答题 1. 已知二叉树的中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，请构造出此二叉树，并写出此树的后序遍历序列。 13