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

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

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2009 年湖北武汉科技大学软件基础考研真题一、填空题（每空 1.5 分，共 15 分） 1、某二叉树的先序和后序序列正好相反，则该二叉树一定是（1）的二叉树。 2、对二叉树从 1 开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（2）次序的遍历实现编号。 3、N 个顶点的有向完全图具有（3）条弧。。 4、N 个元素的顺序查找的平均查找长度为（4） 5、N 个结点的完全二叉树，其深度为（5） 6、二叉树的叶子结点 n0 与度为 2 的结点数 n2 的关系是（6） 7、将有关二叉树的概念推广到三叉树，那么，一颗有 244 个结点的完全三叉树的深度为（7）。 8、快速排序的时间复杂度为（8） 9、在做进栈操作时应判别栈是否（9）。出栈操作时应判别栈是否（10）二、判断题（每题 1.5 分，共 15 分） 1、折半查找方法要求待查表必须是顺序存储结构的有序表。 2、从循环单链表的任一结点出发，不一定能找到表中所有结点。 3、栈是一种先进先出的线性表。 4、串是一个或多个字符组成的有限序列。 5、完全二叉树的叶子结点只可能在层次最大的一层上出现。 6、快速排序算法是稳定的排序，而 shell 排序是不稳定的。 7、在数据结构中，数据的存储结构与所使用的计算机无关。 8、一个广义表的表尾总是一个广义表。 9、当两个字符出现的频率相同时，则其哈夫曼编码也相同。 10、如果某种排序算法是不稳定的，则该算法是没有实际意义的。三、综合应用题（60 分） 1、（6 分）证明在一棵满二叉树中分支 B 与叶子节点 n0 满足关系 B=2（n0-1）。 2、（12 分）已知关键字序列为∶（75，33，52，41，12，88，66，27），哈希表长为 1 0，哈希函数为∶H（k）=k MO D 7，解决冲突用线性探测再散列法，要求构造哈希表，求出等概率下查找成功的平均查找长度。 3、（12 分）已知有向图 G，顶点集为 V（G）={a，b，c，d，el，关系集为 E（G）={,,,,,,,}。（1）试画出图 G 的邻接表表示; （2）试说明，若已知顶点 i，j，如何根据邻接表确定顶点 i 是否邻接到 j; （3）对该图从结点 a 进行深度优先搜索，所得的序列是什么? 4、（6 分）试用权{7，5，1，2，4，5，3}构造哈夫曼树∶ （1）列出构造过程∶ （2）计算该树的路径长度; （3）计算该树的带权路径长度; 5、（6 分）试列出下图全部可能的拓扑序列。

6、（6 分）对关键字序列{161，738，92，485，637，101，21，530，791，306}进行快速排序（写出每一趟的结果）。 7、（6 分）已知二叉树结点的中序序列是 cgbahedjfi，后序序列是 gbchejifda，请画出这棵二叉树的逻辑结构图。 8、（6 分）顺序队列如何解决假溢出问题。四、程序填空题（每空 2 分，共 30 分） 1、下面是对顺序存储的有序表进行二分查找的递归算法，请将空格处填上适当语句使得程序完整。 2、下面算法是求有向图中所有顶点入度的算法，请在空格处填入适当的语句。 3、假设用带头结点的单循环链表表示队列，队尾结点指针为 R，下面为非空队列出队的算法，请将算法填写完整。

4、已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树，采用递归算法实现。ppos 和 ipos 分别存放二叉树的前序遍历和中序遍历序列，n 表示结点数五、算法设计题（共 3 题，每题 10 分，共 30 分） 1、已知二叉树的数据结构定义如下，试编写算法计算二叉树中叶子结点的数目。 2、试设计程序∶输入 m 行 n 列整数矩阵 a，若存在 4 个相邻的元素相同，即有∶ a[i][j]=a[i+1][j]=a[i][j+1]=a[i+1][j+1] (1≤i

分享到：

赞收藏

资料库

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

相关推荐

考研

热门标签

最新资料