硕士研究生入学考试大纲-851数据结构

I 考查目标 ......................................................................................... 2 II 考试形式和试卷结构 ................................................................... 2 III 考查内容 ..................................................................................... 2 IV. 题型示例及参 ................................................................. 3

1

全国硕士研究生入学统一考试

数据结构考试大纲

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 栈和队列的基本概念

2

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. 题型示例及参

3

一、单项选择题(每小题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(2n)的算法 (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个关键码值插入到二叉排序树中,则对这样的二叉

4

4. 5. 6.

7. 8. 9. 10.

三、应用题(共80分) 1. (12分)假设一棵二叉树的中序序列为GLDHBEIACJFK,后序序列为LGHDIEBJKFCA。要求：

（1） 画出该二叉树。

（2） 画出该二叉树所对应的森林。

（3） 画出该二叉树的中序全线索二叉树。

（4） 画出该二叉树所对应的森林中第一棵树的带双亲域的孩子链表。 2. (8分)给定一组数据(15,8,10,21,6,19,3)分别代表字符A,B,C,D,E,F,G出现的频度,要求： （1） 画出构造哈夫曼树的过程以及最后的哈夫曼树。

（2） 在哈夫曼树上对各字符进行编码,并给出各字符的编码值。 （3） 计算哈夫曼树的带权路径长度WPL。 3. (20分)设G=(V,E)为有向网,其中V(G)={V1,V2,V3,V4,V5,V6}。现用三元组表示弧以及弧上的权值z,则E(G)为E(G)={ < V6,V5,100>,< V6,V4,30>,< 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） 将该序列调整为“小顶”堆,并给出调整过程。请从时间和空间两方面对简单选择排

序、树形选择排序和堆排序作一比较。

排序树检索时,在等概率而且查找成功的情况下的平均查找长度ASL为 。 下面程序段中带下划线的语句的执行次数的数量级是 。

i=1; while (i将有关二叉树的概念推广到三叉树,则一棵有244个结点的完全三叉树的高度 。

两个字符串相等的充分必要条件是 。 构造n个结点的强连通图,至少有 条弧。 表达式a*(b+c)-d的后缀表达式是 。

一棵完全二叉树上有1000个结点,其中叶子结点的个数是 。

5

（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 ( ); //析构函数

6

};

//二叉链表的类定义：

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)二叉树

7

ABCDEFGHIJKL

(2)森林

ACFKBEIJDHGL

(3)中序全线索二叉树

ABCNULLDEFNULLGHIJKL(4)双亲孩子链表

1A-1234^2B156^3E1^4I1^5D278^6H2^7G5^8L5^

2. (1)

8

(2)

(3)

WPL=(3+6)*4+(8+10+15)*3+(19+21)*2=36+99+80=215 3. (1)

V6100V5030106V2V45155200V1V3 (2)

9

1 2 3 4 5 6

1 0 ∞ ∞ ∞ ∞ ∞ 2 5 0 ∞ ∞ ∞ ∞ 3 ∞ 50 0 20 ∞ ∞ 4 ∞ ∞ ∞ 0 ∞ 30 5 ∞ ∞ 15 60 0 100 6 ∞ 10 ∞ ∞ ∞ 0 (3)

DFS序列：V1,V2,V3,V5,V6,V4 DFS生成树：

V15V210V6V330V4V5 5015(4)拓扑序列：V1,V2,V6,V4,V3,V5 (5) V1 V2 V3 V4 V5 V6 u (u,v) 长度 4. (1) 关键字 HASH函数值 (1) (V1,V2) 5 ∞ ∞ ∞ ∞ V2 (V1,V2) 5 (2) X (V1,V2,V3) 55 ∞ ∞ (V1,V2,V6) 15 V6 (V1,V2,V6) 15 (3) X (V1,V2,V3) 55 (4) X (V1,V2,V3) 55 (5) X X X (V1,V2,V6,V4) X 45 (V1,V2,V6,V5) (V1,V2,V6,V4,V5) (V1,V2,V3,V5) 115 105 70 X X X V5 (V1,V2,V3,V5) 70 V4 V3 (V1,V2,V6,V4) (V1,V2,V3) 45 55 26 4 36 3 41 8 38 5 44 0 1 4 26 15 15 4 3 5 38 68 2 1 6 15 06 12 1 1 7 06 51 06 6 2 8 41 51 7 3 9 51 25 3 8 10 25 10

比较次数 1 1 1 1 H(k)=k%11, 数组范围：0~10 下标 关键字 0 44 1 12 2 68 3 36 25 冲突关键字

(2)

α=n/m=11/11=1 (3)

ASL()1123 c(17213281)in1111(4)

不能真正地“物理”删除,只能做“删除标记”,否则将截断在它之后填入散列表的同义词结点的查找路径。 5.

{16,3,7,12,9,28,25,18,14,20}

1637LR77LL77RR12316316312312716平衡9129169163928平衡12121228平衡12716RL716257281625LR716183928393928392525平衡141820142028平衡6. (1)

(2)

11

链式基数排序和其他排序方法的最大区别是各关键字之间没有发生比较。 (3) 初始 22 (1) (2) (3) 12 12 12 12 22 22 18 26 26 18 22 40 18 26 14 18 38 14 20 38 14 20 26 14 20 30 16 20 30 16 28 30 16 28 30 16 28 38 28 40

四、简答题 1. 优点 顺序存储结构 存取第i个元素方便(随机存取),O(1) 链式存储结构 (1) 插入、删除不需移动元素,只修改指针,修改指针的时间复杂度为O(1)； (2) 不需要预先分配空间,可根据需要动态申请空间； (3) 表容量只受可用内存空间的。 (1) 存取第i个元素不方便,是O(n) 缺点 (1) 在作插入或删除操作时,需移动大量元素； (2) 由于难以估计,必须预先分配较大的空间,往往使存储空间不能得到充分利用； (3) 表的容量难以扩充。 2.

（1） 长度n为10的递增有序表折半查找的判定树

如左所示。

（2） 不能改善插入排序的时间复杂度

（3） 原因：插入排序中,用折半查找确定待插入元

素位置,比直接插入排序减少了比较次数,但数据移动次数没有改变,排序的时间复杂度也未改变。

3.

52134671012

快速排序的平均时间复杂度为O(nlogn)。

在关键字有序或基本有序的情况下,快速排序将蜕化为起泡排序。 此时的时间复杂度是O(n2)。

为改进之,通常可以采用“三者取中法”,取三者中其关键字为中间值的记录为枢轴,只要将该记录和待排序表的第一个关键字互换即可,算法不变。

4.算法思想：设N=(V,{E})是连通网,TE是N上最小生成树中边的集合 (1)初始令U={u0},(u0V), TE=

(2)在所有uU,vV-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(n2),与顶点数有关

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 <next->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 );

13

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

14