下载文档原格式
数据结构〔本科〕期末综合练习二〔填空与判断题〕填空题数据是__信息__的载体，它能够被计算机程序识别、存储和加工处理。
数据结构包括逻辑结构、__存储结构__和数据的运算三个方面。
数据结构的逻辑结构包括线性结构和__非线性__结构两大类。
数据结构的存储结构包括顺序、__链接___、索引和散列等四种。
5. 根本数据类型是计算机已经实现了的_数据结构__。
抽象数据类型的特点是__数据封装__、信息隐蔽、使用与实现别离。
算法的一个特性是__有穷性__，即算法必须执行有限步就结束。
面向对象的特征应包括对象、类、__继承__、消息通信。
属性与效劳相同的对象构成类，类中的每个对象称为该类的__实例__。
对象的私有状态只能通过该对象的__操作〔或效劳〕_才能改变。
模板类是一种数据抽象，它把__数据类型_当作参数，可以实现类的复用。
1 2.在类的继承结构中，位于上层的类叫做基类，其下层的类那么叫做__派生〔或子〕__类。
1 3.一维数组所占用的空间是连续的。
但数组元素不一定顺序存取，通常是按元素的__下标〔或顺序号〕__存取的。
在程序运行过程中不能扩充的数组是__静态__分配的数组。
这种数组在声明它时必须指定它的大小。
在程序运行过程中可以扩充的数组是__动态___分配的数组。
这种数组在声明它时需要使用数组指针。
16. 二维数组是一种非线性结构，其中的每一个数组元素最多有__两个__个直接前驱〔或直接后继〕。
17. 假设设一个nn的矩阵A的开始存储地址LOC(0,0) 及元素所占存储单元数d，按行存储时其任意一个矩阵元素a[i][j] 的存储地址为__LOC(0,0)+(i*n+j)*d __。
118.对称矩阵的行数与列数__相等_且以主对角线为对称轴，aij=aji，因此只存储它的上三角局部或下三角局部即可。
将一个n阶对称矩阵的上三角局部或下三角局部压缩存放于一个一维数组中，那么一维数组需要存储__n(n+1)/2_个矩阵元素。
上三角矩阵的奇异值分解-回复上三角矩阵是一个矩阵，其除了主对角线及其上方的元素外，其余元素皆为零。
奇异值分解（Singular Value Decomposition，简称SVD）是一种常见的矩阵分解方法，用于分解任意矩阵为三个矩阵的乘积，其中一个矩阵是正交矩阵，另一个是对角矩阵。
这篇文章将介绍上三角矩阵的奇异值分解，并一步一步解释其原理与过程。
上三角矩阵的奇异值分解可以用于数据降维、矩阵逆、矩阵近似等很多应用中。
在深度学习、图像处理、数据分析等领域中，奇异值分解被广泛应用。
要进行奇异值分解，首先需要明确上三角矩阵的定义。
一个m ×n 的上三角矩阵T可以表示为：T = [ t11 t12 t13 (1)0 t22 t23 (2)0 0 t33 (3)...0 0 0 ... tnn ]其中，tij代表矩阵T第i行第j列的元素。
奇异值分解的目标是将矩阵T分解为以下三个矩阵的乘积：T = UΣV^T其中，U是一个m×m的正交矩阵，Σ是一个m×n的对角矩阵，V^T 是V的转置，是一个n×n的正交矩阵。
正交矩阵满足U^TU=I、VV^T=I，对角矩阵Σ的非零元素称为奇异值，通常按降序排列。
接下来，我们将一步一步解释上三角矩阵的奇异值分解过程。
首先，我们计算矩阵T的转置T^T乘以矩阵T的乘积，记作M = T^TT，得到一个对称矩阵：M = [ m11 m12 m13 (1)m12 m22 m23 (2)m13 m23 m33 (3)...mn1 mn2 mn3 .. mnn ]在对称矩阵M上，我们求解其特征值和特征向量，并按特征值的降序排列。
特征向量对应的特征值构成一个对角矩阵Λ。
接下来，我们将矩阵T乘以特征向量矩阵V，记作T' = TV。
T'是一个正交矩阵，满足T'^TT'^T=I。
然后，我们求解矩阵T'的转置乘以T'的乘积Z = T'^TT'，得到一个对角矩阵。
对称矩阵对称矩阵元素以对角线为对称轴对应相等的矩阵。
1855年，埃米特(C.Hermite,1822-1901年)证明了别的数学家发现的一些矩阵类的特征根的特殊性质，如现在称为埃米特矩阵的特征根性质等。
后来，克莱伯施(A.Clebsch,1831-1872年)、布克海姆(A.Buchheim)等证明了对称矩阵的特征根性质。
泰伯(H.Taber)引入矩阵的迹的概念并给出了一些有关的结论。
目录特性矩阵的转置和对称矩阵数据结构中的对称矩阵编辑本段特性C++数组应用之特殊矩阵的压缩存储[1]1.对于任何方形矩阵X，X+XT是对称矩阵。
2.A为方形矩阵是A为对称矩阵的必要条件。
3.对角矩阵都是对称矩阵。
两个对称矩阵的积是对称矩阵，当且仅当两者的乘法可交换。
两个实对称矩阵乘法可交换当且仅当两者的特征空间相同。
用<,>表示Rn上的内积。
的实矩阵A是对称的，当且仅当对于所有，。
任何方形矩阵X，如果它的元素属于一个特征值不为2的域（例如实数），可以用刚好一种方法写成一个对称矩阵和一个斜对称矩阵之和：X=1/2(X+XT)+1/2(X-XT) 每个实方形矩阵都可写作两个实对称矩阵的积，每个复方形矩阵都可写作两个复对称矩阵的积。
若对称矩阵A的每个元素均为实数，A是Hermite矩阵。
一个矩阵同时为对称矩阵及斜对称矩阵当且仅当所有元素都是零。
如果X是对称矩阵,那么AXA T也是对称矩阵.n阶实对称矩阵，是n维欧式空间V（R）的对称变换在单位正交基下所对应的矩阵。
所谓对称变换，即对任意α、β∈V，都有（σ（α），β）=（α，σ（β））。
投影变换和镜像变换都是对称变换。
编辑本段矩阵的转置和对称矩阵把一个m×n矩阵的行,列互换得到的n×m矩阵,称为A的转置矩阵,记为A'或AT。
(其中T为上标)【矩阵转置的运算律】(即性质):1.(A')'=A2.(A+B)'=A'+B'3.(kA)'=kA'(k为实数)4.(AB)'=B'A'若矩阵A满足条件A=A',则称A为对称矩阵，由定义知对称矩阵一定是方阵,而且位于主对角线对称位置上的元素必对应相等.即aij=aji,对任意i,j都成立。
§4矩阵的三角分解矩阵的三角分解定理：设n nA R ×∈,如果A 的前n-1个顺序主子式det()0,1,2,,1i A i n ≠=− ，则A 可分解为一个单位下三角矩阵L 与一个上三角矩阵U 的乘积，且这种分解是唯一的。
证明：1.存在性：利用高斯消去法来构L 和U(1)(2)()1122det()0,1,2,,1i i ii A a a a i n =≠=−1L A U −=，A LU=2112100101n n m L m m ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦ ，(1)(1)(1)11121(2)(1)222()0nn n nn a a a a a U a ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦2．唯一性：分A 非奇异和奇异两种情况来证 （1）A 非奇异考虑到A 的前n-1个顺序主子式非零，得 det()0,1,2,,i A i n ≠=设1122A LUL U ==，12,L L 为单位下三角矩阵，12,U U 为上三角矩阵。
因A 非奇异，所以1U 可逆，从而112121L L U U −−=112121112121(,)L L E U U L L U U −−−−⇒==因为单位下三角阵为上三角阵2121,L L U U ⇒==（2）A 奇异因det()0,1,2,,1i A i n ≠=− ，det()0n A =()0,1,2,,1i ii a i n ⇒≠=− ，()0n nn a = 设1122A LUL U ==，12,L L 为单位下三角矩阵，12,U U 为上三角矩阵。
对它们进行矩阵分块，得(1)(1)(1)(1)(1)(1)111222(1)(1)1122001010n n n n n n n n L U a L U a m a m a −−−−−−−−⎛⎞⎛⎞⎛⎞⎛⎞=⎜⎟⎜⎟⎜⎟⎜⎟⎝⎠⎝⎠⎝⎠⎝⎠其中(1)(1)12,n n L L −−为n-1阶单位下三角矩阵，(1)(1)12,n n U U −−为可逆的n-1阶上三角矩阵(1)(1)(1)(1)(1)(1)(1)(1)11112222(1)(1)(1)(1)(1)(1)(1)(1)1111122222n n n n n n n n n n n n n n n n L U L a L U L a m U m a a m U m a a −−−−−−−−−−−−−−−−⎛⎞⎛⎞⇒=⎜⎟⎜⎟++⎝⎠⎝⎠由(1)(1)(1)(1)1122n n n n L U L U −−−−=(1)(1)(1)(1)2121,n n n n L L U U −−−−⇒==由(1)(1)(1)(1)1122n n n n L a L a −−−−=(1)(1)21n n a a −−⇒= 由(1)(1)(1)(1)1122n n n n m U m U −−−−=(1)(1)21n n m m −−⇒=由(1)(1)(1)(1)222111n n n n m a a m a a −−−−+=+21a a ⇒= 故2121,L L U U == 证毕。
计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编3(总分66, 做题时间90分钟)6. 综合题1.数组A[1．．8，一2．．6，0．．6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A[4，2，3]的存储首地址。
【厦门大学1998五、1(5分)】SSS_TEXT_QUSTI2.数组A中，每个元素A[i，f]的长度均为32个二进位，行下标从一1到9，列下标从1到11，从首地址S开始连续存放在主存储器中，主存储器字长为16位。
求：(1)存放该数组所需多少单元?(2)存放数组第4列所有元素至少需多少单元?(3)数组按行存放时，元素A[7，4]的起始地址是多少?(4)数组按列存放时，元素A[4，7]的起始地址是多少?【大连海事大学1996四、1(6分)】SSS_TEXT_QUSTI3.假设按低下标优先存储整型数组A(一3：8，3：5，一4：0，0：7)时，第一个元素的字节存储地址是100，每个整数占4字节，问A(0，4，一2，5)的存储地址是什么? 【清华大学1996三】SSS_TEXT_QUSTI4.设有五对角矩阵A=(aij )20*20，按特殊矩阵压缩存储的方式将其五条对角线上的元素存于数组A[-10：m]中，计算元素A[15，16]的存储位置。
【东北大学1999一、2(4分)】SSS_TEXT_QUSTI5.数组A[0．8，1．．10】的元素是6个字符组成的串，则存放A至少需要多少字节?A的第8列和第5行共占多少字节?若A按行优先方式存储，元素A[8，5]的起始地址与当A按列优先方式存储时的哪个元素的起始地址一致?【厦门大学2000五、3(14％／3分)】SSS_TEXT_QUSTI6.设m×n阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA[t+1)，1．．3]，试问：非零元素的个数t达到什么程度时用LTMA表示A才有意义?【北京航空航天大学1998一、5(4分)】SSS_TEXT_QUSTI设有三对角矩阵(aij )n×n将其三条对角线上的元素逐行地存于数组B(1：3n一2)中，使得s[k]=ai，j，求：SSS_TEXT_QUSTI7.用i，j表示k的下标变换公式；SSS_TEXT_QUSTI8.若n=10 3，每个元素占用L个单元，则用B[K]方式比常规存储节省多少单元?【西安电子科技大学1996二、4(5分)】9.已知A为稀疏矩阵，试从空间和时间角度，比较采用两种不同的存储结构(二维数组和三元组表)完成求运算的优缺点。
对称矩阵上三角存储公式
对称矩阵上三角存储方式是指只存储矩阵的上三角部分，由于矩阵是对称的，因此下三角部分可以通过对称性质推导得到。
对称矩阵上三角存储方式的公式如下：
设对称矩阵 A\in R^{n\times n}，则有
A=\begin{bmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{12} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{1n} & a_{2n} & \cdots & a_{nn} \\
\end{bmatrix}
对称矩阵上三角存储方式将 A 存储为一个一维数组 a，其中 a 的前n 个元素为矩阵的第一行，接下来 n-1 个元素为矩阵的第二行的除了第一个元素以外的剩余元素，以此类推，最后一个元素为矩阵最后一行的最后一个元素。
即
a=[a_{11},a_{12},\cdots,a_{1n},a_{22},\cdots,a_{2n},\cdots,a_ {(n-1)(n-1)+1},\cdots,a_{(n-1)n},a_{nn}]
对于对称矩阵 A 的第 i 行，第 j 列 (i\le j) 的元素可以通过上三角存储数组 a 中的下标 k 算出，即
k=\frac{(i-1)n-i(i-1)/2+j}
这里 (i-1)n-i(i-1)/2 表示前 i-1 行元素个数之和，加上 j 就是当
前元素所在的位置，且因为是上三角存储，因此要去掉下三角部分。
对称矩阵 A 的第 i 行，第 j 列 (i\ge j) 的元素可以通过对称性质得到，即 a_{ij}=a_{ji}。
