【MOOC】《数据结构》(华中科技大学)章节作业慕课答案

【答案】《数据结构》(华中科技大学)章节作业慕课答案

有些题目顺序不一致，下载后按键盘ctrl+F进行搜索第一章绪论第一章绪论单元测试1.单选题：下面程序的时间复杂度为_______。voidfun(intn){inti=1,k=100;while(i＜=n){k++;i+=2;}}

选项：

A、O(n)

B、O()

C、O(log2n)

D、O(nlog2n)

答案：【O(n)】2.单选题：以下函数中时间复杂度最小的是_______。

选项：

A、T1(n)=nlog2n+5000n

B、T2(n)=-8000n

C、T3(n)=-6000n

D、T4(n)=20000log2n

答案：【T4(n)=20000log2n】3.单选题：算法分析的目的是_______。

选项：

A、找出数据结构的合理性

B、研究算法中输入和输出的关系

C、分析算法的效率以求改进

D、分析算法的易读性和文档性

答案：【分析算法的效率以求改进】4.单选题：算法的时间复杂度为O(n2)，表明该算法的_______。

选项：

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.单选题：下面程序的时间复杂度为_______。voidfun(intn){inti=1;while(i＜=n)i=i*3}

选项：

A、O(n)

B、O()

C、O(nlog3n)

D、O(log3n)

答案：【O(log3n)】11.单选题：下面程序的时间复杂度为_______。voidfun(intn){inti=1;while(i＜=n)i=i*2}

选项：

A、O(n)

B、O()

C、O(log2n)

D、O(nlog2n)

答案：【O(log2n)】12.单选题：取算法的时间复杂度为O（），当n=5时执行时间为50s，当n=15时，执行时间为_______。

选项：

A、3375

B、1350

C、2025

D、675

答案：【1350】13.单选题：一个算法的时间复杂度为(+log2n+14n)/，其数量级表示为_______。

选项：

A、O(n)

B、O()

C、O()

D、O()

答案：【O(n)】14.单选题：下面程序的时间复杂为_______。for（i=1，s=0；i＜=n；i++）{t=1；for(j=1；j＜=i；j++)t=t*j；s=s+t；}

选项：

A、O(n)

B、O()

C、O()

D、O()

答案：【O()】15.单选题：以下数据结构中哪一个是非线性结构？

选项：

A、队列

B、栈

C、线性表

D、二叉树

答案：【二叉树】16.单选题：以下说法中错误的是_______。（1）原地工作算法的含义是指不需要任何额外的辅助空间（2）在相同的问题规模下n下，时间复杂度为O(nlog2n)的算法在执行时间上总是优于时间复杂度为O()的算法（3）时间复杂度通常是指最坏情况下，估计算法执行时间的一个上限（4）一个算法的时间复杂度与实现算法的语言无关

选项：

A、（1）

B、（1）、（2）

C、（1）、（4）

D、（3）

答案：【（1）、（2）】17.单选题：以下函数中时间复杂度最小的是_______。

选项：

A、T1(n)=1000log2n

B、T2(n)=-1000log2n

C、T3(n)=-1000log2n

D、T4(n)=2nlog2n-1000log2n

答案：【T1(n)=1000log2n】18.单选题：以下不属于存储结构是______。

选项：

A、顺序表

B、单链表

C、邻接表

D、线性表

答案：【线性表】19.单选题：以下属于逻辑结构是______。

选项：

A、顺序表

B、有序表

C、双链表

D、单链表

答案：【有序表】20.单选题：以下是数据结构中______属非线性结构。

选项：

A、栈

B、串

C、队列

D、平衡二叉树

答案：【平衡二叉树】21.单选题：数据的逻辑结构是指______关系的整体。

选项：

A、数据元素之间逻辑

B、数据项之间逻辑

C、数据类型之间

D、存储结构之间

答案：【数据元素之间逻辑】22.单选题：数据的逻辑结构可以分为______两类。

选项：

A、紧凑结构和非紧凑结构

B、动态结构和静态结构

C、内部结构和外部结构

D、线性结构和非线性结构

答案：【线性结构和非线性结构】23.单选题：在数据结构中，与所使用的计算机无关的是数据的______结构。

选项：

A、物理

B、逻辑和存储

C、存储

D、逻辑

答案：【逻辑】24.单选题：计算机所处理的数据一般具备某种内在联系，这是指______。

选项：

A、元素内部具有某种结构

B、数据项和数据项之间存在某种关系

C、元素和元素之间存在某种关系

D、数据和数据之间存在某种关系

答案：【元素和元素之间存在某种关系】25.单选题：数据结构是指______的集合以及它们之间的关系。

选项：

A、计算方法

B、数据元素

C、结构

D、数据

答案：【数据元素】26.单选题：_______不是算法的基本特性。

选项：

A、可行性

B、指令序列长度有限

C、在规定的时间内完成

D、确定性

答案：【在规定的时间内完成】27.单选题：数据的运算______。

选项：

A、是根据存储结构来定义的效率

B、与采用何种存储结构有关

C、有算术运算和关系运算两大类

D、必须用程序设计语言来描述

答案：【与采用何种存储结构有关】28.单选题：数据采用链式存储结构时，要求______。

选项：

A、每个节点占用一片连续的存储区域

B、所有节点占用一片连续的存储区域

C、节点的最后一个数据域是指针类型

D、每个节点有多少个后继就设多少个指针域

答案：【每个节点占用一片连续的存储区域】29.单选题：数据在计算机的存储器中表示时，逻辑上相邻的两个元素对应的物理地址也是相邻的，这种存储结构称之为______。

选项：

A、路基结构

B、顺序存储结构

C、链式存储结构

D、以上都对

答案：【顺序存储结构】30.单选题：在决定选取任何类型的存储结构时，一般不多考虑______。

选项：

A、各节点的值如何

B、节点个数的多少

C、对数据有哪些运算

D、所用编程语言实现这种结构是否方便

答案：【各节点的值如何】31.单选题：在数据的存储中，一个节点通常存储一个______。

选项：

A、数据结构

B、数据类型

C、数据元素

D、数据项

答案：【数据元素】32.单选题：数据结构在计算机内存中的表示是指______。

选项：

A、数据的存储结构

B、数据结构

C、数据的逻辑结构

D、数据元素之间的关系

答案：【数据的存储结构】33.单选题：在计算机中存储数据时，通常不仅要存储各数据元素的值，而且还有存储______。

选项：

A、数据的处理方法

B、数据元素的类型

C、数据元素之间的关系

D、数据的存储方法

答案：【数据元素之间的关系】34.单选题：以下说法不正确的是______。

选项：

A、数据可由若干个数据元素构成

B、数据项可由若干个数据元素构成

C、数据元素是数据的基本单位

D、数据项是不可分割的最小标识单位

答案：【数据项可由若干个数据元素构成】35.单选题：______是数据的最小单位。

选项：

A、数据项

B、数据元素

C、信息项

D、表元素

答案：【数据项】36.单选题：逻辑结构不相同的数据，必须采用多种不同的存储方法。

选项：

A、正确

B、错误

答案：【错误】37.单选题：逻辑结构相同的数据，可以采用多种不同的存储方法。

选项：

A、正确

B、错误

答案：【正确】38.单选题：如果数据元素值发生改变，则数据的逻辑结构也随之改变。

选项：

A、正确

B、错误

答案：【错误】39.单选题：数据的逻辑结构与数据元素在计算机中如何存储有关。

选项：

A、正确

B、错误

答案：【错误】40.单选题：任何数据结构都具备3个基本运算：插入、删除、和查找。

选项：

A、正确

B、错误

答案：【错误】41.单选题：数据对象就是一组任意数据元素的集合。

选项：

A、正确

B、错误

答案：【错误】42.单选题：数据元素是数据的最小单位。

选项：

A、正确

B、错误

答案：【错误】43.单选题：健壮的算法不会因非法输入数据而出现莫名其妙的状态。

选项：

A、正确

B、错误

答案：【正确】44.单选题：算法的可行性是指指令不能有二义性。

选项：

A、正确

B、错误

答案：【错误】45.单选题：算法最终必须由计算机程序实现.

选项：

A、正确

B、错误

答案：【错误】46.单选题：程序一定是算法。

选项：

A、正确

B、错误

答案：【错误】47.单选题：算法可以用不同的语言描述，如果用C或PASCAL语言等高级语言来描述，则算法实际上就是程序了。

选项：

A、正确

B、错误

答案：【错误】48.单选题：算法的优劣与算法描述语言无关，但与所用的计算机有关。

选项：

A、正确

B、错误

答案：【错误】49.单选题：数据的逻辑结构时指数据的各数据项之间的逻辑关系。

选项：

A、正确

B、错误

答案：【错误】50.单选题：逻辑结构相同的数据，在设计存储结构时，它们的节点类型也一定相同。

选项：

A、正确

B、错误

答案：【错误】第二章线性表第二章线性表单元测试1.单选题：求一个单链表长度的算法的时间复杂度为_______。

选项：

A、O(log2n)

B、O(n)

C、O(1)

D、O()

答案：【O(n)】2.单选题：在单链表中，要删除某一指定的节点，必须找到该节点的_______节点。

选项：

A、后继

B、头节点

C、前驱

D、尾节点

答案：【前驱】3.单选题：对于双链表，在两个节点之间插入一个新节点是，需要修改_______个指针域。

选项：

A、1

B、2

C、3

D、4

答案：【4】4.单选题：下面关于线性表的叙述错误的是_______。

选项：

A、线性表采用顺序存储必须占用一片连续的存储空间

B、线性表采用链式存储不必占用一片连续的存储空间

C、线性表采用链式存储便于插入和删除操作的实现

D、线性表采用顺序存储便于插入和删除操作的实现

答案：【线性表采用顺序存储便于插入和删除操作的实现】5.单选题：在长度为n的_______上，删除第一个元素，其算法的时间复杂度为O(n)。

选项：

A、只有表头指针的不带表头节点的循环单链表

B、只有表尾指针的不带表头节点的循环单链表

C、只有表尾指针的带表头节点的循环单链表

D、只有表头指针的带表头节点的循环单链表

答案：【只有表头指针的不带表头节点的循环单链表】6.单选题：两个表长都为n、不带表头结点的单链表，结点类型都相同，头指针分别为h1与h2，且前者是循环链表，后者是非循环链表，则_______。

选项：

A、对于两个链表来说，删除首节点的操作，其时间复杂度都是O(1)

B、对于两个链表来说，删除尾节点的操作，其时间复杂度都是O(n)

C、循环链表要比非循环链表占用更多的内存空间

D、h1和h2是不同类型的变量

答案：【对于两个链表来说，删除尾节点的操作，其时间复杂度都是O(n)】7.单选题：在某线性表最常用的操作是在尾元素之后插入一个元素和删除第一个元素。故采用_______存储方式最节省时间。

选项：

A、单链表

B、仅有头节点指针的循环单链表

C、双链表

D、仅有尾指针的循环单链表

答案：【仅有尾指针的循环单链表】8.单选题：如果对含有n（n>1）个元素的线性表的运算只有4种，即删除第一个元素、删除尾元素、在第一个元素前面插入新元素、在尾元素的后面插入新元素，则最好使用_______。

选项：

A、只有尾节点指针没有头节点的循环单链表

B、只有尾节点指针没有头节点的非循环双链表

C、只有开始数据节点指针没有尾节点指针的循环双链表

D、既有表头指针也有表尾指针的循环单链表

答案：【只有开始数据节点指针没有尾节点指针的循环双链表】9.单选题：已知一个长度为n的单链表中所有节点是递增有序的，以下叙述中正确的是_______。

选项：

A、插入一个节点使之有序的算法的时间复杂度为O(1)

B、删除最大值节点使之有序的算法的时间复杂度为O(1)

C、找最小值节点的算法的时间复杂度为O(1)

D、以上都不对

答案：【找最小值节点的算法的时间复杂度为O(1)】10.单选题：将长度为m的单链表链接在长度为n的单链表之后的算法时间复杂度为_______。

选项：

A、O(1)

B、O(n)

C、O(m)

D、O(m+n)

答案：【O(n)】11.单选题：在一个具有n个节点的有序单链表中插入一个新节点并仍然保持有序的时间复杂度是_______。

选项：

A、O(nlog2n)

B、O(1)

C、O(n)

D、O()

答案：【O(n)】12.单选题：在单链表中，增加一个头节点的目的是为了_______。

选项：

A、使单链表至少有一个节点

B、标识链表中重要节点的位置

C、方便运算的实现

D、说明单链表是线性表的链式存储结构

答案：【方便运算的实现】13.单选题：以下关于单链表的叙述中，不正确的是_______。

选项：

A、节点除自身信息外还包括指针域，因此存储密度小于顺序存储结构

B、逻辑上相邻的元素物理上不必相邻

C、可以通过头节点直接计算第i个节点的存储地址

D、插入、删除运算操作简单，不必移动节点

答案：【可以通过头节点直接计算第i个节点的存储地址】14.单选题：在单链表中查找指定值的节点的时间复杂度是_______。

选项：

A、O(log2n)

B、O(1)

C、O()

D、O(n)

答案：【O(n)】15.单选题：对于一个具有n个元素的线性表，建立其单链表的时间复杂度为_______。

选项：

A、O(log2n)

B、O(1)

C、O(n)

D、O()

答案：【O(n)】16.单选题：在带头节点的单链表L为空的判定条件是_______。

选项：

A、L==NULL

B、L->NEXT==NULL

C、L->NEXT==L

D、L!=NULL

答案：【L->NEXT==NULL】17.单选题：某线性表最常用的操作是在尾元素之后插入一个元素和删除尾元素，则采用_______存储方式最节省运算时间。

选项：

A、单链表

B、循环单链表

C、双链表

D、循环双链表

答案：【循环双链表】18.单选题：带表头结点的双循环链表L为空表的条件是_______。

选项：

A、L==NULL

B、L->next->prior==NULL

C、L->prior==NULL

D、L->next==L

答案：【L->next==L】19.单选题：非空的循环单链表L的尾节点（由p所指向）满足_______。

选项：

A、p->next==NULL

B、p==NULL

C、p->next==L

D、p==L

答案：【p->next==L】20.单选题：在一个双链表中，删除*p节点之后的一个节点，其时间复杂度为_______。

选项：

A、O(nlog2n)

B、O(1)

C、O(n)

D、O()

答案：【O(1)】21.单选题：在一个双链表中，删除*p节点的操作是_______。

选项：

A、p->prior–>next=p->next；p->next->prior=p->prior；

B、p->prior=p->prior->prior；p->prior->prior=p；

C、p->next->prior=p；p->next=p->next->next；

D、p->next=p->prior->prior；p->prior=p->prior->prior；

答案：【p->prior–>next=p->next；p->next->prior=p->prior；】22.单选题：在一个双链表中，在*p节点之前插入节点*q的操作是_______。

选项：

A、p->prior=q；q->next=p；p->prior->next=q；q->prior=p->prior；

B、q->prior=p->prior；p->prior->next=q；q->next=p；p->prior=q->next；

C、q->next=p；p->next=q；q->prior->next=q；q->next=p；

D、p->prior->next=q；q->next=p；q->prior=p->prior；p->prior=q；

答案：【p->prior->next=q；q->next=p；q->prior=p->prior；p->prior=q；】23.单选题：在一个双链表中，在*p节点之后插入节点*q的操作是_______。

选项：

A、q->prior=p；p->next=q；p->next->prior=q；q->next=p->next；

B、q->next=p->next；p->next->prior=q；p->next=q；q->prior=p；

C、p->next=q；q->prior=p；q->next=p->next；p->next->prior=q；

D、p->next->prior=q；q->prior=p；p->next=q；q->next=p->next；

答案：【q->next=p->next；p->next->prior=q；p->next=q；q->prior=p；】24.单选题：在一个长度为n（n>1）的带头节点的单链表上，另设有尾指针r（指向尾节点），执行_______操作与链表的长度有关。

选项：

A、删除单链表中的第一个元素

B、删除单链表的尾节点

C、在单链表中第一个元素前插入一个新节点

D、在单链表最后一个元素后插入一个新节点

答案：【删除单链表的尾节点】25.单选题：设线性表中有n个元素，以下操作，_______在单链表上实现要比在顺序表上实现效率高。

选项：

A、删除指定位置元素的后一个元素

B、在第n个元素的后面插入一个新元素

C、顺序输出前k个元素

D、交换第i个元素和第n-i+1个元素的值

答案：【删除指定位置元素的后一个元素】26.单选题：对于一个线性表，既要求能够较快地进行插入和删除操作，又要求存储结构能够反映数据元素之间的逻辑关系，则应采用_______存储结构。

选项：

A、顺序

B、链式

C、散列

D、索引

答案：【链式】27.单选题：设线性表有n个元素，以下操作中，_______在顺序表上实现比在链表上实现效率高。

选项：

A、输入第i（1＜=i＜=n）个元素值

B、交换第1个元素第2个元素的值

C、顺序输出这n个元素的值

D、输出与给定值x相等的元素在线性表中的符号

答案：【输入第i（1＜=i＜=n）个元素值】28.单选题：线性表的顺序存储结构和链式存储结构相比，优点是_______。

选项：

A、所有的操作算法实现简单

B、便于随机存取

C、便于插入和删除

D、节省存储空间

答案：【便于随机存取】29.单选题：线性表的静态链表存储结构与顺序存储结构相比，优点是_______。

选项：

A、所有的操作算法实现简单

B、便于随机存取

C、便于插入和删除

D、便于利用零散的存储器空间

答案：【便于插入和删除】30.单选题：链表不具备的特点是_______。

选项：

A、可随机访问任一节点

B、插入删除不需要移动元素

C、不必事先估计存储空间

D、所需空间与其长度成正比

答案：【可随机访问任一节点】31.单选题：线性表采用链表存储时，其存放各个元素的单元地址是_______。

选项：

A、必须是连续的

B、一定是不连续的

C、部分地址必须是连续的

D、连续与否均可以

答案：【连续与否均可以】32.单选题：关于线性表的正确说法是_______。

选项：

A、每个元素都有一个前驱和一个后继元素

B、线性表中至少有一个元素

C、表中元素的排序顺序必须是由小到大或由大到小

D、除第一个元素和最后一个元素外，其余元素有且仅有一个前驱和一个后继元素

答案：【除第一个元素和最后一个元素外，其余元素有且仅有一个前驱和一个后继元素】33.单选题：将两个长度为n、m的递增有序表归并成一个有序顺序表，其最少的比较次数是_______。（MIN表示取最小值）

选项：

A、n

B、m

C、MIN(m,n)

D、不确定

答案：【MIN(m,n)】34.单选题：在两个各有n个元素的递增有序顺序表归并成一个有序顺序表，其最少的比较次数为_______。

选项：

A、n

B、2n-1

C、2n

D、n-1

答案：【n】35.单选题：在长度为n的顺序表中删除一个元素的时间复杂度为_______。

选项：

A、O(1)

B、O()

C、O(log2n)

D、O(n)

答案：【O(n)】36.单选题：在长度为n的顺序表中插入一个元素的时间复杂度为_______。

选项：

A、O(n)

B、O()

C、O(log2n)

D、O(1)

答案：【O(n)】37.单选题：与单链表相比，双链表的优点之一是_______。

选项：

A、插入、删除操作更简单

B、可以进行随机访问

C、可以省略表头指针或表尾指针

D、访问前后相邻节点更方便

答案：【访问前后相邻节点更方便】38.单选题：如果最常用的操作时取第i个元素及前驱元素，则采用_______存储方式最节省时间。

选项：

A、单链表

B、双链表

C、循环单链表

D、顺序表

答案：【顺序表】39.单选题：要求线性表采用静态空间分配方式，且插入和删除操作时不需要移动元素，采用的存储结构是_______。

选项：

A、单链表

B、静态链表

C、双链表

D、顺序表

答案：【静态链表】40.单选题：以下属于顺序表的优点是_______。

选项：

A、插入元素方便

B、删除元素方便

C、存储密度大

D、以上都不对

答案：【存储密度大】41.单选题：线性表是_______。

选项：

A、一个有限序列，可以为空

B、一个有限序列不可以为空

C、一个无限序列，可以为空

D、一个无限序列，不可以为空

答案：【一个有限序列，可以为空】42.单选题：线性表是具有n个______的有限序列。

选项：

A、表元素

B、字符

C、数据元素

D、数据项

答案：【数据元素】43.单选题：在双链表中，可以从任一节点开始沿着同一方向查找到任何其他节点。

选项：

A、正确

B、错误

答案：【错误】44.单选题：在单链表中，可以从头节点开始查找任何一个节点。

选项：

A、正确

B、错误

答案：【正确】45.单选题：在循环单链表中，从表中任一节点出发都可以通过前后移动操作遍历整个循环链表。

选项：

A、正确

B、错误

答案：【错误】46.单选题：线性表的顺序存储结构优于链式存储结构。

选项：

A、正确

B、错误

答案：【错误】47.单选题：静态链表与动态链表在元素的插入、删除方面类似，不需要做元素的移动。

选项：

A、正确

B、错误

答案：【正确】48.单选题：静态链表既有顺序存储结构的优点，又有动态链表的优点，所以，利用它存取第i个元素的时间与元素个数n无关。

选项：

A、正确

B、错误

答案：【错误】49.单选题：线性表中所有元素的排列顺序必须从小到大或从大到小。

选项：

A、正确

B、错误

答案：【错误】50.单选题：线性表中每个元素都有一个前驱元素和一个后继元素。

选项：

A、正确

B、错误

答案：【错误】第三章栈和队列第三章栈和队列单元测试1.单选题：最适合用做链队列的不带表头节点的链表是_______。

选项：

A、带首节点指针和尾节点指针的循环单链表

B、只带尾节点指针的非循环单链表

C、只带首节点指针的非循环单链表

D、只带尾节点指针的循环单链表

答案：【只带尾节点指针的循环单链表】2.单选题：设循环队列中数组的下标是0~N-1，其队头、队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），则元素个数为_______。

选项：

A、r-f

B、r-f-1

C、(r-f)%N+1

D、(r-f+N)%N

答案：【(r-f+N)%N】3.单选题：循环队列qu的队满条件（front队首指针指向队首元素的前一位置，rear队尾指针指向队尾元素）是_______。

选项：

A、(qu.rear+1)%maxsize==(qu.front+1)%maxsize

B、(qu.rear+1)%maxsize==qu.front+1

C、(qu.rear+1)%maxsize==qu.front

D、qu.rear==qu.front

答案：【(qu.rear+1)%maxsize==qu.front】4.单选题：若某循环队列有队首指针front和队尾指针rear，在队不满时进队操作仅会改变_______。

选项：

A、front

B、rear

C、front和rear

D、以上都不对

答案：【rear】5.单选题：经过下列运算后，队头的元素是_______。InitQueue(qu);Enqueue(qu,‘a’);EnQueue(qu,‘b’);EnQueue(qu,‘c’);DeQueue(qu);

选项：

A、a

B、b

C、1

D、0

答案：【b】6.单选题：栈和队列的不同点是_______。

选项：

A、都是线性表

B、都不是线性表

C、栈只能在一端进行插入删除操作，而队列在不同端进行插入删除操作

D、没有不同点

答案：【栈只能在一端进行插入删除操作，而队列在不同端进行插入删除操作】7.单选题：从一个不带头节点的栈顶指针为lst的栈链中删除一个节点时，用x保存被删节点的值，则执行_______。

选项：

A、x=lst;lst=lst->next;

B、x=lst->data

C、lst=lst->next;x=lst->data;

D、x=lst->data;lst=lst->next;

答案：【x=lst->data;lst=lst->next;】8.单选题：向一个不带头节点的栈顶指针为lst的链栈中插入一个s所指向节点时，则执行_______。

选项：

A、lst->next=s;

B、s->next=lst->next;lst->next=s;

C、s->next=lst;lst=s;

D、s->next=lst;lst->next=s;

答案：【s->next=lst;lst=s;】9.单选题：若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别是0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是_______。

选项：

A、1和5

B、2和4

C、4和2

D、5和1

答案：【2和4】10.单选题：假设用qu[0..M]实现循环队列，f、r分别为队首元素的前一个位置和队尾位置。若用“(r+1)%(M+1)==f”作为队满的标志，则_______。

选项：

A、可用“f==r”作为队空的标志

B、可用“f>r”作为队空的标志

C、可用“(f+1)%(M+1)==r”作为队空的标志

D、队列中最多可以有M+1个元素

答案：【可用“f==r”作为队空的标志】11.单选题：最不合适用做链队的不带头节点的链表是_______。

选项：

A、只带队首节点指针的非循环单链表

B、只带队首节点指针的循环双链表

C、只带队尾节点指针的循环双链表

D、以上都不合适

答案：【只带队首节点指针的非循环单链表】12.单选题：假设用一个不带头节点的单链表表示队列，队头和队尾指针分别为front和rear，则判断队空的条件是_______。

选项：

A、front==rear

B、front!==NULL

C、rear!==NULL

D、front==NULL

答案：【front==NULL】13.单选题：假设用一个不带表头节点的单链表表示队列，在进行删除操作时，_______。

选项：

A、仅修改头指针

B、仅修改尾指针

C、头、尾指针都要修改

D、头、尾指针可能都要修改

答案：【头、尾指针可能都要修改】14.单选题：判定一个顺序栈st为（元素个数最多为MaxSize）为栈满的条件为_______。

选项：

A、st.top！==-1

B、st.top=-1

C、st.top!=MaxSize-1

D、st.top==MaxSize-1

答案：【st.top==MaxSize-1】15.单选题：判定一个顺序栈st为（元素个数最多为MaxSize）空的条件为_______。

选项：

A、st.top==-1

B、st.top!=-1

C、st.top!=MaxSize

D、st.top==MaxSize

答案：【st.top==-1】16.单选题：在数据处理过程中常需要保存一些中间数据，如果后保存的数据先处理，则使用_______来保存这些数据。

选项：

A、线性表

B、栈

C、队列

D、单链表

答案：【栈】17.单选题：设有5个元素的进栈序列是a，b，c，d，e，其输出序列是c，e，d，b，a，则该栈的容量至少是_______。

选项：

A、1

B、2

C、3

D、4

答案：【4】18.单选题：设n个元素的进栈序列是p1,p2,…pn，其输出序列是1,2,3，…n，若p3=3，则p1的值是_______。

选项：

A、可能是2

B、一定是2

C、不可能是1

D、一定是1

答案：【可能是2】19.单选题：设n个元素的进栈序列是p1,p2,…pn，其输出序列是1,2,3，…n，若p3=1，则p1的值是_______。

选项：

A、可能是2

B、一定是2

C、不可能是2

D、不可能是3

答案：【不可能是2】20.单选题：设n个元素的进栈序列是1,2,3，…n，其输出序列是p1,p2,…pn，若p1=3，则p2的值是_______。

选项：

A、一定是2

B、一定是1

C、不可能是1

D、以上都不对

答案：【不可能是1】21.单选题：设n个元素的进栈序列是p1,p2,…pn，其输出序列是1,2,3，…n，若pn=1，则pi（1≤i≤n-1）的值是_______。

选项：

A、n-i+1

B、n-i

C、i

D、不确定

答案：【n-i+1】22.单选题：如果以链表作为栈的存储结构，则退栈操作时_______。

选项：

A、必须判断链栈是否为满

B、判断链栈元素的类型

C、必须判断链栈是否空

D、对链栈不做任何判断

答案：【必须判断链栈是否空】23.单选题：以下各链表均不带有头节点，其中最不合适用作链栈的链表是_______。

选项：

A、只有表头指针没有表尾指针的循环双链表

B、只有表尾指针没有表头指针的循环双链表

C、只有表尾指针没有表头指针的循环单链表

D、只有表头指针没有表尾指针的循环单链表

答案：【只有表头指针没有表尾指针的循环单链表】24.单选题：链栈与顺序栈相比有一个明显的优点，即_______。

选项：

A、插入操作更方便

B、通常不会出现栈满的情况

C、总是不会出现栈空的情况

D、删除操作更加方便

答案：【通常不会出现栈满的情况】25.单选题：若一个栈用数组data[1..n]存储，初始栈顶指针top为1，则以下元素x进入栈的正确操作是_______。

选项：

A、top++;data[top]=x;

B、data[top]=x;top++;

C、top--;data[top]=x;

D、data[top]=x;top--;

答案：【data[top]=x;top++;】26.单选题：若一个栈用数组data[1..n]存储，初始栈顶指针top为0，则以下元素x进入栈的正确操作是_______。

选项：

A、top++;data[top]=x;

B、data[top]=x;top++;

C、top--;data[top]=x;

D、data[top]=x;top--;

答案：【top++;data[top]=x;】27.单选题：若一个栈用数组data[1..n]存储，初始栈顶指针top为n，则以下元素x进入栈的正确操作是_______。

选项：

A、top++;data[top]=x;

B、data[top]=x;top++;

C、top--;data[top]=x;

D、data[top]=x;top--;

答案：【data[top]=x;top--;】28.单选题：若一个栈用数组data[1..n]存储，初始栈顶指针top为n+1，则以下元素x进入栈的正确操作是_______。

选项：

A、top++;data[top]=x;

B、data[top]=x;top++;

C、top--;data[top]=x;

D、data[top]=x;top--;

答案：【top--;data[top]=x;】29.单选题：表达式a*(b+c)-d的后缀表达式是_______。

选项：

A、abcd*+-

B、abc+*d-

C、abc*+d-

D、-+*abcd

答案：【abc+*d-】30.单选题：元素A、B、C、D依次进栈后，栈顶元素是_______。

选项：

A、A

B、B

C、C

D、D

答案：【D】31.单选题：已知一个栈的进栈序列是1,2,3，…n，其输出序列是p1,p2,…pn，若p1=n,则pi的值是_______。

选项：

A、i

B、n-i

C、n-i+1

D、不确定

答案：【n-i+1】32.单选题：已知一个栈的进栈序列是1，2，3，…n，其输出序列的第一个元素是i（1≤i≤n），则第j（1≤j≤n）个出栈元素是_______。

选项：

A、i

B、n-i

C、j-i+1

D、不确定

答案：【不确定】33.单选题：一个栈的进栈序列是abcde，则栈的不可能的输出序列是_______。

选项：

A、edcba

B、decba

C、dceab

D、abcde

答案：【dceab】34.单选题：设一个栈的输入序列为A、B、C、D，则借助一个栈所得的输出序列不可能是_______。

选项：

A、ABCD

B、DCBA

C、ACDB

D、DABC

答案：【DABC】35.单选题：若元素a、b、c、d、e、f依次进栈，允许进栈、退栈的操作交替进行，但不允许连续3次退栈工作，则不可能得到的出栈序列是_______。

选项：

A、dcebfa

B、cbdaef

C、bcaefd

D、afedcb

答案：【afedcb】36.单选题：已知一个栈的进栈序列是ABC，出栈序列为CBA，经过栈的操作是_______。

选项：

A、push,pop,push,pop,push,pop

B、push,push,push,pop,pop,pop

C、push,push,pop,pop,push,pop

D、push,pop,push,push,pop,pop

答案：【push,push,push,pop,pop,pop】37.单选题：经过以下栈运算后，StackEmpty(s)的值是_______。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y)

选项：

A、a

B、b

C、1

D、0

答案：【1】38.单选题：经过以下运算后，x的值是_______。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s,x)

选项：

A、a

B、b

C、1

D、0

答案：【a】39.单选题：队列是一种对进队、出队操作的次序做了限制的线性表。

选项：

A、正确

B、错误

答案：【错误】40.单选题：栈和队列都是限制存取端的。

选项：

A、正确

B、错误

答案：【正确】41.单选题：空栈没有栈顶指针。

选项：

A、正确

B、错误

答案：【错误】42.单选题：对顺序栈进行进栈、出栈操作，不涉及元素的前、后移动问题。

选项：

A、正确

B、错误

答案：【正确】43.单选题：栈是一种对进栈、出栈操作的次序做了限制的线性表。

选项：

A、正确

B、错误

答案：【错误】44.单选题：栈是一种对进栈、出栈操作总次数做了限制的线性表。

选项：

A、正确

B、错误

答案：【错误】45.单选题：若用s[0..m-1]表示顺序栈的存储空间，则对栈的进栈、出栈操作最多只能进行m次；

选项：

A、正确

B、错误

答案：【错误】46.单选题：栈顶元素和栈底有可能是同一元素。

选项：

A、正确

B、错误

答案：【正确】47.单选题：若用“队首指针的值和队尾指针的值相等”作为循环顺序队为空的标识，则在设置一个空队列时，只需给队首指针和队尾指针赋同一个值，在顺序表地址范围内不管什么值都可以。

选项：

A、正确

B、错误

答案：【正确】48.单选题：n个元素依次进栈，它们的出栈顺序和进栈顺序一定正好相反。

选项：

A、正确

B、错误

答案：【错误】49.单选题：顺序栈中元素值的大小是有序的。

选项：

A、正确

B、错误

答案：【错误】50.单选题：栈底元素是不能删除的元素。

选项：

A、正确

B、错误

答案：【错误】第五章数组与广义表第五章数组与广义表单元测试1.单选题：对广义表G=((a,((),b)),(((),(c,d)),()))执行tail(head(head(tail(G))))操作的结果是_________。

选项：

A、()

B、c

C、(c,d)

D、((c,d))

答案：【((c,d))】2.单选题：广义表((a,b),(c),(d))的表尾是______。

选项：

A、(d)

B、d

C、(a,b)

D、((c),(d))

答案：【((c),(d))】3.单选题：广义表((a,b),(c),(d))的表头是______。

选项：

A、a,b

B、(a,b)

C、a

D、()

答案：【(a,b)】4.单选题：广义表((a,()),(b,(c)),(()))的深度是______。

选项：

A、3

B、4

C、5

D、6

答案：【3】5.单选题：广义表(a,(b,c),d)的表长是______。

选项：

A、3

B、4

C、5

D、6

答案：【3】6.单选题：表头和表尾均为空义表的广义表是__________。

选项：

A、()

B、((),())

C、(())

D、((()))

答案：【(())】7.单选题：使用三元组顺序表作为稀疏矩阵中的物理结构，要求对三元组按行序优先的顺序进行存放，原因是按行序优先能__________。

选项：

A、节省存储空间

B、方便稀疏矩阵的运算

C、提高元素的访问速度

D、使元素的摆放形式漂亮一些

答案：【方便稀疏矩阵的运算】8.单选题：使用三元组顺序表或十字链表作为稀疏矩阵中的物理结构，对元素的访问形式只能是__________。

选项：

A、随机访问

B、哈希访问

C、顺序访问

D、索引访问

答案：【顺序访问】9.单选题：下列叙述中，不正确的是______。

选项：

A、对称矩阵只需要存放包括对角线元素在内的下（或上）三角元素即可

B、对角矩阵只需要存放其值不一定为0的对角线上元素

C、稀疏矩阵中值为0的元素较多，因此可以采用三元组方法存储非零元素

D、稀疏矩阵中大量值为0的元素分布有规律，因此可以采用三元组表方法存储

答案：【稀疏矩阵中大量值为0的元素分布有规律，因此可以采用三元组表方法存储】10.单选题：对n*n的对称矩阵进行压缩存储，需要保存的数据元素的个数是_________。

选项：

A、n

B、

C、n(n+1)

D、n(n+1)/2

答案：【n(n+1)/2】11.单选题：对特殊矩阵采用压缩存储的目的主要是_________。

选项：

A、表达变得简单

B、对矩阵元素的存储变得简单

C、去掉矩阵中的多余元素

D、减少不必要的存储空间

答案：【减少不必要的存储空间】12.单选题：不能够对数据元素进行随机访问的物理结构是_________。

选项：

A、数组的顺序存储

B、对称矩阵的压缩存储

C、三元组顺序表

D、三对角矩阵的压缩存储

答案：【三元组顺序表】13.单选题：设有一个10行10列的矩阵A，采用行序优先存储方式。如果A[0][0]为第一个元素，其存储地址为1000，A[2][3]的存储地址为1069，则存储一个元素需要的单元数是_________。

选项：

A、1

B、2

C、3

D、4

答案：【3】14.单选题：设有一个10行10列的矩阵A，采用行序优先存储方式，存储全部数据需要400个字节的空间。如果A[0][0]为第一个元素，其存储地址为1000，则A[3][6]的地址为_________。

选项：

A、1014

B、1144

C、1036

D、1056

答案：【1144】15.单选题：设有一个5行4列的矩阵A，采用行序优先存储方式，A[0][0]为第一个元素，其存储地址为1000，A[2][2]的地址为1040，则A[3][0]的地址为_________。

选项：

A、1024

B、1048

C、1060

D、1096

答案：【1048】16.单选题：数组a[1．．6][1．．5]（无0行0列）以列序优先顺序存储，第一个元素a[1][1]的地址为1000，每个元素占2个存储单元，则a[3][4]的地址是____。

选项：

A、1026

B、1038

C、1040

D、1046

答案：【1040】17.单选题：以行序优先顺序存储数组A[5][5]；假定A[0][0]的地址为1000,每个元素占4个字节，下标变量A[4][3]的地址是____。

选项：

A、1023

B、1046

C、1069

D、1092

答案：【1092】18.单选题：使用三元组来保存稀疏矩阵中的非零元素，三元组不包括非零元素的__________。

选项：

A、个数

B、行号

C、列号

D、元素值

答案：【个数】19.单选题：某稀疏矩阵A采用十字链表作为存储结构，对于矩阵元素的赋值运算Assign(A,e,i,j)，不可能_________。（在Assign(A,e,i,j)中，e是矩阵元素Ai,j的值，i和j分别为矩阵元素的行号和列号）

选项：

A、修改稀疏矩阵的行列数

B、修改某个结点的值

C、增加一个新结点

D、删除一个结点

答案：【修改稀疏矩阵的行列数】20.单选题：下列叙述中，不正确的是__________。

选项：

A、数组是一种线性结构

B、数组是一种定长的线性表

C、除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等

D、数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作

答案：【除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等】21.单选题：对稀疏矩阵进行压缩存储方法一般有两种，分别为________。

选项：

A、三元组和对称矩阵

B、对角矩阵和散列

C、散列和十字链表

D、三元组顺序表和十字链表

答案：【三元组顺序表和十字链表】22.单选题：某稀疏矩阵A采用三元组顺序表作为存储结构，对于矩阵元素的赋值运算Assign(A,e,i,j)，不可能_________。（在Assign(A,e,i,j)中，e是矩阵元素Ai,j的值，i和j分别为矩阵元素的行号和列号）。

选项：

A、修改某个三元组的行号或列号

B、插入一个新的三元组

C、修改某个三元组的元素值

D、删除一个三元组

答案：【修改某个三元组的行号或列号】23.单选题：设10*10三对角矩阵保存SA[1．．28]中，其中A[1][1]保存在SA[1]中，A[5][5]保存在SA[k]中，这里k等于_________。

选项：

A、10

B、11

C、12

D、13

答案：【13】24.单选题：对n行n列的三对角矩阵，需要保存的数据元素的个数是_________。

选项：

A、3n

B、

C、3n-2

D、n(n+1)

答案：【3n-2】25.单选题：设10*10的对称矩阵下三角保存SA[1．．55]中，其中A[1][1]保存在SA[1]中，A[5][3]保存在SA[k]中，这里k等于_________。

选项：

A、12

B、13

C、14

D、15

答案：【13】26.单选题：对对称矩阵进行压缩存储，能提高存储效率，其压缩率可低至50%。（压缩率为压缩后的大小与压缩前的大小之比）

选项：

A、正确

B、错误

答案：【错误】27.单选题：n维数组的存储方案中，每一个数组元素都有n个方向的关系（约束）。

选项：

A、正确

B、错误

答案：【正确】28.单选题：通过数组的顺序存储结构，按行序优先次序保存了数组的全部数据元素，可以通过寻址公式对数组元素进行随机访问。

选项：

A、正确

B、错误

答案：【正确】29.单选题：数组的顺序存储结构中，按行序（或列序）优先次序存放数组元素，是为了方便寻址公式的分析。

选项：

A、正确

B、错误

答案：【正确】30.单选题：数组是一个定长的线性表，所以不能有元素的增加与删除操作。

选项：

A、正确

B、错误

答案：【正确】31.单选题：数组是一种复杂的数据结构，数据元素之间的关系既不是线性的，也不是树型的。

选项：

A、正确

B、错误

答案：【错误】32.单选题：在一维数组（向量）中，能很方便地通过增加数据元素使数组长度增加。

选项：

A、正确

B、错误

答案：【错误】33.单选题：通常广义表的物理结构是链式的。

选项：

A、正确

B、错误

答案：【正确】34.单选题：广义表中的元素既可以是原子，也可以是广义表。

选项：

A、正确

B、错误

答案：【正确】35.单选题：以十字链表存储稀疏矩阵时，只能对数据元素进行顺序访问。

选项：

A、正确

B、错误

答案：【正确】36.单选题：以三元组顺序表存储稀疏矩阵时，对元素A[i][j]赋值一个非零值，只需要三元组顺序表的最后添加新的三元组（i，j，A[i][j]）。

选项：

A、正确

B、错误

答案：【错误】37.单选题：以三元组顺序表存储稀疏矩阵时，对元素A[i][j]赋值0，可能会在三元组顺序表中引起三元组（i，j，A[i][j]）后面的三元组向前面移动。

选项：

A、正确

B、错误

答案：【正确】38.单选题：以三元组顺序表存储稀疏矩阵时，可以通过寻址公式对数据元素进行随机访问。

选项：

A、正确

B、错误

答案：【错误】39.单选题：元素A[i][j]在三对角矩阵的三对角位置上的条件是|i-j|≤1。

选项：

A、正确

B、错误

答案：【正确】40.单选题：元素A[i][j]在对称矩阵的下三角位置上的条件是i。

选项：

A、正确

B、错误

答案：【错误】41.单选题：在特殊矩阵中，有很多值相同的元素并且有规律地分布，所以没有必要重复存储值相同的元素。

选项：

A、正确

B、错误

答案：【正确】42.单选题：对特殊矩阵进行压缩存储后，无法实现对其元素进行随机访问。

选项：

A、正确

B、错误

答案：【错误】43.单选题：广义表(a,(b,(c,d,((),()))))的长度为6。

选项：

A、正确

B、错误

答案：【错误】44.单选题：广义表(a,(b,(c,d,((),()))))的深度为5。

选项：

A、正确

B、错误

答案：【正确】45.单选题：广义表的长度是指广义表中括号嵌套的层数。

选项：

A、正确

B、错误

答案：【错误】46.单选题：一个非空广义表的表尾总是一个广义表。

选项：

A、正确

B、错误

答案：【正确】47.单选题：一个广义表的表头不一定是一个广义表。

选项：

A、正确

B、错误

答案：【正确】48.单选题：当某稀疏矩阵经常进行元素的赋值运算时，十字链表比三元组表更适合作为其存储结构。

选项：

A、正确

B、错误

答案：【正确】49.单选题：以十字链表存储稀疏矩阵时，对元素A[i][j]赋值一个非零值，一定会在2个单链表中进行增加结点的操作。

选项：

A、正确

B、错误

答案：【错误】50.单选题：以十字链表存储稀疏矩阵时，对元素A[i][j]赋值0，一定会在2个单链表中进行结点的删除操作。

选项：

A、正确

B、错误

答案：【错误】第六章树与二叉树第六章树单元测试1.单选题：用13个权值构造哈夫曼树，则该哈夫曼树共有个结点。

选项：

A、13

B、12

C、26

D、25

答案：【25】2.单选题：由树转换成的二叉树里，一个结点N的左孩子是N在原树里对应结点的。

选项：

A、最左孩子结点

B、最右孩子结点

C、最邻近的右兄弟

D、最邻近的左兄弟

答案：【最左孩子结点】3.单选题：给定一棵树的二叉链表存储结构，把这棵树转换为二叉树后，这棵二叉树的形态是。

选项：

A、唯一的

B、有多种

C、有多种，但根结点都没有左孩子

D、有多种，但根结点都没有右孩子

答案：【唯一的】4.单选题：如果二叉树T2是由一棵树T1转换而来的二叉树，那么T1结点的先根遍历序列对应T2的序列。

选项：

A、先序遍历

B、中序遍历

C、后序遍历

D、层次遍历

答案：【先序遍历】5.单选题：设森林F有3棵树，分别有9、8和7个结点，则F此排列次序转换成二叉树后根结点的右子树上结点的个数是。

选项：

A、16

B、15

C、7

D、17

答案：【15】6.单选题：讨论树、森林和二叉树的关系，目的是________。

选项：

A、将树、森林按二叉树的存储结构进行存储，并利用二叉树的算法解决树与森林的有关问题

B、将树、森林转化成二叉树，统一逻辑表示形式

C、只是为了方便定义树、森林的遍历方法

D、体现一种技巧，没有什么实际意义

答案：【将树、森林按二叉树的存储结构进行存储，并利用二叉树的算法解决树与森林的有关问题】7.单选题：基于中序线索化链表，其头结点指针为head，对应的二叉树为空的判断条件是。

选项：

A、head==NULL

B、head->lchild==head&&head->rchild==head

C、head->ltag==0

D、head->rtag==1

答案：【head->lchild==head&&head->rchild==head】8.单选题：二叉树线索化后，仍不能有效求解的问题是。

选项：

A、先序线索二叉树中求先序后继

B、中序线索二叉树中求中序后继

C、中序线索二叉树中求中序前驱

D、后序线索二叉树中求后序后继

答案：【后序线索二叉树中求后序后继】9.单选题：设一组权值集合W=(2，4，5，7)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为。

选项：

A、36

B、46

C、35

D、34

答案：【35】10.单选题：对n（n≧2）个权值不同的字符依哈夫曼算法构造哈夫曼树，下面关于该哈夫曼树的叙述中错误的是。

选项：

A、树中一定没有度为1的结点

B、该树一定是一棵完全二叉树

C、树中两个权值最小的结点一定是兄弟结点

D、树中任何一个非叶结点的权值一定不小于下一层任意一个结点的权值

答案：【该树一定是一棵完全二叉树】11.单选题：在一个非空二叉树的中序序列中，根结点的右边是。

选项：

A、只有右子树上的所有结点

B、只有右子树上的部分结点

C、只有左子树上的部分结点

D、只有左子树上的所有结点

答案：【只有右子树上的所有结点】12.单选题：不使用栈实现二叉树后序遍历的非递归算法，最佳方案是二叉树的存储结构采用表示。

选项：

A、二叉链表

B、广义表

C、三叉链表

D、顺序表

答案：【三叉链表】13.单选题：在二叉树中有两个结点m和n，如果m是n的祖先，使用非递归过程更方便找到从m到n的路径。

选项：

A、先序遍历

B、中序遍历

C、后序遍历

D、层次遍历

答案：【后序遍历】14.单选题：对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左右子女的编号，同一结点的左、右子女中，其左子女的编号小于其右子女的编号，则可采用遍历实现二叉树的这种结点编号。

选项：

A、先序

B、中序

C、后序

D、层序

答案：【后序】15.单选题：下列二叉树，其后序遍历序列与层次遍历序列相同的非空二叉树是。

选项：

A、满二叉树

B、完全二叉树

C、单支树

D、只有根结点的二叉树

答案：【只有根结点的二叉树】16.单选题：二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定满足的条件是。

选项：

A、空或只有一个结点

B、高度等于其结点数

C、任一结点无左孩子

D、任一结点无右孩子

答案：【高度等于其结点数】17.单选题：用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为。

选项：

A、n-1

B、n

C、n+l

D、2n

答案：【n+l】18.单选题：以下存储结构中，不是树的存储结构是。

选项：

A、双亲表示法

B、孩子兄弟链表

C、孩子链表存储结构

D、广义表

答案：【广义表】19.单选题：将下图所示的二叉树按中序线索化，结点c的左指针与结点h的右指针分别指向。

选项：

A、a,c

B、g,c

C、h,g

D、a,g

答案：【a,g】20.单选题：判断线索二叉链表中*p结点有右孩子结点的条件是。

选项：

A、p!=NULL

B、p->rchild!=NULL

C、p->rtag==0

D、p->rtag==1

答案：【p->rtag==0】21.单选题：二叉树采用二叉链表存储结构存储，根指针为t，下列递归算法求其叶子结点的个数,算法的画线处应填的语句是。

选项：

A、t->lchild==NULL

B、t->lchild==NULL&&t->rchild!=NULL

C、t->rchild==NULL

D、t->lchild==NULL&&t->rchild==NULL

答案：【t->lchild==NULL&&t->rchild==NULL】22.单选题：一棵二叉树采用二叉链表存储结构存储，根指针为t，下列递归算法求其先序序列中第k（1≦k≦二叉树中结点的个数）个结点的值，算法的画线处应填的语句是。

选项：

A、k--

B、n++

C、t=t->lchild

D、t=t->rchild

答案：【n++】23.单选题：一棵二叉树的先序遍历序列为EFHIGJK,中序遍历序列为HFIEJKG,则该二叉树根结点的右孩子为。

选项：

A、E

B、F

C、G

D、H

答案：【G】24.单选题：若二叉树采用二叉链表存储结构，要交换所有分支结点的左右子树的位置，利用基于遍历的递归算法最合适。

选项：

A、逆中序

B、中序

C、后序

D、层次

答案：【后序】25.单选题：先序遍历序列为ABC，后序遍历序列为CBA的二叉树共有棵。

选项：

A、1

B、2

C、3

D、4

答案：【4】26.单选题：设某棵二叉树的中序遍历序列为ABCD，先序遍历序列为CABD，则后序遍历该二叉树得到序列为。

选项：

A、BADC

B、BCDA

C、CDAB

D、CBDA

答案：【BADC】27.单选题：具有n(n>0)个结点的完全二叉树的深度为。

选项：

A、élog2(n)ù

B、?log2(n)?

C、?log2(n)?+1

D、élog2(n)+1ù

答案：【?log2(n)?+1】28.单选题：设深度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含结点数至多为。

选项：

A、

B、

C、

D、

答案：【】29.单选题：设深度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含结点数至少为。

选项：

A、2h

B、2h-1

C、2h+1

D、h+1

答案：【2h-1】30.单选题：下列陈述中正确的是。

选项：

A、二叉树是度为2的有序树

B、二叉树中结点只有一个孩子时无左右之分

C、二叉树中必有度为2的结点

D、二叉树中每个结点最多只有两棵子树，并且有左右之分

答案：【二叉树中每个结点最多只有两棵子树，并且有左右之分】31.单选题：在树结构中，若结点A有三个兄弟，且B是A的双亲，则B的度是。

选项：

A、3

B、4

C、5

D、2

答案：【4】32.单选题：树最适合用来表示。

选项：

A、有序数据元素

B、无序数据元素

C、元素之间具有分支层次关系的数据

D、元素之间无联系的数据

答案：【元素之间具有分支层次关系的数据】33.单选题：一棵深度为k且只有k个结点的二叉树按照完全二叉树顺序存储的方式存放于一个一维数组R[n]中，则n至少是才能确保正确存储。

选项：

A、2k

B、2k+1

C、

D、

答案：【】34.单选题：用顺序存储的方法将n个结点的完全二叉树中所有结点按层逐个依从左至右的次序存放在一维数组R[1:n]中，若结点R[i]有左孩子，则左孩子是。

选项：

A、R[2i-1]

B、R[2i]

C、R[2i+1]

D、R[2i+2]

答案：【R[2i]】35.单选题：二叉树是非线性数据结构，所以。

选项：

A、它不能用顺序存储结构存储

B、它不能用链式存储结构存储

C、顺序存储结构和链式存储结构都能存储

D、顺序结构和链式结构都不能使用

答案：【顺序存储结构和链式存储结构都能存储】36.单选题：一棵二叉树有35个结点，则所有结点的度之和为。

选项：

A、35

B、16

C、33

D、34

答案：【34】37.单选题：若一棵二叉树有9个度为2的结点，5个度为1的结点，则叶子结点的个数为。

选项：

A、9

B、10

C、15

D、不确定

答案：【10】38.单选题：具有3个结点的二叉树有种。

选项：

A、3

B、4

C、5

D、6

答案：【5】39.单选题：一棵完全二叉树的第6层上有23个叶子结点，则此二叉树最多有结点。

选项：

A、78

B、79

C、80

D、81

答案：【81】40.单选题：具有32个结点的完全二叉树有个叶子结点。

选项：

A、14

B、15

C、16

D、17

答案：【16】41.单选题：二叉树的先序遍历的递归算法的时间复杂度为线性级。

选项：

A、正确

B、错误

答案：【正确】42.单选题：树的孩子兄弟表示法是一种二叉链表表示法。

选项：

A、正确

B、错误

答案：【正确】43.单选题：树有先根遍历与中根遍历两种遍历方法。

选项：

A、正确

B、错误

答案：【错误】44.单选题：将一棵含有两个以上结点的树转换成二叉树后，该二叉树的根结点没有左子树。

选项：

A、正确

B、错误

答案：【错误】45.单选题：可以不用栈实现基于中序线索二叉链表对二叉树进行中序遍历。

选项：

A、正确

B、错误

答案：【正确】46.单选题：在某种遍历的线索二叉链表中，进行这种遍历时可以直接沿所有右指针一直搜索下去，从而访问所有结点。

选项：

A、正确

B、错误

答案：【错误】47.单选题：用二叉树的先序序列和后序序列可以导出它的中序序列。

选项：

A、正确

B、错误

答案：【错误】48.单选题：由二叉树的某种遍历方式产生的结果是一个线性序列。

选项：

A、正确

B、错误

答案：【正确】49.单选题：在哈夫曼编码中，当两个不同字符出现的频率相同时，其编码也相同。

选项：

A、正确

B、错误

答案：【错误】50.单选题：在哈夫曼树中，权值较大的叶子结点一般离根结点较远。

选项：

A、正确

B、错误

答案：【错误】51.单选题：对一棵树进行先根遍历与后根遍历，其中叶子结点出现的相对次序是相同的。

选项：

A、正确

B、错误

答案：【正确】52.单选题：对于任意的二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n2＝n0＋1。

选项：

A、正确

B、错误

答案：【错误】53.单选题：完全二叉树适合使用顺序存储结构

选项：

A、正确

B、错误

答案：【正确】54.单选题：一棵满二叉树中每棵子树都是完全二叉树。

选项：

A、正确

B、错误

答案：【正确】55.单选题：树与二叉树是两种不同的树形结构。

选项：

A、正确

B、错误

答案：【正确】56.单选题：树中元素结点是多对多的关系。

选项：

A、正确

B、错误

答案：【错误】第七章图第七章图单元测试1.单选题：最小生成树是指________。

选项：

A、连通网的所有生成树中权值之和最小的生成树

B、由连通网得到的边数最少的生成树

C、由连通网得到的顶点数相对较少的生成树

D、连通网的极小连通子图

答案：【连通网的所有生成树中权值之和最小的生成树】2.单选题：对图进行广度优先搜索遍历，需要借助的数据结构为________。

选项：

A、栈

B、队列

C、线索二叉树

D、广义表

答案：【队列】3.单选题：对图进行深度优先搜索遍历，需要借助的数据结构为________。

选项：

A、栈

B、队列

C、线索二叉树

D、广义表

答案：【栈】4.单选题：在下图中，从顶点A出发进行深度优先遍历可得到的序列是_________。

选项：

A、ADCBG

B、ACDBG

C、ADGBC

D、ABDCG

答案：【ABDCG】5.单选题：如图所示的有向图，共有________个强连通分量。

选项：

A、1

B、2

C、3

D、4

答案：【2】6.单选题：如果从无向图的一个顶点出发，进行一次深度优先搜索能访问所有顶点，则该无向图是一个________。

选项：

A、连通图

B、强连通图

C、完全图

D、DAG图

答案：【连通图】7.单选题：n个顶点的有向图为强连通图时，至少含有________。

选项：

A、n-1条弧

B、n条弧

C、n(n-1)/2条弧

D、n(n-1)条弧

答案：【n条弧】8.单选题：设G是一个非连通的无向图，共有10条边，则该图至少有_____个顶点。

选项：

A、5

B、6

C、7

D、8

答案：【6】9.单选题：某无向图的邻接矩阵如下所示，可以得出，该图共有__________个顶点。

选项：

A、3

B、4

C、9

D、5

答案：【3】10.单选题：使用弗洛伊德算法，求任意2个顶点的最短路径，该算法的时间复杂度为________。

选项：

A、O()

B、O(nlogn)

C、

D、

答案：【】11.单选题：使用迪杰斯特拉最短路径算法，求一个源点到其它各顶点的最短路径，该算法的时间复杂度为________。

选项：

A、O()

B、O(nlogn)

C、

D、

答案：【O()】12.单选题：下列关于工程计划的AOE网的叙述中，不正确的是_________。

选项：

A、关键活动不按期完成，会影响整个工程的完成时间

B、任何一个关键活动的提前完成，整个工程的完成时间都会提前

C、所有关键活动都提前完成，会提前整个工程的完成时间

D、某个关键活动提前完成，可能会提前整个工程的完成时间

答案：【任何一个关键活动的提前完成，整个工程的完成时间都会提前】13.单选题：如图所示的DAG图，其拓扑排序序列为_________。

选项：

A、ADBGC

B、ACDGB

C、ADGBC

D、AGBDC

答案：【ADBGC】14.单选题：可借助于____