浙江大学-878-2012-真题.pdfVIP

各个学校计算机/软件专业考研真题 免费分享 /csseky/cskaoyan 浙 江 大 学 2012 年攻读硕士学位研究生入学考试试题 考试科目 计算机专业基础（A 卷） 编号 878 注意：答案必须写在答题纸上，写在试卷或草稿纸上均无效 第一部分：数据结构（共60 分） 一、单项选择题（每题2 分，共24 分） 1.下列函数的时间复杂性是： int f(int n) 微 { if(n=0) return 1; 信 else return n+f(n-1); 公 } n 众 n 2 A. O(log 2) B. O(n) C. O(nlog 2) D. O(n ) 号 2.在单链表中，指针p 指着节点A ，若要删除A 之后的节点（假设存在），则语句可以为： A. p = p-next; B. p-next = p-next-next; 计 C. p = p-next-next; D. p-next = p; 算 机 3.在一个链式队列中，f 和r 分别指向队列的头和尾。如果将s 指向的结点插入队列中，正 确的操作是： 与 A. f-next = s; f = s; B. r-next = s; r = s; 软 C. s-next = r; r = s; D. s-next = f; f = s; 件 考 4.如果某非空二叉树的前序序列和后序序列正好相反，则该二叉树一定具有的特点是： A. 任一结点无左孩子 B. 任一结点无右孩子 研 C. 空或者只有一个结点 D. 不存在度为2 的节点 5.从权值分别为9，2，5，7 的四个叶子结点构造一棵哈夫曼(Huffman)树，则该树的带权路 径长度WPL 为: A. 23 B. 37 C. 44 D. 46 6.若想查找63，哪个最有可能是在二叉排序树上进行的查找： A． 2 25 101 39 80 70 59 63 B． 39 101 25 80 70 59 63 C． 101 70 2 39 25 59 80 63 D． 59 2 80 70 39 25 63 7.对于一个共有n 个结点、K 条边的森林，共有几棵树？ A. n-K B. n-K+1 C. n-K-1 D. 不能确定 获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 各个学校计算机/软件专业考研真题 免费分享 /csseky/cskaoyan 8.对于一个 n 个顶点的有向无环图，如果它的拓扑排序是唯一的，那么下列哪句话是不对 的？ A. 该图的最长路径是n-1 B. 该图不是一个双连通图 C. 至少存在一个顶点它的出度大于 1 D. 当从入度为0 的顶点开始分别进行深度和宽度遍历时，遍历结果是一样的 9.下图为AOV 网，其可能的拓扑排序有序序列为： B A E 微 C F 信 D 公 众 号 A. ACBDEF B. ACBEDF C. ABCEFD D. ABCDFE