数据结构例题详解09.ppt

真题解答 【参考答案】 该方法不一定能求得最短路径。 举例说明： 图a 图b 图a中，设初始顶点为1，目标顶点为4，欲求从顶点1到顶点4之间的最短路径。显然这两点之间的最短路径长度为2。但利用给定方法求得的路径长度为3，这条路径并不是这两点之间的最短路径。 图b中，设初始顶点为1，目标顶点为3，欲求从顶点1到顶点3之间的最短路径。利用给定的方法，无法求出顶点1到顶点3的路径。 此题目给出的算法的关键错误是，将局部最优作为全局最优处理，从而采用了贪心的方法。解答时只要能体现“局部最优不等于全局最优”的思想，就可以得到60%的分数。 真题解答 【参考答案】 （1）算法的基本设计思想： 定义两个指针变量p和q，初始时均指向头结点的下一个结点。p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到链表最后一个结点时，q指针所指元素为倒数第k个结点。 （2）算法的详细实现步骤： ? count = 0, p和q指向链表表头结点的下一个结点； ? 若p为空，转?； ? 若count等于k，则q指向下一个结点；否则，count = count + 1； ? p指向下一个结点，转步骤?； ? 若count等于k，则查找成功，输出该结点的data域的值，返回1；否则，查找失败，返回0； ? 算法结束。 真题解答 类似题目：给定一单链表，判断其链接是否存在回路，要求额外空间复杂度为O(1)。 真题解答 类似题目：令指针p指向非空链表中的一个结点，且该结点不在表尾。设计算法将p所指的结点删除。 分类测试 线性表、堆栈、队列、数组 树与图 查找与排序 线性表、堆栈、队列、数组 自测题 在具有n个结点的单链表中，实现下列哪个操作，其算法的时间复杂度是O(n) A．遍历链表和求链表的第i个结点 B．在地址为p的结点之后插入一个结点 C．删除开始结点 D．删除地址为p的结点的后继结点 线性表、堆栈、队列、数组 自测题 令P代表入栈，O代表出栈。则将一个字符串3 * a +b/c变为3 a * b c / +的堆栈操作序列是哪个？（例如将ABC变成BCA的操作序列是PPOPOO。） PPPOOOPPOPPOOO POPOPOPPOPPOOO POPPOOPPOPPOOO POPPOOPPOPOOPO 线性表、堆栈、队列、数组 自测题 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？ 单链表 仅有头指针的单循环链表 双链表 仅有尾指针的单循环链表 线性表、堆栈、队列、数组 自测题 线性表Ｌ在什么情况下适用于使用链式结构实现? 需经常修改Ｌ中的结点值 需不断对Ｌ进行删除插入 Ｌ中含有大量的结点 Ｌ中结点结构复杂 线性表、堆栈、队列、数组 自测题 对于一个具有n个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为 Ａ. O(n) Ｂ. O(1) Ｃ. O(n/2) Ｄ. O(n2) 线性表、堆栈、队列、数组 自测题 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是？ 5 1 2 3 4 4 5 1 3 2 4 3 1 2 5 3 2 1 5 4 线性表、堆栈、队列、数组 自测题 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn。若p1=n，则pi为： i n – i n – i + 1 不确定 线性表、堆栈、队列、数组 自测题 将5个字母 ‘ooops’ 按此顺序入栈，则有多少种不同的出栈顺序可以仍然得到 ‘ooops’？ 1 3 5 6 线性表、堆栈、队列、数组 自测题 链表不具有的特点是： 插入、删除不需要移动元素 可随机访问任一元素 不必事先估计存储空间 所需空间与线性长度成正比 线性表、堆栈、队列、数组 自测题 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间？ 单链表 双链表 单循环链表 带头结点的双循环链表 线性表、堆栈、队列、数组 自测题 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用哪种存储方式最节省时间？ 顺序表 双链表 单循环链表 带头结点的双循环链表 线性表、堆栈、队列、数组 自测题 数组A[1..5,1..6]每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为 1140 1145 1120 1125 线性表、堆