数据规划考研真题与答案解析.docx(数据规划是什么岗位)--考研网上

一、选择题算法的核算量的巨细称为核算的〔b)。【北京邮电大学2000二、3(20/8分)】功率b.凌乱性c.实际性d,难度算法的时刻凌乱度取决于c)【中科院核算所1998二、1〔2分)】疑问的规划b.待处置数据的初态c.a和b核算机算法指的是(c),它有必要具有(b)这三个特性。a.核算办法b.排序办法c,处置疑问的进程序列d.调度办法a.可实施性、可移植性、可扩展性b.可实施性、断定性、有穷性c.断定性、有穷性、平稳性d.易读性、平稳性、平安性【南京理工大学1999一、1〔2分)【武汉交通科技大学1996一、1〔4分)】一个算法大约是(b)o【中山大学1998二、1〔2分)】a.程序b.疑问求解进程的描绘c.要满足五个根柢特性d.a和c.下面关于算法说法差错的选项是(d)【南京理工大学2000一、1〔1.5分)】a.算法究竟有必要由核算机程序完成为处置某疑问的算法同为该疑问编写的程序意义是相同的算法的可行性是指指令不能有二义性d.以上几个都是差错的下面说法差错的选项是(c)［南京理工大学2000一、2(1.5分)】(1)算法原地作业的意义是指不需耍任何额定的辅佐空间在相同的规划n下,凌乱度0(n)的算法在时刻上老是优于凌乱度0(2吋的算法所谓时刻凌乱度是指最坏情况下，预算算法实施时刻的一个上界〔4)同一个算法，完成言语的等级越高，实施功率就越低47.a.(1)b.7.a.(1)b.⑴，(2)从逻辑上可以把数据规划分为、4〔2分)】a.动态规划、静态规划线性规划、非线性规划c.(1),(4)d.(3)(c)两大类。【武汉交通科技大学1996次序规划、链式规划初等规划、规划型规划8.以下与数据的存储规划无关的术语是〔d)。【北方交通大学2000二、1〔2分)】8.a.循环行列以下数据规划中，1〔2分）】a.广义表b.链表哪一个是线性规划b,二叉树c.d)c.哈希表d.栈?【北方交通大学2001一、稀少矩阵d.串以下那一个术语与数据的存储规划无关？〔a）【北方交通大学2001一、2〔2分）】a.栈链表鄙人面的程序段中，对x的赋值语句的频度为北京工商大学2001一、10〔3分）】fori:=ltondob.哈希表c.条理树d.双向forj:=ltondox:=x+l;a.0（2n）b.0（n）c.0（m）d.0（log『）程序段fori:=n-ldownto1doforj:=ltoidoifa[j]>a[j+l]thena[j]与a[j+1]对换:其间n为正整数，则最终一行的语句频度在最坏情况下是（d）a.0（n）b.o（nlogn）c.0（w）d.0（m）【南京理工大学1998一、1（2分）】以下哪个数据规划不是多型数据类型（d）【中山大学1999一、3（1分）】a.栈b.广义表c.有向图d.字符串以下数据规划中，（a）对错线性数据规划【中山大学1999一、4】a.树b.字符串c.队d.栈以下数据中，〔c）对错线性数据规划。【北京理工大学2001六、1（2分）】a.栈b.行列c.完全二叉树d.堆接连存储方案时，存储单元的地址（a）o[中山大学1999一、1（1分）】a.必定接连b.必定不接连c.不必定接连d.部分接连，部分不接连以下归于逻辑规划的是（c）。【西安电子科技大学使用2001—、1]a.次序表b.哈希表c.有序表d.单链表二、判别题数据元素是数据的最小单位。（x）【北京邮电大学1998一、1（2分）】【青岛大学2000一、1（1分）】【上海交通大学1998一、1】【山东师范大学2001一、1〔2分）】记载是数据处置的最小单位。（x）【上海海运学院1998一、5〔1分）】数据的逻辑规划是指数据的各数据项之间的逻辑联络；（x）【北京邮电大学2002一、1（1分）】算法的好坏与算法描绘言语无关，但与所用核算机有关。（x）【大连海事大学2001一、10（1分）】健旺的算法不会因不合法的输入数据而呈现难以想象的状况。（0）【大连海事大学2001一、11（1分）】算法可以用不一样的言语描绘，假定用c言语或pascal言语等高档言语来描绘，则算法实践上就是程序了。（x）【西安交通大学1996二、7（3分）】程序必定是算法。（x）【燕山大学1998二、2〔2分）并改错】数据的物理规划是指数据在核算机内的实践存储方法。（0）【山东师范大学2001一、2（2分）】数据规划的笼统操作的界说与具体完成有关。（x）【华南理工大学2002一、1〔1分）】在次序存储规划中，有时也存储数据规划中元素之间的联络。（x）【华南理工大学2002一、2〔1分）】次序存储方法的利益是存储密度大，且刺进、删去运算功率高。（x）【上海海运学院1999一、i〔1分）】数据规划的根柢操作的设置的最重耍的原则是，完成使用程序与存储规划的独立。（0）【华南理工大学2002一、5〔1分）】数据的逻辑规划阐明数据元素之间的次序联络，它依靠于核算机的储存规划.（x）【上海海运学院1998一、1〔1分）】三、填空数据的物理规划包括数据元索的标明和数据元素?间联络的标明。【燕山大学1998一、1（2分）】关于给定的n个元素，可以规划出的逻辑规划有集结线性规划树形规划图状规划（或网状规划）四种。【中科院核算所1999二、1〔4分）】数据的逻辑规划是指数据的组织方法，即数据元素之间逻辑联络的全体而逻辑联络是指数据元素之间的相关方法或称“邻接联络"。【北京邮电大学2001二、1（2分）】一个数据规划在核算机中标明（又称映像）称为存储规划。【华中理工大学2000一、1（1分）】笼统数据类型的界说仅取决于它的一组逻辑特性，而与在核算机内部如何标明和完成无关，即不管其内部规划如何改变，只需它的数学特性不变，都不影响其外部运用。【山东大学2001三、3〔2分）】数据规划中评预算法的两个重要方针是算法的时刻凌乱度和空间凌乱度【北京理工大学2001七、1（2分）】数据规划是研讨数据的—逻辑规划和物理规划，以?侵涞谋舜肆纾⒍杂胝庵止婊缢迪嘤Φ牟僮鳌苍怂悖桨赋鱿嘤Φ乃惴ā！疚靼驳缱涌萍即笱?998二、2〔3分）】一个算法具有5个特性:〔1）有穷性（2）断定性（3）可行性，有零个或多个输入、有一个或多个输出。【华中理工大学2000一、2（5分）】【燕山大学1998一、2（5分）】如下程序段fori:=ndownto1do（语句1}beginx:=x+l；{语句2}forj:=ndowntoido{语句3}y:=y+l;{语句4}end；语句1实施的频度为n+1:语句2实施的频度为n:语句3实施的频度为n（n+3）/2；语句4实施的频度为n（n+l）/2。【北方交通大学1999二、4〔5分）】鄙人面的程序段中，对x的赋值语句的频度为1+〔1+2++〔1+2+3）+???+（l+2+—+n）=n（n+l）（n+2）/6ogv）〔标明为n的函数）fori:=1tondoforj:=1toidofork:=ltojdox:=x+delta；【北京工业大学1999一、6〔2分）】下面程序段中带下划线的语句的实施次数的数量级是:log.,n【合肥工业大学1999三、1（分）】i:=1；whilei<ndoi:二i*2;下面程序段中带下划线的语句的实施次数的数量级是（nlog.n）o【合肥工业大学2000三、1〔2分）】i:=l;whilei<nbeginforj:=ltondox:二x+1:i:二i*2end；下面程序段中带有下划线的语句的实施次数的数量级是（logm）【合肥工业大学2001三、1〔2分）】i:=n*nwhileioldoi:=idiv2;核算机实施下面的语句时，语句s的实施次数为(n+3)(n-2)/2.【南京理工大学2000m1(1.5分)】f0r(i=l；i<n-l；i++)f0r(j=n;j>=i;j—)s;下面程序段的时刻凌乱度为—0(n)o(n>l)sum=l；for(i=0;sum<n;i++)sum+=l:【南京理工大学2001二、1〔2分)】设m.n均为天然数，m可标明为一些不跨越n的天然数之和，f(m,n)为这种标明方法的数目。例f(5,3)=5,有5种标明方法:3+2,3+1+1,2+2+1,2+1+1+1,1+1+1+1+u①以下是该函数的程序段，请将未结束的部分填入，使之无缺intf(m,n)intm,n;{if(m==l)return丄；if(n=l)(return丄;}if(m<n){returnf(m,m);}if(m==n){return1+f(m,n-1);}returnf(m.n~l)+f(m-n,n);}②实施程序，f(6,4)=&。【中科院软件所1997二、1〔9分)】在有n个选手参加的单循环赛中，一共将发展n(n-l)/2场竞赛。【合肥工业大学1999三、8〔2分)】四、使用题数据规划是一门研讨啥内容的学科？【燕山大学1999二、1〔4分)】数据规划是一门研讨在非数值核算的程序方案疑问中，核算机的操刁难象及目标间的联络和施加于目标的操作等的学科。数据元素之间的联络在核算机中有几种标明办法？各有啥特征？【燕山大学1999二、2(4分)】四种标明办法次序存储方法。数据元素次序存放，每个存储结点只含一个元素。存储方位反映数据元素间的逻辑联络。存储密度大，但有些操作〔如刺进、删去）功率较差。〔2）链式存储方法。每个存储结点除包括数据元素信息外还包括一组〔至少一个）指针。指针反映数据元素间的逻辑联络。这种方法不需求存储空间接连，便于动态操作（如刺进、删去等），但存储空间开支大〔用于指针），另外不能减半查找等。〔3）索引存储方法。除数据元素存储在一地址接连的内存空间外，需要树立一个索引表，索引表中索引指示存储结点的存储方位〔下标）或存储区间端点〔下标），兼有静态和动态特性。〔4）散列存储方法。经过散列函数和处置冲突的办法，将要害词散列在接连的有限的地址空间内，并将散列函数的值说明成要害词地址元素的存储地址，这种存储方法称为散列存储。其特征是存取速度快，只能按要害词随机存取，不能次序存取，也不能减半存取。数据类型和笼统数据类型是如何界说的。二者有何相同和不一样之处，笼统数据类型的首要特征是啥？运用笼统数据类型的首要优点是啥？【北京邮电大学1994一〔8分）】数据类型是程序方案言语中的一个概念，它是一个值的集结和操作的集结。如c言语中的整型、实型、字符械寥。整型值的规模〔对具体机器都应有整数规模），其操作有加、减、乘、除、求余等。实践上数据类型是厂家供给给用户的已完成了的数据规划。“笼统数据类型（adt）”指一个数学模型及界说在该模型上的一组操作。“笼统”的意义在于数据类型的数学笼统特性。笼统数据类型的界说仅取决于它的逻辑特性，而与其在核算机内部如何标明和完成无关。不管其内部规划如何改变，只需它的数学特性不变就不影响它的外部运用。笼统数据类型和数据类型本质上是一个概念。此外，笼统数据类型的规模更广，它己不再捆绑于机器己界说和完成的数据类型，还包括用户在方案软件体系时自行界说的数据类型。运用笼统数据类型界说的软件模块含界说、标明和完成三部分，封装在一同，对用户通明（供给接口），而不必晓得完成细节。笼统数据类型的呈现使程序方案不再是“艺术"，而是向“科学〃跨进了一步。答复以下疑问（每题2分）【山东工业大学1997一〔8分）】（1）在数据规划课程中，数据的逻辑规划，数据的存储规划及数据的运算之间存在着怎样的联络？数据的逻辑规划反映数据元素之间的逻辑联络（即数据元素之间的相关方法或“邻接联络"），数据的存储规划是数据规划在核算机中的标明，包括数据元素的标明及其联络的标明。数据的运算是对数据界说的一组操作，运算是界说在逻辑规划上的，和存储规划无关，而运算的完成则是依靠于存储规划。（2）假定逻辑规划相同但存储规划不一样，则为不一样的数据规划。这样的说法对吗？举例阐明之。逻辑规划相同但存储不一样，可所以不一样的数据规划c例如，线性表的逻辑规划归于线性规划，选用次序存储规划为次序表，而釆用链式存储规划称为线性链表。（3）在给定的逻辑规划及其存储标明上可以界说不一样的运算集结，然后得到不一样的数据规划。这样说法对吗？举例阐明之。栈和行列的逻辑规划相同，其存储标明也可相同〔次序存储和链式存储），但因为其运算集结不一样而变成不一样的数据规划。（4）评价各种不一样数据规划的标准是啥？数据规划的评价非常凌乱，可以思考两个方面，一是所选数据规划是不是精确、无缺的刻划了疑问的根柢特征；二是是不是简略完成（如对数据分化是不是恰当；逻辑规划的选择是不是合适于运算的功用，是不是有利于运算的完成；根柢运算的选择是不是恰当。）评价一个好的算法，您是从哪几方面来思考的？评价好的算法有四个方面。一是算法的正确性；二是算法的易读性；三是算法的健旺性；四是算法的时空功率〔运转）。【大连海事大学1996二、3（2分）】【中山大学1998三、1（5分）】说明和比较以下各组概念【华南师范大学2000一〔10分）】u）笼统数据类型及数据类型（2）数据规划、逻辑规划、存储规划（3）笼统数据类型【哈尔滨工业大学2000一、1〔3分）】〔4）算法的时刻凌乱性【河海大学1998一、2（3分）】（5）算法【吉林工业大学1999一、1〔2分）】（6）频度【吉林工业大学1999一、2〔2分）】〔1）见上面题3（2）见上面题4（3）见上面题3〔4）算法的时刻凌乱性是算法输入规划的函数。算法的输入规划或疑问的规划是作为该算法输入的数据所含数据元素的数目，或与此数目有关的其它参数。有时思考算法在最坏情况下的时刻凌乱度或均匀时刻凌乱度。〔5）算法是对特定疑问求解进程的描绘，是指令的有限序列，其间每一条指令标明一个或多个操作。算法具有五个重要特性:有穷性、断定性、可行性、输入和输出。〔6）频度。在分析算法时刻凌乱度时，有时需要预算根柢操作的原操作，它是实施次数最多的一个操作，该操作重复实施的次数称为频度。根据数据元素之间的逻辑联络，一般有哪几类根柢的数据规划？集结、线性规划、树形规划、图形或网状规划。【北京科技大学1998一、1】【同济大学1998]关于一个数据规划，一般包括哪三个方面的谈论？【北京科技大学1999一、1〔2分）】逻辑规划、存储规划、操作（运算）。当你为处置某一疑问而选择数据规划时，应从哪些方面思考？【西安电子北京科技大学2000]一般思考算法所需耍的存储空间量和算法所需耍的时刻量。后者又触及到四方面:程序运转时所需输入的数据总量，对源程序发展编译所需时刻，核算机实施每条指令所需时刻和程序中指令重复实施的次数。假定将数据规划界说为一个二元组（d,r）,阐明符号d,r应别离标明啥？【北京科技大学2001一、1（2分）】d是数据元素的有限集结，s是d上数据元素之间联络的有限集结。数据规划与数据类型有啥差异？【哈尔滨工业大学2001三、1（3分）】“数据规划”这一术语有两种意义，一是作为一门课程的称号；二是作为一个科学的概念。作为科学概念，当前尚无公评界说，一般认为，谈论数据规划要包括三个方面，一是数据的逻辑规划，二是数据的存储规划，三是对数据发展的操作（运算）。而数据类型是值的集结和操作的集结，可以看作是己完成了的数据规划，后者是前者的一种简化情况。数据的存储规划由哪四种根柢的存储办法完成？【山东科技大学2001一、1〔4分）】12.见上面题2。假定有100个学生，每个学生有学号，名字，均匀成果，选用啥样的数据规划最便利，写出这些规划？【山东师范大学1996二、2（2分）】将学号、名字、均匀成果当作一个记载（元素，含三个数据项），将100个这样的记载存于数组中。因一般无增删操作，故宜选用次序存储。typedefstruct{intnum;//学号charname[8];//tt名floatscore;/均匀成果）node；nodestudent[100];运算是数据规划的一个重要方面。试举一例，阐明两个数据规划的逻辑规划和存储方法完全相同，只是关于运算的界说不一样。因而两个规划具有显着不一样的特性，是两个不一样的规划。【北京大学1998一、1（5分）】见上面题4（3）o在编制打点通讯录的程序时，啥样的数据规划适合？为啥？【长沙铁道学院1998四、3（6分）】应从两方面发展谈论:如通讯录较少改变（如城市私家号码），首要用于查询，以次序存储较便利，既能次序查找也可随机查找；假定通讯录常常有增删操作，用链式存储规划较为适合，将每自个的情况作为一个元素（即一个结点存放一自个），设名字作要害词，链表组织成有序表，这样可前进査询速度。试举一例，阐明对相同的逻辑规划,同一种运算在不一样的存储方法下完成，其运算功率不一样。【北京理工大学2000三、1（4.5分）】线性表中的刺进、删去操作，在次序存储方法下均匀移动近一半的元素，时刻凌乱度为0（n）；而在链式存储方法下，刺进和删去时刻凌乱度都是0⑴。有完成同一功用的两个算法a1和a2,其间a1的时刻凌乱度为t1二0（2「），a2的时刻凌乱度为t2=0（rv）,仅就时刻凌乱度而言，请具体分析这两个算法哪一个好。【北京航空航天大学2000二〔10分）】对算法a1和a2的时刻凌乱度t1和t2取对数，得nlog?和21ogw显着，算法a2好于a"方案一数据规划，用来标明某一银行储户的根柢信息:账号、名字、开户年月日、储蓄类型、存入累加数、利息、帐面总数。【浙江大学1994一、3〔5分）】structnode{intyear,month,day;};typedefstruct（intnum://帐号charname[8];//tt名structnodedate;//开户年月日inttag;//储蓄类型，如:0-零存，1-一年守时……floatput;//存入累加数；floatinterest;//利息floattotal;//帐面总数）count；写出下面算法中带标号语句的频度。typear=array[l..n]ofdatatype;procedureperm（a:ar;k,n:integer）;varx:datatype;i:integer;beginifk=nthenbeginfori:=ltondowrite(a[i]);writein;endelsebegin⑷fori:=ktondo(5)a[i]:=a[i]+i*i;⑹perm(a,k+1,n);end;end;设k的初值等于1。【北京邮电大学1997二〔10分)】(l)n(2)n+l(3)n(4)(n+4)(n-l)/2(5)(n+2)(n-l)/2(6)n-1这是一个递归调用，因k的初值为1,由语句〔6)知，每次调用k增1,故第(1)语句实施n次。〔2)是for循环语句，在满足(1)的条件下实施,该语句进入循环体(3)n次，加上最终一次判别出界，故实施了n+1次。(4)也是循环语句，当k=l时判别n+1次(进入循环体(5)n次),k=2时判别n次，最终一次k=n-l时判别3次,故实施次数是(n+l)+n+--+3=(n+4)(n-l)/2次。语句(5)是(4)的循环体，每次比(4)少一次判别，故实施次数是n+(n_d+...+2=(n+2)(n-l)/2次。留心分析时，不要把(2)分析成n次，更不是1次。分析下面程序段中循环语句的实施次数。i:=0;s:=0;n:=100;repeati:=i+i;s:=s+10*i;untiln0t((i<n)and(s<n));【北京邮电大学1998四、1〔5分)】4〔这时i=4,s=100)repeat语句先实施循环体，后判别条件，直到条件为真时退出循环。以下算法对一n位二进制数加1,假定无溢出，该算法的最坏时刻凌乱性是啥？并分析它的均匀时刻凌乱性。typenum=array[l..n]of[0..1]:procedureinc(vara:num)；vari:integer；begini:=n；whilea[i]=ldobegina[i]:=0；i:=i~l；end；end:a[i]:=1;endinc；【东南大学1998三(8分)1994二〔15分)】算法在最佳情况下，即二进制数的最终一位为零时，只作一次判别，未实施循环体，赋值语句a[i]实施了一次；最坏情况岀如今:进制数各位均为1(最高位为零，因标题假定无溢出)，这时循环体实施了nt次，时刻凌乱度是0(n),循环体均匀实施n/2次，时刻凌乱度仍是0(n)。阅览以下算法，指出算法a的功用和时刻凌乱性procedurea(h,g:pointer);(h,g别离为单循环链表(singlelinkedcircularlist)中两个结点指针)procedureb(s,q:pointer):varp:pointer;beginp:=s;whilep~.nextoqdop:=p~.next;p\next:=s;end;(ofb)beginb(h,g);b(g,h);end;(ofa)【东南大学1999二〔10分)】该算法功用是将原单循环链表分化成两个单循环链表:其一包括结点h到结点g的前驱结点；另一个包括结点g到结点h的前驱结点。时刻凌乱度是0(n)。调用以下c函数f(n)或pasacal函数f(n)答复以下疑问:试指出f(n)值的巨细，并写出f(n)值的推导进程；假定n=5,试指出f(5)值的巨细和实施f(5)时的输出

成果。c函数:intf(intn)(inti,j,k,sum=0;for(i=l;i<n+l;i++)(for(j=n;j>i-l;j-)for(k=l;k<j+l;k++)sud1++；printf("sum=%d\n",sum)；)return(sum);｝【华中理工大学2000六〔10分)】第一层for循环判别n+1次，往下实施n次，第二层for实施次数为(n+(n-l)+(n-2)+???+1),第三层循环体受第一层循环和第二层循环的控制,其实施次数如下表:toc\o"1-5"\h\zi=123…nj=nnnn???nj=n~ln-1n-1n~l???j=333j=222j=l1实施次数为(l+2+???+n)+(2+3+???+n)+?"+n=n*n(n+l)/2~n(ri2-l)/6。在n=5时，f⑸=55,实施进程中，输岀成果为:sum=15,sum=29,sum=41,sum=50,sum=55〔每个sum二占一行，为节约篇幅，这儿省去换行)。设n是偶数，试核算运转以下程序段后m的值并给出该程序段的时刻凌乱度。m:=0;fori:=ltondoforj:=2*itondom:=m+l;【南京邮电大学2000一、1]0(n0,m的值等于赋值语句m:=m+l的运转次数，其核算式为约〃_2，+1)=?41=1有以下运转时刻函数:(1)t(n)=1000;(2)t(n)=n2+1000n;(3)i2t((n)=3m+100n2+n+l;券别写出相应的大。标明的运算时刻。(1)0(1)(2)0012)(3)0(ns)【吉林工业大学1999二〔12分)】26.试给出下面两个算法的运算时刻。fori-1x—x+1endfori-1forj-1x—x+1endtodototododoend【中科院主动化研讨所1995二、2〔6分)】(do(n)(2)0(曲斐波那契数列虬界说如下f°=o,f=l,fn=fn/fm，n=2,3...请就此斐波那契数列，答复以下疑问。(7分)在递归核算f。的时分，需要对较小的虬」，f?,…，％f°精确核算多少次？(5分)假定用大o标明法，试给出递归核算虬时递归函数的时刻凌乱度录多少？【清华大学2000二〔12分)】(i)由斐波那契数列的界说可得:f=f，+f。toc\o"1-5"\h\znn-1n-2=2f+fn-2n-3=3f_+2f」n-3n-4=5f,+3fn-4n-5=8f<+5fan-5n-o=pf|+qf。设七的实施次数为bn(m=0.1、2、…、n-1),由以上等式可知，丄被实施二次，即bn=1；f〕被实施两次，即bn.=2；直至f〔被实施p次.f。被实施q次，前b「p,”bjq。b,的实施次数"另前两等式第一因式系数之和，即b=b+b,,再有b=1和上=2,这也是一个斐波那契数列。可以nn-1?-2n-1n-2解得:751+j51-75bn=5[(2)fh(2)e2](m=c,1,2,???,n-1)〔2)时刻凌乱度为o(n)将以下函数，按它们在r)f二时的无量大阶数，从小到大排序。么、n,n-n3+7ns,nlogn,2”2,rv,logn,ni^+logn,(3/2)%‘〃丿，n!,n2+logn【中科院核算所1995080385]从小到大摆放为:logo,mz+logn,n,nlogn,nz+logn,m,n-n3+7ns,(2n2s,(3/2)%n!,顷丿

未经允许不得转载：考研网上 - 考研网上辅导班有用吗 > 数据规划考研真题与答案解析.docx(数据规划是什么岗位)