数据结构5-数组答案

数据结构（c语言版）第五章答案第五章1、设二维数组A【8】【10】是一个按行优先顺序存储在内存中的数组，已知A【0】【0】的起始存储位置为1000，每个数组元素占用4个存储单元，求：（1）A【4】【5】的起始存储位置。

A【4】【5】的起始存储位置为1000+（10*4+5）*4=1180；（2）起始存储位置为1184的数组元素的下标。

起始存储位置为1184的数组元素的下标为4（行下标）、6（列下标）。

2、画出下列广义表D=（（c），(e)，(a，(b，c，d))）的图形表示和它们的存储表示。

略，参考第5·2节应用题第5题分析与解答。

3、已知A为稀疏矩阵，试从时间和空间角度比较采用两种不同的存储结构（二维数组和三元组表）实现求∑a(i，j)运算的优缺点。

稀疏矩阵A采用二维数组存储时，需要n*n个存储单元，完成求∑ii a(1≤i≤n)时，由于a【i】【i】随机存取，速度快。

但采用三元组表时，若非零元素个数为t，需3t+3个存储单元（t个分量存各非零元素的行值、列值、元素值），同时还需要三个存储单元存储存稀疏矩阵A的行数、列数和非零元素个数，比二维数组节省存储单元；但在求∑ii a（1≤i≤n）时，要扫描整个三元组表，以便找到行列值相等的非零元素求和，其时间性能比采用二维数组时差。

4、利用三元组存储任意稀疏数组时，在什么条件下才能节省存储空间？当m行n列稀疏矩阵中非零元素个数为t，当满足关系3*t<m*n 时，利用三元组存储稀疏数组时，才能节省存储空间。

< bdsfid="74" p=""></m*n时，利用三元组存储稀疏数组时，才能节省存储空间。

<>5、求下列各广义表的操作结果。

（1）GetHead((a,(b,c),d))GetHead((a,(b,c),d))=a（2）GetTail((a,(b,c),d))GetTail((a,(b,c),d))=((b,c),d)（3）GetHead(GetTail((a,(b,c),d)))GetHead(GetTail((a,(b,c),d)))=(b,c)（4）GetTail(GetHead((a,(b,c),d)))GetTail(GetHead((a,(b,c),d)))=()第六章1、已知一棵树边的集合为{（i,m）,(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)}用树形表示法画出此树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶结点？（3）哪个是g的双亲？（4）哪些是g的祖先？（5）哪些是g的孩子？（6）哪些是e的子孙？（7）哪些是e的兄弟？哪些是f的兄弟？（8）结点b和n的层次号分别是什么？（9）树的深度是多少？（10）以结点c为根的子树的深度是多少？（11）树的度数是多少？略。

《数据结构》填空作业题答案第1章绪论（已校对无误）1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。

2．程序包括两个内容：数据结构和算法。

3. 数据结构的形式定义为：数据结构是一个二元组： Data Structure =（D，S）。

4. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。

5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。

6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。

7. 在树形结构中，数据元素之间存在一对多的关系。

8. 数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。

9. 数据的逻辑结构包括线性结构、树形结构和图形结构 3种类型，树型结构和有向图结构合称为非线性结构。

10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。

11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。

12. 数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。

13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。

14. 数据结构在物理上可分为顺序存储结构和链式存储结构。

15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。

16. 数据元素可由若干个数据项组成。

17. 算法分析的两个主要方面是时间复杂度和空间复杂度。

18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。

19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出。

20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切的定义，并在有穷时间内计算出结果。

1.二维数组A行下标i的范围从1到12，列下标j的范围从3到10，采用行序为主序存储，每个数据存储元素占用4个存储单元，该数组的首地址（既A[1][3]的地址）为1200，则A[6][5]的地址为（D）A.1400B.1404C.1372D.13682.有一个M*N的矩阵A,若采用行序为主序进行顺序存储，每个元素占用8个字节，则A ij (1≤i≤M,1≤i≤N)元素的相对字节地址（相对首元素地址而言）为（B）A.((i-1)*N+j)*8B.((i-1)*N+j-1)*8C.(i*N+j-1)*8D.((i-1)*N+j+1)*83.稀疏矩阵一般的压缩存储方法有两种，即（D）A.二维数组和三维数组B.三元组和散列C.散列和十字链表D.三元组和十字链表4.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点(B)A.正确B.错误5.广义表（（a,b）,c,d)的表头是（C），表尾是（D）。

A.aB.bC.(a,b)D.(c,d)6.一个广义表的表头总是广义表，这个断言是（B）A.正确B.错误7.二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是（326）8.有一个10阶对称矩阵A，采用压缩存储方式（以行序为主存储，且A[0][0]=1），则A[4][3]的地址是（14）9.一个广义表为（a,（a,b）,d,e,((i,j),k))，则该广义表的长度为（5），深度为（3）10.广义表((a),((b),c),(((d))))的表头是（（a）），表尾是（（((b),c),(((d)))））11.已知广义表A=（（a,b,c），（d,e,f）），则广义表运算head(tail(tail(A)))=(e)12.已知广义表GL=（a,(b,c,d),e），运用head和tail函数取出GL中的原子b的运算是（head(head(tail(GL)))）13.特殊矩阵和压缩矩阵哪一种压缩存储后会失去随机存取的功能？为什么？答：稀疏矩阵在进行压缩存储后会失去随机存取的功能，因为非零元素的位置没有办法确定。

数据结构(C语言版)习题参考答案数据结构(C语言版)习题参考答案1. 数据结构简介数据结构是计算机科学中重要的概念之一，它关注如何组织和存储数据，以便有效地进行访问和操作。

C语言是一种广泛应用于数据结构实现的编程语言。

本文将提供一些常见数据结构习题的参考答案，帮助读者理解和掌握数据结构的基本概念与实现。

2. 数组数组是一种线性结构，存储具有相同数据类型的元素。

以下是一些数组习题的参考答案：2.1 统计数组中某个元素出现的次数```int countOccurrences(int arr[], int n, int x) {int count = 0;for (int i = 0; i < n; i++) {if (arr[i] == x) {count++;}}return count;}```2.2 查找数组中的最大值和最小值```void findMinMax(int arr[], int n, int* min, int* max) { *min = arr[0];*max = arr[0];for (int i = 1; i < n; i++) {if (arr[i] < *min) {*min = arr[i];}if (arr[i] > *max) {*max = arr[i];}}}```3. 链表链表是一种动态数据结构，每个节点包含数据和指向下一个节点的指针。

以下是一些链表习题的参考答案：3.1 反转链表```Node* reverseLinkedList(Node* head) {Node* prev = NULL;Node* curr = head;while (curr != NULL) {Node* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}```3.2 合并两个有序链表```Node* mergeLists(Node* list1, Node* list2) {if (list1 == NULL) {return list2;}if (list2 == NULL) {return list1;}if (list1->data < list2->data) {list1->next = mergeLists(list1->next, list2);return list1;} else {list2->next = mergeLists(list1, list2->next);return list2;}}```4. 栈和队列栈和队列是两种重要的线性数据结构，栈支持后进先出（LIFO），队列支持先进先出（FIFO）。

1、以行序优先顺序存储数组A[5][5]；假定A[0][0]的地址为1000, 每个元素占4个字节，下标变量A[4][3]的地址是____。

A.1069B.1092C.1023D.1046正确答案：B2、数组a[1．．6][1．．5] （无0行0列）以列序优先顺序存储，第一个元素a[1][1]的地址为1000，每个元素占2个存储单元，则a[3][4]的地址是____。

A.1040B.1026C.1046D.1038正确答案：A3、设有一个5行4列的矩阵A，采用行序优先存储方式，A[0][0]为第一个元素，其存储地址为1000，A[2][2]的地址为1040，则A[3][0]的地址为_________。

A.1048B.1024C.1096D.1060正确答案：A4、设有一个10行10列的矩阵A，采用行序优先存储方式，存储全部数据需要400个字节的空间。

如果A[0][0]为第一个元素，其存储地址为1000，则A[3][6]的地址为_________。

A.1036B.1144C.1014D.10565、设有一个10行10列的矩阵A，采用行序优先存储方式。

如果A[0][0]为第一个元素，其存储地址为1000，A[2][3]的存储地址为1069，则存储一个元素需要的单元数是_________。

A.4B.1C.2D.3正确答案：D6、不能够对数据元素进行随机访问的物理结构是_________。

A.三元组顺序表B.对称矩阵的压缩存储C.三对角矩阵的压缩存储D.数组的顺序存储正确答案：A7、对特殊矩阵采用压缩存储的目的主要是_________。

A.表达变得简单B.去掉矩阵中的多余元素C.对矩阵元素的存储变得简单D.减少不必要的存储空间正确答案：D8、对n*n的对称矩阵进行压缩存储，需要保存的数据元素的个数是_________。

A.nB.n(n+1)/2C.n2D.n(n+1)9、设10*10的对称矩阵下三角保存SA[1．．55]中，其中A[1][1]保存在SA[1]中，A[5][3] 保存在SA[k]中，这里k等于_________。

第5章：数组和广义表 1. 了解数组的定义；填空题：1、假设有二维数组A 6×8，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A 的起始存储位置（基地址）为1000，则数组A 的体积（存储量）为 288 B ；末尾元素A 57的第一个字节地址为 1282 。

2、三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。

2. 理解数组的顺序表示方法会计算数组元素顺序存储的地址；填空题：1、已知A 的起始存储位置（基地址）为1000，若按行存储时，元素A 14的第一个字节地址为 (8+4)×6+1000=1072 ；若按列存储时，元素A 47的第一个字节地址为 (6×7＋4)×6＋1000）＝1276 。

(注：数组是从0行0列还是从1行1列计算起呢？由末单元为A 57可知，是从0行0列开始！) 2、设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 8950 。

答：不考虑0行0列，利用列优先公式： LOC(a ij )=LOC(a c 1，c 2)+[(j-c 2)*(d 1-c 1+1)+i-c 1)]*L 得：LOC(a 32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950选择题：（ A ）1、假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。

（无第0行第0列元素）A ．16902B ．16904C ．14454D ．答案A, B, C 均不对 答：此题（57列×60行＋31行）×2字节＋10000=16902( B )2、设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是：A ．i(i-1)/2+j-1B ．i(i-1)/2+jC ．i(i+1)/2+j-1D ．i(i+1)/2+j3、从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。

《数据结构》第五章习题参考答案一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、知道一颗树的先序序列和后序序列可唯一确定这颗树。

( ×)2、二叉树的左右子树可任意交换。

（×）3、任何一颗二叉树的叶子节点在先序、中序和后序遍历序列中的相对次序不发生改变。

（√）4、哈夫曼树是带权路径最短的树，路径上权值较大的结点离根较近。

（√）5、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。

( ×)6、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。

( √)7、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。

（×）8、度为2的树就是二叉树。

（×）二、单项选择题1．具有10个叶结点的二叉树中有（ B ）个度为2的结点。

A．8 B．9 C．10 D．112．树的后根遍历序列等同于该树对应的二叉树的( B )。

A. 先序序列B. 中序序列C. 后序序列3、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG 。

该二叉树根的右子树的根是：( C )A. EB. FC. GD. H04、在下述结论中，正确的是（ D ）。

①具有n个结点的完全二叉树的深度k必为┌log2(n+1)┐；②二叉树的度为2；③二叉树的左右子树可任意交换；④一棵深度为k(k≥1)且有2k-1个结点的二叉树称为满二叉树。

A．①②③B．②③④C．①②④D．①④5、某二叉树的后序遍历序列与先序遍历序列正好相反，则该二叉树一定是（ D ）。

A．空或只有一个结点B．完全二叉树C．二叉排序树D．高度等于其结点数三、填空题1、对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为__2n____个，其中___n-1_____个用于指向孩子结点，___n+1___个指针空闲着。

2、一棵深度为k(k≥1)的满二叉树有_____2k-1______个叶子结点。

数据结构-第5章--数组练习题第5章数组一、选择题3.设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为(A)。

A.BA+141B.BA+180C.BA+222D.BA+2254.假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（A）。

A.808B.818C.1010D.10205.数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是()。

1195A.1175B.1180C.1205D.12107.将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。

供选择的答案：A.198B.195C.1972+64某3=19410.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（iA.i某(i-1)/2+jB.j某(j-1)/2+iC.i某(i+1)/2+jD.j某(j+1)/2+i11.设A是n某n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为(C)。

A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-112.A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（AB）。

《数据结构》第五章 数组 习题基本概念题：5-1 分别写出一维数组和二维数组的存储映象公式。

5-2 什么叫二维数组的行序优先存储？什么叫二维数组的列序优先存储？C 语言采用的是行序优先存储还是列序优先存储？5-3 什么叫随机存储结构？为什么说数组是一种随机存储结构？5-4 动态数组和静态数组在使用方法上有什么不同？5-5 什么样的矩阵叫特殊矩阵？特殊矩阵压缩存储的基本思想是什么？5-6 什么样的矩阵叫稀疏矩阵？稀疏矩阵压缩存储的基本思想是什么？5-7 什么叫稀疏矩阵的三元组？什么叫稀疏矩阵的三元组线性表？5-8 稀疏矩阵主要有哪些压缩存储结构？复杂概念题：5-9 设一个系统中二维数组采用以行序为主的存储方式存储，已知二维数组a[n][m]中每个数据元素占k 个存储单元，且第一个数据元素的存储地址是Loc(a[0][0])，求数据元素a[i][j](0≤i≤n -1, 0≤j≤m -1)的存储地址。

5-10 设一个系统中二维数组采用以行序为主的存储方式存储，已知二维数组a[10][8]中每个数据元素占4个存储单元，且第一个数据元素的存储地址是1000，求数据元素a[4][5]的存储地址。

5-11 画出一个3行3列二维动态数组存储结构示意图。

5-12 对于如下所示的稀疏矩阵A（1）写出该稀疏矩阵的三元组线性表；（2）画出稀疏矩阵A 的三元组顺序表结构；（3）画出稀疏矩阵A 的带头结点单链表结构；（4）画出稀疏矩阵A 的行指针数组链表结构；（5）画出稀疏矩阵A 的三元组十字链表结构。

算法设计题：5-13 为节省内存，n 阶对称矩阵采用压缩存储，要求：（1）编写实现C = A + B 操作的函数。

设矩阵A 、矩阵B 和矩阵C 均采用压缩存储方式存储，矩阵元素均为整数类型。

（2）编写一个采用压缩存储的n 阶对称矩阵的输出函数，要求输出显示成矩阵形式，设矩阵元素均为整数类型。

（3）设矩阵A 和矩阵B 为如下所示的矩阵，编写一个用矩阵A 和矩阵B 作为测试例子的测试上述函数的主程序。

第五章习题5.1 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。

已知A的基地址为1000，计算：数组A共占用多少字节；数组A的最后一个元素的地址；按行存储时元素A36的地址；按列存储时元素A36的地址；5.2 设有三对角矩阵An×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= aij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i,j的下标变换公式。

5.3假设稀疏矩阵A和B均以三元组表作为存储结构。

试写出矩阵相加的算法，另设三元组表C存放结果矩阵。

5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。

5.5写一个在十字链表中删除非零元素aij的算法。

5.6画出下面广义表的两种存储结构图示：((((a), b)), ((( ), d), (e, f)))5.7求下列广义表运算的结果：（1）HEAD[((a,b),(c,d))];（2）TAIL[((a,b),(c,d))];（3）TAIL[HEAD[((a,b),(c,d))]];（4）HEAD[TAIL[HEAD[((a,b),(c,d))]]];（5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];实习题若矩阵Am×n 中的某个元素aij是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。

假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。

第五章答案5.2设有三对角矩阵A n×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中，使得B[k]=a ij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i、j的下标变换公式。

【解答】（1）k=2(i-1)+j(2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余）5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。

数据结构实用教程参考答案数据结构实用教程参考答案引言：数据结构是计算机科学中非常重要的一门学科，它研究如何组织和存储数据以便高效地访问和操作。

对于计算机程序员来说，掌握数据结构的知识是必不可少的。

本文将提供一些数据结构实用教程的参考答案，帮助读者更好地理解和应用这些概念。

一、数组（Array）：数组是最简单的数据结构之一，它由一组有序的元素组成，可以通过索引来访问和修改元素。

以下是一些常见问题的参考答案：1. 如何在数组中查找一个元素？可以使用线性搜索或二分查找算法来实现。

线性搜索逐个比较元素，直到找到目标元素或搜索完整个数组。

二分查找算法则要求数组有序，通过递归或循环将数组分成两半进行查找，直到找到目标元素或确定不存在。

2. 如何在数组中插入和删除元素？插入元素时，需要将插入位置后的元素后移一位，然后将新元素插入到指定位置。

删除元素时，需要将删除位置后的元素前移一位，然后将数组长度减一。

这些操作的时间复杂度为O(n)，其中n为数组长度。

二、链表（Linked List）：链表是一种动态数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

以下是一些常见问题的参考答案：1. 如何在链表中查找一个元素？可以使用线性搜索算法来实现，从链表头节点开始逐个比较元素，直到找到目标元素或搜索完整个链表。

2. 如何在链表中插入和删除元素？插入元素时，需要创建一个新节点，并将其指针指向插入位置的下一个节点，然后将插入位置的前一个节点的指针指向新节点。

删除元素时，需要修改前一个节点的指针，使其指向删除位置的下一个节点。

这些操作的时间复杂度为O(1)，即常数时间。

三、栈（Stack）和队列（Queue）：栈和队列是两种常见的数据结构，它们都是限制插入和删除操作的顺序表。

以下是一些常见问题的参考答案：1. 如何实现栈和队列的插入和删除操作？栈的插入和删除操作遵循“先进后出”的原则，可以使用数组或链表来实现。

第五章数组与广义表一、假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000。

计算：1、数组A的体积（即存储量）；2、数组A的最后一个元素a57的第一个字节的地址；3、按行存储时，元素a14的第一个字节的地址；4、按列存储时，元素a47的第一个字节的地址；答案：1、（6*8）*6=2882、loc(a57)=1000+(5*8+7)*6=1282或=1000+（288-6）=12823、loc(a14)=1000+(1*8+4)*6=10724、loc(a47)=1000+(7*6+4)*6=1276二、假设按低下标(行优先)优先存储整数数组A9*3*5*8时第一个元素的字节地址是100，每个整数占四个字节。

问下列元素的存储地址是什么？（1）a0000(2)a1111(3)a3125 (4)a8247答案：（1）100（2）loc(a1111)=100+(1*3*5*8+1*5*8+1*8+1)*4=776(3) loc(a3125)=100+(3*3*5*8+1*5*8+2*8+5)*4=1784(4) loc(a8247)=100+(8*3*5*8+2*5*8+4*8+7)*4=4416五、设有一个上三角矩阵（aij）n*n,将其上三角元素逐行存于数组B[m]中，（m 充分大），使得B[k]=aij且k=f1(i)+f2(j)+c。

试推导出函数f1,f2和常数C（要求f1和f2中不含常数项）。

答：K=n+(n-1)+(n-2)+…..+(n-(i-1)+1)+j-i=(i-1)(n+(n-i+2))/2+j-i所以f1(i)=(n+1/2)i-1/2i2f2(j)=jc=-(n+1)九、已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存储结构（二维数组和三元组表）完成∑aii运算的优缺点。

（对角线求和）解：1、二维数组For(i=1;i<=n;i++)S=s+a[i][i];时间复杂度：O（n）2、for(i=1;i<=m.tu;i++)If(a.data[k].i==a.data[k].j) s=s+a.data[k].value;时间复杂度：O（n2）二十一、当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。

数据结构课后习题答案-完整版下面是《数据结构课后习题答案-完整版》的内容：---第一章：数组1. 题目：给定一个整数数组，判断是否存在两个元素之和等于目标值。

答案：使用双指针法，首先将数组排序，然后设置左指针指向数组头部，右指针指向数组尾部。

如果左指针和右指针指向的元素之和小于目标值，则左指针右移；如果大于目标值，则右指针左移；如果等于目标值，则找到了两个元素之和等于目标值的情况。

2. 题目：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数的下标。

答案：使用哈希表，在遍历数组的过程中，将每个元素的值和下标存储在哈希表中。

遍历到当前元素时，检查目标值与当前元素的差值是否在哈希表中，如果存在，则找到了两个数的下标。

---第二章：链表1. 题目：给定一个链表，判断链表中是否存在环。

答案：使用快慢指针法，定义两个指针，一个指针每次向前移动一个节点，另一个指针每次向前移动两个节点。

如果存在环，则两个指针必定会相遇。

2. 题目：给定一个链表，删除链表的倒数第N个节点。

答案：使用双指针法，定义两个指针，一个指针先移动N个节点，然后两个指针同时向前移动，直到第一个指针到达链表尾部。

此时第二个指针指向的节点即为要删除的节点。

---第三章：栈和队列1. 题目：设计一个栈，使得可以在常数时间内获取栈中的最小元素。

答案：使用辅助栈来保存当前栈中的最小元素。

每次压栈操作时，将当前元素与辅助栈的栈顶元素比较，只有当前元素较小才将其压入辅助栈。

2. 题目：设计一个队列，使得可以在常数时间内获取队列中的最大元素。

答案：使用双端队列来保存当前队列中的最大值。

每次入队操作时，将当前元素与双端队列的末尾元素比较，只有当前元素较大才将其压入双端队列。

---第四章：树和二叉树1. 题目：给定一个二叉树，判断它是否是平衡二叉树。

答案：通过递归遍历二叉树的每个节点，计算每个节点的左子树高度和右子树高度的差值。

如果任意节点的差值大于1，则该二叉树不是平衡二叉树。

数据结构练习题习题5 数组和广义表一、基本内容数组定义及表示方式；特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现；广义表的逻辑结构和存储结构。

二、学习要点1.了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。

2．掌握对特殊矩阵进行压缩存储时的下标变换公式。

3．了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。

4．掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯掌握任意一种结构的链表5.1 单项选择题1. 常对数组进行的两种基本操作是____。

A. 建立与删除B. 索引和修改查找与索引2. 二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从0到9，则存放M 至少需要①_ _个字节；M数组的第8列和第5行共占②____个字节。

①3. 二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是____。

4. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为____。

5. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为____。

5.21. 已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是__ LOC (A[0][0])+(n*i+j)*k __。

2. 二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是__ 200+（12*10+6）= 326_。