1、淮北师范大学2013年硕士研究生入学考试试题(A)科目名称：软件工程学科专业基础综合 科目代码：871适用专业：软件工程 说明：答案必须写在答题纸上，写在本考题纸上的无效。-一、简答题（本题共4小题，满分30分）1.（8分）对图进行遍历可以得到不同的遍历序列，那么导致得到的遍历序列不唯一的因素有哪些？2.（7分）Hash方法的平均查找长度决定于什么？处理冲突的方法主要有哪些？3.（7分）为什么说处理机调度算法中的高响应比优先调度算法是一种较好的折衷算法？4.（8分）简述直接存储器访问（DMA）I/O控制方式的特点。二、解答题（本题共5小题，满分60分）1.（10分）假设用于通信的电文仅由a，b
2、，c，d，e，f，g，h等8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。2.（10分）将关键字序列Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec中的数依次插入到一棵空的平衡二叉树中，试构造相应的平衡二叉树（以字母字典序构造），并求在等概率情况下查找成功的平均查找长度。3.（10分）设初始序列为503，87，512，61，908，170，897，275，653，462，请写出采用快速排序法对该序列作升序排序时的每一趟的结果。4.（15分）在一个
3、请求分页系统中，采用LRU页面置换算法时，假设作业的页面访问顺序为5、4、3、2、3、4、1、2、1、5、4、2、3、4，试画出分配给该作业的物理块分别为3和4时的页面置换图并求出相应的缺页次数和缺页率。5.（15分）设系统中有4个进程P0，P1，P2，P3和三类资源A，B，C，在T0时刻的资源分配情况如下表所示。利用银行家算法分析并回答以下问题：（1）该状态是否安全？（2）若进程P0提出请求Request(1,0,1)后，系统能否将资源分配给它？ProcessAllocation A B CNeed A B CAvailable A B CP02 0 11 2 12 1 2P11 0 12
4、0 2P20 1 11 0 3P30 0 24 2 0三、算法分析与设计（本题共4小题，满分60分）1.（15分）正整数n若是它平方数的尾部，则称n为同构数。例如，6是其平方数36的尾部，76是其平方数5776的尾部，6和76都是同构数。试用C语言编程求出100以内的所有同构数。2.（15分）用C语言编程实现：从键盘输入一个字符串，删除该字符串中的数字字符。3.（15分）已知二叉树采用如下二叉链表储存结构，设计一个算法把二叉树BT的左、右子树进行交换。算法描述的函数原型为：void BTreeExchangeChild(BiTree BT)。二叉树的二叉链表储存结构：typedef struct TNode int data; struct TNode *lchild, *rchild; BiTNode, *BiTree;4.（15分）桌子上有一个盘子，可以存放一个水果，父亲总是放苹果到盘子中，而母亲总是放香蕉到盘子中，一个儿子专等吃盘中的香蕉，而一个女儿专等吃盘中的苹果。请利用信号量机制写出对父亲、母亲、儿子、女儿进行描述的算法。-淮北师范大学2013年硕士研究生入学考试试题纸 第 2 页 共 2 页
