全国数据结构考试集合Word下载.docx
《全国数据结构考试集合Word下载.docx》由会员分享，可在线阅读，更多相关《全国数据结构考试集合Word下载.docx（46页珍藏版）》请在冰点文库上搜索。
D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构
2.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是（）
A.无头结点的单向链表B.带头结点的单向链表
C.带头结点的双循环链表D.带头结点的单循环链表
3.若带头结点的单链表的头指针为head，则判断链表是否为空的条件是（）
A.head=NULLB.head->
next=NULL
C.head!
=NULLD.head->
next!
=head
4.若元素的入栈顺序为1，2，3....，n，如果第2个出栈的元素是n，则输出的第i（1<
=i<
=n）个元素是（）
A.n-iB.n-i+l
C.n-i+2D.无法确定
5.串匹配算法的本质是（）
A.串复制B.串比较
C.子串定位D.子串链接
6.设有一个10阶的对称矩阵A，采用行优先压缩存储方式，a11为第一个元素，其存储地址为1，每个元素占一个字节空间，则a85的地址为（）
A.13B.18
C.33D.40
7.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是（）
A.树中没有度为2的结点B.树中只有一个根结点
C.树中非叶结点均只有左子树D.树中非叶结点均只有右子树
8.若根结点的层数为1，则具有n个结点的二叉树的最大高度是（）
A.nB.
C.+1D.n/2
9.在图G中求两个结点之间的最短路径可以采用的算法是（）
A.迪杰斯特拉（Dijkstra）算法B.克鲁斯卡尔（Kruskal）算法
C.普里姆（Prim）算法D.广度优先遍历（BFS）算法
10.下图G=（V,E）是一个带权连通图，G的最小生成树的权为（）
A.15
B.16
C.17
D.18
11.在下图中，从顶点1出发进行深度优先遍历可得到的序列是（）
A.1234567
B.1426375
C.1425367
D.1246537
12.如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是（）
A.不稳定的B.稳定的
C.基于交换的D.基于选择的
13.设有一组关键字（19,14,23,1，6，20,4，27,5，11,10,9），用散列函数H（key）=key%13构造散列表，用拉链法解决冲突，散列地址为1的链中记录个数为（）
A.1B.2
C.3D.4
14.已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是（）
1．若一个算法的时间复杂度用T（n）表示，其中n的含义是（）
A．问题规模B．语句条数
C．循环层数D．函数数量
2．具有线性结构的数据结构是（）
A．树B．图
C．栈和队列D．广义表
3．将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（）
A．O
（1）B．O（m）
C．O（n）D．O（m+n）
4．在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（）
A．2个B．3个
C．4个D．6个
5．假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（）
A．3B．37
C．50D．97
6．若栈采用链式存储结构，则下列说法中正确的是（）
A．需要判断栈满且需要判断栈空
B．不需要判断栈满但需要判断栈空
C．需要判断栈满但不需要判断栈空
D．不需要判断栈满也不需要判断栈空
s．设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为（）
A．1012B．1017
C．1032D．1039
10．下列数据结构中，不属于二叉树的是（）
A．B树B．AVL树
C．二叉排序树D．哈夫曼树
11．对下面有向图给出了四种可能的拓扑序列，其中错误的是（）
A．1，5，2，6，3，4B．1，5，6，2，3，4
C．5，1，6，3，4，2D．5，1，2，6，4，3
12．以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（）
A．v1，v2，v3，v4，v5，v6，v7B．v1，v2，v5，v4，v3，v7，v6
C．v1，v2，v3，v4，v7，v5，v6D．v1，v2，v5，v6，v7，v3，v4
13．下列排序算法中不稳定的是（）
A．快速排序B．归并排序
C．冒泡排序D．直接插入排序
14．一个有序表为（1，3，9，12，32，41，45，62，75，77，82，95，100），当采用折半查找方法查找值32时，查找成功需要的比较次数是（）
A．2B．3
C．4D．8
15．采用ISAM组织文件的方式属于（）
A．链组织B．顺序组织
C．散列组织D．索引组织
3．指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是（ ）
A．p->
next=r；
q->
next=r->
next；
r->
next=q；
B．p->
C．r->
p->
D．r->
4．若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是（ ）
A．3B．5
C．6D．7
5．假设以数组A［n］存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为（ ）
A．rear==frontB．（front+1）％n==rear
C．rear+1==frontD．（rear+1）％n==front
7．二维数组A［10］［6］采用行优先的存储方法，若每个元素占4个存储单元，已知元素A［3］［4］的存储地址为1000，则元素A［4］［3］的存储地址为（ ）
A．1020B．1024
C．1036D．1240
9．已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（ ）
A．FEDCBAB．ABCDEF
C．FDECBAD．FBDCEA
12．如图所示的有向图的拓扑序列是（ ）
A．c，d，b，a，e
B．c，a，d，b，e
C．c，d，e，a，b
D．c，a，b，d，e
13．对关键字序列（6，1，4，3，7，2，8，5）进行快速排序时，以第1个元素为基准的一次划分的结果为（ ）
A．（5，1，4，3，6，2，8，7）B．（5，1，4，3，2，6，7，8）
C．（5，1，4，3，2，6，8，7）D．（8，7，6，5，4，3，2，1）
14．分块查找方法将表分为多块，并要求（ ）
A．块内有序B．块间有序
C．各块等长D．链式存储
1.下列程序段的时间复杂度为（）
s=0；
for（i=1；
i<
n；
i++）
for（j=1；
j<
j++）
s+=i*j；
A.O
（1）B.O（n）
C.O（2n）D.O（n2）
2.假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件是（）
A.head==NULL；
B.head->
next==NULL；
=NULL；
D.head->
next==head；
3.栈是一种操作受限的线性结构，其操作的主要特征是（）
A.先进先出B.后进先出
C.进优于出D.出优于进
4.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。
若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为（）
A.（rear-front-1）％nB.（rear-front）％n
C.（front-rear+1）％nD.（rear-front+n）％n
5.判断两个串大小的基本准则是（）
A.两个串长度的大小B.两个串中首字符的大小
C.两个串中大写字母的多少D.对应的第一个不等字符的大小
6.二维数组A[4][5]按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A[0][0]的存储地址为1000，则数组元素A[3][2]的存储地址为（）
A.1012B.1017
C.1034D.1036
7.高度为5的完全二叉树中含有的结点数至少为（）
A.16B.17
C.31D.32
8.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为（）
A.5B.8
C.11D.18
9.下列所示各图中是中序线索化二叉树的是（）
10.已知含6个顶点（v0，v1，v2，v3，v4，v5）的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为（）
A.（v0，v1，v2，v5，v4，v3）
B.（v0，v1，v2，v3，v4，v5）
C.（v0，v1，v5，v2，v3，v4）
D.（v0，v1，v4，v5，v2，v3）
11.如图所示有向图的一个拓扑序列是（）
A.ABCDEF
B.FCBEAD
C.FEDCBA
D.DAEBCF
12.下列关键字序列中，构成大根堆的是（）
A.5，8，1，3，9，6，2，7B.9，8，1，7，5，6，2，33
C.9，8，6，3，5，l，2，7D.9，8，6，7，5，1，2，3
14.已知一个散列表如图所示，其散列函数为H（key）=key％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为（）
1.数据的不可分割的最小标识单位是（）
A.数据项B.数据记录
C.数据元素D.数据变量
3.若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是（）
A.单链表B.双链表
C.单循环链表D.顺序表
4.设单链表中指针p指向结点A，要删除A之后的结点（若存在），则修改指针的操作为（）
A.p—>
next=p—>
next—>
nextB.p=p—>
next
C.p=p—>
nextD.p—>
next=p
5.向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行的操作为（）
A.hs—>
next=s；
B.s—>
next=hs；
hs=s；
C.s—>
next=hs—>
hs—>
D.s—>
hs=hs—>
6.设循环队列的元素存放在一维数组Q［0‥30］中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。
如果队列中元素的个数为11，front的值为25，则rear应指向的元素是（）
A.Q［4］B.Q［5］
C.Q［14］D.Q［15］
7.定义二维数组A［1‥8，0‥10］，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（）
A.LOC+28LB.LOC+36L
C.LOC+50LD.LOC+52L8.具有n个结点的二叉树，拥有指向孩子结点的分支数目是（）
A.n-1B.n
C.n+1D.2n
9.对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（）
A.99B.98
C.97D.50
10.有m个叶子结点的哈夫曼树，其结点总数是（）
A.2m-1B.2m
C.2m+1D.2（m+1）
11.有n个结点的无向图的边数最多为（）
A.n+1B.
C.n（n+1）D.2n（n+1）
12.设图的邻接矩阵为
，则该图为（）
A.有向图B.无向图
C.强连通图D.完全图
13.二分查找算法的时间复杂度是（）
A.O（n2）B.O（nlog2n）
C.O（n）D.O（log2n）
14.已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（）
A.4B.5
C.6D.7
15.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（）
A.插入和快速B.冒泡和快速
C.选择和插入D.选择和冒泡
1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）
A.栈B.队列
C.树D.图
2.下面程序段的时间复杂度为（）
for（i=0;
i<
m;
i++）
for（j=0;
j<
n;
j++）
A[i][j]=i*j;
A.O（m2）B.O（n2）
C.O（m*n）D.O（m+n）
3.在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是（）
A.p->
next==headB.p->
next->
next==head
C.p->
next==NULLD.p==head
4.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（）
A.SXSSXXXXB.SXXSXSSX
C.SXSXXSSXD.SSSXXSXX
5.两个字符串相等的条件是（）
A.串的长度相等B.含有相同的字符集
C.都是非空串D.串的长度相等且对应的字符相同
7.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点
个数为（）
A.0B.1
C.48D.49
8.在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout，则所有顶点的入度之和为（）
A.DoutB.Dout-1
C.Dout+1D.n
9.如图所示的有向无环图可以得到的拓扑序列的个数是（）
A.3B.4
C.5D.6
10.如图所示的带权无向图的最小生成树的权为（）
A.51B.52
C.54D.56
11.对长度为n的关键字序列进行堆排序的空间复杂度为（）
A.O（log2n）B.O
（1）
C.O（n）D.O（n*log2n）
12.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为
（35，51，24，13，68，56，42，77，93）
（35，24，13，51，56，42，68，77，93）
所采用的排序方法是（）
A.插入排序B.冒泡排序
C.快速排序D.归并排序
13.已知散列表的存储空间为T[0..18]，散列函数H（key）=key%17,并用二次探测法处理冲突。
散列表中已插入下列关键字：
T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是（）
A.T[2]B.T[4]
C.T[8]D.T[10]
14.适宜进行批量处理的文件类型是（）
A.顺序文件B.索引顺序文件
C.散列文件D.多关键字文件
1.逻辑上通常可以将数据结构分为（ ）
A.动态结构和静态结构B.顺序结构和链式结构
C.线性结构和非线性结构D.初等结构和组合结构
2.在下列对顺序表进行的操作中，算法时间复杂度为O
（1）的是（ ）
A.访问第i个元素的前驱（1<
）
B.在第i个元素之后插入一个新元素（
C.删除第i个元素（
D.对顺序表中元素进行排序
3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（ ）
A.head==NULLB.head–>
next==NULL
=NULLD.head–>
next==head
4.已知栈的最大容量为4。
若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ ）
A.5，4，3，2，1，6B.2，3，5，6，1，4
C.3，2，5，4，1，6D.1，4，6，5，2，3
8.树的先根序列等同于与该树对应的二叉树的（ ）
A.先序序列B.中序序列
C.后序序列D.层序序列
9.假设有向图含n个顶点及e条弧，则表示该图的邻接表中包含的弧结点个数为（ ）
A.nB.e
C.2eD.n·
e
10.如图所示的有向无环图可以得到的不同拓扑序列的个数为（ ）
11.下列排序方法中，稳定的排序方法为（ ）
A.希尔排序B.堆排序
C.快速排序D.直接插入排序
12.对下列关键字序列进行快速排序时，所需进行比较次数最少的是（ ）
A.（1，2，3，4，5，6，7，8）B.（8，7，6，5，4，3，2，1）
C.（4，3，8，6，1，7，5，2）D.（2，1，5，4，3，6，7，8）
13.含n个关键字的二叉排序树的平均查找长度主要取决于（ ）
A.关键字的个数B.树的形态
C.关键字的取值范围D.关键字的数据类型
14.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是（ ）
A.分块查找B.顺序查找
C.二分查找D.散列查找
15.可有效提高次关键字查找效率的文件是（ ）
A.顺序文件B.倒排文件
C.散列文件D.VSAM文件
1.下面程序段的时间复杂度为（）
i；
A.O
（1）B.O（logn）
2.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。
假设指针s指向
另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（）
A.q->
next=s->
s->
next=p；
B.s->
q->
C.p->
D.s->
p->
3.在计算机内实现递归算法时所需的辅助数据结构是（）
A.栈B.队列
C.树D.图
4.假设以数组A[m]存放循环队列的元素。
已知队列的长度为length，指针rear指向队
尾元素的下一个存储位置，则队头元素所在的存储位置为（）
A.（rear-length+m+1）％mB.（rear-length+m）％m
C.（rear-length+m-1）％mD.（rear-length）％m
5.通常将链串的结点大小设置为大于1是为了（）
A.提高串匹配效率B.提高存储密度
C.便于插入操作D.便于删除操作
8.用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为（）
A.n-1B.n
C.n+lD.2n
9.为便于判别有向图中是否存在回路，可借助于（）
A.广度优先搜索算法B.最小生成树算法
C.最短路径算法D.拓扑排序算法
10.连通网的最小生成树是其所有生成树中（）
A.顶点集最小的生成树B.边集最小的生成树
C.顶点权值之和最小的生成树D.边的权值之和最小的生成树
11.按排序过程中依据的原则分类，快速排序属于（）
A.插入类的排序方法B.选择类的排序方法
C.交换类的排序方法D.归并类的排序方法
12.下列关键字序列中，构成小根堆的是（）
A.{84，46，62，41，28，58，15，37}
B.{84，62，58，46，41，37，28，15}
C.{15，28，46，37，84，41，58，62}
D.{15，28，46，37，84，58，62，41}
13.在长度为32的有序表中进行二分查找时，所需进行的关键字比较次数最多为（）
A.4B.5
C.6D.7
15.散列文件也称为（）
A.顺序文件B.索引文件
C.直接存取文件D.间接存取文件
1.在数据结构中，从逻辑上可以把数据结构分成（）
A.线性结构和非线性结构B.紧凑结构和非紧凑结构
C.动态结构和静态结构D.内部结构和外部结构
2.for（i=0；
m；
for（j=0；
A［i］［j］=i*j；
上面算法的时间复杂度为（）
A.O（m2）B.O（n2）
C.O（m×
n）D.O（m+n）
3.设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为（）
A.5B.6
C.7D.9
4.设p为指向双向循环链表
升级会员 