2019 北京交通大学 925《数据结构》 考试大纲

北京交通大学考试试题（A卷）课程名称:数据结构与算法2011-2012学年第一学期出题教师:张勇(请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场)一、填空题（每空2分，共20分）1. 在顺序表中访问任意一个元素的时间复杂度均为，因此顺序表也称为的数据结构。

2．三维数组a[4][3][2](下标从0开始)，假设a[0][0][0]的地址为50，数据以行序优先方式存储，每个元素的长度为2字节，则a[2][1][1]的地址是。

3. 直接插入排序用监视哨的作用是。

4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子d的运算是。

5．对有14个元素的有序表A[1..14]进行折半查找，当比较到A[4]时算法结束。

被比较元素除A[4]外，还有。

6. 在AOV网中，顶点表示，边表示。

7. 有向图G可进行拓扑排序的判别条件是。

8. 若串S1=‘ABCDEFGHIJK’,S2=‘451223’,S3=‘####’,则执行Substring(S1,Strlength(S3),Index(S2,‘12’,1))的结果是。

二、选择题（每空2分，共20分）1.在下列存储形式中，哪一个不是树的存储形式？（）A．双亲表示法B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法2.查找n个元素的有序表时，最有效的查找方法是（）。

A．顺序查找B．分块查找C．折半查找D．二叉查找3.将所示的s所指结点加到p所指结点之后，其语句应为（）。

p(A) s->next=p+1 ; p->next=s;(B) (*p).next=s; (*s).next=(*p).next; (C) s->next=p->next ; p->next=s->next; (D) s->next=p->next ; p->next=s;4.在有向图的邻接表存储结构中，顶点v 在链表中出现的次数是（ ）。

数据结构科目考研大纲
数据结构是计算机科学与技术专业考研的重要科目之一，其大纲主要包括以下内容：
一、基本概念。

1. 数据结构的基本概念和术语。

2. 算法的基本概念和特性。

3. 算法复杂度分析。

二、线性表。

1. 线性表的顺序存储结构和链式存储结构。

2. 线性表的基本操作及实现。

3. 线性表的应用。

三、栈和队列。

1. 栈和队列的定义和基本操作。

2. 栈和队列的顺序存储结构和链式存储结构。

3. 栈和队列的应用。

四、树与二叉树。

1. 树的基本概念和性质。

2. 二叉树的基本概念和性质。

3. 二叉树的存储结构和基本操作。

4. 树和二叉树的遍历。

五、图。

1. 图的基本概念和性质。

2. 图的存储结构和基本操作。

3. 图的遍历和最小生成树。

4. 图的最短路径和拓扑排序。

六、查找。

1. 查找的基本概念和分类。

2. 顺序查找和折半查找。

3. 散列查找和二叉排序树。

七、排序。

1. 排序的基本概念和分类。

2. 插入排序、交换排序、选择排序。

3. 快速排序、堆排序、归并排序。

4. 外部排序。

以上是数据结构科目考研大纲的主要内容，考生在备考过程中需要深入理解各个知识点，并能够灵活应用到实际问题中。

希望对你有所帮助。

课程设计题目（2019版）：（1-8题必做）1、系统进程统计（必做）（链表）[问题描述]设计一个程序，每秒统计一次当前系统的进程状况，并按照内存使用自多到少排序打印输出相关信息。

对已经结束的进程，另外给出一个列表，并显示该进程的结束时间和持续时间。

[基本要求]（1）该题目要求使用两个链式线性表。

一个链表存储当前活动进程，要求使用双向链表，排序要求是按照内存使用自多到少排序。

另外一个链表存储已结束进程，要求使用单向链表，按照结束时间离当前时间的关系排序，最近的最前，最远的最后。

（2）每秒在窗口内更新一次当前系统进程情况，输出内容包括：进程名，持续时间，内存使用情况。

（3）每秒在窗口内更新一次已结束进程情况，输出内容包括：进程名，持续时间，结束时间。

（4）注意进程在这两个链表中的切换，一个进程既可被结束，也可以过一段时间后再被运行。

2、算术表达式求值(必做) （栈）[问题描述]一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。

假设操作数是正实数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#6+15*（21-8/4）#。

引入表达式起始、结束符是为了方便。

编程利用“运算符优先法”求算术表达式的值。

[基本要求]（1）从键盘或文件读入一个合法的算术表达式，输出正确的结果。

（2）显示输入序列和栈的变化过程。

（3）考虑算法的健壮性，当表达式错误时，要给出错误原因的提示。

（4）实现非整数的处理（*）。

3、公共钥匙盒（必做）（线性表，栈，队列）[问题描述]有一个学校的老师共用N个教室，按照规定，所有的钥匙都必须放在公共钥匙盒里，老师不能带钥匙回家。

每次老师上课前，都从公共钥匙盒里找到自己上课的教室的钥匙去开门，上完课后，再将钥匙放回到钥匙盒中。

钥匙盒一共有N个挂钩，从左到右排成一排，用来挂N个教室的钥匙。

一串钥匙没有固定的悬挂位置，但钥匙上有标识，所以老师们不会弄混钥匙。

819数据结构考研大纲2024数据结构是计算机科学与技术专业中一门重要的基础课程，它主要研究计算机中数据的组织、存储和管理方式，以及基本的数据操作和算法。

数据结构考研大纲旨在培养学生对数据结构的理解和应用能力，为其以后的研究和工作提供必要的基础。

根据2024年的数据结构考研大纲，该课程主要包括以下几个方面的内容：1.线性表：线性表是最基本的一种数据结构，它包括顺序表和链表两种形式。

顺序表是通过一段连续的存储空间来存储数据，链表使用指针将不连续的存储单元连接起来。

学生需要掌握线性表的存储结构、基本操作和常见应用。

2.栈和队列：栈是一种先进后出的数据结构，队列是一种先进先出的数据结构。

学生需要学习栈和队列的基本操作，以及它们在计算机系统中的应用，如操作系统的进程调度和内存管理。

3.树和二叉树：树是一种非线性的数据结构，它由节点和边组成，节点之间存在一对多的关系。

二叉树是一种特殊的树，每个节点最多有两个子节点。

学生需要学习树和二叉树的表示方法、遍历算法和常用的应用，如哈夫曼树和二叉查找树。

4.图：图是一种用于表示多对多关系的数据结构，它由节点和边组成。

学生需要学习图的存储结构、遍历算法和最短路径算法，如Dijkstra算法和Floyd-Warshall算法。

5.排序和查找算法：排序算法是将一组数据按照某种规则进行排序的算法，常见的排序算法有插入排序、冒泡排序和快速排序等。

查找算法是在给定数据集合中找到特定元素的算法，学生需要学习常见的查找算法，如顺序查找和二分查找。

6.文件存储结构：文件存储结构是将数据存储到硬盘上的一种方式，学生需要学习文件的组织方式，如顺序文件和索引文件，并了解文件的读写操作和常见的文件操作算法。

以上是2024年数据结构考研大纲的主要内容，通过学习这些知识，学生将能够掌握数据结构的基本理论和应用技巧，为以后的学习和工作打下坚实的基础。

数据结构是计算机科学与技术专业中一门重要的基础课程，对于学生的专业发展和职业发展具有重要意义。

902数据结构与C语言程序设计考研大纲902 数据结构与C语言程序设计考研大纲一、考试内容（一）数据结构1.线性表1）线性表的定义2）线性表的顺序存储和基本运算（查找、插入和删除）的实现3）线性表的链式存储和基本运算（查找、插入和删除）的实现4）线性表的应用2.栈、队列和矩阵1）栈和队列的定义2）栈和队列的实现（1）栈的顺序存储和基本操作（入栈、出栈和判栈空、栈满）的实现（2）栈的链式存储和基本操作（入栈、出栈和判栈空）的实现（3）队列的链式存储和基本操作（入队、出队和判队空）的实现（4）循环队列的定义和基本操作（入队、出队和判队空、队满）的实现3）栈和队列的应用4）矩阵的压缩存储（1）特殊矩阵（对称矩阵、三角矩阵、对角矩阵）的压缩存储（2）稀疏矩阵的压缩存储3.树与二叉树1）树的基本概念2）二叉树（1）二叉树的定义及性质（2）二叉树的顺序存储和链式存储（3）二叉树的先序、中序、后序遍历和层序遍历运算（4）线索二叉树的定义3）树和森林（1）树的存储结构（2）树（森林）与二叉树的相互转换（3）树和森林的遍历4）树与二叉树的应用（1）二叉查找树（Binary Search Tree）（2）平衡二叉树（Balanced Binary Tree 或Height-Balanced Tree或A VL Tree）（3）哈夫曼（Huffman）树和哈夫曼编码4.图1）图的基本概念2）图的存储（1）数组表示法（邻接矩阵表示法）（2）邻接表表示法3）图的遍历（1）深度优先搜索（DFS）算法（2）广度优先搜索（BFS）算法4）图的应用（1）最小（代价）生成树求解方法（Prim算法和Kruskal算法）（2）最短路径求解方法（Dijkstra算法和Floyd算法）（3）AOV-网和拓扑排序方法（4）AOE-网和关键路径求解方法5.查找1）查找的基本概念2）顺序查找法（1）顺序查找算法（2）平均查找长度计算3）折半查找法（1）折半查找算法（2）折半查找判定树的构造（3）平均查找长度计算4）动态查找表（1）二叉查找树（也称为二叉排序树）的构造及查找、插入和删除运算（2）平衡二叉树的构造及查找运算（3）B-树的特点及查找运算（4）平均查找长度计算5）哈希表（1）哈希表的构造及查找运算（2）平均查找长度计算6）字符串的模式匹配（1）基本的模式匹配算法（2）KMP模式匹配算法（模式串的next函数计算）6.内部排序1）简单排序方法（1）直接插入排序算法（2）冒泡排序算法（3）简单选择排序算法（4）简单排序算法的时间复杂度、空间复杂度及稳定性分析2）快速排序（1）划分过程及分析（2）快速排序算法及其时间复杂度、空间复杂度及稳定性分析3）堆排序（1）堆的定义及初始堆的建立（2）堆排序算法及其时间复杂度、空间复杂度及稳定性分析4）归并排序（1）归并过程及分析（2）二路归并排序算法的时间复杂度、空间复杂度及稳定性分析5）基数排序（1）多关键排序方法（2）链式基数排序方法及特点6）内部排序方法的比较和应用（二）C语言程序设计1. C语言基础（1）数据类型（基本类型和复合类型），常量与变量，运算符与表达式，类型转换；（2）关键字（保留字），用户定义标识符；（3）typedef，sizeof，static，extern，const。

814程序设计与数据结构考试大纲085211计算机技术专业一、考试目的本考试是全日制计算机技术专业学位研究生的入学资格考试之专业基础课，各语种考生统一用汉语答题。

各招生院校根据考生参加本考试的成绩和其他三门考试的成绩总分来选择参加第二轮，即复试的考生。

二、考试的性质与范围本考试是测试考生计算机科学基础知识的水平考试。

考试范围包括本大纲规定的C++语言程序设计和数据结构。

三、考试基本要求1. 具备扎实的C++语言程序设计基本功。

2. 具备设计数据结构和算法求解问题的基本能力。

四、考试形式本考试采取客观试题与主观试题相结合，单项技能测试与综合技能测试相结合的方法，强调考生设计数据结构和算法并编程实现来求解问题的能力。

试题分类参见“考试内容一览表”。

五、考试内容本考试包括两个部分：C++程序设计、数据结构。

总分150分。

I. C++程序设计1. 考试要求该部分要求考生对C++语言基本特性、面向对象程序设计方法和Visual C++编译器相关特性有很好的了解。

2. 题型选择题、读程序写出Visual C++下的执行结果、程序填空，共75分。

II. 数据结构1. 考试要求该部分要求考生掌握线性表（及其扩展：栈和FIFO队列）、树（包括基本的二叉树和堆、搜索树等特殊树结构）、图等基本数据结构及其上的操作；掌握二分搜索、Hash技术及搜索树等搜索方法；掌握选择、起泡、插入等简单排序算法，堆排序、快速排序、归并排序和谢尔（希尔）等快速排序算法，以及箱子、基数排序等非比较排序算法。

具备利用上述数据结构和算法以及设计新数据结构和算法来求解问题的能力。

2. 题型选择题、简答题、算法设计题，共75分。

要求考生用钢笔或圆珠笔做在答题卷上。

《程序设计与数据结构》考试内容一览表序号内容题型和题量时间（分钟）1 C++程序设计选择题、读程序写结果题、程序填空题2 数据结构选择题、简答题、算法设计题共计：180。

815 《C++与数据结构》考试大纲《C++与数据结构》之C++部分考试大纲一、考试目的本考试是全日制软件工程硕士学术学位研究生的入学资格考试之专业基础课，各语种考生统一用汉语答题。

各招生院校根据考生参加本考试的成绩和其他三门考试的成绩总分来选择参加第二轮，即复试的考生。

二、考试的范围以下是本科目的考试范围。

1. 数据封装1.1 对象占用内存大小；1.2 类的嵌套定义。

2. 存取控制2.1 public，private，friend关键字的含义及使用；2.2 将一个嵌套的类定义为友元；2.3 存取控制的应用。

3. 初始化和清理3.1 构造函数（及何时被调用）；3.2析构函数（及何时被调用）；3.3对象数组中对象的构造；3.4 默认构造函数。

4. 函数重载与默认参数4.1 函数名的重用；4.2 默认参数；4.3 类中的常量；4.4 初始化列表；4.5常量对象；4.6常量成员函数。

5. 内联函数以及名字控制5.1 内联函数；5.2 函数中的静态变量与对象；5.3构造与析构顺序；5.4名字空间。

6. 引用、复制构造函数以及运算符重载6.1 复制构造函数；6.2 默认复制构造函数；6.3 指向数据成员的指针；6.4 指向成员函数的指针；6.5 自动类型转换。

7. 继承与复合7.1 继承中的存取控制；7.2 构造、析构的调用顺序；7.3 私有继承；7.4 运算符重载与继承；7.5 upcasting。

8. 多态性与虚函数8.1 早/晚绑定；8.2 虚函数；8.3 多态性。

9. 模板9.1 类模板；9.2 函数模板；9.3 自动类型推断；9.4 模板特化；9.5 容器与迭代器。

三、考试基本要求1. 掌握C++的基本语法知识。

2. 综合运用C++解决一些基本问题的能力。

四、考试形式本考试包括两个部分：单项选择题、编程题。

I. 单项选择考试要求该部分考察考生对C++基本语法知识的掌握程度。

其中大部分选择题要求考生阅读一段程序，理解程序的执行过程，预测程序的输出结果。

计算机学院2020年自命题科目《数据结构》考试大纲一、考查目标1. 掌握数据结构及算法的基本概念、原理和方法。

2. 掌握数据逻辑结构、存储结构及建立其上数据基本操作实现，对基本算法能够进行相应时间和空间复杂度分析。

3. 运用数据结构原理和方法进行基本问题的分析求解，使用C或C++进行基本算法设计与实现。

二、考查内容1．数据结构与算法1.1 数据逻辑结构与存储结构1.2 数据类型与抽象数据类型1.3 算法概念及性质和时间及空间复杂度分析2．线性表2.1线性表概念和数据操作2.2线性表顺序与链式存储3. 栈、队列和数组3.1栈（1）栈概念与性质（2）栈的存储结构（3）栈的应用3.2队列（1）队列概念与性质（2）队列存储结构，循环队列（3）队列应用3.3矩阵（二维数组）（1）二维数组概念与存储（2）特殊矩阵压缩存储4. 二叉树与树4.1 二叉树（1）二叉树递归定义，特殊二叉树，基本性质（2）二叉树顺序和链式存储结构4.2 二叉树遍历4.3 线索二叉树基本概念和构造4.4 二叉树应用：二叉排序树，平衡二叉树，哈夫曼树与编码4.5 树与森林（1）树和森林概念及存储结构（2）树和森林遍历（3）树和森林与二叉树转换5.图5.1图相关概念性质：有向与无向图，邻接与连通，握手定理5.2图存储结构：邻接矩阵法，邻接表法5.3图的遍历：深度优先遍历，广度优先遍历5.4图的应用：最小生成树，最短路径，拓扑排序，关键路径6. 查找6.1查找基本概念，查找码与查找表，查找算法分析6.2 基于线性表查找：顺序查找法，二分查找法6.3 基于树表查找：二叉查找树6.4 基于散列表查找，冲突处理6.5 基于索引查找，B+树7.排序7.1排序基本概念，内排序与外排序，稳定性与算法分析7.2插入排序：直接插入排序，二分插入排序，表插入排序，希尔排序7.3交换排序：冒泡排序，快速排序7.4选择排序：直接选择排序，堆排序7.5 归并排序：二路归并排序7.6 各种（内）排序算法的比较未列出知识：广义表、B树、串（定义-已看及KMP算法）、基数排序、外部排序新增：握手定理（已在书上补充）、表插入排序。

2020北京交通大学软件工程考研初试科目、参考书目、复试线本文将由新祥旭刘老师全方位的对北京交通大学计算机与软件工程专业考研进行解析，主要有以下几个板块：学院介绍，专业情况介绍，2019录取情况分析，考研科目介绍，专业课参考书目及备考指导等几大方面。

一、学院介绍北京交通大学计算机与信息技术学院成立于2000年3月，属于北京交通大学的二级学院，其前身是成立于1977年的电子工程系（后更名为计算机系）和创立于1978年的信息科学研究所等单位，是计算机与信息科学领域培养高级专门人才的摇篮和科研基地。

学院下设有计算机科学系、计算机工程系、生物医学工程系、信息安全系、信息科学研究所、网络管理研究中心、先进计算研究所、计算机基础教学基地、计算机综合实验室等9个单位。

以计算机与信息技术学院为依托，2003年成立了北京交通大学软件学院，是教育部批准的国家示范性软件学院之一。

二、计算机专业考试科目1.计算机与信息技术学院计算机学硕：①101思想政治理论②201英语一③301数学一④923 操作系统原理或925 数据结构注：计算机专硕考试科目与学硕一致；网安公共课与学硕一致，专业课考923。

软件工程学硕：①101思想政治理论②201英语一③301数学一④926 软件工程理论或925 数据结构注：计算机学院的软工专硕为40人非全，所以不多加叙述。

2.软件学院：软件工程学硕：①101思想政治理论②201英语一③301数学一④901 软件工程2.综合面试综合面试由英语听力口语测试和综合能力面试两部分组成。

计算机科学与技术（全日制081200）、软件工程（全日制083500）、计算机技术（全日制085211）、软件工程（一志愿非全日制085212）四个专业综合能力面试采取分环节流程，整个综合面试过程包含以下三个环节（合计120分）：第一环节：考核程序设计基础知识（高级语言程序设计、面向对象程序设计、数据结构、算法等），满分40分；第二环节：考核计算机专业知识（操作系统、编译原理、数据库、软件工程、计算机网络、计算机组成原理、计算机体系结构等核心专业知识），满分40分；第三环节：综合考核（创新创业、竞赛、科研、社会实践、逻辑思维、组织协调能力、表达能力、思想政治素质和道德品质等），满分40分。

02103：程序设计基础
1、过程化程序设计基础（1）C 语言基础、基本数据类型、基本 I/O、运算符表达式与流程控制、函数与递归、参数传递；（2）数组和指针、字符串处理、变量及其存储、内存管理、结构、位运算、文件 I/O；（ 3）C 预处理器及运行库、多模块程序设计、数据抽象、流程图、程序设计规范。

2、面向对象程序设计基础（1）OOP 基本思想与方法：类、对象、属性、方法、重载/覆盖、封装、继承/派生、多态、模板(集合与泛型)、异常处理等基础知识。

（2）OOP 程序设计语言（C#、Java 等）、简单设计模式、包、类图、程序设计规范。

3、基础算法与数据结构（1）算法复杂度分析、基础输入输出、简单实现、暴力、枚举、贪心、排序、搜索(BFS/DFS)、
二分；（2）简单数学推理、串处理、栈、队列、简单树/图算法。

本文来源于公众号：北交考研联盟。

北京交通大学计算机与信息技术学院数据结构历年最新资料，W O考研真格式汇可编辑修改！目录2015年北京交通大学计算机与信息技术学院925数据结构考研真题.............. 2013年北京交通大学计算机与信息技术学院925数据结构考研真题（回忆版）2007年北京交通大学计算机与信息技术学院925数据结构考研真题.............. 2006年北京交通大学计算机与信息技术学院925数据结构考研真题.............. 2005年北京交通大学计算机与信息技术学院925数据结构考研真题.............. 2002年北京交通大学计算机与信息技术学院925数据结构考研真题.............. 2001年北京交通大学计算机与信息技术学院925数据结构考研真题.............. 2000年北京交通大学计算机与信息技术学院925数据结构考研真题.............. 1999年北京交通大学计算机与信息技术学院925数据结构考研真题.............. 1998年北京交通大学计算机与信息技术学院925数据结构考研真题.............. 1997年北京交通大学计算机与信息技术学院925数据结构考研真题.............. 1996年北京交通大学计算机与信息技术学院925数据结构考研真题.............. 1995年北京交通大学计算机与信息技术学院925数据结构考研真题.............. 1994年北京交通大学计算机与信息技术学院925数据结构考研真题.............. 1993年北京交通大学计算机与信息技术学院925数据结构考研真题..............2013年北京交通大学计算机与信息技术学院925数据结构考研真题（回忆版）一、填空题（15x2）1•一个数据结构的抽象数据类型（ADT）包括哪三部分2. n个顺序存储删除第i个元素需要移动多少个元素3•有向完全图又多少条弧4•用邻接表表示的无向图有n个顶点e条边在邻接表中有多少个边结点5•强连通图至少包含几条弧6. （（a,（b,d）,c）,（e,（f,g）,k））广义表的深度和长度是多少（具体的变量记不清了）7•有31个结点的有序序列在等概率的条件下查找成功的平均查找长度8•有2013个结点的哈夫曼树有多少个叶子结点二、选择题（15x2 ）1. abcde入栈得不到下列哪个序列2.双向循环链表在p节点后插入s结点的操作3.给了一个哈希表问用链式存储哈希函数H （key ）mod11问1的顶点结点有多少个链接结点4.深度为6的完全二叉树最多最少有多少结点5.后序线索二叉树若一个结点即有左子树也有右子树则他的后继结点是三、判断题（15x1 ）1.栈的数据元素是先进后出队列的数据元素是先进先出2.无向图的邻接矩阵一定是是对称矩阵有向图的一定不是对称矩阵四、简答题1.将森林转化为二叉树2.一个n个结点的完全二叉树有多少叶子结点（结果用n表示）3.建立小顶堆画出建立初始堆的过程4.画平衡二叉树5.哈希表平方探测解决冲突计算等概率查找成功平均查找长度6.图的深度优先遍历序列prim生成最小代价树并求最小代价7. AOE网的关键路径五、算法题（4x10 ）1.程序填空中序线索二叉树2.程序填空折半查找3•读程序写结果有个大程序包括三个子程序个人理解分别是先序生成二叉树中序遍历并判断是否为二叉排序树4 •算法设计求无向连通图的简单路径1999年北京交通大学计算机与信息技术学院925数据结构考研真题。

以下2024年考研数据结构大纲供参考：
一、绪论
1. 数据结构的基本概念
2. 算法与数据结构的关系
3. 算法分析基础
二、线性表
1. 线性表的定义和基本操作
2. 线性单链表、双向链表与循环链表
3. 一维数组和广义表
三、栈和队列
1. 栈和队列的基本概念
2. 栈和队列的顺序存储及其基本操作
3. 栈和队列的链式存储及其基本操作
4. 栈和队列的应用
四、树与二叉树
1. 树的基本概念
2. 二叉树的定义及其性质
3. 二叉树的存储结构及其基本操作
4. 二叉树的遍历
5. 线索二叉树
6. 哈夫曼树及其应用
7. 平衡二叉树
8. B-树和B+树
9. 并查集
五、图
1. 图的基本概念
2. 图的存储结构及其基本操作
3. 图的遍历
4. 最小生成树(MST)
5. 最短路径问题
6. 拓扑排序
7. 关键路径
8. AOV网与拓扑排序
9. AOE网与关键路径
10. 有向无环图(DAG)及相关算法
11. 二分图匹配问题
12. 网络流问题
13. 动态规划在图论中的应用
14. 图的着色问题。

理工大学2020年硕士学位研究生招生考试业务课考试大纲考试科目：数据结构代码：991考试的总体要求考查学生对数据的逻辑结构和物理结构的基本概念的掌握，对基本的数据结构和算法的掌握；考查学生利用基本数据结构和算法，使用C语言来解决实际科学和理论问题的思想和能力。

基本内容一、线性表1．线性表的概念及特点2．线性表的逻辑结构3．线性表的顺序及链式存储结构4．相关的各种基本运算二、栈和队列1．栈的概念、特点及存储结构2．栈的基本运算3．栈的应用4．队列的概念、特点及存储结构5．链队列、循环队列6．队列的应用及基本运算三、数组和广义表1．数组的顺序存储结构（二维及三维数组的元素地址计算）2．稀疏矩阵的压缩存储结构（三元组表、十字链表）四、树和二叉树1．二叉树的定义、性质及存储结构2．遍历二叉树和线索二叉树3．二叉树的应用五、图1．图的定义及存储结构（邻接矩阵表示和邻接表表示。

）2．图的遍历3．最小生成树4．拓扑排序六、查找1．静态表查找2．动态表查找（二叉排序树、平衡二叉树、B-树和B+树）3．哈希表的构造、哈希表的查找及分析、处理哈希冲突的方法七、内部排序1．插入排序、快速排序、选择排序、归并排序、基数排序等内部排序的特点与算法，各类排序方法的比较，时、空复杂度分析2．相关排序的应用考试题型：选择题（15％）、填空题（20％）、判断题（10％）、应用题（35％）、算法设计题（20％）；其中算法设计题将着重考查学生使用C语言编程解决实际问题的能力，需要有一定的实际编程基础，而不是只会解书上的习题。

《数据结构》试卷B一、填空题（每空1分，共15分）1. 向量、栈和队列都是结构，可以在向量的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入和删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为。

不允许插入和删除运算的一端称为。

3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。

4. 在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。

5. 在具有n个单元的循环队列中，队满时共有个元素。

6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为；比较四次查找成功的结点数为；平均查找长度为。

二、判断正误（判断下列概念的正确性，并作出简要的说明。

）（每小题1分，共10分）（）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（）2. 在表结构中最常用的是线性表，栈和队列不太常用。

（）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

（）5.线性表的逻辑顺序与存储顺序总是一致的（）6. 栈和队列是一种非线性数据结构。

（）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。

（）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

（）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

（）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。

三、单项选择题（每小题1分，共20分）（ ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A ）存储结构 （B ）逻辑结构 （C ）顺序存储结构 （D ）链式存储结构（ ）2. 若已知一个栈的入栈序列是1，2，3，…，n ，其输出序列为p1，p2，p3，…，pn ，若p1=n ，则pi 为Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定（ ）3. 判定一个栈ST （最多元素为m0）为空的条件是Ａ．ST->top<>0 Ｂ．ST->top=0 Ｃ．ST->top<>m0 Ｄ．ST->top=m0（ ）4设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素a i,j (i ≤j), 在一维数组B 中下标k 的值是：Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j（ ）5．具有n(n>0)个结点的完全二叉树的深度为 。

课程教学大纲课程代号:07021021学时数:56+S16适用专业：计算机科学与技术专业一、本课程的性质、目的和任务1。

本课程的性质数据结构是高等院校计算机各专业的核心课程之一,也是重要的专业基础课,主要介绍和研究各种基本的数据结构及其应用.2。

本课程的目的通过本课程的学习，使学生获得有关数据的各种逻辑结构、在存储器上的存储结构以及相关运算的算法：并能够根据实际问题的需要选择和设计出相应运算的算法。

为《操作系统》、《数据库概论》等后续课程的学习及为应用软件特别是非数值应用软件的开发打下良好的基础和时间基础。

3.本课程的任务本课程的主要任务是培养学生:(1)熟练掌握各种数据结构的特点、存储表示，操作算法及在计算机科学中基本应用。

（2)初步掌握算法的时间分析和空间分析的技巧。

(3)培养、训练学生选用合格的数据结构和使用类C语言编写质量高、风格好的应用程序及初步评价算法程序的能力.二、教学基本内容和要求1。

绪论（1）教学目的与要求熟悉数据结构的一些基本概念；了解抽象数据类型的定义、表示和实现方法；掌握C++语言的语句及算法描述的书写规则;掌握计算语句频度和估算算法时间复杂度的方法。

(2）主要内容数据、数据元素、数据对象、数据类型、数据结构等概念；抽象数据类型的定义、表示和实现方法；描述算法的C++语言；算法设计的基本要求以及从时间和空间角度分析算法的方法。

(3)重点、难点重点：算法的时间和空间复杂性的评价；难点:算法效率的度量。

2.线性表(1）教学目的与要求掌握线性表的定义和顺序存储结构；掌握线性表的链式存储结构；掌握线性表的插入、删除、归并等基本运算；了解静态链表和一元多项式的有关知识。

(2）主要内容线性表的顺序存储结构、线性表的链式存储结构；在线性表的两类存储结构（顺序的和链式的)上实现基本操作;静态链表的存储结构和运算；一元多项式的抽象数据类型定义、表示及加法的实现。

(3)重点、难点重点：线性表的链式存储结构；难点：静态链表的存储结构和运算。