2020 Data Structures(南京邮电大学) 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2020-04-09到2020-07-15
本篇答案更新状态:已完结

Chapter 1 Introduction 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
答案: 【A good algorithm will not appear inexplicable due to illegal input data.】

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
答案: 【Linear Structure and Nonlinear 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.
答案: 【Not necessarily continuous】

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
答案: 【Linear structure, nonlinear structure】

5、 问题:The four basic logical structures are set structure, ____ structure, graph structure, and tree structure.
答案: 【linear】

6、 问题:The four basic logical structures include linear structures, ____ structures, graphical structures, and tree structures.
答案: 【set】

7、 问题:The four basic logical structures are set structure, ____ structure, linear structure, and tree structure.
答案: 【graph】

8、 问题:The four basic logical structures are set structure, ____ structure, linear structure, and graphical structure.
答案: 【tree】

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).
答案: 【21,28,71,72,92,73】

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).
答案: 【15,22,43,32,56,87】

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).
答案: 【36,54,42,65,98,76】

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).
答案: 【96,91,72,44,46,24】

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).
答案: 【84,69,71,25,33,15,32】

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).
答案: 【97,92,82,86,88,53,65,18,54,36,81】

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).
答案: 【99,94,84,89,94,46,82,26,49,29,80】

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).
答案: 【99,97,86,91,94,41,76,7,72,30,91】

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)
答案: 【66,61,27,9,19】

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)
答案: 【27,31,70,83】

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)
答案: 【50,45,22】

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)
答案: 【56,53,48,23,19】

【作业】Chapter 3 Linear Data Structures 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.
评分规则: 【 void Invert(SeqList *L) {ElemType temp; int i; for ( i=0; i<L->n/2; i++) {     temp =L->element[i];     L->element[i] = L->element[L->n-i-1];     L->element[L->n-i-1] = temp; }}评分要点：语法错误不扣分，一个空7分
】

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.
评分规则: 【 void invert(SingleList L) { Node p=L->first,*q; L->first=NULL; while (p) {     q=p->link;     p->link=L->first;     L->first=p;     p=q; } }评分标准：一个空7分，语法错误不扣分
】

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; }
评分规则: 【 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(pa->element<pb->element) {            pc->link=pa;            pc=pa;            pa=pa->link;            La->n–; }     else if(pa->element>pb->element) {            pc->link=pb;            pc=pb;            pb=pb->link;           Lb->n–; }       else {            pc->link=pa;            pc=pa;            pa=pa->link;            q=pb->link;            free(pb);            pb =q; } Lc->n++; } pc->link=pa?pa:pb; //插入剩余段 Lc->n+=pa?La->n:Lb->n; }评分要点：一空5分
】

【作业】Chapter 2 Complexity Theory 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)
评分规则: 【 执行次数为n写成n+1或者n-1或者O(n)扣5分
渐进时间复杂度为O(n)没有写大O扣5分
】

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);
评分规则: 【 执行次数上下限写错或没有上下限得8分，写成对数形式但是底数写错得5分，写成近似时间复杂度或者其他答案不给分
渐近时间复杂度评分要点：没有大O扣5分；括号内公式写错扣5分；
】

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;
评分规则: 【 答案：执行次数为评分要点：写成带大O的形式扣5分
答案：渐近时间复杂度是评分要点：没有写大O扣5分
】

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>=yy)         y++;
评分规则: 【 答案：执行次数是解析：设下划线语句执行次数为t，进行递推：第1次执行后，y=1，如果 n>=11 时，则有下一趟第2次执行后，y=2，如果 n>=22 时，则有下一趟….第t次执行后，y=t，此时为最后1趟，满足 n<tt 时，因此不会有t+1趟因此t=评分要点：向上取整写成向下取整扣1分，没有取整符号扣2分
答案：渐进时间复杂度是评分要点：没有大O扣5分
】

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.
答案: 【Scale of the problem】

2、 问题:The calculation amount of algorithm is called the _____ of the calculation.
选项：
A:Time Complexity
B:Efficiency
C:Reality
D:Difficulty
答案: 【Time Complexity】

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:
答案: 【O(n^2)】

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");        }    }}
答案: 【O(n^2)】

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", i);    }}
答案: 【O(logn)】

7、 问题:The asymptotic time complexity of the algorithm is __ if the number of key steps of the algorithm is .
答案: 【O(n^2)】

8、 问题:The asymptotic time complexity of the algorithm is __ if the number of key steps of the algorithm is 
答案: 【(以下答案任选其一都对)O(mlogn+m^3);
O(m^3+mlogn)】

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
答案: 【Sequential 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.
答案: 【Each element has a direct antecedent and a direct successor except the first element and the last element】