《数据结构》-第五章

习题51选择题1、一维数组和线性表的区别是（A）。A、前者长度固定，后者长度可变B、后者长度固定，前者长度可变C、两者长度均固定D、两者长度均可变2、设W为一个二维数组，其每个数据元素WIJ占用6个字节，行下标I从0到8，列下标J从2到5，则二维数组W的数据元素共占用（C）个字节。A、480、192、216、1443、在稀疏矩阵的行逻辑链式存储中，每个行单链表中的结点都具有相同的（A）。A、行号B、列号、元素值D、地址4、二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标I的范围从0到4，列下标J的范围从0到5，M按行序存储时元素M35的起始地址与M按列序存储时的元素（）的起始地址相同。A、M24B、M34C、M35D、M445、稀疏矩阵一般的压缩存储方法有两种，即（C）。A、二维数组和三维数组B、三元组和散列C、三元组和十字链表D、散列和十字链表52填空题1、一维数组的逻辑结构是（线性表），存储结构是（顺序存储）；对于二维或多维数组，分为按（行序）和（列序）两种不同的方式存储。2、对于一个二维数组AMN，若按行序为主序存储，则任一元素AIJ相对于A00的地址为（AIMJ每个元素所占字节数）。3、已知广义表AA,B,C,D,E,F，则运算HEADTAILTAILA（E）。4、三维数组RC1D1,C2D2,C3D3共含有（D1C11）D2C21D3C31）个元素。（C1D1,C2D2,C3D3）5、二维数组A1020510以行序为主序存储，每个元素占4个存储单元，且A105的存储地址是1000，则A189的地址是（1368）。53应用题1、按行优先存储方式，写出三维数组A324在内存中的排列顺序及地址计算公式（假设每个数组元素占用L个字节的内存单元，A000的内存地址为LOCA000）。答内存中的排列顺序为A000,A001,A002,A003,A010,A011,A012,A013,A100,A101,A102,A103,A110,A111,A112,A113,A200,A201,A202,A203,A210,A211,A212,A213地址计算公式为LOCAIJKLOCA000（I24J4K）L2、给定矩阵A如下，写出它的三元组表示、行逻辑链式存储和十字链表存储。答三元组表示法M5,N5,T6,DATA数组为行列值下标123456MAXTERMS行逻辑链式存储方式11123224332435555612345十字链表存储方式11112345111111111111111123453、求下列广义表的运算的结果111232243324355556（1）HEADP,H,W结果为P,H,W（2）TAILB,K,P,H结果为（3）HEADA,B,C,D结果为A,B,C,D（4）TAILB,C,D结果为（5）HEADTAILHEADA,D,C,D结果为C（6）TAILHEADTAILA,B,C,D结果为4、求出下列广义表的长度和深度。（1）A（）结果为12（2）B（A，（B，（C）结果为23（3）C（A，（B，（C，D），（E）结果为33（4）F（A，（B，（），C），（D）,E）结果为335、画出下列广义表的图形表示（1）AB,A,A,CA,CA（2）DA,BE,CA,LB,C,D答ACBADBCEAABDCL126、画出第5题的广义表的单链表表示。答0B1110A111A（1）1110E0A10B0DD0C（2）54算法题1、试写一个算法，查找十字链表中某一非零元素X。INCLUDEINCLUDETYPEDEFINTELEMTYPEDEFINEMAXROWS10DEFINEMAXCOLUMNS10STRUCTCROSSNODEINTROW,COLELEMTYPEVALCROSSNODEDOWN,RIGHTSTRUCTCLMATRIXINTM,N,TCROSSNODERHEADMAXROWS1CROSSNODECHEADMAXCOLUMNS1VOIDCREATECLMATRIXPRINTF“请输入稀疏矩阵的行数和列数中间以逗号隔开N“SCANF“D,D“,FORINTJ1JROW,SRIGHTCLRHEADSROWCLRHEADSROWSSDOWNCLCHEADSCOLCLCHEADSCOLSVOIDPRINT1CROSSNODELCROSSNODEPPLWHILEPRIGHTPRINTF“D,D,DN“,PROW,PCOL,PVALPPRIGHTPRINTF“D,D,DN“,PROW,PCOL,PVALVOIDPRINT2CROSSNODELCROSSNODEPPLWHILEPDOWNPRINTF“D,D,DN“,PROW,PCOL,PVALPPDOWNPRINTF“D,D,DN“,PROW,PCOL,PVALVOIDPRINTCLCLMATRIXCLINTNPRINTF“请按提示输入N“PRINTF“按行序输出，请输入1N“PRINTF“按列序输出，请输入2N“SCANF“D“,IFN1FORINTI1IVALELEM/顺序查找符合条件的结点PPRIGHTIFPRETURNP/查找成功，返回结点的序号ELSERETURNNULL/查找不成功，返回0值VOIDLOCATELCCLMATRIXCL,ELEMTYPEXCROSSNODEPFORINTI1IROW,PCOL,PVALVOIDMAINCLMATRIXCLELEMTYPEXCREATECLPRINTF“输出创建的按十字链表存储的稀疏矩阵N“PRINTCLCLPRINTF“请输入要查找的非零元素的值“SCANF“D“,LOCATELCCL,X2、试编写一个以三元组形式输出，用十字链表表示的稀疏矩阵中非零元素及其下标的算法。INCLUDEINCLUDETYPEDEFINTELEMTYPEDEFINEMAXROWS10DEFINEMAXCOLUMNS10STRUCTCROSSNODEINTROW,COLELEMTYPEVALCROSSNODEDOWN,RIGHTSTRUCTCLMATRIXINTM,N,TCROSSNODERHEADMAXROWS1CROSSNODECHEADMAXCOLUMNS1INTX0,Y0VOIDCREATECLMATRIXPRINTF“请输入稀疏矩阵的行数和列数中间以逗号隔开N“SCANF“D,D“,FORINTJ1JROW,SRIGHTCLRHEADSROWCLRHEADSROWSSDOWNCLCHEADSCOLCLCHEADSCOLSVOIDPRINT1CROSSNODELCROSSNODEPPLWHILEPRIGHTXPRINTF“第D个非零元素为N“,XPRINTF“D,D,DN“,PROW,PCOL,PVALPPRIGHTXPRINTF“第D个非零元素为N“,XPRINTF“D,D,DN“,PROW,PCOL,PVALVOIDPRINT2CROSSNODELCROSSNODEPPLWHILEPDOWNYPRINTF“第D个非零元素为N“,YPRINTF“D,D,DN“,PROW,PCOL,PVALPPDOWNYPRINTF“第D个非零元素为N“,YPRINTF“D,D,DN“,PROW,PCOL,PVALVOIDPRINTCLCLMATRIXCLINTNPRINTF“请按提示输入N“PRINTF“按行序输出，请输入1N“PRINTF“按列序输出，请输入2N“SCANF“D“,IFN1FORINTI1ICLMIIFCLRHEADINULLPRINT1CLRHEADIELSEFORINTJ1JCLMJIFCLCHEADJNULLPRINT2CLCHEADJVOIDMAINCLMATRIXCLCREATECLPRINTF“按三元组输出创建的稀疏矩阵N“PRINTCLCL3、编写一个算法MAX（GL），求出一个广义表GL中最大的原子。例如，MAX（A，（B），D，C）返