求全国2019年4月高等教育自学考试数据结构试题以及答案

1.都考些什么课程？ 计算机及应用专业（独立本科段）考试课程与学分要求：考试课程不得少于14门，总学分不得少于76学分。

必设课程及学分：

公共政治课(4)、外语(14)、高等数学(10)、物理(工)(6)、概率论与数理统计(3)、离散数学(4)、计算机系统结构(4)、操作系统(5)、面向对象顺序 设计(4)、数据结构(4)、 软件工程(4)、数据库原理(5)、计算机网络及通信(6)、工程经济(3)。

2．实践性环节及要求：

(1)含实验的课程及实验所占学分： 物理(工)(1)、操作系统(1)、数据结构(1)、面向对象顺序 设计(1)、数据库原理(1)、软件工程(1)；

(2)含课程设计的课程及课程设计所占学分：在数据库原理(1)、软件工程(1)或面向对象顺序 设计中任选一门；

(3)毕业设计(论文)并辩论 。

2.考试费用是多少？每科30元 实践课60元

3.读几年，什么时候报名？ 每年4月 10月考，各四科，3月 9月报名。 自考要一门一门地考试，顺利的话，两年拿证，学位证，本科证。八年时间考完有效。

4.我明年毕业，什么时候报名合适？

明年3月报名。

5.报名的 时候必需 要大专毕业证吗？ 学校出证明，就可以报。

6.听说可以免考，就我这个专业具体免哪些课程？我只过了英语三级和计算机操作员中级！

大专证免考公共课。

7.自考难么？如果在内大读几年？

国考难，省考简单。

内蒙古大学继续教育学院

打电话问问内蒙古大学，看看有没有助考，助考就是考试院校办的辅导班，交一定的费用，几千块钱吧。考前辅导，有考试题库，过的容易，辩论 容易过，好拿证。

呼和浩特市自考办 呼市招生考试管理中心 0471-6916743

一、指导思想

高等教育自学考试计算机及应用专业(独立本科段)是为满足社会开展 普遍需要而设置的；同时，根据高等教育自学考试的特点，具有较强的针对性和实用性，注重考核应考者对本专业的基本理论、基础知识和基本技能的掌握水平 以及运用所学知识剖析 和解决实际问题的能力。

二、学历层次和规格

本专业为本科层次，在总体上与全日制普通高校相近专业本科的水平相一致。本专业的课程均采用学分计算，每门课程考试合格后发给单科合格证书，并获得本课程的相应学分。

凡依照 本专业(独立本科段)考试计划的规定，取得5门公共课、9门专业基础课和专业课程合格分数 ，累计不少于76学分，并通过相应课程的实验考核，完成毕业设计并合格，思想品德鉴定契合 要求者，并核准专科专业毕业证书或加考课程后，发给本科毕业证书；同时，其学业水平到达 了国家规定的学位规范 ，依照 《中华人民共和国高等教育法》第二十二条和《中华人民共和国学位条例》的规定，由具有学位授予权的主考学校授予学士学位。

三、专业培养目标和基本要求

高等教育自学考试计算机及应用专业(独立本科段)培养从事计算机软件和硬件设计、开发及应用的高层次工程技术人才。

本专业要求应考者努力学习马克思列宁主义、毛泽东思想、邓小平理论，树立爱国主义、集体主义和社会主义思想，遵守法律、法规，具有良好的思想品德。要求能系统地掌握计算机软件、硬件的基础理论和基本知识；具有计算机应用系统的剖析 、设计、实现及维护的知识与技能；具有查阅 本专业外文资料的能力。

四、考试课程与学分要求：考试课程不得少于14门，总学分不得少于76学分。

1．必设课程及学分：

公共政治课(4)、外语(14)、高等数学(10)、物理(工)(6)、概率论与数理统计(3)、离散数学(4)、计算机系统结构(4)、操作系统(5)、面向对象顺序 设计(4)、数据结构(4)、 软件工程(4)、数据库原理(5)、计算机网络及通信(6)、工程经济(3)。

2．实践性环节及要求：

(1)含实验的课程及实验所占学分： 物理(工)(1)、操作系统(1)、数据结构(1)、面向对象顺序 设计(1)、数据库原理(1)、软件工程(1)；

(2)含课程设计的课程及课程设计所占学分：在数据库原理(1)、软件工程(1)或面向对象顺序 设计中任选一门；

(3)毕业设计(论文)并辩论 。

3．说明：

(1)每门课程的学分反映了课程的比重和内容的份量，每个学分大致相当于全日制普通高等学校本科课程的18学时；

(2)各门课程的考试内容、要求和试题难度以及实践环节的内容、要求和考核方法 ，由各门课程的自学考试大纲规定。实践环节的考核在主考学校或主考学校认可的单位进行；

(3)在下列课程中任选一门作课程设计：数据库原理、软件工程或面向对象顺序 设计。课程设计占1学分；

(4)本科应考者在全部课程考试合格后，必需 进行毕业设计，题目由主考学校确定，也可结合应考者的工作实践自选，但必需 经主考学校审批同意。主考学校可以为考生指派指导教师。毕业设计完成后由主考学校组织评阅辩论 ；

(5)报考本专业独立本科段的条件：

①本专业专科毕业生可直接报考本专业；

②电子电工信息类非本专业专科毕业生报考本专业，须加考：计算机组成原理(4)、汇编语言顺序 设计(4)两门课程；

③工科类非电子电工信息类专业专科毕业生报考本专业，须加考：计算机组成原理(4)、汇编语言顺序 设计(4)、模拟电路和数字电路(8)三门课程；

④其它专业专科毕业生报考本专业，必需 加考：计算机组成原理(4)、汇编语言顺序 设计(4)、模拟电路和数字电路(8)、数据结构导论(4)、高级语言顺序 设计(4)五门课程。

五、课程说明与自学用书

1．公共政治课(略)。

2．英语(二)

(1)课程说明：本课程为本专业(独立本科段)的一门公共课。本课程的目的是使应考者掌握4000个单词(含中学阶段1600个单词)、一定量的习语和系统的语法知识，具有较强的查阅 能力和一定的英译汉能力以及初步的听、说、写和汉译英的能力，使其能以英语为工具，获取专业所需要的信息，并为进一步提高英语水平打下较好的基础。应考者在学完本课程后，应能借助词典独立查阅 与后期课文难度相当的一般性资料并能译成汉语，理解基本正确，译文基本通顺。

(2)自学教材：《大学英语自学教程》(上、下册)(全国考委组编)，高远主编，高等教育出版社出版。

3．高等数学(工本)

(1)课程说明：本课程为本专业(独立本科段)的一门公共课。通过学习，要求应考者系统地获得一元函数的微积分学、多元函数微积分学(其中包括向量代数与空间解析几何)、常微分方程、级数的基本知识、理论和办法 。要求应考者掌握各有关内容的基本概念、基本理论和基本办法 ，具有比较熟练的运算能力和剖析 能力、空间想象能力及笼统 数学模型的初步能力，为学习后续课程和进一步扩大数学知识奠定必要的基础。

(2)自学教材：《高等数学》(上、下册)(全国考委组编)，陆庆乐主编，西安交通大学出版社出版。

4．物理(工)

(1)课程说明：本课程为本专业(独立本科段)的一门公共课。本课程内容包括：力学、热学、电磁学、振动、动摇 、动摇 光学和近现代物理学的基础理论，及其在科学技术和生产实际中应用的初步知识；物理实验的理论基础和基本技能；现代物理主要分支学科开展 的专题讲座。本课程是理工科各专业的一门重要的基础课，可为应考者掌握科学的思想办法 、培养科研能力、开阔思路、激发探索和发明 精神、提高科学素质及进一步学习新理论、新技术奠定必要的物理学基础。

(2)自学教材：《物理(工)》(全国考委组编)，丁俊华、祁有龙主编，辽宁大学出版社出版。

5．概率论与数理统计

(1)课程说明：本课程为本专业(独立本科段)的一门公共课。是研究随机现象统计规律的一门数学课。本课程概率论局部 包括：随机事件及其概率、随机变量、多维随机变量和随机变量的数字特征等外 容；数理统计局部 包括抽样散布 、参数估计、假设检验、方差剖析 、回归剖析 和正交试验设计等外 容。通过本课程的学习，要求应考者理解概率论的基本概念，熟悉随机事件及其概率的重要性质，熟悉随机变量的常用散布 ，并会进行相应的计算。掌握数理统计中有关参数估计和假设检验的办法 ，了解方差剖析 、回归剖析 和正交试验设计。

(2)自学教材：《工程数学(概率论与数理统计)》(全国考委组编)，范金城主编，辽宁大学出版社出版。

6．离散数学

(1)课程说明：本课程为本专业(独立本科段)的一门专业基础课。课程内容为：命题逻辑和一阶谓词逻辑的基本概念和基本演算；集合的概念和运算、二元关系和函数；代数运算和代数系统的基本性质、半群和群、队和域、格和布尔代数；图的基本概念、树、欧拉图和哈密顿图、平面图、图着色、赋权图、二部图等。通过本课程的学习，使应考者有笼统 思维和逻辑推理能力，掌握计算机科学技术常用的离散数学中的概念、性质和运算。

(2)自学教材：《离散数学》(全国考委组编)，左孝凌主编；

(3)参考用书：《离散数学》，左孝凌等编，上海科技出版社1982年出版。

7．工程经济

(1)课程说明：本课程为本专业(独立本科段)的一门专业基础课。

(2)自学教材：《工程经济》(全国考委组编)，陈锡璞编，机械工业出版社出版。

8．数据结构

(1)课程说明：本课程为本专业(独立本科段)的一门技术基础课。课程内容为各种主要的数据结构及其在计算机中的实现。主要内容有：线性表，栈，队列，串、多维数组和广义表，树和二叉树，多维数组、广义表和一般的图结构等；数据在内存中的管理以及在外存中的表示(文件结构)；排序和检索等常用算法。通过本课程的学习，使应考者掌握如何根据问题的需求合理地组织数据，在计算机中有效地存储数据和处置 数据，并初步了解算法设计和剖析 。

(2)自学教材：《数据结构》(全国考委组编)，黄刘生主编；

(3)参考用书：《数据结构》，严蔚敏、吴伟民编，清华大学出版社1992出版。

9．数据库原理

(1)课程说明：本课程为本专业(独立本科段)的一门专业基础课。内容为：数据库概论，关系数据模型，关系运算理论，SQL语言和QBE语言，关系数据库的规范化，数据库设计的全过程，数据库的维护 ，数据库管理系统的结构，以及散布 式数据库与面向对象的数据库等数据库新技术的介绍。通过本课程的学习，使应考者掌握数据库的基本原理和技术，能应用现有数据库管理系统，掌握数据库设计和数据库系统的开发办法 。

(2)自学教材：《数据库原理》(全国考委组编)，丁宝康主编；

(3)参考书：《数据库系统概论》(第二版)，萨师煊、王珊编，高等教育出版社1991年出版。

10．计算机系统结构

(1)课程说明：本课程为本专业〔独立本科段〕的一门专业课。课程内容为：计算机系统结构的基本概念，数据表示，指令系统的设计和改良 ，CISC与RISC，输入输出技术，虚拟存储器，存储体系， Cache存储器，流水和向量处置 机，阵列处置 机，多处置 机多计算机系统，性能评测。通过本课程的学习，使应考者掌握计算机组织和系统结构的基本知识，熟悉现代计算机中各种典型系统结构的原理、组织、关键技术和性能剖析 ；了解结构设计的基本办法 ；具有一定的选择和使用计算机系统的能力。

(2)自学教材：《计算机系统结构》(全国考委组编)，李学干主编；

(3)参考用书：《计算机系统结构》，陆鑫达编，高等教育出版社出版。

11．操作系统

(1)课程说明：本课程为本专业(独立本科段)的一门专业课。课程内容为：操作系统的典型算法和结构，作业管理，进程管理，存储管理，设备管理，文件管理，操作系统结构设计以及UNIX操作系统介绍。

通过本课程的学习，使应考者掌握操作系统的基本结构、设计原理及实现办法 ，了解它与硬件和其它系统软件的关系，能使用和剖析 经常见 的操作系统。

(2)自学教材：《操作系统》(全国考委组编)，谭耀明主编；

(3)参考用书：《计算机操作系统》(第二版)，汤子瀛等编，西安电子科大出版社出版。

12．面向对象顺序 设计

(1)课程说明：本课程为本专业(独立本科段)的一门专业课。课程内容有：面向对象的基本概念和要素，包括类、对象、类的特性、消息传递等,C语言基础，包括变量、类型、数组、指针、结构，控制语句，顺序 结构等，C++对C的改良 局部 ，包括注释，作用域运算符，宏定义等；类，包括封装、数据成员、函数成员、可见性控制、构造函数与析构函数、继承、多态性等；模板；异常处置 等。

通过本课程的学习，使应考者了解面向对象的思想和基本概念，参照 C++语言的各种面向对象的成分加深对面向对象的核心概念类和对象的理解和掌握，能够熟练使用 C++语言进行应用顺序 的开发。

(2)自学教材：《面向对象顺序 设计》(全国考委组编)，刘振安主编；

(3)参考用书：《C++顺序 设计实用教材》，张国峰编著，清华大学出版社出版。

13．软件工程

(1)课程说明：本课程为本专业(独立本科段)的一门专业课。课程内容包括：软件工程的基本概念；可行性研究与计划，需求剖析 和规格说明办法 ，设计办法 ，编程办法 ，检验和测验 办法 ，维护办法 ，面向对象的软件开发办法 ，软件工具和环境等。通过本课程的学习，使应考者掌握软件工程的有关概念和各阶段的主要技术、办法 与工具，具备组织和从事软件开发的基天性 力。

(2)自学教材：《软件工程》(全国考委组编)，陆丽娜编；

(3)参考用书：《软件工程》(修订版)，张海藩编，清华大学出版社1992出版。

14．计算机网络与通信

(1)课程说明：本课程为本专业(独立本科段)的一门专业课。课程内容包括：数据通信技术，包括数据传输原理，通信交换技术，通信规程，过失 控制等；计算机网络体系结构，OSI中的物理层，数据链路层，网络层，传输层及高层协议；计算机局域网，网络互连，因特网的实用技术与应用等。通过本课程的学习，使应考者了解简化的ISO/OSI参考模型,掌握计算机网络基本原理和概念，熟悉计算机网络典型技术与协议，具备适应网络开展 的能力。

(2)自学教材：《计算机网络与通信》(全国考委组编)，冯博琴编。

(3)参考用书：《计算机网络》，雷震甲、马玉祥编著，西安电子科技大学出版社1996年出版。

引用

当然是数据结构导论相对容易学，导论就是大约 概述下，内容不是很深。

全国2019年10月高等教育自学考试

数据结构导论试题

课程代码：02142

一、单项选择题(本大题共15小题，每小题2分，共30分)

在每小题列出的四个备选项中只有一个是契合 题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1．下列描述中正确的是( )

A.数据元素是数据的最小单位

B.数据结构是具有结构的数据对象

C.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合

D.算法和顺序 原则上没有区别，在讨论数据结构时两者是通用的

2．归并排序的时间复杂度是( )

A．O（n2）

B.O（nlog2n）

C.O（n）

D.O（log2n）

3．二分查找的时间复杂度是( )

A．O（n2）

B.O（nlog2n）

C.O（n）

D.O（log2n）

4．顺序存储的表中有90000个元素，已按关键字值升序排列，假设对每个元素进行查找的概率相同，且每个元素的关键字值皆不相同，用顺序查找法查找时，需平均比较的次数为( )

A．25000

B.30000

C.45000

D.90000

5．散列文件是一种( )

A．顺序文件

B.索引文件

C.链接文件

D.计算寻址文件

6．两个矩阵A：m×n，B：n×p相乘，其时间复杂度为( )

A．O(n)

B.O(mnp)

C.O(n2)

D.O（mp）

7.常用于函数调用的数据结构是( )

A.栈

B.队列

C.链表

D.数组

8．二维数组A［n］［m］以列优先顺序存储，数组A中每个元素占用1个字节，A［1］［1］为首元素，其地址为0，则元素A［i］［j］的地址为( )

A.（i-1）×m+(j-1)

B.(j-1)×n+(i-1)

C.(j-1)×n+i

D.j×n+i

9.图的广度优先搜索使用的数据结构是( )

A．队列

B.树

C.栈

D.集合

10．序列（21,19,37,5,2）经冒泡排序法由小到大排序，在第一次执行交换后所得结果为( )

A．(19，21，37，5，2)

B.(21，19，5，37，2)

C.(21，19，37，2，5)

D.(2，21，19，37，5)

11．数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种办法 称为( )

A．索引存储办法

B.顺序存储办法

C.链式存储办法

D.散列存储办法

12．在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的( )

A．直接前趋

B.直接后继

C.开始结点

D.终端结点

13．在已知头指针的单链表中，要在其尾部插进 一新结点，其算法所需的时间复杂度为( )

A．O（1）

B.O（log2n）

C.O（n）

D.O（n2）

14．在链队列中执行入队操作，( )

A．需判别队是否空

B.需判别队是否满

C.限制在链表头p进行

D.限制在链表尾p进行

15．一整数序列26，59，77，31，51，11，19，42，以二路归并排序从小到大排序，第一阶段的归并结果为( )

A.31，51，11，42，26，77，59，19

B.26，59，31，77，11，51，19，42

C.11，19，26，31，42，59，51，77

D.26，11，19，31，51，59，77，42

二、填空题(本大题共13小题，每小题2分，共26分)

请在每小题的空格中填上正确答案。错填、不填均无分。

16．下列顺序 段的时间复杂度为_______。

i=0；s=0；

while（s

{i++；

s=s+i；

}

17．数据的存储结构被分为顺序存储结构、_______、散列存储结构和索引存储结构4种。

18．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动_______个元素。

19．在单链表中，插进 一个新结点需修改_______个指针。

20．在队列结构中，允许插进 的一端称为_______。

21．稀疏矩阵采用的压缩存储办法 是_______。

22．向一个栈顶指针为top的链栈中插进 一个新结点*p时，应执行p->next=top和_______操作。

23．有m个叶结点的哈夫曼树所具有的结点数为_______。

24．在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结点编号。设根结点编号为1。若编号为i的结点有右孩子，那么其右孩子的编号为_______。

25．在一棵树中，_______结点没有前驱结点。

26．一个具有n个顶点的有向完全图的弧数是_______。

27．n个顶点的无向图G用邻接矩阵A［n］［n］存储，其中第i列的所有元素之和等于顶点Vi的_______。

28．选择排序的平均时间复杂度为_______。

三、应用题(本大题共5小题，每小题6分，共30分)

29．在栈的输入端元素的输入顺序为1，2，3，4，5，6，进栈过程中可以退栈，则退栈时能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，写出进栈、退栈过程，若不能，简述理由。（用push（x）表示x进栈，pop(x)表示x退栈）

30．已知一棵二叉树的中根遍历序列为CBEDFAGH，后根遍历序列为CEFDBHGA，画出该二叉树。

31．给定表（15，11，8，20，14，13），试按元素在表中的顺序将它们依次插进 一棵初始时为空的二叉排序树，画出插进 完成后的二叉排序树，并判断该二叉排序树是否为平衡二叉排序树，若为非平衡二叉排序树，将它调整为平衡二叉排序树。

32．如题32图所示无向图，（1）写出其邻接矩阵；（2）写出三种以顶点A为起点的深度优

先搜索顶点序列。

题32图

33．用冒泡排序法对数据序列（49，38，65，97，76，134，27，49）进行排序，写出排序过程。并说明冒泡排序是否为稳定排序。

四、算法设计题(本大题共2小题，每小题7分，共14分)

34.编写计算二叉树中叶子结点数目的算法。

35.开散列表的类型定义如下：

typedef struct tagnode

{keytype key;

struct tagnode*next;

}*pointer,node;

typedef pointer openhash［n］;

试写出开散列表上的查找算法。

0人赞 添加讨论(0) 回答 举报