《数据结构》填空作业题(答案).doc

《《数据结构》填空作业题(答案).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》填空作业题答案第1章绪论（已校对无误）1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。2．程序包括两个内容：数据结构和算法。3.数据结构的形式定义为：数据结构是一个二元组：DataStructure=（D，S）。4.数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。5.数据的逻辑结构可以分类为线性结构和非线性结构两大类。6.在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。7.在树形结构中，数据元素之间存在一对多的关系。8.数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。9.数据的逻辑结构包括线性

2、结构、树形结构和图形结构3种类型，树型结构和有向图结构合称为非线性结构。10.顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。11.链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。12.数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。13.线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。14.数据结构在物理上可分为顺序存储结构和链式存储结构。15.我们把每种数据结构均

3、视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。16.数据元素可由若干个数据项组成。17.算法分析的两个主要方面是时间复杂度和空间复杂度。18.一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。19.算法具有如下特点：有穷性、确定性、可行性、输入、输出。20.对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切的定义，并在有穷时间内计算出结果。21.下面程序段的时间复杂度为㏒3n。i=1；while(i<=n)i=i﹡3；第2章线性表（已校对

4、无误）1.一线性表表示如下：（a1，a2，…，ai-1，ai，ai+1，…，an），其中每个ai代表一个数据元素（或结点）。a1称为起始结点，an称为终端结点，i称为ai在线性表中的位置（或序号）。对任意一对相邻结点ai，ai+1，（1≤i≤n），ai称为ai+1的直接前驱，ai+1称为ai的直接后继。2.对一个长度为n的线性表，要删除第i个元素，则在顺序表示的情况下，计算复杂性为O(n)，在链式表示的情况下，计算复杂性为O(1)。3.在一个长度为n的顺序表中，向第i个元素（1≤i≤n）之前插入一个新元素时，需向后移动n－i＋1个元素。4.顺序表中逻辑上相邻的元素在

5、物理位置上一定相连。5.在n个结点的顺序表中插入一个结点需平均移动n/2个结点，具体的移动次数取决于表长n和插入位置i。6.在顺序表中访问任意一个结点的时间复杂度均为O(1)，因此，顺序表也称为随机访问的数据结构。7.顺序表相对于链表的优点有随机访问和空间利用率高。8.在长度为n的顺序表中插入一个元素的时间复杂度为O(n)。9.在带有头结点的单链表L中，若要删除第一个结点，则须执行下列三条语句：U＝L->next；L->next=U->next；free（U）。10.链表相对于顺序表的优点有插入和删除操作方便。11.在单链表中除首结点外，任意结点的存储位置都由直接前

6、驱结点中的指针指示。12.在n个结点的单链表中要删除已知结点*p，需找到它的直接前驱结点的地址，其时间复杂度为O(n)。13．单链表中设置头结点的作用是简化操作，减少边界条件的判断。14．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的前驱结点。15.在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后续结点。16.带头结点的单链表L为空的判定条件是L->next==NULL，不带头结点的单链表L为空的判定条件是L==NULL。17.在单链表中，指针p所指结点为最后一个结点的条件是p->next==NULL。18.循环链表的最大优点是从表中

7、任意结点出发都可访问到表中每一个元素（或从表中任意结点出发都可遍历整个链表）。19.设rear是指向非空、带头结点的循环单链表的尾指针，则该链表首结点的存储位置是rear->next->next。20.带头结点的双向循环表L为空表的条件是L->prior==L->next。21.在循环链表中，可根据任一结点的地址遍历整个链表，而单链表中需知道头指针才能遍历整个链表。22.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是1。第3章栈和队列（已校对无误）1.栈又称为后进先出表，队列又称为先进先出表。2.向一个顺序栈插入一个元素时，首先使栈顶指针后移一个