I am habing trouble with these problems for my review sheet. If you could please
ID: 3804257 • Letter: I
Question
I am habing trouble with these problems for my review sheet. If you could please help, I will upvote clear helpful response. Also if you could go into a bit more detail with questions #6 and #7 I would appreicate it. Thanks
1. Why does our node class have two versions of the link member function?
A. One is public, the other is private.
B. One is to use with a const pointer, the other with a regular pointer.
C. One returns the forward link, the other returns the backward link.
D. One returns the data, the other returns a pointer to the next node.
2. Suppose that p is a pointer variable that contains the NULL pointer. What happens if your program tries to read or write *p?
A. A syntax error always occurs at compilation time.
B. A run-time error always occurs when *p is evaluated.
C. A run-time error always occurs when the program finishes.
D. The results are unpredictable.
3. Suppose that f is a function with a prototype like this:
void f(________ head_ptr);
// Precondition: head_ptr is a head pointer for a linked list.
// Postcondition: The function f has done some computation with
// the linked list, but the list itself is unchanged.
What is the best data type for head_ptr in this function?
A. node
B. const node
C. node*
D. const node*
4. Suppose that f is a function with a prototype like this:
void f(________ head_ptr);
// Precondition: head_ptr is a head pointer for a linked list.
// Postcondition: The function f has done some manipulation of
// the linked list, and the list might now have a new head node.
What is the best data type for head_ptr in this function?
A. node
B. node&
C. node*
D. node*&
5.
Consider the usual algorithm for determining whether a sequence of parentheses is balanced. Suppose that you run the algorithm on a sequence that contains 2 left parentheses and 3 right parentheses (in some order). What is the maximum number of parentheses that will ever appear on the stack AT ONE TIME during the computation?
A. 1
B. 2
C. 3
D. 4
E. 5 or more
6.In the circular array version of the queue class (with a fixed-sized array), which operations require linear time for their worst-case behavior?
A. front
B. push
C. empty
D. None of these operations require linear time.
7. In the linked-list version of the queue class, which operations require linear time for their worst-case behavior?
A. front
B. push
C. empty
D. None of these operations require linear time.
Explanation / Answer
1. C. One returns the forward link, the other returns the backward link.
Genrally, a node representation of a linked list will contain pointer to front and back so return them we use two pointers
2. B. A run-time error always occurs when *p is evaluated.
At compile time system does not know so we get run time error and once a error is encounted the program terminates. We get segmentation fault error.
3. D. const node*
Since, we should not change the pointer reference to head pointer we should specify it with const. If we try to change a value of a variable which is defined as const we get a compilation error.
4. C. node*
Here we can change the refernce to head pointer so should not specify const.
5. B. 2
- This is because only if input is in this format (())) we have 2 elements on the satck and int other cases such as ()()) we have only 1 and we cannot more than 2 elements on the stack for given input
6. D. None of these operations require linear time.
7. D. None of these operations require linear time.
Explanation for 6 and 7:
Front, push and empty opeartion take O(1) in both linked list and array implementation. Because we have pointer for front so we return it directly. For push we maintain a pointer to rare to when we perform push
just we need to create a node and change the rare pointer. In case of empty we just compare whether front== rare and return tha boolean value so it also takes constant time
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.