南京经济学院(10页DOC).docx

……………………………………………………………最新资料推荐…………………………………………………南 京 财 经 大 学2008年攻读硕士学位研究生入学考试（初试）试卷考试科目： 819数据结构与单片机 适用专业： 计算机应用技术 考试时间： 2008年1月20日下午2:00~5:00 注意事项： 所有答案必须写在答题纸上，做在试卷或草稿纸上无效第一部分：数据结构部分试题（本部分共三大题，共计75分）一、简答题（共15题，每题1分，共计15分）1．已知一有向图的邻接表存储结构如下图所示根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列为何？根据有向图的广度优先遍历算法，从顶点v1出发，所得到的顶点序列又为何？2. 如果最常用的操作是取第i个结点及其前驱，则采用单链表、双链表、顺序表还是单循环链表这四种存储方式中的哪一种最节省时间？3. 已知一个图如下图所示，若从顶点a出发，则在以下四种顶点序列中，哪一种是按照深度优先搜索法进行遍历时可能得到的序列？为什么？ A. a, b, e, d, c, f B. a, b, c, e, f, dC. a, e, d, f, c, b D. a, e, b, d, c, f4. 向一个栈顶指针为H的链栈中插入一个s所指的结点时，应该执行什么样的运算？5．试图在一个循环顺序队列中插入一个元素，需要判断该队列是否已满。

问这与队头指针的值还是与队尾指针的值有关？6．数组元素之间的关系是线性的吗？是树形的吗？7．若一个有向图的邻接距阵中对角线以下的元素均为零，则该图是否存在拓扑有序序列？8．采用邻接表存储的图的深度优先遍历算法类似于二叉树的哪种遍历？9. 广义表 (a,b,(c,d)) 的表头、表尾是什么？10. 树最适合用来表示何种数据？11．若广义表A=(a,b,(c,d),(e,(f,g)))，则 head( tail( head( tail( tail( A) ) ) ) ) = ?12. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树问树的先根遍历序列与其对应的二叉树的何种遍历序列相同？13. 在一非空二叉树的中序遍历序列中，根结点的左、右边各有哪些结点？14．在对线性表进行折半查找时，对线性表本身有何要求？15. 一棵二叉树如图所示，其中序遍历的序列为何？二、解析题（共６题，每题6分，共计36分）1．请对下面的无向带权图，写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树2．分别画出和下列树对应的各个二叉树：3．简述以下算法的功能（栈的元素类型SElemType为int）。

Status algo1(Stack S) { int i, n, A[255]; n=0; while(!StackEmpty(S)) {n++; Pop(S, A[n] ) ;} for(i=1; i<=n; i++) Push(S, A[i] ) ;}4．令u = ’abcaabbabcabaacbacba’ ．试分别求出它们的next函数值和nextval函数值5．已知下面的有向图，请给出该图的（1）逆邻接表；（2）强连通分量6．已知下图为广义表存储结构图，其中表结点为 tag=1 | hp | tp ，原子结点结构为 tag=0 | atom 写出如图表示的广义表三、算法题（共3题，每题8分，共计24分）1．假设以两个元素依值递增有序排列的线性表A和B分别表示两个集合（即同一表中的元素值各不相同），现要求另辟空间构成一个线性表C，其元素为A和B中元素的交集，且表C中的元素也依值递增有序排列试对顺序表编写求C的算法2． 编写递归算法，从大到小输出给定二叉树中所有关键字不小于x的数据元素要求算法的时间复杂度为O(log2n+m)，其中n为排序树中所含结点数，m为输出的关键字个数。

3．试写出一趟快速排序（一次划分）的算法即交换顺序表的子表R[low..high]中的记录，使枢轴记录到位，并返回其所在位置，此时在它前面的记录均不大于它，在它后面的记录均不小于它第二部分：单片机部分试题（本部分共五大题，共计75分）四、简答题（共6小题，每小题5分，共30分） 1、80C51系列单片机在片内集成了哪些主要逻辑功能部件?简述各个部件的主要功能?2、80C51单片机RAM和ROM的地址空间分别是多少？访问RAM和ROM的指令有何区别？请举例加以说明 3、80C51单片机的指令周期、机器周期、时钟 (晶体振荡器) 周期的关系如何?当主频为12 MHz时，1个机器周期等于多少µs？执行一条最长的指令需多少µs？　4、80C51单片机内部有几个定时器／计数器? 有几种工作方式? 作定时用时，定时时间与哪些因素有关? 举例说明　5、什么是中断？80C51有几个中断源？其中断入口地址各是多少？ 6、某80C51串行接口，采用帧格式为：一个起始位,八个数据位、一个停止位，其工作方式为哪种？已知每秒钟传送9600个字符，传送波特率是多少五、阅读下列程序段，写出整个程序段的功能（1×9分） MOV A,#55H MOV R0，#20H MOV R1，#4LOOP：MOV ＠R0，A INC R0 CPL A DJNZ R1，LOOP RET六 、编程（1×12分）已知80C51单片机时钟(晶体振荡器)频率为6 MHz，编程使P1.0输出周期为1 ms的方波。

要求用定时器T1、工作方式2定时、中断方式工作，说明其控制字；定时常数七、电路分析（1×12分） 下图为某80C51单片机片外扩展存储器的电路，分析回答：1、 图中芯片A、芯片B分别是程序存储器还是数据存储器2、 芯片A、B的地址范围分别是多少？3、 芯片A、B的存储容量是多少？4、写出芯片A、B的型号八、应用题（1×12分） 下图为某80C51单片机扩展D/A转换器电路，分析回答：1、 写出DAC0832的地址2、 若其参考电压Vre为-5.12V，写出使其输出电压2V的程序段3、 编程使其输出锯齿波最新精品资料整理推荐，更新于二〇二〇年十二月二十七日2020年12月27日星期日11:10:02。