数据结构课件数据结构习题.ppt

1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为( D, R ),其中 D是数据元素的有限集合, R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类,它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多系,图形结构中元素之间存在多对多关系。 ,第一个结点没有前驱结点,其余每个结点有且只有 1个前驱结点;最后一个结点没有后续结点,其余每个结点有且只有 1个后续结点。 7. 在树形结构中,树根结点没有前驱结点,其余每个结点有且只有 1个前驱结点;叶子结点没有后续结点,其余每个结点的后续结点数可以任意多个。 8. 在图形结构中,每个结点的前驱结点数和后续结点数可以任意多个。 2种基本的存储方法表示,它们分别是顺序存储结构和连式存储结构。 10. 数据的运算最常用的有 5种,它们分别是检索、排序、插入、删除、修改。 11. 一个算法的效率可分为时间效率和空间效率。(B)1. 非线性结构是数据元素之间存在一种: B)多对多关系(C)2. 数据结构中,与所使用的计算机无关的是数据的结构; C) 逻辑(C)3. 算法分析的目的是: C) 分析算法的效率以求改进(A)4. 算法分析的两个主要方面是: A) 空间复杂性和时间复杂性(C)5. 计算机算法指的是: C) 解决问题的有限运算序列(B)6. 计算机算法必须具备输入、输出和等5个特性。 B) 可行性、确定性和有穷性 1. 在顺序表中插入或删除一个元素,需要平均移动一半元素,具体移动的元素个数与表长和该元素在表中的位置有关。 2. 线性表中结点的集合是有限的,结点间的关系是一对一的 3. 向一个长度为 n的表的第 i个元素(1≤i≤n+1) 之前插入一个元素时,需向后移动 n-i+1 个元素。 4. 向一个长度为 n的表中删除第 i个元素(1≤i≤n)时,需向前移动 n-i 个元素。 5. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ,因此,顺序表也称为随机存取的数据结构。 6. 顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。(C),物理地址与逻辑地址相同并且是连续的,称之为:( C)顺序存储结构(A)3. 在n个结点的顺序表中,算法的时间复杂度是 O(1)的操作是: (A)访问第 i个结点( 1≤i≤n)和求第 i 个结点的直接前驱( 2≤i≤n) (B)4. 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动个元素( B) (×)。答:错误。链表中的结点可含多个指针域,分别存放多个指针。例如,双向链表中的结点可以含有两个指针域,分别存放指向其直接前趋和直接后继结点的指针。(×)。错,链表的存储结构特点是无序,而链表的示意图有序。(×),因为当删除链中某个结点后,计算机会自动地将后续