作业1：线性表
1．设A是一个线性表（al，a2，?,an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？请说明理由和计算方法。 【解答】若考虑在最后一个元素后插入元素的情况，可知共有n+1种元素插入情况：插入元素到ai之前（1≤i≤n）需要移动的元素个数为n-i+1，插入到最后一个元素an之后需要移动的元素个数为0。因此，在等概率的前提下，平均每插入一个元素需要移动的元素个数为
?n?1?n??(n?i?1)?/(n?1)?2 ?i?1?说明：若可能的插入位置为n（即不考虑在最后一个元素后插入元素的情况），
则平均移动元素个数为
?n?n?1??(n?i?1)?/n?2 ?i?1?
2．For singly linked list and doubly linked list, which one can visit all nodes from an arbitrary node? Please explain the reason.
【解答】单链表结点中只有指向后继结点的指针，因此单链表只能沿后继方向访问结点，即只能由当前结点出发访问其后的任一结点，而不能从当前结点出发访问到该结点的前驱结点；双向链表结点中既有指向后继结点的指针，也有指向前驱结点的指针，因此双向链表即可沿后继方向也可沿前驱方向访问结点，所以双向链表可以从任意结点出发访问表中其它任一结点。
Answer: For a singly linked list, every node contains only one pointer which points to its next node, so we can only visit nodes in a backward direction. That is to say, from an arbitrary node in a singly linked list, we can only visit those nodes behind it and can’t visit those nodes ahead of it. For a doubly linked list, every node contains two pointers which point to its previous and next nodes respectively, so we can visit nodes in forward and backward directions. That is to say, we can visit all nodes from an arbitrary node in a doubly linked list.
作业2：栈和队列
1．有 5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素C第一个出栈，D第二个出栈的次序有哪几个？
【解答】按照栈的特点可知，元素C第一个出栈、D第二个出栈时A、B已分别进栈且仍在栈中（栈底元素为A，栈顶元素为B），而E尚未进栈。则根据栈的LIFO特点以及元素E可能的进栈时机，可以推导出以元素C第一个出栈、D第二个出栈的次序有CDEBA 、CDBAE 和CDBEA 3种。
2．Provided that the input sequence for a stack S is a, b, c, d, analyze whether the following two sequences could be obtained by the operations of pop and push of stack. If it could, write out the operation sequence; otherwise, explain the reason. （1）cdba （2）dbca 【解答】
（1）可以实现。操作序列为：
a入栈，b入栈，c入栈，c出栈，d入栈，d出栈，b出栈，a出栈。 （2）不能实现，因为若d为最先出栈的元素，则d进栈前a、b、c已入栈且c为栈顶元素、a为栈底元素。由栈的特点可知，此时出栈序列只能为dcba。
(1)Yes, it could be obtained. The operation sequence is shown as follows:
push a, push b, push c, pop , push d, pop, pop, pop
(2)No, it couldn’t be obtained. If d is the first element popped off, then a, b, c should be already pushed into the stack before d was pushed into stack, where c is the top element and a is the bottom element in the stack. So, the output sequence can only be dcba.
作业3：树和二叉树
1．某二叉树的中序序列为：ABCEFGHD；后序序列为：ABFHGEDC； （1）请画出此二叉树，并写出其前序序列。
（2）请画出该二叉树的顺序存储和链式存储（二叉链表）结构图。 【解答】
（1）根据后序序列知根结点为C，所以左子树：中序序列为AB，后序序列为AB；右子树：中序序列为EFGHD，后序序列为FHGED，以此类推得该二叉树结构如图所示。
图 二叉树示意图
?
注意：此类题的解法是先根据后序序列找到根结点，然后分别得到左右子树的中序序列和后序序列，如此类推。
易得前序序列为CBADEGFH。
（2）顺序存储结构（数组结构）：注意结点编号应和数组下标正确对应（数组下标从0开始或从1开始均可）。
C B D A E G F H 1 2 3 4 6 13 26 27
链式存储结构（二叉链表）：
2．对于n个结点的完全二叉树，用1到n的连续整数顺序编号，试回答下列问题：
（1）它共有多少层？各层的结点数分别是多少？
（2）各层最左边的结点的编号分别是多少？各层最右边的结点的编号分别是多少？
（3）对于编号为i（1≤i≤n）的结点，它所在的层是多少？它的双亲（若存在的话）的编号是多少？它的左孩子（若存在的话）和右孩子（若存在的话）的编号分别是多少？ 【解答】
（1）该二叉树的层数：k＝[Log2n]+1；第i层的结点数有两种情况:
2i?1,1?i?k;n?[2i?1?1],i?k 最后一层(即第k层))的结点数的计算：结点总数n减去1～(k-1)
k?12?1）层的结点总数（！ （2）除最后一层外，每一层最右边的结点编号为该层以上所有层的结点的总数。因此，第i层（1≦i≦k－1）最右边的结点编号为2?1，而最后一层最右边的结点编号即n。即最右边结点的编号为：
i2i?1,1?i?k n,i?k除第一层外，每一层最左边的结点编号为其上一层最右边结点编号加1，故第i层最左边的结点的编号为2(1?i?k)。
（3）该结点所在的层为[Log2i]?1（直接利用1结论），其双亲（若存在的话）的编号为[i/2]，左孩子（若存在的话）的编号为2i，右孩子（若存在的话）的编号为2i+1。
i?1作业4：查找与排序
1．Construct the binary sort tree with the sequence of {23，13，5，28，14，25}，and calculate its Average Search Length (ASL).
【Answer】We can construct the binary sort tree step by step as shown in Figure 1:
Figure 1 Process of Constructing the Binary Sort Tree
The ASL of the resulted binary sort tree is
ASL=(1+2+3+3+2+3)/6=14/6≈2.3
2．对有序表（4，9，14，23，55，68，79，84）进行折半查找，若要查找值为14的元素，则将依次与哪些元素进行比较？若要查找值为80的元素，则又将依次与哪些元素进行比较？
【解答】设关键字从数组下标为1的数组单元开始存放，如下：
4 9 14 23 55 68 79 84 数组下标：1 2 3 4 5 6 7 8 查找值为x=14的元素时： （1）low＝1，high＝8，得mid＝4，由key[mid]＝23>x，修改high＝mid－1＝3； （2）low＝1，high＝3，得mid＝2，由key[mid]＝9 因此，查找14时，将依次与元素23、9和14比较。 查找值为80的元素时： （1）low＝1，high＝8，得mid＝4，由key[mid]＝23 因此，查找80时，将依次与元素23、68、79和84比较。 说明：（1）数组下标也可以从0开始；（2）在计算mid=(low+high)/2时，mid值也可以向上取整（前面计算过程是向下取整的）。 3．Given a sequence of keys of (2, 8, 28, 4, 10, 20)，write out each sequence of keys after each time of sorting the sequence under the following sort methods: （1）bubble sort；（2）selection sort；（3）insertion sort；（4）quick sort 【解答】 （1）冒泡排序（排序遍数：一直到某一遍排序没有出现数据交换时停止） 初始：2，8，28，4，10，20 第1遍：2，8，4，10，20，28 第2遍：2，4，8，10，20，28 第3遍：2，4，8，10，20，28（同第2遍结果） （2）简单选择排序（排序遍数：n－1遍，n为关键字个数） 初始：2，8，28，4，10，20 第1遍：2，（8，28，4，10，20） 选中2，由于本身处于目标位置，无需交换 第2遍：2，4，（28，8，10，20） 选中2，与元素8进行位置交换 第3遍：2，4，8，（28，10，20） 选中8，与元素28进行位置交换 第4遍：2，4，8，10，（28，20） 选中10，与元素28进行位置交换 第5遍：2，4，8，10，20，28） 选中20，与元素28进行位置交换 （3）直接插入排序（排序遍数：n－1遍，n为关键字个数） 初始：2，8，28，4，10，20 第1遍：2，8，28，4，10，20 插入元素8 第2遍：2，8，28，4，10，20 插入元素28 第3遍：2，4，8，28，10，20 插入元素4 第4遍：2，4，8，10，28，20 插入元素10 第5遍：2，4，8，10，20，28 插入元素20 （4）快速排序（排序遍数：一直到每个划分出来的区域都只有一个元素为止） 若始终取排序区域的首元素作为枢轴，则有（括号内为每次快速排序后划分出来的新的排序区域）： 初始：2，8，28，4，10，20 第1遍：2，（8，28，4，10，20） 对2，8，28，4，10，20进行快速排序 第2遍：2，(4) ，8，(28，10，20) 对（8，28，4，10，20）进行快速排序 第3遍：2，4，8，（20，10），28 对（28，10，20）进行快速排序 第4遍：2，4，8，10，20，28 对（20，10）进行快速排序 作业5：进程及进程管理 1．三个并发进程共用一个公共变量Q，写出用信号灯实现这三个进程互斥时的程序描述（用结构化的程序设计语言，例如用类C、类Pascal等描述），并说明信号灯的取值范围和意义。 【解答】设这三个进程分别为A、B、C，其访问公共变量Q的三个临界区分别为SA，SB和SC。信号灯mutex初值为1，表示没有进程访问变量Q。则实现这三个进程互斥的程序如下： main() A() B() { ? P(mutex); SA； V(mutex); ? P(mutex); SB； V(mutex); ? } C() { ? P(mutex); SC； V(mutex); ? } {int mutex=1; { cobegin A;B;C; coend } } ? 信号灯mutex可能取值及其意义如下： mutext＝1：无进程访问变量Q； mutext＝0：有一个进程在访问变量Q； mutext＝－1：有一个进程在访问变量Q，有一进程等待访问Q； mutext＝－2：有一个进程在访问变量Q，有两个进程等待访问Q； 2．设一输入进程get和一输出进程put共用一个缓冲区buf（缓冲区大小为每次存放一个数据）。其中，get进程负责不断地计算数据并送入缓冲区，put进程负责从缓冲区取出数据去打印。试用信号灯的P、V操作实现这两个进程的同步，并写出程序描述。 【解答】：设信号灯pa、pb分别表示缓冲区有无空位置和缓冲区有无可供打印的数据，初值分别为1和0。则实现进程同步的程序如下： Main() { pa=1;pb=0; cobegin get; put； coend } get() { while(计算未完成) {计算得到一数据； P（pa）; 数据送入缓冲区； V（pb）；} } put() { while(打印未完成) {P（pb）; 从缓冲区读取数据； V（pa）； 打印该数据；} } 作业6：操作系统资源管理 1．在右图所示的主存中（阴影部分为空闲区）： （1）请分别画出在首次适应算法和最佳适应算法下的自由 主存队列结构。 （2）假设有一个35K字节的作业要求分配主存空间，则在 上述两种分配策略下该作业分别放在哪一个空闲区？ （1）首次适应算法下的自由主存队列为： 25K 0 30K 100K 0 60K 180K 0 40K 自由主存队 列头指针 ^ 最佳适应算法下的自由主存队列为： 自由主存队 列头指针 25K 0 30K 180K 0 40K 100K 0 60K ^ （2）首次适应算法：作业分配到起始地址为100K大小为60K的自由主存(空闲区)； 最佳适应算法：作业分配到起始地址为180K大小为40K的自由主存(空闲区)； 2．已知主存容量为64K字节，某一作业A的地址空间如右图所示。它的4个页面（页面大小为1K）0、1、2、3被分配到主存的1、2、4、6块中： （1）画出作业A的页表。 （2）假设600号单元处有一指令“mov r1，[3700]”，请对 逻辑地址3700进行地址重定位，求出其对应的物理地址。 【解答】（1）页表为： 0 1 2 3 1 2 4 6 （2）已知页面大小为1K，则由作业地址3700＝3×1024+628，可知该地址对应页号P＝3，页内偏移W＝628。根据页表可知对应物理块号为6，因此其对应的物理地址为：6×1024＋628＝6772。 3．设某连续文件由四个逻辑记录组成，每个逻辑记录大小为1K字节，磁盘块大小为512字节。若第一个记录从第100号磁盘块开始存放，试画出此连续文件结构。 【解答】设记录分别为r0、r1、r2、r3，由题意知每个记录占两个磁盘块空间，结构图为： 4．设某串联文件由四个逻辑记录组成（其大小与磁盘块大小相等，均为1K），并分别存放在100、157、66、67号磁盘块上。试画出此串联文件结构。 【解答】设文件记录分别为r0、r1、r2、r3，则结构图为: 注明：也可用FAT表的结构图形式表示，如下图： 作业7：SQL Given a relation scheme as follows: Student（SNo，SName，SSex，SAge） Where the attributes of SNo, SName, SSex and SAge mean the student’s number, name, sex and age respectively. The underlined attribute is the primary key. （1）Explain the operation of the following SQL statements. ① CREATE TABLE Student（ SNo CHAR(6) NOT NULL, SName CHAR(6), SSex CHAR(2), SAge SMALLINT, PRIMARY KEY（SNo））; To define a relation schema named Student with four attributes: Sno, Sname, Ssex, Sage, with the attribute Sno as the primary key and the value of SNo is not NULL. ② SELECT Sno, Sname, SAge FROM Student WHERE SSex＝’Female’ ORDER BY SAge; To find the number, name and age of all female students and display the result by ascending order of age of those students. （2）Design and write out corresponding SQL query statements according to the following requirements. ① To find the number, name and sex of students whose age are large than 19. SELECT SNo, SName, SSex FROM Student WHERE SAge >19; ② To find the number and name of male students who are 19 or 20 years old. SELECT SNo, SName FROM Student WHERE (SSex =’Male’ AND (SAge =19 OR SAge =20 )); ③ To find the average age of all students. SELECT Average (SAge) FROM Student; 百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库华工软件技术基础(双语)作业解答在线全文阅读。
相关推荐：
