数据结构(西北大学) 中国大学mooc慕课答案2024版 m106290

第一章 绪论（总时长：56分26秒，共6讲） 第一章 单元测试

1、 下面程序段的时间复杂度为（   ）。for(int i=0;i<m;i++)  for(int j=0;j<n;j++)     a[i][j]=ij;

A:O(m2)
B:O(n2)
C:O(mn)
D:O(m+n)
答案: O(m*n)

2、 执行下面程序段时，语句S的执行次数为（   ）。for(int i=0;i<=n;i++)  for(int j=0;j<=i;j++)    S;

A:nn
B:nn/2
C:(n+1)(n+2)/2 
D:n(n+1)/2
答案: (n+1)(n+2)/2 

3、 评价一个算法性能好坏的最重要标准是（  ）。

A:算法的鲁棒性
B:算法的可读性
C:算法的时间复杂度和空间复杂度 
D:算法的正确性    
答案: 算法的时间复杂度和空间复杂度 

4、 算法的时间复杂度与（    ）有关。

A:问题规模 
B:计算机硬件性能 
C:编译程序质量 
D:程序设计语言
答案: 问题规模 

5、 算法分析的主要任务是分析（   ）。

A:算法是否具有较好的可读性  
B:算法中是否存在语法错误
C:算法的功能是否符合要求    
D:算法的执行时间与所需空间与问题规模的关系
答案: 算法的执行时间与所需空间与问题规模的关系

6、 算法分析的目的是(   )。

A:找出数据结构的合理性
B:研究算法中输入和输出的关系
C:分析算法的时空效率以求改进
D:分析算法的可读性
答案: 分析算法的时空效率以求改进

7、 数据的最小单位是（  ）。

A:数据项 
B:数据类型 
C:数据元素 
D:数据变量
答案: 数据项 

8、 某算法的时间复杂度是O（nn）,表明该算法的（   ）。

A:问题规模是nn
B:问题规模与nn正比    
C:执行时间与nn正比 
D:执行时间等于nn
答案: 执行时间与nn正比 

9、 如下程序段:   for(i=1;i<=n-1;i++)    for(j=i+1;j<=n;j++)                   x=x+1;其中语句x=x+1执行的语句频度为（    ）。

A:nn
B:n(n-1)/2
C:n(n+1)/2
D:n(n-1)
答案: n*(n-1)/2

10、 以下算法的时间复杂度为（   ）。if (n >= 0) {      for(int i = 0; i < n; i++)         for(int j = 0; j < n; j++)               printf(“输入数据大于等于零”);    } else {          for(int j = 0; j < n; j++)           printf(“输入数据小于零”); }

A:O(1)
B:O(nn+n)
C:O(n)
D:O(nn)
答案: O(n*n)

11、 在数组A[0..n-1]中查找给定值K的算法大致如下：   i=n-1;            while(i>=0 && (A[i]!=k))             i–;        return i;  该算法的时间复杂度为（    ）。

A:O(n-i+1)
B:O(n-i)
C:O(n)
D:无法确定
答案: O(n)

12、 下面算法的时间复杂度为（    ）。x=100; y=100;while(y>0)      if(x>100)         {x=x-10; y–;}      else           x++;

A:O(n)
B:O(100)
C:O(1)
D:O(n*n)
答案: O(1)

13、 假设sqrt(n)函数中涉及的算法时间复杂度为O(1)，那么下面的算法是判断n是否为素数，其时间复杂度为（      ）。void prime(int n){   for (i=2; i<sqrt(n) && (n % i)!=0; i++) ;    if (i>sqrt(n))            printf(“%d is a prime number”, n);     else          printf(“%d is not a prime number”, n);} 

A:O(n)
B:O(1)
C:O(sqrt(n))    sqrt表示对n取根方
D:O(n-i)
答案: O(sqrt(n))    sqrt表示对n取根方

14、 某算法中，执行频率最高的语句的执行次数为    则该算法的时间复杂度应该是（   ）。

A:T(n) = O(nnn)
B:T(n) = O(nn)
C:T(n) = O(   (nnn+nn+n)/n  )
D:T(n) = O(nn+n)
答案: T(n) = O(nn)

15、 数据结构中，数据处理的最小单位是（    ）。

A:数据
B:数据对象
C:数据元素
D:数据项
答案: 数据元素

16、 以下属于数据元素间基本逻辑结构的是（    ）。

A:集合
B:线性
C:树
D:图
答案: 集合;
线性;
树;
图

17、 以下属于算法特性的是（    ）。

A:0个或多个输入；至少1个输出
B:正确性
C:确定性
D:可行性和有限性
答案: 0个或多个输入；至少1个输出;
确定性;
可行性和有限性

18、 算法设计的要求包括（   ）。

A:正确性
B:可读性
C:健壮性
D:高效率和低存储
答案: 正确性;
可读性;
健壮性;
高效率和低存储

19、 数据元素在计算机内存中的存储映像包括（   ）。

A:顺序存储
B:非顺序存储
C:图结构
D:树结构
答案: 顺序存储;
非顺序存储

20、 抽象数据类型包括了（    ）。

A:一个数据对象
B:元素的存储结构
C:元素间的关系
D:一组操作
答案: 一个数据对象;
元素间的关系;
一组操作

21、 具有线性结构的元素只能用顺序存储，具有非线性结构的元素只能非顺序存储。

A:正确
B:错误
答案: 错误
分析：线性、非线性结构是元素间的逻辑关系。
顺序、非顺序存储时元素的存储结构。
二者没有明显的一一对应关系。

也就是说，无论元素的逻辑关系如何，顺序和非顺序存储结构都是可以的。

22、 算法就是程序。

A:正确
B:错误
答案: 错误
分析：程序是用某种程序设计语言对算法的实现。二者不同。

23、 算法的优劣与算法描述的语言无关。

A:正确
B:错误
答案: 正确

24、 算法的可行性是指每一条指令具有明确含义。

A:正确
B:错误
答案: 错误
分析：可行性指算法咋原则上要能实现；每一条指令需要由明确含义是算法的确定性。

25、 健壮的算法不会因为非法输入数据而出现莫名的执行结果。

A:正确
B:错误
答案: 正确

26、 算法设计的要求就是要设计高效率和低存储的算法。

A:正确
B:错误
答案: 错误
分析：二者是算法的设计要求，但不是全部。还包括正确性、可读性、鲁棒性（健壮性）

27、 数据类型就是变量。

A:正确
B:错误
答案: 错误
分析：数据类型是一组性质相同的元素及在其上的一组操作的总称。其并不占内存空间。
而变量是某种数据类型具体表现，需要占内存空间。

28、 数据元素的存储结构分为顺序存储和非顺序存储。

A:正确
B:错误
答案: 正确

29、 数据元素的顺序存储结构优于非顺序存储。

A:正确
B:错误
答案: 错误
分析：哪种存储结构更优，取决于其操作。二者各有优缺点。

30、 元素间的逻辑关系可分为线性和非线性关系两种。

A:正确
B:错误
答案: 错误
分析：还有集合结构，既不属于线性，也不属于非线性。集合结构中，元素间没有任何关系。

第二章 线性表（一）（总时长：72分22秒，共6讲） 第二章 单元测试（1）

1、 在长度为n的顺序表中的第i( 1 <=  i <= n+1 )个位置上插入一个元素，其算法时间复杂度为（  ）。

A:O(logn)(以2为底)
B:O(1)  
C:O(n)   
D:O(n*n)
答案: O(n)   

2、 在长度为n的顺序表中的第i( 1 =< i <= n+1 )个位置上插入一个元素，需要移动的元素个数为（   ）。

A:n-i
B:i
C:n-i+1
D:n-i-1
答案: n-i+1

3、 链表不具有的特点是（  ）。

A:插入、删除不需要移动元素
B:可随机访问任一元素
C:不必事先估计存储空间
D:所需存储空间与线性表程度成正比
答案: 可随机访问任一元素

4、 在一单链表中，删除指针p所指的后继结点，以下语句正确的是（   ）。

A:p->next=p->next->next;  free(p->next);
B:free(p->next);p->next=p->next->next;
C: p=p->next;
D:s=p->next;p->next=s->next;free(s);
答案: s=p->next;p->next=s->next;free(s);

5、 假设删除长度为n的顺序表中的每个元素的概率相同，则删除一个元素平均要移动的元素个数是（  ）。

A:n
B:(n+1)/2
C:(n-1)/2
D:n/2
答案: (n-1)/2

6、 设某顺序表中第一个元素的地址是Base，每个结点占m个单元，则第i个结点的地址为（ ）。

A:Base+(i-1)×m              
B:Base+i×m          
C:Base-i×m              
D:Base+(i+1)×m 
答案: Base+(i-1)×m              

7、 长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是（  ）。

A:i>0    
B:1≤i≤n+1 
C:1≤i≤n-1
D:0≤i≤n+1
答案: 1≤i≤n+1 

8、 非空单链表结点结构为data,next，若指针p所指结点是尾结点，则（   ）表达式为真。

A:p==NULL
B:p->next==NULL
C:p->next==P
D:p->next!=NULL
答案: p->next==NULL

9、 某顺序表的第一个元素的存储地址是500，每个元素占4个单元，则第8个元素的起始地址是(    )。

A:504
B:508
C:516
D:528
答案: 528

10、 在长度为n的顺序表中删除第i(1<=i<=n)个位置上的元素，需要移动的元素个数为（   ）。

A:n-i
B:n-i+1
C:n-i-1
D:i
答案: n-i

11、 在长度为n的顺序表中的的末尾位置上插入一个元素，其算法时间复杂度为（  ）。

A:O(1)
B:O(n)
C:O(logn）（以2为底）
D:O(nlogn)
答案: O(1)

12、 以下算法的功能是在一个非递减的顺序存储线性表中，删除所有值相等的多余元素。时间复杂度为O(n)，空间复杂度为O(1)。划线部分应填入的语句是（   ）。void DelRepeatData(SeqList *L){ i=0; j=1; while( j<=L->last) { if(L->elem[i]==L->elem[j])                                      ; else { L->elem[i+1]=L->elem[j]; i++; j++; } }    L->last=i;}

A:i++
B:j++
C:i–
D:j–
答案: j++

13、 以下算法是删除带头结点单链表L中的最小的元素，横线处应填入的语句是（    ）。void DelMinNode(LinkList L){   p=L->next;  pre=L;   if(L==NULL)  return;   while(p->next!=NULL)  //pre指向最小元素的前驱元素，开始默认第一个结点最小，pre指向头结点   {        if(p->next->data < pre->next->data)                           pre=p;  }   //删除pre后面的结点   p=pre->next;                             ;}

A:free(p); pre->next=p->next;
B:free(p->next);pre->next=p->next;
C:pre->next=p->next; free(p); 
D:p->next=pre->next;free(p);
答案: pre->next=p->next; free(p); 

14、 单链表中增加头结点的目的是存储链表的长度。

A:正确
B:错误
答案: 错误
分析：添加头结点的目的是，简化操作，使得在表头和中间位置对链表的操作统一化。不一定是为了存储链表的长度。

15、 线性表在链式存储时，查找第i个元素的时间同i的值无关。

A:正确
B:错误
答案: 错误

16、 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比。

A:正确
B:错误
答案: 错误
分析：顺序表中，查找第i个元素，时间是常量。

17、 线性表的特点是每个元素都有一个前驱和一个后继。

A:正确
B:错误
答案: 错误
分析：首元素没有前驱，尾元素没有后继。

18、 线性表的链式存储结构优于顺序存储。

A:正确
B:错误
答案: 错误
分析：两种存储结构各有优缺点。要根据实际问题选择合适的存储结构。

19、 顺序存储方式的优点是存储密度大，插入、删除效率高。

A:正确
B:错误
答案: 错误
分析：前半句正确，后半句错误。
顺序存储中，插入和删除的效率比较低。

20、 顺序表的每个结点只能是一个基本类型，而链表的每个结点可以是一个构造类型。

A:正确
B:错误
答案: 错误

21、 插入和删除操作是线性表的基本操作。这两种操作在数组中也经常使用。

A:正确
B:错误
答案: 错误
分析：数组本身不能进行插入和删除，因为数组的长度是不可变的。（在某些语言中）

22、 在顺序表中，逻辑上相邻的两个元素物理存储上也一定也相邻。

A:正确
B:错误
答案: 正确

23、 在线性表的链式存储结构中，逻辑上相邻的两个元素在物理存储上并不一定紧邻。

A:正确
B:错误
答案: 正确

24、 线性表采用顺序存储，必须占用一段地址连续的存储单元。

A:正确
B:错误
答案: 正确

25、 顺序表结构适宜进行随机访问，而链表适宜进行插入、删除。

A:正确
B:错误
答案: 正确

第二章 线性表（二）（总时长：59分37秒） 第二章 单元测试（2）

1、 非空循环单链表L中，p指针指向尾结点，则以下表达式可能成立的是（  ）。

A:p->next==NULL
B:p==NULL
C:p->next==L
D:p==L
答案: p->next==L

2、 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（   ）存储方式最节省时间。

A:顺序表    
B:双向链表
C:带头结点的双循环链表
D:单循环链表
答案: 顺序表    

3、 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（   ）存储方式最节省运算时间。

A:单链表  
B:仅有头指针的单循环链表 
C:双链表
D:带尾指针的单循环链表
答案: 带尾指针的单循环链表

4、 对于双向循环链表，在两个结点之间插入一个新结点需修改的指针共（  ）个。

A:2
B:3
C:4
D:5
答案: 4

5、 将带头指针的长度为m的单链表，链接到同样带头指针的长度为n的单链表末尾。该算法的时间复杂度为(   )。

A:O(m)
B:O(n)
C:O(m+n)
D:O(m*n)
答案: O(n)

6、 在某双向链表中删除一个结点，需要改动（   ）个指针域。

A:1
B:2
C:3
D:4
答案: 2

7、 某双向链表中，结点结构为prior,data,next。那么删除p指针所指结点时，需要执行语句：p->next->prior=p->prior;  (                ); free(p);

A:p->prior->next = p->next
B:p->next = p->prior
C:p->prior = p->next
D:p->prior->next = p
答案: p->prior->next = p->next

8、 在一个长度大于2的单循环链表L中，P指针指向某结点，在P前插入S结点，要求在O(1)时间复杂度内完成，以下正确的是（   ）。

A:s->next=p->next;p->next=s;  //将s结点插入到p之后t=s->data;s->data=p->data;p->data;   //s结点和p结点的值互换
B:q=p->next;while(q->next!=p)  q=q->next;s->next=p; q->next=s;
C:q=p->next;while(q->next!=p)  q=q->next;q->next=s; s->next=p;
D:在p结点前插入s结点，而且要求在O(1)内，无法实现。
答案: s->next=p->next;p->next=s;  //将s结点插入到p之后t=s->data;s->data=p->data;p->data;   //s结点和p结点的值互换

9、 两个单链表，可能相交，也可能不相交。如果相交，则从交点开始，合并为一个链表。设计一个算法那，判断两个链表是否相交，如果相交，求出相交的第一个结点。以下哪种说法正确（   ）。

A:可采用以下算法实现：第一步：先将两个链表各自遍历一遍，统计出两个单链表的长度m和n。假设m>n，k=m-n第二步：长链表先走k步：用指针p从长链表头开始，先走k步，此时p指向长链表的第k+1个结点。第三步：q从短链表头开始，和p一起走。p和q相等时，即为交点；如果p和q不相交，则两个链表不相交。
B:可采用以下算法实现：第一步：用两个指针p和q，分别从两个链表头开始，向后走。第二步：如果两个指针相等，即指向同一个结点，则说明相交，该结点就是交点。
C:可采用以下算法实现：第一步：将两个链表分别逆置。第二步：从头开始，什么时候链表分叉，该分叉的结点就是相交的结点。
D:该问题无法求解。
答案: 可采用以下算法实现：第一步：先将两个链表各自遍历一遍，统计出两个单链表的长度m和n。假设m>n，k=m-n第二步：长链表先走k步：用指针p从长链表头开始，先走k步，此时p指向长链表的第k+1个结点。第三步：q从短链表头开始，和p一起走。p和q相等时，即为交点；如果p和q不相交，则两个链表不相交。

10、 编写高效算法，找出链表的中间结点。以下哪个算法更高效（   ）。

A:采用快慢指针方法。即：第一步：一个指针走的快，每次走2个结点；一个指针走的慢，每次走1个结点。第二步：当快指针到结尾或空时，慢指针所指结点即为中间结点。注：遇到链表结点为奇数或偶数时，需稍加改进即可。
B:第一步：遍历一遍链表，求出其长度n。第二步：再从头开始遍历链表，到n/2处即可。若n为偶数，中间结点则有2个；若n为奇数，则只有1个。需稍加处理。
C:第一步：将链表中的结点依次放入一个数组中，同时记录结点个数；第二步：数组中间位置即为中间结点。
D:无法实现
答案: 采用快慢指针方法。即：第一步：一个指针走的快，每次走2个结点；一个指针走的慢，每次走1个结点。第二步：当快指针到结尾或空时，慢指针所指结点即为中间结点。注：遇到链表结点为奇数或偶数时，需稍加改进即可。

11、 为了逆序输出单链表中的结点，以下哪些算法无法实现该功能（  ）。

A:第一步：将单链表逆置；第二步：输出单链表中的元素；第三步：将单链表逆置，即恢复之前的单链表。
B:第一步：将单链表中的 元素依次放入一个数组中第二步：逆序输出该数组中的元素。
C:可用如下代码实现：void reversePrint(Node *p//p初值为单链表第一个结点{       while(p!=NULL)      {  reversePrint(p->next);         printf(“%c  “,p->data);  //假设结点值为字符}
D:算法思想：第一步：从头到尾找到最后一个结点；第二步：从最后一个结点向前依次输出每个结点的值。
答案: 算法思想：第一步：从头到尾找到最后一个结点；第二步：从最后一个结点向前依次输出每个结点的值。

12、 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。

A:正确
B:错误
答案: 错误
分析：静态链表本质仍然是链表，所以它不具有顺序表的优点。

13、 循环单链表中，每个结点都有一个前驱和后继，因此循环单链表不是线性结构。

A:正确
B:错误
答案: 错误
分析：前驱和后继是元素间的逻辑关系。
循环单链表是元素的存储关系，只是为了操作方便而采用循环链表，并不会改变元素的逻辑关系。

下方是付费阅读内容：本平台商品均为虚拟商品，无法用作二次销售，不支持退换货，请在购买前确认您需要购买的资料准确无误后再购买，望知悉！

完整答案需点击上方按钮支付5元购买,所有答案均为章节测试答案，购买后上方矩形框将出现已付费的隐藏内容。

不知道怎么购买？点此查看购买教程！