koorio.com
海量文库 文档专家
赞助商链接
当前位置:首页 >> 研究生入学考试 >>

武汉科技大学考研真题之计算机软件技术基础2004答案年专业课考研真题


2004 年硕士研究生考试《软件基础 1》试题参考答案 一、填空题(2×15=30) 1、无回路 3、 (?x ( ) ?P( x) ? Q( x)) 5、3 7、n×(n-1) n 9、A[r]=x; r1)=(r+1)%m; 11、n 2、φ 4、6 6、任一结点无右孩子 8、1000*1000 是 10、O(n2) 12、待排序的记录数 n ?log2 n? +1 二、简答题(4+5+5+5+5+6=30 分) 1、 答: (1)头结点的数据域可以存储链表的附加信息; (2)便于链表的插入和删除操作; (3)标识该单链表 (4)其指针域可表示第一个元素结点的存储未知 2、 答:最多有 7 个结点,最少有 4 个结点(不包含叶子结点) 。 O O O O F F F F O F F O F F O O F O O O O O O O O F F F F F F F F F 3、 答:举例:5 4 1 在第一趟比较时,5 和 4 比较,则 5 和 4 交换,而 4 却朝着与最终排序相反 的方向移动。 快速排序是对起泡排序方法的一种改进, 只是改进了数据交换和比较的次数, 而其它特点同起泡排序方法一样。快速排序方法也存在上述现象。 1 4、 答:结论不对。反例如下: 假设在叶子结点 4 处结束,则 A={2} B={1,5,3,4} C={6} 若 a=2,b=1,c=6 很显然,a≤b≤c 不成立 5、 答:二元关系 R={<a,a>,<a,b>,<b,c>,<c,b>} ; 其关系图如图所示。 6、 答: (1)4132 (2)4213 (3)4231 5 3 2 4 6 a b c 三、综合题() 1、答: (1)答案有多种 (一种见右边) (2)欧拉回路的必要条件为: 每个结点的度为偶数。 A C B D A 2、如图所示: 从 C 点开始按深度优先遍历该图的结果: C,A,B,F,E,D C,A,B,D,F,E C,A,D,E,B,F C,D,E,A,B,F B D C F E 3、证明:a=a∧ (a∨ c)=a∧ (b ∨ c)=(a∧ b)∨ (a∧ c) =(b∧ a)∨ (b∧ c)=b∧ (a∨ c)=b∧ (b∨ c)=b 4、答:假设该树中有 b 个分支结点,n0 个叶子结点; 则:该树共有分支数 B=kb n=b+n0 n=B+1 所以:n0=n-(n-1)/k 5、答:假设该树的结点总数为 N,分支数为 B,则: N=m+n N=B+1 B=mk 所以: n=mk+1-m 6、 证明: (用反证法)假设 G 和 G’均不连通,则: G 中存在一个结点(假设为结点 Vi)与其它结点均无边相连; 同理,G’ 中也存在一个结点(假设为结点 Vj)与其它结点均无边相连; 则将 G 和 G’合起来后,结点 Vi 和 Vj 无边相连。 与两图合起来为完全图相矛盾。 所以假设不成立,G 或 G’是连通的成立。 6、 答: (1)顺序查找时的判定树和采用折半查找时的判定树分别如下: do for if repeat while for while if do repeat (2)顺序查找成功时的平均查找长度: (p1×1+p2×2+p3×3+p4×4+p5×5)/(p1+p2+p3+p4+p5) =(0.2×1+0.15×2+0.1×3+0.03×4+0.01×5)/0.49 =0.97/0.49=2 顺序查找不成功时的平均查找长度: (q0×1+q1×2+q2×3+q3×4

赞助商链接
推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 酷我资料网 koorio.com
copyright ©right 2014-2019。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com