数据结构第1章 绪论[4]

下面程序段的时间复杂度为________(n>)

sum=;

for (i=;sum

16.设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+1。

①以下是该函数的程序段，请将未完成的部分填入，使之完整

int f(m,n)

int m,n;

{ if(m==1)

return (1) ;

if(n==1){

return (2) ;}

if(m

{return f(m,m);}

if (m==n)

{return 1+ (3) ;}

return f(m.n-1)+f(m-n, (4) );

}

②执行程序，f(6,4)= 。TW.WINGwIT.cOm 【中科院软件所 1997 二、1 (9分)】

17. 在有n个选手参加的单循环赛中，总共将进行______场比赛。【合肥工业大学1999三、8(2分)】

四、应用题

1. 数据结构是一门研究什么内容的学科?【燕山大学 1999 二、1 (4分)】

2. 数据元素之间的关系在计算机中有几种表示方法?各有什么特点?【燕山大学1999 二、2(4分)】

3. 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么?使用抽象数据类型的主要好处是什么?【北京邮电大学 1994 一(8分)】

4. 回答问题(每题2分)【山东工业大学 1997 一 (8分)】

(1)在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系?

(2)若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗?举例说明之。

(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分)】

(6)频度【吉林工业大学 1999 一、2(2分)】

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

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

[1] [2] [3] [4] [5] [6] [7]