《数据结构》课后题及答案.doc

《《数据结构》课后题及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章　绪论一、选择题1、()是数据的基本单位。 A)数据结构　　B)数据元素　　C)数据项　　　D)数据类型2、以下说法不正确的是()。 Ａ)数据结构就是数据之间的逻辑结构。 Ｂ)数据类型可看成是程序设计语言中已实现的数据结构。Ｃ)数据项是组成数据元素的最小标识单位。 Ｄ)数据的抽象运算不依赖具体的存储结构。3、计算机算法是解决问题的有限运算序列,它具备输入、输出和（　　）等5个特性。A)可执行性、可移植性和可扩充性　　　　B)可行性、确定性和有穷性C)确定性、有穷性和稳定性　　　　　　D)易读性、稳定性和安全性4、一般而言，最适合描述算法的语言是()。A)自

2、然语言B)计算机程序语言C)介于自然语言和程序设计语言之间的伪语言D)数学公式5、通常所说的时间复杂度指()。A)语句的频度　　B)算法的时间消耗C)渐近时间复杂度　　D)最坏时间复杂度6、A算法的时间复杂度为O(n3)，B算法的时间复杂度为O(2n)，则说明()。 A)对于任何数据量，A算法的时间开销都比B算法小 B)随着问题规模n的增大，A算法比B算法有效 C)随着问题规模n的增大，B算法比A算法有效 D)对于任何数据量，B算法的时间开销都比A算法小7、算法分析的目的是（）。A)找出数据结构的合理性　　　　B)研究算法中的输入和输出的关系C)分析算法的效率以

3、求改进　　　D)分析算法的易懂性和文档性8、下面程序段的时间复杂度为（）。for(i=0;i

4、

5、n==1)return1;elsereturnn*f(n-1);}A)O(1)B)O(n)C)O(n2)D)O(n!)二、填空题1、数据的(　　)结构依赖于计算机语言。2、在线性结构中，第一个结点（）前驱结点,其余每个结点有且只有（）个前驱结点；最后一个结点（）后继结点；其

6、余每个结点有且只有（）个后继结点。993、在树形结构中,树根结点没有（）结点，其余每个结点有且只有（）个前驱结点；叶子结点没有（　　）结点，其余每个结点的后继结点可以（　　　）。4、在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着(　　)、（）和（）的关系。5、评价一个算法优劣的两个主要指标是（）和（）。6、数据的逻辑结构被分为()、()、()和()四种。7、数据的存储结构被分为()、（）、（）、（）四种.8、算法的时间复杂度除了与问题的规模有关外，还与输入实例的(　)有关。三、问答题与算法题1、简述下列概念：数据元素：数据结构：数据类型：数据的逻

7、辑结构及其4种类型：数据的存储结构及其4种方式：2、设两个算法在同一台机器上执行，其执行时间分别是n2和2n，要使前者快于后者，n至少需要多大？3、有时为比较两个同数量级的算法优劣，须突出主项的常数因子，而将低次项用”O”记号表示。如：设T1(n)=1.39nlogn+100n+256=1.39nlogn+O(n);T2(n)=2.0nlogn-2n=2.0nlogn–O(n);这两个式子表示，当n足够大时，T1(n)优于T2(n)，因为前者的系数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣。(1)T1(n)=5n2-3n+6

8、0logn;(2)T2(n)=3n2+1000n+3logn;(3)T3(n)=8n2+3logn;　　(4)T4(n)=1.5n2+O(n)。4、计算执行下面程序段时，执行S语句的次数为。for(i=1;i<=n;i++)for(j=1;j<=i;j++)S;第二章　线性表一、选择题1、线性表是具有n个（　　）的有限序列。A)数据项；　B)数据元素；　C)数据对象；　D)表元素。2、以下关于线性表的说法不正确的是()。A)线性表中的数据元素可以是数字、字符、记录等不同类型。B)线性表中包含的数据元素个数不是任意的。 C)线性表中的每个结点都有且只有一个直接前趋

9、和直接后继。 99D)存在这样的线性表：表中各结点都没有直接前趋和直接后继。3、线性表的顺序存储结构是一种()的存储结构。 A)随机存取　 B)顺序存取　C)索引存取　　 D)散列存取4、在顺序表中，只要知道()，就可在相同时间内求出任一结点的存储地址。A)基地址 　B)结点大小　C)线性表大小　　D)基地址和结点大小5、下面关于线性表的叙述中，错误的是哪一个？（）A)线性表采用顺序存储，必须占用一片连续的存储单元。B)线性表采用顺序存储，便于进行插入和删除操作。C)线性表采用链接存储，不必占用一片连续的存储单元。D)线性表采用链接存储，便于插入和删除操作。6、

10、线性表采用链表存储时其存