2018年北京市培养单位国家天文台862计算机学科综合(非专业)之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 对给定关键字序号j(1 中找到关键字从小到大排在第j 位上的记 录，写一个算法利用快速排序的划分思想实现上述查找(要求用最少的时间和最少的空间) 。 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。 【答案】算法如下； 在后半部分继续进行划分 在前半部分继续进行划分 2． 设在4地(A, B , C , D) 之间架设有6座桥，如图所示。 要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 (1)试就以上图形说明:此问题有解的条件是什么？ (2)设图中的顶点数为n ，试用C 或PASCAL 语言描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。 【答案】(1)只有所有的顶点的度都是偶数，才能有解。 (2)算法如下: 图中顶点的最大个数 弧(边) 结点 是邻接点在顶点向量中的下标，num 是边的编号 指向下一邻接点的指针 与弧(或边) 相关的信息指针 顶点结点 顶点信息及指向第一邻接点 的指针 邻接表 修改常规访问标志数组visited 的含义:当元素值为1时表示该边已访问；当元素值为0时表示该边尚未访问。 用邻接表作为存储结构的深度优先遍历算法 第一邻接点 结束dfs （ ） 求顶点的度 若顶点度为0, 或顶点的度不是偶 数，无解 无解 3． 试设计一个C 语言算法(或C 语言程序) :用单链表做存储结构，以回车符为结束标志，输入一个任意长度的字符串，然后判断该字符串是否为“回文”(正向读和反向读时，串值相同的字符串称为“回文”) ，输出信息“Yes ”或“NO ”；最后删除字符串并释放全部空间。例如: 若输入“ABCD12321DCBA”是回文，则输出“Yes”； 若输入“ABCD123DCBA”，不是回文，则输出“NO”。 要求:定义相关数据类型，不得使用数组(顺序表) 做字符串的存储结构和辅助存储空间。假定字符串的长度为n ，试分析上述算法的时间复杂度。 【答案】算法如下: //本算法判断数据域为字符且长为n 的单链表是否是”回文" ，返回1或0表示成功或失败 //字符栈，容量足够大 //设链表带头结点 //前一半字符入栈，链表指针后移 //若链表有奇数个结点，则跳过中间结点 //不是回文 4． 设有一头指针为L 的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针) ，data(数据) 和next(后继指针) 域外，还有一个访问频度域freq 。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate(L，X) 运算时，令元素值为x 的结点中freq 域的值增1，并使此链表中结点保持按访问频度非增(递减) 的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L，x) 运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。 【答案】算法如下: //L是带头结点的按访问频度递减的双向链表 //本算法先査找数据x ，査找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中 //P为L 表的工作指针，q 为p 的前驱，用于査找插入位置 //查找值为x 的结点 ("不存在所査结点\n”) ；exit(0)； //令元素值为x 的结点的freq 域加1