完整第五章-考研真题精选.doc

请实现划红线局部的标题第三局部考研真题精选一、选择题1.设有一个10阶的对称矩阵A，采纳紧缩存储方法，以行序为主存储，a11为第一元素，其存储地点为1，每个元素占一个地点空间，那么a85的地点为。A.13B.33 C.18D.402.有一个二维数组A1:6，0:7每个数组元素用相邻的6个字节存储，存储器按字节编址，那么那个数组的体积是个字节。假定存储数组元素A1，0的第一个字节的地点是0，那么存储数组A的最初一个元素的第一个字节的地点是。假定按行存储，那么A2，4的第一个字节的地点是。假定按列存储，那么A5，7的第一个字节的地点是。就普通状况而言，当时，按行存储的AI，J地点与按列存储的AJ，I地点相称。供选择的谜底：-：A12B.66 C.72D.96E.114 F.120G.156H.234I.276J.282K.283 L.288：A行与列的上界一样B.行与列的下界一样C.行与列的上、下界都一样D.行的元素个数与列的元素个数一样3.设无数组Ai,j，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地点BA开场次序寄存，当用以列为主寄存时，元素A5，8的存储首地点为()。A.BA+141B.BA+180 C.BA+222D.BA+2254.假定以行序为主序存储二维数组A=array1.100，1.100，设每个数据元素占2个存储单位，基地点为10，那么LOC5，5=。A.808B.818 C.1010D.10205.数组A0.5,0.6的每个元素占五个字节，将其按列优先次第存储在肇端地点为1000的内存单位中，那么元素A5，5的地点是()。A.1175B.1180 C.1205D.12106.有一个二维数组A0:8,1:5,每个数组元素用相邻的4个字节存储，存储器按字节编址，假定存储数组元素A0,1的第一个字节的地点是0，存储数组A的最初一个元素的第一个字节的地点是。假定按行存储，那么A3,5跟A5,3的第一个字节的地点是跟。假定按列存储，那么A7,1跟A2,4的第一个字节的地点是跟。-:A.28B.44 C.76D.92E.108 F.116 G.132H.176I.184J.1887.将一个A1.100，1.100的三对角矩阵，按行优先存入一维数组B1298中，A中元素A6665即该元素下标i=66，j=65，在B数组中的地位K为。供选择的谜底：A.198B.195 C.1978.二维数组A的元素基本上6个字符构成的串，行下标i的范畴从0到8，列下标j的范圈从1到10。从供选择的谜底当选出应填入以下对于数组存储表白中内的准确谜底。1寄存A至多需求个字节；2A的第8列跟第5行共占个字节；3假定A按行寄存，元素A8，5的肇端地点与A按列寄存时的元素的肇端地点分歧。供选择的谜底：1A.90B.180 C.240D.270E.5402A.108B.114 C.54D.60E.1503A.A8,5B.A3,10C.A5,8D.A0,99.二维数组A的每个元素是由6个字符构成的串，其行下标i=0,1,8,列下标j=1,2,10。假定A按行先存储，元素A8,5的肇端地点与当A按列先存储时的元素的肇端地点一样。设每个字符占一个字节。A.A8,5B.A3,10C.A5,8D.A0,910.假定对n阶对称矩阵A以行序为主序方法将其下三角形的元素(包含主对角线上一切元素)顺次寄存于一维数组B1.(n(n+1)/2中，那么在B中断定aiji<j的地位k的关联为()。A.i*(i-1)/2+jB.j*(j-1)/2+iC.i*(i+1)/2+jD.j*(j+1)/2+i11.设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次第寄存在一维数组B1.n(n+1)/2中，对上述任一元素aij(1i，jn，且ij)在B中的地位为()。A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-112.AN，N是对称矩阵，将上面三角包含对角线以行序存储到一维数组TNN+1/2中，那么对任一上三角元素aij对应Tk的下标k是。A.ii-1/2+jB.jj-1/2+iC.ij-i/2+1D.ji-1/2+113.设二维数组A1.m，1.n即m行n列按行存储在数组B1.m*n中，那么二维数组元素Ai，j在一维数组B中的下标为()。A.i-1*n+jB.i-1*n+j-1 C.i*j-1D.j*m+i-114.有一个100*90的稀少矩阵，非0元素有10个，设每个整型数占2字节，那么用三元组表现该矩阵时，所需的字节数是。A.60B.66 C.18000D.3315.数组A0.4,-1.-3,5.7中含有元素的个数。A.55B.45 C.36D.1616.用数组r存储静态链表，结点的next域指向后继，任务指针j指向链中结点，使j沿链挪动的操纵为()。A.j=rj.nextB.j=j+1 C.j=j->nextD.j=rj->next17.对稀少矩阵进展紧缩存储目标是。A便于进展矩阵运算B便于输入跟输入C节约存储空间D落低运算的时刻庞杂度18.曾经明白狭义表L=x,y,z，a，u，t，w，从L表中掏出原子项t的运就是。A.headtailtailLB.tailheadheadtailLC.headtailheadtailLD.headtail(headtailtailL)19.曾经明白狭义表LS(a,b,c),(d,e,f),应用head跟tail函数掏出LS华夏子e的运就是()。A.head(tail(LS)B.tail(head(LS)C.head(tail(head(tail(LS)D.head(tail(tail(head(LS)20.狭义表A=(a,b,(c,d),(e,(f,g),那么上面式子的值为。Head(Tail(Head(Tail(Tail(A)A.(g)B.(d)C.cD.d21.曾经明白狭义表:A=(a,b),B=(A,A),C=(a,(b,A),B),求以下运算的后果:tail(head(tail(C)=()。A.aB.AC.aD.(b)E.bF.(A)22.狭义表运算式Tail(a,b),(c,d)的操纵后果是。A.(c,d)B.c,dC.(c,d)D.d23.狭义表L=a，b，c，进展TailL操纵后的后果为。A.cB.b，cC.b，cD.b，c24.狭义表a,b,c,d的表头是，表尾是。A.aB.C.a,b,c,dD.b,c,d25.狭义表a,(b,c),d,e的表头为。A.aB.a,(b,c)C.(a,(b,c)D.(a)26.设狭义表L=a,b,c，那么L的长度跟深度分不为。A.1跟1B.1跟3 C.1跟2D.2跟327.上面说法不准确的选项是()。A.狭义表的表头老是一个狭义表B.狭义表的表尾老是一个狭义表C.狭义表难以用次序存储构造D.狭义表能够是一个多档次的构造二、推断题1.数组不合适作为任何二叉树的存储构造。2.从逻辑构造上看，n维数组的每个元素均属于n个向量。3.稀少矩阵紧缩存储后，必会得到随机存取功用。4.数组是同范例值的聚集。5.数组可当作线性构造的一种推行，因而与线性表一样，能够对它进展拔出，删除等操纵。6.一个稀少矩阵Am*n采纳三元组方法表现，假定把三元组中有关行下标与列下标的值调换，并把m跟n的值调换，那么就实现了Am*n的转置运算。7.二维以上的数组事实上是一种特别的狭义表。8.狭义表的取表尾运算，其后果平日是个表，但偶然也但是个单位素值。9.假定一个狭义表的表头为空表，那么此狭义表亦为空表。10.狭义表中的元素或许是一个弗成联系的原子，或许是一个非空的狭义表。11.所谓取狭义表的表尾确实是前往狭义表中最初一个元素。12.狭义表的同级元素直属于统一个表中的各元素存在线性关联。13.对长度为无量年夜的狭义表，因为存储空间的限度，不克不及在盘算机中实现。14.一个狭义表能够为别的狭义表所共享。三、填空题1.数组的存储构造采纳_存储方法。2.设二维数组A-20.30,-30.20,每个元素占领4个存储单位,存储肇端地点为200.如按行优先次序存储,那么元素A25,18的存储地点为_1_；如按列优先次序存储,那么元素A-18,-25的存储地点为_2_。3.设数组a1.50,1.80的基地点为2000，每个元素占2个存储单位，假定以行序为主序次序存储，那么元素a45,68的存储地点为_1_;假定以列序为主序次序存储，那么元素a45,68的存储地点为_2_。4.将整型数组A1.8，1.8按行优先次第存储在肇端地点为1000的延续的内存单位中，那么元素A7，3的地点是：_。5.二维数组a456下标从0开场计，a有4*5*6个元素，每个元素的长度是2，那么a234的地点是_。(设a000的地点是1000,数据以行动主方法存储)6.设有二维数组A0.9,0.19,其每个元素占两个字节，第一个元素的存储地点为100，假定按列优先次序存储，那么元素A6,6存储地点为_。7.曾经明白数组A0.9,0.9的每个元素占5个存储单位，将其按行优先次第存储在肇端地点为1000的延续的内存单位中，那么元素A6，8的地点为_。8.曾经明白二维数组A1.10，0.9中每个元素占4个单位，在按行优先方法将其存储到肇端地点为1000的延续存储地区时，A5，9的地点是：_。9.用一维数组B与列优先寄存带状矩阵A中的非零元素Ai,j(1in,i-2ji+2),B中的第8个元素是A中的第_1_行，第_2_列的元素。10.设数组A0.8,1.10,数组中任一元素Ai,j均占内存48个二进制位，从首地点2000开场延续寄存在主内存里，主内存字长为16位，那么l寄存该数组至多需求的单位数是_;2寄存数组的第8列的一切元素至多需求的单位数是_;3数组按列存储时，元素A5,8的肇端地点是_。11设n行n列的下三角矩阵A已紧缩到一维数组B1.n*n+1/2中，假定按行动主序存储，那么Ai,j对应的B中存储地位为_。12.n阶对称矩阵a满意aij=aji,i,j=1.n,，用一维数组t存储时，t的长度为_(1)_，当i=j，aij=t(2),i>j,aij=t(3),i<j,aij=t(4)。13己知三对角矩阵A【1.9,1.9】的每个元素占2个单位，现将其三条对角线上的元素逐行存储在肇端地点为1000的延续的内存单位中，那么元素A7,8的地点为_。14.设有一个10阶对称矩阵A采纳紧缩存储方法以行动主序存储：a11=1，那么a85的地点为_。15.所谓稀少矩阵指的是_。16.对矩阵紧缩是为了_。17.上三角矩阵紧缩的下标对应关联为：_。18.假定一个15阶的上三角矩阵A按行优先次序紧缩存储在一维数组B中，那么非零元素A9,9在B中的存储地位k=_。注：矩阵元素下标从1开场19.当狭义表中的每个元素基本上原子时，狭义表便成了_。20.狭义表的表尾是指除第一个元素之外，_。21.狭义表简称表，是由零个或多个原子或子表构成的无限序列，原子与表的差异仅在于(1)_。为了辨别原子跟表，普通用(2)_表现表，用(3)_表现原子。一个表的长度是指(4)_，而表的深度是指_(5)_22.狭义表的_界说为狭义表中括弧的重数。23设狭义表L=(),(),那么head(L)是(1)_；tail(L)是(2)_；L的长度是(3)_；深度是(4)_。24.曾经明白狭义表A=(9,7,(8,10,(99),12)，试用求表头跟表尾的操纵Head()跟Tail()将原子元素99从A中掏出来。25.狭义表的深度是_。26.狭义表(a,(a,b),d,e,(i,j),k)的长度是1_，深度是2_。27.曾经明白狭义表LS=(a，(b，c，d)，e),应用head跟tail函数掏出LS华夏子b的运就是_。28.狭义表A=a，b，c，d，e，掏出A中的原子e的操纵是:_。29.设某狭义表H=A，a,b,c，应用head函数跟tail函数求出狭义表H中某元素b的运算式_。30.狭义表A(),(a,(b),c)，head(tail(head(tail(head(A)等于。31.狭义表运算式HEAD(TAIL(a,b,c),(x,y,z)的后果是_。32.曾经明白狭义表A=a，b，c，d，e，headtailtailheadA的后果是_。33.应用狭义表的GetHead跟GetTail操纵，从狭义表L=apple，pear，banana，orange中不离出原子banana的函数表白式是_。34.以下次序段search(a,n,k)在数组a的前n(n>=1)个元素中寻出第k(1<=k<=n)小的值。这里假定数组a中各元素的值都不一样。#defineMAXN100intaMAXN,n,k;intsearch_c(inta,intn,intk)intlow,high,i,j,m,t;k-,;low=0;high=n-1;doi=low;j=high;t=alow;dowhile(i<j&&t<aj)j-;if(i<j)ai+=aj;while(i<j&&t>=ai)i+if(i<j)aj-=ai;while(i<j);ai=t;if(1);if(i<k)low=(2);elsehigh=(3);while(4)_;return(ak);35.完美以下次序，每题在PASCAL言语a跟C言语b中任选一题。上面的次序将数列1,2,3,n*n,顺次按蛇型方法寄存在二维数组A1.n,1.n中。即(表现图编者略)。算法的C言语次序描绘：#defineNMAX10#include“stdio.hmain()inti,j,n,k,p,q,m;intaNMAXNMAX;scanf(“%d,&n);m=1;for(k=1；(1)；k+)ifk<nq=k；else(2)_;for(p=1;p<=q;p+)if(3)i=q-p+1；j=p；elsei=p；j=q-p+1；if(4)i=i+n-q；j=j+n-q；aij=m；(5)_;fori=1；i<=n;i+forj=1；j<=n；j+printf“%4d,aij;printf(“n);36.设有一个背包能够放入的物品分量为S，现有n件物品，分量分不为W1，W2，.，Wn。咨询是否从这n件物品当选择假定干件放入背包，使得放入的分量之跟恰好是S。设布尔函数Knap(S，n)表现背包咨询题的解，Wi(i=1,2,.，n)均为正整数，并已次序存储地在数组W中。请在以下算法的下划线处填空，使其准确求解背包咨询题。Knap(S，n)假定S=0那么Knaptrue否那么假定S<0或(S>0且n<1)那么Knapfalse否那么假定Knap(1),_=true那么print(Wn)；Knaptrue否那么KnapKnap(2)_,_四使用题1.数组A1.8，-2.6，0.6以行动主序存储，设第一个元素的首地点是78，每个元素的长度为4，试求元素A4,2,3的存储首地点。2.数组A中，每个元素Ai,j的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地点S开场延续寄存主存储器中，主存储器字长为16位。求：1寄存该数组所需几多单位？2寄存数组第4列一切元素至多需几多单位？3数组按行寄存时，元素A7,4的肇端地点是几多？4数组按列寄存时，元素A4,7的肇端地点是几多？3假定按低下标优先存储整型数组A-3:8,3:5,-4:0,0:7时，第一个元素的字节存储地点是100，每个整数占4个字节，咨询A0，4，-2，5的存储地点是什么？4设有三维数组A-2:4,0:3,-5:1按列序寄存，数组的肇端地点为1210，试求A(1,3,-2地点的地点。5.三维数组A1.10,-2.6,2.8的每个元素的长度为4个字节，试咨询该数组要占几多个字节的存储空间？假如数组元素以行优先的次序存贮，设第一个元素的首地点是100，试求元素A5,0,7的存贮首地点。6数组A0.8,1.10的元素是6个字符构成的串，那么寄存A至多需求几多个字节？A的第8列跟第5行共占几多个字节？假定A按行优先方法存储，元素A8,5的肇端地点与当A按列优先方法存储时的哪个元素的肇端地点分歧？7.假定依照紧缩存储的思维将n×n阶的对称矩阵A的下三角局部包含主对角线元素以行序为主序方法寄存于一维数组B1.n(n+1)/2中，那么，A中任一个下三角元素aij(ij),在数组B中的下标地位k是什么？数组跟狭义表考研真题精选谜底一、选择题1.B2.1L2.2J2.3C2.4I2.5C3.B4.B5.A6.1H6.2C6.3E6.4A6.5F7.B8.1E8.2A8.3B9.B10.B11.B12.B13.A14.B15.B16.A17.C18.D19.C20.D21.F22.C23.D24.C25.A26.C27.A二、推断题1.×2.3.4.×5.×6.×7.8.×9.×10.×11.×12.13.14.局部谜底说明如下。1.过错。对于完整二叉树，用一维数组作存储构造是效力高的存储密度年夜。4.过错。数组是存在一样性子的数据元素的聚集，数据元素不只要值，另有下标。因而，能够说数祖是元素值跟下标形成的偶对的有穷聚集。5.过错。数组在维数跟界偶断定后，其元素个数曾经断定，不克不及进展拔出跟删除运算。6.过错。稀少矩阵转置后，除行列下标及行列数调换外，还必需断定该元素转置后在新三元组中的地位。8.过错。狭义表的取表尾运算，长短空狭义表撤除表头元素，残余元素构成的表，不克不及够是原子。9.过错。狭义表的表头确实是狭义表的第一个元素。只要非空狭义表才干取表头。10.过错。狭义表中元素能够是原子，也能够是表包含空表跟非空表。11.过错。狭义表的表尾，指去掉落表头元素后，残余元素所构成的表。三、填空题1.次序存储构造2.19572212283.19174287884.11005.1164公式：LOC(aijk)=LOC(a000)+v2*v3*(i-c1)+v3*(j-c2)+(k-c3)*l(l为每个元素所占单位数)6.2327.13408.11969.第1行第3列10.(1)270(2)27(3)220411.i(i-1)/2+j(1<=i,j<=n)12.(1)n(n+1)/2(2)i(i+1)/2(或j(j+1)/2)(3)i(i-1)/2+j(4)j(j-1)/2+i(1<=i,j<=n)13.1038三对角矩阵按行存储：k=2(i-1)+j(1<=i,j<=n)14.33(k=i(i-1)/2+j)(1<=i,j<=n)15.非零元非常少(t<<m*n)且散布不法则16.节约存储空间。17.上三角矩阵中，主对角线上第r(1£r£n)行有n-r+1个元素，aij所外行的元素数是j-i+1。因而，元素在一维数组的下标k跟二维数组下标关联:k=(i-1)*(2n-i+2)/2+(j-i+1)=(i-1)(2n-i)/2+j(i£j)18.i(i-1)/2+j19.线性表20.其他元素构成的表21.1原子单位素是构造上弗成再分的，能够是一个数或一个构造；而表带构造，实质确实是狭义表，因作为狭义表的元素故称为子表。2年夜写字母3小写字母4表中元素的个数5表开展后所含括号的层数22.深度23.12324224.headheadtailtailheadtailtailA25.表开展后所含括号的层数26.152327.head(head(tail(LS)28.head(tail(tail(head(tail(head(A)29.head(tail(head(tail(H)30.(b)31.(x,y,z)32.(d,e)33.GetHead(GetHead(GetTail(L)341(i=k)return2i+13i-14i!=k本算法应用疾速排序思维，寻到第k个元素的地位下标k-1因而开初有k-。内层do轮回以t(t=alow)为“枢轴寻到其应在i地位。这时假定i等于k，那么算法完毕。即第一个空格处if(i=k)return)。否那么，假定i<k，就在i+1至high两头去查；假定i>k，那么在low到i-1间去寻，直到寻到i=k为止。35.此题请求将1，2，.,n*n个天然数，按蛇型方法寄存在二位数组Ann中。“蛇型方法，等于按“副对角线平行的各对角线，从左下到右上，再从右上到左下，寄存n2个整数。对角线共2n-1条，在副对角线上方的对角线，标题顶用k表现第k条对角线最左上角k=1，数组元素x跟y偏向坐标之跟为k+1即标题中的i+j=k+1。副对角线下方第k条对角线与第2n-k条对角线对称，其元素的下标等于其对称元素的响应坐标各加(k-n)。1k<=2*n-1/共填2*n-1条对角线2q=2*n-k/副对角线以下的各条对角线上的元素数3k%2！=0/k为偶数时从右上到左下，否那么从左下向右上填数。本处盘算下标i跟j4k>=n/修正副对角线下方的下标i跟j。5m+；或m=m+1/为填下个数作预备，m变更范畴1.n*n。此题解法的另一种思绪见本章算法计划题第9题。36.假定第n件物品能放入背包，那么咨询题变为是否再从n-1件物品当选出假定干件放入背包这时背包可放入物品的分质变为s-wn。假定第n件物品不克不及放入背包，那么思索从n-1件物品选假定干件放入背包这时背包可放入物品仍为s。假定终极s=0,那么有一解；否那么，假定s<0或尽管s>0但物品数n<1,那么无解。1s-wn,n-1/Knap(s-wn,n-1)=true2s,n-1/KnapKnap(s,n-1四、使用题1、958三维数组以行动主序存储，其元素地点公式为：LOC(Aijk)=LOC(Ac1c2c3)+(i-c1)V2V3+(j-c2)V3+(k-c3)*L+1此中ci,di是各维的下界跟上界，Vi=di-ci+1是各维元素个数，L是一个元素所占的存储单位数。2每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。12422223s+1824s+14231784(公式：Loc(Aijkl)=100(基地点)+(i-c1)v2v3v4+(j-c2)v3v4+(k-c3)v4+(l-c4)*44.1210+108L(LOC(A1,3,-2)=1210+(k-c3)v2v1+(j-c2)v1+(i-c1)*L设每个元素占L个存储单位5.数组占的存储字节数=10*9*7*4=2520；A5,0,7的存储地点=100+4*9*7+2*7+5*4=11846154021083i=3,j=10，即A3,107k=i(i-1)/2+j