整理数据结构与算法题库下发版doc.docx
《整理数据结构与算法题库下发版doc.docx》由会员分享，可在线阅读，更多相关《整理数据结构与算法题库下发版doc.docx（66页珍藏版）》请在冰点文库上搜索。
整理数据结构与算法题库下发版doc
一、单选题
知识点一：
绪论
1.设有如下遗产继承规则:
丈夫和妻子可以互相继承遗产;子女可以继承父亲或母亲的遗产:
子女间不能相互继承。
则表示该遗产继承关系的最合适数据结构应该是（）。
A．树B.图C.数组D.二叉树
2.设有一遗传关系:
X是Y的父亲，X可以把它的属性遗传给Y。
则表示该遗传关系最适合的数据结构为（）。
A.向量B.树C.图D.广义表
3.在数据结构中，从逻辑上可以把数据结构分成（）
A.动态结构和静态结构B.紧凑结构和非紧凑结构
C.线性结构和非线性结构D.内部结构和外部结构
4.数据结构在计算机内存中的表示是指（）
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．设计一个“好”的算法应达到的目标为（）。
A.正确性、可读性、健壮性及效率和低存储量需求B.正确性、可读性、健壮性及有穷性
C.正确性、可读性、健壮性及可行性D.正确性、可读性、健壮性及确定性
知识点二：
线性表
11.和线性表的链接存储相符的特性是（）。
A.插入和删除操作灵活B.需要连续存储空间C.便于随机访问D.存储密度大
12.在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是（）。
A.p=NULLB.p->next=NULLC.p=hD.p->next=h
13.和线性表的链接存储不相符的特性是（）。
A.插入和删除操作灵活B.需要连续的存储空间
C.存储空间动态分配D.需另外开辟空间来保存元素间的关系
14.以h为头指针的带头结点的单向循环链表为空的条件是（）。
A.h=NULLB.h->next=NULLC.h->next=hD.h->next->next=h
15.和线性表的链式存储不相符合的特性是（）。
A．插入和删除操作灵活B.需要连续的存储空间C.存储空间动态分配D.非紧凑结构
16.链表不具备的特点是（）
A.可随机访问任一结点B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间和其长度成正比
17.带头结点的单链表head为空的判定条件是（）
A.head==NULLB.head->next==NULLC.head->next==headD.head!
=NULL
18.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构
A.单链表B.静态链表c.线性链表D.顶序存储结构
19.如果最常用的操作是取第i个结点及其前驱，则采用存储方式最节省时间。
A.单链表B.双链表C.单循环链表D.顺序表
20.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是
A.0
（1）B.O（n）C.0（n2）D.0（nlog2n）
21.和单链表相比，双链表的优点之一是（）
A.插入、删除操作更简单B.可以进行随机访问
C.可以省略表头指针或表尾指针D.顺序访问相邻结点更灵活
22.一维数组和线性表的区别是（）
A.前者长度固定，后者长度可变B.后者长度固定，前者长度可变
C.两者长度均固定D.两者长度均可变
知识点三：
栈和队列
23.若进队序列为1，2，3，4，则出队序列是（）。
A.4，3，2，1B.1，2，3，4C.1，3，2，4D.3，2，4，1
24.设输入序列为1，2，3，4借助一个栈不可能得到的输出序列是（）。
A.1，2，3，4B.4，3，2，1C.3，4，1，2D.1，3，4，2
25.若进栈序列为1，2，3,4则不可能得到的出栈序列为（）。
A.3，2，1，4B.3，2，4，1C.4，2，3，1D.2，3，4，1
26.栈使用的典型事例是（）。
A.排队B.查找C.归并D.用“算符优先法”进行表达式求值
27.栈和队列都是（）。
A.顺序存储的线性结构B.链式存储的线性结构
C.限制存取点的线性结构D.限制存取点的非线性结构
28.对于顺序存储的队列，存储空间大小为n，头、尾指针分别为F和R，若将其看成一个首尾相接的圆环，则队列中元素个数为（）。
A.R-FB.n+R-FC.C（R-F+1）%nD.（n+R-F）%n
29.从一个顺序队列删除元素时，首先需要。
A.前移一位队首指针B.后移一位队首指针
C.取出队首指针所指位置上的元素D.取出队尾指针所指位置上的元素
30.假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为。
A.f+1==rB.r+1==fC.f==0D.f==r
31.初始为空的堆栈中依次插入元素:
f、e、d、c、b、a以后，连续进行了3次删除操作，此时的栈顶元素是（）。
A.cB.dC.bD.e
32．在解决计算机主机和打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，这样主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。
该缓冲区应该是一个（）结构。
A.堆B.队列C.数组D.线性表
33．设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（）。
A.ABCDB.DCBAC.ACDBD.DABC
34．设栈最大长度为3，入栈序列为1、2、3、4、5、6，则不可能的出栈序列是（）。
A.1、2、3、4、5、6B.2、1、3、4、5、6
C.3、4、2、1、5、6D.4、3、2、1、5、6
35．设栈的输入序列是1，2，…，n，若输出序列的第一个元素是n，则第i个输出元素是（）。
A.n-i+1B.iC.n-iD.前面都不正确
知识点四：
串
36．串的长度是（）。
A.串中不同字母的个数B.串中不同字符的个数
C.串中所含数字的个数D.串中所有字符的个数
37．（）是C语言中"abcd32lABCD"的子串。
A.abedB.32lABC."abcABC"D."21AB"
38．串是（）。
A.不少于一个字符的序列B.有限个字符的序列
C.不少于一个字母的序列D.任意个字母的序列
39．设有两个串p和q，求q在p中首次出现的位置的运算称做（）
A.连接B.模式匹配C.求子串D.求串长
40．若串s='software'，其真子串（不含自身）的个数是
A.8B.37C.36D.9
41．有串sl='ABCDEFG'，s2='PQRST'，假设函数con（x,y）返回x和y串的连接串，subs（s，i，j）返回串S的从序号i的字符开始的j个字符组成的子串，len（s）返回串S的长度，则con（subs（s1，2，len（s2）），subs（s1，len（s2），2））的结果串是
A.BCDEFB.BCDEFGC.BCPQRSTD.CDEFGFG
42．串是一种特殊的线性表，其特殊性体现在（）
A.可以顺序存储B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符
知识点五：
数组和广义表
43.己知广义表A=（（a，b）（c，d）），则head（A）等于（）。
A.（a，b）B.（（a，b））C.a，bD.a
44.设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为_______。
A.O（m）B.O（n）C.O（n+t）D.O（n*t）
45．一个三对角矩阵An×n已按行压缩存储到一维数组B中，则B的长度至少为（）。
A.3n+1B.3nC.3n-1D.3n-2
46．二维数组A[10][20]采用列序为主方式存储，每个元素占1个存储单元，并且A[O][O]的存储地址是200，则A[6][12]的地址是（）
A.328B.327C.326D.329
47.多维数组的数组元素之间的关系，
A.是线性的B.是树形的C.既是线性的，又是树形的D.既不是线性的，也不是树形的
知识点六：
树和二叉树
48.n个结点的二叉树，若用二叉链表作为存储结构，则非空闲的左、右孩子链域为（）。
A.nB.2nC.n-lD.n+l
49.对于下边的二叉树，其中序序列为（）。
A.DBAFCGB.DBAFGC
C.ABDCFGD.ABCDFG
50.在一棵二叉树上，第5层的结点数最多为（）。
A.8B.15C.16D.32
51.对于下面的二叉树，其中序序列为（）。
A.ABCDEFGB.ABDECFGC.DBEAFCGD.ADEBCFG
52．n个结点的二叉树中，用二叉链表做存储，非空指针数目为（）。
A.nB.2nC.n-1D.n+1
53.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为______。
A.24B.48C.72D.51
54.二叉树的先序遍历和中序遍历如下：
先序遍历：
EFHIGJK
中序遍历：
HFIEJKG
该二叉树根的右子树的根是（）。
A.EB.FC.GD.H
55.树结构最适合用来表示（）。
A.元素间具有分支层次关系的数据B.无序数据
C.有序数据D.元素间没有关联的数据
56.具有127个结点的完全二叉树其深度为（）。
A.8B.7C.6D.5
57.哈夫曼树是（）。
A.满二叉树B.二叉排序树
C.树的路径长度最短的二叉树D.带权路径长度最短的二叉树
58．设一棵二叉树中没有度为1的结点，已知叶子结点数为n，此树的结点数为（）。
A.2n+2B.2n+1C.2nD.2n-1
59．设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个叶子结点，则此二叉树中空指针域个数为（）。
A.n0+n1+n2B.n2+n1+2n0C.2n2+n1D.2n0+n1
60．用权值分别为15，2，4，5的四个结点，构造出的哈夫曼树为（D）。
61．由带权9、1、3、5、6的五个叶子结点生成的哈夫曼树的带权路径长度为（）。
A.50B.60C.52D.65
62．A、B两个结点可以构成（）棵不等价的二叉树。
A.2B.3C.4D.5
63．设哈夫曼树的叶结点数为n，则它的结点总数为（）。
A.2n-1B.2nC.2n+1D.不确定
64.深度为k的完全二叉树所含叶结点的个数最多为（）
A.2kB.2k-1C.kD.2k
65.在线索化二叉树中，t所指结点没有左子树的充要条件是
A.t一>lchild==NULL
B.t一>ltag==1
C.t->ltag==l且t一>lchild==NULL
D..以上都不对
66.在一非空二叉树的中序遍历序列中，根结点的右边（）
A.只有右子树上的所有结点B.只有右子树上的部分结点
C.只有左子树上的部分结点D.只有左子树上的所有结点
67.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次
A．不发生改变B.发生改变C.不能确定D.以上都不对
68.对一个满二叉树，m个树叶，n个结点，深度为h，则（）
A.n=h+mB.h+m=2nC.m=h-lD.n=2h-l
69.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定（）
A.空或只有一个结点B.完全二叉树C.二叉排序树D.高度等于其结点数
70.线索二叉树是一种（）结构。
A.逻辑B.逻辑和存储C.物理D.线性
知识点七：
图
71.给定下列有向图，从顶点V1出发，其深度优先搜索序列为（）。
A.12534B.12435C.14325D.12345
72．6个顶点的连通图的深度优先生成树，其边数为（）。
A.6B.5C.7D.4
73.具有8个顶点的连通图的深度优先生成树，其边数为（）。
A.8B.9C.7D.6
74．G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。
A.6B.7C.8D.9
75．一个n个顶点的连通无向图，其边的个数至少为（）。
A.n-1B.nC.n+1D.nlogn
76．对于有向图的邻接矩阵
，该图共有（）条弧。
A.5B.4C.3D.2
77．对于具有n个顶点的强连通图，其弧条数的最小值为（）。
A.n+1B.nC.n-1D.n-2
78．采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的（）。
A.先序遍历B.中序遍历C.后序遍历D.层次遍历
79.采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）
A.先序遍历B.中序遍历C.后序遍历D.按层遍历
80．对某个无向图的邻接矩阵来说，
A.第i行上的非零元素个数和第i列的非零元素个数一定相等
B.矩阵中的非零元素个数等于图中的边数
C.第i行上，第i列上非零元素总数等于顶点Vi的度数
D.矩阵中非全零行的行数等于图中的顶点数
81．以下说法中不正确的是
A.无向图中的极大连通子图称为连通分量
B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
C.图的深度优先搜索中一般要采用找来暂存刚访问过的顶点
D.有向图的遍历不可采用广度优先搜索方法
82.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（）
A.nB.n+lC.n-lD.n+e
83.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，所有邻接表中的结点总数是（）
A.e/2B.eC.2eD.n+e
知识点八：
查找
84．以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为______.
A.n（n+1）/2B.n2C.n（n-1）/2D.log2n
85.以二分查找方法查找一个线性表时，此线性表必须是顺序存储的_____
A.有序表B.无序表C.栈D.队列
86．若在线性表中采用折半查找法查找元素，该线性表应该（）。
A.元素按值有序B.采用顺序存储结构
C.元素按值有序，且采用顺序存储结构D.元素按值有序，且采用链式存储结构
87.衡量查找算法效率的主要标准是（）。
（A）元素个数（B）所需的存储量（C）平均查找长度（D）算法难易程度
88.设哈希表长m=14,哈希函数H（key）=key%11,表中已有4个结点:
Add（15）=4
Add（38）=5
Add（61）=6
Add（84）=7
其余地址为空,如用二次探测再散列处理冲突,关键字为49的结点地址是（）
A.8B.3C.5D.9
知识点九：
排序
89.下列排序算法中，最坏情况下，时间复杂度为O（n2）的排序算法是（）。
A.堆排序B.希尔排序C.归并排序D.快速排序
90．Shell排序的平均时间复杂度为（）。
A.O（n）B.O（nlog2n）C.O（n2）D.n1.3
91.下列排序中，占用的辅助空间最多的是（）。
A.快速排序B.冒泡排序C.直接选择排序D.二路归并排序
92.下列排序算法中不稳定的是（）。
A.直接选择排序B.二分插入排序C.冒泡排序D.归并排序
93.在文件局部有序的情况下，最好的内部排序应该是（）。
A.直接插入排序B.冒泡排序C.直接选择排序D.快速排序
94.n个关键字的直接插入排序所需的最小移动次数是（）。
A.2（n-1）B.0C.（n+3）（n-2）/2D.n2/2
95.如表r有100000个元素，前99999个元素递增有序，则采用（）方法比较次数较少。
A.直接插入排序B.快速排序C.归并排序D.选择排序
96．初始文件中有两个关键字相同的记录，通过不稳定的排序方法排序后，（）。
A.使得领先关系不发生变化B.领先关系一定发生变化
C.两个位置都不会发生变化D.领先关系可能发生变化
97．每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（）。
A.冒泡排序B.简单选择排序C.希尔排序D.直接插入排序
知识点十：
文件
98.在索引顺序文件中（）
A.主文件是无序的B.主文件是有序的c.不适合随机查找D.索引是稠密索引
99.散列文件的特点是
A.记录按关键字排序
B.记录可以进行顺序存取
c.存取速度快，但占用较多的存储空间
D.记录不需要排序，存取效率高
100.用ISAM和VSAM组织文件属于
A.顺序文件B.索引文件c.散列文件解ISAM和VSAM都属于索引顺序文件。
二、填空题
绪论
1．在数据结构中，从逻辑上可以把数据结构分成结构和结构。
2．分析一个算法的优劣要从两个方面，即复杂度和复杂度。
3．数据的结构是依赖于计算机存在的。
4．线性结构元素之间是对的关系；树形结构元素之间关系是；
图形结构元素之间关系是。
线性表
5．单链表的结点空间包括两部分，即域和域。
6．带头结点的单链表L为空的条件是。
7．单链表的和操作大多数情况下要优于顺序表。
8．在长度为n的顺序表中删除第i个元素时，假设i值合法，需向前移动个元素。
9．在线性表的顺序存储中，若一个元素的下标为i,则它的前驱元素的下标为，后继元素的下标为。
栈和队列
10.插入限定在表的一端，而删除限定在表的另一端进行的线性表称为______,允许插入的一端称为_______。
11.顺序循环队列Q[M]，下标从0到M-l，头尾指针分别用F和R表示，则队空条件是__________。
12._____是限定仅在表尾进行插入或删除操作的线性表。
13.插入和删除操作在进行。
串
14.串s=“love”,其真子串（不含自身）的个数是。
15.设S1=“GOOD”，S2=“︼”，S3=“BYE!
”，则S1，S2，S3连接之后的结果是。
数组和广义表
16．一个广义表的深度等于________嵌套的最大层数。
17．在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的__、___和____三项。
树和二叉树
18．二叉树的叶结点数no和二度结点数n2的关系是______。
19．具有256个结点的完全二叉树的深度为_____。
20．深度为k的完全二叉树至少有_______个结点，至多有______个结点。
21．如果结点A有3个兄弟，而且B是A的双亲，则B的度是______。
22．具有n个结点的二叉树，采用二叉链表存储，共有______个空链域。
23．线索二叉树的左线索指向其______，右线索指向其______。
24．具有50个结点的完全二叉树的高度是。
25.具有100个结点的完全二叉树有个叶子。
图
26．具有n个顶点的图用邻接矩阵存储，矩阵是行列。
27．一个n个顶点的连通无向图，其边的个数至少为。
28．要连通具有n个顶点的有向图，至少需要条边。
29．n个结点的完全有向图含有边的数目是。
30．具有10个顶点的无向图，边的总数最多为。
31．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的；对于有向图来说等于该顶点的。
查找、排序
32．顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为____次；最少为次。
33．以二分查找方法查找一个线性表时，此线性表必须是___存储的___表。
34．每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做______排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做__排序。
35．n个元素进行冒泡排序，最少的比较次数是。
三、判断题
绪论
1.在数据结构中，数据的逻辑结构和所使用的计算机无关
2.数据元素是数据的最小单位。
3.健壮的算法不会因非法的输入数据而出现莫名其妙的状态
线性表
4.线性表的逻辑顺序和存储顺序总是一致的
5.在线性表的顺序存储结构中，逻辑上相邻的2个元素在物理位置上并不一定紧邻
6.顺序存储的线性表示可以按序号随机存取
7.循环链表中每一个元素都有后继
8.线性表的唯一存储形式是链表。
9.在顺序表中取出第i个元素所花费的时间和i成正比。
10.线性表的长度是线性表所占用的存储空间的大小。
11.线性表的链式存储结构优于顺序存储结构。
12.链表的每个节点中都包含一个指针域。
栈和队列
13.一个栈的入栈顺序为A、B、C、D、E，则，出栈顺序ACEDB是不可能的。
14.栈和队列都是运算受限的线性表。
15.在栈为空的情况下，不能做出栈操作，否则产生下溢出。
16.在循环队列中，若尾指针Rear大于头指针Front，则其元素数为（Rear–Front）。
17.一个栈的输入序列是12345，则输出序列43512是可能的。
18.循环队列队满的条件是rear+1=front。
19.循环队列是链队列。
串
20.串长度是指串中不同字符的个数。
21.串是n（≥0）个字母的有限序列。
22.空串的长度为零。
23.子串是指串中任意个连续字符组成的子序列。
24.空串是任何串的子串。
25.空串和空白串是相同的。
数组和广义表
26.广义表的长度是指广义表中的原子个数。
27.取出广义表A=（a,（b,c）,d）中的运算head（tail（A））的结果不是b。
28.若广义表中的每个元素都是原子，则广义表为线性表。
29.稀疏矩阵是指大多数元素值为0，只有少数元素值不为0的矩阵。
30.矩阵的压缩存储适用于所有矩阵。
31.稀疏矩阵可以用三元组的方式存储。
树和二叉树
32.完全二叉树中没有度为1的结
升级会员 