188宝金博页面版

2017 年杭州电子科技大学数字媒体与艺术设计学院 851 数据结构考研导师圈点必考题汇编?一? 说明?①本资料为 VIP 学员内部使用?整理汇编了历届导师圈点的重点试题及常考试题。 —————————————————————————————————————————— 一、填空题 1? 对于一个具有n个结点的单链表?在已知的结点半p后插入一个新结点的时间.复杂度为_____?在给定值为 x 的结点后插入一个新结点的时间复杂度为_____。 【答案】 【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到 x 的结点。 2? 阅读下列程序说明和裎序?填充程序中的_____。 【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示?编科略? 本程序采用非递归的方法?设立一个堆栈 存放还没有转换过的结点?它的栈顶指针为 。交换左、右子树的算法为? ?1?把根结点放入堆栈。 ?2?当堆栈不空时?取出栈顶元素?交换它的左、右子树?并把它的左、右子树分别入栈。 ?3?重复?2?直到堆栈为空时为止。 ?1? {?2? If? ?3? ? } }} 【答案】 【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈?然后判断栈足否为空?如果不为空?则取栈顶元素?交换取出节点的左右指针。并将左右指针分别进桟?重复这一操作。完成二叉树左右孩子的交换。 3? 应用 prim 算法求解连通网络的最小生成树问题。 ?1?针对如图所示的连通网络?试按如下格式给出在构造最小生成树过程中顺序选出的各条边。 〔始顶点号?终顶点号?权值?