得分 评卷人 三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小 题2分，共14分) )1.算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。 )2.用字符数组存储长度为n的字符串，数组长度至少为n十1。 )3.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 )4.邻接矩阵适用于稀疏图的表示，邻接表适用于稠密图的表示。 ( )5.对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的新所有顶点。 )6.在索引顺序结构的搜索中，对索引表只可以采取顺序搜索，不可以采用折半搜索。 ( )7.图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。 得 分 评卷人 四、运算题（每小题6分，共30分） 1.假定一棵二叉树广义表表示为a(b(c),d(e,f),分别写出对它进行中序、后序、按层遍 历的结果。 中序： 后序： 按层： 2.一个一维数组a[12]中存储着有序表(15,26,34,39,45,56,58,63,74,76,80,86)，根据 折半搜索所对应的判定树，写出该判定树中度为1的结点个数，并求出在等概率情况下进行成 功搜索时的平均搜索长度。 度为1的结点个数： 平均搜索长度： 3.假定一个线性序列为(38,42,55,15,23,44,30,74,48,26)，根据此线性序列中元素的 排列次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点、右子树为空 的所有单支结点和所有叶子结点，请按照结点值从小到大的次序写出。 左子树为空的所有单支结点： 右子树为空的所有单支结点： 所有叶子结点： 70得 分 评卷人 三、判断题，在每小题前面打对号表示正确或打叉号表示错误(每小 题 2分 ，共 14分) )1 )2 2 .、 了 ‘ 龟 0 口 ‘斗 、.产 、 J )5 )6 ( )7 算法和程序都应具有下面一些特征 :有输人 ，有输 出，确定性，有穷性 ，有效性 。 用字符数组存储长度为 n的字符串，数组长度至少为 n-1- l o 在用循环单链表表示的链式队列中，可以不设队头指针 ，仅在链尾设置队尾指针 。 邻接矩阵适用于稀疏图的表示 ，邻接表适用于稠密图的表示。 对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。 在索引顺序结构的搜索中，对索引表只可以采取顺序搜索 ，不可以采用折半搜索 。 图中各个顶点 的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。 得 分 评卷人 四、运算题(每小题 6分.共 30分 ) 1.假定一棵二叉树广义表表示为 a(b(c),d(e,f))，分别写出对它进行中序、后序、按层遍 历的结果。 中序 : 后序 : 按层 : 2.一个一维数组 a巨12]中存储着有序表(15,26,34,39,45,56,58,63,74,76,80,86)，根据 折半搜索所对应的判定树 ，写出该判定树 中度为 1的结点个数 ，并求 出在等概率情况下进行成 功搜索时的平均搜索长度。 度为 1的结点个数: 平均搜索长度: 3.f段定一个线性序列为(38,42,55,15,23,44,30,74,48,26)，根据此线性序列 中元素的 排列次序生成一棵二叉搜索树，求出该二叉搜索树中左子树为空的所有单支结点、右子树为空 的所有单支结点和所有叶子结点，请按照结点值从小到大的次序写出。 左子树为空的所有单支结点 : 右子树为空的所有一单支结点 : 所有叶子结点 :