13-14-2数据结构试卷(a).doc

得分 评卷人 二、选择题（每题2分，共40分） 算法指的是（ ）。A．计算机程序????? ? B．解决问题的计算方法C．排序算法???????? D．解决问题的有限运算序列 线性表采用链式存储时，结点的存储地址（ ）。A．必须是不连续的 B．连续与否均可C．必须是连续的 D．和头结点的存储地址相连续 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ）。A．O（1）????? B．O（n）???C．O（m）?? D．O（m+n） 线性表L在（ ）情况下适用于使用链式结构实现。A.需经常修改Ｌ中的结点值 B.需不断对Ｌ进行删除插入C.L中含有大量的结点 D.L中结点结构复杂 设单链表中结点的结构为(data，1ink)。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作? （ ）。A．s一1ink=p一1ink；p一1ink＝sB．q一1ink＝s；s一link=pC．p一link＝s一1ink；s一1ink＝pD．p一1ink＝s；s一1ink＝q 由两个栈共享一个向量空间的好处是：（ ）。A．减少存取时间，降低下溢发生的机率B．节省存储空间，降低上溢发生的机率C．减少存取时间，降低上溢发生的机率D．节省存储空间，降低下溢发生的机率 如下陈述中正确的是（ ）。A．串是一种特殊的线性表????????B．串的长度必须大于零C．串中元素只能是字母??????????D．空串就是空白串 一个非空广义表的表头（ ）。A．不可能是子表???????????B．只能是子表C．只能是原子?????????????D．可以是子表或原子 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（ ）。A.较快 B.较慢 C.相同 D.不一定 树中所有结点的度等于所有结点数加（ ）。A.0 B.1 C.一1 D.2 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（ ）。A.n B.n一1 C.n+1 D.2*n 某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。A.空或只有一个结点。 B.高度等于其结点数。C.任一结点无左孩子。 D.任一结点无右孩子。 n个结点的二叉树，若用二叉链表存贮则非空闲的左、右孩子链域为（ ）。A.n B.2n C.n-1 D.n+1 已知二叉树叶子数为50，仅有一个孩子的结点数为30，则总结点数为（ ）。A.130 B. 129 C.131 D.不确定 在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为（ ）。A．4?????????? B．5???????C．6???????D．7 假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是（ ）。 A．O(n)????????B．O(e)??? C．O(n+e)??? ? D．O(n*e) 在无向图中定义顶点vi与vj之间的路径为从vi到达vj的一个（ ）。A、顶点序列 B、边序列 C、权值总和 D、边的条数 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：????????20，15，21，25，47，27，68，35，84????????15，20，21，25，35，27，47，68，84????????15，20，21，25，27，35，47，68，84????则所采用的排序方法是（ ）。A．选择排序????B．希尔排序???? C．归并排序????D．快速排序 适于对动态查找表进行高效率查找的组织结构是（ ）。A．有序表??????B．分块有序表?? C．三叉排序树??D．线性链表 如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（ ）方法最快。A、起泡排序 B、快速排序 C、堆排序 D、直接选择排序 得分 评卷人 三、操作题（共50分） 1.若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，试画出二