2018年南京师范大学地理科学学院635C语言程序设计(含数据结构)之数据结构考研核心题库
● 摘要
一、综合题
1． 画出对算术表达式表所示。
表 操作数栈和运算符栈的变化过程
F 求值时操作数栈和运算符栈的变化过程。
F 求值，过程如
【答案】设操作数栈是opnd ，运算符栈是optt ，对算术表达式
2． 在各种排序方法中，哪些是稳定的? 哪些是不稳定的? 并为每一种不稳定的排序方法举出一个不稳定的实例。
【答案】各种排序算法稳定性的归纳如图所示:
图各种排序算法稳定性归纳
3． s 是字符数组，s[0]中存放的是该字符串的有效长度，假设S[l..7]中字符串的内容为〃abcabaa" ，说明下列程序的功能及执行结果。
（ ）
【答案】本程序的功能是求字符串的nextval 函数，程序执行结果是0110132。
4． 设度为m 的树采用多重链表存储。每个结点有m+1个域，其中有1个数据域，m 个指向孩子的指针。则空指针的数目是多少? 说明这种存储方式的利弊。
【答案】(1)空指针数目:n(n>0)个结点的m 度树共有nm 个链域，除根结点外，每个结点均有一个指针所指，故该树的空链域有
+1个。
(2)利弊:这种存储结构统一，便于处理但空链域造成存储效率低。
5． 设依以下次序给出关键字:34，16，19，21，5，49，24，62，3，17，45，8，构造3阶B-树。要求从空树开始，每插入一个关键字，画出一棵树。
【答案】如图所示:
图
6． 某博物馆最多可容纳500人同时参观, 有一个出入口, 该出入口一次仅允许个通过。参观者的活动描述如下:
Cobegin
参观者进程i : {
进门; 参观;
出门; } coend
请添加必要的信号量和P 、V(或wait （ ）、signal （ ）) 操作, 以实现上述操作过程中的互斥与同步。要求写出完整的过程, 说明信号量含义并赋初值。
【答案】定义两个信号量
博物馆可以容纳的最多人数
用于出入口资源的控制
相关内容
相关标签