1.(10 points)give an advantage that a.a sequential file has over an indexed file b.a sequential file has over a hashed file c.a indexed file has over a sequential file d.a indexed file has over a hashed file e.a hashed file has over a sequential f.a hashed file has over a indexed file 2.(10 points)design an algorithm that lists all possible rearrangements of the symbols in a string of five distinct characters 3.(10 points)arrange the name Bi,Di,Ri,Si,Ti, and Wi in an order that requires the leaset number of comparisons when sorted by the quick sort algorithm. 4.(10 points)describe what is the stored-program concept. 5.(10 points)would a large array probably be passed to a subroutine by valve? yes or no? support your judgment 6.(10 points)draw a state diagram and write the turing.instructions for a turing machine that takes any string of 1s and changes every third 1 to a 0. thus,for example, ...b111111b... would become ...b110110b... 7.(15 points)implement the combination logic f(A,B,C,D)=sigma(0,3,8,10,12,14)+ d(1,2,5,7) a.by using 3 level NAND gate(using minimal number of gates) b.by using a decoder c.by using a 8*1 multiplexor 8.(5 points)describe the difference between syntax,run-time,and logic errors. 9.(20 points)given the following list:14,15,5,9,8,3,19,4 a.please construct a binary search tree for the sequence. b.please traverse the binary serch tree in postorder c.construct an AVL tree for the sequence. d.Construct a heap tree(note,the root has the maximum key)for the sequence. (note.show your answers step by step.) 1.which are privileged instructions? a.I/O instruction b.trap or software-generated interrupt c.WAIT instruction d.the base and limit registers(for memory space)loading 2.which are correct for real-time system? a.in hard real-time systems,the operating system kernel delays do not need to be bounded. b.a hard real-time system guarantees that critical tasks be completed on time c.virtual memory is almost never found on hard real-time systems d.a soft real-time system claims that a critical real-time task gets priority over other tasks,and retains that priority until it completes. 3.which activities should be taken in the secondary-storage management? a.free-space management b.creating and deleting derectries c.storage allocation d.buffering 4.which are correct for process state? a.if a process is created,it will enter the "running"state. b.if the waiting event of a process occurs,the process will enter the "running" state. d.if a running process encounters an interrupt,it will enter the "ready"state. 5.which are correct for CPU-scheduleing algorithms? a.the FCFS scheduling algorithm must be nonpreemptive. b.the SJF algorithm must be preemptive. c.An SJF algorithm is simply a priority algorithm where the priority is the inverse of the next CPU burst. d.the round-robin scheduling algorithm is designed especially for time-sharing systems. 6.which are correct for process synchronizations? a.a semaphor,apart from initialization,is accessed only through two standard atomic operarions:wait and signal. b.mutual-exclusion can be implemented with testandset or swap instructions. c.a spinlock(some kind of semaphores)is not useful when locks are expected to be held for short time d.a counting semaphore can be implemented using binary semaphores. 7.what conditions does the approach(i.e.,imposing a total ordering of all resource types,and requiring that each process requests resources in an increasing order of enumeration) try to prevent? a.mutual exclusion b.circular wait c.no preemption d.hold and wait 8.which are correct for pure segmentation? a.segmentation is a memory-management scheme that supports the user view of memory. b.a particular advantage of segmentation is the association of protection with the segment. c.an advantage of segmentation involves the sharing of code or data. d.like paging,segmentation has no external fragmentation. 9.which are correct for virtual memory? a.FIFO page replacement is a stack algoritm. b.the LRU strategy is the optimal page-replacement algorithm looking backward in time,rather than forward. c.the accuracy of the working set depends on the selection of a(i.e.,the working-set window). d.if I/O is done to ro from user virtual memory,these pages do not need to be locked in memory when demand paging is used. 10.which disk scheduling algorithms always service I/O requests in only one direction? a.SSTF scheduling b.SCAN scheduling c.C-SCA scheduling d.LOOK scheduling 11.the following code is designed to solved the dining philosopher problem. suppose that there are five philosophers spending their lives alternatively thinking and eating spaghetti,and they are seated around a table on which is placed five plates of pasta anf five forks. when a philosopher decides to eat,then he or she must obtain two forks by first picking up the left fork and then picking up the right fork.after consuming food,the philosophor replaces the forks and resumes thinking.what problems would occur in the following code executed by each philosopher?modify the code to solve the problems posed by you. semaphore fork[5]={1,1,1,1,1}; philosopher(int i){ while (true){ .../*thinking*/ p(fork[i]); /*pick up left fork*/ eat(); V(fork[(i+1)mod 5]; v(fork[i]); ) 12.consider the following page reference string: 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6 how many page faults would occur for the following rplacemant algorithms:LRU replacement,FIFO replacement,Optimal replacement.Assuming the number of allocated frames is three and all frames are initially empty. 13.consider the problem of jobs waiting in --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.58.22.74