当前位置：问答库＞考研试题

武汉科技大学

2004年硕士研究生入学考试试题

课程名称：软件基础1 总页数：3 说 明：1. 适用专业：计算机应用技术

2. 答题内容写在答题纸上，写在试卷或草稿纸上一律无效。

3. 算法描述可用类Pascal 或C 语言。

4. 本试卷共4大题，分值共150分，考试时间为3小时。

一、 填空题（2×15＝30分）

1、 一个连通且（ ）的无向图称为树。

2、 若集合A ＝｛a ，b ｝，B ＝｛1，2，3｝，则（A ×B ）∩（B ×A ）＝（ ）。

3、 公式(∀x ) P (x ) →(∃x ) Q (x ) 对应的前束范式是（ ）。

4、 设A={a,b}，B={x,y,z}，可以定义由A 到B 的入射函数个数有（ ）个。

5、 设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1，则顺序栈的容量至少应为（ ）。

则该二叉树一定满足（ ）。 6、 已知一颗二叉树的先序序列和中序序列相反，

7、 有n 个顶点的有向连通图最多有（ ）条边，最少有（ ）条边。 8、 表示一个有1000个顶点、1000条边的有向图的邻接矩阵有（ ）个矩

（ ）。 阵元素，是否稀疏矩阵（是/否）

9、 已知循环队列存储在数组A 中，其下标范围为0～m-1，头尾指针分别为f 和r ，则将值为x 的元素入队的操作序列是（ ）。

10、 在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为

。 （ ）

，最小递归深度是（ ）。 11、 快速排序的最大递归深度是（ ）

。 12、 归并排序所需要的辅助存储空间的大小是（ ）

二、 简答题（30分）

1、 （4分）对链表设置头结点的作用是什么？（至少说出两条好处）

试问含有8个关键字的3－阶B 树最多有几个结点？最少有几个结2、 （5分）

点？画出其形态。

3、 （5分）在起泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。快速排序过程中有没有这种现象？