《公共基础补充内容》由会员分享，可在线阅读，更多相关《公共基础补充内容（53页珍藏版）》请在金锄头文库上搜索。
1、87654321初始状态为空，rear=front=88X7F6E5D4C3B2A1元素 B、C、D、E、F、X 先后入队可用上图代替教材图 1.14，这样会 更第一章数据结构与算法 循环队列入队、出队运算示意循环队列入队、出队运算示意 图图元素 M、A 先后入队后情况元素 Y 入队后,rear=front=1,队 满容易理解循环队列的运算。排头元素 M 退队 后情况排头元素 A 退队后情况 元素 M 入队时，应存储在 9#存8765432A1M8X7F6E5D4C3B2A1Y8765432A18X7F6E5D4C3B21Yrear frontfrontfrontfrontfrontfront
2、rearrearrearrearrear储单元中，即 rear=9，但这超过了 队列的长度 8，所以在 rear=9=8+1 时，应置 rear=1，最终元素 M 存储 在了 1#存储单元中。参见 P8，循环 队列的入队运算有关描述。P2：直接递归：P=P+1 间接递归：P=Q+2 Q=P+3减半递推：为求在(a,b)间函数 f(X)与横轴的交点，可取 a、b的中点坐标，求出 f()来，可看到 f(2ba2ba)与 f(b)同号，从而可以将,b舍掉2ba2ba(问题规模减半,问题性质未变)，接下来可在(a,)间重复上述操作(递推),直到足够逼近所2ba求为止。P4： 一般来讲，同一种逻辑结构可
3、采用不同的存储 （物理）结构；反之，同一种存储（物理）结构可用于abf(a)f(b)f()2ba2ba实现不同的逻辑结构。有序表：后件不大于前件P5：线性表示意图（a1，a2，.，ai，.，an）a1a2.ai.anP5 上半页资料原话“线性结构又称线性表”，这里的“线性表”代指了所有“线性结构” 。可同一页的下半页，又提到了一个非空线性结构具备了列举出的三个特征，才能被叫做“线性表” ，也就是在这里， “线性表”是指一种特殊的线性结构。这样， “线性表”这个概念有了广义和狭义之分，大家今后在阅读此资料时请仔细分辨，资料中后面再提“线性表” ，一般是指狭义概念，是指符合列举出的三个特征的一种特
4、殊的线性结构。“一年四季”逻辑结构的“顺序存储”示意图：10241025 10261027 10281029 1030 1031春夏秋冬首行为“存储单元地址”,第二行为“存储内容”建议补充在 P4 图 1.2 处,该图为“一年四季”的逻辑结构示意图。P5P6:对顺序存储的长度为 n 的线性表插入与删除有：平均性态均为： n/2，即平均移动 n/2 个元素最坏情况复杂性均为：n,即最多移动 n 个元素入栈、退栈演示图10 9 8 7 6F 5E 4D 3C 2B 1A栈中元素数 n= top -bottom+1体会为什么要+1bottomtop1.一个栈的初始状态为空。现将元素1、2、3、4、5
5、、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是_。A、12345ABCDEB、EDCBA54321C、ABCDE12345D、54321EDCBA体会栈是“后进先出”或“先进后出”表。2.假设用一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有_个元素。n= top -bottom+1=30-49+1=20非循环队列入队、退队演示图 8 7 6 E 5 D 4 C 3 2 1front rearrear非循环队列的元素数 n= rear-f
6、ront循环队列入、退队操作演示8 7 6 5 4 3 2 1初始状态为空，rear=front=8元素 M、A 先后入队后情况元素 M 入队时，应存储在 9#存储单元中，rearrearfront即 rear=9，但这超过了队列的长度 8，所以在rear=9=8+1 时，应置 rear=1，最终元素 M 存储在了 1#存储单元中。参见 P8，循环队列的入队运算有关描述。排头元素 M 退队后情况元素 B、C、D、E、F、X 先后入队元素 Y 入队后,rear=front=1,队满排头元素 A 退队后情况以上各步将在授课时逐一加以动态演示。各步的阶段效果图，请详见本资料的第一页，课下可反复对照琢
7、磨。假设某循环队列，初始状态为空(即 s=0)时，front=rear=m(即队列的长度为 m)，队尾指针为rear，排头指针为 front，则该循环队列某时刻所包含的元素个数 n 为：rear-front , rearfront 时n= m(s=1 时)或 0(s=0 时) , front=rear 时m+(rear-front) , rearfront时 n=29-5=242.设某循环队列的容量为50，如果头指针front=45（指向队头元素的前一位置），尾指针rear=10（指向队尾元素），则该循环队列中共有_个元素。n= m+(rear-front) , rear70(选课成绩)请注意
8、 与 不能同时为常量，如下表达式是错误的： 9070(选课成绩)实际上，学过查询的就会马上意识到，上述表达式中缺少必要的字段名，从而投影运算无法进行。笛卡尔积运算举例： R ST=RS ABCDE 124m8 124hk 124ty 135m8 135hk 135tyABC124135DEm8hkty交运算举例：R S T=RSABCD 1234ABCD 1234 2257 9038ABCD 2238 1234 9123三个除法：RS T=R/ST=R/S：在 R 中寻找与 S 中的3，4 、5，6均组合过的 A、B 两列的值，这些值就是 T 中的内容。ABCD 1234 7856 7834
9、1256 1242CD 34 56AB 12 78RS T=R/ST=R/S：在 R 中寻找与 S 中的3，4组合过的 A、B 两列的值，这些值就是 T 中的内容。ABCD 1234 7856 7834 1256 1242CD 34AB 12 78RS T=R/S T=R/S：在 R 中寻找与 S 中的3，4 、 5，6 、4，2均组合过的 A、B 两列的值，这些值就是 T 中的内容。ABCD 1234 7856 7834 1256 1242CD 34 56 42AB 12连接与自然连接举例：R ST1=RS (大于连接)ED|ABCDEF 123418 321818 321879 32185
10、2T2=RS (等值连接)ED|ABCDEF 732118EF 18 79 52ABCD 1234 3218 7321R ST=R|ST=R|S (自然连接:公共域上的等值连接)ABCDE 24264 24268 11473请注意此处的“公共域”是指：类型和取值范 围都相同的属性(字段)。并不要求属性(字段)名一 定要相同 注：此公共基础资料，在“关系代数”这 里，漏讲了“并”和“差”两种运算。好在VF教材 第一章中已经讲过，学VF的诸位可以复习VF教材第 一章中相关内容。建议在公共基础资料上注明 这一点，以防以后复习时会漏掉这个知识点。DE 51 64 73 68ABCD 1234 1583
11、 2426 11471.有三个关系R、S和T如下： 则由关系R和S得到关系T的操作是_。 A)自然连接 B)交 C)除 D)并 2.有三个关系R、S和T如下：则由关系R和S得到关系T的操作是_。A、自然连接 B、交 C、投影 D、并3.有两个关系R和T如下：则由关系R得到关系T的操作是_。A、选择 B、投影 C、交 D、并4.有三个关系R，S和T如下：其中关系T由关系R和S通过某种操作得到，该操作为_。A、选择 B、投影 C、交 D、并5.有两个关系R，S如下：R S由关系R通过运算得到关系S，则所使用的运算_。A、选择 B、投影 C、插入 D、连接6.有三个关系R、S和T如下：由关系R和S通
12、过运算得到关系T，则所使用的运算为_。A、并 B、自然连接 C、笛卡尔积 D、交7.有三个关系R、S和T如下：R S T则由关系R和S得到关系T的操作是 。A)自然连接 B)差C)交D)并补充原教材表 4.10E-R 模型与关系间的比较表E-R 模型关系属性属性实体元组实体集关系ABC a12 b21 c31ABC a12 b21ABC c31联系关系1.数据库应用系统中的核心问题是_。A、数据库设计 B、数据库系统设计C、数据库维护 D、数据库管理员培训2.数据库设计中，用E-R图来描述信息结构但不涉及信息在计算机中的表示，它属于数据库设计的_。A、需求分析阶段 B、逻辑设计阶段C、概念设计阶段 D、物理设计阶段3. 在数据库设计中，将E-R图转换成关系数据模型的过程属于_。A、需求分析阶段 B、概念设计阶段C、逻辑设计阶段 D、物理设计阶段4. 将E-R图转换为关系模式时，实体和联系都可以表示为_。A、属性 B、键 C、关系 D、域5. 下列关于数据库设计的叙述中，正确是的A)在需求分析阶段建立数据字典B)在概念设计阶段建立数据字典C)在逻辑设计阶段建立数据字典D)在物理设计阶段建立数据字典群号：146047818 群名：2013 二级 VF 验证信息：一、四晚 1404二、五晚 1308三晚、四下 1308 验证信息三选一，据实填写。
