2020年02142数据结构导论模拟试题（3）

自考生网为考生收集整理了“2020年02142数据结构导论模拟试题（3）”。

注：不同省份、不同专业的自考本科模拟试题，只要课程代码和课程名称相同，都可参考使用。

更多自考02142数据结构导论模拟试题可查看“自考02142数据结构导论模拟试题”栏目。

点击查看：02142数据结构导论模拟试题答案

一、单项选择题

1.1.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（3）存储方式最节省运算时间。

（1）单链表（2）双链表

(3)容量足够大的顺序表（4）带头结点的双循环链表

2.若某线性表中最常用的操作是取第I个元素的前驱元素，则采用（3）存储方式最节省运算时间。

（1）单链表（2）双链表

(3)顺序表（4）带头结点的双循环链表

将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（A）。

A．98 B.99 C.50 D.48

一个具有n个顶点的无向完全图的边数为（B）。

A．n(n+1)/2 B．n(n-1)/2 C．n(n-1)D．n(n+1)

折半查找要求查找表中各元素的关键字值必须是____A_______排列。

A.递增或递减B.递增C.递减D.无序

栈操作的原则是B。

A.先进先出B.后进先出C.只能进行插入D.只能进行删除

3.2.设一个栈的输入序列为A，B，C，D，则借助一个栈所得的输出序列不可能是____（4）___。

（1）A，B，C，D（2）D，C，B，A（3）A，C，D，B（4）D，A，B，C

将下三角矩阵A[1..10，1..10]的所有非0元素以行序为主序存放在首地址为2000的存储区中，每个元素占有4个单元，则元素A[9，5]的首地址为（D）

A．2340 B．2336 C．2164 D．2160

4.3.串是______（4）_______。

（1）（1）不少于一个字母的序列（2）任意个字母的序列

（2）（2）不少于一个字符的序列（4）有限个字符的序列

5.4.链表不具有的特点是______A______.

（1）可随机访问任一元素（2）插入删除不需要移动元素

（3）不必事先估计存储空间（4）所需空间与线性表长度成正比

6.5.在有n个结点的哈夫曼树中，其结点总数为____4__________。

（1）（1）不确定（2）2n（3）2n+1（4）2n-1

7.6.任何一个无向连通图的最小生成树______B_______。

（1）（1）只有一棵（2）有一棵或多棵（3）一定有多棵（4）可能不存在

8.7.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为____1______。

（1）98（2）99（3）50（4）48

9.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为____2______。

（1）98（2）99（3）50（4）48

10.将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的双亲编号为____2______。

（1）23（2）24（3）25（4）无法确定

设计一个判别表达式中左右括号是否配对出现的算法，采用（B）数据结构最佳。

A．线性表的顺序存储结构B．栈C．队列D．线性表的链式存储结构

11.8.下列序列中，_______A_______是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。

（1）[da,ax,eb,de,bb]ff[ha,gc](2)[cd,eb,ax,da]ff[ha,gc,bb]

(3)[gc,ax,eb,cd,bb]ff[da,ha](4)[ax,bb,cd,da]ff[eb,gc,ha]

12.9.用n个键值构造一棵二叉排序树，最低高度为___D_________。

（1）n/2(2)n1/2(3)NLOG2N(4)[LOG2N]+1

13.10.折半查找要求查找表中各元素的关键字值必须是___1________排列。

（1）（1）递增或递减（2）递增（3）递减（4）无序

14.11.对于关键字值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为______3____的结点开始。

（1）100（2）12（3）60（4）15

快速排序的记录移动次数（C）比较次数，其总执行时间为0（NLOG2N）

A．大于B．大于等于C．小于等于D．小于

3个结点可构成（D）个不同形态的二叉树。

A．2 B．3 C．4 D．5

对有n个记录的有序表采用二分查找，其平均查找长度的量级为（A）

A．O（LOG2N）B．O（NLOG2N）C．O（N）D．O（N2）

对有n个记录的表按记录键值有序的顺序建立二叉排序树，在这种情况下，其平均查找长度的量级为（C）

A．O（LOG2N）B．O（NLOG2N）C．O（N）D．O（N2）

设矩阵A[1..8,1..8]是一对称矩阵，若每个矩阵元素占3个单元，将其上三角部分按行序为主序存放在数组B中，B的首址为1000，则矩阵元素A[6，7]的地址为（B）

A．1031 B．1093 C．1096 D．1032

链表适用于顺序查找，但在链表中进行（D）操作的效率比在顺序存储结构中进行同样操作的效率高。

A．顺序查找B．二分法查找C．快速查找D．插入

散列法中的冲突指的是（C）。

A．两个元素具有相同的序号B．两个元素的键值不同，而其它属性相同

C．不同键值的元素对应于相同的存储地址D．数据元素过多

如果以链表作为栈的存储结构，则退栈操作时（C）

A．必须判断栈是否满B．对栈不作任何判断C．必须判断栈是否空

D．判断栈元素的类型

设数组A[0..M]作为循环队列SQ的存储空间，front为队头指针，rear为对尾指针，则执行出队操作的语句为（D）

A．front=front+1 B．front=(front+1)%m

C．rear=rear+1 D．rear=(rear+1)%m

深度为6的二叉树至多有（D）个结点

A．64 B．32 C．31 D．63

设高度为k的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少为（C）

A．K+1 B．2K C．2K-1 D．2K+1

堆的存储表示（A）

A．顺序存储B.静态链接存储C.动态链接存储D.不一定

若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用(A)遍历方法最合适。

A．前序B．中序C．后序D．按层次

利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行(A)元素间的比较。

A．4次B．5次C.7次D．10次

下面给出的四种排序法中(D)排序法是不稳定性排序法。

A．插入B．冒泡C．二路归并D．堆积

下面B方法可以判断出一个有向图中是否有环（回路）？

A.深度优先遍历B.拓朴排序C.求最短路径D.求关键路径

1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为(D)

A.顺序存储结构B.链式存储结构

C.索引存储结构D.散列存储结构

2.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为(A)

A.n-i+1 B.n-i

C.i D.i-1

3.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为(C)

A.顺序表B.用头指针表示的单循环链表

C.用尾指针表示的单循环链表D.单链表

4.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为()

A.4 B.5 C.6 D.7

5.为查找某一特定单词在文本中出现的位置，可应用的串运算是(D)

A.插入B.删除C.串联接D.子串定位

6.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到(A)

A.P=″SCIENCE″B.P=″STUDY″

C.S=″SCIENCE″D.S=″STUDY″

7.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］[4][5]的存储地址为()

A.356 B.358 C.360 D.362

8.如右图所示广义表是一种(C)

A.线性表

B.纯表

C.结点共享表

D.递归表

9.下列陈述中正确的是(D)

A.二叉树是度为2的有序树

B.二叉树中结点只有一个孩子时无左右之分

C.二叉树中必有度为2的结点

D.二叉树中最多只有两棵子树，并且有左右之分

10.n个顶点的有向完全图中含有向边的数目最多为(D)

A.n-1 B.n C.n(n-1)/2 D.n(n-1)

11.已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为(A)

A.a d b e f c

B.a d c e f b

C.a d c b f e

D.a d e f c b

12.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是(C)

A.快速排序B.堆排序C.归并排序D.基数排序

13.不可能生成右图所示二叉排序树的关键字序列是(A)

A.4 5 3 1 2

B.4 2 5 3 1

C.4 5 2 1 3

D.4 2 3 1 5

14.ALV树是一种平衡的二叉排序树，树中任一结点的(B)

A.左、右子树的高度均相同B.左、右子树高度差的绝对值不超过1

C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树的高度

15.在VSAM文件的控制区间中，记录的存储方式为()

A.无序顺序B.有序顺序

B.C.无序链接D.有序链接

二、二、判断题

1.（）串长度是指串中不同字符的个数。

2.（）数组可以看成是线性结构的一种推广，因此可以对它进行插入、删除等运算。

3.（）在顺序表中取出第i个元素所花费的时间与i成正比。

4.()在栈满的情况下不能作进栈的运算，否则产生“上溢”。

5.（）二路归并排序的核心操作是将两个有序序列归并为一个有序序列。

6.（）对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。

7.（）一个有向图的邻接表和逆邻接表中的结点个数一定相等。

8（）在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。

9.（）二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其右孩子的值。

10.（）在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。

二、判断题(判断下列各题是否正确，若正确在括号内打“√”，错误的打；

1．如果两个串含有相同的字符，则这两个串相等。（N）

2．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。(N)，

3．在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块元素个数有关。（Y）

4．在顺序表中取出第i个元素所花费的时间与i成正比。（N）

5．在栈满情况下不能作进栈运算，否则产生“上溢”。（Y）

6．二路归并排序的核心操作是将两个有序序列归并为一个有序序列，(Y)

7．对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。（N）

8．二叉排序树或是一棵空二叉树，或是具有下列性质的二叉树；若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其右孩子的值。（N）

9．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的(N)。

10．一个有向图的邻接表和逆邻接表中表结点的个数一定相等（Y）

①（101，88，46，70，34，39，45，58，66，10）是堆（Y）；

②将一棵树转换成二叉树后，根结点没有左子树（N）；

③用二叉树的前序遍历和中序遍历可以导出树的后序遍历（Y）；

④即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同(N)；

⑤哈夫曼树是带权路径长度最短的二叉树，路径上权值较大的结点离很较近（Y）。

11、表示一个有1000个顶点、1000条边的有向图的邻接矩阵有1000000个矩阵元素，是否稀疏矩阵是

三、填空题

1.在带有头结点的单链表L中，第一个元素结点的指针是___L->next________。

2.在双循环链表中，在指针p所指结点前插入指针s所指的结点，需执行下列语句：

s->next=p;s->prior=p->prior;p->prior=s;_s->prior->next_______________=s;

3.设s[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是___top==0__________，栈为满的条件是________top==maxsize_____________。

4.具有100个结点的完全二叉树的深度为______7__________________。

5.有向图G用邻接矩阵A[1..n,1..n]存储，其第i行的所有元素之和等于顶点i的____出度_______________。

以上“2020年02142数据结构导论模拟试题（3）”内容由自考生网收集整理，以供参考。