数据结构复习题Word文件下载.docx
《数据结构复习题Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构复习题Word文件下载.docx（24页珍藏版）》请在冰点文库上搜索。
7.在单链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（C）存储方式。
A、顺序表B、用头指针标识的循环单链表
C、用尾指针标识的循环单链表D、双向链表
8.在一个单链表中的p和q两个结点之间插入一个新结点s，则修改链接的语句为（）。
A、s->
next=p;
q->
next=s;
B、p->
next=s->
next;
s->
C、q->
D、p->
next=q;
9.在一个长度为n的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（C）。
A、O
（1）B、O（long2n）C、O（n）D、O（n2）
10.要将一个顺序表（a0，a1，……，an-1）中的数据元素ai（0<
=i<
=n-1）删除，需要移动（C）个数据元素。
A、iB、n-i-1C、n-iD、n-i+1
11.在栈中存取数据的原则是（B）。
A、先进先出B、先进后出C、后进先出D、没有限制
12.若将整数1,2,3,4依次进栈，则不可能得到的出栈序列是（D）。
A、1234B、1324C、4321D、1423
13.在链栈中进行出栈操作时（B）。
A、需要判断栈是否满B、需要判断栈是否空
C、需要判断栈元素的类型D、无须对栈做任何判断
将递归算法转换成对应的非递归，使用栈保存中间结果
14.在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxsize,则顺序栈的判空条件是（B）。
A、top==0B、top==-1C、top==maxsizeD、top==maxsize-1
15.在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxsize,则顺序栈的判满条件是（D）。
16.在队列中存取数据元素的原则是（A）。
A、先进先出B、先进后出C、后进后出D、没有限制
17.在循环顺序队列中，假设以少用一个存储单元的方法来区分判断队满和队空的条件，front和rear分别为队头和队尾指针，他们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxsize，则队列的判空条件是（A）。
A、front==rearB、front!
=rear
C、front==rear+1D、front==（rear+1）%maxsize
18.在循环顺序队列中，假设以少用一个存储单元的方法来区分判断队满和队空的条件，front和rear分别为队头和队尾指针，他们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxsize，则队列的判满条件是（D）。
19.在循环顺序队列中，假设以少用一个存储单元的方法来区分判断队满和队空的条件，front和rear=--为队头和队尾指针，他们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxsize，则队列的长度是（C）。
A、rear-frontB、rear-front+1
C、（rear-front+maxsize）%maxsizeD、（rear-front+1）%maxsize
20．设长度为n的链队列采用单循环链表表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度为（B）。
A、O
（1）B、O（n）C、O（long2n）D、O（n2）
21.下面关于串的叙述中，（ B ）是不正确的。
A、模式匹配是串的一种重要运算B、空串是由空格构成的串
C、串既可以采用顺序存储，也可以采用链式存储D、串是字符的有限序列
22.串是一种特殊的线性表，其特殊性体现在（D）。
A、可以顺序存储B、数据元素是一个字符
C、可以链式存储D、数据元素可以是多个字符
23.串的长度是指（B）。
A、串中所含不同字母的个数B、串中所含字符的个数
C、串中所含不同字符的个数D、串中所含非空格字符的个数
24.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（C）。
A、求子串B、连接C、模式匹配D、求串长
25.若串S=’software’，其子串的个数是（A）。
A、8B、37C、36D、9
26.常对数组进行的两种操作是（C）。
{顺序存储}
A、建立与删除B、索引与修改C、查找与修改D、查找与索引
27.数组A[0…5，0…6]的每个元素占5个字节，将其按列优先的次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是（A）。
A、1175B、1180C、1205D、1210
28.对稀疏矩阵进行压缩存储的目的是（C）。
A、便于进行矩阵运算（缺点）B、便于输入和输出（缺点）
C、节省存储空间D、降低运算的时间复杂度（缺点）
29.顺序查找法适合于存储结构为（B）的线性表。
A、散列存储B、顺序存储或链式存储
C、压缩存储D、索引存储
30.若查找每个记录的概率相等，则在具有n个记录的连续顺序文件中采用顺序查找法法查找一个记录，其平均查找长度ASL为（B）。
A、（n-1）/2B、n/2C、（n+1）/2D、n
31.适用于折半查找的表的存储方式及元素排列要求为（D）。
A、链表方式存储，元素无序B、链表方式存储，元素有序
C、顺序方式存储，元素无序D、顺序方式存储，元素有序
32.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度（）。
A、必定快B、不一定快
C、在大多数情况下要快D、取决于表递增还是递减
33.树形结构是指元素之间存在一种（D）。
A、一对一关系B、多对多关系C、多对一关系D、一对多关系
34.在一棵二叉树上第四层的结点数最多为（D）。
第i层至多有2^i-1个节点
A、2B、4C、6D、8
35.一棵深度为k的满二叉树的结点总数为（A）。
A、2k-1B、2k-1C、2k+1D、2k
36.一棵深度为k的完全二叉树的最少结点数为（A）。
37.一棵深度为k的完全二叉树的最多结点数为（A）。
38.树最适合用来表示（B）。
A、有序数据元素B、元素之间具有层次关系的数据
C、无序数据元素D、元素之间无联系的数据
39.设森林F中有3棵树，其中树的结点数依次为M1，M2，M3，则与F对应的二叉树的根结点的右子树上的结点数为（D）。
A、M1B、M1+M2C、M3D、M2+M3
40.讨论树、森林和二叉树的关系，是为了（B）。
A、借助二叉树上的运算方法去实现树的一些运算
B、将树、森林按二叉树的存储方式进行存储
C、将树、森林转换为二叉树
D、体现一种技巧，没有什么实际意义
41.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（C）。
A、250B、500C、501D、505
42．下列说法中正确的是（D）。
A、任何一个二叉树中至少有一个结点的度为2
B、任何一个二叉树中每个结点的度都可以大于2最大是2
C、任何一个二叉树中结点的度均为2
D、任何一个二叉树中结点的度可以小于2
43．在下列情况中，可称为二叉树的是（C）。
A、每个结点至多有两棵子树的树
B、每个结点只有一棵左子树的树
C、每个结点至多有两棵子树的有序树
D、每个结点只有一棵右子树的树
44.下面几组编码集合中，不是前缀编码的是（）。
A、{0，10，110，1111}B、{11，10，001，101，0001}
C、{00，010，0110，1000}D、{b，c，aa，ac，aba，abb，abc}
45.图中有关路径的定义是（A）。
A、由顶点和相邻顶点构成的边所形成的序列
B、由不同顶点所形成的序列
C、由不同边所形成的序列
D、上述定义都不是
带权路径长度WPL=权值i*路径长度l
完全二叉树的路径长度=
46.以下说法正确的是（B）。
A、连通分量是无向图中的极小连通子图
B、强连通分量是有向图中的极大强连通子图
C、在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧<
a,b>
D、对有向图G，如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图
47.要连通具有n个顶点的有向图，至少需要（A）条弧。
A、n-1B、nC、n+1D、2n
48.（B）的邻接矩阵是对称矩阵。
A、有向图B、无向图C、AOV网D、AOE网
49.以下说法不正确的是（C）。
A、图的遍历是从给定的源点出发访问图中的每一个顶点且仅访问一次
B、图的遍历算法有两种：
深度优先和广度优先
C、图的深度遍历不适合用于有向图
D、图的深度遍历是一个递归过程
50.在图采用邻接表存储时求最小生成树的Prim算法的时间复杂度为（B）。
邻接矩阵储存则是CPrim算法的时间复杂度是（
o（n*n）
），适用于求（
稠密
）图的最小生成树；
kruskal算法的时间复杂度是（
O（eloge）
稀疏
）图的最小生成树。
A、O（n）B、O（n+e）C、O（n2）D、O（n3）
51.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（D）。
有向图G可拓扑排序的判别条件是不存在环
A、G中有弧<
Vi，Vj>
B、G中有一条Vi到Vj的路径
C、G中没有弧<
D、G中有一条Vj到Vi的路径
52.下列关于AOE网的叙述中不正确的是（）。
A、关键活动不按期完成就会影响整个工程的完成时间
B、任何一个关键活动提前完成，那么整个工程将会提前完成
C、所有关键活动都提前完成，那么整个工程将会提前完成
D、某些关键活动提前完成，那么整个工程将会提前完成
AOE网为边表示活动的网，是一个带权的（有向图，其长度最长的路径称为关键路径。
在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为（关键路径）。
9、AOV网中,结点表示（活动,边表示（活动时间的优先关系）。
AOE网中,结点表示（事件）,边表示（活动10、在AOV网中，存在环意味着（某项活动应以自己为先决条件），这是荒谬的；
对程序的数据流图来说，它表明存在（死循环
53.当采用分块查找时，数据的组织方式为（B）。
A、数据分成若干块，每块内数据有序
B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D、数据分成若干块，每块（除最后一块外）中数据个数需相同
54.散列表的平均查找长度（A）。
A、与处理冲突方法有关而与表的长度无关
B、与处理冲突方法无关而与表的长度有关
C、与处理冲突方法有关，与表的长度也有关
D、与处理冲突方法无关，与表的长度也无关
55.内部排序算法的稳定性是指（B）。
A、该排序算法不允许有相同的关键字记录
B、该排序算法允许有相同的关键字记录
C、平均时间为O（nlogn）的排序算法
D、以上都不对
56.在下列排序算法中，算法（D）的时间复杂度与初始排序序列无关。
A、直接插入排序B、冒泡排序
C、快速排序D、简单选择排序
57.一组记录的关键字为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准记录得到的一次划分结果为（C）。
A、（38,40,46,56,79,84）B、（40,38,46,79,56,84）
C、（40,38,46,56,79,84）D、（40,38,46,84,56,79）
58.对关键字序列（70,55,100,15,33,65,50,40,95）进行直接插入排序时，把65插入，需要比较（）次关键字。
A、2B、3C、6D、8
59.当待排序序列基本有序时，以下排序方法中，（B）最不利于其优势的发挥。
A、直接选择排序B、快速排序
C、冒泡排序D、直接插入排序
60.在待排序序列局部有序时，效率最高的排序算法是（B）。
C、归并排序D、直接插入排序
61.若需要利用形式参数直接访问修改实参值，则应将形参说明为（）。
A、指针B、值参数C、局部变量D、全局变量
62.执行下面程序段的时间复杂度为（C）。
for（i=0;
m;
i++）
for（j=0;
n;
a[i][j]=i*j;
A、O（m2）B、O（mn）C、O（n2）D、O（m+n）
63.执行下面程序段时，语句S的执行次数为（D）。
=i;
S;
A、n2B、n2/2C、n（n+1）D、（n+1）（n+2）/2
64.为解决计算机主机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区。
主机将要打印输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据打印。
该缓冲区的逻辑结构应该是（C）。
汽车加油站、模拟打印机缓冲区、CPU分时系统等方面。
A、树B、栈C、队列D、图
65.设栈S和队列Q的初始状态均为空，元素a、b、c、d、e、f、g依次进入栈S。
如果每个元素出栈后立即进入队列Q，且7个元素出队的顺序为bdcfeag，则栈S的容量至少是（）。
A、1B、2C、3D、4
66.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，元素a、b、c、d、e依次入队，则不可能得到的出队顺序是（C）。
A、bacdeB、dbaceC、dbcaeD、ecbad
二、填空题。
1．数据的逻辑结构包括（线性结构、树形结构和图形结构，存储结构包括（顺序存储）、（链接存储）、（索引存储）、（散列存储）。
2.数据结构的主要研究内容是（数据的逻辑结构、存储结构和数据的运算
3.冒泡排序算法的时间复杂度是（n^2）。
4.下面程序段的时间复杂度是（）。
sum=1;
for（i=0;
sum<
i++）sum+=1;
5.为了便于讨论，有时将含有n（n>
=0）个节点的线性结构表示成（a1，a2，……，an），其中每个ai代表一个（），a1称为（）节点，an称为（）节点，i称为ai在线性表中的（）。
对任意一对相邻节点ai，ai+1（1<
=n），ai称为ai+1的（），ai+1称为ai的（）。
6.线性结构的基本特征是：
若至少含有两个节点，则除起始节点没有直接（前驱）外，其他节点有且仅有一个直接（直接前驱）；
除终端节点没有直接（后继）外，其他节点有且仅有一个直接（后继）。
7.线性表的常见链式存储结构有（单向链表）、（双向链表）、（循环链表）。
8.在顺序表（a1，a2，……，an）的第i（1<
=n）个位置之前插入一个新的数据元素，会引起（i/2）个数据元素的移动操作。
9.在线性表的单链表存储结构中，每一个结点有两个域，一个是数据域，用于存储数据元素本身；
另一个是（结点指针），用于存储后继结点的地址。
10.在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中则只能进行（插入）存取。
11.顺序表中逻辑上相邻的数据元素，其物理位置（一定）相邻，而在单链表中逻辑上相邻的数据元素，其物理位置（不一定）相邻。
12.在含有N个结点的单链表，若要删除一个指定的结点p则首先必须找到（头指针），其时间复杂度为（）。
13.线性表通常采用（链式存储结构）和（顺序存储结构）两种存储结构。
若线性表的长度确定或变化不大，则适合采用（顺序存储结构）进行存储。
14.在仅设置了尾指针的循环链表中，访问第一个结点的时间复杂度（）。
15.栈是一种操作受限制的特殊线性表，其特殊性体现在插入和删除操作都限制在表的一端进行。
允许插入和删除操作的一端称为（），二另一端称为（）。
16.栈有两种存储结构，分别是（）和（）；
以这两种存储结构存储的栈分别称为（）和（）。
17.在不带头结点的链栈中，若栈顶指针top直接指向栈顶元素，则将一个新结点p入栈时修改链接的语句为（）和（）。
18.在不带头结点的链栈中，若栈顶指针top直接指向栈顶元素，则将栈顶元素出栈时修改链接的语句为（）、（）和（）。
19.队列也是一种操作受限制的特殊线性表，与栈不同的是，队列中所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为（），允许删除的一端称为（）。
20.由于队列的插入和删除操作分别在队头和队尾进行，因此，在链式存储结构中需要设置两个指针分别指向（）和（），这两个指针又分别称为（）和（）。
21.循环顺序队列是将顺序队列的存储区域看成是一个首尾相连的环，首尾相连的状态是通过数学上的（）运算来实现的。
22.在循环顺序队列中，若规定当front==rear时，循环队列为空，当front==（rear+1）%maxsize时，循环队列为满，则入队操作时队尾指针变化的相应语句为（）；
出队操作时队尾指针变化的相应语句为（）。
23.无论是顺序栈还是顺序队列，插入元素时必须先进行（）判断，删除元素时必须先进行（）判断；
而链栈或链队列中，插入元素不必进行栈或队列是否为满的判断，只要在删除元素时先进行栈或队列是否为空的判断。
24.含零个字符的串称为（）。
任何串中所含（）的个数称为该串的长度。
25.当且仅当两个串的（）相等并且各个对应位置上的字符都（）时，这两个串相等。
一个串中任意个连续字符组成的序列称为该串的（），该串称为它的所有子串的（）。
26.通常采用（）存储结构来存储数组。
对二维数组可有两种存储方法：
一种是以（）为主序的存储方式，另一种是以（）为主序的存储方式。
27.所谓稀疏矩阵是指（）。
28.在一棵度为m的树中，如果度为1的结点有n1个，度为2的结点有n2个，……，度为m的结点有nm个，则这棵树中的叶子结点的个数为（）。
29.树的存储结构包括（）、（）和（）。
30.若一棵完全二叉树的第4层有7个节点，则这棵完全二叉树的结点的总数为（）。
31.在哈夫曼树中，任何一个结点的度都是（）。
32.若对一棵完全二叉树按层次从0开始进行结点编号，且每层按从左到右的顺序编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中，其余类推，则A[i]的左孩子编号为（），右孩子编号为（），双亲编号为（）。
33.具有10个顶点的无向图，边的总数最多为（）。
34.在有向图的邻接矩阵表示中计算第i个顶点入度的方法是（）。
35.构造连通网的最小生成树的两个典型算法是（）和（）。
36.有向图G可拓扑排序的判别条件是（）。
37.AOV网中，顶点表示（），弧表示（）。
AOE网中，顶点表示（），弧表示（）。
38.顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为（）次；
当使用监视哨时，若查找失败，则比较关键字的次数最多为（）。
39.在顺序表（8,11,15,19,25,25,30,33,42,48,50）中，用二分法（折半法）查找关键码值20，需进行的关键码比较次数为（）。
40.一个无序序列可以通过构造一棵（）树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
41.执行排序操作时，根据使用的存储器可将排序算法分为（）和（）。
42.在对一组记录序列（50,40,95,20,15,70,60,45,80）进行直接插入排序时，当把第7个记录60插入到有序表中时，为寻找插入位置需比较（）次。
43.在直接插入排序和直接选择排序中，若初始序列基本有序，则选用（）法效率更高。
44.在对一组记录序列（50,40,95,20,15,70,60,45,80）进行直接选择排序时，第4次交换和选择后，未排序记录为（）。
45.n个记录的冒泡排序算法所需的最多移动次数为（），最少移动次数为（）。
46.对n个结点进行快速排序，最多的比较次数为（）。
47.在归并排序中，若待排序记录的个数为20，则共需要进行（）趟归并。
48.内部排序算法的稳定性是指（）。
49.一棵二叉树中度为1的结点个数为5，度为2的结点有3个，则这棵二叉树中的叶子结点的个数为（）。
50.一棵有100个结点的完全二叉树，其叶子结点的个数为（）。
51.变量的作用域是指（）。
52.抽象数据类型具有（）和（）的特点。
53.一种抽象类型包括（）、（）和（）。
54.在线性结构、树状结构和图结构中，数据元素之间分别存在着（）、（）和（）联系。
55.算法是规则的有限集合，是为解决特定问题而规定的（）。
56.算法具有有穷性/确定性/可行性/输入/输出/确定性/和输出/五大特性。
57.线性表通常采用顺序存储和链式存储两种存储结构。
在顺序表中，线性表的长度在定义数组时就已确定，是（）保存；
在链表中，整个链表由“头指针”来指示，单链表的长度是（）保存。
三、判断题。
1.给定任意一棵树都可以找到一棵对应的二叉树
升级会员 