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

目录

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

本文来源：https://www.bwwdw.com/article/9u52.html