1、 科目代码: 821 科目名称: 数据结构及算法 第 1 页 共 2 页 南京师范大学南京师范大学 20212021 年硕士研究生入学考试初试试题(年硕士研究生入学考试初试试题( B 卷)卷) 科目代码: 821 科目名称: 数据结构及算法 满分: 150 分 考生注意:认真阅读答题纸上的注意事项;所有答案必须写在考生注意:认真阅读答题纸上的注意事项;所有答案必须写在答题纸答题纸上,写在本试题纸或草稿纸上上,写在本试题纸或草稿纸上均无效;均无效;本试题纸须随答题纸一起装入试题袋中交回!本试题纸须随答题纸一起装入试题袋中交回! 一一、单项选择题(每、单项选择题(每小小题题 3 3 分,共分,共
2、3 30 0 分)分) 1. 对一个算法的评价,不包括如下( )方面的内容。 A. 健壮性和可读性 B并行性 C正确性 D时空复杂度 2. 在带有头结点的单链表 HL 中,要向表头插入一个由指针 p 指向的结点,则执行( ) A. p-next=HL-next; HL-next=p; B. p-next=HL; HL=p; C. p-next=HL; p=HL; D. HL=p; p-next=HL; 3. 在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有相同的( ) A行号 B列号 C元素值 D非零元素个数 4. 若需要利用形参直接访问实参时,应将形参变量说明为( )参数。 A
3、值 B函数 C指针 D引用 5. 采用开放定址法处理散列表的冲突时,其平均查找长度( ) A低于链接法处理冲突 B. 高于链接法处理冲突 C与链接法处理冲突相同 D高于二分查找 6. 设有一个二维数组 Amn,假设 A00存放位置在 644(10),A22存放位置在 676(10),每个元素占一个空间,问 A33(10)存放在( )位置?脚注(10)表示用 10 进制表示。 A688 B678 C692 D696 7. 在含 n 个顶点和 e 条边的无向图的邻接矩阵中,零元素的个数为( ) Ae B2e Cn2e Dn22e 8. 用某种排序方法对关键字序列(25,84,21,47,15,27
4、,68,35,20)进行排序时,序列的变化情况如下: 20,15,21,25,47,27,68,35,84 15,20,21,25,35,27,47,68,84 15,20,21,25,27,35,47,68,84 则所采用的排序方法是( ) A选择排序 B希尔排序 C归并排序 D快速排序 9.设栈 S 和队列 Q 的初始状态为空,元素 E1、E2、E3、E4、E5 和 E6 依次通过栈 S,一个元素出栈后即进入队列 Q,若 6 个元素出列的顺序为 E2、E4、E3、E6、E5 和 E1,则栈 S 科目代码: 821 科目名称: 数据结构及算法 第 2 页 共 2 页 的容量至少应该是( )
5、A. 6 B. 4 C. 3 D. 2 10. 设某有向图中有 n 个顶点,则该有向图对应的邻接表中有( )个表头结点。 A. n-1 B. n C. n+1 D. 2n-1 二、算法设计题(每二、算法设计题(每小小题题 10 分,共分,共 60 分)分) 1. 设有两个集合 A 和集合 B,要求设计生成集合 C=AB 的算法,其中集合 A、B 和 C 用链式存储结构表示。 2. 设计在链式存储结构上建立一棵二叉树的算法。 3. 设计判断单链表中结点是否关于中心对称算法。 4. 一棵二叉树以二叉链表的存储结构如下。设计一个算法,求在前序序列中处于第 K 个位置的结点。 lchild data
6、rchild 5. 设计在顺序存储结构上实现求子串算法。 6. 写一算法,将一单链表逆转。要求逆转在原链表上进行,不允许重新构造一个新链表。 三、综合应用题(每三、综合应用题(每小小题题 15 分,共分,共 60 分)分) 1. 请画出下图的邻接矩阵和邻接表。 2. 假定用于通讯的电文由 a、b、c、d、e、f、g、h 等 8 个字符组成,它们在电文中出现的频率分别为:0.07、0.19、0.02、0.06、0.32、0.03、0.21、0.10,请: (1)画出为这些字符设计赫夫曼编码所构造的赫夫曼树; (2)写出各个字符的赫夫曼编码。 3. 音乐播放器是一款常用应用程序,请: (1)描述音乐播放器的常见播放方式及功能特点;(2)用数据结构知识分析这些功能实现的数据结构; (3)写出实现这些功能的伪代码。 4. 认知图谱(Cognitive Graph)旨在结合认知心理学、脑科学和人类知识等,研发融合知识图谱、认知推理、逻辑表达的新一代认知引擎,支持大规模知识的表示、获取、推理与计算的基础理论和方法,实现人工智能从感知智能向认知智能的演进,建立可解释、鲁棒性的第三代人工智能。请结合数据结构中有关图的知识,设计一个抽象数据类型,表示儿童是如何进行概念学习、建立概念间联系、形成概念网络的。