全国计算机等级考试四级教程——高效SRS系统设计解析

"全国计算机等级考试四级教程——数据库工程师习题参考答案" 在设计一个学生试卷成绩输入、查询和成绩单输出系统(SRS)时，主要考虑的是数据结构的选择和高效的操作算法。根据题目描述，系统需要支持学号、姓名、课程名和成绩的数据录入，以及高效的查询和输出功能。 (1) 数据结构设计（15分） ① Pascal语句描述： 首先定义两个记录类型，一个用于表示试卷成绩(pnode)，包含课程名(cname)、成绩(score)和指向下一个试卷成绩的指针(next)。另一个记录类型(snode)用于表示学生，包含学号(sno)、姓名(sname)以及双向链表链接(llink, rlink)和指向试卷成绩链表的指针(plink)。变量t作为二叉排序树的根节点。 ```pascal TYPE pptr = ^pnode; pnode = RECORD cname: string; score: 0..100; next: pptr; END; sptr = ^snode; snode = RECORD sno: integer; sname: string; llink, rlink: sptr; plink: pptr; END; VAR t: sptr; ``` ② 数据结构示意图： 在示意图中，每个学生节点(snode)包含学号、姓名，以及指向左孩子、右孩子和试卷链表的指针。试卷成绩节点(pnode)按照课程名排序，链接在一起形成链表，而所有学生节点则按照学号构成二叉排序树。 ③ 简单文字说明： 学生信息以二叉排序树的形式存储，便于快速查找。每个学生节点包含一个指向其所有试卷成绩的链表，链表中的试卷成绩按课程名排序。这样，插入新的试卷成绩时可以快速定位，查询学生成绩时也能高效地遍历。 (2) 算法要点（10分） ① 试卷成绩插入： 在二叉排序树中插入学生节点，然后在对应的试卷链表尾部插入新的试卷成绩。由于二叉排序树的特性，插入操作的时间复杂度接近O(log n)。 ② 学生成绩查询： 通过二叉搜索找到学生节点，然后遍历其试卷链表，查找对应课程的成绩。查询时间复杂度为O(log n + k)，n是学生数量，k是学生选修的课程数。 ③ 成绩单输出： 遍历二叉排序树，按学号递增顺序输出学生信息及所有课程成绩。时间复杂度为O(n)。 (3) 设计理由（5分）： 这种设计充分利用了二叉排序树的特性，使得插入、查询和输出操作高效。二叉排序树在大多数情况下保持平衡，因此查找速度快。同时，通过链表连接试卷成绩，方便按课程名排序和查找。整体上，这种设计在保证操作效率的同时，也确保了数据的有序性，满足了系统的需求。