2020 数据结构(东北大学) 最新满分章节测试答案

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

第一章 绪论 单元测试一

1、 问题:利用数据元素在计算机存储器的相对位置来表示数据元素之间的逻辑关系，称之为_____存储结构。
选项：
A:物理
B:逻辑
C:顺序
D:链式
答案: 【顺序】

2、 问题:具有相同性质的数据元素的集合称为______，它是数据的一个子集。
选项：
A:记录
B:数据对象
C:数组
D:数据结构
答案: 【数据对象】

3、 问题:算法具有5个重要特性，除输入和输出外还包括:_，_，___。
选项：
A:有穷性
B:确定性
C:可读性
D:可行性
答案: 【有穷性;
确定性;
可行性】

4、 问题:算法的设计要求包括达到以下目标：正确性、___、___和效率与低存储量需求。
选项：
A:反编译性
B:可读性
C:健壮性
D:操作性
答案: 【可读性;
健壮性】

5、 问题:非线性结构指的是图和网。
选项：
A:正确
B:错误
答案: 【错误】

6、 问题:数据的物理结构是指数据结构在计算机中的表示，也称为映像。
选项：
A:正确
B:错误
答案: 【正确】

7、 问题:数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的_____和操作的学科。
答案: 【关系】

8、 问题:计算机中具有两种不同的存储结构：顺序存储结构和_____存储结构。
答案: 【链式】

9、 问题:数据的基本单位是____。
答案: 【数据元素】

【作业】第一章 绪论 单元作业一

1、 问题:分析下面代码段中各行的执行次数，用大O表示算法的时间复杂度。说明：方次可用符号^表示，如100的3次方表示为100^3。y=0;
for(i=1; i<=n; i++)
   for(j=1; j<=n; j++)
      y++;
评分规则: 【 算法时间复杂度为 O(n^2)，正确得10分，否则得0分。参考：y=0;                   // 1次for(i=1; i<=n; i++)    // n + 1次  for(j=1; j<=n; j++)  // n(n + 1) 次     y++;              // n^2全部代码的执行次数：1 + (n + 1) + n(n + 1) + n^2 = 2n^2 + 2n + 2 因此，时间复杂度T(n) = O(n^2)
】

第二章 线性表 单元测验二

1、 问题:判定带头结点的单链表head为空的条件是___。
选项：
A:head->next==NULL
B:head==NULL
C:head->next==head
D:head!=NULL
答案: 【head->next==NULL】

2、 问题:如果在n个结点的单链表中删除已知结点s，那么需要___。
选项：
A:找到s的直接后继结点
B:找到s的直接前驱结点
C:移动s后的所有结点
D:释放s后的所有结点
答案: 【找到s的直接前驱结点】

3、 问题:在一个线性表含有10个数据元素，如果在第i个位置前插入新的数据元素，那么i的取值错误的是___。
选项：
A:1
B:10
C:11
D:12
答案: 【12】

4、 问题:线性表的顺序存储结构是一种随机存取结构，即访问任一数据元素的时间相同。
选项：
A:正确
B:错误
答案: 【正确】
分析：【在线性表中，任一数据元素的存储地址可以通过线性表的首地址与该元素相对于首地址的存储位置计算得出，因此所有数据元素的访问时间相同。】

5、 问题:在线性结构中，所有的结点仅有一个前驱结点和一个后继结点。
选项：
A:正确
B:错误
答案: 【错误】
分析：【不是所有结点，应是除第一个结点和最后一个结点之外的结点。】

6、 问题:一个长度为1000的线性表，采用顺序存储，如果在第900个元素之前插入一个元素，需要向后移动_个元素。
答案: 【101】
分析：【向后移动的元素个数：1000-900+1=101】

7、 问题:一个长度为1000的线性表，采用顺序存储，如果删除第900个元素，需要向前移动_个元素。
答案: 【100】
分析：【需要向前移动元素的个数：1000-900=100】

8、 问题:在长度为n的顺序存储的线性表中，查找一个数据元素的时间复杂度为O(__)。
答案: 【n】

9、 问题:线性表采用链式存储时，每个结点包含两个域，存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为_域。
答案: 【指针】

10、 问题:在链表的操作中，生成和释放结点的标准函数是malloc和_。
答案: 【free】

【作业】第二章 线性表 单元作业二

1、 问题:设存在一个带头结点的单循环链表L，每个结点包含三个域，它们分别是prior、data和next。其中data为数据域，prior是指针域，其值为空指针；next是指针域，指向直接后继结点。下面的代码将此单链表转化为双向循环链表。#define OK          1#define ERROR    0 typedef int ElemType;typedef int Status;typedef struct LNode{        struct LNode prior;        ElemType data;        struct LNode next;}DuLNode,*DuLinkList; Status CreateDuList_prior(DuLinkList &L){// Make the prior point to the precursor node.     DuLinkList p,q;             1       ;     do{        q = p->next;                2       ;        p = q;     }while(p!=L);     return OK;}请填写空格1和2处的代码，实现上述功能。
评分规则: 【 参考答案：1. p=L   2. q->prior=p评分标准：每个空格5分，代码正确得分，错误不得分。
】

2、 问题:设指针p指向单链表中的某个结点，将要删除该结点的直接后继结点，而直接后继结点有可能不存在。所有语句如下，需要重新排列才能完成上述功能。1. q=p->next;2. free(q);3. if(p->next==NULL)    return ERROR;4. return OK;5. p->next=q->next; 正确的语句顺序应为___。A. 1 5 2 4 3B. 3 1 5 2 4C. 3 1 2 5 4D. 3 5 1 2 4
评分规则: 【 答案为B得10分，否则0分。
】

第三章 栈与队列 单元测试三

1、 问题:某链栈的栈顶指针为top，若向该栈中插入一个p所指结点，则执行______。
选项：
A:p->next=top; top=top->next;
B:top->next=p; 
C:p->next=top->next; top->next=p;
D:p->next=top; top=p;
答案: 【p->next=top; top=p;】

2、 问题:设循环队列采用一维数组A[0..20]存储，队头指针front = 15，元素个数size = 5，在插入两个新元素后，队尾的位置是______。
选项：
A:0
B:1
C:2
D:22
答案: 【1】

3、 问题:一个栈的入栈序列是a、b、c、d、e，则栈的可能输出的序列是______。
选项：
A:a、b、c、d、e
B:d、c、e、a、b 
C:d、e、c、b、a  
D:e、d、c、b、a
答案: 【a、b、c、d、e;
d、e、c、b、a  ;
e、d、c、b、a】

4、 问题:一个队列的入列序列是a、b、c、d、e，则队列的输出序列不可能是______。
选项：
A:a、b、c、d、e
B:a、c、b、d、e
C:a、b、d、c、e
D:e、d、c、b、a
答案: 【a、c、b、d、e;
a、b、d、c、e;
e、d、c、b、a】

5、 问题:采用顺序存储结构的栈称为链栈。
选项：
A:正确
B:错误
答案: 【错误】
分析：【采用顺序存储的栈称为顺序栈。】

6、 问题:循环队列解决了一般顺序存储队列中出现的“假上溢”问题。
选项：
A:正确
B:错误
答案: 【正确】