数据结构考研分类复习真题 第七章 图[52]

五算法设计题

．(单独命题考生做)设无向图G有n个顶点m条边试编写用邻接表存储该图的算法(设顶点值用～n或～n编号) 【南京航空航天大学 十二 (分)】

．请用流程图或类高级语言(pascal或c)表示算法已知有向图有n个顶点请写算法根据用户输入的偶对建立该有向图的邻接表即接受用户输入的<vivj>(以其中之一为标志结束)对于每条这样的边申请一个结点并插入到的单链表中如此反复直到将图中所有边处理完毕提示先产生邻接表的n个头结点(其结点数值域从到n)【上海大学 四 (分)】

．设无向图G有n个点e条边写一算法建立G的邻接多表要求该算法时间复杂性为O(n+e)且除邻接多表本身所占空间之外只用O()辅助空间【东南大学 六(分) 二 (分)】

．给出以十字链表作存储结构建立图的算法输入(ijv)其中ij为顶点号v为权值【河海大学 六 (分)】

．设有向G图有n个点(用…n表示)e条边写一算法根据其邻接表生成其反向邻接表要求算法复杂性为O(n+e)【东南大学 三 (分)】

类似本题的另外叙述有

()下图(编者略)是有向图按出度建立的邻接表试写一算法将此出度邻接表改成入度建立的邻接表【北京邮电大学 五 (分)】

()编写算法实现以下功能根据含有n个顶点的有向图邻接表构造相应的逆邻接表【东南大学 六(分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []