大数据结构期末考试(题集)

《大数据结构期末考试(题集)》由会员分享，可在线阅读，更多相关《大数据结构期末考试(题集)（38页珍藏版）》请在金锄头文库上搜索。

1、word数据结构的根本概念选择题（1） 顺序存储结构中数据元素之间的逻辑关系是由表示的，存储结构中的数据元素之间的逻辑关系是由表示的。A线性结构B非线性结构C存储位置D指针（2） 假设有如下遗产继承规如此：丈夫和妻子可以相互继承遗产，子女可以继承父亲或母亲的遗产；子女间不能相互继承，如此表示该遗产继承关系的最适宜的数据结构应该是。A树B图C线性表D集合（3） 计算机所处理的数据一般具有某种在联系，这是指。A数据和数据之间存在某种关系B元素和元素之间存在某种关系C元素部具有某种结构D数据项和数据项之间存在某种关系（4） 在数据结构中，与所使用的计算机无关的是数据的。A树B图C线性表D集合（5）

2、在存储数据时，通常不仅要存储各数据元素的值，还要存储。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） 可以用定义一个完整的数据

3、结构。A数据元素B数据对象C数据关系D抽象数据类型（11） 对于数据结构的描述，如下说法中不正确的答案是。A一样的逻辑结构对应的存储结构也必一样B数据结构由逻辑结构、存储结构和根本操作三方面组成C数据结构根本操作的实现与存储结构有关D数据的存储结构是数据的逻辑结构的机实现（12） 以下关于存储结构的表示中，是不正确的。A结点除数据信息外还包括指针域，因此存储密度小于顺序存储结构B逻辑上相邻的结点物理上不一定相邻C可以通过计算得到第i个结点的存储地址D插入和删除操作方便，不必移动结点（13） 可以用、数据关系和根本操作定义一个完整的抽象数据类型。A数据元素B数据对象C原子类型D存储结构应用题（1

4、4） 设有数据结构D，R，其中D=1，2，3，4，5，6，R=(1，2)，(2，3)，(2，4)，(3，4)，(3，5)，(3，6)，(4，5)，(4，6)。试画出其逻辑结构图并指出属于何种结构。（15） 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。（16） 说明数据的逻辑结构和存储结构之间的关系。（17） 抽象数据类型的主要特点是什么？数据类型和抽象数据类型的关系如何？使用抽象数据类型的主要好处是什么？1 算法和算法分析选择题（1） 算法指的是。A对特定问题求解步骤的一种描述，是指令的有限序列B计算机程序C解决问题的计算方法D数据处理（2） 下面不是算法所必须具备的

5、特性。A有穷性B确切性C高效性D可行性（3） 算法必须具备输入、输出和等特性。A可行性、可移植性和可扩大性B可行性、确定性和有穷性C确定性、稳定性和有穷性D易读性、稳定性和健壮性（4） 算法应该具有确定性、可行性和有穷性，其中有穷性是指。A算法在有穷的时间终止B输入是有穷的C输出是有穷的D描述步骤是有穷的（5） 当输入非法错误时，一个“好的算法会进展适当处理，而不会产生难以理解的输出结果，这称为算法的。A可读性B健壮性C正确性D有穷性（6） 算法分析的目的是，算法分析的两个主要方面是。A找出数据结构的合理性B研究算法中输入和输出的关系C分析算法的效率以求改良D分析算法的易读性和文档性E空间性能

6、和时间性能F正确性和简明性G可读性和文档性H数据复杂性和程序复杂性（7） 算法的时间复杂度与有关。A问题规模B计算机硬件性能C编译程序的质量D程序设计语言（8） 算法的时间复杂度与有关。A问题规模B待处理数据的初态C算法的易读性DA和B（9） 某算法的时间复杂度是(n2)，明确该算法。A问题规模是n2B执行时间等于n2C执行时间与n2成正比D问题规模与n2成正比（10） 下面说法错误的答案是。算法原地工作的含义是指示不需要如何额外的辅助空间在一样的规模n下，复杂度(n)的算法在时间上总是优于复杂度(2n)的算法所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界同一个算法，实现语言的级别越

7、高，执行效率就越低（11） 算法for (i=n-1; i=1; i-)for (j=1; jaj+1) aj与aj+1交换；其中n为正整数，如此最后一行语句的频度执行次数在最坏情况下是。A(n)B(nlog2n)C(n3)D(n2)（12） 算法的时间复杂度属于一种。A事前统计的方法B事先分析估算的方法C事后统计的方法D事后分析估算的方法（13） 设某算法完成对n个元素进展处理，所需的时间是T(n)=100 nlog2n+200n+500，如此该算法的时间复杂度是。A(1)B(n)C(nlog2n)D(nlog2n+n)（14） 假设时间复杂度为(n2)的算法在有200个元素的数组上运行需要

8、3.1ms，如此在有400个元素的数组上运行需要ms。Dx无法确定（15） 如下程序段加下划线的语句执行次。for (m=0,i=1; i=1; i+)for (j=1; j=2*i; j+)m=m+1；An2B3nCn(n+1)Dn3应用题（16） 将如下函数按它们的n时的无穷大阶数，从小到大排列。n，n-n3-7n5，nlog2n，2n/2，n3，log2n，n1/2+log2n，(3/2)n，n!，n2+log2n（17） 分析以下程序段，并用大记号表示其执行时间。 / i=1;k=0;while (in-1)k=k+10*i;i+; i=1;j=0;while (i+jj) j+;el

9、se i+; for (i=1;i=n;i+)for (j=1;j=i;j+)for (k=1;k=j;k+)x+; i=1;k=0;dok=k+10*i;i+; while (i=n) y=0;while (y+1)*(y+1)=n)y=y+1 for (i=0;in;i+)for (j=0;jm;j+)aij=0;（18） 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为T1=(2n)，A2的时间复杂度为T2=(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。综合应用题（19） 设n是偶数，且有程序段：for (i=1;i=n;i+)if (2*i=n)for (j=2

10、*I;j=n;j+)y=y+i*j;如此语句y=y+i*j的执行次数是多少？要求列出计算公式。（20） 斐波那契数列Fn定义如下：F0=0，F1=1，Fn=Fn-1+Fn-2n=2，3，请就此斐波那契数列，回答如下问题。在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，F1，F0准确计算多少次？ 用大表示法给出递归计算时递归函数的时间复杂度是多少？（21） 运算是数据结构的一个重要方面。举例说明两个数据结构的逻辑结构和存储方式完全一样，只是对于运算的定义不同，因而具有不同的特性，如此这两个数据结构是不同的。（22） 针对给定的实际问题建立数据结构时，应从哪些方面考虑。2 线性表的逻辑结构选

11、择题（1） 线性表是具有n个的有限序列。A数据B字符C数据元素D数据项（2） 线性表是。A一个有限序列，可以为空B一个有限序列，不能为空C一个无限序列，可以为空D一个无限序列，不能为空（3） 关于线性表，如下说法中正确的答案是。A线性表中每个元素都有一个直接前驱和一个直接后继B线性表中的数据元素可以具有不同的数据类型C线性表中数据元素的类型是确定的D线性表中任意一对相邻的数据元素之间存在序偶关系（4） 是一个线性表。A由n个实数组成的集合B由所有实数组成的集合C由所有整数组成的序列D由n个字符组成的序列3 顺序线性表选择题（1） 一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素

12、的地址为144，如此第一个元素的地址是。A108B180C176D112（2） 在长度为n的线性表中查找值为x的数据元素的时间复杂度为。A(0)B(1)C(n)D(n2)（3） 在一个长度为n的线性表的第i1in+1个元素之前插入一个元素，需向后移动个元素，删除第i1in个元素时，需向前移动个元素。An-iBn-i+1Cn-iDn-i+1（4） 线性表的顺序存储结构是一种的存储结构。A随机存取B顺序存取C索引存取D散列存取（5） 顺序存储结构的优点是。A存储密度大B插入运算方便C删除运算方便D可方便地用于各种逻辑结构的存储表示（6） n个结点的线性表采用数组实现，算法的时间复杂度是(1)的操作是。A访问第i个结点1in和求第i个结点的直接前驱2inB在第i个结点后插入一个新结点1inC删除第i个结点1inD以上都不对（7） 对于顺序存储的线性表，访问某个元素和增加一个元素的时间复杂度为。A(n)、(n)B(n)、(1)C(1)、(n)D(1)、(1)（8） 顺序表的插入算法中，当n个空间已满时，可再申请增加分配m个空间，假如申请失败，如此说明系统没有可分配的存储空间。Am个Bm个连续的Cn+m个Dn+m个连续的应