数据结构第五章习题课

1、1、 特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么?答：后者在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号作为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。2、二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M35的起始地址与M按列存储时元素（ ）的起始地址相同。 A、M24B、M34C、M35D、M443、设有一个10阶的对称矩阵A，采用压

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

3、jn，且ij)在B中的位置为( )。A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-16、设二维数组A1. m，1. n（即m行n列）按行存储在数组B1. m*n中，则二维数组元素Ai，j在一维数组B中的下标为( )。A.（i-1）*n+j B.（i-1）*n+j-1 C. i*（j-1） D. j*m+i-17、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。A. 60 B. 66 C. 18000 D. 33 8、已知广义表L=（x,y,z），a，（u，t

4、，w），从L表中取出原子项t的运算是（ ）。A.head（tail（tail（L） B.tail（head（head（tail（L） C.head（tail（head（tail（L） D.head（tail(head（tail（tail（L）)）9、下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构10、若采用按行优先顺序存储，试写出三维数组A323所有元素在内存中的存储次序。答：A000，A001，A002，A010，A011，A012，A100，A101，A102，A110，A11

5、1，A112，A200，A201，A202，A210，A211，A212 11、二维数组Amn采用按行存储，每个元素占k个存储单元，第一个元素的存储地址是LOC（A00），则Aij的存储地址是 。答：LOC（A00）+（n*i+j）*k12、三维数组a456（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a234的地址是_。(设a000的地址是1000,数据以行为主方式存储) 答：1164 公式：LOC(aijk)=LOC(a000)+v2*v3*(i-c1)+v3*(j-c2)+(k-c3)*l (l为每个元素所占单元数)13、假设一个15阶的上三角矩阵A按行优先顺序压缩存储

6、在一维数组B中，则非零元素A9,9在B中的存储位置k=_。 （ 注：矩阵元素下标从1开始 ）答：9314、设广义表L=(),(), 则head(L)是(1)_；tail(L)是(2)_；L的长度是(3)_；深度是 (4)_。答：（1）（） （2）（） （3）2 （4）215、广义表A=（a，b），（c，d，e），取出A中的原子e的操作是: _。答：head(tail(tail(head(tail(head(A)16、设对称矩阵A=（1）若将A中包括主对角线的下三角元素按列的顺序压缩到数组S中, 即S:1002300050下标： 1 2 3 4 5 6 7 8 9 10试求出A中任一元素的行列下

7、标i,j(1<=i,j<=4)与S中元素的下标K之间的关系.（2）若将A视为稀疏矩阵时,画出其三元组表形式压缩存储表。答：（1）k=(2n-j+2)(j-1)/2+i-j+1 （当ij时，本题n=4）k=(2n-i+2)(i-1)/2+j-i+1 （当i<j时，本题n=4） （2）稀疏矩阵的三元组表为：s=(4,4,6),(1,1,1),(1,4,2),(2,2,3),(3,4,5),(4,1,2),(4,3,5)。其中第一个三元组是稀疏矩阵行数、列数和非零元素个数。其它三元组均为非零元素行值、列值和元素值。17、设任意n个整数存放于数组A(1:n)中，试编写程序，将所有正数

8、排在所有负数前面（要求算法复杂性为0( n)）。 类似本题的另外叙述有：（1）已知数组A1.n的元素类型为整型，设计算法调整A，使其左边的所有元素小于零，右边的所有元素大于等于零。（要求算法的时间复杂度和空间复杂度均为0（n）（2）设计一个算法，把整数数组中所有的偶数放到所有的奇数之前。要求时间、空间效率尽可能高。（3）设一系列正整数存放在一个数组中，试设计算法，将所有奇数存放在数组的前半部分，将所有的偶数存放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。请试着分析你实现的算法的时间复杂度和空间复杂度。（4）设计算法将数组A1.n调整为左右两部分，使的左边所有的元素小于右边的所有元

9、素，并给出这一划分的分界位置。要求算法的时间复度为O(n)。 答：题目分析本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i和j，i自小至大搜索到负数停止，j自大至小搜索到正数停止。然后i和j所指数据交换，继续以上过程，直到 i=j为止。void Arrange(int A,int n) /n个整数存于数组A中，本算法将数组中所有正数排在所有负数的前面 int i=0,j=n-1,x; /用类C编写，数组下标从0开始 while(i<j)while(i<j && Ai>0) i+;while(i<j && Aj<0

10、) j-; if(i<j) x=Ai; Ai+=Aj; Aj-=x; /交换Ai 与Aj /算法Arrange结束.算法讨论对数组中元素各比较一次，比较次数为n。最佳情况(已排好,正数在前,负数在后)不发生交换，最差情况(负数均在正数前面)发生n/2次交换。用类c编写，数组界偶是0.n-1。空间复杂度为O(1).类似本题的其它题的解答:：（1）与上题同，因要求空间复杂度也是O(n)，可另设一数组C，对A数组从左到右扫描，小于零的数在C中从左（低下标）到右（高下标）存，大于等于零的数在C中从右到左存。（2）将19题中判定正数(Ai>0)改为判偶数(Ai%2=0)，将判负数(Aj<

11、;0)改为(Aj%2!=0)。（3）同（2），只是要求奇数排在偶数之前。（4）利用快速排序思想，进行一趟划分。int Partition(int A,int n) /将n个元素的数组A调整为左右两部分，且左边所有元素小于右边所有元素，返回分界位置。int i=0,j=n-1,rp=A0; /设数组元素为整型 while(i<j) while(i<j &&Aj>=rp) j-; while(i<j &&Ai<=rp) i+; if(i<j) x=Ai;Ai=Aj; Aj=x; Ai=rp; return(i); /分界元素/ P

12、artition18、在数组 A1.n中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个。答：题目分析本题要求建立有序的循环链表。从头到尾扫描数组A，取出Ai（0<=i<n）,然后到链表中去查找值为Ai的结点，若查找失败，则插入。LinkedList creat(ElemType A,int n)/由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点 LinkedList h;h=(LinkedList) malloc(sizeof(LNode);/申请结点h->next=h; /形成空循环链表for(i=

13、0;i<n;i+) pre=h;p=h->next; while(p!=h && p->data<Ai) pre=p; p=p->next; /查找Ai的插入位置 if(p=h | p->data!=Ai) /重复数据不再输入 s=(LinkedList) malloc(sizeof(LNode); s->data=Ai; pre->next=s; s->next=p;/将结点s链入链表中/for return(h);/ creat19、编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为

14、A-Z这26个字母和0-9这10个数字）。问题分析由于字母共26个，加上数字符号10个共36个，所以设一长36的整型数组，前10个分量存放数字字符出现的次数，余下存放字母出现的次数。从字符串中读出数字字符时，字符的ASCII代码值减去数字字符0的ASCII代码值，得出其数值(0.9)，字母的ASCII代码值减去字符A的ASCII代码值加上10，存入其数组的对应下标分量中。遇其它符号不作处理，直至输入字符串结束。void Count（）/统计输入字符串中数字字符和字母字符的个数int i，num36；char ch；for（i0；i<36；i+）numi0；/ 初始化while（chget

15、char（）!=#） /#表示输入字符串结束if（0<=ch<=9）i=ch48;numi+； / 数字字符 elseif（A<=ch<=Z）i=ch-65+10;numi+；/ 字母字符for（i=0；i<10；i+） / 输出数字字符的个数printf（“数字d的个数dn”，i，numi）；for（i10；i<36；i+）/ 求出字母字符的个数printf（“字母字符c的个数dn”，i55，numi）；/算法结束7. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积

16、（存储量）为 288 B ；末尾元素A57的第一个字节地址为 1282 ；若按行存储时，元素A14的第一个字节地址为 (8+4)×6+1000=1192 ；若按列存储时，元素A47的第一个字节地址为 (6×74)×61000）1276 。9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。10.求下列广义表操作的结果：（1） GetHead【(a,b),(c,d)】= (a, b) ; /头元素不必加括号（2） GetHead【GetTail【(a,b),(c,d)】= (c,d) ;（

17、3） GetHead【GetTail【GetHead【(a,b),(c,d)】= b ;（4） GetTail【GetHead【GetTail【(a,b),(c,d)】= （d） ;（A）4.01年计算机系考研题假设有60行70列的二维数组a160, 170以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a32,58的存储地址为 。（无第0行第0列元素）16902 16904 14454 答案A, B, C均不对答：（57列×60行31行）×2字节10000=16902(B)5.设矩阵A是一个对称矩阵，为了节省存储，将其下三角部

18、分（如下图所示）按行序存放在一维数组B 1, n(n-1)/2 中，对下三角部分中任一元素ai,j(ij), 在一维数组B中下标k的值是：i(i-1)/2+j-1 i(i-1)/2+j i(i+1)/2+j-1 i(i+1)/2+j解：注意B的下标要求从1开始。先用第一个元素去套用，可能有B和C；再用第二个元素去套用B和C，B=2而C3（不符）；所以选B6.【91初程P78】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。有一个二维数组A，行下标的范围是0到8，列下标的范围是1到5，每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素

19、A0,1的第一个字节的地址是0。存储数组A的最后一个元素的第一个字节的地址是 A 。若按行存储，则A3,5和A5,3的第一个字节的地址分别是 B 和 C 。若按列存储，则A7,1和A2,4的第一个字节的地址分别是 D 和 E 。供选择的答案AE：28 44 76 92 108 116 132 176 184 188答案：ABCDE=8, 3, 5, 1, 67.【94程P12】 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组

20、的体积是 A 个字节。假设存储数组元素A1,0的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是 B 。若按行存储，则A2,4的第一个字节的地址是 C 。若按列存储，则A5,7的第一个字节的地址是 D 。供选择的答案AD：12 66 72 96 114 120 156 234 276 282 （11）283 （12）288答案：ABCD=12, 10, 3, 92.已知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢？解：公式教材已给出，此处虽是方阵，但行列

21、公式仍不相同；按行存储的元素地址公式是： Loc(aij)= Loc(a11) + (i-1)*m+(j-1) * K按列存储的元素地址公式是： Loc(aij)= Loc(a11) + (j-1)*m+(i-1) * K3.【全国专升本资格考试】递归算法比非递归算法花费更多的时间，对吗？为什么？答：不一定。时间复杂度与样本个数n有关，是指最深层的执行语句耗费时间，而递归算法与非递归算法在最深层的语句执行上是没有区别的，循环的次数也没有太大差异。仅仅是确定循环是否继续的方式不同，递归用栈隐含循环次数，非递归用循环变量来显示循环次数而已。4.用三元组表表示下列稀疏矩阵： 解：三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。所以（1）可列表为： （2）可列表为：8866416-225943565353233685467858125.下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。 解：（1）为6×4矩阵，非零元素有6个，但其中一数下标有误？（2）为4×5矩阵，非零元素有5个1