经典数据结构题.docx
- 文档编号:9110684
- 上传时间:2023-05-17
- 格式:DOCX
- 页数:49
- 大小:166.11KB
经典数据结构题.docx
《经典数据结构题.docx》由会员分享,可在线阅读,更多相关《经典数据结构题.docx(49页珍藏版)》请在冰点文库上搜索。
经典数据结构题
目录
第一部分选择题2
第二部分填空题19
第三部分应用题24
第一部分选择题
1.数据的四种基本逻辑结构是指()
A.数组、链表、树、图形结构B.线性表、链表、栈、广义表
C.线性结构、链表、树、图形结构D.集合、线性结构、树、图形结构
2.在以单链表为存储结构的线性表中,数据元素之间的逻辑关系用________表示
A.数据元素的相邻地址B.数据元素在表中的序号
C.指向后继元素的指针D.数据元素的值
3.顺序存储的线性表(a1,a2,a3……an),在任一结点前插入一个新结点时所需移动结点的平均次数为()
A.nB.n/2C.n+1D.(n+1)/2
4.栈和队列都是()
A.限制存取位置的线性结构B.顺序存储的线性结构
C.链式存储的线性结构D.限制存取位置的非线性结构
5.若有三个字符a、b、c依次入栈,入栈过程中可以出栈,而其不可能的出栈序列为()
A.a、b、cB.c、a、bC.c、b、aD.b、a、c
6.稀疏矩阵一般采用________方法压缩存储。
A.三维数组B.单链表
C.三元组表D.散列表
7.深度为5的二叉树至少有_______个叶子()
A.16B.15C.8D.7
8.二叉树若采用二叉链表结构表示,则对于n个结点的二叉树一定有()
A.2n个指针域,其中n个指针为NULL
B.2n个指针域,其中n+1个指针为NULL
C.2n-1个指针域,其中n个指针为NULL
D.2n-1个指针域,其中n+1个指针为NULL
9.具有3个结点的二叉树可有________种形态。
A.3B.5C.6D.9
10.在一个带权连通图G中,权值最小的边一定包含在G的()
A.最小生成树中B.深度优先生成树中
C.广度优先生成树中D.深度优先生成树中
11.能进行二分查找的线性表,必须以()
A.顺序方式存储,且元素按关键字有序
B.链式方式存储,且元素按关键字有序
C.顺序方式存储,且元素按关键字分块有序
D.链式方式存储,且元素按关键字分块有序
12.散列文件不能()
A.随机存取B.索引存取
C.按关键字存取D.直接存取
13.在题13图所示的各棵二叉树中,二叉排序树是()
14.一组记录的关键码为(46,79,56,38,40,84),则利用快速排序方法,以第一个记录为基准得到的一次划分结果为()
A.38,40,46,56,79,84B.40,38,46,79,56,84
C.40,38,46,56,79,84D.40,38,46,84,56,79
15.堆排序属于一种选择排序,其时间复杂性为()
A.O
(1)B.O(n)
C.O(n2)D.O(log2n)
16.下列数据组织形式中,()的结点按逻辑关系依次排列形成一个“锁链”。
A.集合B.树形结构
C.线性结构D.图状结构
17.数据结构可以形式化地定义为(S,△),其中S指某种逻辑结构,△是指()
A.S上的算法B.S的存储结构
C.在S上的一个基本运算集D.在S上的所有数据元素
18.下列说法正确的是()
A.线性表的逻辑顺序与存储顺序总是一致的
B.线性表的链式存储结构中,要求内存中可用的存储单元可以是连续的,也可以不连续
C.线性表的线性存储结构优于链式存储结构
D.每种数据结构都具有插入、删除和查找三种基本运算
19.设非空单链表的数据域为data,指针域为next,指针p指向单链表中第i个结点,s指向已生成的新结点,现将s结点插入到单链表中,使其成为第i个结点,下列算法段能正确完成上述要求的是()
A.s->next=p->next;p->next=s;
B.p->next=s;s->next=p->next;
C.s->next=p->next;p->next=s;交换p->data和s->data;
D.p=s;s->next=p;
20.稀疏矩阵一般采用()方法压缩存储。
A.三维数组B.单链表
C.三元组表D.散列表
21.树若用双亲链表表示,则()
A.可容易地实现求双亲及子孙的运算
B.求双亲及子孙的运算均较困难
C.可容易地实现求双亲运算,但求子孙运算较困难
D.可容易地实现求子孙运算,但求双亲运算较困难
22.将一棵有50个结点的完全二叉树按层编号,则对编号为25的结点x,该结点()
A.无左、右孩子
B.有左孩子,无右孩子
C.有右孩子,无左孩子
D.有左、右孩子
23.用邻接表作为有向图G的存储结构。
设有n个结点、e条弧,则拓扑排序的时间复杂度为()
A.O(n)B.O(n+e)
C.O(e)D.O(n*e)
24.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点,则该图一定是()
A.完全图B.连通图
C.有回路D.一棵树
25.采用线性探测法解决冲突问题,所产生的一系列后继散列地址()
A.必须大于等于原散列地址
B.必须小于等于原散列地址
C.可以大于或小于但不能等于原散列地址
D.地址大小没有具体限制
26.在对查找表的查找过程中,若被查找的数据元素不存在,则把该数据元素插入到集合中。
这种方式主要适合于()
A.静态查找表B.动态查找表
C.静态查找表与动态查找表D.两种表都不适合
27.由索引集、顺序集和数据集三部分组成的文件称为()
A.VSAM文件B.散列文件
C.顺序文件D.索引文件
28.下列有关散列文件的说法中不正确的是()
A.散列文件具有随机存放的优点
B.散列文件只能按关键字存取
C.散列文件需要索引区
D.散列文件的记录不需要进行排序
29.一组记录的键值为(12,38,35,25,74,50,63,90),按2路归并排序方法对该序列进行一趟归并后的结果为()
A.12,38,25,35,50,74,63,90B.12,38,35,25,74,50,63,90
C.12,25,35,38,50,74,63,90D.12,35,38,25,63,50,74,90
30.用快速排序方法对包含有n个关键字的序列进行排序,最坏情况下执行的时间复杂度为()
A.O(n)B.O(log2n)
C.O(nlog2n)D.O(n2)
31.下列数据结构中,()不都是线性结构。
A.栈和队列B.队列和数组
C.数组和串D.文件和队列
32.为了最快地对线性结构的数据进行某数据元素的读取操作,则其数据存储结构宜采用()方式。
A.顺序存储B.链式存储
C.索引存储D.散列存储
33.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1,则删除双链表中指针s所指结点的操作为()
A.s->t1->r1=s->t1;s->r1->t1=s->r1;
B.s->t1->r1=s->r1;s->r1->t1=s->t1;
C.s->r1=s->t1->r1;s->t1=s->r->t1;
D.s->t1=s->t1->r1;s->r1=s->r->t1;
34.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域,现要把一个指针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向链表中,则下列算法段能正确完成上述要求的是()
A.q->right=s;s->left=q;q->right->left=s;s->right=q->right;
B.s->left=q;q->right=s;q->right->left=s;s->right=q->right;
C.s->left=q;s->right=q->right;q->right->left=s;q->right=s;
D.以上都不对
35.由下列三棵树组成的森林转换成一棵二叉树为()
36.具有100个结点的完全二叉树的深度为()
A.6B.7C.8D.9
37.已知一个稀疏矩阵的三元组表如下:
(1,2,3),(1,6,1),(3,1,5),(3,2,-1),(4,5,4),(5,1,-3),则其转置矩阵的三元组表中第3个三元组为()
A.(2,1,3)B.(3,1,5)C.(3,2,-1)D.(2,3,-1)
38.无向图的邻接矩阵是一个()
A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵
39.下列说法中正确的是()
A.一个具有n个顶点的无向完全图的边数为n(n-1)
B.连通图的生成树是该图的一个极大连通子图
C.图的广度优先搜索是一个递归过程
D.对于非连通图的遍历过程中每调用一次深度优先搜索算法都得到该图的一个连通分量
40.顺序查找法与二分查找法对存储结构的要求是()
A.顺序查找与二分查找均只适用于顺序表
B.顺序查找与二分查找既适用于顺序表,也适用于链表
C.顺序查找只适用于顺序表
D.二分查找只适用于顺序表
41.在开散列表上,每个地址单元所链接的同义词表()
A.其键值相同B.其元素值相同
C.其散列地址相同D.其含义相同
42.散列文件中的记录通常成组存放,若干个记录组成一个存储单位,这个存储单位称为()
A.磁道B.块C.柱面D.桶
43.索引非顺序文件中的索引表是()
A.非稠密索引B.稠密索引
C.主索引D.多级索引
44.对n个记录的文件进行堆排序,最坏情况下的执行时间为()
A.O(log2n)B.O(nlog2n)
C.O(n)D.O(n2)
45.一组记录的关键码为(46,79,56,38,40,84),则利用快速排序方法,以第一个记录为基准得到的一次划分结果为()
A.38,40,46,56,79,84B.40,38,46,79,56,84
C.40,38,46,56,79,84D.40,38,46,84,56,79
46.下列说法正确的是( )
A.数据是数据元素的基本单位
B.数据元素是数据项中不可分割的最小标识单位
C.数据可由若干个数据元素构成
D.数据项可由若干个数据元素构成
47.数据结构的基本任务是( )
A.逻辑结构和存储结构的设计B.数据结构的运算实现
C.数据结构的评价与选择D.数据结构的设计与实现
48.在一个具有n个结点的有序单链表中插入一个新结点,并使插入后仍然有序,则该操作的时间复杂性量级为( )
A.O
(1)B.O(n)
C.O(nlog2n)D.O(n2)
49.顺序存储的线性表(a1,a2,…,an),在任一结点前插入一个新结点时所需移动结点的平均次数为( )
A.nB.n/2
C.n+1D.(n+1)/2
50.下列树U′,经剪技运算DELETE(U′,x,2)后为( )
51.一棵有16结点的完全二叉树,对它按层编号,则对编号为7的结点X,它的双亲结点及右孩子结点的编号分别为( )
A.2,14B.2,15
C.3,14D.3,15
52.设有一5阶上三角矩阵A[1..5,1..5],现将其上三角中的元素按列优先顺序存放在一堆数组B[1..15]中。
已知B[1]的地址为100,每个元素占用2个存储单元,则A[3,4]的地址为( )
A.116B.118
C.120D.122
53.一个带权的无向连通图的最小生成树( )
A.有一棵或多棵B.只有一棵
C.一定有多棵D.可能不存在
54.下列有关图遍历的说法中不正确的是( )
A.连通图的深度优先搜索是一个递归过程
B.图的广度优先搜索中邻接点的寻找具有“先进先出”的特征
C.非连通图不能用深度优先搜索法
D.图的遍历要求每一顶点仅被访问一次
55.在最坏的情况下,查找成功时二叉排序树的平均查找长度( )
A.小于顺序表的平均查找长度B.大于顺序表的平均查找长度
C.与顺序表的平均查找长度相同D.无法与顺序表的平均查找长度比较
56.闭散列表中由于散列到同一个地址而引起的“堆积”现象,是由( )
A.同义词之间发生冲突引起的
B.非同义词之间发生冲突引起的
C.同义词之间或非同义词之间发生冲突引起的
D.散列表“溢出”引起的
57.从外存设备的观点看,存取操作的基本单位是( )
A.逻辑记录B.数据元素
C.文件D.物理记录
58.对文件进行检索操作时,每次都要从第一个记录开始的文件是( )
A.顺序文件B.索引文件
C.顺序索引文件D.散列文件
59.一组记录的键值为(46,74,18,53,14,20,40,38,86,65),利用堆排序的方法建立的初始堆为( )
A.(14,18,38,46,65,40,20,53,86,74)
B.(14,38,18,46,65,20,40,53,86,74)
C.(14,18,20,38,40,46,53,65,74,86)
D.(14,86,20,38,40,46,53,65,74,18)
60.对序列(22,86,19,49,12,30,65,35,18)进行一趟排序后得到的结果如下:
(18,12,19,22,49,30,65,35,86),则可以认为使用的排序方法是( )
A.选择排序B.冒泡排序
C.快速排序D.插入排序
61.下列数据组织形式中,( )的各个结点可以任意邻接。
A.集合B.树形结构
C.线性结构D.图状结构
62.设某二维数组A[1..n,1..n],则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为( )
A.O(log2n)B.O(n)
C.O(nlog2n)D.O(n2)
63.在线性表的下列存储结构中,读取元素花费时间最少的是( )
A.单链表B.双链表
C.循环链表D.顺序表
64.将一个头指针为p的单链表中的元素按与原单链表相反的次序存放,则下列算法段中的空白处应为
q=NULL;
while(p!
=NULL)
{
( )
}
p=q;
A.r=q;q=p;p=p->next;q->next=r;
B.q=p;r=q;p=p->next;q->next=r;
C.r=q;p=p->next;q=p;q->next=r;
D.q=p;p=p->next;r=q;q->next=r;
65.数组通常具有两种基本运算,即( )
A.创建和删除B.索引和修改
C.读和写D.排序和查找
66.除根结点外,树上每个结点( )
A.可有任意多个孩子、任意多个双亲
B.可有任意多个孩子、一个双亲
C.可有一个孩子、任意多个双亲
D.只有一个孩子、一个双亲
67.具有100个结点的二叉树中,若用二叉链表存储,其指针域部分用来指向结点的左、右孩子,其余( )个指针域为空。
A.50B.99
C.100D.101
68.邻接表是图的一种( )
A.顺序存储结构B.链式存储结构
C.索引存储结构D.散列存储结构
69.如果无向图G必须进行二次广度优先搜索才能访问其所有顶点,则下列说法中不正确的是( )
A.G肯定不是完全图B.G一定不是连通图
C.G中一定有回路D.G有2个连通分量
70.若构造一棵具有n个结点的二叉排序树,最坏的情况下其深度不会超过( )
A.n/2B.n
C.(n+1)/2D.n+1
71.若用二分查找法取得的中间位置元素键值大于被查找值,说明被查找值位于中间值的前面,下次的查找区间为从原开始位置至( )
A.该中间位置B.该中间位置-1
C.该中间位置+1D.该中间位置/2
72.散列文件不能( )
A.随机存取B.索引存取
C.按关键字存取D.直接存取
73.若检索顺序文件各个记录的概率相同,设文件占用的页块数为n,则按关键字存取时的平均访问外存次数为( )
A.n/2B.nC.n/4D.logn
74.下列关键码序列中,属于堆的是( )
A.(15,30,22,93,52,71)B.(15,71,30,22,93,52)
C.(15,52,22,93,30,71)D.(93,30,52,22,15,71)
75.已知10个数据元素为(54,28,16,34,73,62,95,60,26,43),对该数列按从小到大排序,经过一趟冒泡排序后的序列为( )
A.16,28,34,54,73,62,60,26,43,95
B.28,16,34,54,62,73,60,26,43,95
C.28,16,34,54,62,60,73,26,43,95
D.16,28,34,54,62,60,73,26,43,95
76.要将现实生活中的数据转化为计算机所能表示的形式,其转化过程依次为( )
A.逻辑结构、存储结构、机外表示B.存储结构、逻辑结构、机外表示
C.机外表示、逻辑结构、存储结构D.机外表示、存储结构、逻辑结构
77.若评价算法的时间复杂性,比较对数阶量级与线性阶量级,通常( )
A.对数阶量级复杂性大于线性阶量级
B.对数阶量级复杂性小于线性阶量级
C.对数阶量级复杂性等于线性阶量级
D.两者之间无法比较
78.下列关于线性表的基本操作中,属于加工型的操作是( )
A.初始化、求表长度、插入操作B.初始化、插入、删除操作
C.求表长度、读元素、定位操作D.定位、插入、删除操作
79.在一个单链表中,若p所指结点不是最后结点,s指向已生成的新结点,则在p之后插入s所指结点的正确操作是( )
A.s–>next=p–>next;p–>next=s;B.p–>next=s–>next;s–>next=p;
C.s–>next=p;p–>next=s;D.s–>next=p–>next;p=s;
80.若有三个字符的字符串序列执行入栈操作,则其所有可能的输出排列共有( )
A.3种B.4种
C.5种D.6种
81.C语言对数组元素的存放方式通常采用( )
A.按行为主的存储结构B.按列为主的存储结构
C.按行或列为主的存储结构D.具体存储结构无法确定
82.根据定义,树的叶子结点其度数( )
A.必大于0B.必等于0
C.必等于1D.必等于2
83.二叉树若采用二叉链表结构表示,则对于n个结点的二叉树一定有( )
A.2n个指针域其中n个指针为NULL
B.2n个指针域其中n+1个指针为NULL
C.2n-1个指针域其中n个指针为NULL
D.2n-1个指针域其中n+1个指针为NULL
84.在一个无向图中,所有顶点的度数之和等于边数的( )
A.1倍B.2倍
C.3倍D.4倍
85.若采用邻接表存储结构,则图的广度优先搜索类似于二叉树的( )
A.先根遍历B.中根遍历
C.后根遍历D.层次遍历
86.采用顺序查找法,若在表头设置岗哨,则正确的查找方式通常为( )
A.从第0个元素开始往后查找该数据元素
B.从第1个元素开始往后查找该数据元素
C.从第n个元素开始往前查找该数据元素
D.从第n+1个元素开始往前查找该数据元素
87.下列查找中,效率最高的查找方法是( )
A.顺序查找B.折半查找
C.索引顺序查找D.分块查找
88.索引文件通常由索引表和主文件两部分构成,其中( )
A.索引表和主文件均必须是有序文件
B.索引表和主文件均可以是无序文件
C.索引表必须是有序文件
D.主文件必须是有序文件
89.直接插入排序算法,其时间复杂性为( )
A.O
(1)B.O(n)
C.O(nlog2n)D.O(n2)
90.下列排序方法中,属于稳定的排序方法是( )
A.直接插入排序法B.快速排序法
C.冒泡排序法D.堆排序法
91.数据的四种基本逻辑结构是指()
A.数组、链表、树、图形结构B.线性表、链表、栈队列、数组广义表
C.线性结构、链表、树、图形结构D.集合、线性结构、树、图形结构
92.数据结构中,通常采用两种方法衡量算法的时间复杂性,即()
A.最大时间复杂性和最小时间复杂性
B.最好时间复杂性和最坏时间复杂性
C.部分时间复杂性和总体时间复杂性
D.平均时间复杂性和最坏时间复杂性
93.下列关于线性表的叙述中,不正确的是()
A.线性表是n个结点的有穷序列
B.线性表可以为空表
C.线性表的每一个结点有且仅有一个前趋和一个后继
D.线性表结点间的逻辑关系是1:
1的联系
94.在一个单链表中,若p所指结点不是最后结点,则删除p所指结点的后继结点的正确操作是()
A.p=p->nextB.p->next=p->next
C.p->next=p->next->nextD.p->next=p
95.栈和队列()
A.共同之处在于二者都是先进先出的特殊的线性表
B.共同之处在于二者都是先进后出的特殊的线性表
C.共同之处在于二者都只允许在顶端执行删除操作
D.没有共同之处
96.二维数组A[5][6]采用按列为主序的存储方式,每个元素占3个存储单元,若A[0][0]的存储地址是100,则A[4][3]的存储地址是()
A.127B.142C.150D.157
97.深度为k的二叉树至多有()
A.2k个结点B.2k-1个结点
C.2k-1个结点D.2k-1-1个结点
98.对于如图所示二叉树采用中根遍历,正确的遍历序列应为()
A.ABCDEFB.ABECDF
C.CDFBEAD.CBDAEF
99.下面关于生成树的描述中,不正确的是()
A.生成树是树的一种表现形式
B.生成树一定是连通的
C.生成树一定不含有环
D.若生成树顶点个数为n,则其边数一定为n-1
100.图的邻接表如下所示,从顶点V1出发采用深度优先搜索法遍历该图,则可能的顶点序列是()
A.V1V2V3V4V5B.V1V2V3V5V4
C.V1V4V3V5V2D.V1V3V4V5V2
101.下列查找方法中,不属于动态的查找方法是()
A.二叉排序树法B.平衡树法
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 经典 数据结构