|
2017年江苏大学851数据结构考研大纲
1
目录
I 考查目标........................................................................................ 2
II 考试形式和试卷结构 ..................................................................2
III 考查内容..................................................................................... 2
IV. 题型示例及参考答案.................................................................3
2
全国硕士研究生入学统一考试
数据结构考试大纲
I 考查目标
全国硕士研究生入学统一考试模式识别与智能系统、计算机技术、软件工程、农业信息
化硕士专业学位《数据结构》考试是为江苏大学招收以上硕士生设置的具有选拔性质的考试
科目。其目的是科学、公平、有效地测试考生是否具备攻读模式识别与智能系统、计算机技
术、软件工程、农业信息化专业硕士所必须的基本素质、一般能力和培养潜能,以利用选拔
具有发展潜力的优秀人才入学,为国家的经济建设培养具有良好职业道德、法制观念和国际
视野、具有较强分析与解决实际问题能力的专业人才。考试要求考生比较系统地掌握数据结
构课程的概念、基本原理和方法,能够运用所学的基本原理和基本方法分析、判断和解决有
关理论问题和实际问题。
具体来说,要求考生：
1. 理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异,以及各种基
本操作的实现。
2. 掌握基本的数据处理原理和方法的基础上,能够对算法进行设计与分析。
3. 能够选择合适的数据结构和方法进行问题求解。
II 考试形式和试卷结构
一、试卷满分及考试时间
试卷满分为 150 分,考试时间 180 分钟。
二、答题方式
答题方式为闭卷、笔试。
三、试卷内容与题型结构
单项选择题 10 题,每小题 1 分, 共 10 分
填空题 题数不定,每空 1 分, 共 10 分
应用题 题数不定, 共 80 分
简答题 题数不定, 共 30 分
算法设计题 题数不定, 共 20 分
III 考查内容
1 绪论
1.1 数据结构的基本概念和术语
1.2 算法的定义、性能标准和复杂度
2 线性表
2.1 线性表的定义
2.2 线性表的顺序表示和实现
2.3 线性表的链表表示和实现
2.4 线性表的应用
3 栈和队列
3.1 栈和队列的基本概念
3
3.2 栈和队列的顺序存储结构
3.3 栈和队列的链式存储结构
3.4 栈和队列的应用
4 串、数组和广义表
4.1 字符串的定义、存储结构和操作,模式匹配算法
4.2 数组的定义和顺序存储结构,特殊矩阵和稀疏矩阵的压缩存储
4.3 广义表的定义和存储结构
5. 树和森林
5. 1 树的定义和术语,树的表示形式和基本操作
5. 2 二叉树的定义、性质和基本操作
5. 3 二叉树的顺序存储结构和链式存储结构
5. 4 二叉树的遍历
5. 5 线索二叉树
5. 6 哈夫曼树和哈夫曼编码
5. 7 树的存储结构,树、森林和二叉树的转换,树和森林的遍历
5. 8 等价类及其表示
6 图
6. 1 图的定义、术语和基本操作
6. 2 图的存储结构(邻接矩阵、邻接表)
6. 3 图的深度优先遍历、广度优先遍历和连通分量
6. 4 最小生成树、最短路径、拓扑排序和关键路径
7 查找
7. 1 查找的基本概念
7. 2 顺序查找法、折半查找法和索引顺序表上的查找
7. 3 二叉排序树的定义,二叉排序树上的查找、插入和删除,二叉排序树查找的性能分析
7. 4 平衡二叉树的定义,平衡旋转,平衡二叉树的插入和删除
7. 5 散列表的基本概念、构造和分析
8 内部排序
8. 1 排序的基本概念
8. 2 交换排序(冒泡排序,快速排序)
8. 3 插入排序(直接插入排序,折半插入排序,希尔排序)
8. 4 选择排序(直接选择排序,锦标赛排序,堆排序)
8. 5 两路归并排序
8. 6 基数排序
8. 7 各种内部排序算法的比较和应用
IV. 题型示例及参考答案
4
一、单项选择题(每小题 1 分,共 10 分)
1. 设有数组 A[i,j],数组的每个元素长度为 3 字节,i 的值为 1 到 8,j 的值为 1 到 10,数组从内
存首地址 SA 开始顺序存放,当以列为主存放时,元素 A[5,8]的存储首地址为( )。
(A) SA+180 (B) SA+141 (C) SA+222 (D) SA+225
2. 在双向链表指针 p 的结点前插入一个指针 q 的结点操作是( )。
(A) p->Llink=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；
(B) q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;
(C) p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;
(D) q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;
3. 一棵二叉树高度为 h,所有结点的度或为 0,或为 2,则这棵二叉树最少有( )结点。
(A) 2h (B) 2h+1 (C) 2h-1 (D) h+1
4. 当在一个有序的顺序存储表上查找一个数据时,既可用折半查找,也可用顺序查找,但前
者比后者的查找速度( )。
(A) 取决于表递增还是递减 (B) 必定快 (C) 不一定 (D) 在大部分情况下要快
5. 串的长度是指( )。
(A)串中所含不同字母的个数 (B)串中所含非空格字符的个数
(C)串中所含不同字符的个数 (D)串中所含字符的个数
6. 下面说法错误的是( )。
(A) 算法原地工作的含义是指不需要任何额外的辅助空间
(B) 在相同的规模 n 下,复杂度 O(n)的算法在时间上总是优于复杂度 O(2
n
)的算法
(C) 所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界
(D) 同一个算法,实现语言的级别越高,执行效率就越低
7. 以下错误的是 ( )
(i) 静态链表既有顺序存储的优点,又有动态链表的优点。所以,它存取表中第 i 个元素
的时间与 i 无关。
(ii) 静态链表中能容纳的元素个数的最大数在表定义时就确定了,以后不能增加。
(iii) 静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。
(A) (i),(ii) (B) (i) (C) (i),(ii),(iii) (D) (ii)
8. 已知广义表 LS＝((a,b,c),(d,e,f)),运用 head 和 tail 函数取出 LS 中原子 e 的运算是
( )。
(A) head(tail(head(tail(LS))) (B) tail(head(LS))
(C) head(tail(LS)) (D) head(tail(tail(head(LS))))
9. 对于顺序存储的线性表,访问结点和增加结点的时间复杂度为( )。
(A)O(n) O(n) (B) O(n) O(1) (C) O(1) O(n) (D) O(1) O(1)
10. 若栈采用顺序存储方式存储,现两个栈共享空间 V[1..m],top[j]表示第 j 个栈(j=1,2)栈顶指
针,栈 1 的底设在 V[1],栈 2 的底设在 V[m],则栈满的条件是( )。
(A) top[2] – top[1] = = m (B) top[2] – top[1] = = 1
(C) top[2] – top[1] = = 0 (D) top[2] + top[1] = = m
二、填空题(每空 1 分,共 10 分)
1. 循环队列用下标范围是 0 到 m 的数组 V 存放其元素值,已知其头、尾指针分别是 f 和 r,f
是队首元素的前一个位置,r 是队尾元素位置,若用牺牲一个单元的办法来区分队满和队
空,则队满的条件为 。
2. 有一个 100×200 的元素值为整型的稀疏矩阵,非零元素有 20 个,设每个整型数占 2 字节,
则用三元组顺序表表示该矩阵时,所需的字节总数是 。
3. 如果按关键码值递增的顺序依次将99个关键码值插入到二叉排序树中,则对这样的二叉
5
排序树检索时,在等概率而且查找成功的情况下的平均查找长度 ASL 为 。
4. 下面程序段中带下划线的语句的执行次数的数量级是 。
i=1; while (i,< V4,V5,60>, <
V4,V3,20>,< V3,V5,15>,< V2,V6,10>, < V2,V3,50>, < V1,V2,5>}。要求：
（1） 画出该有向网。
（2） 画出该有向网的邻接矩阵。
（3） 求基于你的邻接矩阵的从顶点 V1 出发的 DFS 序列以及 DFS 生成树。
（4） 给出该有向网的所有拓扑有序序列。
（5） 用 dijkstra 算法,求从源点 V1 出发到其它各终点的最短路径以及长度,请给出执行算
法过程中各步的状态,可用下面给出的表格形式表示。
4. (12 分)有一结点的关键字序列 F={26,36,41,38,44,15,68,12,06,51,25},
散列函数为：H(K)= K % 11,其中 K 为关键字,散列地址空间为 0～10。要求：
（1） 画出相应的闭散列表。发生冲突时,以线性探测法解决。
（2） 该散列表的装填因子 α 是多少？
（3） 在等概率情况下查找成功时的平均查找长度 ASL 是多少？
（4） 用线性探测法解决冲突时,如何处理被删除的结点？为什么？
5.(8 分)已知长度为 10 的表{16,3,7,12,9,28,25,18,14,20},按表中元素顺序依次插入一棵初始时
为空的平衡二叉排序树中,画出每一步插入后平衡二叉排序树的形态。若做了某种旋转,说
明旋转的类型。
6.(20 分)已知关键字序列 F={22,12,26,40,18,38,14,20,30,16,28}。要求：
（1） 将该序列调整为“小顶”堆,并给出调整过程。请从时间和空间两方面对简单选择排
序、树形选择排序和堆排序作一比较。
6
（2） 若采用链式基数排序方法排序,请写出第一趟“分配”之后各队列的状态和第一趟“收
集”之后的关键字序列。并请简要说出基数排序方法和其他排序方法有什么区别？
（3） 要求最后排序结果是按关键字从小到大的次序排列,请给出冒泡排序的前 3 趟排序结
果。
四、简答题(共 30 分)
1. (6 分)线性表的顺序存储结构和链式存储结构各有哪些优缺点？
2. (8 分)画出对长度 n 为 10 的递增有序表{A[1]、A[2]、……、A[10]}进行折半查找的判定
树。当实现插入排序过程时,可以用折半查找来确定第 i 个元素在前 i-1 个元素中的可能插
入位置,这样做能否改善插入排序的时间复杂度？为什么？
3. (8 分)快速排序的平均时间复杂度是多少？快速排序在所有同数量级的排序方法中,其平
均性能好。但在什么情况下快速排序将蜕化为起泡排序,此时的时间复杂度又是多少？为
改进之,通常可以怎么做？
4. (8 分)请简要叙述求最小生成树的 Prim 算法的思想(或步骤)。并指出对具有 n 个顶点和 e
条边的连通网而言,Prim 算法和Kruskal算法各自适合于什么情况下的连通网？其时间复杂
度又各为多少？
五、算法设计题(共 20 分)
1.(10 分) 给定( 已生成) 一个带表头结点的单链表, 设 head 为头指针, 结点的结构为
(data,next),data 为整型元素,next 为指针,试写出算法：按递减次序输出单链表中各结点的数
据元素,并释放结点所占的存储空间。(要求：不允许使用数组作辅助空间)
2.(10 分)以二叉链表作为二叉树的存储结构,试编写递归算法,求二叉树中以元素值为 item 的
结点为根的子树的深度(假设树中一定存在值为 item 的结点)。
注意：
(1)可用(类)Pascal 语言或(类)C 语言或 C++语言描述你的算法；
(2)请简要描述你的算法思想；
(3)若你的算法是(类)Pascal 或(类)C 语言编写,则请给出相应的存储结构描述；
(4)若你的算法是用 C++语言描述,则可参考使用以下给出的相关存储结构的类定义,算
法中可以使用类中已列出的成员函数。若在你的算法中使用了未列出的成员函数,则要写出
该成员函数的完整算法描述
//单链表的类定义
template class linklist; //单链表前视声明
template class node{//单链表结点类
friend class linklist ; //定义单链表类 linklist 为结点类的友元
private:
node *next; //链指针域
public:
type data; //数据域
node (node *pnext = NULL) {next = pnext;}//构造函数,用于构造头结点
};
template class linklist{ //单链表类定义
private:
node *head; //指向头结点的头指针
public:
linklist ( ){ head = new node ( ); head->next=NULL; }//构造函数
~linklist ( ); //析构函数
7
};
//二叉链表的类定义：
template class BinaryTree; //二叉链表类前视声明,以便使用友元
template class BinTreeNode { //结点类
friend class BinaryTree;
private:
BinTreeNode *leftChild, *rightChild; //结点的左、右孩子指针域
Type data; //结点的数据域
public:
BinTreeNode ( ) : leftChild (NULL), rightChild (NULL) { } //构造函数,构造一个空结点
BinTreeNode (Type d, BinTreeNode *lp = NULL, BinTreeNode *rp =NULL ) :
data (d), leftChild (lp), rightChild (rp) { }
//构造函数,构造一个数据域的值为 d 的结点
};
template class BinaryTree { //二叉链表类
private:
BinTreeNode *root; //二叉树根结点指针
public:
BinaryTree ( ) : root (NULL) { } //构造函数
~BinaryTree ( ) { destroy ( root ); } //析构函数
};
参考答案
一、单项选择题
1. A；2. B；3. C；4. D；5. D；6. C；7. B；8. A；9. C；10. B；
二、填空题
1. (r-f+m+1)%(m+1)
2. 20*3*2+6=126
3. (99+1)/2=50
4. O(nlog2n)
5. (9+1)/2+(6+1)/2=17/2=8.5
6. log3(244+1)的上取整或 log3244 下取整+1
7. 长度相等,对应位置的字符相同
8. n
9. abc+*d-
10. 500 (n2=499,n0=n2+1=499+1=500)
三、应用题
1.
(1)二叉树
8
D FE
CB
A
JH KG
L
I
(2)森林
D
F
E
C
B
A
J
H
K
G L
I
(3)中序全线索二叉树
D FE
CB
A
JH KG
L
I
NULL
NULL
(4)双亲孩子链表
A -1
B 1
E 1 ^
I 1 ^
D 2
H 2 ^
G 5 ^
L 5 ^
1
2
3
4
5
6
7
8
2 ^43
^65
^87
2.
(1)
9
(2)
(3)
WPL=(3+6)*4+(8+10+15)*3+(19+21)*2=36+99+80=215
3.
(1)
V1
510
V3
V6
V2
V5
V4
20
30
100
60
15
50
(2)
10
1 2 3 4 5 6
1 0 5 ∞ ∞ ∞ ∞
2 ∞ 0 50 ∞ ∞ 10
3 ∞ ∞ 0 ∞ 15 ∞
4 ∞ ∞ 20 0 60 ∞
5 ∞ ∞ ∞ ∞ 0 ∞
6 ∞ ∞ ∞ 30 100 0
(3)
DFS 序列：V1,V2,V3,V5,V6,V4
DFS 生成树：
V1 5
10
V3
V6
V2
V5
V430
15
50
(4)拓扑序列：V1,V2,V6,V4,V3,V5
(5)
V1 (1) (2) (3) (4) (5)
V2 (V1,V2)
5
X X X X
V3 ∞ (V1,V2,V3)
55
(V1,V2,V3)
55
(V1,V2,V3)
55
X
V4 ∞ ∞ (V1,V2,V6,V4)
45
X X
V5 ∞ ∞ (V1,V2,V6,V5)
115
(V1,V2,V6,V4,V5)
105
(V1,V2,V3,V5)
70
V6 ∞ (V1,V2,V6)
15
X X X
u
(u,v)
长度
V2
(V1,V2)
5
V6
(V1,V2,V6)
15
V4
(V1,V2,V6,V4)
45
V3
(V1,V2,V3)
55
V5
(V1,V2,V3,V5)
70
4.
(1)
关键字 26 36 41 38 44 15 68 12 06 51 25
HASH 函数值 4 3 8 5 0 4 2 1 6 7 3
比较次数 1 1 1 1 1 3 1 1 2 3 8
H(k)=k%11, 数组范围：0~10
下标 0 1 2 3 4 5 6 7 8 9 10
关键字 44 12 68 36 26 38 15 06 41 51 25
冲突关键字 25 15 06 51
11
(2)
α=n/m=11/11=1
(3)
1 1 23
() (1 7 2 1 3 2 8 1)
11 11
i
ASL c
n
(4)
不能真正地“物理”删除,只能做“删除标记”,否则将截断在它之后填入散列表的同义词结
点的查找路径。
5.
{16,3,7,12,9,28,25,18,14,20}
12
7 18
93 2516
14 20 28
12
7 25
93 2816
14 18
20
12
7 25
93 2816
12
7 16
93 28
7
3 12
9 16
7
3 16
12
9
7
3 16
16
3
7
LR LL
RL LR
平衡
平衡
平衡
平衡
7
3 12
9 16
28
12
7 16
93 28
25
RR
平衡
6. (1)
(2)
12
链式基数排序和其他排序方法的最大区别是各关键字之间没有发生比较。
(3)
初始 22 12 26 40 18 38 14 20 30 16 28
(1) 12 22 26 18 38 14 20 30 16 28 40
(2) 12 22 18 26 14 20 30 16 28 38
(3) 12 18 22 14 20 26 16 28 30
四、简答题
1.
顺序存储结构 链式存储结构
优
点
存取第 i 个元素方便(随机存取),O(1) (1) 插入、删除不需移动元素,只修改指针,修
改指针的时间复杂度为 O(1)；
(2) 不需要预先分配空间,可根据需要动态申
请空间；
(3) 表容量只受可用内存空间的限制。
缺
点
(1) 在作插入或删除操作时,需移动大量
元素；
(2) 由于难以估计,必须预先分配较大的
空间,往往使存储空间不能得到充分
利用；
(3) 表的容量难以扩充。
(1) 存取第 i 个元素不方便,是 O(n)
2.
（1） 长度 n 为 10 的递增有序表折半查找的判定树
如左所示。
（2） 不能改善插入排序的时间复杂度
（3） 原因：插入排序中,用折半查找确定待插入元
素位置,比直接插入排序减少了比较次数,但数
据移动次数没有改变,排序的时间复杂度也未
改变。
3.
1 93
82
5
6
7 104
13
快速排序的平均时间复杂度为 O(nlogn)。
在关键字有序或基本有序的情况下,快速排序将蜕化为起泡排序。
此时的时间复杂度是 O(n
2
)。
为改进之,通常可以采用“三者取中法”,取三者中其关键字为中间值的记录为枢轴,只要将该
记录和待排序表的第一个关键字互换即可,算法不变。
4.算法思想：设 N=(V,{E})是连通网,TE 是 N 上最小生成树中边的集合
(1)初始令 U={u0},(u0V), TE=
(2)在所有 uU,vV-U 的边(u,v)E 中,找一条代价最小的边(u0,v0)
(3)将(u0,v0)并入集合 TE,同时 v0 并入 U.即 TE=TE+{(u0,v0)},U=U+{v0}
(4)重复上述(2),(3)操作直至 U=V 为止,则 T=(V,{TE})为 N 的最小生成树
对具有 n 个顶点和 e 条边的连通网而言:
Prim 算法适合于边稠密的连通网,其时间复杂度为 O(n
2
),与顶点数有关
Kruskal 算法适合于边稀疏的连通网,其时间复杂度为 O(elog2e),与边的条数有关
五、算法设计题
1.
算法思想：对链表进行遍历,在每趟遍历中查找出整个链表的最大值元素,输出并释放结点所
占空间；再查次最大值元素,输出并释放空间,如此下去,直至链表为空,最后释放头结点所占存
储空间。
void MiniDelete(linklist head)
∥head是带头结点的单链表的头指针,本算法按递增顺序输出单链表中各结点的数据元素,并
释放结点所占的存储空间。
{
while(head->next!=null) ∥循环到仅剩头结点。
{pre=head； ∥pre 为元素最大值结点的前驱结点的指针。
p=pre->next； ∥p 为工作指针
while(p->next!=null)
{if(p->next->data>=pre->next->data)pre=p；∥记住当前最大值结点的前驱
p=p->next；
}// while(p->next!=null)
cout data；∥输出元素最大值结点的数据。
q=pre->next；pre->next=q->next; delete q；∥删除元素值最大的结点 q,释放结点空
间
}∥ while(head->next!=null)
delete head；∥释放头结点。
}// MiniDelete
2.(10 分)
算法思想：在树中先找值为 item 的结点 p,然后再求以 p 为根的子树的深度。
int GetSubDepth(BinaryTree p,Type item){
if (p->data = = item) {//找到值为 item 的结点 p
return GetDepth(p);//求以 p 为根的子树的深度
}
else {//在左、右子树中继续寻找值为 item 的结点
if (p->leftChild != NULL) GetSubDepth(p->leftChild, item );
14
if (p->rightChild != NULL) GetSubDepth(p->rightChild, item );
}
}// GetSubDepth
int GetDepth(BinaryTree p){//求子树 p 的深度
int m,n;
if ( p= = NULL) return 0;//空树的深度是 0
else {//不是空树
m=GetDepth(p->leftChild); //求 p 的左子树的深度
n=GetDepth(p->rightChild); //求 p 的右子树的深度
return (m>n?m:n)+1;//树 p 的深度是其左、右子树深度大者加 1
}
}//GetDepth
上一篇文章： 2017年江苏大学852通信系统原理考研大纲
下一篇文章： 2017年江苏大学850计算机组成原理考研大纲 |
文章搜索
