数据结构—矩阵课后题

数据结构习题集答案(C语言版严蔚敏)第2章线性表2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

解：头指针是指向链表中第一个结点的指针。

首元结点是指链表中存储第一个数据元素的结点。

头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。

它可以对空表、非空表以及首元结点的操作进行统一处理。

2.2 填空题。

解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。

(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。

单链表中逻辑上相邻的元素的物理位置不一定紧邻。

(3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。

(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。

2.3 在什么情况下用顺序表比链表好？解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。

2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。

解：2.5 画出执行下列各行语句后各指针及链表的示意图。

L=(LinkList)malloc(sizeof(LNode)); P=L;for(i=1;i<=4;i++){P->next=(LinkList)malloc(sizeof(LNode));P=P->next; P->data=i*2-1;}P->next=NULL;for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2);for(i=1;i<=3;i++) Del_LinkList(L,i);解：2.6 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是__________________。

第七章图（参考答案）7．1（1）邻接矩阵中非零元素的个数的一半为无向图的边数；（2）A[i][j]= =0为顶点，I 和j无边，否则j和j有边相通；（3）任一顶点I的度是第I行非0元素的个数。

7．2（1）任一顶点间均有通路，故是强连通；（2）简单路径V4 V3 V1 V2;（3）0 1 ∞ 1∞ 0 1 ∞1 ∞ 0 ∞∞∞ 1 0邻接矩阵邻接表（2）从顶点4开始的DFS序列：V5,V3,V4,V6,V2,V1（3）从顶点4开始的BFS序列：V4,V5,V3,V6,V1,V27．4（1）①adjlisttp g; vtxptr i,j; //全程变量② void dfs(vtxptr x)//从顶点x开始深度优先遍历图g。

在遍历中若发现顶点j，则说明顶点i和j间有路径。

{ visited[x]=1; //置访问标记if (y= =j){ found=1;exit(0);}//有通路，退出else { p=g[x].firstarc;//找x的第一邻接点while (p!=null){ k=p->adjvex;if （!visited[k]）dfs(k);p=p->nextarc;//下一邻接点}}③ void connect_DFS (adjlisttp g)//基于图的深度优先遍历策略，本算法判断一邻接表为存储结构的图g种，是否存在顶点i //到顶点j的路径。

设 1<=i ,j<=n,i<>j.{ visited[1..n]=0;found=0;scanf (&i,&j);dfs (i);if (found) printf （” 顶点”,i,”和顶点”,j,”有路径”）；else printf （” 顶点”,i,”和顶点”,j,”无路径”）；}// void connect_DFS(2)宽度优先遍历全程变量，调用函数与（1）相同，下面仅写宽度优先遍历部分。

第1章绪论2 、(1)×(2)×(3) √3 、(1)A(2)C(3)C5、f or计(算i=下1n程;序中 1 得语句频度for(j=1;j<=i; j++)for(k=1;k<=j;k ++)x=x+1;【解答】 x=x+1 得语句频度为：T(n)=1+(1+2)+(1+2+3)+. …+(1+2+……+n)=n(n+1)(n+2)/66 、编写算法，求一元多项式p。

(x)=a。

+a,x+a₂X2+……、+a Xn得值p(x) 并确定算法中每一语句得执行次数与整个算法得时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数.注意：本题中得输入为a,(i=01,…n)、x 与n,输出为P。

(x)。

算法得输入与输出采用下列方法(1)通过参数表中得参数显式传递(2)通过全局变量隐式传递。

讨论两种方法得优缺点，并在算法中以您认为较好得一种实现输入输出.【解答】(1)通过参数表中得参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。

缺点：形参须与实参对应，且返回值数量有限。

(2)通过全局变量隐式传递优点：减少实参预形参得个数，从而减少内存空间以及传递数据时得时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue({ int,in;floatx,a[]p;pri n tf(hn=”);s c anf(“%f,”&n);printf(“x=”;)sca nf(“%f&x);f or(i=0;i<n; i++)s c anf(%f ,&a[i]; /*执行次数：n 次 */p=a[0];for (i=1;i<=n;i++){ p=p+a [i]*x; /*执行次数：n次*/x= x*x;}prin t f(%f” p);}算法得时间复杂度：T(n)=0(n)通过参数表中得参数显式传递f loat PolyVa lue(float a[ ], float x, i nt n)f 1 oat p, s;int;is p a X0];for(=1;i<= n;i++)/执行次数：n 次*/{s=s+a [i]* p;p=p*x;}re turn(p);算法得时间复杂度：T(n)=O(n)第2章线性表习题1、填空：(1)在顺序表中插入或者删除一个元素，需要平均挪移一半元素，具体挪移得元素个数与插入或者删除得位置有关。

矩阵练习题及答案矩阵是线性代数中的一个重要概念，也是在数学、物理、计算机科学等领域中广泛应用的工具。

通过解矩阵练习题，可以帮助我们加深对矩阵运算和性质的理解。

下面给出一些矩阵练习题及其答案，供大家参考。

1. 问题描述：已知矩阵 A = [4 2]，求 A 的转置矩阵 A^T。

解答：矩阵的转置就是将矩阵的行和列互换得到的新矩阵。

因此，A 的转置矩阵为 A^T = [4; 2]。

2. 问题描述：已知矩阵 B = [1 -2; 3 4]，求 B 的逆矩阵 B^-1。

解答：对于一个可逆矩阵 B，其逆矩阵 B^-1 满足 B * B^-1 = I，其中 I 是单位矩阵。

通过矩阵的求逆公式，可以得到 B 的逆矩阵 B^-1 = [4/11 2/11; -3/11 1/11]。

3. 问题描述：已知矩阵 C = [2 1; -3 2]，求 C 的特征值和特征向量。

解答：矩阵的特征值和特征向量是矩阵在线性变换下的重要性质。

特征值λ 是方程 |C - λI| = 0 的根，其中 I 是单位矩阵。

解方程可得特征值λ1 = 1 和λ2 = 3。

特征向量 v1 对应于特征值λ1，满足矩阵C * v1 = λ1 *v1，解方程可得 v1 = [1; -1]。

特征向量 v2 对应于特征值λ2，满足矩阵C * v2 = λ2 * v2，解方程可得 v2 = [1; 3]。

4. 问题描述：已知矩阵 D = [1 2 -1; 3 2 4]，求 D 的行列式和秩。

解答：矩阵的行列式表示线性变换后单位面积或单位体积的变化率。

计算 D 的行列式可得 det(D) = 1 * (2*4 - 4*(-1)) - 2 * (3*4 - 1*(-1)) + (-1) * (3*2 - 1*2) = 10。

矩阵的秩表示矩阵中独立的行或列的最大个数。

对矩阵 D 进行行变换得到矩阵的行最简形式为 [1 0 6; 0 1 -3]，因此 D 的秩为 2。

矩阵习题带答案矩阵习题带答案矩阵是线性代数中的重要概念，广泛应用于各个领域。

掌握矩阵的运算和性质对于学习线性代数和解决实际问题都具有重要意义。

在这篇文章中，我们将提供一些矩阵习题，并附上详细的解答，帮助读者更好地理解和掌握矩阵的相关知识。

1. 习题一已知矩阵A = [1 2 3; 4 5 6; 7 8 9]，求矩阵A的转置矩阵AT。

解答：矩阵A的转置矩阵AT即将A的行变为列，列变为行。

因此，矩阵A的转置矩阵为：AT = [1 4 7; 2 5 8; 3 6 9]2. 习题二已知矩阵B = [2 4; 1 3]，求矩阵B的逆矩阵B-1。

解答：对于一个二阶矩阵B，如果其行列式不为零，即|B| ≠ 0，那么矩阵B存在逆矩阵B-1，且B-1 = (1/|B|) * [d -b; -c a]，其中a、b、c、d分别为矩阵B的元素。

计算矩阵B的行列式：|B| = ad - bc = (2*3) - (4*1) = 6 - 4 = 2因此，矩阵B的逆矩阵为：B-1 = (1/2) * [3 -4; -1 2]3. 习题三已知矩阵C = [1 2 3; 4 5 6]，求矩阵C的秩rank(C)。

解答：矩阵的秩是指矩阵中非零行的最大个数，也可以理解为矩阵的行向量或列向量的最大线性无关组的向量个数。

对于矩阵C，我们可以通过高斯消元法将其化为行简化阶梯形矩阵：[1 2 3; 0 -3 -6]可以看出，矩阵C中非零行的最大个数为1，因此矩阵C的秩为1。

4. 习题四已知矩阵D = [2 1; -1 3]，求矩阵D的特征值和特征向量。

解答：对于一个n阶矩阵D，如果存在一个非零向量X，使得D*X = λ*X，其中λ为常数，则称λ为矩阵D的特征值，X为对应的特征向量。

首先，我们需要求解矩阵D的特征值，即求解方程|D - λI| = 0，其中I为n阶单位矩阵。

计算矩阵D - λI：[D - λI] = [2-λ 1; -1 3-λ]设置行列式等于零，得到特征值的方程式：(2-λ)(3-λ) - (1)(-1) = 0λ^2 - 5λ + 7 = 0解特征值的方程，得到两个特征值：λ1 = (5 + √(-11))/2λ2 = (5 - √(-11))/2由于特征值的计算涉及到虚数，这里不再继续计算特征向量。

7_1对于图题7.1（P235）的无向图，给出：（1）表示该图的邻接矩阵。

（2）表示该图的邻接表。

（3）图中每个顶点的度。

解：（1）邻接矩阵：0111000100110010010101110111010100100110010001110（2）邻接表：1：2----3----4----NULL;2: 1----4----5----NULL;3: 1----4----6----NULL;4: 1----2----3----5----6----7----NULL;5: 2----4----7----NULL;6: 3----4----7----NULL;7: 4----5----6----NULL;（3）图中每个顶点的度分别为：3，3，3，6，3，3，3。

7_2对于图题7.1的无向图，给出：（1）从顶点1出发，按深度优先搜索法遍历图时所得到的顶点序（2）从顶点1出发，按广度优先法搜索法遍历图时所得到的顶点序列。

（1）DFS法：存储结构：本题采用邻接表作为图的存储结构，邻接表中的各个链表的结点形式由类型L_NODE规定，而各个链表的头指针存放在数组head中。

数组e中的元素e[0],e[1],…..,e[m-1]给出图中的m条边，e中结点形式由类型E_NODE规定。

visit[i]数组用来表示顶点i是否被访问过。

遍历前置visit各元素为0，若顶点i被访问过,则置visit[i]为1.算法分析：首先访问出发顶点v.接着，选择一个与v相邻接且未被访问过的的顶点w访问之，再从w 开始进行深度优先搜索。

每当到达一个其所有相邻接的顶点都被访问过的顶点，就从最后访问的顶点开始，依次退回到尚有邻接顶点未曾访问过的顶点u,并从u开始进行深度优先搜索。

这个过程进行到所有顶点都被访问过，或从任何一个已访问过的顶点出发，再也无法到达未曾访问过的顶点，则搜索过程就结束。

另一方面，先建立一个相应的具有n个顶点,m条边的无向图的邻接表。

填空题（10 * 1’ = 10’）一、概念题2.2.当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。

2.3.当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。

2.6.带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。

3.6.循环队列的引入，目的是为了克服假溢出。

4.2.长度为0的字符串称为空串。

4.5.组成串的数据元素只能是字符。

4.8.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。

7.2.为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。

5.7.广义表的深度是广义表中括号的重数7.8.有向图G可拓扑排序的判别条件是有无回路。

7.9.若要求一个稠密图的最小生成树，最好用Prim算法求解。

8.8.直接定址法法构造的哈希函数肯定不会发生冲突。

9.2.排序算法所花费的时间，通常用在数据的比较和交换两大操作。

1.1.通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。

1.2.对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。

1.3.存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。

1.4.抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。

1.5.一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。

2.8.在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。

2.9.在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。

数组和矩阵1、(2分)【单选题】某串的长度小于一个常数，则采用( )存储方式最节省空间A、链式B、顺序C、堆结构D、无法确定参考答案：B解析：串的顺序和链式存储结构2、(2分)【单选题】与线性表相比，串的插入和删除操作的特点是( )。

A、通常以串整体作为操作对象B、需要更多的辅助空间C、算法的时间复杂度较高D、涉及移动的元素更多参考答案：A解析：串的基本运算3、(2分)【单选题】在稀疏矩阵的三元组表示法中，每个三元组表示( )。

A、矩阵中非零元素的值B、矩阵中数据元素的行号和列号C、矩阵中数据元素的行号、列号和值D、矩阵中非零数据元素的行号、列号和值参考答案：D解析：二维数组的存储结构及求址方法4、(2分)【单选题】已知二维数组A8X10，按行存储时，元素a12的地址为1000，每个元素占2个字节，则元素a00的地址为( )A、972B、974C、976D、978参考答案：C解析：二维数组的存储结构及求址方法5、(2分)【单选题】数组通常具有的两种基本操作是( )A、建立和删除B、索引和修改C、查找和修改D、查找和索引参考答案：C解析：二维数组的存储结构及求址方法6、(2分)【单选题】在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是( )。

A、i＞0B、i≤nC、1≤i≤nD、1≤i≤n+1参考答案：D解析：串的基本运算7、(2分)【单选题】两个字符串相等的条件是( )。

A、两串的长度相等B、两串包含的字符相同C、两串的长度相等，并且两串包含的字符相同D、两串的长度相等，并且对应位置上的字符相同参考答案：D解析：串的基本运算8、(2分)【单选题】设有串s=“software”，则其子串的数目是( )。

A、36B、37C、8D、9参考答案：B解析：串的基本运算9、(2分)【单选题】广义表A=((x,(a,b)),((x,(a,b)),y),y)，则运算head(head(tail(A)))为( )A、xB、(a,b)C、(x,(a,b))D、A参考答案：C解析：广义表的概念10、(2分)【单选题】串的模式匹配是指( )。

1、特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么?答：后者在采用压缩存储后将会失去随机存储的功能。

因为在这种矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号作为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。

2、二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素（）的起始地址相同。

A、M[2][4]B、M[3][4]C、M[3][5]D、M[4][4]为第3、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11的地址为（）。

一元素，其存储地址为1，每个元素占一个地址空间，则a85A. 13B. 33C. 18D. 404、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线（i<j）上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij的位置k的关系为( )。

A. i*(i-1)/2+jB. j*(j-1)/2+iC. i*(i+1)/2+jD. j*(j+1)/2+i5、设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序(1≤i，j≤n，且i≤j)存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij在B中的位置为( )。

A. i(i-l)/2+jB. j(j-l)/2+iC. j(j-l)/2+i-1D. i(i-l)/2+j-16、设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。

A.（i-1）*n+jB.（i-1）*n+j-1C. i*（j-1）D. j*m+i-17、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。