Data structure questions, questions about data structures

These things are expressed in ASCII codes, and then determined by scan input and if statements.

1(1): Linked lists, because linked lists can efficiently perform insert and delete operations, and are suitable for situations where there are many changes in elements.

1 (2): Sequential table, which is inconvenient to insert and delete, but can efficiently read the elements in the linear table.

2: Linked lists can overcome weakness one, only need to change the adjacent pointer, no need to move the element; Weakness can be overcome two, dynamic distribution of controls; Weakness can be overcome three, and the linked list is convenient for expansion.

3: Yes.

4: 4 3 5 6 1 2 No, 1234 in stack 43 out stack 5 in stack 5 out stack 6 in stack 6 out stack 12 reverse order.

1 3 5 4 2 6 Yes, 1 in 1 out of 23 3 out 45 54 out of 2 out 6 6 out of 6 out of 6 out of the stack.

5: Yes.

6: See Fig.

7: See diagram.

8: All the nodes of the tree except the leaves have only the right node, which degenerates into a linear table like a pinch.

9: No picture.

10: It is the insertion sorting, but the insertion process uses a dichotomy when finding the insertion position.

Select A, and each node occupies a contiguous storage area.

The chained storage structure does not require all nodes to occupy a contiguous storage area, and the nodes are linked by pointers.

Sequential storage requires all nodes to have a contiguous storage area.

However, whether it is sequential or chained, each node occupies a contiguous storage area.

The structure of the node is:

Precursor pointer—data field—successor pointer.

Note: The first node has no predecessor, and the last node has no successor.

The result is a CD error.

Do it with one stack. Scan the expression character by character in order, and if you encounter (, [Check whether the top element of the stack is the corresponding left symbol, if yes, the top of the stack symbol will be removed from the stack, and then continue to judge, otherwise an error will be reported; Finally, see whether the stack is empty, if it is empty, it is correct, otherwise an error is reported.

(1)b

Delete the first node, and the time complexity is o(1) and o(n), respectively, and the two linked lists use the same type of variable, occupying the same size of space.

2) It is possible that both the ch and h-1 layers may have leaf nodes.

Layer H-1 may have a node of degree 1.

3) A refers to the insertion algorithm of the B tree.

4) CQ is the precursor junction of P.

5)b6)c

7)dtail(a)=((d,e,f))

head(tail(a))=(d,e,f)tail(head(tail(a)))=(e,f)(8)a

9) d The first three are not necessarily spanning trees.

10) The process is complicated.

11) The key is to build a huffman tree.

（ ×1.Each node of a linked list contains exactly one pointer.

A: False. A node in a linked list can contain multiple pointer fields, each holding multiple pointers. For example, a node in a doubly linked list can contain two pointer fields that hold pointers to its immediate predecessor and successor.

2.The physical storage structure of a linked list has the same order as a linked list.

False, the storage structure of a linked list is characterized by disorder, while the schematic diagram of a linked list is orderly.

3.The deletion algorithm of a linked list is simple, because when a node in the chain is deleted, the computer automatically moves the subsequent units forward.

False, the nodes of the linked list do not move, but the pointer content changes.

4.The sequential table structure is suitable for sequential access, while the linked list is suitable for random access.

Wrong, it's the other way around. Sequential tables are suitable for random access, and linked lists are suitable for "following the vine".

5.The advantages of the sequential storage method are that the storage density is large and the insertion and deletion operations are efficient.

False, the first half is correct, but the second half is wrong, and that's the advantage of chained storage. In a sequential table with a table length of n, inserting and deleting a data element requires moving half the number of data elements on average.

6.Linear tables must also be continuous in physical storage space.

False, linear tables are stored in two ways, sequential storage and chain storage. The latter does not require continuous storage.

7.Stacks and queues can be stored sequentially or linked.

8.When two stacks share a contiguous memory space, the bottom of the stack should be set at both ends of the memory space to improve memory utilization and reduce the chance of overflow.

9.A team is a linear table in which insertion and deletion operations are performed at both ends of the table, and it is an advanced last-out structure. Wrong, the second half of the sentence is wrong.

10.If the input sequence of a stack is 12345, the output sequence of the stack cannot be 12345. Wrong, possibly.

1. C Sparse matrix storage is a waste of space, and compression is generally to reduce space complexity.

2、C originally wanted to choose more. Later I remembered that arrays can't be deleted, so the answer is only c

7.The number of nodes in a linear table is , and the relationship between nodes is .

Limited? Linear? Or is it one-on-one?

8.When inserting an element before the ith element (1 i n+1) of a vector with a bench hall degree n, you need to move the element backwards.

n - i + 1

9.When deleting the ith element (1 i n) from a vector of length n, you need to move the element forward.

n - i10.The time complexity of accessing any node in a sequential table is , so a sequential table is also known as a data structure of .

o(1) Random visits.

11.The physical location of logically adjacent elements in a sequential table. The physical location of logically adjacent elements in a singly linked list Adjacency. Also. Need not.

12.In a singly linked list, the storage location of any node except the first node is indicated by .

A successor pointer to the precursor node.

13 To delete a known node *p in a singly linked list of n nodes, you need to find its , which has a time complexity of .

Prodromal nodes. o(n)

inserting and deleting elements; For consumer travel queues can only be found in.

inserting and deleting elements;

Linear? Arbitrarily.

Header (top of stack).

Tail of the table (tail of the line).

Table head (team head).

15.In a round-robin queue with n units, it is shared when the queue is full.

elements. If you waste an element space, n - 1 when the team is full, n if you use the flag method, etc.

16.This is called an empty string;

This is called a blank string.

Strings that do not contain characters.

Strings that are all spaces.

17.Let s="a; document, the position of the character of strlen(s)= is .

Positioning from 1 is 3, and from 0 it is 2

18.Suppose you have a two-dimensional array a6 8, where each element is stored in 6 adjacent bytes, and the memory is addressed by bytes. Knowing that the starting storage location (base address) of a is 1000, the volume (storage amount) of array a is ; Take the first byte address of element a57 at the end of the stool.

6 x 6 x 8 = 288

1000 + 6 x (5 x 8 + 7) =1282

These two questions look at different aspects:

The relationship between the pre-sequence sequence and the mid-order sequence is equivalent to the pre-sequence sequence as the stack entry order, and the middle sequence as the out-stack order, because the traversal is obtained through recursion, and the recursion needs to be completed by the stack, and what cannot be obtained through the stack cannot be obtained by traversal, in fact, the number of different sequences obtained by n elements entering the stack is equal to the form of n node binary trees.

Another problem examines the nature of binary tree traversal, which is the opposite of the pre-order and the post-order, that is, there is only one node in each layer, which is a bit far from that stack.