# Fundamentals of Data Structures and Algorithms Answers

### Data Structures and Algorithms seeking expert answers. Grateful

Question 1

Title Type:Single Choice

Title:Data Structures Major Study (4)

1.Logical structure of data

2.Storage structure of data

3. 4.Logical structure of data, storage structure and implementation of data in operations

Question 2

Topic Type: Single Choice Question

Topic: Since the logical structure of data can be obtained by different storage mapping methods, there are no common data storage structures (3).

2.Sequential storage structure

3.Indexed storage structure

4.Hash storage structure

QUESTION 3

Title Type:Single Choice Question

Title: When we discuss a particular data structure, we discuss four main aspects of the problem, ① logical structure of the data ② data storage structure ③ in the logical structure of the data defined in the data of the basic operations; ④ basic operations algorithms of the specific implementation; the discussion of these four issues in what order of priority should be? (1 )

1.① ② ③ ④

2.① ③ ② ④

3.① ③ ④

3.① ① ③ ④

4.① ① ④ ③

QUESTION 4

Topic Type: Single Choice

Title: In what way does a linear chained table express the Relationships between elements(1)

2. Order in which the elements are stored

3. Addresses of the left and right children

4. Relative storage location of the elements

Question 5

Topic type: single choice

Question:When storing a linear table with a linear chain table, storage space is required(2)

1. Must be continuous

2. Both continuous and discontinuous are possible

3. The storage space for some of the elements must be continuous

4. Must be discontinuous

p>Question 6

Title Type: Single Choice

Title: For applications that frequently require access to elements in any specified location of a linear table, the linear table should have a (1) storage structure.

1.Sequential storage structure

2.Chained storage structure

3.Linear chained tables

4.Stacks

Question 7

Topic Type:Single Choice Question

Topic:A data structure with a linear structure is (2)<

1.

Huffman Tree

2.Stack

3.Diagram

4.Tree

QUESTION 8

Title Type:Multiple Choice Question

QUESTION:The sequence of entries of a stack is abcde, then the impossible output sequence of a stack is (3).

1.edcba

2.decba

3.dceab

4.abcde

QUESTION 9

Question Type:Single Choice Question

Question:To a chained stack with the top pointer of the stack HS to a chain stack where the top pointer of the stack is HS, perform (2).

1.HS->next=s

2.S->next=HS->next;HS->next=s

3.

S->next=HS;HS=s

4.S->next=HS;HS=HS->next

Question 10

Topic Type:Multiple Choice

Title:The following statements are correct (2)

1.Stacks are operated at both ends, first-in, first-out Linear table

2. Stack is a linear table that operates at one end, FIFO

3. Queue is a linear table that operates at one end, FIFO

4.

### Data Structures and Algorithms questions need to be answered

Simulation Questions on Data Structures and Algorithms

I. Fill in the blanks: (15 points) (one point for each blank)

According to the device in which the data is stored when sorting, sorting can be categorized into <1> sorting and <2> sorting. Internal and external sorting

The two common storage structures for graphs are <3> and <4>. Adjacency matrix and adjacency table

The three basic forms of structure in data structures are <5> linear structure and <6> tree structure, graph structure <7>.

A binary tree of height 6 has at most <8>63 nodes.

The time complexity of linear lookup is <9>O(n^2), the time complexity of folded lookup is <10>O(nlogn), and the time complexity of heap classification is <11>O(nlogn).

In the use of hashing method for finding, in order to reduce the chance of conflict, hash function must have a better randomness, in our introduction of several hash function construction method, the best randomness is <12> random number method, the simplest construction method is to divide and leave the remainder of the method <13>.

The three storage structures for linear tables are: arrays, <14> chained lists, <15> static chained lists.

The root node has:

The leaf nodes have:

The node with maximum degree:

The ancestors of a node are:

The descendants of a node are:

The stack is stored in an array A[m], with the bottom of the stack at position m-1.Ask:

What is the condition for the stack to be empty?top=m-1

What is the condition that the stack is full? top=-1

Difference and connection between data structure and abstract datatype:

Data structure (datastructure)- is a collection of data elements that have one or more specific relationships with each other. The relationship of data elements with each other is called structure.

Abstract Data Type (ADT): is a mathematical model (data structure) and a set of operations defined on that model (data structure).

### Data Structures and Algorithms Test Questions, High Score, Answers Wanted

3 It is known that a non-empty binary tree whose first and middle roots are traversed as follows:

First Root: ABCDEFGHI

Middle Heel: CBEDAGFHI

Construct this binary tree.

/ \

B F

/ \ / \

C D G H

/ \

I E

4. Analyze the running time of the following program:

A) void mystery(intn)<

{int i,j,k;

for(i=1;i<n;i++)

for(j=i+1;j<=n;j++)

for(k=1;k<=j;k++)

{some statement requiring O( 1) time;}

}

My answer is n3 but I’m not sure

B) void podd(int n)

{int I,j,x,y;

for(I=1;I<=n;I++)

if(odd(I))

{for(j=I;j<=n;j++)

x=x+1;

for(j=1;j<=I;j++)

y=y+1;

}

}

n2 isn’t quite sure

5 It is known that the The mathematical expression is (3+b)sin(x+5)-a/x2, find the prefix and suffix representations of the Polish representation of the expression (the procedure is required to be given).

The binary tree corresponding to the expression is

So the corresponding prefix is: -*+3bsin+x5/a*xx

Suffix: 3b+x5+sin*axx*/-

Three implements the following algorithm

p>In a pointer implementation of a linear table L, realize the deletion of the node with keyword x in the linear table L.

intvisited[n];

voiddfs(Graphg,inti)

{edgeNode*t;

printf(“%4d”,i);

visited[i]=1;

t=g[i];

while(t!=NULL){

if(visited[t->vno]==0)

dfs(g,t->vno);

t=t->next;

< p>}

}

Find the successor of the order of its middle root from the node P in a clue binary tree.

typedefstructBinThrNode{

TElemTypedata;

structBinThrNode*lchilid, *rchild;

PointerTagltag, rtag;

} BinThrNode,*BinThrTree;

Middle-order traversal of clue binary tree

Find the predecessor of the node pointed to by p:

When p->ltag==THREAD, the predecessor is p->lchild;

When p->ltag==LINK, the predecessor is the rightmost lower node of p->lchild.

Implement the insertion of record R in the binary lookup tree F.

VoidINSERT(recordsR,BST&F)

{if(F==NULL)

{F=newcelltype;

< p>F->data=R;

F->lchild=NULL;

F->rchild=NULL;}

elseif(R,key<F->data.key)

INSERT(R,F-&gt. lchild);

elseif(R,key>F->data.key)

INSERT(R,F->rchild);

}

Fourth, for the following connected undirected graph with weights, use Prim’s algorithm to construct a minimum spanning tree. Draw each step of the construction process. (12 points)

V Let the data to be categorized be stored in array A

3141592653

To classify the heap, you first have to build an initial heap for it, try to draw the change of the binary tree and the change of the array A in the process of initial construction of the heap.

### What are the answers to the following questions on data structures and algorithms in computing?

(1) Handle conflicts by linear probing open address method;

H(Jan)=10/2=5;

H(Feb)=6/2=3;

H(Mar)=13/2=6;

H(Apr)=1/2=0;

H(May)=13/2=6; Conflict;H1=6+1=7;

H(June)=10/2=5; Conflict;H1=5+1=6; Conflict;H2=7;H3=8;

H(July)=5;H1=6;H2=7;H3=8;H4=9

H(Aug)=0;H1=1;

H(Sep)= 9;H1=10;

H(Oct)=7;H1=8;H2=9;H3=10;H4=11;

H(Nov)=7;H1=8;H2=9;H3=10;H4=11;H5=12

H(Dec)=2

ASL=(1+2+1+1+1+1+2+2+) 4+5+2+5+6)/12=31/12

(2) Handling conflicts by chain address method

H(Jan)=5;

H(Feb)=3;

H(Mar)=6;

H(Apr)=0;

H(May)=6

H(June )=5;

H(July)=5;

H(Aug)=0;;

H(Sep)=9;

H(Oct)=7;

H(Nov)=7;

H(Dec)=2

0->Apr->Aug

< p>1->

2->Dec

3->Feb

4->

5->Jan->June->July

6->Mar->May

7->Oct-& gt;Nov

8->

9->Sep

ASL=(1+2+1+1+1+2+3+1+2+1+2+1)/12=18/12

### I’m looking for help from someone high up in data structures and algorithm analysis to help me with these questions. (I hope the correct answers are given, thanks in advance!!!)

Fill in the blanks

1.n-1

Because the end-of-queue pointer always points to null.

2.1

Because the adjacency matrix of an undirected graph is symmetric.

3.61

Number of elements =

(rear+max-front) when front>rear

(front+max-rear) when rear>front

4. Depth-first search algorithm

5. Judgment Questions

1.F

Binary trees can then be stored in arrays.

2.F

When a conflict occurs, it has to look for it in the next position, but still needs to move on if that position is already occupied. Therefore, synonyms

3. The number of ranks in the adjacency matrix of an F

graph depends only on the number of vertices.

4.F

There is no fastest sorting algorithm, only relatively fast under certain conditions.

5.T

Multiple Choice

1.D

2.B

Loc(a[6])=Loc(a[1])+(6-1)*2

=90+10=100

3.A

4.C

5.C

Go to Heap sort with each element at the bottom leaf level, then the larger non-leaf nodes are stored.

6.C

Construct a binary tree:

/

*+

A+-F

BCDE

A backward traversal of this binary tree is sufficient.

7.C

Fold-and-half lookup requires that the lookup table be ordered and can be located based on subscripts, and requires direct access.

Sequential storage: direct access, but insertion and deletion time-consuming

Chained storage: only sequential access, insertion and deletion is convenient

8.D

Quadratic probing and then hashing method:

di=1,-1,4,-4,9,-9…

This is the first time that a table has been accessed in the past. 4, 9, -9…