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

数据结构的基本概念选择题（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．可以通过计算得到第i个结点的存储地址D．插入和删除操作方便，不必移动结点（13）可以用（）、数据关系和基本操作定义一个完整的抽象数据类型。

A．数据元素B．数据对象C．原子类型D．存储结构应用题（14）设有数据结构（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）下面（）不是算法所必须具备的特性。

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．空间性能和时间性能F．正确性和简明性G．可读性和文档性H．数据复杂性和程序复杂性（7）算法的时间复杂度与（）有关。

A．问题规模B．计算机硬件性能C．编译程序的质量D．程序设计语言（8）算法的时间复杂度与（）有关。

A．问题规模B．待处理数据的初态C．算法的易读性D．A和B（9）某算法的时间复杂度是○(n2)，表明该算法（）。

A．问题规模是n2B．执行时间等于n2C．执行时间与n2成正比D．问题规模与n2成正比（10）下面说法错误的是（）。

①算法原地工作的含义是指示不需要如何额外的辅助空间②在相同的规模n下，复杂度○(n)的算法在时间上总是优于复杂度○(2n)的算法③所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界④同一个算法，实现语言的级别越高，执行效率就越低（11）算法for (i=n-1; i>=1; i--)for (j=1; j<=i; j++)if (a[j]>a[j+1]) a[j]与a[j+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个元素的数组上运行需要3.1ms，则在有400个元素的数组上运行需要（）ms。

A．3.1 B．6.2 C．12.4 D．x（无法确定）（15）下列程序段加下划线的语句执行（）次。

for (m=0,i=1; i<=1; i++)for (j=1; j<=2*i; j++)m=m+1；A．n2B．3n C．n(n+1) D．n3应用题（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 (i<n-1){k=k+10*i;i++;}②i=1;j=0;while (i+j<=n)if (i>j) j++;else i++;③for (i=1;i<=n;i++)for (j=1;j<=i;j++)for (k=1;k<=j;k++)x++;④i=1;k=0;do{k=k+10*i;i++;} while (i<=n)⑤y=0;while ((y+1)*(y+1)<=n)y=y+1⑥for (i=0;i<n;i++)for (j=0;j<m;j++)a[i][j]=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*I;j<=n;j++)y=y+i*j;则语句y=y+i*j的执行次数是多少？要求列出计算公式。

（20）斐波那契数列F n定义如下：F0=0，F1=1，…，F n=F n-1+F n-2n=2，3，…请就此斐波那契数列，回答下列问题。

①在递归计算F n的时候，需要对较小的F n-1，F n-2，…，F1，F0精确计算多少次？②用大○表示法给出递归计算时递归函数的时间复杂度是多少？（21）运算是数据结构的一个重要方面。

举例说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同，因而具有不同的特性，则这两个数据结构是不同的。

（22）针对给定的实际问题建立数据结构时，应从哪些方面考虑。

2线性表的逻辑结构选择题（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个元素的地址为144，则第一个元素的地址是（）。

A．108 B．180 C．176 D．112（2）在长度为n的线性表中查找值为x的数据元素的时间复杂度为（）。

A．○(0) B．○(1) C．○(n) D．○(n2)（3）在一个长度为n的线性表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动（）个元素，删除第i（1≤i≤n）个元素时，需向前移动（）个元素。

A．n-i B．n-i+1 C．n-i D．n-i+1（4）线性表的顺序存储结构是一种（）的存储结构。

A．随机存取B．顺序存取C．索引存取D．散列存取（5）顺序存储结构的优点是（）。

A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示（6）n个结点的线性表采用数组实现，算法的时间复杂度是○(1)的操作是（）。

A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．以上都不对（7）对于顺序存储的线性表，访问某个元素和增加一个元素的时间复杂度为（）。

A．○(n)、○(n) B．○(n)、○(1) C．○(1)、○(n) D．○(1)、○(1)（8）顺序表的插入算法中，当n个空间已满时，可再申请增加分配m个空间，若申请失败，则说明系统没有（）可分配的存储空间。

A．m个B．m个连续的C．n+m个D．n+m个连续的应用题（9）设A是一个线性表（a1，a2，…，a n），采用顺序存储结构，则在等概论的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在a i与a i+1之间(1≤i≤n)的概率为（n-i）/（n（n-1）/2），则平均每插入一个元素所移动的元素个数是多少？（10）设n表示线性表中的元素个数，E表示存储数据元素所需要的存储单元大小，D表示可以在数组中存储线性表的最大元素个数（D≥n），则使用顺序存储方式存储线性表需要多少存储空间？（11）在什么情况下线性表使用顺序存储比较好？算法设计题（12）试以顺序表作存储结构，实现线性表就地逆置。