内容发布更新时间 : 2024/11/8 3:08:57星期一 下面是文章的全部内容请认真阅读。
数据结构的基本概念
选择题
（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．数据结构由逻辑结构、存储结构和基本操作三方面组成
1
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） 抽象数据类型的主要特点是什么？数据类型和抽象数据类型的关系如何？使
用抽象数据类型的主要好处是什么？
2
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．问题规模是n2 B．执行时间等于n2 C．执行时间与n2成正比 D．问题规模与n2成正比
（10） 下面说法错误的是（ ）。
3
①算法原地工作的含义是指示不需要如何额外的辅助空间
②在相同的规模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为正整数，则最后一行语句的频度（执行次数）在最坏情况下是（ ）。
32
A．○(n) B．○(nlog2n) C．○(n) D．○(n)
（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．n2 B．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; else i++;
while (i while (i+j<=n) { if (i>j) j++; k=k+10*i; 4 i++; } while (i<=n) ⑥ for (i=0;i while ((y+1)*(y+1)<=n) a[i][j]=0; y=y+1 （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） 斐波那契数列Fn定义如下： F0=0，F1=1，?，Fn=Fn-1+Fn-2 n=2，3，? 请就此斐波那契数列，回答下列问题。 ① 在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，?，F1，F0精确计算多少次？ ② 用大○表示法给出递归计算时递归函数的时间复杂度是多少？ （21） 运算是数据结构的一个重要方面。举例说明两个数据结构的逻辑结构和存储方 式完全相同，只是对于运算的定义不同，因而具有不同的特性，则这两个数据结构是不同的。 （22） 针对给定的实际问题建立数据结构时，应从哪些方面考虑。 5