1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。2.数据结构被形式地定义为（D,R），其中D是数据元素的有限集合，R是D上的关系有限集合。3.数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。4.数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。5.线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。7.在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。8.在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。10.数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。11.一个算法的效率可分为时间效率和空间效率。二、单项选择题（B）1.非线性结构（B）多对多关系（C）2.数据结构中，与所使用的；C)逻辑（C）3.算法分析的目的是：（A）4.算法分析的两个主要方面是：A)空间复杂性和时间复杂性：C)解决问题的有限运算序列（B）6.计算机算法必须具备输入、输出和等5个特性。B)可行性、确定性和有穷性第2章自测卷答案一、填空1.在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。2.线性表中结点的集合是有限的，结点间的关系是一对一的。3.向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1个元素。4.向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i个元素。5.在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。6.顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。7.在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。8．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。二、判断正误（在正确的说法后面打勾，反之打叉）（×）1.链表的每个结点中都恰好包含一个指针。答：错误。（×）2.链表的物理存储结构（×）3.链表的删除算法很简单（×）4.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂（×）5.顺序表结构适宜于进行顺序存取（×）6.顺序存储方式的优点是存储密（×）7.线性表在物理存储空间中也一定是连续的。（×）8.线性表在顺序存储时，逻辑上相邻的元素未必在存（×）9.顺序存储方式只能用于存储线性结构。（×）10.线性表的逻辑顺序与存储顺序总是一致的。三、单项选择题（C）1．数据在计算机存储器内表示时物理地址与逻辑地址（C）顺序存储结构（B）2.一个向量第一个元素的存储地址是100（B）108（A）3.在n个结点的顺序表中，（B）4.向一个有127个元素的顺序表中插入一个新元素并（A）8（A）5.链接存储的存储结构所占存储空间：分两部分，一部分存放结点值（B）6.链表是一种采用存储结构存储的线性表；（B）链式（D）7.线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（D）连续或不连续都可以（B）8．线性表Ｌ在情况下适用于使用链式结构实现。（Ｂ）需不断对Ｌ进行删除插入（C）9．单链表的存储密度（Ｃ）小于1；（B）10．设a1、a2、a3为3个结点，整数P0，3，4代表地P034P0a13a24A30（Ｂ）单链表第3章栈和队列自测卷答案1.向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。2.栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。3.队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。4.在一个循环队列中，队首指针指向队首元素的前一个位置。5.在具有n个单元的循环队列中，队满时共有n-1个元素。6.向栈中压入元素的操作是先移动栈顶指针，后存入元素。7.从循环队列中删除一个元素时，其操作是先移动队首指针，后取出元素。8.〖00年统考题〗带表头结点的空循环双向链表的长度等于0。head解：（×）1.线性