目前最完整的数据结构1800题包括完整答案 第一章 绪论

7. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？

【北京科技大学 1998 一、1】【同济大学 1998】

8．对于一个数据结构，一般包括哪三个方面的讨论？【北京科技大学 1999 一、1（2分）】 9. 当你为解决某一问题而选择数据结构时，应从哪些方面考虑？【西安电子北京科技大学 2000】

10. 若将数据结构定义为一个二元组（D，R）,说明符号D，R 应分别表示什么？

【北京科技大学 2001 一、1（2分）】

11．数据结构与数据类型有什么区别？【哈尔滨工业大学 2001 三、1（3分）】

12．数据的存储结构由哪四种基本的存储方法实现？【山东科技大学 2001 一、1（4分）】 13．若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？

【山东师范大学 1996 二、2（2分）】 14. 运算是数据结构的一个重要方面。试举一例，说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不同的结构。

【北京大学 1998一、1（5分）】

15. 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么?【 长沙铁道学院1998四、3(6分)】

16. 试举一例，说明对相同的逻辑结构,同一种运算在不同的存储方式下实现，其运算效率不同。

【北京理工大学 2000 三、1（4.5分）】

n

17. 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2)，A2的时间复

2

杂度为T2=O(n)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。【北京航空航天大学 2000 二（10分）】

18．设计一数据结构，用来表示某一银行储户的基本信息： 账号、姓名、开户年月日、储蓄类型、存入累加数、利息、帐面总数。【浙江大学 1994 一 、3（5分）】 19. 写出下面算法中带标号语句的频度。

TYPE ar=ARRAY[1..n] OF datatype;

PROCEDURE perm ( a: ar; k, n: integer); VAR x: datatype; i:integer; BEGIN

（1）IF k=n THEN BEGIN

（2）FOR i:=1 TO n DO （3）write (a[i]); writeln; END ELSE BEGIN

（4） FOR i:=k TO n DO （5）a[i]:=a[i]+i*i; （6） perm (a, k+1, n); END; END;

设k的初值等于1。

【北京邮电大学 1997二（10分）】

20. 分析下面程序段中循环语句的执行次数。

i:=0;s:=0;n:=100; REPEAT i:=i+1; s:=s+10*i;

UNTIL NOT((i

【北京邮电大学 1998 四、1（5分）】

21．下列算法对一n位二进制数加1，假如无溢出，该算法的最坏时间复杂性是什么？并分析它的平均时间复杂性。

TYPE num=ARRAY [1..n] of [0..1]； PROCEDURE Inc （VAR a：num）； VAR i：integer； BEGIN i：=n；

WHILE A[i]=1 DO

BEGIN A[i]：=0； i：=i-1；END； END；

A[i]：=1； END Inc；

【东南大学1998 三 (8分) 1994 二（15分）】

22. 阅读下列算法，指出算法A的功能和时间复杂性

PROCEDURE A (h,g:pointer);

(h,g分别为单循环链表（single linked circular list）中两个结点指针) PROCEDURE B(s,q:pointer)； VAR p:pointer; BEGIN p:=s;

WHILE p^.next<>q DO p:=p^.next; p^.next:=s; END;(of B) BEGIN

B(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-1; j--) for(k=1;k

sum++;

printf(\；

}

return (sum);

} 【华中理工大学 2000 六（10分）】

24．设n是偶数，试计算运行下列程序段后m的值并给出该程序段的时间复杂度。

m:=0;

FOR i:=1 TO n DO

FOR j:=2*i TO n DO m:=m+1;

【南京邮电大学 2000 一、1】 25．有下列运行时间函数：

232

（1）T1 (n)=1000; （2）T2(n)=n+1000n; （3）T3(n)=3n+100n+n+1; 分别写出相应的大O表示的运算时间。

【吉林工业大学 1999 二（12分）】 26. 试给出下面两个算法的运算时间。

（1） for i←1 to n do x ← x+1 END

（2） for i← 1 to n do for j←1 to n do x← x+1 end end

【中科院自动化研究所 1995 二、2 （6分）】 27. 斐波那契数列Fn定义如下

F0=0， Fl=1， Fn=Fn-1+Fn-2, n=2,3... 请就此斐波那契数列，回答下列问题。

(1) (7分) 在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，…, Fl, F0精确计算多少次? (2) (5分) 如果用大O表示法，试给出递归计算Fn时递归函数的时间复杂度录多少?

【清华大学 2000 二（12分）】

28．将下列函数，按它们在n→∝时的无穷大阶数，从小到大排序。

?2n?????35n/231/2nn??,n!, n2+logn n, n-n+7n, nlogn, 2, n, logn, n+logn, (3/2),

【中科院计算所 1995 】

小学少先队组织机构 少先队组织由少先队大队部及各中队组成，其成员包括少先队辅导员、大队长、中队长、小队长、少先队员，为了健全完善我校少先队组织，特制定以下方案： 一、成员的确定 1、大队长由纪律部门、卫生部门、升旗手、鼓号队四个组织各推荐一名优秀学生担任（共四名），该部门就主要由大队长负责部门内的纪律。 2、中、小队长由各班中队公开、公平选举产生，中队长各班一名（共11名），一般由班长担任，也可以根据本班的实际情况另行选举。小队长各班各小组先选举出一名（共8个小组，就8名小队长）然后各班可以根据需要添加小队长几名。 3、在进行班级选举中、小队长时应注意，必须把卫生、纪律部门的检查学生先选举在中、小队长之内，剩余的中、小队长名额由班级其他优秀学生担任。 4、在班级公开、公平选举出中、小队长之后，由班主任老师授予中、小队长标志，大队长由少先队大队部授予大队长标志。 二、成员的职责及任免 1、大、中、小队长属于学校少先队组织，各队长不管是遇见该班的、外班的，不管是否在值勤，只要发现任何人在学校内出现说脏话、乱扔果皮纸屑、追逐打闹、攀爬栏杆、乱写乱画等等一些违纪现象，都可以站出来制止或者报告老师。 2、班主任在各中队要对中、小队长提出具体的责任，如设置管卫生的小队长，管纪律的小队长，管文明礼貌的、管服装整洁的等等，根据你班的需要自行定出若干相应职责，让各位队长清楚自己的职权，有具体可操作的事情去管理，让各位队长成为班主任真正的助手，让学生管理学生。各中队长可以负责全班的任何违纪现象，并负责每天早上检查红领巾与校牌及各小队长标志的佩戴情况。 3、大、中、小队长标志要求各队长必须每天佩戴，以身作则，不得违纪，如有违纪现象，班主任可根据中、小队长的表现撤消该同学中、小队长的职务，另行选举，大队长由纪律、卫生部门及少先队大队部撤消，另行选举。 4、各班中、小队长在管理班级的过程中负责，表现优秀，期末评为少先队部门优秀干部。