计算机数据结构习题1附答案.doc

第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 填空题： 1.常见的数据结构有_线性__结构，__树形___结构，__图形__结构等三种。 2.常见的存储结构有__顺序存储_______结构，__链式存储____结构等两种。 3.数据的基本单位是_数据元素___，它在计算机中是作为一个整体来处理的。 4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，__线性结构____和__非线性结构___。 5.《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和_________。1.2 设有数据结构(D,R)，其中 ，， 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.3设有以下三个函数： ，， 请判断以下断言正确与否： (1) f(n)是O(g(n)) (2) h(n)是O(f(n)) (3) g(n)是O(h(n)) (4) h(n)是O(n3.5) (5) h(n)是O(nlogn) 解：(1)对 (2)错 (3)错 (4)对 (5)错 第二章 序列 2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。 解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。 2.2 填空题。 (1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。 (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。 (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。 (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。 (5) 线性表按照存储结构不同主要有两种实现方式，一种是__顺序_表，另一种是___链___表。 (6)顺序表采用__随机___访问机制对数据元素进行访问。 (7)在单向链表中，若要删除某个结点p，一般要找到__p的前趋__结点，才能实现该操作。 （8）若频繁地对线性表进行插入与删除操作，该线性表应采用___________存储结构。 _____head-next==head______。 p指向单链表中某个结点，语句p-next=p-next-next的作用是__删除P后面的结点_____。 (11)从一个具有100个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要平均比较的结点数是___50.5_ 。 （12）在一个长度为n的顺序表中，删除第i个元素时，需要移动___n-i____个元素。 2.3选择题、判断题： 1.若长度为n的线性表采用顺序存储结构，在其第i个位置一个元素的算法的时间复杂度为(??? )。(1≤i≤n) A．O(0)??? B．O(1)??? C.O(n)??? D．O(n2) 若长度为n的线性表采用顺序存储结构，在其第i个位置一个新元素(??B? )。(1≤i≤n+1)A．?? B．??? C. i??? D．线性表的逻辑顺序与物理顺序总是一致的。 判断带头指针head的单链表A长度为m，带头结点的单链表B长度为n，若将B链接在A的末尾，其时间复杂度应为 （ A ） 。 O(1) B、O(m) C、O(n) D、O(m+n) 7.在一个双向链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（ C ）个结点的指针域的值。 A、1 B、2 C、3 D、4 2.4 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是__________________。 //b. 在P结点前插入S结点的语句序列是__________