CSD201 FE Lý thuyết

Select the statement that is most correct.Which of the following applications may not use a stack?

• A. Keeping track of local variables a trun time

• B. Undo sequence in a text editor.

• C. Multi-programming

• D. Evaluating arithmetic expressions.

Select the statement that is most correct.Suppose we are considering a doubly linked list which is not empty. What does the java code snippet below do?Node q = new Node(x);q.prev=null;q.next = head;head.prev = q;head = q;

• [A]It inserts new node with value x at the head of the list.

• [B]It inserts new node with value x after the head of the list.

Select the statement that is most correct.Suppose we are considering a singly linked list and p is some node in the list which has both predecessor and successor nodes. What does the java code snippet below do?

Node f = head;

while(f.next != p)

f = f.next;

f.next = p.next;

• [A]It does not make any change on the list.

• [B]It deletes the node after p.

• [C]It deletes the node p.

• [D]It deletes the node before p.

Select the statement that is most correct.Which of the following applications may use a queue?

• [A]Store all variables in a program.

• [B]Store a waiting list of printing jobs.

• [C]Keeping track of local variables at run time.

• [D]Undo sequence in a text editor.

Binary search algorithm cannot be applied to

• [A]sorted linear array

• [B]Binary search tree

• [C]sorted singly linked list

Select the statement that is most correct. Suppose we are considering a doubly linked list and p is some node in the list which has successor node. What does the java code snippet below do? Node p1, p2; p1 = new Node(x); p2 = p.next; p.next = p1; p1.prev = p; p1.next = p2; p2.prev = p1;

• [A] It creates new node with value x at the end of the list.

• [B] It inserts new node with value x after the node p.

• [C] It inserts new node with value x before the node p.

• [D] It replaces the node p with new node with value x.

Fill in the blank of the statement to form the most correct one:In a ____ every element contains some data and a link to the next element, which allows to keep the structure.

• [A]doubly linked list

• [B]skip list

• [C]singly linked list

• [D]binary search tree

Whatis the correct definition of a hash function? (Select the best answer)

• [A]Hash function h(x) is a function which transforms a particular key (string, or number) into an index i= h(x) in the table T. where T[i] is used for storing an item having key x or its address.

• [B]Hash function h(x) is a function which transforms a particular key x, be it a string, number, record, or the like. into an index i= h(x) in the table T. where T[i] is used for storing an item having key x or its address.

• [C]Hash function h(x) is a function which transforms a particular key x, be it a string, number, record, or the like. into a positive integer.

• [D]Hash function h(x) is a function which transforms a particular key x, be it a string, number, record, or the like. into non-negative integer.

Specify the correct statement about chaining method for handling collision

• [A]In chaining, each position of the table is associated with a linked list or chain of structures whose info fields store keys or references to keys

• [B]In chaining, the linked-list is used instead of array for a hash table

• [C]In chaining, only some positions ofthe table is associated with a linked list or chain of structures whose info fields store keys or references to keys:

• [D]None of others

Specify the correct statement about coalesced chaining method for handling collision (select the best answer).

• [A]Because in coalesced hashing, the linked list is created inside the hash table, thus the searching raust be carried out sequentially

• [B]In coalesced hashing, the linked list is created inside the hash table and a colliding key is put in the first available position of the table.

• [C]In coalesced hashing, the linked list is created inside the hash table. Each position pos in the table contains 2 fields: info and next. The next field contains the index of thenext key that is hashed to pos

• [D]In coalesced hashing, the linked list is created outside the hash table and a colliding keys are put in the list connected to the colliding position of the table.