分别常用的基本技术和手段。〔8分〕
六、〔共10分〕假设数据库中数据项A、B和C的初值均为100。现有两个事务T1和T2，分别包含如下操作：事务T1：yReadCxReadAxxyWriteAx〔即，读数据库中数据项C的值并赋给变量y；读数据库中数据项A的值并赋给变量x；变量x的值与变量y的值相加的结果赋给变量x；将变量x的值写到数据库中数据项A中；〕事务T2：vReadCuReadBuuvWriteAu
下面是利用锁机制来实现事务T1、T2的一个并发调度S：
T1
T2
SlockC
2
fSlockC
vReadC
U
lockC
SlockB
yReadC
U
lockC
SlockA
uReadB
U
lockB
uuv
XlockA
xReadA
等待
U
lockA
等待
WriteAu〔获得排它锁，并实现写〕
xxy
XlockA
等待
U
lockA
〔获得排它锁，并实现写〕WriteAx
完成以下解答：
U
lockA
1、调度S是否是可串行化调度？为什么？〔4分〕
2、利用锁机制给出关于事务T1、T2的一个可串行化并发调度S′不能是串行调度，使它与串行调度T1→T2的执行结果等价。并说明等价的理由。〔6分〕
3
f第二部分：数据结构
一、概念题〔每题3分，共9分〕
1、栈2、二叉排序树3、存储结构
二、简答题每题10分，共20分
1、用类C描述语言定义稀疏矩阵的三元组存储结构，并写出以下矩阵的存储表示。
005000
020000
0018000M000090
080000


000010
2、假设有一个待排序的无序序列为：｛4938659776132749｝，现用堆排序方法对其排序，请图示初始堆的建立过程。
三、算法填空题〔每空3分，共30分〕
1、在以下算法中填上适当的类C程序设计语言语句，使之实现求矩阵M的转置矩阵T的功能。其中：矩阵用三元组表示，mu为矩阵行数、
u为矩阵列数，tu为矩阵非零个数，三元组ije表示矩阵第i行第j列的值为e。StatusTra
sposeSMatrixTSMatrixMTSMatrixT______________1_____________ifTtuforcol1colM
ucol
umcol0fort1tM
ut
um________2______cpot11forcol2colM
ucol_______________3___________forp1_______4_____pcolMdatapjqcpotcolTdataqiMdatapjTdataqjMdatapiTdataqeMdatape_________5___________forifretur
OKTra
sposeSMatrix
4
f2、完成以下算法，使之实现功能：给有向无环图G中每个顶点赋以一个自然数序号，并满足以下条件：假设从顶点i至顶点j有一条弧，则应使ij。注释：有向图的存储结构为邻接表，且在头结点中增加二个数组：一个存放顶点入度的数组〔i
degree〕，一个存放本算法生成的顶点序号No。另设一栈S暂存所有入度为零的顶点r