2018年西藏大学藏文信息技术研究中心840计算机专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、算法设计题
1． 用邻接多重表存储结构，编写FERST-ADJ(G，V) 函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。
【答案】算法如下:
在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回
确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情
况
返回第一邻接点，
和
中必有一个等于
i
取第一个边结点
2． 己知字符串S1中存放一段英文，写出算法format(s1，s2，s3，n) ，将其按给定的长度n 格式化成两端对齐的字符串S2，其多余的字符送S3。
【答案】算法如下:
//将字符串si 拆分成字符串S2和字符串S3，要求字符串S2长度为n 且两端对齐
//滤掉s1左端空格
("字符串s1为空串或空格串\n")；exit(0)；
}
//字符串S1向字符串S2中
复制
(”字符串s1没有
//P指针也后退
//往后査找一个非空格字符作为串S2的尾字
符
("s1串没有
//字符串s2最后一个非空字符
//置S2字符串结束标记
第 2 页，共 40 页
个有效字符\n"，n) ；exit(0)；
}
//若最后一个字符为空格，
则需向后找到第一个非空格字符
个两端对齐的字符串exit(0)；
}
//将s1串其余部分送字符串
S3
//置串S3结束标记
3． 设在4地(A, B , C , D) 之间架设有6座桥，如图所示。
要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 (1)试就以上图形说明:此问题有解的条件是什么？
(2)设图中的顶点数为n ，试用C 或PASCAL 语言描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。
【答案】(1)只有所有的顶点的度都是偶数，才能有解。 (2)算法如下:
图中顶点的最大个数
弧(边) 结点
是邻接点在顶点向量中的下标，num 是边的编号
指向下一邻接点的指针
与弧(或边) 相关的信息指针
顶点结点
顶点信息及指向第一邻接点
的指针
邻接表
修改常规访问标志数组visited 的含义:当元素值为1时表示该边已访问；当元素值为0时表示该边尚未访问。
用邻接表作为存储结构的深度优先遍历算法
第一邻接点
第 3 页，共 40 页
结束dfs （ ）
求顶点的度
若顶点度为0, 或顶点的度不是偶
数，无解
无解
4． 以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。
【答案】算法如下:
//串用一维数组s 存储，本算法求最长重复子串，返回其长度
//index记最长的串在s 串中的开始位置，max
记其长度
//length记局部重复子串长度，i 为字符数组下标
//上一个重复子串结束
//当前重复子串长
度大，则更新
max
//初始化下一重复子串的起始位置和长度
(”最长重复子串的长度为
.//算法结束
5． 当一棵有n(
，在串中的位置
，max ，index) ；
时间复杂度:算法的时间复杂度为O(n)，每个字符与其后继比较一次。
) 个结点的二叉树按顺序存储方式存储在
中时，试写一个算法，求
出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。
【答案】算法如下:
第 4 页，共 40 页