2018年广西大学计算机与电子信息学院408计算机学科专业基础综合之数据结构考研强化五套模拟题
● 摘要
一、算法设计题
1． 给定nxm 矩阵
并设
设计一算法判定x 的值是否在A 中，要求时间复杂度
为O(m＋n) 。
【答案】算法如下:
//n*m矩阵A ，行下标从a 到b ，列下标从c 到d ，本算法査找x 是否在矩阵A 中
//flag是成功査到x 的标志
//假定x 为整型
(“矩阵A 中无
算法search 结束。
2． 设在4地(A, B , C , D) 之间架设有6座桥，如图所示。
元素\n"，x) ；
要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 (1)试就以上图形说明:此问题有解的条件是什么？
(2)设图中的顶点数为n ，试用C 或PASCAL 语言描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。
【答案】(1)只有所有的顶点的度都是偶数，才能有解。 (2)算法如下:
图中顶点的最大个数
弧(边) 结点
是邻接点在顶点向量中的下标，num 是边的编号
指向下一邻接点的指针
与弧(或边) 相关的信息指针
顶点结点
顶点信息及指向第一邻接点
的指针
邻接表
修改常规访问标志数组visited 的含义:当元素值为1时表示该边已访问；当元素值为0时表示该边尚未访问。
用邻接表作为存储结构的深度优先遍历算法
第一邻接点
结束dfs （ ）
求顶点的度
若顶点度为0, 或顶点的度不是偶
数，无解
无解
3． 设给定关键字输入序列为(100，90，120，60，78，35，42，31，15) 用哈希法散列0-10的地址区间。要求设计一合理的哈希函数；冲突时用链表法解决，写出哈希算法，并构造出哈希表，在等概率查找情况下查找成功的平均查找长度是多少？
【答案】算法如下:
关键字
链指针
用链地址法解决冲突，构造哈希表，哈希函数用
初始化
输入n(本例中n=9)
个关键字按题意x 互不相同
4等插入结点链入同义词表
构造的哈希表如图所示:
图构造的哈希表
查找成功时的平均查找长度
。
4． 请用流程图或高级语言表示算法。已知有向图有n 个顶点，请写算法，根据用户输入的数对建立该有向图的邻接表。即接受用户输入的
(以其中之一为0标志结束) ，对于每条这样的
边，申请一个结点，并插入到的单链表中，如此反复，直到将图中所有边处理完毕。
提示:先产生邻接表的n 个头结点(其结点数值域从1到n) 。 【答案】算法如下:
建立有向图的邻接表存储结构
输入顶点信息