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）旨在结合认知心理学、脑科学和人类知识等，研发融合知识图谱、认知推理、逻辑表达的新一代认知引擎，支持大规模知识的表示、获取、推理与计算的基础理论和方法，实现人工智能从感知智能向认知智能的演进，建立可解释、鲁棒性的第三代人工智能。请结合数据结构中有关图的知识，设计一个抽象数据类型，表示儿童是如何进行概念学习、建立概念间联系、形成概念网络的。
