Conclusion Literature tests with answers on the structures of algorithms

Literature

1. 
   Bertiss A.T. Data Structures. / Per.s Engl.- M.: Statistics, 1974.
2. 
   Wirth N. Algorithms and data structures.- M .: Mir, 1989.
3. 
   D. Reilly. Abstraction and data structures. Introductory course. M .: Mir, 1993.
4. 
   Kostin AE, Shan'gin V.F. Organization and processing of data structures in computing systems.- M .: Higher School, 1987.
5. 
   Lengsam et al. Data structures for personal computers. - M .: Mir, 1989.
6. 
   J. Tremblay, P. Sorenson. Introduction to data structures. - M .: Mashinostroenie, 1982.

attachment.
Tests with answers

Lab 1. Semistatic data structures (stacks).

6. 
   What are the features of the queue?

• 
  open on both sides (true);
• 
  open on one side for insertion and deletion;
• 
  any item is available.

7. 
   What is the stack stack?

• 
  open on both sides for insertion and deletion;
• 
  any item is available;
• 
  open on one side for insertion and deletion (true).

8. 
   What discipline of service is called FIFO?

• 
  stack;
• 
  queue (true);
• 
  Dec

9. 
   What operation reads the top of the stack without deleting?

• 
  pop;
• 
  push;
• 
  stackpop (true).

10. 
    What is the rule to fetch an item from the stack?

• 
  first item;
• 
  last element (true);
• 
  any item.

Laboratory work 2. List data structures (singly-connected queues).

6. 
   How to free memory from an item from the list?

• 
  p = getnode;
• 
  ptr (p) = nil;
• 
  freenode (p) (true);
• 
  p = lst.

7. 
   How to create a new list item with information field D?

• 
  p = getnode;
• 
  p = getnode; info (p) = D (true);
• 
  p = getnode; ptr (D) = lst.

8. 
   How to create an empty element with a pointer p?

• 
  p = getnode (true);
• 
  info (p);
• 
  freenode (p);
• 
  ptr (p) = lst.

9. 
   How many pointers are used in single-linked lists?

• 
  1 (true);
• 
  2;
• 
  any number

10. 
    What is the distinctive feature of dynamic objects?

• 
  generated immediately before the execution of the program;
• 
  arise already in the process of program execution (correct);
• 
  set during program execution.

Laboratory work 3. List data structures.

6. 
   When removing an item from the ring list ...

• 
  the list is broken;
• 
  a hole appears in the list;
• 
  the list gets shorter by one element (true).

7. 
   What is the pointer used in ring lists?

• 
  to reference the next item;
• 
  to memorize the number of the element location segment;
• 
  to link to the previous item (true);
• 
  for the location of the item in the memory list.

8. 
   What is the difference between a ring list and a linear one?

• 
  in the ring list, the last element is simultaneously the first one;
• 
  in the ring list, the last element pointer is empty;
• 
  there is no last item in the ring lists (true);
• 
  in the ring list, the last element pointer is not empty.

9. 
   How many pointers are used in a single ring list?

• 
  1 (true);
• 
  2;
• 
  any number

10. 
    In which directions can you navigate in the bidirectional ring list?

• 
  in both (true);
• 
  to the left;
• 
  to the right.

Lab 4. Model of queuing.

6. 
   What is the difference between the first priority application and the second priority application?

• 
  the fact that the application of the second priority is served with the probability P = 1, and the application of the first priority is served with the probability P (B);
• 
  the fact that the application of the second priority goes to the top of the queue, and the first priority goes to the end of the queue (true);
• 
  nothing if there is a queue.

7. 
   Can the first priority application displace the second priority application from the queue?

• 
  yes, if P (B) = 1;
• 
  Yes;
• 
  no (correct).

8. 
   Can the first priority application be serviced if the second priority application is in the queue?

• 
  yes, if P (B) = 1;
• 
  yes (true);
• 
  not.

9. 
   What data structure is the most efficient way to implement a queue?

• 
  stack;
• 
  list (correct);
• 
  Dec

10. 
    When the application leaves the system. Find the error.

• 
  if the application was served by the number of clocks enclosed by it;
• 
  if the application is in the queue for more than T cycles;
• 
  if there are more applications of the second priority than applications of the first priority (correct).

Laboratory work 5. Binary trees (basic procedures).

6. 
   To include a new vertex in the tree, you need to find a node to which it can be attached. The node will be found if the next link defining the branch of the tree in which to continue the search is the link:

• 
  p = right (p);
• 
  p = nil (true);
• 
  p = left (p).

7. 
   To write a procedure on two trees, you need to describe an element of the record type that contains the fields:

• 
  Element = Record

Left, Right: Pointers

Rec: Record;

• 
  Element = Record

Left: Pointer

Key: Key

Rec: Record;

• 
  Element = Record (true)

Left, Right: Pointers

Keu: Key

Rec: Record.

8. 
   In computer memory, a binary tree can be conveniently represented as:

• 
  linked linear lists;
• 
  arrays;
• 
  linked non-linear lists (true).

9. 
   Element t for which there are no links:

• 
  root (true);
• 
  intermediate;
• 
  terminal (list).

10. 
    A tree is called complete binary if the degree of outcomes of the vertices is:

• 
  2 or 0 (true);
• 
  2;
• 
  M or 0;
• 
  M.

Laboratory work 6. Sorting by direct inclusion.

6. 
   Three conditions are given for the end of sifting when sorting by direct inclusion. Find among them too much.

• 
  found the element a (i) with a key smaller than the key at x;
• 
  found the element a (i) with a key larger than the key of x (true);
• 
  Reached the left end of the finished sequence.

7. 
   Which of the criteria for sorting efficiency is determined by the formula M = 0.01 * n * n + 10 * n?

• 
  number of comparisons (true);
• 
  time spent writing a program;
• 
  number of movements;
• 
  time spent on sorting.

8. 
   What is the name of the sorting that happens in RAM?

• 
  sorting the address table;
• 
  complete sorting;
• 
  live-sorting;
• 
  internal sorting (true);
• 
  external sorting.

9. 
   How can I reduce the cost of machine time when sorting a large amount of data?

• 
  Sort in the key address table (true);
• 
  produce sorting on a more powerful computer;
• 
  split the data into smaller portions and sort them.

10. 
    There are the following sorting methods. Find the error.

• 
  strict;
• 
  advanced;
• 
  dynamic (true).

Lab 7. Selection by direct selection.

6. 
   The sorting method is called sustainable if the sorting process ...

• 
  relative positioning of the elements is indifferent;
• 
  the relative position of elements with equal keys does not change (true);
• 
  the relative position of elements with equal keys changes;
• 
  relative position of elements is not defined.

7. 
   Improved methods have a significant advantage:

• 
  with a large number of sorted items (true);
• 
  when the array is back ordered;
• 
  with small quantities of sorted elements;
• 
  in all cases.

8. 
   Which of the following concepts is one of the types of sorting?

• 
  internal sorting (true);
• 
  descending sorting;
• 
  data sorting;
• 
  Sort Ascending.

9. 
   How many comparisons does an improved sorting algorithm require?

• 
  n * log (n) (true);
• 
  e ⁿ ;
• 
  n * n / 4.

10. 
    Which method is the sort that requires n * n key comparisons?

• 
  direct (true);
• 
  binary;
• 
  the simplest;
• 
  the reverse.

Lab 8. Sorting using direct exchange.

6. 
   How many comparisons and permutations of elements are required in bubble sorting?

• 
  n * lon (n);
• 
  (n * n) / 4 (true);
• 
  (n * nn) / 2.

7. 
   How many additional variables do you need in bubble sorting besides an array containing elements?

• 
  0 (not needed);
• 
  only 1 item (true);
• 
  n variables (exactly as many elements in the array).

8. 
   How to sort an array faster using the bubble method?

• 
  equally (true);
• 
  on the recovery of elements;
• 
  descending elements.

9. 
   What is the idea behind the QuickSort method?

• 
  selection of 1,2, ... n - th element for comparison with the rest;
• 
  separation of keys in relation to the selected (true);
• 
  exchange of places between adjacent elements.

10. 
    The array is sorted by the “bubble” method. For how many passes through the array the “easiest” element in the array will be at the top?

• 
  for 1 pass (true);
• 
  in n-1 passes;
• 
  for n passes, where n is the number of array elements.

Lab 9. Sort using the tree.

6. 
   When traversing a tree

from left to right, we get a sequence ...

• 
  sorted in descending order;
• 
  unsorted (true);
• 
  sorted by ascending.

7. 
   Which of the three trees is not strictly balanced?

• 
  A;
• 
  B (true);
• 
  C.

8. 
   When traversing a tree from left to right, its element is entered into an array ...

• 
  during the second entry into the element (correct);
• 
  when you first enter the item;
• 
  at the third entry into the element.

9. 
   The element of the array with the key k = 20 must be inserted into the depicted tree so that the tree remains sorted. Where to insert it?

• 
  the left son of element 30 (true);
• 
  the left son of element 41;
• 
  element 8's left son.

10. 
    By traversing which tree from left to right is an array sorted in ascending order?

• 
  A;
• 
  B;
• 
  C (true).

Laboratory work 10. Investigation of methods of linear and binary search.

6. 
   Where is linear search effective?

• 
  in the list;
• 
  in array;
• 
  in the array and in the list (true).

7. 
   What search is more effective?

• 
  linear;
• 
  binary (true);
• 
  no difference.

8. 
   What is the essence of a binary search?

• 
  finding an element of array x by dividing the array in half each time until the element is found (true);
• 
  finding the element x by traversing the array;
• 
  finding the element of array x by dividing the array.

9. 
   How are the elements in the binary search array?

• 
  ascending (true);
• 
  chaotically;
• 
  descending.

10. 
    What is the essence of linear search?

• 
  sequential viewing is performed from beginning to end and back through 2 elements;
• 
  sequential view of the elements from the middle of the table;
• 
  sequential viewing of each element (true).

Laboratory work 11. Research of search methods with moving to the beginning and transposition.

6. 
   Where is the transposition method most effective?

• 
  in arrays and lists (true);
• 
  only in arrays;
• 
  only in lists.

7. 
   What is the essence of the permutation method?

• 
  found element is placed in the head of the list (true);
• 
  the found element is placed at the end of the list;
• 
  found element is reversed.

8. 
   What is the essence of the transposition method?

• 
  rearrangement of adjacent elements;
• 
  finding the same elements;
• 
  permutation of the found element by one position towards the beginning of the list (correct).

9. 
   What is a unique key?

• 
  if the difference between the values ​​of the two data is equal to the key;
• 
  if the sum of the two data values ​​is equal to the key;
• 
  if there is only one data in the table with such a key (true).

10. 
    What is the purpose of the search?

• 
  among the data array to find the data that match the specified argument (true);
• 
  determine that there is no data in the array;
• 
  using data to find the argument.

Laboratory work 12. Search the tree with the inclusion.

6. 
   In which binary tree do you need to sort out N / 2 elements on average in binary search?

• 
  A;
• 
  B (true);
• 
  C.

7. 
   How many elements need to be sorted out in a balanced tree?

5. 
   N / 2;
6. 
   Ln (N);
7. 
   Log ₂ (N);
8. 
   e ^N.

• 
  A;
• 
  B;
• 
  C (true);
• 
  D.

8. 
   Select the tree variant obtained after inserting the node -1.

• 
  A (true);
• 
  B;
• 
  C.

9. 
   Which element attach element 40 to insert it into this tree?

• 
  by the 30th (true);
• 
  by the 15th;
• 
  by –15;
• 
  by the 5th.

10. 
    What kind of tree will take after the entry of the element with key 58?

• 
  A (true);
• 
  B;
• 
  C.

Lab 13. Search the tree with the exception.

6. 
   Select the variant of the tree obtained after removing the node –3.

• 
  A;
• 
  B (true);
• 
  C.

7. 
   What version of the tree will be obtained after removing the element –1 and then –8?

• 
  A;
• 
  B (true);
• 
  C.

8. 
   Select the variant of the tree obtained after removing the node with index 0.

• 
  A (true);
• 
  B;
• 
  C.

9. 
   Which of the following pairs of numbers can become the roots of a tree after removing element 10 according to two ways to remove a node that has two sons?

• 
  0 or 15;
• 
  0 or 20;
• 
  5 or 30;
• 
  5 or 15 (correct).

10. 
    What kind of tree will take after deleting an item with key 58?

• 
  A (true);
• 
  B;
• 
  C.

Conclusion

The tutorial examined the most common operational data structures and processing algorithms that are traditionally used in the creation of software systems and complexes. Due to the limited scope of the course, attention was not paid to such structures as B - trees and graphs; in the search section, the hashing section was omitted. However, on the basis of the material already reviewed, these sections can be easily studied independently.

The current state and development trends of computer technology as the main informatics tool are such that, along with the increase in functionality, computer technology acquires properties that allow a user who does not understand programming to work on it. Recently local, corporate and global computer networks are rapidly developing. Powerful data drives are being created. In other words, the basic processes of information technology (processing, sharing and accumulating data) have risen to the next step, which naturally requires new approaches to organizing data in computers and creating appropriate programming systems. The decisive factors for this are current user interface requirements and multimedia systems. Structural graphic data and larger, integral information units - objects appeared. The result was the rapid development of object-oriented programming systems: Visual BASIC, Visual PASCAL, Visual C ⁺⁺ , etc., used to create programs based on the processing of object data structures. The exchange of object structures in networks is caused by the development of network operating systems: Intranetware, Solaris, Windows NT, etc. Data processing on multiprocessor computing systems required the creation of new data structures based on abstract representations and new programming languages: Modula 2, ADA, OCCAM.

Thus, the development of information technologies, their penetration into all areas of human life require a computer display of information in the form of relevant data structures and, of course, each new progressive step of computer science will be accompanied by a corresponding step in the field of data structures.