2018年西安科技大学计算机科学与技术学院408计算机学科专业基础综合之数据结构考研核心题库
● 摘要
一、算法设计题
1． 若x 和y 是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。
【答案】算法如下:
//本算法判断两个顺序存储的串x 和y 是否相等，相等返回1，否则返回
//对应字符相等，指针后移
2． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
【答案】算法如下:
//la，lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列 //本算法将两链表合并成一个按元素值递减次序排列的单链表
//pa, pb 分别是链表la 和lb 的工作指针
//la作为结果链表的头指针，先将结果链表初始化为空
//当两链表均不为空时
//将pa 的后继结点暂存于
r
//将pa 结点链于结果表中，同时逆置
//恢复pa 为当前待比较结点
//将pb 的后继结点暂存于
r
//将pb 结点链于结果表中，同时逆置
//恢复pb 为当前待比较结点
//避免再对pa 写下面的While 语句
//算法Union 结束
3． 已知L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符、数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符(要求用最少的时间和最少的空间) 。
【答案】算法如下:
L 是不带头结点的单链表第一个结点的指针，链表中的数据域存放字符
//本算法将链表L 分解成含有英文字母字符、数字字符和其他幸符的带头结点的三个循环链表
//建立三个链表的头结点
//置三个循环链表为空表
//分解原链表
//L指向待处理结点的后继
//处理字母字符
//处理数字字符
//处理其他符号
//结束while(L!＝
null) //算法结束
4． 令G=(V, E) 为一个有向无环图，编写一个给图G 中每一个顶点赋以一个整数序号的算法，并满足以下条件:若从顶点i 至顶点j 有一条弧，则应使i 【答案】算法如下: 对以邻接表存储的DAG 图g 重新编号, 使若有 ，则编号 求各顶点的入度 记录结点的逆序序号 5． 已知二叉树采用二叉链表存储，设计算法以输出二叉树T 中根结点到每个叶结点的路径。 【答案】算法如下:: 打印从根结点bt 到结点p 之间路径上的所有结点 . 是元素为二叉树结点指针的栈，容量足够大 是数组，元素值为0或1, 访问左、右子树的标志，tag 和s 同 步 根结点就是所找结点 左子女入栈，并置标记 找到结点P , 栈中元素均为结点P 的祖先 从根结点到P 结点的路径为 沿左分支向下 本题不要求输出遍历序列， 这里只出栈 沿右分支向下 结束算法 为叶结点 从根结点到P 结点的路径为 输出从根到叶子q 的路径上的所有袓先 二、应用题 6． 带权图(权值非负，表示边连接的两顶点间的距离) 的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法: ①该最短路径初始时仅包含初始顶点，令当前顶点为初始顶点；
相关内容
相关标签