2023年自考类计算机类(工学类)数据结构导论题库

2023年自考类计算机类(工学类)数据结构导论题库卷I一.历年考点试题黑钻版(共50题)1.试写出一组键值(46，58，15，45，90，18，10，62)应用直接插入排序算法从小到大排序后各趟的结果。2.设记录数为20，则冒泡排序算法在最好情况下所作的比较次数为______。3.______是指将两个或两个以上的有序表合并成一个新的有序表，其算法时间复杂度为______。4.队列的插入操作在队列的______部分进行。5.有一个整数序列，其输入顺序为20，30，90，-10，45，78，试用栈将其输出序列变为30，-10，45，90，78，20。请给出该整数序列进栈和出栈的操作步骤(可用push(x)表示x进栈，pop(x)表示x出栈)。6.下列表述正确的是______A.栈空时出栈产生“上溢”，栈满时进栈产生“下溢”B.栈空时出栈产生“下溢”，栈满时进栈产生“上溢”C.栈空时出栈和栈满时进栈均产生“上溢”D.栈空时出栈和栈满时进栈均产生“下溢”7.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是______A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表8.分别画出题图所示二叉树的二叉链表、三叉链表和顺序存储结构。

9.一个10×10阶对称矩阵A，采用行优先顺序压缩存储下三角矩阵，a00为第一个元素，其存储地址为0，每个元素占用1个存储单元，则a33的地址为______。10.写出计算方阵A[n][n]与B[n][n]乘积C[n][n]的算法。11.数据的基本单位是______。12.一个栈的输入序列为123…n，若输出序列的第一个元素是n，则输出第i(1≤i≤n)个元素是

A.不确定B.n-i+1C.iD.n-i13.设计一个用链表表示的直接插入排序算法。14.对顺序表执行插入操作，其插入算法的平均时间复杂度为______。15.要将现实生活中的数据转换为计算机所能表示的形式，其转移过程为

A.原始数据、存储结构、逻辑结构B.原始数据、逻辑结构、存储结构C.逻辑结构、存储结构、原始数据D.逻辑结构、原始数据、存储结构16.m个叶结点的哈夫曼树中，其结点总数为______A.mB.2m+1C.2mD.2m-117.按照二叉树的定义，具有3个结点的二叉树有

A.3利B.4种C.5种D.6种18.设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针q指向与链表中结点同类型的一个新结点。现要将指针q指向的结点插入表中，使之成为第一个结点，则所需的操作为“q-＞next=head;”和“______”。19.一棵树上的任何结点(不包括根本身)称为根的______。若B是A的子孙，则称A是B的______。20.对n个记录的集合进行快速排序，其最坏情况下所需的时间复杂度是______。21.具有10个顶点的有向完全图应具有

A.20条弧B.50条弧C.90条弧D.100条弧22.已知完全二叉树T的第5层只有9个结点，则该树共有______个叶子结点。23.队列的队尾位置通常是随着______操作而变化的。24.设二维数组A5×6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节?A的终端结点a45的起始地址为何?按行和按列优先存储时，a25的起始地址分别为何?25.分别写出下图中树的先序、后序和层次遍历的结点访问序列。

26.在栈中，可进行插入和删除操作的一端称为______。27.已知连通带权图如下图所示，试利用普里姆(Prim)算法，从顶点A出发，构造它的最小生成树，并画出构造过程。

28.一个顺序队列的第5个元素的存储地址是200，第10个元素的存储地址是225。每个元素的长度是5，则第21个元素的地址是______。29.下列说法错误的是______A.一个图的邻接矩阵表示是唯一的B.一个图的邻接表表示是不唯一的C.一个图的生成树必为该图的极小连通子图D.一个无环有向图的拓扑排序序列必唯一30.设栈S1的入栈序列为1，2，3，4(每个数字为13个元素)，则不可能得到出栈序列3，1，4，2。但可通过增设栈S2来实现。例如，按下图中的箭头指示，依次经过栈S1和S2，便可得到序列3，1，4，2。

如果用H1和H2分别表示栈S1和S2的进栈操作，用P1和P2分别表示两个栈的出栈操作，则得到3，1，4，2的一个操作步骤为H1，H1，H1，P1，H2，P2，P1，H2，P1，H2，P2，H1，P1，H2，P2，P2。

请仿照上例写出利用两个栈从1，2，3，4得到4，1，3，2的操作步骤。31.单链表中逻辑上相邻的两个元素在物理位置上______相邻。32.A[0…6，0…6]每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续内存单元中，则元素a[5，5]的地址为______A.1175B.1160C.1055D.114033.栈下溢是指在______时进行出栈操作。34.在一棵初始时为空的二叉树中，依次插入键值序列50，72，43，85，75，20，38，45，65，60，构造对应的二叉排序树以后，查找元素60要进行的比较次数是______A.2B.3C.4D.535.若用后序遍历法遍历题下图所示的二叉树，其输出序列为______。

36.若二叉树的中序遍历序列是abcdef，且c为根结点，则______A.结点c有两个孩子B.二叉树有两个度为0的结点C.二叉树的高度为5D.以上都不对37.对特殊矩阵采用压缩存储的目的主要是为了______A.减少不必要的存储空间B.对矩阵元素的存取变得简单C.去掉矩阵中多余元素D.表达变得简单38.程序段“i=1;while(i＜=n)i=i*2;”的时间复杂度T(n)=______。39.二叉树如下图所示，分别写出其先序遍历、中序遍历和后序遍历的结点访问序列。

40.单链表中删除由某个指针变量指向的结点的直接后继，该算法的时间复杂度是______

A．O(log2n)

B．

C．O(1)

D．O(n)41.在最好的情况下，对于具有n个元素的有序序列，若采用冒泡排序，所需的比较次数为______次。42.排序趟数与序列的原始状态有关的排序方法是

A.插入排序法B.选择排序法C.二路归并排序法D.快速排序法43.快速排序属于______A.插入排序B.选择排序C.交换排序D.归并排序44.下列查找中，效率最高的查找方法是______A.顺序查找B.二分查找C.索引顺序查找D.分块查找45.设有向图G的邻接矩阵为A，如果＜Vi，Vj＞是图中的一条弧，则A[i][j]的值为______。46.含有n个顶点的连通图中的任意一条简单路径，其最大长度为______。47.顺序表中有20个元素，第一个元素的地址为300，且每个元素占一个字节，则第14个元素的存储地址为______A.313B.314C.315D.31248.对n个记录的集合进行快速排序，其最坏情况下所需的时间复杂度是______，就平均性能而言，快速排序方法最佳，其时间复杂度为______。49.可以唯一地转化成一棵一般树的二叉树的特点是______A.根结点无左孩子B.根结点无右孩子C.根结点有两个孩子D.根结点没有孩子50.循环链表中一个结点有多少个指针______A.1B.2C.3D.0卷I参考答案一.历年考点试题黑钻版1.参考答案：初始序列：[46],58,15,45,90,18,10,62

第一趟：[46,58],15,45,90,18,10,62

第二趟：[15,46,58],45,90,18,10,62

第三趟：[15,45,46,58],90,18,10,62

第四趟：[15,45,46,58,90],18,10,62

第五趟：[15,18,45,46,58,90],10,62

第六趟：[10,15,18,45,46,58,90],62

第七趟：[10,15,18,45,46,58,62,90][考点]直接插入排序算法2.参考答案：19[考点]冒泡排序[解析]设记录数为20，则冒泡排序算法在最好情况下所作的比较次数为19。3.参考答案：二路归并O(nlog2n)[考点]二路归并定义[解析]二路归并是指将两个或者两个以上的有序表合成—个新的有序表，其算法复杂度为O(nlog2n)。4.参考答案：队尾[考点]队列的操作[解析]队列的插入操作在队列的队尾部分进行。5.参考答案：push(20)，push(30)，pop(30)，push(90)，push(-10)，pop(-10)，push(45)，pop(45)，pop(90)，push(78)，pop(78)，pop(20)。[考点]栈的存取原则是后进先出6.参考答案：B[考点]栈的存储结构[解析]栈空时出栈产生“下溢”，栈满时进栈产生空间溢出，称为“上溢”。7.参考答案：D8.参考答案：(1)二叉链表示意图

(2)三叉链表示意图

(3)顺序存储结构爪意图

9.参考答案：910.参考答案：voidmatrixmultiply(intA[][n],intB[][n],intC[][n],intn)

//求n阶方阵A与B的乘积C

{inti,j;

for(i=0;i＜n;i++)

for(j=0,j＜n;j++)

{c[i][j]=0;

for(k=0;k＜n;k++)

C[i][j]+=A[i][k]×B[k][j];

}

}11.参考答案：数据元素12.参考答案：B13.参考答案：voidsort(DLinkListH)

{pre=H-＞next；

while(p!=H)

{p=pre-＞next；

q=p-＞next；

while((pre!=H)&&(p-＞data＜pre-＞data))

pre=pre-＞prior；

if(pre!=p-＞prior)

{p-＞priorr-＞next=p-＞next；

p-＞next-＞prior=p-＞prior；

p-＞next=pre-＞next；

pre-＞next-＞prior=p；

p-＞prior=pre；pre-＞next=p；

}

p=q；

}

}14.参考答案：(n/2)[考点]顺序表插入操作的时间复杂度[解析]顺序表插入操作的时间复杂度为n/2。15.参考答案：B[解析]本题主要考查的知识点是计算机解决问题的步骤。[要点透析]在数学模型中，需要把原始数据按照某种方式组织起来，以便很好地体现数据之间的关系，数据及数据的组织方式称为数据的逻辑结构。为了能用计算机加工处理，逻辑结构还必须转换为能被计算机存储的存储结构。16.参考答案：D[考点]哈夫曼算法[解析]对于m个叶子结点的哈夫曼树，其是m个权值分量，经过m-1次合并又产生m-1个新结点，从而组成的m+m-1=2m-1个结点的哈夫曼树。17.参考答案：C[解析]本题主要考查的知识点是二叉树的定义。[要点透析]非空二叉树的判定条件是：①有且只有一个根结点；②其余结点分为两个互不相交的集合T1、T2，T1与T2都是二叉树，并且T1与T2有顺序关系(T1在T2之前)。由此可知，3个结点的二叉树有5种。18.参考答案：head=p[考点]单链表元素插入操作的指针修改[解析]将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为“p→Next=head;”和“head=p”。19.参考答案：子孙

祖先[考点]树的基本概念[解析]一棵树上的任何结点(不包括根本身)称为根的子孙。若B是A的子孙，则称A是B的祖先。20.参考答案：O(n2)21.参考答案：C[解析]本题主要考查的知识点是一个具有n个顶点的有向完全图的弧数。[要点透析]任何两点之间都有弧的有向图称为有向完全图。一个具有n个顶点的有向完全图的弧数为，则本题中的有向完全图应具有的弧数为90条。22.参考答案：12[考点]完全二叉树性质[解析]完全二叉树第5层最多应有25-1=16个结点＞9，所以此完全二叉树深度为5，叶子结点个数为：23+9/2=12。23.参考答案：入队24.参考答案：因4*5*6=120，所以A[0…4，0…5]共占120个字节。

(2)a45的起始地址为：

Loc(a45)=1000+120-4=1116

(3)按行优先顺序排列时：

Loc(a25)=1000+(2*6+5)*4=1068

(4)按列优先顺序排列时：

Loc(a25)=1000+(5*5+2)*4=110825.参考答案：先序序列：ABEFKLCGDHIJ

后序序列：EKLFBGCHIJDA

层次序列：ABCDEFGHIJKL26.参考答案：栈顶27.参考答案：[考点]普里姆算法应用[解析]由起始结点，每次选取边上权值最小的连入最小生成树中。28.参考答案：280[考点]数组存储位置的计算[解析]第20个元素地址=225+(21-10)×5=280。29.参考答案：D30.参考答案：利用两个栈从1，2，3，4得到4，1，3，2的操作步骤为：H1，P1，H2，H1，H1，H1，P1，H2，P2，P2，P1，H2，P2，P1，H2，P2。[考点]栈的存取规则：先进后出31.参考答案：不一定32.参考答案：A[考点]二维数组元素的地址计算[解析]a[5，5]的地址是1000+[(5+1)×5+5]×5=1175。33.参考答案：栈空[考点]栈的操作容易出现的现象[解析]栈下溢是指在栈空时进行出栈操作。34.参考答案：C[考点]二叉排序树的插入及查找[解析]得到二叉排序树见下图，由图可知，查找元素60需进行4次比较。

35.参考答案：DBFHGECA36.参考答案：A[考点]本题主要考查的知识点是二叉树的遍历。

中序序列是abcdef，则ab为根结点c的左子树的中序序列，def为根结点c的右子树的中序序列，说明结点c既有左子树叉有右子树。故本题答案为A。37.参考答案：A[考点]压缩存储的目的[解析]对特殊矩阵采用压缩存储的目的主要是为了减少不必要的存储空间。38.参考答案：O(log2n)39.参考答案：先序遍历：ABDEFC。