2008 年江苏南京财经大学数据结构与单片机考研真题
第一部分:数据结构部分试题
(本部分共三大题,共计 75 分)
一、简答题(共 15 题,每题 1 分,共计 15 分)
1.已知一有向图的邻接表存储结构如下图所示。根据有向图的深度优先遍历算法,从顶
点 v1 出发,所得到的顶点序列为何?根据有向图的广度优先遍历算法,从顶点 v1 出
发,所得到的顶点序列又为何?
2. 如果最常用的操作是取第 i 个结点及其前驱,则采用单链表、双链表、顺序表还是单
循环链表这四种存储方式中的哪一种最节省时间?
3. 已知一个图如下图所示,若从顶点 a 出发,则在以下四种顶点序列中,哪一种是按照
深度优先搜索法进行遍历时可能得到的序列?为什么?
A. a,
b,
e,
d,
c,
C. a,
e,
d,
f,
c,
f
b
B. a,
b,
c,
e,
f,
D. a,
e,
b,
d,
c,
d
f
4. 向一个栈顶指针为 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题,每题 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,#4
LOOP: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、 编程使其输出锯齿波。