1目录I 考查目标 .2II 考试形式和试卷结构 .2III 考查内容 .2IV. 题型示例及参考答案 .32全国硕士研究生入学统一考试数据结构考试大纲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 栈和队列的基本概念33.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. 设有数组 Ai,j,数组的每个元素长度为 3 字节,i 的值为 1 到 8,j 的值为 1 到 10,数组从内存首地址 SA 开始顺序存放,当以列为主存放时,元素 A5,8的存储首地址为( )。(A) SA+180 (B) SA+141 (C) SA+222 (D) SA+2252. 在双向链表指针 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+14. 当在一个有序的顺序存储表上查找一个数据时,既可用折半查找,也可用顺序查找,但前者比后者的查找速度( )。(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. 若栈采用顺序存储方式存储,现两个栈共享空间 V1.m,topj表示第 j 个栈(j=1,2)栈顶指针,栈 1 的底设在 V1,栈 2 的底设在 Vm,则栈满的条件是( )。(A) top2 top1 = = m (B) top2 top1 = = 1(C) top2 top1 = = 0 (D) top2 + top1 = = m二、填空题(每空 1 分,共 10 分 )1. 循环队列用下标范围是 0 到 m 的数组 V 存放其元素值,已知其头、尾指针分别是 f 和r,f 是队首元素的前一个位置,r 是队尾元素位置,若用牺牲一个单元的办法来区分队满和队空,则队满的条件为 。2. 有一个 100×200 的元素值为整型的稀疏矩阵,非零元素有 20 个,设每个整型数占 2 字节,则用三元组顺序表表示该矩阵时,所需的字节总数是 。53. 如果按关键码值递增的顺序依次将 99 个关键码值插入到二叉排序树中,则对这样的二叉排序树检索时,在等概率而且查找成功的情况下的平均查找长度 ASL 为 。4. 下面程序段中带下划线的语句的执行次数的数量级是 。i=1; while (i表示弧以及弧上的权值 z,则 E(G)为 E(G)= , , , 。要求：（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 为关键字,散列地址空间为 010。要求：（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。要求：6（1） 将该序列调整为“小顶”堆,并给出调整过程。请从时间和空间两方面对简单选择排序、树形选择排序和堆排序作一比较。（2） 若采用链式基数排序方法排序,请写出第一趟“分配”之后各队列的状态和第一趟“收集”之后的关键字序列。并请简要说出基数排序方法和其他排序方法有什么区别？（3） 要求最后排序结果是按关键字从小到大的次序排列,请给出冒泡排序的前 3 趟排序结果。四、简答题(共 30 分)1. (6 分) 线性表的顺序存储结构和链式存储结构各有哪些优缺点？ 2. (8 分) 画出对长度 n 为 10 的递增有序表A1、A2、A10进行折半查找的判定树。当实现插入排序过程时,可以用折半查找来确定第 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:7linklist ( ) head = new node ( ); head->next=NULL; /构造函数linklist ( ); /析构函数;/二叉链表的类定义：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=1263. (99+1)/2=504. O(nlog2n)5. (9+1)/2+(6+1)/2=17/2=8.56. log3(244+1)的上取整或 log3244 下取整+17. 长度相等,对应位置的字符相同8. n9. abc+*d-10. 500 (n2=499,n0=n2+1=499+1=500)三、应用题81.(1)二叉树D FECBAJHKGLI(2)森林DFECBAJHKG LI(3)中序全线索二叉树D FECBAJHKGLIN U L LN U L L(4)双亲孩子链表A - 1B 1E 1 I 1 D 2H 2 G 5 L 5 123456782 4365872. (1)9(2)(3)WPL=(3+6)*4+(8+10+15)*3+(19+21)*2=36+99+80=2153. (1)V 1510V 3V 6V 2V 5V 420301 0 0601550(2)101 2 3 4 5 61 0 5 2 0 50 103 0 15 4 20 0 60 5 0 6 30 100 0(3)DFS 序列：V1,V2,V3,V5,V6,V4DFS 生成树：V 1510V 3V 6V 2V 5V 4301550(4)拓扑序列：V1,V2,V6,V4,V3,V5(5)V1 (1) (2) (3) (4) (5)V2 (V1,V2)5X X X XV3 (V1,V2,V3)55(V1,V2,V3)55(V1,V2,V3)55XV4 (V1,V2,V6,V4)45X XV5 (V1,V2,V6,V5)115(V1,V2,V6,V4,V5)105(V1,V2,V3,V5)70V6 (V1,V2,V6)15X X Xu(u,v)长度V2(V1,V2)5V6(V1,V2,V6)15V4(V1,V2,V6,V4)45V3(V1,V2,V3)55V5(V1,V2,V3,V5)704. (1)关键字 26 36 41 38 44 15 68 12 06 51 25HASH 函数值 4 3 8 5 0 4 2 1 6 7 3比较次数 1 1 1 1 1 3 1 1 2 3 8H(k)=k%11, 数组范围：010下标 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