题目内容
（请给出正确答案）
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
更多“a)试按照158页6.4节的思路，以邻接表的形式实现图ADT的各操作接口;b)分析这一实现方式的时间、空间效率，并与基于邻接矩阵的实现做一对比。”相关的问题
试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点vi到顶点vi的路径(i≠j)。注意：算法中涉及的图的基本操作必须在存储结构上实现。
试写一算法；判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i＜＞j)。注意：算法中涉及的图的基本操作必须在存储结构上实现。【哈尔滨工业大学2001九(12分)】
当元素类型为字符串时，为避免复杂的散列码转换，可以改用键树(trie)结构来实现词典ADT。
a)remove()接口复杂度中的因子r可否消除？
b)put()接口复杂度中的因子r可否消除？
c)试举例说明，以上实现方式在最坏情况下可能需要多达Ω(nr)的空间，其中n=|S|为字符串集的规模。
d)试改用列表来实现各节点，使所需空间的总量线性正比于S中所有字符串的长度总和——当然，get()接口的效率因此会降至O(hr)，其中h为树高，同时也是Ss中字符串的最大长度。
e)键树中往往包含大量的单分支节点。试如图x9.5所示，通过折叠合并相邻的单分支节点，进一步提高键树的时、空效率。改进之后，键树的时、空复杂度各是多少？
f)习题[8-19](173页)曾介绍过四叉树(quadtree)结构，并指出其深度不受限制的缺陷。若将四个象限的二进制编码视作字符，即将字符表取作∑={00，01，10，11}，则四叉树可以看作键树的特例，试基于这一理解，仿照以上技巧对四叉树进行压缩，使其深度不致超过O(n)。
A.ADT是对数据进行处理的一种逻辑描述。
B.ADT建立的封装技术将可能的处理实现细节隐蔽起来。
C.同一ADT只有唯一的数据结构可以实现。
D.采用程序设计语言的控制结构和基本数据类型来实现ADT的所提供的逻辑接口。
试分别以顺序表和单链表作存储结构，各写一个实现线性表的自身(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a1，a2，…an)逆置为(an，…a2，a1)。
已知图采用邻接表存储方式，试写出删除边(vi，vi)(对于无向图)或删除弧i，Vi＞(对于有向图)的算法。
警告：系统检测到您的账号存在安全风险
为了保护您的账号安全，请在“简答题”公众号进行验证，点击“官网服务”-“账号验证”后输入验证码“”完成验证，验证成功后方可继续查看答案！
