数据结构考研题.doc

1、求整数 n(n≥0)阶乘的算法如下，其时间复杂度是 int fact(int n) { if (n=1)return 1; return n*fact(n-1); } A. O(log2n) B. O(n) C. (nlog2n) D. O(n2) 答案：B 2、已知操作符包括‘+’、‘-’、‘*’、‘/’、‘(’和‘)’。将中缀表达式 a+b-a*((c+d)/e-f)+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是 A. 5 B. 7 C. 8 D. 11 答案：A 后缀表达式中：1）若读到的是操作数，这输出该操作数，并读入下一个字符；2）若读到的是左括号则压入到OPTR栈中，并读入下一个字符；3）若读到是右括号，这表明括号中的中缀表达式已经扫描完毕，将OPTR栈从栈顶直到左括号之前的操作符依次出栈并输出，然后左括号也出栈，并读入下一个字符；4）若读到的是操作符（c）则应与操作符栈的栈顶元素（pre_op）进行比较：若cpre_op,则将c入栈，并读入下一个字符，若c=pre_op，则将pre_op出栈并输出 3、若一棵二叉树的前序遍历序列为 a, e, b, d, c，后序遍历序列为 b, c, d, e, a，则根结点的孩子结点 A. 只有 e B有 e、b C. 有 e、c D. 无法确定 答案：A 采用排除法来做该题,若b是a的孩子结点，则由前续遍历可知，b不可能为左孩子结点，所以后序遍历不可能是以b开始；若c是孩子结点，则c为右孩子，且c不存在孩子结点，在这种情况下仍不能得到题中的后续遍历序列；若d为孩子结点，则二叉树应是，e和d为a的孩子结点，b为e的孩子结点，c为d的孩子结点，当这种情况下的后续遍历，仍不满足题中的后序遍历序列，所以只能e是a的孩子结点 若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为 A.10 B.20 C.32 D.33 答案：B 因为所有非叶子结点的平衡因子是1，所以该平衡树所有非叶子结点的左子树的深度减去右子树的深度的值为1.又因为该树的高度为6，所以由题意可知，该树共有20个结点形状为 对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是 O(n) B.O(e) C.O(n+e) D.O(n*e) 答案：C 课本P149 若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是 存在且唯一 B.存在且不唯一 C.存在可能不唯一 D.无法确定是否存在 答案：C 因为该有向图主对角线及以下元素均为0，所以该图中不存在循环结构，即该有向图存在拓扑序列，当该有向图的邻接矩阵表上三角全为1时，拓扑序列唯一，否则拓扑序列不唯一 对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求源点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是 d,e,f Bf,e,d 答案：后序其余顶点应为d，f，e dist s path a 0 0 1 1 1 1 0 b 3 0 1 1 1 1 0 c 5 4 4 0 1 1 1 0 1 1 d ∞ 6 6 6 0 1 1 -1 1 1 e ∞ 7 7 7 0 -1 1 1 f ∞ 6 6 0 1 -1 2 下列关于最小生成树的说法中，正确的是 I. 最小生成树树的代价唯一 II. 权值最小的边一定会出现在所有的最小生成树中 III. 用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同 IV. 普里姆算法和克鲁斯卡尔（Kruskal）算法得到的