数据结构期末考试(题集).doc
41页
数据结构得基本概念选择题（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．问题规模就是n2 B．执行时间等于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．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;while (i 综合应用题（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） 针对给定得实际问题建立数据结构时，应从哪些方面考虑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。
