计算机考研数据结构

数据结构部分（共75分）

一. 单项选择题（2×10分，共20分）

1. 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用 d 存储方式最节省运算时间。

A. 单链表 B.循环单链表 C. 双链表 D.仅有尾结点指针的循环单链表 2. 栈和队列的共同点是 c 。 A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点

3．对于含有n个互不相同字符的串，则真子串（不包括串自身）的个数是 c 。 A. n B.n2 C.n(n+1)/2 D.n(n-1)/2

4. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为 2*2+1*1=5。

A. 4 B. 5 C. 6 D. 7

5. 某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 d 。 A. 空或只有一个结点 B. 完全二叉树 C. 二叉排序树 D. 高度等于其结点数

6. 对图1所示的无向图，从顶点1开始进行深度优先遍历；可能得到顶点访问序列是

数据结构部分（共75分）

一. 单项选择题（2×10分，共20分）

1. 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用 d 存储方式最节省运算时间。

A. 单链表 B.循环单链表 C. 双链表 D.仅有尾结点指针的循环单链表 2. 栈和队列的共同点是 c 。 A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点

3．对于含有n个互不相同字符的串，则真子串（不包括串自身）的个数是 c 。 A. n B.n2 C.n(n+1)/2 D.n(n-1)/2

4. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为 2*2+1*1=5。

A. 4 B. 5 C. 6 D. 7

5. 某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 d 。 A. 空或只有一个结点 B. 完全二叉树 C. 二叉排序树 D. 高度等于其结点数

6. 对图1所示的无向图，从顶点1开始进行深度优先遍历；可能得到顶点访问序列是

2015福州大学计算机考研数据结构资料

2015福州大学计算机考研数据结构资料

计算机是福州大学一大热门学科，报考的考生都没减少过，今年也不例外，针对2015考研先分享一些思远福大考研网的数据结构的复习指导内容，也只是个大概，详细的可参考官网计算机专业考研资料。

数据：指能够被计算机识别、存储和加工处理的信息载体。

数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。

数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。

在高级语言程序中又分为：非结构的原子类型和结构类型

抽象数据类型(ADT)：是指一个数学模型以及定义在该模型上的一组操作。

一个抽象的数据类型的软件模块通常包含 定义和表示和实现

用三元组(D，S，P)：数据对象、数据关系、基本操作

数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容: 数据的逻辑结构、存储结构和数据的运算。

逻辑结构：指各数据元素之间的逻辑关系。

存储结构：就是数据的逻辑结构用计算机语言的实现。

线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个

共25套适用于计算机考研数据结构系统练习

（PS：其他正在整理，敬请期待）

数据结构试卷12

一、填空题

1.已知数组A［１０］［１０］为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［５，６］对应的地址是_______。

2.在有n个结点的无向图中，其边数最多为_______。

3.取出广义表A=(x,(a,b,c,d))中原子x的函数是_______。

4.对矩阵采用压缩存储是为了___ ____。 5.带头结点的双循环链表L为空表的条件是_______。

6.设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是 。

7. 对于顺序存储的栈，因为栈的空间是有限的，在进行 运算时，可能发生栈的上溢，在进行 运算时，可能发生栈的下溢。

8.在双向链表中，每个结点有两个指针域，一个指向____ __，另一个指向_ __ __。

9.由一棵二叉树的前序序列和 可唯一确定这棵二叉树。 10.折半查找的存储结构仅限于___

新东方2012计算机考研大纲解析之数据结构

2012年计算机统考大纲已经公布，我们第一时间来解析一下计算机统考大纲数据结构部分及其相关知识点：数据结构占了45分，和计算机组成原理部分同一个比重，这足以体现计算机专业研究生选拔对数据结构课程的要求之重。

一、大纲变化

2012年计算机统考的数据结构部分大纲都是变动在第六部分的排序方面，具体如下：

2011年大纲2012年大纲变动六、内部排序六、排序将内部排序范围扩展为排序(一) 排序的基本概念(一) 排序的基本概念无变化(二) 插入排序(二) 插入排序无变化1. 直接插入排序2. 直接插入排序无变化2. 折半插入排序3. 折半插入排序无变化(三) 起泡排序(bubble sort)(三) 起泡排序(bubble sort)无变化(四) 简单选择排序(四) 简单选择排序无变化(五) 希尔排序(shell sort)(五) 希尔排序(shell sort)无变化(六) 快速排序(六) 快速排序无变化

(七) 堆排序(七) 堆排序无变化(八) 二路归并排序(merge sort)(八) 二路归并排序(merge sort)无变化(九) 基数排序(九) 基数排序无变化(十)外部排序新增加(十) 各种内部排序算法的

共25套适用于计算机考研数据结构系统练习

（PS：其他正在整理，敬请期待）

数据结构试卷12

一、填空题

1.已知数组A［１０］［１０］为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［５，６］对应的地址是_______。

2.在有n个结点的无向图中，其边数最多为_______。

3.取出广义表A=(x,(a,b,c,d))中原子x的函数是_______。

4.对矩阵采用压缩存储是为了___ ____。 5.带头结点的双循环链表L为空表的条件是_______。

6.设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是 。

7. 对于顺序存储的栈，因为栈的空间是有限的，在进行 运算时，可能发生栈的上溢，在进行 运算时，可能发生栈的下溢。

8.在双向链表中，每个结点有两个指针域，一个指向____ __，另一个指向_ __ __。

9.由一棵二叉树的前序序列和 可唯一确定这棵二叉树。 10.折半查找的存储结构仅限于___

共25套适用于计算机考研数据结构系统联系

（PS：其他正在整理，敬请期待）

数据结构试卷4

一、选择题

1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。 (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)

2．设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。

kk-1k

(A) 2k-1 (B) 2 (C) 2 (D) 2-1 3．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（ ）。 (A) n (B) e (C) 2n (D) 2e 4．在二叉排序树中插入一个结点的时间复杂度为（ ）。

2

(A) O(1) (B) O(n) (C) O(log2n) (D) O(n)

5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。 (A) n (B) n-1 (C) m (D) m-1

6．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。 (A) 3 (B) 4 (C) 5 (D) 8 7．设用链表作为栈的存储结构则退栈操

第1章 绪论

一、选择题

1. 算法的计算量的大小称为计算的（ ）。【北京邮电大学2000 二、3 （20/8分）】

A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（ ）【中科院计算所 1998 二、1 （2分）】

A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2） 这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法

(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性

C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安

全性

【南京理工大学 1999 一、1（2分） 【武汉交通科技大学 1996 一、1（ 4分）】

4．一个算法应该是（ ）。【中山大学 1998 二、1（2分）】

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.

5. 下面关于算法说法错误的

一、选择题（共20分，每题1分）

1．从逻辑上可以把数据结构分为两大类,分别是（）。

A．动态结构、静态结构 B．顺序结构、链式结构

C．线性结构、非线性结构 D．初等结构、构造型结构

2.下面给出的四种排序法中( )排序法是不稳定的排序法。

A. 插入

B. 冒泡

C. 二路归并

D. 堆排序

3.线性表是具有n个（）的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项

4.在下面的程序段中，对x的赋值语句的频度为（）

FOR i:=1 TO n DO

FOR j:=1 TO n DO

x:=x+50;

A． O(2n) B．O(n) C．O(n2) D．O(log2n)

5.下述哪一条是顺序存储结构的优点？（）

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

6. 栈是一种（）的线性表。

A. 先进先出

B. 后进先出

C. 后进后出

D. 不分顺序

7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。

A. 4，3，1，2，

B. 2，1，3，4，

C. 1，4，3，2，

D. 1，2，4，3，

8.双向链表中有两

哈尔滨工业大学2000年数据结构考研试题

一． 名词解释：（12分） 1． 抽象数据类型； 2． 算法的时间复杂性； 3． 散列法(hashing)； 4． 索引文件。 二． 填空：(12分)

1． 在单链表中设置头结点的作用是_________________________________。 2． n个顶点的连通无向图，其边的条数至少为________________________。 3． 线索二元树的左线索指向其_______________，右线索指向其____________。 4． 树在计算机内的表示方式有___________，_____________，________________。

5． 排序（sorting）有哪几种方法_______________，_____________，____________，_____________，____________。

三．判断下列叙述是否正确，若你认为正确，请画“ “，否则画” “。 1． 存在这样的二元树，对它采用任何次序的遍历，结果相同。（ ） 2． 二元树就是结点度为2的树。（ ）

3． 若连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ） 4