2007年湖北武汉科技大学软件基础考研真题.doc

发布时间：2022-10-27 发布人：admin 分类：说明书资料大小：0.12M 资料格式：doc 举报版权申诉

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2007 年湖北武汉科技大学软件基础考研真题第一部分数据结构（80 分） 1、（10 分）设键盘输入若干个正整数（以输入 0 表示结束），试设计相应的数据结构及算法建立一个单向链表，要求满足以下要求：（1）如果整数重复出现，则只在链表上保留一个；（2）链表结点中包含一个计数域，记录该整数重复出现的次数；（3）构造的链表应以整数重复出现次数的降序排列； 2、（10 分）假设一稀疏矩阵 A[1..n,1..n]如下：该矩阵中非零元逐行存放于数组 B[0..3n-3]中，使得 B[k]=A[i,j]，写出将 A 存入数组 B 中的算法以及由数组 B 确定 A[i,j]的算法。 3、（10 分）模式匹配算法是在主串中快速寻找模式的一种有效的方法。（1）假设串采用如下存储结构，试设计 KMP 算法实现模式匹配。（2）如果主串和模式的长度分别为 m，n，则 KMP 算法的时间复杂性是多少？（3）如果某一模式 P=’abcaacabaca’，请给出它的 NEXT 函数值。 4、（10 分）设有两个栈 S1,S2 都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。若采取如下数据结构，试设计 S1,S2 有关入栈和出栈的操作算法。

5、（10 分）若二叉树采用二叉链表的数据结构，试设计相应的非递归算法中序遍历该二叉树。 6、（10 分）下表给出了某工程各工序之间的优先关系和各工序所需时间。（1）画出相应的 AOE 网。（2）列出各事件的最早发生时间，最迟发生时间。（3）找出关键路径并指明完成该工程所需最短时间。 7、（10 分）二叉排序树的建立是否与关键字输入序列有关？试给出例子进行说明来证明你的结论。试设计一个递归算法能够输出二叉排序树的关键字降序序列。对于某二叉排序树，现在需要删除指针 p 所指向的节点（其双亲节点指针为 f，p 是 f 的左孩子节点）使得该二叉树仍然是二叉排序树，试根据不同的情况写出相应的操作算法。 8、（10 分）对于 n 个元素组成的线性表进行快速排序时，所需进行的比较次数与这 n 个元素的初始排序有关。问：（1）当 n=7 时，在最好情况下需进行多少次比较？请说明理由。（2）当 n=7 时，给出一个最好情况的初始排序的实例。（3）当 n=7 时，在最坏情况下需进行多少次比较？请说明理由。（4）当 n=7 时，给出一个最坏情况的初始排序的实例。第二部分离散数学（70 分） 1.（10 分）证明： 2．（10 分）设 G 是无向连通图，证明：若 G 中有桥或割点，则 G 不是哈密顿图。 3．（10 分）在一次象棋比赛中，n 名选手中的任意两名选手之间至多只下一盘，又每人至少下一盘，证明：总能找到两名选手，他们下棋的盘数相同。 4.（10 分，每个问题 2 分）设 F 表示一年级大学生的集合，S 表示二年级大学生的集合，M 表示数学专业学生的集合，R 表示计算机专业学生的集合，T 表示听离散数学课学生的集合，G 表示星期一晚上参加音乐会的学生的集合，H 表示星期一晚上很迟才睡觉的学生的集合。问下列各句子所对应的集合表达式分别是什么？请从备选的中挑出来。 (1)所有计算机专业二年级的学生在学离散数学课。 (2)这些且只有这些学离散数学课的学生或者星期一晚上去听音乐会的学生在星期一晚上很迟才睡觉。 (3)听离散数学课的学生都没参加星期一晚上的音乐会。 (4)这个音乐会只有大学一、二年级的学生参加。 (5)除去数学专业和计算机专业以外的二年级学生都去参加了音乐会。备选：

5.（10 分）在自然推理系统 F 中，证明推理：好人、坏人都是人，猴子不是人，因此猴子既不是好人、也不是坏人。 6．（10 分）利用 Kruskal 算法求下图一棵最小生成树。 7.（10 分）设群 G 为，其中⊕为集合的对称差运算，解下列方程： {a}⊕x=φ和 y⊕{a,b}={b}。

分享到：

赞收藏

资料库

2007年湖北武汉科技大学软件基础考研真题.doc

相关推荐

考研

热门标签

最新资料