moocData Structures答案(慕课2023课后作业答案)
78 min readmoocData Structures答案(慕课2023课后作业答案)
Chapter 1 Unit test
1、答案答案The慕课 following statement is correct ____
A、A good algorithm will not appear inexplicable due to illegal input data.
B、课后The作业 pros and cons of the algorithm has nothing to do with the description language of the algorithm, but it is related to the environmental factors of the computer.
C、The答案答案 logical structure of data depends on the storage structure of the data.
D、All of the above are wrong
2、慕课Logically,课后 the data structure can be divided into _____ two categories
A、Linear Structure and Nonlinear Structure
B、作业Primary Structure and Tectonic Structure
C、答案答案Sequential Structure and chain Structure
D、慕课Dynamic Structure and Static Structure
3、课后When the data is 作业stored in a linked structure, the address of the storage unit ________
A、Not necessarily continuous
B、答案答案Must be continuous.
C、慕课Must be discontinuous.
D、课后Partly continuous, partly discontinuous.
4、Logically, data structures can be divided into two main categories of ___________
A、Linear structure, nonlinear structure
B、Dynamic structure, static structure
C、Sequential structure, chain structure
D、Primary structure, structural structure
5、The four basic logical structures are set structure, ____ structure, graph structure, and tree structure.
6、The four basic logical structures include linear structures, ____ structures, graphical structures, and tree structures.
7、The four basic logical structures are set structure, ____ structure, linear structure, and tree structure.
8、The four basic logical structures are set structure, ____ structure, linear structure, and graphical structure.
Chapter 2 Complexity Theory
Chapter 2 Unit test
1、The time complexity of the algorithm depends on ________.
A、Scale of the problem
B、Hardware and software configuration of the computer
C、Both.
D、Neither.
2、The calculation amount of algorithm is called the ___________ of the calculation.
A、Time Complexity
B、Efficiency
C、Reality
D、Difficulty
3、The time complexity of the following program is _________________. for(i=0;i<n;i++） for(j=0;j<i;j++) x++;
A、O(n^2)
B、O(2n)
C、O(n)
D、
4、The time complexity of the following function is_________________. int func（int n）｛ int i=0,sum=0; while(sum<n) sum+=++i; return i; ｝
A、
B、
C、O(n)
D、
5、The asymptotic time complexity of the following method is ______. (Note that there should no spaces when filling in the answer. You can use x^y to denote y power of x) void aFunc(int n) { for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { printf("Hello World\n"); } } }
6、The time complexity of aFunc is _____. (Note that there should no spaces when filling in the answer. logn denotes the logarithm function and its base is 2) void aFunc(int n) { for (int i = 2; i < n; i++) { i *= 2; printf("%i\n", i); } }
7、The asymptotic time complexity of the algorithm is ________ if the number of key steps of the algorithm is .
8、The asymptotic time complexity of the algorithm is ________ if the number of key steps of the algorithm is
Chapter 2 Homework
1、Determine the number of executions of underlined code and calculate their asymptotic time complexity （Note that there are two questions） i=1; k=0; do { k=k+10*i; i++; } while(i<=n)
2、Determine the number of executions of underlined code and calculate their asymptotic time complexity （Note that there are two questions） i=1; x=0; do { x++; i=3*i; } while( i<n);
3、Determine the number of executions of underlined code and calculate their asymptotic time complexity （Note that there are two questions） i=1; x=0; for(i=0;i<n;i++) for( j=0;j<n;j++) a[i][j]=0;
4、Determine the number of executions of underlined code and calculate their asymptotic time complexity （Note that there are two questions） y=0; while(n>=y*y) y++;
Chapter 3 Linear Data Structures
Chapter 3 Unit test
1、If the most common operation of a linear list is to read the value of the ith element, it is most efficient to use ________ storage.
A、Sequential List
B、Ordered List
C、Single Linked List
D、Two-way Linked List
2、For a linear list, the following statement is correct ________.
A、Each element has a direct antecedent and a direct successor except the first element and the last element
B、Each element has a direct precursor and a direct successor
C、There should be at least one element in the linear list.
D、The elements in the list must be in order.
3、It is known that each element in the sequential list occupies 2 storage units, and the first element address is 100, then the storage address of the 6th element in the table is ________.
A、110
B、112
C、120
D、140
4、The characteristic of a linear list with a linked storage structure is _____.
A、Insert, delete operations do not have to move elements
B、The required spatial address must be continuous.
C、Random access
D、Need to estimate storage space in advance
5、In a single linked list with a header node, set the pointer FIRST to point to the header node. when _____ indicating that the list is empty .
A、first->link==NULL
B、first==NULL
C、first->link==first
D、first!=NULL
6、In a cyclic single linked list, set the pointer FIRST to point to the header node, when ______ indicating that the chain table is empty.
A、first==NULL
B、first->link==NULL
C、first->link==first
D、first->link->link==first
7、The purpose of adding a header node to a single linked list is ________.
A、Easy implementation of insertion and deletion operations
B、Make a single linked list has at least one node
C、Avoid the break of the list
D、indicate that the single linked list uses a linked storage
8、The main advantage of a cyclic list is ________.
A、Scan the entire chain table from any node in the table
B、No longer need the head pointer.
C、can quickly access the direct precursor of certain node
D、Avoid list breaking when performing insertion and deletion operations
9、The average time complexity of element searching operations on a single linked list containing n nodes is ________.
A、O(n)
B、O(1)
C、O(n/2)
D、O(n^2)
10、If the most common operations for a linked list are inserting nodes at the end and deleting the tail nodes, then _____ is the most time-efficient.
A、Double-cycle linked list with header nodes
B、Single linked list
C、Single-cycle linked list
D、Single-cycle linked list with tail pointer
11、In a single-cycle linked list with the header pointer FIRST, the condition for the pointer p point to the tail node is ___________.
A、p->link=first
B、p->link=NULL
C、p->link->link=first
D、p->element=-1
12、The correct operation for inserting a pointer of a node S after a pointer P in a single linked list is: ( ).
A、s->link=p->link; p->link=s;
B、p->link=s; s->link=p->link;
C、p->link=s; p->link=s->link;
D、p->link=s->link; p->link=s;
13、The following options ______ are not features of the linked list.
A、Random access to any location element
B、Insert, delete operations do not require moving elements
C、No need to estimate and apply for continuous storage space in advance
D、The storage space required is proportional to the linear table length
Chapter 3 Homework
1、Please complete the following algorithm by filling in the blank to realize the reversion of the sequent list. The reversion means reverse the linear relationship of elements. For example, by reverse（a0,a1,a2）, we can get（a2,a1,a0). SeqList is defined as follows： typedef struct seqList { int n; int maxLength; ElemType *element; }SeqList; void Invert(SeqList *L) { ElemType temp; int i; for ( i=0; i<________; i++) { temp =____________; L->element[i] = L->element[___________]; L->element[________] = ___________; } } Note: There is no penalty for grammatical errors in program questions. In order to avoid mistakes mutual evaluation, please try to write clear notes or simply describe the algorithm idea.
2、Please complete the following algorithm by filling in the blank to realize the reversion of the sequent list. The reversion means reverse the linear relationship of elements. For example, by reverse（a0,a1,a2）, we can get（a2,a1,a0). typedef struct node { ElemType element; struct node *link; }Node; typedef struct singlelist { Node *first; int n; }SingleList; void invert(SingleList *L) { Node *p=__________,*q; L->first=NULL; while (_____) { q=p->link; p->link=_______; L->first=_______; p=_______; } } Note: There is no penalty for grammatical errors in program questions. In order to avoid mistakes mutual evaluation, please try to write clear notes or simply describe the algorithm idea.
3、Complete the following algorithm to fill in the blanks, and merge two sequentially-increased singly-linked lists with header nodes into one sequentially-increasing singly-linked list. typedef struct node { ElemType element; struct node *link; }Node; typedef struct headerlist { Node *head; int n; }HeaderList; void MergeList1(HeaderList *La,HeaderList *Lb,HeaderList *Lc) { //合并链表La和Lb，合并后的新表使用头指针Lc指向 Node *pa,*pb,*pc,*q; pa=La->head->link; pb=Lb->head->link; pc=Lc->head; while(pa && pb) { if(____________________) { pc->link=pa; pc=pa; pa=pa->link; La->n--; } else if(pa->element>pb->element) { pc->link=___________; pc=________; pb=_________; Lb->n--; } else { pc->link=pa; pc=pa; pa=_________; q=_________; free(pb); pb =q; } Lc->n++; } pc->link=pa?pa:pb; //插入剩余段 Lc->n+=pa?La->n:Lb->n; }
Chapter 4 Sorting
Chapter 4 Homework
1、The keywords of the data elements to be sorted are: 65,78,21,30,80,7,79,57,35,26, please sort the data elements in ascending order according to the following algorithm. Please give the results of the first 2 passes of each algorithm. 1.Direct insert sort algorithm 2.Simple selection sort algorithm 3.Bubble sorting algorithm 4.Quick sort algorithm 5.Two way merge sort algorithm 6.Heap sort algorithm
2、Please sort element sequence 27, 6, 32, 48, 26, 17, 63 1.Please use the direct insertion sorting algorithm and write out the first pass result:____________ 2.Please use bubble sorting algorithm and write out the first pass result:____________ 3.Please use the two-way merge sorting algorithm and write out the first pass result:____________ 4.Please use the fast sorting algorithm and write out the first pass result:____________
3、The elements to be sorted are: 24,33,12,17,33,15,12 Please write the results of first 3 passes of quick sort algorithm.
4、The data elements to be sorted are stored in a singly-linked list. Please complete the following simple selection sorting algorithm. The structure of the singly linked list node is defined as follows: typedef struct node{ int key; //For simplicity, the sort key is defined as an integer struct node* link; }Node; void SelectSort(Node *first) { Node * small, p, q; int temp; for (p=first; (1) ; (2) ){ small=p; for (q=p->link; q!=NULL; q=q->link) // find the minimum value if ( (3) ) // small=q; //change the values of elements temp = p->data; (4) ; (5) ; } }
Chapter 5 Sorted Sequence
Chapter 5 Unit test
1、The root node of the AVL tree constructed by inserting A, Z, B, T, C, and P in turn is ______ (the letters are numbered 1 to 26 for A~Z according to the numbering in the alphabet).
A、C
B、A
C、B
D、Z
2、Assuming that the subtrees of any node in the AVL tree are t1 and t2, the heights of t1 and t2 cannot be _____.
A、0 or 2
B、1 or 2
C、3 or 4
D、11 or 10
3、A pre-order traversal of the binary search tree yields traversal sequences of 28, 21, 25, 36, 33, 43, and then the right child of node 28 is ________.
A、36
B、33
C、43
D、No right child.
4、Which of the following trees is not a AVL tree ______.
A、
B、
C、
D、
5、Given a binary search tree as shown in the following figure, 33,9,11 are deleted from the binary search tree in turn, and then parent 17 in the final tree is ________ . Hypothesis: When performing a deletion operation, if the deletion is of a node with two children, select the directly succeeding node under the sequence of its sequential iterations as the replacement.
A、41
B、33
C、11
D、62
6、Insert the elements with keywords 65, 35, 25, 39, 38 into the empty AVL tree in turn, and the resulting AVL tree will have a root node of ________.
A、35
B、65
C、39
D、38
7、The following statement is incorrect ________.
A、Insert a new node in the AVL tree and the new node becomes a leaf node
B、A binary search tree with a full binary tree shape must be a avl tree
C、Binary search tree with n nodes, the taller the tree, the more efficient the search
D、Insert a new element in the B tree, and the new element may be adjusted to the root node
8、Which of the following trees is not a AVL tree.
A、
B、
C、
D、
9、Given a binary search tree as shown in the figure below, insert 27,65,35 into the binary search tree in turn, and then the parents of 65 is ______ .
10、Given a binary search tree as shown in the figure below, insert 27,65,35 into the binary search tree in turn, and the parent of 35 in the tree is ______.
11、Given the binomial search tree as shown in the following figure, 15,5,24 are deleted from the binary search tree in turn, and the parent of 17 is ________ . Asumption: When performing a deletion operation, if the deletion is of a node with two children, select the direct successor node under the iterative sequence as the replacement
12、Given a binary search tree as shown in the following figure, 33,9,11 are deleted from the binary search tree in turn, and then the parent of 42 is ________. Hypothesis: When performing a deletion operation, if the deletion is of a node with two children, select the directly succeeding node under the sequence of its sequential iterations as the replacement.
13、Insert the elements with keyword 76,58,0,99,7 into the empty AVL tree in turn, and the resulting AVL tree will have a root node of ________.
Chapter 5 Homework
1、Given three nodes A, B, and C, how many different unordered trees, ordered trees, and binary trees can be formed?
2、Let the binary tree be stored in a binary linked list, and try to complete the recursive algorithm for the following problems. Let the binary tree node and binary tree structure be defined as follows: typedef struct btnode { ElemType element; struct btnode* lchild, *rchild; }BTNode; typedef struct binarytree{ BTNode* root; }BinaryTree; （1）compute the height of a binary tree int Depth(BTNode *p) { int lh, rh; if (!p) return 0; lh = ______________; rh = _____________; if (lh > rh) return _________; else return ________; } int DepthofBT(BinaryTree Bt) { return ___________; } （2）compute the number of nodes in a binary tree； int Size(BTNode * p) { if (!p) return _____ ; else return Size(p->lchild)+______________+1; } int SizeofBT(BinaryTree Bt) { return ______________); } （3）change the left and right subtrees of each node in a binary tree void exchange ( BTNode * p) { if(!p) return; if ( p->lchild != NULL || p->rchild != NULL ) { temp = p->lchild; p->lchild = ____________; p->rchild = temp; exchange (___________ ); exchange ( p->rchild ); } } void exchange(BinaryTree *bt) { ____________________; }
3、It is known that the pre-order traversal sequence of a binary tree node is: F, D, E, B, C, A, and the mid-order traversal sequence is D, B, E, F, A, C. Please draw the binary tree.
4、4.It is known that the post-traversal sequence of a binary tree node is: A, C, B, D, F, E, and the middle-order traversal sequence is C, A, E, F, B, D. Please draw the binary tree.
Chapter 6 Hash Tables
Chapter 5 Unit test
1、The conflict resolution method in the scattered list ___________ is not the open address method.
A、Method of dividing residuals
B、Linear Probe Method
C、The Secondary Probe Act
D、Double hash method
2、There is a null hash list HT of length 11, insert 23, 89, 55, 46, 12, 7, 48, 66 in turn, please use the double hash method to solve the conflict, the hash function is h1(key)=key%11, h2(key)=key%9+1, 89 is stored in the hash list location is _____.
A、10
B、7
C、8
D、9
3、There is a hash list HT of length 11, insert 23, 89, 55, 46, 12, 7, 48, 66 in turn, please use the double hash method to solve the conflict, the hash function is h1(key)=key%11, h2(key)=key%9+1, 23 in the hash list storage location is _____.
A、1
B、0
C、2
D、3
4、Given an empty hash list of length 11, use linear probing to solve the conflict, the hash function is h(key)=key%11, please insert the collection elements of keywords 27,19,54,48,63 into the hash list in turn, after the insertion of 63 in the hash list storage location is ___________.
A、9
B、10
C、11
D、8
5、Given an empty hash list of length 7 ht, using the quadratic probe method to solve the conflict, the hash function is h(key)=key%7, please insert the set of keywords 20,11,55 to the hash list in turn, after the completion of the insertion of 55 in the hash list storage address is ________.
A、0
B、4
C、6
D、10
6、Given a null hash list ht of length 7, the conflict is resolved using the double hash method, with the two hash functions being. h1(key)=key%7 h2(key)=key%5+1 Insert the collection elements with the keywords 9, 16, 30 into the hash list, and store the address of 30 in the hash list as ________ after the insertion.
A、3
B、2
C、4
D、5
7、Given a null hash list ht of length 7, the conflict is resolved using the double hash method, with the two hash functions being. h1(key)=key%7 h2(key)=key%5+1 Insert the collection elements with keywords 30, 58, 65 into the hash list, and store the address 65 in the hash list as ________ after the insertion.
A、3
B、2
C、5
D、6
8、Given a null hash list ht of length 7, the conflict is resolved using the double hash method, with the two hash functions being. h1(key)=key%7 h2(key)=key%5+1 Insert the collection elements with the keywords 29, 64, 15 into the hash list, and store the address of 15 in the hash list as ________ after the insertion.
A、2
B、1
C、3
D、4
9、Given a null hash list ht of length 7, the conflict is resolved using the double hash method, with the two hash functions being. h1(key)=key%7 h2(key)=key%5+1 Insert the collection elements with keywords 35, 63, 21 into the hash list in turn, and store the address 21 in the hash list as ________ after the insertion.
A、2
B、1
C、3
D、4
10、The scattered list adopts the linear probe method to solve the conflict, and the storage position of the collection elements in the table is easy to join together, and the search efficiency is reduced, this phenomenon is called ________ (the test terms in this chapter are based on the video and the revised electronic textbook, the system does not support the semantic recognition function, please watch the video carefully).
11、The keywords in the hash list are not the same, but the data elements with the same hash value obtained by a given hash function are mutually called ________ (the terms tested in this chapter are based on the video and the revised electronic textbook, the system does not support the semantic recognition function, please watch the video carefully).
12、For a given hash function, the phenomenon of two data elements having the same hash value is called ______ (the test terms in this chapter are based on the video and the revised electronic textbook, the system does not support the semantic recognition function, please watch the video carefully).
13、The scattered list adopts the secondary probing method to resolve the conflict, the collection elements with the same base address have the same probing sequence, which will also cause a decrease in the search efficiency, this phenomenon is called ________ (the test terms in this chapter are based on the video and the revised electronic textbook, the system does not support the semantic recognition function, please watch the video carefully).
14、Given an empty hash list ht of length 7, use linear probing method to solve the conflict, the hash function is h(key)=key%7, please insert the set of keywords 92,29,16,17,25 to the hash list in turn, and the storage address of 25 after insertion is ________ (give the hash list location subscript).
15、Given an empty hash list ht of length 7, use linear probing method to solve the conflict, the hash function is h(key)=key%7, please insert the set of keywords 92,52,7,3,59 into the hash list in turn, the storage address of 59 after the completion of the insertion is ________ (give the hash list location subscript).
16、Given an empty hash list ht of length 7, use the quadratic probe method to solve the conflict, the hash function is h(key)=key%7, please insert the set of keywords 62,72,80 to the hash list in turn, after the insertion of 80 in the hash list storage address is ________ (give the hash list location subscript).
17、Given an empty hash list of length 7 ht, using the quadratic probe method to solve the conflict, the hash function is h(key)=key%7, please insert the collection of keywords 18,32,46 to the hash list in turn, after the insertion of 46 in the hash list storage address is ________ (give the hash list location subscript).
18、Given an empty hash list of length 7 ht, using the quadratic probe method to solve the conflict, the hash function is h(key)=key%7, please insert the set of keywords 35,21,7 to the hash list in turn, after the insertion of 7 in the hash list to store the address of ________ (give the hash list location subscript).
19、Given a null hash list ht of length 7, the conflict is resolved using the double hash method, with the two hash functions being. h1(key)=key%7 h2(key)=key%5+1 Insert a set of elements with the keywords 3, 17, 45 into the hash list, and store 45 in the hash list with the address ________ (give the hash list location subscript).
20、Given a null hash list ht of length 7, the conflict is resolved using the double hash method, with the two hash functions being. h1(key)=key%7 h2(key)=key%5+1 Insert the collection elements with the keywords 95, 25, 67 into the hash list, and store the address 67 in the hash list as ________ after the insertion.
Chapter 6 Homework
1、Given a hash table ht of length 13 as shown below, the linear probing method is used to resolve conflicts. The hash function is h(key)=key%13. Please insert keywords 55,35,88,98,26into the hash table in sequence. Please give the hash table after insertion.
2、Given a hash table ht of length 13 as shown below, the quadratic probing method is used to resolve conflicts. The hash function is h(key)=key%13. Please insert keywords 78,96,18, 2,40，into the hash table in sequence. Please give the hash table after the insertion.
3、3.Given a hash table ht of length 13 as shown below, the quadratic probing method is used to resolve conflicts. The hash function is h(key)=key%13. Please insert keywords 42,91,33, 73, 34 into the hash table and give the hash table after the insertion.
4、Given a hash table ht of length 13 as shown below, the double hash method is used to resolve conflicts. The two hash functions are: h1(key)=key%13 h2(key)=key%11+1 Please insert the set elements with keywords 61,35,59,93,78 into the hash table in sequence, and give the hash table after the insertion.
5、Given a hash table ht of length 13 as shown below, the double hash method is used to resolve conflicts. The two hash functions are: h1(key)=key%13 h2(key)=key%11+1 Please insert the set elements with keywords 30,22,87,57,82 into the hash table in sequence, and give the hash table after the insertion.
Chapter 7 Priority Queues
Chapter 7 Unit test
1、Please adjust the given data element sequence 71,28,21,72,92,73 to the smallest heap: _____________ (Hint: the adjustment process needs to call the AdjustDown method, please indicate the answer as an element sequence, separated by half-centred commas, no spaces in the answer).
2、Please adjust the given data element sequence 87,32,15,22,56,43 to the smallest heap: _____________ (Hint: the adjustment process requires calling the AdjustDown method, please indicate the answer as an element sequence, separated by half-centred commas, no spaces in the answer).
3、Please adjust the element sequence 36,65,42,54,98,76 of the given data to the smallest heap: _____________ (Hint: the adjustment process requires calling the AdjustDown method, please indicate the answer as an element sequence, separated by half-centred commas, no spaces in the answer).
4、Please adjust the given data element sequence 72,46,24,44,91,96 to the maximum heap: _____________ (Hint: the adjustment process requires calling the AdjustDown method, please indicate the answer as an element sequence, separated by half-centred commas, no spaces in the answer).
5、Insert elements 84 into the largest heap 71,69,32,25,33,15 in turn, the final largest heap is ________________ (hint: the heap of element insertion operations need to call the AdjustUp method, please indicate the answer as a sequence of elements, separated by half-centred commas, no spaces in the answer).
6、Insert elements 82,86,88,97,81 into the largest heap 92,54,65,18,36,53 in turn, and the final largest heap is _____________ (hint: the heap element insertion operation needs to call the AdjustUp method, please express the answer as a sequence of elements, separated by half-centred commas, no spaces in the answer).
7、Insert elements 94,99,89,80,94 into the largest heap 84,49,82,26,29,46 in turn, and the final largest heap is _____________ (hint: the heap element insertion operation needs to call the AdjustUp method, please express the answer as a sequence of elements, separated by half-centred commas, no spaces in the answer).
8、Insert elements 86,91,91,94,97 into the largest heap 99,72,76,7,30,41 in turn, and the final largest heap is _____________ (Hint: the heap element insertion operation needs to call the AdjustUp method, please express the answer as a sequence of elements, separated by half-centred commas, no spaces in the answer).
9、Perform a delete operation on the largest heap sequence 95,61,66,9,19,27 (hint: perform a delete operation on the priority queue to delete the top element of the heap by default) and get the largest heap sequence ______ (hint: the heap element delete operation needs to call the AdjustDown method, please indicate the answer as an element sequence, separated by half-centred commas, no spaces in the answer)
10、Perform 2 deletion operations on the smallest heap sequence 10,21,70,27,31,83 (hint: perform the deletion operation on the priority queue to delete the top element of the heap by default) and get the smallest heap sequence ______ (hint: the heap element deletion operation needs to call the AdjustDown method, please indicate the answer as an element sequence, separated by half-centred commas, no spaces in the answer)
11、Execute three deletion operations on the largest heap sequence 59,55,57,50,45,22 (hint: Execute the deletion operation on the priority queue to delete the top element of the heap by default) and get the largest heap sequence ______ (hint: The heap element deletion operation needs to call the AdjustDown method, please express the answer as an element sequence, separated by half-centred commas, no spaces in the answer)
12、Perform a delete operation on the largest heap sequence 61,56,48,23,53,19 (hint: perform a delete operation on the priority queue to delete the top element of the heap by default) and get the largest heap sequence ______ (hint: the heap element delete operation needs to call the AdjustDown method, please indicate the answer as an element sequence, separated by half-centred commas, no spaces in the answer)
Chapter 7 Homework
1、Please adjust the given data element sequence 84,23,32,54,16,97 to the maximum heap.
2、Insert elements 1,6 into the minimum heap 35,75,37,85,93,72 in sequence, please give the final minimum heap.
3、Perform two delete operations on the minimum heap sequence 14,39,50,79,95,59, please give the minimum heap finally obtained.
Chapter 8 Introduction to Graphs
Chapter 8 Unit test
1、If there are n vertices in a strong connection graph, the strong connection graph has at most ( ) sides.
A、n*(n-1)
B、n
C、n*(n-1)/2
D、n*(n+1)
2、The set of sides of a known graph : Then the sequence ________ is one of the topological sequences of the graph.
A、4, 5, 6, 1, 2, 3
B、6, 3, 4, 5, 1, 2
C、6, 1, 2, 3, 4, 5
D、4, 3, 5, 2, 1, 6
3、Assuming that there are n vertices and e edges in the directionless graph G, the number of vertex nodes and edge nodes corresponding to them in the adjacency table is _____.
A、n and 2e
B、n and e
C、e and n
D、2n and e
4、An ordinate graph with n vertices (n>1) must have at least ________ sides to be a strongly connected graph.
A、n
B、n-1
C、n(n-1)
D、n(n-1)/2
5、An indirectional graph with n vertices, containing 2 connected components, has at least ________ sides.
A、n-2
B、n-1
C、n
D、n+1
6、A directed graph with n vertices (n>2) containing 2 strongly connected components has at least _____ sides.
A、n-1
B、n-2
C、n
D、n+1
7、An indirectional graph with n vertices, containing four connected components, has at least ________ sides.
A、n-4
B、n-3
C、n-2
D、n-1
8、A directed graph with n (n>3) vertices containing three strongly connected components has at least ________ sides.
A、n-2
B、n-3
C、n-1
D、n
9、Regarding the topological sorting algorithm, the following statement is incorrect ________.
A、The larger the entry value of the vertex, indicating that the more preconditions it has, the further back it must be in the topological sequence
B、The correct topological sequence can only be obtained by entering the DAG plot
C、Algorithm error if non-DAG graph is entered
D、The topological sequence of a given DAG graph may not be unique
10、The set of edges of figure G is known to be. Then the entry of vertex 0 is __________.
11、The basic storage structure of the Graph includes ______ and the adjacency table representation (fill in the terms defined in the textbook).
12、The set of edges of figure G is known to be. The vertex 2 entry is __________.
13、The set of edges of the graph is known: If the neighbor table is stored, there are ______ edge nodes in the chain table of edge nodes corresponding to vertex 4.
14、The set of edges of the graph is known: If the adjacency table is stored, there are ______ edge nodes in the chain table of edge nodes corresponding to vertex 5.
15、The set of edges of the graph is known: If the adjacency table is stored, there are ______ edge nodes in the chain table of edge nodes corresponding to vertex 2.
16、Set of sides of a known graph If adjacency table storage is used, there are ______ vertices adjacent to 4.
Chapter 8 Homework
1、For the directed graphs in the figure: 1) Please give the indegree of each vertex; (2) Please give the adjacency matrix; (3) Please draw all strongly connected components.
2、Draw the adjacency matrix of the undirected graph in the figure.
3、Given a directed graph with only 7 vertices (vertices are numbered from 0) without edges, the graph is stored in adjacency list, and now use the Insert function on the textbook to insert the following edges in order: <0,1>,<0,2>,<1,6>,<2,4>,<3,5>,<4,6>,<4,1>, please draw the constructed adjacency list .
Chapter 9 Graph Traversal
Chapter 9 Unit test
1、Given a set of sides with a vector map. The following sequence is ______, which is not the topological sequence of the graph.
A、0,1,2,3,4,5,6
B、0,1,2,3,4,6,5
C、0,2,4,1,6,5,3
D、0,2,4,1,6,3,5
2、The following option ______ is not the depth-first traversal sequence in the figure below.
A、A,B,C,E,F,D,J,H,I,G,K,O,L,M,N
B、A,B,C,E,F,D,K,G,I,H,J,L,M,N,O
C、A,B,C,E,D,K,G,I,H,J,F,O,M,N,L
D、A,B,C,E,J,H,I,G,K,D,F,O,M,N,L
3、The following option ______ is the depth-first traversal sequence in the figure below.
A、K,D,A,B,E,C,F,G,J,H,I
B、K,D,A,B,E,C,F,J,H,I,G
C、J,H,I,G,E,C,F,K,D,A,B
D、J,H,I,G,E,F,C,K,D,A,B
4、The following option ______ is the width-first traversal sequence of the figure below.
A、K,D,G,A,E,B,C,F,J,H,I
B、K,D,G,A,E,C,B,F,J,H,I
C、K,D,A,E,B,C,F,J,H,I,G
D、K,D,G,A,B,C,F,J,E,H,I
Chapter 9 Homework
1、The adjacency list of known graph G is shown in the figure. 1. Perform a depth-first search traversal on this adjacency list and give the traversal sequence; 2. Please draw the spanning forest obtained by depth-first traversal process; 3. Perform a breadth-first traversal on this adjacency list and give the traversal sequence; 4.Please draw the spanning forest obtained by the width-first traversal process.
2、As shown in the directed graph, please give the topological sorting sequence of the directed graph.
Chapter 10 Minimum Spanning Trees
Chapter 10 Unit test
1、The minimum spanning trees of the following figure is constructed using Primm's algorithm, starting from A, and the third bar is added to the generation tree with a side of ______.
A、(D,E)
B、(A,B)
C、(D,K)
D、(E,C)
2、The minimum spanning trees of the following figure is constructed using Primm's algorithm, starting with B, and the third bar is added to the generation tree with a side of ______.
A、(E,J)
B、(C,F)
C、(E,C)
D、(D,E)
3、Using Primm's algorithm to construct the minimum spanning trees of the following graph, starting from E, then the edges (J,H) must be the edges of the 5th article added to the generation tree.
4、Using Kruskal's algorithm to construct the minimum spanning trees for the following figure, the first edge that is added to the generation tree must be (E,C).
5、Using Kruskal's algorithm to construct the minimum spanning trees for the following figure, the last edge that is added to the generation tree must be (A,B).
6、Using Kruskal's algorithm to construct the minimum spanning trees for the following figure, the last edge that is added to the generation tree must be (D,K).
7、The single source shortest path algorithm can be used to find the shortest path between any two vertices in the graph
Chapter 9 Homework
1、Use Prim algorithm to construct the minimum spanning tree of the connected graph shown in the figure below, starting with A. Please draw the construction process. Tip: The construction process is divided into 5 steps.
2、Use the Kruskal algorithm to construct the minimum cost spanning tree of the connected graph shown in the figure below. Please draw the construction process of the minimum cost spanning tree.
学习通Data Structures
数据结构是计算机科学的重要基础，也是开发软件的关键部分之一。学习通Data Structures是一门为初学者设计的数据结构课程，它以简单易懂的方式介绍了数据结构的基本概念和实现方法。
课程概述
学习通Data Structures课程由四个部分组成：
- 线性数据结构：介绍了数组、链表、队列和栈等基本数据结构，以及它们的实现和应用；
- 树：介绍了二叉树、AVL树、红黑树等树形数据结构，以及它们的实现和应用；
- 图：介绍了图论基本概念、最短路径算法、最小生成树算法等图形数据结构，以及它们的实现和应用；
- 高级数据结构：介绍了哈希表、堆等高级数据结构，以及它们的实现和应用。
课程特点
学习通Data Structures有以下几个特点：
- 内容简单易懂：该课程针对初学者，教材和讲解都非常简单易懂；
- 实用性强：该课程介绍的数据结构都是非常实用的，可以帮助学生快速理解并应用在实际项目中；
- 适合自学：该课程提供了丰富的案例和代码实现，可以帮助学生自学。
学习建议
学习通Data Structures虽然内容简单易懂，但是想要真正掌握这门课程，需要学生付出较大的努力。
以下是一些学习建议：
- 跟着课程实现代码：该课程提供的代码实现非常清晰明了，建议学生跟着课程一步一步进行实现；
- 多做练习：该课程提供了许多练习题，建议学生多做练习，以巩固所学知识；
- 阅读相关书籍：如果想要更深入地了解数据结构，建议学生阅读相关书籍，如《算法导论》等。
总结
学习通Data Structures是一门非常优秀的数据结构课程，它简单易懂、实用性强、适合自学。通过该课程的学习，不仅可以掌握基本的数据结构概念和实现方法，还可以为日后的软件开发打下坚实的基础。
中国大学Data Structures
数据结构是计算机科学中的重要概念。在中国大学的计算机科学课程中，Data Structures（数据结构）是一个非常重要的课程，它为学生提供了理解和实践数据结构的基础知识。
课程概述
中国大学Data Structures课程涵盖了各种数据结构的基本概念，包括链表、栈、队列、树、二叉树、平衡树、图等等。课程的重点是教授如何在不同情况下选择合适的数据结构，以及如何在数据结构中实现基本操作，如插入、删除和搜索等。
在许多大学中，Data Structures课程是计算机科学专业的重要先修课程，它为后续学习提供了必要的基础。在中国大学中，Data Structures课程通常是计算机科学专业中的必修课程，学生需要在大约两个学期内完成该课程的学习。
课程内容
课程内容通常从基础的数据结构开始，如线性数据结构（链表、栈、队列等），然后继续介绍非线性数据结构，如树、二叉树、平衡树、图等。课程的重点是如何在这些数据结构中实现基本操作，并且如何在不同情况下选择合适的数据结构。
课程还涵盖了一些重要的算法，如排序算法（冒泡排序、快速排序、归并排序等）和搜索算法（二分搜索、广度优先搜索、深度优先搜索等）。这些算法通常与特定的数据结构相关联，因此在学习这些算法时需要对相关数据结构有深入的了解。
课程目标
中国大学Data Structures课程的主要目标是让学生掌握数据结构的基本概念和实践技能。学生应该能够：
- 理解各种数据结构的基本概念和实现方式
- 能够在不同情况下选择合适的数据结构
- 能够对数据结构进行基本操作，如插入、删除和搜索等
- 理解和实现各种重要的算法，如排序算法和搜索算法
- 能够应用数据结构和算法解决实际问题
课程难度
中国大学Data Structures课程通常被认为是计算机科学专业中的难点课程之一。课程内容相对较为抽象，需要对数学和算法有一定的理解和掌握。
学生需要花费大量的时间和精力来学习这门课程。例如，学生需要花费时间来思考如何在不同情况下选择合适的数据结构，以及如何实现各种操作。此外，学生还需要掌握各种算法和数据结构的性能分析方法，以便评估它们在实际应用中的效率。
课程评估
中国大学Data Structures课程通常通过考试和作业来评估学生的掌握情况。考试通常包括理论和实践两部分，理论部分考察学生对数据结构和算法的理解和知识掌握情况，实践部分则要求学生在计算机上实现基本操作，并应用算法和数据结构解决一些具体的问题。
作业通常是编程练习，要求学生实现特定的数据结构和算法，并对其进行性能评估。作业的目的是帮助学生巩固课程内容，并提高他们的实践能力。
课程培养目标
中国大学Data Structures课程是计算机科学专业中的关键课程之一。它为学生提供了深入理解和实践数据结构的机会，为后续学习和职业发展打下了坚实的基础。
通过学习这门课程，学生应该能够掌握数据结构和算法相关的核心概念和技能，并能够应用它们解决实际问题。这些技能和知识对于计算机科学专业的学生来说是至关重要的，也是他们实现自己的职业目标所必需的基础。
总结
中国大学Data Structures课程是计算机科学专业中的重要课程，它为学生提供了深入理解和实践数据结构的机会。学生需要花费大量时间和精力来学习这门课程，但他们的努力将会得到回报，因为这些技能和知识对于他们实现职业目标来说是必不可少的。
