《计算机软件技术基础所有题目答案-自学》由会员分享，可在线阅读，更多相关《计算机软件技术基础所有题目答案-自学（38页珍藏版）》请在金锄头文库上搜索。
1、1数据结构习题答案2第一节 概 论2第二节 线性表5第三节 栈和队列16第五节 树19第七节 查找25第八节 排序29操作系统练习题参考答案321数据结构习题答案第一节 概 论一、选择题1要求同一逻辑结构的所有数据元素具有相同的特性，这意味着( )。A数据元素具有同一的特点 B不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 C每个数据元素都一样 D数据元素所包含的数据项的个数要相等2数据结构是一门研究非数值计算的程序设计问题中计算机的( (1) )以及它们之间的( (2) )和运算的学科。(1) A操作对象 B计算方法 C逻辑存储 D数据映像(2) A结构 B关系 C运算 D
2、算法3数据结构被形式地定义为(D，R)，其中D是( (1) )的有限集合，R是D上( (2) )的有限集合。 (1) A算法 B数据元素 C数据操作 D逻辑结构 (2)A操作 B映像 C存储 D关系4在数据结构中，从逻辑上可以把数据结构分为( )。A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构5线性表的顺序存储结构是一种( )的存储结构。A随机存取 B顺序存取 C索引存取 DHash存取6算法分析的目的是( )。A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性7计算机算法指的是( (1) )
3、，它必须具备输入、输出和( (2) )等五个特征。 (1) A计算方法 B排序方法 C解决某一问题的有限运算序列 D调度方法 (2) A可行性、可移植性和可扩充性 B可行性、确定性和有穷性 C确定性，有穷性和稳定性 D易读性、稳定性和安全性8线性表若采用链表存储结构，要求内存中可用存储单元的地址( )。A必须是连续的 B部分必须是连续的 C一定是不连续的 D连续不连续都可以9在以下的叙述中，正确的是( )。A线性表的线性存储结构优于链式存储结构 B二维数组是它的每个数据元素为一个线性表的线性表 C栈的操作方式是先进先出 D队列的操作方式是先进后出10根据数据元素之间关系的不同特性，以下四类基本
4、的逻辑结构反映了四类基本的数据组织形式，其中解释错误的是( )。A集合中任何两个结点之间都有逻辑关系但组织形式松散 B线性结构中结点按逻辑关系依次排列形成一条“锁链” C树形结构具有分支、层次特性，其形态有点像自然界中的树 D图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接11以下说法正确的是( )。A数据元素是数据的最小单位 B数据项是数据的基本单位 C数据结构是带有结构的各数据项的集合 D数据结构是带有结构的数据元素的集合二、判断题1数据元素是数据的最小单位。2数据结构是带有结构的数据元素的集合。3数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。4数
5、据项是数据的基本单位。5数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。6数据的物理结构是数据在计算机中实际的存储形式。7算法和程序没有区别，所以在数据结构中二者是通用的。8顺序存储结构属于静态结构，链式存储结构属于动态结构。三、填空题1所谓数据的逻辑结构指的是数据元素之间的_逻辑关系_。2，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容_数据的逻辑结构、数据的存储结构、对数据施加的操作_。3数据的逻辑结构包括_集合结构_、_线性结构_、_树型结构_和_图状结构_四种类型。4在线性结构中，开始结点_没有_前驱结点，其余每个结点有且只有_一个_个
6、前驱结点。5在树形结构中，根结点只有_一个_，其余每个结点有且只有_一个_前驱结点；叶结点没有_后继_结点，其余每个结点的后继结点可以有_任意个_6在图形结构中，每个结点的前驱结点和后继结点可以有_任意个_。7算法的五个重要特性是_可行性_、_确定性_、_有穷性_、_输入_、_输出_。8下列程序段的时间复杂度是_O（n）_。 for (i=1；i=n；i+) Ai，i=0；9下列程序段的时间复杂度是_ O（n2）_。 S=0； for(i=1；i=n；i+) for(j=1；j=n；j+) s=s+Bi,j； sum=s；10存储结构是逻辑结构的_物理_实现。11从数据结构的观点看，通常所说的
7、“数据”应分成三个不同的层次，即_数据_、_数据元素_和_数据项_。12根据需要，数据元素又被称为_结点_、_记录_、_元素_或_顶点_。13通常，存储结点之间可以有_顺序存储_、_链式存储_、_索引存储_、_散列存储_四种关联方式，称为四种基本存储方式。14通常从_确定性_、_可读性_、_健壮性_、_高效性_等几方面评价算法(包括程序)的质量。15一个算法的时空性能是指该算法的_时间复杂度和_空间复杂度_，前者是算法包含的_计算量_，后者是算法需要的_存储量_。16在一般情况下，一个算法的时间复杂度是_问题规模_的函数。17常见时间复杂度的量级有：常数阶O(_1_)、对数阶O(_log2n_
8、)、线性阶O(_n_)、平方阶O(_n2_)和指数阶O(_2n_)。通常认为，具有指数阶量级的算法是_不可行_的。18数据结构的基本任务是数据结构的_设计_和_实现_。19数据对象是性质相同的_数据元素_的集合。20抽象数据类型是指一个_数学模型_以及定义在该模型上的一组操作。四、应用题1分析下列程序段的时间复杂度。 i=1； WHILE (i=n) i=i2； 答：O(log2n)2叙述算法的定义及其重要特性。答：算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。算法应该具有下列特性：可行性、确定性、有穷性、输入和输出。3简述下列术语：数据，数据元素，数
9、据结构，数据对象。答：数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。数据结构是指相互之间存在着一种或多种关系的数据元素的集合。数据对象是性质相同的数据元素的集合。4逻辑结构与存储结构是什么关系？答：在数据结构中，逻辑结构与存储结构是密切相关的，存储结构不仅将数据元素存储到计算机中，而且还要表示各数据元素之间的逻辑关系。逻辑结构与计算机无关，存储结构是数据元素之间的关系在计算机中的表示。5将数量级210，n，n2，n3，nlog2n，log2n，2n，n
10、!，(23)n，n23按增长率进行排列。答：(23)n，210，log2n，n23，n，nlog2n，n2，n3，2n，n!6设有数据逻辑结构为：D=k1，k2，k3，k9，R=，画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？答：图略。开始结点k1、k2，终端结点k6、k7。7设有如图1.1所示的逻辑结构图，给出它的逻辑结构，并说出它是什么类型的逻辑结构。答：数据逻辑结构为：D=k1，k2，k3，k8，R=，其逻辑结构类型为树型结构。8分析下列程序的时间复杂度(设n为正整数)。 (1)int rec(int n) if(n=1)return(1)； els
11、e return(nrec(n-1)； (2)x=91；y=100； While (y0) if(x10) y-； (3)i=1；j=0； while(i+jj)j+； else i+; (4)x=n；y=0；while(x=(y+1)(y+1) y+；答：(1) O(n) (2) O(1) (3) O(n) (4) O(n1/2)9设n为正数。试确定下列各程序段中前面加记号的语句的频度： (1)i=1；k=0； while(i=n-1) k+=10i； i+； ) (2) k=0； for(i=1；i=n；i+) for(j=i；j=n：j+) k+；答：(1)n-1 (2)n+(n-1)+
12、1=n(n+1)/2第二节 线性表一、选择题1线性结构中的一个结点代表一个( )。 A数据元素 B数据项 C数据 D数据结构2线性表L=(a1，a2，ai，an)，下列说法正确的是( )。 A每个元素都有一个直接前驱和直接后继 B线性表中至少要有一个元素 C表中诸元素的排列顺序必须是由小到大或由大到小的 D除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继3顺序表是线性表的( )。 A链式存储结构 B顺序存储结构 C索引存储结构 D散列存储结构4对于顺序表，以下说法错误的是( )。 A顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B顺序表的所有存
13、储结点按相应数据元素间的逻辑关系决定的次序依次排列 C顺序表的特点是：逻辑结构中相邻的结点在存储结构中仍相邻 D顺序表的特点是：逻辑上相邻的元素，存储在物理位置也相邻的单元中5对顺序表上的插入、删除算法的时间复杂度分析来说，通常以( )为标准操作。 A条件判断 B结点移动 C算术表达式 D赋值语句6对于顺序表的优缺点，以下说法错误的是( )。 A无需为表示结点间的逻辑关系而增加额外的存储空间 B可以方便地随机存取表中的任一结点 C插入和删除操作较方便 D由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)7在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数为( )。 An Bn/2 C(n-
