武汉科技大学软件基础Ⅰ_含数据结构和计算机组成原理_2009考研试题研究生入学考试试题考研真题
● 摘要
二 O O 九年招收硕士研究生入学考试试题 考试科目及代码： 数据结构（代码：821） 适用专业： 材料加工工程 答题内容写在答题纸上，写在试卷或草稿纸上一律无效考完后试题随答题纸交回。 考试时间 3 小时，总分值 150 分。 一、填空题（每空 1.5 分，共 15 分） 准考证号码： 1、某二叉树的先序和后序序列正好相反，则该二叉树一定是 （1） 的二叉树。 2、 对二叉树从 1 开始进行连续编号， 要求每个结点的编号大于其左右孩子的编号， 同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用 （2） 密 封 线 内 不 要 写 题 次序的遍历实现编号。 （3） 条弧。 （4） （5） 。 （6） 。 。 3、N 个顶点的有向完全图具有 4、N 个元素的顺序查找的平均查找长度为 5、N 个结点的完全二叉树，其深度为 6、二叉树的叶子结点 n0 与度为 2 的结点数 n2 的关系是 深度为 （7） 。 （8） 。 7、将有关二叉树的概念推广到三叉树，那么，一颗有 244 个结点的完全三叉树的 8、快速排序的时间复杂度为 报考学科、专业： 9、 在做进栈操作时应判别栈是否 （9） 。 出栈操作时应判别栈是否 （10） 。 二、判断题（每题 1.5 分，共 15 分） 1、折半查找方法要求待查表必须是顺序存储结构的有序表。 2、从循环单链表的任一结点出发，不一定能找到表中所有结点。 3、栈是一种先进先出的线性表。 4、串是一个或多个字符组成的有限序列。 5、完全二叉树的叶子结点只可能在层次最大的一层上出现。 6、快速排序算法是稳定的排序，而 shell 排序是不稳定的。 7、在数据结构中，数据的存储结构与所使用的计算机无关。 8、一个广义表的表尾总是一个广义表。 9、当两个字符出现的频率相同时，则其哈夫曼编码也相同。 10、如果某种排序算法是不稳定的，则该算法是没有实际意义的。 第 1 页 共 4 页 姓名：
三、综合应用题（60 分）
1、 （6 分）证明在一棵满二叉树中分支 B 与叶子节点 n0 满足关系 B=2(n0-1)。 2、 （12 分）已知关键字序列为： （75，33，52，41，12，88，66，27） ，哈希表长 为１０，哈希函数为：Ｈ（ｋ）＝ｋＭＯＤ７，解决冲突用线性探测再散列法， 要求构造哈希表，求出等概率下查找成功的平均查找长度。 3、 （12 分）已知有向图 G，顶点集为 V(G)={a，b，c，d，e}，关系集为 E(G)={
四、程序填空题（每空 2 分，共 30 分）
1、 下面是对顺序存储的有序表进行二分查找的递归算法， 请将空格处填上适当语 句使得程序完整。 int Binsch( ElemType A[ ],int low ,int high,KeyType K ) { if (low <= high) { int mid =___（1）_____ if ( K= = A[ mid ].key ) else if ( K < A[mid].key) else } else } 2、下面算法是求有向图中所有顶点入度的算法，请在空格处填入适当的语句。 void FindIndegree(ALGraph { For(i=0;i
4、 已知某二叉树的前序遍历和中序遍历序列， 生成一棵用二叉链表表示的二叉树， 采用递归算法实现。ppos 和 ipos 分别存放二叉树的前序遍历和中序遍历序列，n 表示结点数 TNODE *restore(char *ppos,char *ipos,int n) { TNODE *ptr； char *rpos; int k; if(n<=0) return NULL; ptr->data=___（10）_____; for(___（11）_____; rpos
相关内容
相关标签