《考研“数据结构”复习题.docx》由会员分享，可在线阅读，更多相关《考研“数据结构”复习题.docx（248页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1章绪论一、选择题1 .算法的计算量的大小称为计算的（）。【北京邮电大学2000二、3（20/8分）】A.效率B.复杂性 C.现实性D.难度2 .算法的时间复杂度取决于（）【中科院计算所1998二、1（2分）】A.问题的规模B.待处理数据的初态 C. A和B3 .计算机算法指的是（1）,它必须具备（2）这三个特性。（1） A.计算方法 B.排序方法（2） A.可执行性、可移植性、可扩充性C.确定性、有穷性、稳定性C.解决问题的步骤序列 D.调度方B.可执行性、确定性、有穷性D.易读性、稳定性、安全性【南京理工大学1999一、1（2分）【武汉交通科技大学1996一、1（4分）】4 .一个算法应
2、该是（）。【中山大学1998二、1（2分）】A.程序 B.问题求解步骤的描述C.要满足五个基本特性 D. A和C.5 .下面关于算法说法错误的是（）【南京理工大学2000一、1（1.5分）】A.算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上儿个都是错误的6 .下面说法错误的是（）【南京理工大学2000一、2（1.5分）】（1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模nA,复杂度O（n）的算法在时间上总是优于复杂度0（2）的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4
3、）同一个算法，实现语言的级别越高，执行效率就越低A.（1） B.（1）,（2） C.（1）,（4） D.（3）7 .从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学1996一、4（2分）】A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构 D.初等结构、构造型结构8 .以下与数据的存储结构无关的术语是（）。【北方交通大学2000二、1（2分）】A.循环队列B.链表 C.哈希表D.栈9 .以下数据结构中，哪一个是线性结构（）？【北方交通大学2001一、1（2分）】A.广义表B.二叉树 C.稀疏矩阵D.串10.以下那个术语与数据的存储结构无关？（）【北方交通大学2001
4、-、2 （2分）】D.双向链表）【北京工商大学2001 -、10 （3A.栈B.哈希表 C.线索树11 .在下面的程序段中，对x的赋值语句的频度为（分）】FOR i:=l TO n DOFOR j:=l TO n DO x:=x+l;A.0(2n) B.0(n) C.0(n2)D.0(log2n)12 .程序段 FOR i:=n-l DOWNTO 1 DOFOR j:=l TO i DOIF AjAj+lTHEN A_j与 Aj+1对换：其中n为正整数，则最后一行的语句频度在最坏情况下是（）A.0（n） B. O（nlogn） C.0（n3） D.0（n2）【南京理工大学1998、1（2分）】
5、13 .以下哪个数据结构不是多型数据类型（）【中山大学1999一、3（1分）】A.栈 B.广义表 C.有向图 D.字符串14 .以下数据结构中，（）是非线性数据结构【中山大学1999一、4A.树 B.字符串 C.队D.栈15 .下列数据中，（）是非线性数据结构。【北京理工大学2001六、1（2分）】A.栈 B.队列C.完全二叉树 D.堆16 .连续存储设计时，存储单元的地址（）。【中山大学1999一、1（1分）】A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续17 .以下属于逻辑结构的是（）。【西安电子科技大学应用2001、1】A.顺序表 B.哈希表 C.有序表D.单链表二、判
6、断题1 .数据元素是数据的最小单位。（）【北京邮电大学1998-、1（2分）】【青岛大学2000-、1（1分）】【上海交通大学1998一、1】【山东师范大学2001一、1（2分）】2 .记录是数据处理的最小单位。（）【上海海运学院1998-、5（1分）】3 .数据的逻辑结构是指数据的各数据项之间的逻辑关系；（）【北京邮电大学2002、1（1分）】4 .算法的优劣与算法描述语言无关，但与所用计算机有关。（）【大连海事大学2001、10（1分）】5 .健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（）【大连海事大学2001一、11（1分）】6 .算法可以用不同的语言描述，如果用C语言或PAS
7、CAL语言等高级语言来描述，则算法实际上就是程序了。（）【西安交通大学1996二、7（3分）】7 .程序一定是算法。（）【燕山大学1998,2（2分）并改错】8 .数据的物理结构是指数据在计算机内的实际存储形式。（）【山东师范大学2001、2（2分）】9 .数据结构的抽象操作的定义与具体实现有关。（）【华南理工大学2002-、1（1分）】10 .在顺序存储结构中，有时也存储数据结构中元素之间的关系。（）【华南理工大学2002一、2（1分）】11 .顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）上海海运学院1999一、1（1分）】12 .数据结构的基本操作的设置的最重要的准则是，实
8、现应用程序与存储结构的独立。（）【华南理工大学2002一、5（1分）】13 .数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的储存结构.（）【上海海运学院1998、1（1分）】三、填空1 .数据的物理结构包括的表示和的表示。【燕山大学19981（2分）】2 .对于给定的n个元素，可以构造出的逻辑结构有（1）,（2）,（3）,（4）四种。【中科院计算所1999二、1（4分）】3 .数据的逻辑结构是指。【北京邮电大学2001二、1（2分）】4 .一个数据结构在计算机中称为存储结构。【华中理工大学2000一、1（1分）】5 .抽象数据类型的定义仅取决于它的一组（1）,而与（2）无关,即不论
9、其内部结构如何变化，只要它的（3）不变,都不影响其外部使用。【山东大学2001三、3（2分）】6 .数据结构中评价算法的两个重要指标是【北京理工大学2001七、1（2分）】7 .数据结构是研讨数据的（1）和（2）,以及它们之间的相互关系，并对与这种结构定义相应的（3）,设计出相应的（4）。【西安电子科技大学1998二、2（3分）】8 .一个算法具有5个特性：（1）、,有零个或多个输入、有一个或多个输出。【华中理工大学2000、2（5分）】【燕山大学1998、2（5分）】9 .已知如下程序段FOR i:=n DOWNTO1DO语句1BEGINx:=x+1；语句2FORj:=n DOWNTOi D
10、O 语句3y:=y+l;语句4END；语句1执行的频度为（1）;语句2执行的频度为（2）；语句3执行的频度为（3）；语句4执行的频度为（4）。【北方交通大学1999二、4（5分）】10 .在下面的程序段中，对x的赋值语句的频度为（表示为n的函数）FOR i：=1 TO n DOFOR j：=1 TO i DOFOR k：=1 TO j DOx ：= x +delta；【北京工业大学1999一、6（2分）】11 .下面程序段中带下划线的语句的执行次数的数量级是：【合肥工业大学1999三、1（2分）】 i：=1； WHILE in DO i：=i*2;12 .下面程序段中带下划线的语句的执行次数的
11、数量级是（）。【合肥工业大学2000三、1（2分）】i:=l;WHILE in BEGIN FOR j:=l TO n DO x:=x+l;i:=i*2 END；13 .下面程序段中带有下划线的语句的执行次数的数量级是（）【合肥工业大学2001三、1（2分）】i：=n*n WHILE iOl DO i:=i div 2;14 .计算机执行下面的语句时，语句s的执行次数为。【南京理工大学2000二、1（L5分）】FOR（i=l； i=i; j）15 .下面程序段的时间复杂度为。（nl）sum=l；for (i=0; sumn; i+) sum+=l;【南京理工大学2001二、1(2分)】16 .
12、设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以下是该函数的程序段，请将未完成的部分填入，使之完整 int f (m, n) int m,n; if(m=l)return (1);if (n1)return ；if(mn)return f (m, m); if (m=n)return 1+(3);)return f (m. n-1)+f (m-n,(4);)执行程序，f(6,4)=。【中科院软件所1997二、1(9分)】17 .在有n个选手参加
13、的单循环赛中，总共将进行场比赛。【合肥工业大学1999三、8(2分)】四、应用题1 .数据结构是一门研究什么内容的学科？【燕山大学1999二、1(4分)】2 .数据元素之间的关系在计算机中有几种表示方法？各有什么特点？【燕山大学1999二、2(4分)】3 .数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？【北京邮电大学1994一(8分)】4.回答问题(每题2分)【山东工业大学1997一(8分)】(1)在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？(2)若逻辑结构相同但存储结构不同，则
14、为不同的数据结构。这样的说法对吗？举例说明之。(3)在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。(4)评价各种不同数据结构的标准是什么？5 .评价一个好的算法，您是从哪几方面来考虑的？【大连海事大学1996二、3(2分)】【中山大学1998三、1(5分)】6 .解释和比较以下各组概念【华南师范大学2000一(10分)】(1)抽象数据类型及数据类型(2)数据结构、逻辑结构、存储结构(3)抽象数据类型【哈尔滨工业大学2000一、1(3分)】(4)算法的时间复杂性【河海大学1998一、2(3分)】(5)算法【吉林工业大学1999一、1(2分
15、)】(6)频度【吉林工业大学1999、2(2分)】7 .根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？【北京科技大学1998一、1】【同济大学1998】8 .对于一个数据结构，一般包括哪三个方面的讨论？【北京科技大学1999一、1(2分)】9.当你为解决某一问题而选择数据结构时，应从哪些方面考虑？【西安电子北京科技大学2000)10 .若将数据结构定义为一个二元组(D, R),说明符号D, R应分别表示什么？【北京科技大学2001、1(2分)】11 .数据结构与数据类型有什么区别？【哈尔滨工业大学2001三、1(3分)】12 .数据的存储结构由哪四种基本的存储方法实现？【山东科技大学
16、2001-、1(4分)】13 .若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？【山东师范大学1996二、2(2分)】14 .运算是数据结构的一个重要方面。试举一例，说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不同的结构。【北京大学1998、1大分)】15 .在编制管理通讯录的程序时，什么样的数据结构合适？为什么？【长沙铁道学院1998四、3(6分)】16 .试举一例，说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算效率不同。【北京理工大学2000三、1(4.5分)】17
17、.有实现同一功能的两个算法A1和A2,其中A1的时间复杂度为Tl=0(2n), A2的时间复杂度为T2=0(r?),仅就时间复杂度而言，请具体分析这两个算法哪个好。【北京航空航天大学2000二(10分)】18 .设计一数据结构，用来表示某一银行储户的基本信息：账号、姓名、开户年月日、储蓄类型、存入累加数、利息、帐面总数。【浙江大学1994一、3(5分)】19 .写出下面算法中带标号语句的频度。TYPE ar=ARRAYl.n OF datatype;PROCEDURE perm ( a: ar; k, n: integer);VAR x: datatype; i:integer;BEGIN(1
18、) IF k=nTHEN BEGIN(2) FOR i:=l TO n DO(3) write (ai);writein;ENDELSE BEGIN(4) FOR i:=k TO n DO(5) ai:=ai+i*i;(6) perm (a, k+1, n);END;END;设k的初值等于1。【北京邮电大学1997二(10分)】20 .分析下面程序段中循环语句的执行次数。i:=0;s:=0;n:=100;REPEATi:=i+l;s:=s+10*i;UNTIL N0T(in) AND (sn);【北京邮电大学1998四、1(5分)】21 .卜列算法对一 n位二进制数加1,假如无溢出，该算法的最
19、坏时间复杂性是什么？并分析它的平均时间复杂性。TYPE num=ARRAY l.n of 0.1； PROCEDURE Inc (VAR a： num)； VAR i： integer； BEGIN i：=n； WHILE Ai=l DOBEGIN Ai：=0； i：=i-l； END；END；Ai：=1；END Inc；【东南大学1998三(8分)1994二(15分)】22 .阅读下列算法，指出算法A的功能和时间复杂性 PROCEDURE A (h, g:pointer);(h, g分别为单循环链表(single linked circular list)中两个结点指针) PROCEDURE
20、 B(s,q:pointer)；VAR p:pointer;BEGINP：=s;WHILE p nextOq DO p:=p next;p next :=s;END;(of B)BEGINB(h, g); B(g, h);END;(of A)【东南大学1999二(10分)】23 .调用下列C函数f(n)或PASACAL函数f(n)回答下列问题：(1)试指出f(n)值的大小，并写出f(n)值的推导过程；(2)假定n=5,试指出f (5)值的大小和执行f (5)时的输出结果。C 函数：int f (int n) int i, j, k,sum=0;for(i=l; ii-l; j-) for(k=
21、l;k0）【清华大学1998、4（2分）】A.表元素 B.字符 C.数据元素D.数据项E.信息项4.若某线性表最常用的操作是存取任指定序号的元素和在最后进行插入和删除运算,则利用（）存储方式最节省时间。【哈尔滨工业大学2001二、1（2分）】A.顺序表 B.双链表 C.带头结点的双循环链表D.单循环链表5 .某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。【南开大学2000一、3A.单链表 B.仅有头指针的单循环链表C.双链表 D.仅有尾指针的单循环链表6 .设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。A.
22、单链表 B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表【合肥工业大学2000一、1（2分）】7 .若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（）存储方式最节省运算时间。【北京理工大学2000一、1（2分）】A.单链表 B.双链表 C.单循环链表D.带头结点的双循环链表8 .静态链表中指针表示的是（）.【北京理工大学2001六、2（2分）】A.内存地址 B.数组下标 C.下一元素地址D.左、右孩子地址9 .链表不具有的特点是（）【福州大学1998一、8（2分）】A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间
23、与线性长度成正比10 .下面的叙述不正确的是（）【南京理工大学1996一、10（2分）】A.线性表在链式存储时，查找第i个元素的时间同i的值成正比B.线性表在链式存储时，查找第i个元素的时间同i的值无关C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比D.线性表在顺序存储时，查找第i个元素的时间同i的值无关11.线性表的表元存储方式有（1）和链接两种。试指出下列各表中使用的是何种存储方式：表1是（2）存储方式；表2是（3）存储方式；表3是（4）存储方式；表4是（5）存储方式。表左的s指向起始表元。表元编号货号数量表元间联系16184022205233103154450120557811
24、766910240表元编号货号数量表元间联系16184052205213103154450120257811766910243Sf表元编号货号数量表元间联系16184052205213103154450120057811766910243表元编号货号数量表元诃联系1216184052220521031031546450120035781176169102435供选择的答案:A.连续B.单向链接C.双向链接 D.不连接E.循环链接F.树状 G.网状 H.随机I.顺序J.顺序循环【上海海运学院1995二、1(5分)】12. (1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i
25、个元素的时间与i无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是()【南京理工大学2000-、3(1.5分)】A.(1),(2) B.(1) C.(1),(2),(3) D.(2)13 .若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为()(lLlink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；B. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C. q-
26、Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;24 .在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）oA. p-next=s;s-next=p-next; B. s-next=p-next;p-next=s;C. p-next=s;p-next=s-next; D. p-next=s-next;p-next=s;【青岛大学2001五、3（2分）】25 .对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A.
27、 head二二NULL B. head-next=NULL C. headnext二二headD. head!=NULL【北京工商大学2001-5（3分）】26 .在双向链表存储结构中，删除p所指的结点时须修改指针（）。A.B.C.D.(p-.11 ink)rlink:=p-. rlink p . llink: = (p. 11 ink)llink(p*.rlink)*. llink:=pp .rlink: = (p-. llink)llink(p-.rlink)*. 11ink:=p-. llink;(p-.llink)rlink:=p;p. rlink: = (p .rlink) . rl
28、inkp. llink: = (p-. rlink)二 rlink;【西安电子科技大学1998一、1（2分）】27 .双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去P所指结点，则正确的删除是（）（链中结点数大于2, p不是第一个结点）A. p . llink*. rlink:=p*. llink; p*.llink*.rlink:=p*. rlink; dispose(p); B. dispose(p); p.llink.rlink:=p.llink; p. llink,rlink:=p. rlink; C. p. llink. rlin
29、k:=p*. llink; dispose(p); p*. llink. rlink:=p*. rlink; D.以上A, B, C都不对。【南京理工大学1997一、1(2分)】二、判断1 .链表中的头结点仅起到标识的作用。（）【南京航空航天大学1997一、1（1分）】2 .顺序存储结构的主要缺点是不利于插入或删除操作。（）【南京航空航天大学1997-、3 （1分）】4 .线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（）【北京邮电大学1998、2（2分）】5 .顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（）【北京邮电大学2002-、2（1分）】6 .对任何数
30、据结构链式存储结构一定优于顺序存储结构。（）【南京航空航天大学1997一、3（1分）】7 .顺序存储方式只能用于存储线性结构。（）【中科院软件所1999六、1-2（2分）上海海运学院1997一、1（1分）】8 .集合与线性表的区别在于是否按关键字排序。（）【大连海事大学2001-.5（1分）】9 .所谓静态链表就是一直不发生变化的链表。（）【合肥工业大学2000二、1（1分）】10 线性表的特点是每个元素都有一个前驱和一个后继。（）【合肥工业大学2001二、1（1分）】11 .取线性表的第i个元素的时间同i的大小有关.（）【南京理工大学1997二、9（2分）】12 .循环链表不是线性表.（）【
31、南京理工大学1998二、1（2分）】13 .线性表只能用顺序存储结构实现。（）【青岛大学2001四、2（1分）】14 .线性表就是顺序存储的表。（）【青岛大学2002一、1（1分）】15 .为了很方便的插入和删除数据，可以使用双向链表存放数据。（）【上海海运学院1995一、1（1分）】【上海海运学院1997一、2（1分）】16 .顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）【上海海运学院1996一、1（1分）】【上海海运学院1999一、1（1分）】17 .链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。（）【上海海运学院1998一、2（1
32、分）】三、填空1 .当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。【北方交通大学2001二、42 .线性表L=（al, a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除个元素平均需要移动元素的个数是。【北方交通大学2001二、93 .设单链表的结点结构为（data, next）, next为指针域，已知指针px指向单链表中data 为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需要执行以卜语句：_；【华中理工大学2000一、4（2分）】4 .在一个长度为n的顺序表中第i个元素（l=i=n）
33、之前插入一个元素时，需向后移动个元素。【北京工商大学2001二、4（4分）】5 .在单链表中设置头结点的作用是。【哈尔滨工业大学2000二、1（1分）】6.对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为,在给定值为x的结点后插入一个新结点的时间复杂度为。【哈尔滨工业大学2001、1（2分）】7.根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成和而乂根据指针的连接方式，链表又可分成和。【西安电子科技大学1998二、4（3分）】8.在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是、。【中国矿业大学2000、1（3分）】9.在双向链表
34、结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s. next :=p； s. prior:=； p . prior:=s；:=s；【福州大学1998二、7（2分）】10.链接存储的特点是利用来表示数据元素之间的逻辑关系。【中山大学1998一、1 （1分）】11 .顺序存储结构是通过表示元素之间的关系的；链式存储结构是通过表示元素之间的关系的。【北京理工大学2001七、2（2分）】12 .对于双向链表，在两个结点之间插入一个新结点需修改的指针共个，单链表为个。【南京理工大学2000二、2（3分）】13 .循环单链表的最大优点是：。1福州大学1998二、3（2分）】
35、14 .已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：.【合肥工业大学1999三、2（2分）】15 .带头结点的双循环链表L中只有-一个元素结点的条件是：【合肥工业大学1999三、32000三、2（2分）】16 .在单链表L中，指针p所指结点有后继结点的条件是：【合肥工业大学2001三、3（2分）】17 .带头结点的双循环链表L为空表的条件是：o【北京理工大学2000二、1（2分）】【青岛大学2002三、1（2分”18.在单链表p结点之后插入s结点的操作是：。【青岛大学2002三、2（2分）】19.请在下列算法的横线上填入适当的语句。【清华大学1994五（15分）】FUNCTION inclusion (ha, hb:linklisttp):boolean;以ha和hb为头指针的单链表分别表示有序表A和B,本算法判别表A是否包含在表B 内，若是，则返回“true”，否则返回“false”BEGINpa:=ha next; pb:=hb next;(1);WHILE (2) DOIF pa data=pb data THEN (3) ELSE (4);END;20 .完善算法：已知单链表结点类型为：TYPE ptr= node；