南京经济学院

1、PAGE PAGE 11 第 页 共8页南 京 财 经经 大 学2008年攻读读硕士学位研究生入入学考试（初初试）试卷考试科目： 819数据结结构与单片机机 适用专业： 计算机应用用技术 考试时间： 2008年年1月20日下午2:005:00 注意事项： 所有答案必必须写在答题题纸上，做在在试卷或草稿稿纸上无效。第一部分：数据据结构部分试试题（本部分共三大大题，共计775分）一、简答题（共共15题，每每题1分，共共计15分）1已知一有向向图的邻接表表存储结构如如下图所示。根根据有向图的的深度优先遍遍历算法，从从顶点v1出发，所所得到的顶点点序列为何？根据有向图图的广度优先先遍历算法，从从顶点v

2、1出发，所所得到的顶点点序列又为何何？2. 如果最常常用的操作是是取第i个结结点及其前驱驱，则采用单单链表、双链表、顺序表还是单循环链链表这四种存储方方式中的哪一一种最节省时时间？3. 已知一个个图如下图所所示，若从顶顶点a出发，则在在以下四种顶顶点序列中，哪哪一种是按照照深度优先搜搜索法进行遍遍历时可能得得到的序列？为什么？ A. a, b, e, dd, c, f B. a, bb, c, e, f, dC. a, e, dd, f, c, b D. a, e, bb, d, c, f4. 向一个栈栈顶指针为HH的链栈中插插入一个s所指的结点时，应该该执行什么样的的运算？5试图在一个个循环

3、顺序队队列中插入一一个元素，需需要判断该队列是否已满。问这与队头头指针的值还还是与队尾指指针的值有关关？6数组元素之之间的关系是是线性的吗？是树形的吗吗？7若一个有向向图的邻接距距阵中对角线线以下的元素素均为零，则则该图是否存在拓扑扑有序序列？8采用邻接表表存储的图的的深度优先遍遍历算法类似似于二叉树的的哪种遍历？9. 广义表 (a,b,(c,d) 的表头、表尾尾是什么？10. 树最适适合用来表示示何种数据？11若广义表表A=(a,b,(c,d),(ee,(f,gg)，则则 headd( taiil( heead( ttail( tail( A) ) ) ) ) = ?12. 树的基基本遍历策

4、略略可分为先根根遍历和后根根遍历；二叉叉树的基本遍遍历策略可分分为先序遍历历、中序遍历历和后序遍历历。这里，我我们把由树转转化得到的二二叉树叫做这这棵树对应的的二叉树。问问树的先根遍遍历序列与其其对应的二叉叉树的何种遍遍历序列相同同？13. 在一非非空二叉树的的中序遍历序序列中，根结结点的左、右右边各有哪些些结点？14在对线性性表进行折半半查找时，对对线性表本身身有何要求？15. 一棵二二叉树如图所所示，其中序序遍历的序列列为何？二、解析题（共共题，每题题6分，共计计36分）1请对下面的的无向带权图图，写出它的的邻接表，并并按克鲁斯卡卡尔算法求其其最小生成树树。2分别画出和和下列树对应应的各个

5、二叉叉树：3简述以下算算法的功能（栈栈的元素类型型SElemmType为为int）。Status algo11(Stacck S) int ii, n, A2555; n=0; whilee(!StaackEmppty(S) n+; Pop(S, An ) ; for(ii=1; ii=n; i+) Push(S, Ai ) ;4令u = abcaaabbabbcabaaacbacbba 试分别求求出它们的nnext函数数值和nexxtval函函数值。5已知下面的的有向图，请请给出该图的的（1）逆邻接表表；（2）强连通分分量。6已知下图为为广义表存储储结构图，其其中表结点为为 tag=1 |

6、hhp | ttp ，原子结点点结构为 ttag=0 | atoom 。写出出如图表示的的广义表。三、算法题（共共3题，每题题8分，共计计24分）1假设以两个个元素依值递递增有序排列列的线性表AA和B分别表示两两个集合（即即同一表中的的元素值各不不相同），现现要求另辟空空间构成一个个线性表C，其元素为为A和B中元素的交交集，且表CC中的元素也也依值递增有有序排列。试试对顺序表编编写求C的算法。2 编写递归归算法，从大大到小输出给给定二叉树中中所有关键字字不小于x的的数据元素。要要求算法的时时间复杂度为为O(logg2n+m)，其其中n为排序序树中所含结结点数，m为为输出的关键键字个数。3试写出

7、一趟趟快速排序（一一次划分）的的算法。即交交换顺序表的的子表Rllow.highh中的记录录，使枢轴记记录到位，并并返回其所在在位置，此时时在它前面的的记录均不大大于它，在它它后面的记录录均不小于它它。第二部分：单片片机部分试题题（本部分共五大大题，共计775分）四、简答题（共共6小题，每每小题5分，共共30分） 1、80CC51系列单单片机在片内内集成了哪些些主要逻辑功功能部件?简简述各个部件件的主要功能能?2、80C511单片机RAAM和ROMM的地址空间间分别是多少少？访问RAAM和ROMM的指令有何何区别？请举举例加以说明明。 3、80CC51单片机机的指令周期期、机器周期期、时钟 (

8、晶体振荡器器) 周期的关系系如何?当主主频为12 MHz时，11个机器周期期等于多少s？执行一一条最长的指指令需多少s？4、80C551单片机内内部有几个定定时器计数数器? 有几几种工作方式式? 作定时时用时，定时时间与与哪些因素有有关? 举例例说明。5、什么是中中断？80C51有有几个中断源源？其中断入入口地址各是是多少？ 6、某800C51串行接口口，采用帧格式为：一一个起始位,八个数据位、一个个停止位，其工作方方式为哪种？已知每秒钟传送96000个字符，传送送波特率是多多少。五、阅读下列程程序段，写出出整个程序段段的功能（119分） MOV A,#555H MOV R00，#20H MOV R1，#4LOOP：MOOV R0，A INC R0 CPL A DJNZZ R1，LOOPP RET六 、编程（1112分）已知80C511单片机时钟钟(晶体振荡器器)频率为66 MHz，编程使P1.0输出周期为1 ms的方波。要求用定时器T1、工作方式2定时、中断方式工作，说明其控制字；定时常数。七、电路分析（1112分） 下图为为某80C51单单片机片外扩扩展存储器的的电路，分析析回答：图中芯片A、芯芯片B分别是是程序存储器器还是数据存存储器。芯片A、B的地地址范围分别别是多少？芯