数据结构 第五章数组和广义表

-第五章数组和广义表：习题习 题一、选择题1假设以行序为主序存储二维数组A1100,1100，设每个数据元素占两个存储单元，基地址为10，则LOC(A5，5)=( )。 A. 808 B. 818 C. 1010 D. 10202同一数组中的元素( )。 A. 长度可以不同 B不限 C类型相同 D. 长度不限3二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。 (1)存放A至少需要( )个字节。 (2)A的第8列和第5行共占( )个字节。 (3)若A按行存放，元素A8【5的起始地址与A按列存放时的元素( )的起始地址一致。 供选择的答案： (1)A. 90 B. 180 C. 240 D. 270 E.540 (2) A. 108 B. 114 C. 54 D. 60 E.150 (3)A.A85 B. A310 c.A58 D.AO94.数组与一般线性表的区别主要是( )。 A.存储方面 B.元素类型方面 C.逻辑结构方面 D.不能进行插入和删除运算5设二维数组A1m，1n按行存储在数组B1mn中，则二维数组元素Ai，j在一维数组B中的下标为( )。 A. (i-l)n+j B. (i-l)n+j-l Ci(j-l) D. jm+i-l6所谓稀疏矩阵指的是( )。A.零元素个数较多的矩阵B.零元素个数占矩阵元素中总个数一半的矩阵C.零元素个数远远多于非零元素个数且分布没有规律的矩阵D.包含有零元素的矩阵7对稀疏矩阵进行压缩存储的目的是( )。A.便于进行矩阵运算 B.便于输入和输出C.节省存储空间 D. 降低运算的时间复杂度8稀疏矩阵一般的压缩存储方法有两种，即( )。A.二维数组和三维数组 B.三元组和散列C.三元组和十字链表 D.散列和十字链表9有一个10090的稀疏矩阵，非0元素有10个，设每个整型数占两字节，则用三元组表示该矩阵时，所需的字节数是( )。A. 60 B. 66 C18000 D3310. AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组TN(N+I)/2中，则对任一上三角元素aij对应Tk的下标k是( )。A. i(i-l)/2+j B. j(j-l)/2+iC. i(j-i)/2+1 D. j(i-l)/2+111已知广义表L=(x，y,z)，a，(u，t，w)，从L表中取出原子项t的运算是( )A. head(tail(tail(L) B. tail(head(head(taiI(L)C. head(tail(head(taiI(L) D. head(tail(head(tail(tail(L)12.广义表A=(a，b，(c，d)，(e，(f,g)，则下面式子的值为( )。Head(TaiI(Head(TaiI(Tail(A)A(g) B(d)C.c D.d13广义表(a，b，c，d)的表头是( )，表尾是( )。A.a B.( ) C.(a,b,c,d) D.(b,c,d)14设广义表L=(a，b，c)，则L的长度和深度分别为( )。A.1和1 B.1和3 C.1和2 D.2和315.下面说法不正确的是( )。A. 广义表的表头总是一个广义表 B.广义表的表尾总是一个广义表C.广义表难以用顺序存储结构 D.广义表可以是一个多层次的结构二、填空题1.数组的存储结构采用_存储方式。 2.二维数组A1020每个元素占一个存储单元，并且A0O的存储地址是200，若采用行序为主方式存储，则A612的地址是_ ，若采用列序为主方式存储，则A612的地址是_。3.三维数组a456（下标从0开始计，a有456个元素），每个元素的长度是2，则a234的地址是_。（设a000的地址是1000，数据以行为主方式存储）4. n阶对称矩阵a满足aij=aji，i,j=1n，用一维数组t存储时，t的长度为_， glist p； glist q，h，t，s； if (p=NULL) q=NULL; else if_q= (glist)malloc( sizeof (gnode);q-tag=0; q-val.data=p-val.data; elsef _； if_ t=reverse (p-val. ptr. tp); s=t; while( s-val. ptr.tp! =NULL) s=s-val .ptr.tp; s-val .ptr. tp=( glist) malloc( sizeof (gnode); s=s-val .ptr.tp; s-tag=l; s-valptr.tp=NULL; s-val.ptr.hp=h;_; else q=( glist) malloc( sizeof( gnode);q-tag=l; q-val.ptr.tp=NULL;_; return (q)； 三、判断题 1.数组不适合作为任何二叉树的存储结构。( ) 2.稀疏矩阵压缩存储后，必会失去随机存取功能。( ) 3.数组是同类型值的集合。( ) 4.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。( ) 5.一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。( ) 6.广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。( ) 7.若一个广义表的表头为空表，则此广义表亦为空表。( ) 8.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。( ) 9.所谓取广义表的表尾就是返回广义表中最后一个元素。( ) 10.广义表的同级元素（直属于同一个表中的各元素）具有线性关系。( ) 11. 一个广义表可以为其他广义表所共享。( ) 四、简答题 1.在以行序为主序的存储结构中，给出三维数组A2*3*4的地址计算公式（下标从0开始计数）。 2.数组A中，每个元素A嘶的长度均为32个二进位，行下标从-1到9，列下标从1到11，从首地址s开始连续存放主存储器中，主存储器字长为16位。 求： (1)存放该数组所需多少单元？ (2)存放数组第4列所有元素至少需多少单元？ (3)数组按行存放时，元素A7，4的起始地址是多少？ (4)数组按列存放时，元素A4，7的起始地址是多少？3将数列1，2，3，n*n，依次按下列方式存放在二维数组A1n，1一n中。例如：n=5时，二维数组为 4画出下列广义表的链接存储结构，并求其深度。 (),a,(b,c),(),d),(e)5已知题图5-1为广义表的链接存储结构，写出该图表示的广义表。 题图5-16设有广义表K1(K2(K5(a，K3(c，d，e)，K6(b，k)，K3，K4(K3，f)，要求： (1)指出K1的各个元素及元素的构成。 (2)计算表K1，K2，K3，K4，Ks，K6的长度和深度。 (3)画出K1的链表存储结构。五、算法设计题 1对于二维整型数组Am,n，分别编写相应函数实现如下功能： (1)求数组A4边元素之和。 (2)当m=n时分别求两条对角线上的元素之和，否则显示mn的信息。 2编写子程序，将一维数组An*n(ntag=0, h=p-val.ptr.hp, p-next!=NULL, q=t, reverse(h)。 三、判断题 1 2 3 4 5 6 7 8 9 10. 11. 四、简答题1. LOC(Aijk=LOC(A000+i*12+j*4+k. 2 (1) 12l*32/16=242。 (2) 11*32/16=22 (3) LOC(A00)+(8*11+3)*32/16=LOC(A00)+182. (4) LOC(A00)+182。 3程序如下所示： #define NMAX 10 #include main() int i,j，n，k，m; int a NMAX NMAX; scanf( %d, &n); m=l; for (i=O; in; i+) for (j=i*n,k=O; j(i+1)*n; j+,k+) aik=m+; for(i=O; in; i+) for(j=O;jn;j+) printf (%4d,a ij); printf(n); 4深度为4广义表的链接存储结构为： 5.(x,(y),(),(),(z) 6ki由k2, k3, k4构成 k1 k2 k3 k4 k5 k6 长度： 3 2 3 2 2 2 深度： 4 3 1 2 2 l 五、算法设计题 1 (1) #define M 5 #define N 7 long sum side (int aM N) /计算四边元素之和，注意不要重复 long sum=0; int i; for(i=0; iM; i+) sum+=ai0; for(i=1; iN; i+) sum+=aOi; for (i=1; iM; i+) sum+=ai N-1; for (i=l; iN-1; i+) sum+=aM-1 i; return sum; (2) long sum tilt (int aMN) /计算两条对角线元素之和 long sum=0; int i，j ;if (M!=N) printf (nM不等于Nn”); return O;for (i=O; i=0; i-) sum+=aiM-i-l;if (M%2!=0) sum-= aM/2 M/2;/M为奇数时中间元素加了两遍 return (sum);2#define NMAX 20 /最大N值int aNMAX*NMAX，bNMAX NMAX，cnt; /定义全局变量利于通信void MakeLine (int RowStart, int ColStart, int RowEnd) /*功能：用数组A中的元素去填充数组B的一个对角线 参数含义：RowStart-斜线起始行号 ColStart-斜线起始列号 RowEnd-斜线结束行号*/ int i，j，step; if (RowStart=0 ;i+-.s tep,j -=step) bij=acnt+; /斜线赋值，cnt用于赋值计数，初值为O void MakeArray (int n) /给数组B的所有斜线赋值，n为数组大小 int d： for (d=O;d2*n; d+) if(dn) /上三角赋值 if (d%2=0) MakeLine(d，O，O); else MakeLine(O，d，d); else /下三角赋值 if ( d%2=0) Makeline (n-l, d-n+l, d-n+l); else MakeLine (d-n+l, n-l, n-l); main() int i,j,n; printf (nPlease input n: ); scanf(%d，&n); for (i=O ;in*n; i+) ai=i+1; cnt=0; /赋值计数 MakeArray (n); for(i=O;in;i+) /输出结果 printf(n”); for (j=0; jval. sublist; while(p!=NULL) /循环将hb中的各个元素合并至ha中 q=ha-valsublist; while (q! =NULL) if (equal (p,q) /相等元素不合并 break; q=q-link; if (q= =NULL) r=p-link; GListInsertTail (ha,p); /若ha中无相同元素，则插入到末尾 p=r; else p=p-link; /请读者在此处添加释放hb结点的代码 return ha; int equal (GListNode *ha, GlistNode *hb) /判别由ha和hb指向的广义表元素是否相等，相等返回l，否则返回0 GListNode *p，*q ; if (ha= =NULL) /空表情况判断 if (hb= =NULL) return 1; else return O; if (ha-tag! =hb-tag) /子表元素与单元素必不等 return O; if (ha-tag= -0) /单元素相等判定 if (ha-val. data= =hb-val. data) return l; else return O;else /子表相等判定 p=ha-val. sublist; q=hb-valsublist; /通过循环依次比较两表中的元素是否相等 while(p!