2021年自考专业(计算机网络)数据结构考试真题及答案

自考计算机网络的专业核心能力是计算机网络安装与维护能力、网络应用软件的编程能力，需要掌握计算机网络专业知识技术，能从事计算机网络安装、调试、运行、维护及管理，以及企事业单位信息化建设工作，适应企事业单位生产、管理、经营、服务第一线需要的高等应用型技术人才。上学吧自考计算机网络题库是专门为自考计算机网络考试提供专业且具有品质的题库，希望可以帮助到考生。现在就点击安装APP刷题。以下为试卷的详细内容：

一、单项选择题 每小题2分，共15小题参考答案见试卷末尾

1、下列关于数据项和数据元素的叙述中，正确的是（）

A.数据项只能是数值类型

B.数据项可以包含数据元素

C.数据元素是数据的基本单位

D.数据元素是由数据项组成的集合

2、下列关于抽象数据类型的叙述中，正确的是（）

A.抽象数据类型与具体实现相关

B.抽象数据类型是由C语言本身提供的

C.抽象数据类型是C语言提供的类型的逻辑描述

D.抽象数据类型将数据定义和数据操作封装在一起

3、设有初始为空的栈S，入栈序列是f，e，d，c，b，a，出栈序列是d，e，a，b，c，f，则需要为S分配的空间大小至少是（）

A.2

B.3

C.4

D.5

4、指针head指向带头结点的单链表L的表头，结点结构为：data next，其中，data为int型，next是指向后继结点的指针。指针p指向L中的首个数据结点，指针q指向p的后继结点。现要交换p、q所指向的两结点中的data值，下列选项中，不能完成该任务的操作是（）

A.head->next=q;p->next=q->next;q->next=p

B.p->next=q->next;head->next=q;q->next=p

C.q->next=p;p->next=q->next;head->next=q

D.int temp=p->data;p->data=q->data;q->data=temp

5、采用行优先压缩存储方式保存6行6列对称矩阵A的上三角部分，每个元素占2个单元，若A中第一个元素a11的存储地址是10，则元素a34的存储地址是（）

A.22

B.26

C.34

D.40

6、已知广义表L=（（l，i），h），（x，i，a，o）），下列运算中，结果得到h的是（）

A.head（tail（L））

B.head（tail（head（L）））

C.head（head（tail（L）））

D.head（head（tail（tail（L））））

7、下列关于二叉树的叙述中，错误的是（）

A.二叉树可以为空

B.二叉树可以保存在数组中

C.二叉树中叶结点的个数多于度为1结点的个数

D.二叉树中叶结点的个数多于度为2结点的个数

8、若二叉树的前序遍历序列是ABCD，中序遍历序列是ACDB，则其后序遍历序列是（）

A.ABDC

B.ACDB

C.CDBA

D.DCBA

9、对下图进行广度优先搜索遍历，正确的遍历序列是（）

A.bdeac

B.badce

C.acedb

D.abced

10、关于图G的深度优先生成树T1与广度优先生成树T2，下列叙述中正确的是（）

A.T1与T2一定相同

B.T1与T2可能相同

C.T1与T2一定不相同

D.T1与T2中所含边数不相等

11、对n个记录进行排序，最坏情况下，时间复杂度不是O（n）2的排序方法是（）

A.直接插入排序

B.冒泡排序

C.快速排序

D.堆排序

12、下列排序方法中，不宜在链表上实现的是（）

A.直接插入排序

B.快速排序

C.归并排序

D.基数排序

13、若元素序列11，13，15，7，8，9，23，2，5是采用下列排序算法之一得到的第2趟排序后的结果，则该排序算法是（）

A.直接插入排序

B.冒泡排序

C.选择排序

D.二路归并排序

14、在长度为n（≥100）的有序线性表中进行二分查找，查找成功时，查找长度不多于4的关键字个数是（）

A.4

B.7

C.15

D.100

15、将下列数据分别依次插入到初始为空的二叉排序树中，能得到高度最低二叉排序树的是（）

A.9，7，2，1，4，10

B.6，4，1，8，10，5

C.5，1，2，6，3，4

D.2，4，7，5，8，10

二、填空题 每空2分，共10空参考答案见试卷末尾

1、非空的带头结点的单循环链表中，终端结点的指针域指向的是链表的（）

2、已知循环队列存储在一维数组A[0..n-1]中，头指针是front，尾指针是rear，初始时front的值和rear的值均是0，则第1个入队元素存储在数组中存储位置的下标是（）

3、将中级表达式9-（2+4*7）转换为后缀表达式的结果是（）

4、广义表G=（27，G）的深度是（）

5、具有n（n≥1）个结点的二叉树，采用二叉链表存储，空指针域的个数是（）

6、两个无向连通图均含有10个顶点，它们之间的边数差最大是（）

7、有向图G存在拓扑序列的条件是（）

8、若用C语言的数组A保存含n（n≥10）个元素的大根堆，则第3大元素在A中的下标最大是（）

9、分块查找又称为（）

10、非空的3阶B树中，每个非根结点中含有的关键字个数最少是（）

三、解答题 每小题5分，共4小题参考答案见试卷末尾

1、链栈为什么不必设置头结点

2、已知字符集{a，b，c，d，e}中各字符出现的频次分别为2，3，6，8，10，对字符集进行哈夫曼编码，字符a的编码是000，字符e的编码是11，则其余3个字符的编码分别是什么

3、设有向图G如题28图所示，给出图G的邻接矩阵

4、设有关键字16，15，32，11，6，30，将它们依次保存在哈希表（长度为7的一维数组）中，哈希函数为H（k）=k mod7，采用线性探查法解决冲突。已知关键字16已放置在数组下标为2的位置。请画出哈希表

四、算法阅读题 每小题5分，共4小题参考答案见试卷末尾

1、程序f30（）创建了一个带头结点的含n（n≥3）个数据结点的单链表L，L前两个数据结点中的data值均为1，从第3个结点开始，结点的data值是其前两个结点data值之和。请在空白处填上适当内容将算法补充完整

2、已知图的邻接矩阵表示的存储结构定义如下，算法f31（）统计图中各顶点的度，并返回最大度数。请在空白处填上适当内容将算法补充完整

3、已知二叉排序树结点的数据类型定义及二叉排序树的某个算法f32()如下。

4、阅读程序，并回答下列问题

五、算法设计题参考答案见试卷末尾

1、设n个整数存放在数组A中，请编写函数f34（int A[]，int n），将所有奇数调整到所有偶数之前

参考答案：

【一、单项选择题】

1~5 CDCCC 6~10 BCDBB

11~15点击安装“计算机网络自考APP”查看答案

【二、填空题】

1 头结点 2 0 3 9 2 4 7 * + - 4 ∞ 5 n+1

6~10点击安装“计算机网络自考APP”查看答案

【三、解答题】

1 链栈是运算受限的单链表，链表的头指针可以看作是栈顶指针，入栈和出栈操作仅限制在表头位置（栈顶）进行，因此不必设置头结点。 2 字符b的编码是001，字符c的编码是01，字符d的编码是10。
[说明]按照算法及题目条件构造的哈夫曼树结果如下图所示。
34

【四、算法阅读题】

1234 (1)f33=2
(2)在数组中采用二分查找（折半查找）法查找指定元素，若查找成功，则返回指定元素在数组中的下标；如果查找失败，则返回-1。

【五、算法设计题】

1

如果这样刷题不过瘾，请立即安装APP刷题，历年真题、高质量模拟题应有尽有。