数据结构模拟试题及答案.doc
《数据结构模拟试题及答案.doc》由会员分享，可在线阅读，更多相关《数据结构模拟试题及答案.doc（17页珍藏版）》请在冰点文库上搜索。
如有帮助欢迎下载支持
数据结构模拟试题一
一、判断题（每小题1分，共15分）
1.计算机程序处理的对象可分为数据和非数据两大类。
2.全体自然数按大小关系排成的序列是一个线性表。
3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。
4.顺序栈是一种规定了存储方法的栈。
5.树形结构中的每个结点都有一个前驱。
6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。
7.若某顶点是有向图的根，则该顶点的入度一定是零。
8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。
9.用一维数组表示矩阵可以节省存储空间。
10.广义表的长度与广义表中含有多少个原子元素有关。
11.分块查找的效率与线性表被分成多少块有关。
12.散列表的负载因子等于存入散列表中的结点个数。
13.在起泡排序过程中，某些元素可能会向相反的方向移动。
14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。
15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。
二、填空题（每空1分，共15分）
1.顺序表是一种_____________线性表。
2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。
3.栈和队列的区别在于________的不同。
4.在高度为h（h≥0）的二叉树中至少有___个结点，至多有___个结点。
5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域为空的结点。
6.n个顶点的有根有向图中至少有___条边，至多有___条边。
7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。
8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是_____。
9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。
10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。
三、选择题（每题2分，共30分）
1.计算机所处理的数据一般具有某种内在联系性，这是指________。
A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系
C．元素内部具有某种结构D．数据项和数据项之间存在某种关系
2.假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4。
若把新插入元素存入R[6]，则________。
A．会产生运行错误B．R[1]~R[6]不构成一个顺序表
C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率
D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦
3.设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。
当P指向链表最后一个结点时，_________。
A．P所指结点指针字段的值为空B．P的值与H的值相等
C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等
4.栈的定义不涉及数据的__________。
A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构
5.设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。
A．2,4,1,3,5B．3,4,1,5,2C．3,2,4,1,5D．4,1,3,2,5
6.若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。
A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在
7.对于一棵具有n个结点，度为3的树来说，____________。
A．树的高度至多是n-3B．树的高度至多是n-2C．树的最低高度是┏log3（n+1）┓
D．至少在某一层上正好有3个结点
8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。
A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点
D．是一个有根有向图
9.特殊矩阵用行优先顺序表表示，_____________
A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素
C．无法根据行列号计算矩阵元素的存储地址D．可以节省存储空间
10.对一个非空的广义表来说，______________。
A．可能不含任何原子元素B．至少含一个原子元素
C．其长度不小于其中任何一个子表的长度D．至少含一个非空的子表元素
11.在有序表（2,4,6,8,10,12,14,16,18,20）上用折半查找方法查找13，依次被比较的是___________。
A．10,16,12,14B．10,16,12C．12,16,14D．10,16,12,13
12.含14个结点的平衡二叉排序树，其最大深度是____。
A．4B．5C．6D．7
13．如果元素R1和R2有相同的排序码，并且进行归并排序前，R1在R2的前面，则当排序结束后，___________。
A．R1有可能在R2的后面B．R1一定在R2的后面
C．R1一定在R2的前面D．选择R1或R2中的一个留在线性表中
14.下面4个序列中，只有___满足堆的定义。
A．13,27,49,76,76,38,85,97B．76,38,27,49,76,85,13,97
C．13,76,49,76,27,38,85,97D．13,27,38,76,49,85,76,97
15．下面4种排序方法中，属于不稳定的排序方法是_________排序和_________排序。
A．快速B．归并C．简单选择D．折半插入
四、图表题
1.已知树结点的前序序列是abcdefgh ，后序序列是cdebfhga，请画出这棵树的逻辑结构图。
2.采用基数排序法，对排序码序列572,586,413,15,724,529,525,608,37,119按从小到大的次序排序，请写出每趟收集后的线性表。
五、算法填空题
假设G是n个顶点的连通无向图的邻接矩阵。
下面的算法可用于对无向图进行深度遍历。
请在空内填入适当内容，将算法补充完整。
Constn=10;
IntG[n][n];
Voidtrav（inti）{
Intj,t;
IntM[n],S[n];
Cout<M[i]=1;//做已访问标记
T=1;s[t]=I;//进栈
Do{
（1）_______________
While
（2）_______________
I++;
If（i>n）（3）_______
Else{
Cout<（4）_______
S[++t]=I;
}
}while（t）
}
六、算法设计题（每小题12分，共24分）
1.假设长度为n的线性表已存放在R[1]~R[n]中，元素类型为整型。
请写一个算法，给每个元素加上一个常数x，若相加后该元素为0，则将该元素从线性表中删除。
2.在一个m行n列的矩阵中，由相邻的并且取值相同的元素所构成的集合称为区域。
例如，在图1所示矩阵中存在5个区域。
设计算法setcolor（x,y,c），算法的功能中将x行y列元素所在区域的所有元素的值改为c。
例如，对图1所示矩阵执行算法调用setcolor（4,3,1），应得结果如图2所示。
3022031221
0020011211
3033031331
3003031131
3300033111
图1图2
数据结构模拟试题二
一．判断题（每小题1分，共15分）
1.构成数据的最小单位是数据项。
2.空线性表的一个特性是线性表中各结点尚未赋值。
3.非循环单向链表一定要有表头指针。
4.顺序栈的栈顶指针是一个指针类型的变量。
5.在表示树的双亲数组中，找结点的双亲要比找结点的孩子容易。
6.哈夫曼树中不存在度为1的结点。
7.在图中，与Vi相邻的顶点其序号一定是i+1或i-1。
8.如果是不连通的无向图，则在相应的邻接表中一定有空链表。
9.矩阵的行数和列数可以不相等。
10.广义表的深度与广义表中含有多少个子表元素有关。
11.折半查找可以在有序的双向链表上进行。
12.散列查找过程中，关键字的比较次数和散列表中关键字的个数直接相关。
13.对n个元素执行简单选择排序，排序码的比较次数总是n（n-1）/2次。
14.物理记录的大小与逻辑记录的大小成正比。
15.对索引文件，索引表是建立在内存的，数据区是建立在外存的。
二．填空题（每空1分，共15分）
1.在程序中，描述顺序表的存储空间一般用________变量。
2.若用Q[0]~Q[100]作为循环顺序队列的存储空间，用“队首指针f的值等于队尾指针r的值”作为队空的标志，则创建一个空队列所要执行的操作是___________。
3.栈和顺序栈的区别仅在于________。
4.n个结点的二叉树最大高度是___，最小高度是___。
5.树的存储方法主要有_____、_____和_____三种。
6.n个顶点的强连通图中至少有___条边。
7.10行20列矩阵若用列优先顺序表来表示，则矩阵中第7行第6列元素是顺序表中第___个元素。
8.在各元素查找概率相等的情况下，在含有14个元素的平衡二叉排序树上查找其中一个元素，元素间的平均比较次数至少是_____次，至多是______次。
9.对n个元素执行快速排序，在进行第一次分组时，元素的移动次数至多是____次，至少是___次。
10.在B-树中，若某结点有i个孩子，则该结点中一定有___个关键字。
三．选择题（每题2分，共30分）
1.数据结构的研究内容不涉及________。
A．算法用什么语言来描述B．数据如何存储
C．数据的运算如何实现D．数据如何组织
2.若H1是动态单向链表的表头指针，H2是动态双向链表的表头指针，则________。
A．H1和H2占用同样多的内存空间B．H1和H2是同类型的变量
C．H2要比H1占用更多的内存空间
D．双向链表要比单向链表占用更多的内存空间
3.对于K个带头结点的静态单向链表来说，若各结点类型相同，则K个链表一般可共用_________。
A．同一个数组B．某些数组元素C．同一个表头结点D同一个表头指针
4.最不适合用作链接栈的链表是_____________。
A．只有表头指针没有表尾指针的循环双向链表
B．只有表尾指针没有表头指针的循环双向链表
C．只有表尾指针没有表头指针的循环单向链表
D．只有表头指针没有表尾指针的循环单向链表
5.栈和队列的共同点在于_____________。
A．都对存储方法作了限制B．都是只能进行插入、删除运算C．都对插入、删除的位置作了限制D．都对插入、删除两种操作的先后顺序作了限制
6.如果5个元素的出栈的顺序是1,2,3,4,5，则进栈的顺序可能是_____________。
A．3,5,4,1,2B.1,4,5,3,2C.2,4,3,1,5D.5,1,3,2,4
7.若某棵二叉树结点的后序序列和层次序列正好相反，则该二叉树_____________。
A．每个结点都没有右孩子B．不存在度为2的结点C．每个结点都没有左孩子D．不存在
8.对于一棵具有n个结点，度为3的树来说，树的高度至少是____________。
A．┏log32n┓B．┏log3（3n-1）┓C．┏log3（3n+1）┓D．┏log3（2n+1）┓
9．对n个顶点的带权连通图来说，它的最小生成树是指图中任意一个由n-1条__________。
A．权值最小的边构成的子图B．权值之和最小的边构成的子图C．权值之和最小的边构成的连通子图D．权值之和最小的边构成的无环子图
10.所谓特殊矩阵是指_____________比较特殊。
A．矩阵元素之间的关系B．矩阵的处理方法
C．矩阵元素的取值D．矩阵的存储方法
11.若长度为n且有n种不同原子的广义表用链接方法存储，则时间复杂度为O（n）的运算是___________。
A．复制一个广义表B．求广义表的长度C．查找某个子表D．查找某个原子
12.待查找元素关键字的值依次是47，且已存入变量k中，如果在查找过程中，和K进行比较的关键字值依次是47,32,46,25,47,则采用的查找方法____。
A．是一种错误的查找方法B．可能是分块查找C．可能是顺序查找D．可能是折半查找
13．如果元素R1和R2有相同的排序码，并且进行堆排序前，R1在R2的前面，则当排序结束后，___________。
A．R1一定在R2的前面B．R1一定在R2的后面
C．R1有可能在R2的后面D．选择R1或R2中的一个留在线性表中
14.下面4种排序方法中，属于稳定的排序方法是_________排序和_________排序。
A．堆B．基数C.快速D.起泡
15．在线性表中元素很多，且各元素已有序排列的情况下，执行_______排序或_________排序，排序码比较次数最多。
A．简单选择B．堆C．归并D．堆
四．图表题（每小题4分，共8分）
1.已知5个叶子结点的权值分别为2，5，5，6，9，13请画出相应的哈夫曼树。
2.对图1所示无向网络，画出从顶点V6开始用普里姆方法构造的最小生成树。
五．算法填空题（每空2分，共8分）
假设待排序的n个元素已存放在顺序表R[1]~R[n]中，排序码字段名是key。
下面的算法用于对顺序表进行归并排序，请在空内填入适当内容，将算法补充完整。
Voidmergesort（listR,listS,inti,intj）{
Inta,b,c,k;
If（I{
K=（i+j）/2;
mergesort（R,S,i,k）;
mergesort（R,S,k+1,j）;
（1）____________________________
While（（a<=k）&&（b<=j））
{
If（R[a].key<=R[b].key）
{S[c]=R[a];
a++;
}
Else{
（2）____________________________
}
c++;
}
（3）____________________________
While（b<=j）
{
S[c]=R[b];
b++;
c++;
}
（4）____________________________
}
}
六．算法设计题（每小题12分，共24分）
1.假设head是某个带头结点单链表的表头指针，每个结点数值字段的类型为整型。
写一个算法，从该链表中删除一个值最大的结点，并将该结点的值存入表头结点的数值字段。
2.如果一个十进制正整数首位数字不为零，而且从左往右读和从右往读都一样，则称其为回文数。
对一个n位的正整数x，反复执行下列操作，有可能得到一个回文数：
（1）生成一个位数和x相同的正整数y，其中yi=xn-i+1,i=1,2,3…;
（2）将y累加到x中。
如对于正整数87，按上述方法重复4次后，将得到回文数4884：
87+78=165165+561=726726+627=13531353+3531=4884
写一个按上述方法求回文数的算法。
要求：
x的初始值从键盘输入，其位数最多允许10位。
如果得到回文数，就输出这个数，并输出上述步骤重复执行的次数，如果上述步骤重复了30次还得不到回文数，则放弃。
数据结构模拟试题三
一．判断题（每小题1分，共10分）
1.逻辑结构不同的数据，要采用不同的存储方法来存储。
2.单链表中的结点只有后继，没有前驱。
3.栈和队列具有相同的逻辑特性。
4.二叉树中结点之间的相互关系不能用二元组来表示。
5.关键路径是由权值最大的边构成的。
6.在表示矩阵的三元组顺序表中，各元素的排列顺序与矩阵元素值的大小无关。
7.在广义表中，每个原子必须是单个字符。
8.在平衡二叉排序树中，每个结点的平衡因子值是相等的。
9.只有在线性表的初始状态为逆序排列的情况下，起泡排序过程中，元素的移动次数才会达到最大值。
10.在B+树上可以进行顺序查找。
二．填空题（每空1分，共10分）
1.若用不带表头结点的单链表来表示链接队列，则只有在________情况下，插入操作既要修改队尾指针的值，也要修改队头指针的值;只有在________情况下，删除操作仅需修改队首指针的值，不需修改队尾指针的值。
2.无向图中边的数目等于邻接矩阵中___________。
3.在各元素查找概率相等的情况下，在含有12个元素的二叉排序树上查找其中一个元素，元素间的平均比较次数至少是____次，至多是____次。
4.对12个元素进行快速排序，排序码的比较次数最多是___次。
5.对B+树来说，若某个非根分支结点中有6个关键字，则在它的某个孩子结点中至少有_____个关键字，至多有_____个关键字。
6.如果在根结点中要查到要找的关键字，则对于B-树来说，下一步应该_________，而对于B+树来说，下一步应该_________。
三．单选题（每题2分，共20分）
1.线性结构采用链式存储，________。
A．对插入、删除结点的操作较为有利B．不利于进行顺序访问
C．逻辑上相邻的结点在存储器中也相邻D．可以用一些不连续的存储区域来存放一个结点
2.某算法的时间复杂度为O（2n），表明该算法的________。
A．执行时间与2n成正比B．执行时间等于2n
C．问题规模是2nD．问题规模与2n成正比
3.在长度为n的_________上，删除最后一个元素，其算法的时间复杂度是O（n）。
A．只有表头指针的循环双向链表B．只有表头指针的非循环双向链表
C．只有表尾指针的非循环双向链表D .只有表尾指针的循环双向链表
4.在4个元素的进栈序列给定以后，由这4个元素构成的可能出栈序列共有________种。
A．14B.16C.17D.24
5.在任何一棵二叉树中，如果结点a有左孩子b、右孩子c，则在结点的前序序列、中序序列、后序序列中，_____________。
A．结点b一定在a的前面B．结点a一定在结点c的前面C．结点b一定在结点c的前面D．结点a一定在结点b的前面
6.若二叉树中结点的中序序列是abcdef，则结点的前序序列不可能是_____________。
A．dbacefB.acbedfC.efbacdD.bafdce
7.对稀疏矩阵采用压缩存储，其优点之一是可以_____________。
A．减少非零元素的存储空间B．不减少访问非零元素所需时间
C．减少矩阵的存储空间D．降低非零元素间逻辑关系的复杂程度
8.设待查找元素关键字的值是47，且已存入变量k中，如果在查找过程中，和k进行比较的关键字值依次是82,72,36,84,47，则所采用的查找方法可能是____________。
A．顺序查找B．分块查找C．折半查找D．平衡二叉排序树查找
9．在线性表中元素很多且各元素逆序排列的情况下，执行_______排序，元素的移动次数最少。
A．直接插入B．起泡C．简单选择D．折半插入
10.8阶方阵，每个元素占1个单元，按行优先顺序存储，起始地址为100，存储地址为135的那个元素是矩阵中每5行第___列的元素。
A．2B．3C.4D.5
四．图表题（每小题4分，共8分）
1.用h（x）=xmod7作为散列函数，用线性探测法处理冲突，所建立的散列表如下图所示，请将关键字17，27依次填入表中。
0123456
HT
15
10
45
20
2.二叉树的表态二叉链表存储结构如下图所示。
请给这棵二叉树加上中序线索。
12345678
Llink
Data
rlink
2
3
0
5
0
0
0
0
a
b
c
d
e
f
g
h
7
4
0
6
0
0
8
0
1
Root
五．算法填表题（10分）
在下面的表格中给出一些语句，每个语句都有编号。
要求利用这些语句设计一个完整的算法，该算法可对顺序表R[1]~R[n]进行选择排序。
请按所选语句在算法中出现的先后顺序，将其编号填入空内。
1
Voidsort（inti）
2
Sort（i+1）;
3
If（i==k）
4
If（i5
If（i>1）
6
If（k>i）
7
If（R[j]>R[k]）
8
If（R[j]9
For（j=i+1;j<=n;j++）
10
For（j=I;j11
R[0]=R[j]
12
R[i]=R[k];R[k]=R[0];
13
K=1;
14
K=j;
15
K=i;
16
{
17
}
1234567891011121314151617181920
六．算法设计题（24分）
1.在一个字符序列中，由相同字符构成的子序列称为平台。
写一个算法，其功能是，输入一个以句号结尾，长度任意的字符序列，分别统计由字符’A’所构成的平台的最大长度值，和由字符’B’所构成的最大长度值。
如对于字符序列’ABCDANBBCBAJKBCAAABA’。
’A’平台的最大长度是3，’B’平台的最大长度是2。
数据结构模拟试题四
一、（共30分，每题2分）单项选择题
1．循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为（）
A．（rear-front+m）modmB．rear-
升级会员 