数据结构 第1章 绪论

第1章绪论

一、选择题

1. 算法的计算量的大小称为计算的（B）。

A．效率B. 复杂性C. 现实性D. 难度

2. 算法的时间复杂度取决于（C ）A．问题的规模B. 待处理数据的初态C. A和B

3.计算机算法指的是（1）C，它必须具备（2）B 这三个特性。

(1) A．计算方法B. 排序方法C. 解决问题的步骤序列D. 调度方法

(2) A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性

C. 确定性、有穷性、稳定性

D. 易读性、稳定性、安全性

4．一个算法应该是（B ）。

A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.

5. 下面关于算法说法错误的是（D ）

A．算法最终必须由计算机程序实现

B.为解决某问题的算法同为该问题编写的程序含义是相同的

C. 算法的可行性是指指令不能有二义性

D. 以上几个都是错误的

6. 下面说法错误的是（C）【南京理工大学2000 一、2 （1.5分）】

(1）算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

（4）同一个算法，实现语言的级别越高，执行效率就越低

A．(1) B.(1),(2) C.(1),(4) D.(3)

7．从逻辑上可以把数据结构分为（C）两大类。【武汉交通科技大学1996 一、4（2分）】

A．动态结构、静态结构B．顺序结构、链式结构

C．线性结构、非线性结构D．初等结构、构造型结构

8．以下与数据的存储结构无关的术语是（D）。【北方交通大学2000 二、1（2分）】A．循环队列B. 链表C. 哈希表D. 栈

9．以下数据结构中，哪一个是线性结构（D）？【北方交通大学2001 一、1（2分）】A．广义表B. 二叉树C. 稀疏矩阵D. 串

10．以下那一个术语与数据的存储结构无关？（A ）【北方交通大学2001 一、2（2分）】

A．栈B. 哈希表C. 线索树D. 双向链表

11．在下面的程序段中，对x的赋值语句的频度为（C ）【北京工商大学2001 一、10（3分）】

FOR i:=1 TO n DO

FOR j:=1 TO n DO

x:=x+1;

A．O(2n) B．O(n) C．O(n2) D．O(log2

n)

12．程序段FOR i:=n-1 DOWNTO 1 DO

FOR j:=1 TO i DO

IF A[j]>A[j+1]

THEN A[j]与A[j+1]对换；

其中n为正整数，则最后一行的语句频度在最坏情况下是（D ）

A. O（n）

B. O(nlogn)

C. O(n3)

D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（D ）【中山大学1999 一、3（1分）】A．栈B．广义表C．有向图D．字符串

14．以下数据结构中，（A）是非线性数据结构【中山大学1999 一、4】

A．树B．字符串C．队D．栈

15. 下列数据中，（C）是非线性数据结构。【北京理工大学2001 六、1（2分）】A．栈B. 队列C. 完全二叉树D. 堆

16．连续存储设计时，存储单元的地址（A）。【中山大学1999 一、1（1分）】A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续

17．以下属于逻辑结构的是（C ）。【西安电子科技大学应用2001一、1】

A．顺序表B. 哈希表C.有序表D. 单链表

二、判断题

1. 数据元素是数据的最小单位。(F ) 数据项

2. 记录是数据处理的最小单位。(F ) 数据项

3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( F)

逻辑结构就是反应数据之间的逻辑关系

4．算法的优劣与算法描述语言无关，但与所用计算机有关。( F)

5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(T )

6．算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。(F )

7．程序一定是算法。(F )

程序算法是对特定问题求解过程的描述，是指令的有限序列，每条指令完成一个或多个操作。通俗地讲，就是为解决某一特定问题而采取的具体有限的操作步骤。

8．数据的物理结构是指数据在计算机内的实际存储形式。( T )

9. 数据结构的抽象操作的定义与具体实现有关。(F )

10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(F )

11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(F )

12. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。( T )

13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (F )

三、填空

1．数据的物理结构包括的表示和的表示。数据元素数据元素间关系

2. 对于给定的n个元素,可以构造出的逻辑结构有（1），（2），（3），__（4）_四种。集合线性结构树形结构图状结构或网状结构

3．数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或称“邻接关系”。【北京邮电大学2001 二、1（2分）】

4．一个数据结构在计算机中表示（又称映像）称为存储结构。【华中理工大学2000 一、1（1分）】

5．抽象数据类型的定义仅取决于它的一组__（1）_，而与_（2）_无关，即不论其内部结构如何变化，只要它的_（3）_不变，都不影响其外部使用。【山东大学2001 三、

3（2分）】

（1）逻辑特性（2）在计算机内部如何表示和实现（3）数学特性。

6．数据结构中评价算法的两个重要指标是【北京理工大学2001 七、1（2分）】

算法的时间复杂度和空间复杂度

7. 数据结构是研讨数据的_（1）_和_（2）_，以及它们之间的相互关系，并对与这种结构定义相应的_（3）_，设计出相应的（4）_。【西安电子科技大学1998 二、2（3分）】

（1）逻辑结构（2）物理结构（3）操作（运算）（4）算法。

8．一个算法具有5个特性: （1）、（2）、（3），有零个或多个输入、有一个或多个输出。

8．（1）有穷性（2）确定性（3）可行性。

【华中理工大学2000 一、2（5分）】【燕山大学1998 一、2（5分）】

9．已知如下程序段

FOR i:= n DOWNTO 1 DO {语句1}

BEGIN

x:=x+1；{语句2}

FOR j:=n DOWNTO i DO {语句3}

y:=y+1; {语句4}

END；

语句1执行的频度为（1）；语句2执行的频度为（2）；语句3执行的频度为（3）；语句4执行的频度为（4）。【北方交

通大学1999 二、4（5分）】

10．在下面的程序段中，对ｘ的赋值语句的频度为______（表示为n的函数）

FOR i：＝１TO n DO

FOR j：＝１TO i DO

FOR k：＝1 TO j DO

ｘ：＝ｘ＋delta；

【北京工业大学1999 一、6（2分）】

11.下面程序段中带下划线的语句的执行次数的数量级是：【合肥工业大学1999三、1（2分）】

i：=1；WHILE i

https://www.wendangku.net/doc/2f18418917.html,/zzu/kaoyan/document/kaoyan/shiti/st01.htm（第2／6 页）2010-4-15 10:59:40

第一章

12. 下面程序段中带下划线的语句的执行次数的数量级是( )。【合肥工业大学2000 三、1（2分）】

i:=1;

WHILE i

13. 下面程序段中带有下划线的语句的执行次数的数量级是( ) 【合肥工业大学2001

三、1（2分）】

i：=n*n WHILE i<>1 DO i:=i div 2;

14. 计算机执行下面的语句时，语句s的执行次数为_______ 。【南京理工大学2000二、1（1.5分）】

FOR(i=l；i

FOR(j=n;j>=i;j--)

s;

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

sum=1；

for (i=0;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)= 。【中科院软件所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】

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分）】

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

言，请具体分析这两个算法哪一个好。【北京航空航天大学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)；

https://www.wendangku.net/doc/2f18418917.html,/zzu/kaoyan/document/kaoyan/shiti/st01.htm（第4／6 页）2010-4-15 10:59:40

第一章

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; i

{for(j=n;j>i-1; j--)

for(k=1;k

sum++;

printf("sum=%d\n",sum)；

}

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．有下列运行时间函数：

（1）T1 (n)=1000; （2）T2(n)=n2+1000n; （3）T3(n)=3n3+100n2+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. 斐波那契数列F n定义如下

F0=0，F l=1，F n=F n-1+F n-2, n=2,3...

请就此斐波那契数列，回答下列问题。

(1) (7分) 在递归计算F n的时候，需要对较小的F n-1，F n-2，?, F l, F0精确计算多少次?

(2) (5分) 如果用大O表示法，试给出递归计算F n时递归函数的时间复杂度录多少? 【清华大学2000 二（12分）】

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

n, n-n3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n, ,n!, n2+log__

数据结构练习 第一章 绪论

数据结构练习第一章绪论 一、选择题 1.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 2．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02， 06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（）。 A. 线性结构 B. 树型结构 C. 物理结构 D. 图型结构 3．下面程序的时间复杂为（） for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} A. O(n) B.O(n2) C. O(n3) D. O(n4) 4．数据的最小单位是（）。 A.数据项 B. 数据类型 C.数据元素 D. 数据变量 5．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（）。 A. O(n) B. O(nlog 2 n) C. O(n2) D. O(n3/2) 6．下列程序段的时间复杂度为（）。 for(i=0； i

数据结构 习题 第一章 绪论

第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（） A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 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 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中 n为正整数，则最后一行的语句频度在最坏情况下是（）

《数据结构》习题汇编01 第一章 绪论 试题

《数据结构与算法设计》习题册 第一章绪论 一、单项选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运 算等的学科。 ①A. 数据元素 B. 计算方法 C. 逻辑存储 D. 数据映象 ②A. 结构 B. 关系 C. 运算 D. 算法 2.数据结构被形式地定义为（K，R），其中K是①的有限集，R是K上的②有限集。 ①A. 算法 B. 数据元素 C. 逻辑结构 D. 数据操作 ②A. 操作 B. 存储 C. 映象 D. 关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 4.数据结构在计算机内存中的表示是指。 A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系 5.在数据结构中，与所使用的计算机无关的是数据的结构。 A. 逻辑 B. 存储 C. 逻辑和存储 D. 物理 6.算法分析的目的是①，算法分析的两个主要方面是②。 ①A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ②A. 空间复杂度和时间复杂度 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 7.计算机算法指的是①，它必须具备输入、输出和②等5个特性。 ①A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 8.在以下叙述中，正确的是。 A. 线性表的线性存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C. 栈的操作方式是先进先出 D. 队列的操作方式是先进后出 9.在决定选取何种存储结构时，一般不考虑。 A. 各结点的值如何 B. 结点个数的多少 C. 对数据有哪些运算 D. 所用编程语言实现这种结构是否方便 10.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储。

数据结构(第二版)习题

第一章绪论 一、问答题 1. 什么是数据结构？ 2. 叙述四类基本数据结构的名称与含义。 3. 叙述算法的定义与特性。 4. 叙述算法的时间复杂度。 5. 叙述数据类型的概念。 6. 叙述线性结构与非线性结构的差别。 7. 叙述面向对象程序设计语言的特点。 8. 在面向对象程序设计中，类的作用是什么？ 9. 叙述参数传递的主要方式及特点。 10. 叙述抽象数据类型的概念。 二、判断题（在各题后填写“√”或“×”） 1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（） 2. 算法就是程序。（） 3. 在高级语言（如C或 PASCAL）中，指针类型是原子类型。（） 三、计算下列程序段中X=X+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 四、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。（2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 第二章线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元素结点。 2.2 填空： （1）在顺序表中插入或删除一个元素，需要平均移动＿＿＿＿元素，具体移动的元 素个数与＿＿插入或删除的位置＿＿有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。在单链表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由＿＿＿＿＿＿指示，首元素结点的存储位置由＿＿＿＿＿＿指示，除首元素结点外，其它任一元素结点的存储位置由＿＿＿＿指示。 2.3 已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。

数据结构(C语言版)第一章绪论练习及答案

一、选择题 1、数据结构通常是研究数据的（）及它们之间的相互联系。 A、存储和逻辑结构 B、存储结构 C、顺序结构 D、链式存储结构 2、数据在计算机存储器内表示时，物理地址和逻辑位置相同并且是连续的，称之为（） A、存储结构 B、逻辑结构 C、顺序存储结构 D、链式存储结构 3、线性结构是数据元素之间存在一种（） A、一对多关系 B、多对多关系 C、多对一关系 D、一对一关系 4、计算机算法指的是（），它具备输入、输出和（）等五个特性。 1）A、计算方法B、排序方法C、解决问题的有限运算序列D、调度方法2）A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、易读性、确定性和安全性 5、在计算机中数据有链式和顺序两种存储方式，在存储空间利用率上，链式存储比顺序存储更（） A、高 B、低 C、相同 D、不确定 6、计算机内部数据处理的基本单位是（） A、数据 B、数据元素 C、数据项 D、数据库 7、设语句x++的时间是单位时间，则语句： for(I=1;I<=n;I++) x++; 时间复杂度为（） A、O（1） B、O（n） C、O（n2） D、O（n3） 二、填空题 1、数据结构按逻辑结构可分为两大类，分别是（线性结构）和（非线性结构）。 2、一个算法的效率可分为（时间）效率和（空间）效率。 3、在树型结构中，根结点没有（双亲）结点，其余每个结点有且只有（一）个前驱结点；叶子结点没有（孩子）结点，其余每个结点的都可以（一个或多个）个这种结点。 4、下面程序段的时间复杂度是（O(N1/2)） I=s=0; while (s

数据结构第一章 绪论 答案

数据结构与算法上机作业第一章绪论

一、选择题 1、数据结构是一门研究非数值计算程序中计算机的○1A 以及它们之间的○2B 和运算等的学科。 ○1 A. 操作对象 B. 计算方法 C. 逻辑存储 D. 数据映像 ○2 A. 结构 B. 关系 C. 运算 D. 算法 2、线性结构的顺序存储结构是一种○1 A 的存储结构，线性结构的链式存储结构是一种○2 B 的存储结构。 ○1 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 ○2 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 3、下面程序的时间复杂度为 C 。 for(i=0; i

算法与数据结构1—5章 课后习题

第一章绪论习题练习答案 1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结 构、非线性结构。 ●数据：指能够被计算机识别、存储和加工处理的信息载体。 ●数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、 记录。数据元素有时可以由若干数据项组成。 课后答案网https://www.wendangku.net/doc/2f18418917.html, ●数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以 看作是程序设计语言中已实现的数据结构。 ●数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容: 数据的逻辑结构、存储结构和数据的运算。 ●逻辑结构：指数据元素之间的逻辑关系。 ●存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构. ●线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一 个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋

和一个直接后继。线性 表就是一个典型的线性结构。栈、队列、串等都是线性结构。 ●非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前 趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 答： 例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。 这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录 (有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它 的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前 趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结 构是线性结构。 这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片 连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点

数据结构课程总结——第一章绪论

第一章——绪论 前言（为什么会有数据结构这门课） 计算机主要应用在两个方面：一个是数值计算，另一个是非数值计算。 早期的计算机只能处理数值计算（也就是数学上的运算，特点是计算过程复杂，数据类型相对简单，数据量较少），这时候人们主要通过程序设计的思想来处理处理问题。 随着计算机渗入生活，人们开始要求计算机参与处理非数值计算（特点是计算过程相对简单，数据结构相对复杂，数据的组织排列结构从某种意义上决定着非数据计算应用的有效性，数据的组织排列结构成为处理和解决数据处理问题的核心），这时候原来的程序设计以程序为中心的设计过程已经无法满足大量的非数值计算。急需一门以复杂数据为中心，研究数据的合理组织形式，并设计出基于合理数据组织结构下的高效程序的科学来指导计算机的发展。数据结构就是在这种环境下诞生的。 每种数据结构类型都分四个描述层次——概念层、逻辑层、存储层、运算实现层。 而数据结构往往在逻辑层上为程序抽象出算法，并对算法进行优化。最终推出较优的指导性算法，方便后续的具体程序设计。 什么是数据结构 数据结构是随着计算机科学的发展而建立起来的围绕非数值计算问题的一门科学。 准确来说，数据结构就是研究大量数据在计算机中存储的组织形式，并定义且实现对数据相应的高效运算，以提高计算机的数据处理能力的一门科学。 这里的运算主要指的是非公式化的运算，如数据存取、插入、删除、查找、排序和遍历等运算。 也就是说，数据结构是管信息管理和存储的，研究怎么存比较好，怎么管理相对比较优化。 而这里就涉及到一个问题：信息应该怎么表示，根据程序设计中介绍的思路，要在电脑中写入一个数据，应该包括它的属性和它的位置。只要有他的位置和属性都确定了，那这个数据就完整地被存储到计算机中了。 所以，信息是由信息元素的值及信息元素之间的相互关系（逻辑顺序）和信息元素在计算机中的存储方式（物理顺序）共同组成。 逻辑结构就是代表了信息本身的属性，他是与计算机本身无关的“逻辑组织结构”它的构成是由数据的值、数据与数据之间的关联方式两个部分组成。 而存储方式则是代表他在计算机的位置，是将具有逻辑组织结构的数据在计算机的存储介质上如何存放的“物理组织结构”。 做好了逻辑和储存两方面的处理，信息才真正变成了计算机中的一个数据。 同时，根据定义，另一个问题无法忽视，什么高效运算？ 在我看来，高效运算指的就是算法的优化。因为算法不仅要实现问题的要求，而且，应

南京晓庄学院数据结构题库参考答案

数据结构与算法 习题册 （课后部分参考答案） 《数据结构与算法》课程组

目录 目录 课后习题部分 第一章绪论 (1) 第二章线性表 (3) 第三章栈和队列 (5) 第四章串 (8) 第五章数组和广义表 (10) 第六章树和二叉树 (13) 第七章图 (16) 第九章查找 (20) 第十章排序 (23)

第一章绪论 一. 填空题 1. 从逻辑关系上讲，数据结构的类型主要分为集合、线性结构、树结构和图结构。 2. 数据的存储结构主要有顺序存储和链式存储两种基本方法，不论哪种存储结构，都要存储两方面的内容：数据元素和数据元素之间的关系。 3. 算法具有五个特性，分别是有穷性、确定性、可行性、输入、输出。 4. 算法设计要求中的健壮性指的是算法在发生非法操作时可以作出处理的特性。 二. 选择题 1. 顺序存储结构中数据元素之间的逻辑关系是由C表示的，链接存储结构中的数据元素之间的逻辑关系是由D表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 2. 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是B。 A 树 B 图 C 线性表 D 集合 3. 算法指的是A。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 三. 简答题 1. 分析以下各程序段，并用大O记号表示其执行时间。 (1)(2) i=1;k=0; i=1;k=0; While(i

数据结构题集答案

数据结构题集答案

数据结构题集 第一章绪论 一、单选题 1.在数据结构中，从逻辑上可以把数据结构分成【 C 】。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2.数据结构在计算机内存中的表示是指【A 】。 A.数据的存储结构 B.数据结构 C.数据结构的逻辑结构 D.数据元素之间的关系 3. 【A 】是数据的最小单位，【B 】是数据的基本单位。 A.数据项 B.数据元素 C.信息项 D.表元素 4. 计算机所处理数据一般具有某种内在联系，这是指【 B 】。 A.数据与数据之间存在某种关系 B.数据元素与数据元素之间存在某种关系 C.元素内部存在某种结构 D.

数据项与数据项之间存在某种关系 5.算法分析的目的是【C 】。 A.找出数据结构的合理性 B.研究输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性 6.在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储【 C 】。 A.数据处理的方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 7.算法分析的主要任务是分析【D 】。 A.算法是否具有较好的可读性 B.算法中是否存储语法错误和逻辑错误 C.算法的功能是否符合设计要求 D.算法的执行时间与问题规模之间的关系。 8.数据的运算【A 】。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述

9.算法的计算量的大小称为算法的【B 】。 A.效率 B.时间复杂度 C.现实性 D.难度 10.连续存储分配时，存储单元的地址【A 】。 A.一定连续 B.一定不连续 C.不一定连续 D.部分连续，部分不连续 二、判断题 1.数据元素是数据结构的最小单位【.×】。 2.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【×.】。 3.数据的逻辑结构指数据元素的各数据项之间的逻辑关系【×.】。 4.算法的优劣与算法的描述语言无关，但与使用的计算机有关【.×】。 5.数据结构的抽象操作的定义与具体实现有关【.×】。 三、填空题 1.数据的逻辑结构指数据元素之间的逻辑关系。 2.一个数据结构在计算机中的表示称为存储结构。 3.数据的物理结构主要包括顺序存储结构

数据结构课后习题解答第一章 绪论

第一章绪论 1.1 试写一个算法，自大到小依次输出顺序读入的三个数X、Y和Z的值。 void Desceding(int &x, int &y, int &z) { //将x、y和z按从大到小的顺序排列 if (xsqrt(n) printf("%d is a prime number", n) else printf("%d is not a prime number", n); }/* prime */ 最坏情况下O(sqrt(n)) (2) float sum1(int n){ /* 计算1！+2！+…+n! */ p=1; sum1=0; for (i=1; i<=n; ++i){ p=p*i; sum1=sum1+p } }/* sum1 */ O(n) (3) float sum2(int n){

/* 计算1！+2！+…+n! */ sum2=0; for (i=1; i<=n; ++i){ p=1; for (j=1; j<=i; ++j) p=p*j; sum2=sum2+p; } }/* sum2 */ O(n2) (4) void sort(int a[],int n){ /* 将数组a中的元素按自小到大的顺序排列*/ for (i=1; i<=n-1; ++i){ k=i; for (j=i+1; j<=n; ++j) if (a[j]j) {x=a[i];a[i]=a[k];a[k]=x;} } }/* sort */ O(n2) （5）void matrimult(a[m][n],b[n][l],c[m][l],int m,int n,int l){ /* a为m×n阶的矩阵，b为n×l阶的矩阵，c为m×l阶的矩阵*/ /* 计算c=a*b */ for (i=1; i<=m; ++i) for (j=1; j<=l; ++j) c[i,j]=0; for (i=1; i<=m; ++i) for (j=1; j<=l; ++j) for (k=1; k<=n; ++k) c[i,j]=c[i,j]+a[i,k]*b[k,i]; }/* matrimult */ O(n3) 1.16 void print_descending(int x,int y,int z) //按从大到小顺序输出三个数{ scanf("%d,%d,%d",&x,&y,&z);

《数据结构》(C语言版) 第一章 绪论 习题及答案

一、单选题 1、______ 是数据的最小单位。 A、数据项 B、表元素 C、信息项 D、数据元素 2、以下说法不正确的是______。 A、数据可由若干个数据元素构成 B、数据项可由若干个数据元素构成 C、数据项是不可分割的最小标识单位 D、数据元素是数据的基本单位 3、数据结构是指 ______ 的集合以及它们之间的关系。 A、数据 B、结构 C、数据元素 D、计算方法 4、计算机所处理的数据一般具备某种内在联系，这是指 ______。 A、数据和数据之间存在某种关系 B、元素和元素之间存在某种关系 C、元素内部具有某种结构 D、数据项和数据项之间存在某种关系 5、在数据结构中，与所使用的计算机无关的是数据的 ______ 结构。 A、逻辑 B、存储 C、逻辑和存储 D、物理 6、数据的逻辑结构可以分为 ______ 两类。 A、紧凑结构和非紧凑结构 B、动态结构和静态结构 C、线性结构和非线性结构

D、内部结构和外部结构 7、数据的逻辑结构是指 ______ 关系的整体。 A、数据项之间逻辑 B、数据元素之间逻辑 C、数据类型之间 D、存储结构之间 8、以下是数据结构中 ______ 属非线性结构。 A、串 B、栈 C、队列 D、平衡二叉树 9、以下属于逻辑结构是 ______。 A、双链表 B、单链表 C、顺序表 D、有序表 10、以下不属于存储结构是______。 A、顺序表 B、线性表 C、邻接表 D、单链表 11、在计算机中存储数据时，通常不仅要存储各数据元素的值，而且还有存储 ______。 A、数据元素之间的关系 B、数据元素的类型 C、数据的处理方法 D、数据的存储方法 12、数据结构在计算机内存中的表示是指 ______。 A、数据的逻辑结构 B、数据结构 C、数据元素之间的关系

通信数据结构第一章绪论习题

第一章绪论 一、选择题 1.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 2．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02， 06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（）。 A. 线性结构 B. 树型结构 C. 物理结构 D. 图型结构 3．下面程序的时间复杂为（） for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} A. O(n) B.O(n2) C. O(n3) D. O(n4) 4．数据的最小单位是（）。 A.数据项 B. 数据类型 C.数据元素 D. 数据变量 5．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(n3/2) 6．下列程序段的时间复杂度为（）。 for(i=0； i

数据结构-数据结构-1绪论

第一章绪论 一．单项选择题 1．数据对象是指______ 。 A.描述客观事物且由计算机处理的数值、字符等符号的总称 B.数据的基本单位 C.性质相同的数据元素的集合 D.相互之间存在一种或多种特定关系的数据元素的集合 2．在数据结构中，数据的基本单位是。 A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 3．数据结构中数据元素之间的逻辑关系被称为____________________________________________________ 。 A. 数据的存储结构 B. 数据的基本操作 C. 程序的算法 D. 数据的逻辑结构 4．在数据结构中，与所使用计算机无关的是数据的________________________________ 。 A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构 5．在链式存储结构中，数据之间的关系是通过______________________________________________ 体现的。 A. 数据在内存的相对位置 B. 指示数据元素的指针 C. 数据的存储地址 D. 指针 6．在定义 ADT 时，除数据对象和数据关系外，还需说明 ____________ 。 A. 数据元素 B. 算法 C. 基本操作 D. 数据项 7．计算算法的时间复杂度是属于一种。 A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法 8．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是 _____________ 。 A. n2 B. nlogn C. n D. logn 9．设使用某算法对 n 个元素进行处理，所需的时间是 T(n)=100nlog2n+200n+2000 ，则该算法的渐近时间复杂度为______________ 。 A. O(1) B. O(n) C. O(200n) D. O(nlog2n) 10．有如下递归函数 fact(a) ，其时间复杂度为 _________ 。 int fact(int a) { if(n==0) retrun 1; else return(n*fact(n-1)); } A. 0(n) B. 0(n2) C. 0(n3) D. O(n4) 11 .线性表若米用链式存储结构时，要求内存中可用存储单兀的地址_______ 。 A.必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续不连续都可以

数据结构第一章绪论练习题

一、选择题 1．组成数据的基本单位是( c )。 (A)数据项 (B)数据类型 (C)数据元素(D)数据变量 2．数据结构是研究数据的( c )以及它们之间的相互关系。 (A)理想结构，物理结构 (B)理想结构，抽象结构 (c)物理结构，逻辑结构 (D)抽象结构，逻辑结构3．下列程序的时间复杂度为( A ) for(i=0;i

5．已知某算法的执行时间为， n为问题规模，则该算法的时间复杂度是( D )。 〔A)O(n) (B)O(n2) (C)O(log2n) (D)0(n3log2n) 二、填空题 1．一个算法，如果不论问题规模大小，运行所需 时间都一样，则该算法的时间复杂度是___常量阶__。 2．巳知某算法的执行时间为(n+n2)/2+log2 (2n+1)，n为问题规模，则该算法的时间复杂度是___ O(n2)__________。 3．数据结构有线性结构、树结构、___集合、_图 状结构或网状结构等几种逻辑结构。 4．数据结构有_逻辑结构和物理结构等两种物 理结构。

数据结构考试题库含答案

数据结构考试题库含答案 Revised by Jack on December 14,2020

数据结构习题集含答案 目录

选择题 第一章绪论 1. 数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2. 数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3. 某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分， 那么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4. *数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6. 算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系

C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 7. 算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8. 计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存 储比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10. 算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11. 数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12. 在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13. 线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种 （ A ）存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取

数据结构习题及答案 (8)

第一章绪论 一、选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 参考答案：C 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 参考答案：C 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 参考答案：C 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构（B）关系（C）运算（D）算法 参考答案：A B 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 参考答案：C 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。 ① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性参考答案：C B 二、判断题 1.数据的机内表示称为数据的存储结构。（）

2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 参考答案：1、√2、×3、×4、×5、√ 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 线性、树形、图形、集合；非线性（网状） 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 没有；1；没有；1 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。 前驱；1；后继；任意多个 4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________。 任意多个 5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系。 一对一；一对多；多对多 6.算法的五个重要特性是_______、_______、______、_______、_______。 有穷性；确定性；可行性；输入；输出 7.数据结构的三要素是指______、_______和________。 数据元素；逻辑结构；存储结构 8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。 插入、删除、合并等操作较方便 9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构。 顺序存储；链式存储

数据结构耿国华课后答案

数据结构耿国华课后答案 本文由edu_tech贡献 第一章绪论 一、问答题 1. 什么是数据结构？ 2. 叙述四类基本数据结构的名称与含义。 3. 叙述算法的定义与特性。 4. 叙述算法的时间复杂度。 5. 叙述数据类型的概念。 6. 叙述线性结构与非线性结构的差别。 7. 叙述面向对象程序设计语言的特点。 8. 在面向对象程序设计中，类的作用是什么？ 9. 叙述参数传递的主要方式及特点。 10. 叙述抽象数据类型的概念。 二、判断题（在各题后填写“√”或“×”） 1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（） 2. 算法就是程序。（） 3. 在高级语言（如C或PASCAL）中，指针类型是原子类型。（） 三、计算下列程序段中X=X+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】 i=1时： 1 = (1+1)×1/2 = (1+12)/2 i=2时：1+2 = (1+2)×2/2 = (2+22)/2 i=3时：1+2+3 = (1+3)×3/2 = (3+32)/2 … i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n2)/2 x=x+1的语句频度为： f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2 =[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2 =n(n+1)(n+2)/6 =n3/6+n2/2+n/3 区分语句频度和算法复杂度： O(f(n)) = O(n3) 四、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x 和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出