2018年贵州财经大学信息学院408计算机学科专业基础综合之数据结构考研基础五套测试题
● 摘要
一、算法设计题
1． 串以静态存储结构存储，结构如下所述，试实现串操作equal 算法。
串被确认的最大长度
【答案】算法如下:
//本算法判断字符串S 和字符串t 是否相等，如相等返回1，否则返回
//在类C 中，一维数组下标从零开始
//两串相等
//算法结束
2． 试设计一个C 语言算法(或C 语言程序) :用单链表做存储结构，以回车符为结束标志，输入一个任意长度的字符串，然后判断该字符串是否为“回文”(正向读和反向读时，串值相同的字符串称为“回文”) ，输出信息“Yes ”或“NO ”；最后删除字符串并释放全部空间。例如:
若输入“ABCD12321DCBA”是回文，则输出“Yes”； 若输入“ABCD123DCBA”，不是回文，则输出“NO”。
要求:定义相关数据类型，不得使用数组(顺序表) 做字符串的存储结构和辅助存储空间。假定字符串的长度为n ，试分析上述算法的时间复杂度。
【答案】算法如下:
//本算法判断数据域为字符且长为n 的单链表是否是”回文" ，返回1或0表示成功或失败
//字符栈，容量足够大
//设链表带头结点
//前一半字符入栈，链表指针后移
//若链表有奇数个结点，则跳过中间结点
//不是回文
3． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下: 对以邻接表存储的DAG 图g 重新编号, 使若有 记录结点的逆序序号 4． 已知关键字序列( 试写出一算法将( 利用(1)的算法写一个建大根堆的算法。 【答案】(1)算法如下: '' 假设 是大堆，本算法把 (2) ，则编号 求各顶点的入度 ) 是大根堆。 ) 调整为大根堆； 调成大堆 5． 设二叉树用二指针结构存储(可以是动态存储结构) ，元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。 【答案】算法如下: 在二叉树t 中査找结点值等于x 的结 点 结束 统计以t 为根结点的子树的叶结点数 n0 . 叶结点 输出并计数 结束 : 二、应用题 6． 将算术表达式 转化为二叉树。 【答案】该算术表达式转化的二叉树如图所示。 图 7． 设将n(n>l)个整数存放到一维数组R 中. 试设计一个在时间和空间两方面都尽可能高效的算法，将R 中存有的序列循环左移P(0 中的数据由 . 要求: (1)给出算法的基本设计思想. (2)根据设计思想，采用C 或C++或JA V A 语言描述算法，关键之处给出注释. (3)说明你所设计算法的时间复杂度和空间复杂度. 【答案】(1)算法的基本设计思想:先将n 个数据由 变换为 原地逆置，