数据结构与算法知到智慧树章节测试课后答案2024年秋山东石油化工学院VIP

数据结构与算法知到智慧树章节测试课后答案2024年秋山东石油化工学院第一章单元测试

关于数据结构以下说法正确的是（）。

A:数据项是数据的基本单位B:数据结构是带有结构的各数据项的集合C:数据对象是带结构的数据元素的子集D:数据元素是数据的最小单位

答案:数据对象是带结构的数据元素的子集数据结构的定义是（）。

A:相互之间存在一种或多种特定关系的数据元素的集合B:数据的存储结构C:一种数据类型D:一组性质相同的数据元素的集合

答案:相互之间存在一种或多种特定关系的数据元素的集合在数据结构中，与所使用的计算机无关的是数据的（）结构。

A:逻辑和存储B:存储C:逻辑D:物理

答案:逻辑数据结构在计算机内存中的表示是指（）。

A:数据的逻辑结构B:数据结构C:数据元素之间的关系D:数据的存储结构

答案:数据的存储结构在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（）。

A:数据的存储方法B:数据的处理方法C:数据元素的类型D:数据元素之间的关系

答案:数据元素之间的关系在数据结构中，从逻辑上可以把数据结构分成（）。

A:紧凑结构和非紧凑结构B:动态结构和静态结构C:线性结构和非线性结构D:内部结构和外部结构

答案:线性结构和非线性结构可以用（）定义一个完整的数据结构。

A:数据关系B:抽象数据类型C:数据元素D:数据对象

答案:抽象数据类型数据的存储结构包括（）。

A:逻辑结构和物理结构B:线性结构和非线性结构C:虚拟结构和抽象结构D:连续结构和非连续结构

答案:连续结构和非连续结构计算机算法指的是解决问题的步骤序列，它必须具备（）这五个特性。

A:可执行性、确定性、有穷性、输入、输出B:确定性、有穷性、稳定性、输入、输出C:可执行性、可移植性、可扩充性、输入、输出D:易读性、稳定性、安全性、输入、输出

答案:可执行性、确定性、有穷性、输入、输出算法的时间复杂度取决于（）。

A:待处理数据的初态B:算法执行的实际时间C:问题的规模D:问题的规模和待处理数据的初态

答案:问题的规模和待处理数据的初态在下面的程序段中，对x的赋值的语句频度为（）。

for(i=0;i<n;i++)

for(j=0;j<n;j++)

x=x+1;

A:O(n)B:O(n2)C:O(2n)D:O(log2n)

答案:O(n2)下面的程序段中，n为正整数，则最后一行的语句频度在最坏情况下是（）

for(i=n-1;i>=1;i--)

for(j=1;j<=i;j++)

if(A[j]>A[j+1])

A[j]与A[j+1]对换；

A:O(n)B:O(n3)C:O(nlog2n)D:O(n2)

答案:O(n2)算法分析的目的是（）。

A:研究算法中的输入和输出的关系B:分析算法的效率以求改进C:找出数据结构的合理性D:分析算法的易懂性和文档性

答案:分析算法的效率以求改进算法指的是（）。

A:求解特定问题的指令有限序列B:解决问题的方法C:计算机程序D:查找或排序过程

答案:求解特定问题的指令有限序列算法的效率主要是指（）

A:其他说法都不对B:算法的时间效率C:算法的空间效率D:算法的空间效率和时间效率

答案:算法的空间效率和时间效率试分析下面各程序段的时间复杂度为（）。

i=1;

while(i<=n)

i=i*3;

A:O(n)B:O(1)C:O(log3n)D:O(log2n)

答案:O(log3n)计算下列程序的渐进时间复杂度为（）。

x=n;//n>1

y=0;

while(x≥(y+1)*(y+1))

y++;

A:O(n)B:O(1)C:O(sqrt(n))D:O(log3n)

答案:O(sqrt(n))

第二章单元测试

线性表的顺序存储结构是一种（）的存储结构。

A:索引存取B:散列存取C:顺序存取D:随机存取

答案:随机存取对线性表的定义是（）。

A:一个有限序列，可以为空 B:一个无限序列，不可以为空C:一个无限序列，可以为空D:一个有限序列，不可以为空

答案:一个有限序列，可以为空 线性结构的数据元素之间存在一种（）。

A:多对多关系B:多对一关系C:一对一关系D:一对多关系

答案:一对一关系有关线性表L=(a1，a2,……an)，下列说法正确的是（）。

A:每个元素都有一个直接前驱和一个直接后继B:表中诸元素的排列必须是由小到大或由大到小C:线性表中至少有一个元素D:除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。

答案:除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。以下关于顺序表的说法中，正确的是（）。

A:在顺序表中每一元素的数据类型还可以是顺序表B:顺序表可以利用一维数组表示,因此顺序表与一维数组在结构上是一致的，它们可以通用C:顺序表和一维数组一样,都可以按下标随机(或直接)访问，顺序表还可以从某一指定元素开始,向前或向后逐个元素顺序访问D:在顺序表中,逻辑上相邻的元素在物理位置上不一定相邻

答案:顺序表和一维数组一样,都可以按下标随机(或直接)访问，顺序表还可以从某一指定元素开始,向前或向后逐个元素顺序访问顺序表具有的特点是（）。

A:不必事先估计存储空间B:插入、删除不需要移动元素C:可随机访问任一元素D:所需空间不必连续

答案:可随机访问任一元素若长度为n的顺序表在其第i个位置插入一个新元素，需移动的元素个数是（）。

A:n-i+1B:n-iC:iD:n

答案:n-i+1向一个有126个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。

A:8B:63.5C:7D:63

答案:63假设删除长度为n的顺序表中的每个元素的概率相同，则删除一个元素平均要移动的元素个数是（）。

A:(n+1)/2B:(n-1)/2C:nD:n/2

答案:(n-1)/2假设长度为127的顺序表，在任意位置上插入和删除元素都是等概率的，删除一个新元素时需平均移动表中的（）个元素。

A:64B:63C:63.5D:127

答案:63若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。

A:O(n2)B:O(1)C:O(n)D:O(0)

答案:O(n)在长度为n的顺序表中删除一个元素的时间复杂度为（）。

A:O(n^2)B:O(1)C:O(log2n)D:O(n)

答案:O(n)若设一个顺序表的长度为n,那么，在表中顺序查找一个值为x的元素时，在等概率的情况下，查找成功的数据平均比较次数为（）。

A:(n+1)/2B:(n-1)/2C:NULLD:n

答案:(n+1)/2在n个结点的顺序表中，算法的时间复杂度是O(n)的操作是（）。

A:将n个结点从小到大排序B:访问第i个结点（1≤i≤n）C:求第i个结点的直接前驱（2≤i≤n）D:在第i个结点后插入一个新结点（1≤i≤n）

答案:在第i个结点后插入一个新结点（1≤i≤n）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。

A:部分地址必须是连续的B:必须是连续的C:连续或不连续都可以D:一定是不连续的

答案:连续或不连续都可以在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。

A:s->next=p->next;p->next=s;B:s->next=p->next;p->next=s->next;C:(*p).next=s;(*s).next=(*p).next;D:s->next=p+1;p->next=s;

答案:s->next=p->next;p->next=s;已知L是带头结点的单链表，则删除首元结点的语句是（）。

A:L->next=L->next->next;B:L->next=L;C:L=L->next;D:L=L->next->next;

答案:L->next=L->next->next;在一个单链表中,若删除p所指结点的后继结点q(注:P既不是第一个结点,也不是最后一个结点)，则执行（）操作。

A:q->next=p->next;B:p=q->next;C:p-next=q->next;D:p=p->next->next;

答案:p-next=q->next;单链表的存储结构中增加了一个头结点，关于头结点的描述中，下面哪一项是错误的（）

A:在单链表中增加头结点，插入或删除首元结点时不必进行特殊处理B:若链表中有头结点，则头指针一定不为空C:头结点中不存储链表的数据元素，而是一些诸如表长之类的辅助信息D:有没有头结点对算法执行的效率没有任何影响

答案:有没有头结点对算法执行的效率没有任何影响带头结点的单链表head为空的判定条件是（）。

A:head!=NULLB:head->next==NULLC:head->next==LD:head==NULL

答案:head->next==NULL单链表的存储密度（）。

A:等于1B:不能确定C:大于1D:小于1

答案:小于1以下关于单链表的叙述中，不正确的是（）。

A:结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B:可以通过头结点直接计算第i个结点的存储地址C:插入、删除运算操作方便，不必移动结点D:逻辑上相邻的元素物理上不必相邻

答案:可以通过头结点直接计算第i个结点的存储地址单链表又称线性链表，在单链表上实施删除操作（）。

A:只需移动结点，不需改变结点指针B:不需要移动结点，不需改变结点指针C:既需移动结点，又需要改变结点指针D:不需移动结点，只需改变结点指针

答案:不需移动结点，只需改变结点指针单链表又称线性链表，在单链表上实施插入操作（）

A:只需移动结点，不需改变结点指针B:不需移动结点，只需改变结点指针C:不需要移动结点，不需改变结点指针D:既需移动结点，又需要改变结点指针

答案:不需移动结点，只需改变结点指针在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（）。

A:p->next=q;q->prior=p;p->next->prior=q;q->next=q;B:q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;C:p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;D:q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;

答案:q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;在双向链表存储结构中，删除p所指的结点时须修改指针（）。

A:p->next=p->next->next;p->next->prior=p;B:p->prior->next=p;p->prior=p->prior->prior;C:p->prior=p->next->next;p->next=p->prior->prior;D:p->next->prior=p->prior;p->prior->next=p->next;

答案:p->next->prior=p->prior;p->prior->next=p->next;以下链表结构中，从当前结点出发能够访问到任一结点的是（）。

A:双向链表和循环链表 B:单向链表、双向链表和循环链表C:单向链表和循环链表D:单向链表和双向链表

答案:双向链表和循环链表 循环链表的主要特点是（）

A:在进行插入删除运算时，能更好的保证链表不断开B:已知某个结点的位置后，能容易找到它的直接前驱C:在链表的任意位置出发都能扫描到整个链表D:不再需要头指针了

答案:在链表的任意位置出发都能扫描到整个链表双向链表的主要特点是（）

A:已知某个结点的位置后，能容易找到它的直接前驱B:在链表的任意位置出发都能扫描到整个链表C:不再需要头指针了D:在进行插入删除运算时，能更好的保证链表不断开

答案:已知某个结点的位置后，能容易找到它的直接前驱线性表Ｌ在（）情况下适用于使用链式结构实现。

A:需不断对Ｌ进行删除插入B:Ｌ中结点结构复杂C:Ｌ中含有大量的结点D:需经常修改Ｌ中的结点值

答案:需不断对Ｌ进行删除插入若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A:带头结点的双循环链表B:顺序表C:双链表D:单循环链表

答案:顺序表某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A:仅有尾指针的单循环链表B:循环链表C:单链表D:双链表

答案:仅有尾指针的单循环链表

第三章单元测试

栈是一种受限的线性结构，其操作特点是（）。

A:没有顺序B:先进后出C:先进先出D:后进后出

答案:先进后出若让元素1,2,3,4,5依次进栈，则出栈次序不可能出现在（）种情况。

A:5,4,3,2,1B:2,3,5,4,1C:2,1,5,4,3D:4,3,1,2,5

答案:4,3,1,2,5若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pj为（）。

A:jB:n-jC:不确定D:n-j+1

答案:n-j+1判定一个顺序栈ST(最多元素数为m)为满的的条件是ST->top==m0-1，则其为空的条件是（）。

A:ST->top=mB:ST->top<>mC:ST->top<>0D:ST->top==-1

答案:ST->top==-1以下关于顺序栈的操作，正确的是（）。

A:栈是一种对进栈和出栈操作的次序做了限制的线性表B:若一个栈的存储空间为S[n]，则对栈的进栈和出栈操作最多只能执行n次C:空栈没有栈顶指针D:n个元素进入一个顺序栈后，如果一次性进栈完毕再出栈，它们的出栈顺序一定与进栈顺序相反

答案:n个元素进入一个顺序栈后，如果一次性进栈完毕再出栈，它们的出栈顺序一定与进栈顺序相反向一个栈顶指针为top的不带头结点的链栈中插人一个*S结点的时候，应当执行语句（）。

A:S->next＝top->next；top->next＝S；B:S->next=top；top=S；C:top->next=S;D:S->next＝top；top＝S->next；

答案:S->next=top；top=S；向一个带头结点、栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（）。

A:S->next=top->next；top->next=S；B:top->next=S；C:S->next=top；top=S；D:S->next=top；top=S->next；

答案:S->next=top->next；top->next=S；算术表达式a+b*(c+d)/e转为后缀表达式后为（）。

A:abcde*/++B:abcde/+*+C:abcde/*++D:abcd+*e/+

答案:abcd+*e/+设计一个判别表达式中左、右括号是否配对出现的算法，采用（）数据结构最佳。

A:队列B:线性表的顺序存储结构C:栈D:线性表的链式存储结构

答案:栈链式栈的存储结构为(data,next)，top和bottom分别是指向栈顶和栈底的指针，此时p指针所指的结点入栈，则应执行操作是（）。

A:p->next=top;top=p;B:p->next=top;top=p->link;C:p->next=top->next;top=p;D:p->next=top;top->next=p;

答案:p->next=top;top=p;向一个栈顶指针为top的不带头结点的链栈中插人一个*S结点的时候，应当执行语句（）。

A:S->next=top;top=S;B:S->next=top;top=S->next;C:top->next=S;D:S->next=top->next;top->next=S;

答案:S->next=top;top=S;链式栈结点为：(data,link)，top指向栈顶。若想删除栈顶结点，并将删除结点的值保存到x中，则应执行操作（）。

A:top=top->link;x=top->link；B:x=top;top=top->link；C:x=top->data;top=top->link；D:x=top->link；

答案:x=top->data;top=top->link；以下会用到栈的应用的是（）。

A:其他选项均有可能B:子程序调用C:括号匹配D:递归

答案:其他选项均有可能实现递归调用中的存储分配通常用（）数据结构。

A:链表B:数组C:栈D:堆

答案:栈队列是一种受限的线性结构，其操作原则是（）。

A:先进先出B:后进先出C:先进后出D:不分顺序

答案:先进先出判定一个顺序队列Q(最多有n个元素)为满的条件是（）。

A:Q->rear+1==Q->frontB:Q->rear-Q->front+1==nC:Q->rear-Q->front==nD:Q->rear==Q->front

答案:Q->rear-Q->front==n判定一个顺序循环队列Q(最多有n个元素)为空的条件是（）。

A:Q->front==(Q->rear+1)%nB:Q->rear==Q->frontC:Q->rear==Q->front+1D:Q->front==(Q->rear-1)%n

答案:Q->rear==Q->front最大容量为n的循环队列，队尾指针是rear，队头是front，则队满的条件是（）。

A:(rear-l)%n==frontB:rear+1==frontC:(rear+1)%n==frontD:rear==front

答案:(rear+1)%n==front数组Ｑ[ｎ]用来表示一个循环队列，front为当前队列头元素的前一位置，rear为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A:(n+rear-front)%nB:n+rear-frontC:rear-frontD:(n+front-rear)%n

答案:(n+rear-front)%n循环队列存储在数组A[0..m]中，则入队时的操作为（）。

A:rear=rear+1B:rear=(rear+1)%(m-1)C:rear=(rear+1)%mD:rear=(rear+1)%(m+1)

答案:rear=(rear+1)%(m+1)队列的插入操作在（）进行。

A:任意位置B:指定位置C:rear所指的位置D:front所指的位置

答案:rear所指的位置一个队列的进队顺序是1,2,3,4,则该队列可能的输出序列是（）。

A:4,3,2,1B:1,3,2,4C:1,4,2,3D:1,2,3,4

答案:1,2,3,4对于链式队列，在执行插入操作时（）。

A:头、尾指针都要修改B:仅修改头指针C:仅修改尾指针D:头、尾指针可能都要修改

答案:头、尾指针可能都要修改用链接方式存储的队列，在进行出队运算时（）。

A:头、尾指针可能都要修改B:头、尾指针都要修改C:仅修改尾指针D:仅修改头指针

答案:头、尾指针可能都要修改用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（）。

A:仅修改队头指针B:队头、队尾指针都要修改C:仅修改队尾指针D:队头、队尾指针可能都要修改

答案:队头、队尾指针可能都要修改在带头结点的链接方式存储的队列中，在进行入队运算时（）。

A:仅修改头指针B:仅修改尾指针C:头、尾指针可能都要修改D:头、尾指针都要修改

答案:仅修改尾指针在带头结点的链接方式存储的队列中，在进行出队运算时（）。

A:头、尾指针都要修改B:仅修改头指针C:头、尾指针都可能不需要修改D:仅修改尾指针

答案:头、尾指针都可能不需要修改为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。

A:线性表B:队列C:栈D:有序表

答案:队列某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，若元素a,b,c,d,e依次入此队列后再进行出队操作，则不可能得到的出队序列是()。

A:b,a,c,d,e

B:d,b,a,c,e

C:e,c,b,a,d

D:d,b,c,a,e

答案:d,b,c,a,e

第四章单元测试

串是一种特殊的线性表，其特殊性体现在（）。

A:可以顺序存储B:数据元素没限制C:可以链式存储D:数据元素是字符

答案:数据元素是字符与线性表相比，串的插入和删除操作的特点是（）。

A:通常以串整体作为操作对象B:涉及移动元素更多C:算法的时间复杂度较高D:需要更多的辅助空间

答案:通常以串整体作为操作对象判断两个字符串相等是指（）。

A:两个串长度相等且含有相同的字符集B:两个串的长度相等且对应位置的字符相同C:两个串的长度相等D:两个串含有相同的字符集

答案:两个串的长度相等且对应位置的字符相同在串的简单模式匹配中(BF)，当模式串位j与目标串位i比较时,两字符不相等，则i的位移方式是（）。(下标从0开始)

A:i=j+1B:i++C:i=i-j+1D:i=j-i+1

答案:i=i-j+1在KMP模式匹配中，用next数组存放模式串的部分匹配信息。当模式串位j与目标串位i比较时，两字符不相等，则i的位移方式是（）。

A:i不变或者移动到下一位置B:j不变C:j=next[j]D:i=next[j]

答案:i不变或者移动到下一位置串的长度是指（）。

A:串中所含字符的个数B:串中所含不同字母的个数C:串中所含非空格字符的个数D:串中所含相同字符的个数

答案:串中所含字符的个数下面关于串的叙述中，正确的是（）。

A:串中元素只能是字母B:串是一种特殊的线性表C:空串就是空格串D:串的长度必须大于零

答案:串是一种特殊的线性表若串str=“Software”,其子串的个数是（）。

A:8B:36C:9D:37

答案:37空串与空格串（）。

A:不相同B:无法确定C:可能相同D:相同

答案:不相同一个子串在包含它的主串中位置是指（）。

A:子串的第一个字符在主串中首次出现的位置B:子串的最后那个字符在主串中的位置C:子串的最后那个字符在主串中首次出现的位置D:子串的第一个字符在主串中的位置

答案:子串的第一个字符在主串中首次出现的位置设有两个串p和q，求q在p中首次出现的位置的运算称做（）。

A:求串长B:求子串C:模式匹配D:连接

答案:模式匹配在KMP模式匹配中，用next数组存放模式串的部分匹配信息。当模式串位j与目标串位i比较时，两字符不相等，则i的位移方式是（）。

A:j不变B:j=next[j]C:i=next[j]D:i不变或者移动到下一位置

答案:i不变或者移动到下一位置在KMP模式匹配中，用next数组存放模式串的部分匹配信息。当模式串位j与目标串位i比较时，两字符不相等，则j的位移方式是（）。

A:i不变B:j不变C:i=next[j]D:j=next[j]

答案:j=next[j]已知字符串s为"abcacaabaabcc"，模式串t为"babaabc"。采用KMP算法进行匹配，第一次出现“失配”(s[i]!=t[j])时,i=j=0,则下次开始匹配时，i和j的值分别是（）

A:i=1,j=0B:i=0,j=-1C:i=2,j=0D:i=1,j=2

答案:i=1,j=0设主串的长度为n，子串的长度为m，那么BF算法的时间复杂度和KMP算法的时间复杂度为（）

A:O(nxm)，O(n+m)B:O(m)，O(n)C:O(n)，O(m)D:O(n+m)，O(nxm)

答案:O(nxm)，O(n+m)字符串“ababaabab”的next数组为（）。

A:(-1,0,0,1,2,3,1,2,3)B:(-1,0,-1,0,-1,1,0,-1,0)C:(-1,0,-1,0,-1,0,-1,0,0)D:(-1,0,-1,0,-1,-1,-1,0,0)

答案:(-1,0,0,1,2,3,1,2,3)

第五章单元测试

一个稀疏矩阵采用压缩后，和直接采用二维数组存储相比会失去（）特性。

A:随机存取B:顺序存储C:ABC都不对D:输入输出

答案:随机存取假设以行序为主序存储二维数组A=array[0..8,0..8](9行*9列)，设每个数据元素占2个存储单元，基地址为0，则LOC[5,5]=（）。

A:102B:100C:88D:89

答案:100设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址A开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（）。

A:BA+222B:BA+225C:BA+141D:BA+180

答案:BA+180在二维数组A[9][10]中，每个数组元素占用3个字节，从首地址base开始按行连续存放。在这种情况下，元素A[8][5]的地址为（）。

A:base+141B:base+222C:base+144D:base+255

答案:base+255若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij（i<j）的位置k的关系为（）。

A:j*(j-1)/2+iB:i*(i+1)/2+jC:j*(j+1)/2+iD:i*(i-1)/2+j

答案:j*(j-1)/2+i将一个A[1..100,1..100]的三对角矩阵，按行序优先存入一维数组B[1..298]中，A中元素A66,66，在B数组中的位置K为（）。

A:196B:197C:198D:195

答案:196对稀疏矩阵进行压缩存储的目的是（）。

A:便于进行矩阵运算B:便于输入和输出C:节省存储空间D:降低运算的时间复杂度

答案:节省存储空间稀疏矩阵常用的压缩存储方法有（）。

A:散列表和十字链表B:二维数组C:三元组和十字链表D:三元组和散列表

答案:三元组和十字链表有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2个字节，则用三元组表示该矩阵时，所需的字节数是（）。

A:18000B:33C:66D:60

答案:66

第六章单元测试

一棵有n个结点的树的所有结点的度数之和为（）。

A:nB:n+1C:2nD:n-1

答案:n-1在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（）

A:82B:113C:41D:122

答案:82表达人类社会中的族谱关系最适合的数据结构为（）。

A:线性表B:数组C:树D:图

答案:树不含任何结点的空树（）。

A:是一棵二叉树;B:是一棵树;C:是一棵树也是一棵二叉树;D:既不是树也不是二叉树

答案:是一棵树也是一棵二叉树;有关二叉树下列说法正确的是（）。

A:二叉树中每个结点的度都为2B:一棵二叉树的度可以小于2C:二叉树中任何一个结点的度都为2D:二叉树中至少有一个结点的度为2

答案:一棵二叉树的度可以小于2在一棵高度为k的满二叉树中，结点总数为（）。

A:2kB:2k-1C:2k-1D:2k-1+1

答案:2k-1若一棵完全二叉树中某结点无左孩子，则该结点一定是（）。

A:叶子结点B:分支结点C:度为2的结点D:度为1的结点

答案:叶子结点一棵完全二叉树上有98个结点，其中叶子结点的个数是（）。

A:48B:51C:50D:49

答案:49某二叉树中有60个叶子结点，则该二叉树中度为2的结点个数为（）。

A:不一定B:60C:59D:61

答案:59一个具有129个结点的二叉树的高h为（）。

A:7B:8C:8至129之间D:7至129之间

答案:8至129之间对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）遍历实现编号。

A:后序B:中序C:从根开始按层次遍历D:先序

答案:后序二叉树是非线性数据结构，所以（）。

A:顺序存储结构和链式存储结构都不能使用B:不能用顺序存储结构存储;C:不能用链式存储结构存储;D:顺序存储结构和链式存储结构都能存储

答案:顺序存储结构和链式存储结构都能存储一棵有124个叶子结点的完全二叉树最多有（）个结点。

A:249B:248C:250D:247

答案:248在有10个结点的二叉树的二叉链表表示中，空指针数为（）。

A:10B:11C:不定D:9

答案:11已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）。

A:FEDCBAB:CBEDFAC:不确定D:CBEFDA

答案:CBEFDAn个结点的线索二叉树上含有的线索数为（）。

A:nB:n+1C:2nD:n-1

答案:n+1引入二叉线索树的目的是（）。

A:为了能在二叉树中方便的进行插入与删除B:为了能方便的找到双亲C:加快查找结点的前驱或后继的速度D:使二叉树的遍历结果唯一

答案:加快查找结点的前驱或后继的速度一个具有129个结点的二叉树的高h为（）。

A:7至129之间B:8至129之间C:8D:7

答案:8至129之间如果二叉树T2是由一棵树T1转换而来的二叉树，那么T1中结点的先根序列对应T2的（）序列。

A:中序遍历B:先序遍历C:后序遍历D:层次遍历

答案:先序遍历设哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

A:102B:101C:100D:99

答案:100由权值为7,19,2,6,32,3,21,10的结点构成的哈夫曼树的带权路径长度为（）。

A:241B:271C:261D:231

答案:261有一电文共使用8种字符abcdefgh，各字符出现的次数分别为3，31，6，8，16，21，4，11。构造赫夫曼树，为这8个字符设计赫夫曼编码，并求出用赫夫曼编码传送电文的总长度为___bit。

答案:219拓扑排序算法是通过重复选择具有___个前驱顶点的过程来完成的。

答案:0

第七章单元测试

在一个无向图中，所有顶点的度数之和等于图的边数的（）倍。

A:4B:1/2C:2D:1

答案:2具有n个顶点的有向图最多有（）条边。

A:n(n+1)B:n(n-1)C:nD:n2

答案:n(n-1)在无向图中定义顶点的度为与它相关联的（）的数目。

A:权值B:权C:边D:顶点

答案:边具有n个顶点且每一对不同的顶点之间都有一条边的无向图被称为（）。

A:无向强连通图B:无向完全图C:无向树图D:无向连通图

答案:无向完全图在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为（）。

A:nB:s+1C:sD:s-1

答案:s有8个结点的无向连通图最少有（）条边。

A:8B:6C:5D:7

答案:7无向图的邻接矩阵是一个（）。

A:零矩阵B:对角矩阵C:上三角矩阵D:对称矩阵

答案:对称矩阵在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于（）。

A:i+jB:0C:1D:i-j

答案:1下列说法中正确的是（）。

A:一个图的邻接矩阵表示不唯一，邻接表表示也不唯一B:一个图的邻接矩阵表示是唯一的，邻接表表示不唯一C:一个图的邻接矩阵表示不唯一，邻接表表示唯一D:一个图的邻接矩阵表示是唯一的，邻接表表示也唯一

答案:一个图的邻接矩阵表示是唯一的，邻接表表示不唯一图是非线性数据结构，关于其存储结构，正确的描述是（）。

A:它不能用顺序存储结构存储B:顺序存储结构和链式存储结构都不能使用C:它不能用链式存储结构存储D:顺序存储结构和链式存储结构都能使用

答案:顺序存储结构和链式存储结构都能使用由一个具有n个顶点的连通图生成的最小生成树中，具有（）条边。

A:nB:n+1C:n-1D:2×n

答案:n-1用邻接表表示图进行深度优先遍历时，通常借助（）来实现算法。

A:图B:队列C:树D:栈

答案:栈若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。

A:非连通B:强连通C:有向D:连通

答案:连通图的深度优先遍历类似于二叉树的（）。

A:先序遍历B:层次遍历C:后序遍历D:中序遍历

答案:先序遍历下面（）算法适合构造一个稠密图G的最小生成树。

A:Floyd算法B:Prim算法C:Dijkstra算法D:Kruskal算法

答案:Prim算法下面（）方法可以判断出一个有向图是否有环。

A:求关键路径B:求最短路径C:拓扑排序D:深度优先遍历

答案:拓扑排序关键路径是AOE网络中（）。

A:从源点到汇点的最长路径B:最短回路C:最长回路D:从源点到汇点的最短路径

答案:从源点到汇点的最长路径对于一个具有n个顶点和e条边的无向图,若采用邻接矩阵表示，则该矩阵大小是（）

A:nB:(n-1)2C:n2D:n-1

答案:n2对于一个具有n个顶点和e条边的无向图,若采用邻接矩阵表示，矩阵中的非零元素个数是（）。

A:e2B:eC:2eD:n2

答案:2e在下列有关图的存储结构的说法中错误的是（）。

A:邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。B:对同一个有向图来说，邻接表中边结点数与逆邻接表中边结点数相等。C:用邻接矩阵存储一个图时所占用的存储空间大小与图中的顶点个数有关，而与图的边数无关。D:邻接矩阵只适用于稠密图(边数接近于顶点数的平方)，邻接表适用于稀疏图(边数远小于顶点数的平方)。

答案:邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发不可以得到一种深度优先遍历的顶点序列为（）。

A:aedfcbB:abedfcC:aebdfcD:acfebd

答案:acfebd广度优先遍历类似于二叉树的（）。

A:后序遍历B:层次遍历C:中序遍历D:先序遍历

答案:层次遍历用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。

A:树B:图C:队列D:栈

答案:队列关键路径中的关键活动是指活动的___开始时间和___开始时间相等的活动。

答案:最早开始时间和最晚开始时间相等的活动。若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先遍历，得到的顶点序列可能为

A:A,B,D,C,E,FB:A,B,C,F,D,E

C:A,C,B,F,D,ED:A,B,C,D,E,F

答案:A,C,B,F,D,E已知一个有向图的边集为{<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>}，则由该图产生的一种可能的拓扑序列为

A:

a,c,b,e,d

B:a,b,d,e,b

C:

a,c,d,b,e

D:a,b,c,d,e

答案:a,b,c,d,e

第八章单元测试

对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。

A:nB:(n-1)/2C:n/2D:(n+1)/2

答案:(n+1)/2适用于折半查找的表的存储方式及元素排列要求为（）。

A:链接方式存储，元素无序B:顺序方式存储，元素无序C:链接方式存储，元素有序D:顺序方式存储，元素有序

答案:顺序方式存储，元素有序采用折半查找方式查找一个长度为n的有序顺序表时，其平均查找长度为（）。

A:O(n)B:O(log2n)C:O(n2)D:O(nlog2n)

答案:O(log2n)二叉排序树关键字中序遍历序列的排列顺序是（）。

A:由小到大B:无序排列C:由大到小

答案:由小到大在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于（）。

A:静态查找表B:静态查找表与动态查找表C:两种表都不适合D:动态查找表

答案:动态查找表二叉排序树的查找效率与二叉树的树形有关，在（）时其查找效率最低。

A:结点太复杂B:结点太多C:完全二叉树D:呈单支树

答案:呈单支树下面关于哈希查找的说法，正确的是（）。

A:哈希表的平均查找长度有时也和记录总数有关B:哈希函数构造的越复杂越好，因为这样随机性好,冲突小。C:不存在特别好与坏的哈希函数，要视情况而定D:除留余数法是所有哈希函数中最好的

答案:不存在特别好与坏的哈希函数，要视情况而定对于线性表(7,34,55,25,64,46,20,10)进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有（）个。

A:1B:4C:2D:3

答案:4设哈希表的地址范围为0~13,哈希函数为:H(key)=key%13。用线性探测法处理冲突,输入关键字序列:(10,24,3