2025年学历类自考专业(计算机信息管理)管理经济学-数据结构导论参考题库含答案解析.docxVIP

2025年学历类自考专业(计算机信息管理)管理经济学-数据结构导论参考题库含答案解析

一、单选题（共35题）

1.

在顺序表中，若第i个元素之前有k个元素被删除，则第j个元素（ji）在顺序表中的新位置是（）。

A.j-k

B.j+k

C.j-k-1

D.j+i-k

【选项】

A.j-k

B.j+k

C.j-k-1

D.j+i-k

【参考答案】A

【解析】顺序表中删除第i个元素前的k个元素，相当于所有下标≥i的元素会向前移动k位。原第j个元素（ji）的新位置下标为j减去向前移动的位数k，即j-k。选项B、C、D均未正确反映元素移动规律。

2.

栈的特点是“先进后出”。若元素入栈顺序为A、B、C、D、E，则不可能的出栈序列是（）。

A.E、D、C、B、A

B.A、B、C、D、E

C.B、C、D、E、A

D.C、A、D、B、E

【选项】

A.E、D、C、B、A

B.A、B、C、D、E

C.B、C、D、E、A

D.C、A、D、B、E

【参考答案】D

【解析】选项D中，C为第一个出栈元素，说明A、B在C入栈后仍在栈中。若C出栈后直接出A，则A需在B之前入栈且未出栈，但此时B尚未出栈，A不可能先于B出栈，故D不合法。其他选项均可通过合法操作实现。

3.

一棵完全二叉树有500个节点，则其叶子节点数为（）。

A.250

B.251

C.249

D.500

【选项】

A.250

B.251

C.249

D.500

【参考答案】A

【解析】完全二叉树中，若节点数n满足2^h≤n2^(h+1)-1，则叶子节点数为n-(2^h-1)。因500接近512（2^9=512），故高度h=9，非叶节点数为2^9-1=511（仅适用于满二叉树）。因500511，实际非叶节点数为前8层节点数255+第9层非叶节点数（500-255=245中父节点数?245/2?=122），总计255+122=377，叶子节点数=500-377=123。但更简算法：n=500为偶数，叶子节点数=?n/2?=250。

4.

对长度为n的线性表进行冒泡排序，最坏情况下时间复杂度是（）。

A.O(n)

B.O(nlogn)

C.O(n2)

D.O(1)

【选项】

A.O(n)

B.O(nlogn)

C.O(n2)

D.O(1)

【参考答案】C

【解析】冒泡排序通过相邻元素比较交换实现排序。最坏情况（逆序初始序列）需进行n-1轮排序，每轮比较n-i次（i为轮数），总比较次数为n(n-1)/2，故时间复杂度为O(n2)。选项A适用于已有序序列，选项B为快速排序平均复杂度，选项D为常数量级操作。

5.

哈希表长度为11，哈希函数H(key)=keymod11，采用线性探测法处理冲突。若插入关键字序列{18,26,35,42,50}，则关键字50的存储位置是（）。

A.5

B.6

C.7

D.8

【选项】

A.5

B.6

C.7

D.8

【参考答案】D

【解析】

-18mod11=7→存入位置7

-26mod11=4→存入位置4

-35mod11=2→存入位置2

-42mod11=9→存入位置9

-50mod11=6→位置6空闲，直接存入

因此50的位置为6，选项B正确。注：原参考答案D为错误，应为B。

6.

对一个有向图进行拓扑排序，若存在多个入度为0的顶点，则（）。

A.排序结果唯一

B.排序结果不唯一

C.图中必有环

D.无法进行拓扑排序

【选项】

A.排序结果唯一

B.排序结果不唯一

C.图中必有环

D.无法进行拓扑排序

【参考答案】B

【解析】拓扑排序中，每次可选择任意入度为0的顶点作为下一个顶点。若存在多个入度为0的顶点，选择顺序不同会导致不同排序序列，故结果不唯一（选项B）。选项C错误，环会导致无入度为0的顶点；选项D仅在存在环时成立。

7.

用邻接矩阵存储有n个顶点和e条边的无向图，则矩阵中非零元素个数为（）。

A.e

B.2e

C.n2

D.n(n-1)/2

【选项】

A.e

B.2e

C.n2

D.n(n-1)/2

【参考答案】B

【解析】无向图的邻接矩阵是对称矩阵，每条边(i,j)会在矩阵中对应两个非零元素（i,j和j,i）。因此非零元素个数为2e（选项B）。选项A为邻接表的存储特征，选项C为矩阵总元素数，选项D为完全无向图的边数。

8.

下列排序算法中，稳定且时间复杂度为O(nlogn)的是（）。

A.快速排序

B.堆排序

C.归并排序

D.希尔排序

【选项】

A.快速排序

B.堆排序

C.归并排序

D.希尔