数据结构1_3章习题课.ppt

习 题 课（1~3章）;一、填空题 数据的逻辑结构被分为 、 、 和 4种. 数据的存储结构被分为 、 2种. 在线性结构、树形结构和图形结构中，直接前驱和 直接后继结点之间分别存在着 、 和 的联系。 4. 一个算法应具有 、 、 输 入和输出特性. 5. 一个算法的效率主要由 和 来度量。 6. 抽象数据类型包括___________和______________。 ;在顺序表中插入一个元素，需要平均移动 元素，具体移动的元素个数与 有关。 8. 在顺序表中逻辑上相邻的元素的物理位置 紧邻。 单链表中逻辑上相邻的元素的物理位置 紧邻。 9. 在单链表中，除了首元结点外，任一结点的存储位 置由 指示。 10. 在单链表中设置头结点的作用是 。 11. 栈的特点是 。 12. 队列的特点是 。 13. 在能存放m个元素的循环队列中，允许最多存放 个元素。 ;从一维数组A[n]中顺序找出一个最大值元素的时间复杂度 为 ,输出一个二维数组B[m][n]中所有元素值的时 间复杂度为 . ;16. 一维数组逻辑结构是 ,存储结构是 . 对于二维数组有 和 两种不同的存储方式. 对于一个二维数组A[m][n],若采用行优先顺序存储的方式, 则任一数组元素A[i][j]相对于A[0][0]的地址为 .17. 栈的插入和删除操作是在 进行.当利用大小为 n 的 数组顺序存储一个栈时,假定top==n表示栈空, 则向这个栈插 入一个元素时,首先应执行 语句修改 top 指针.18. 队列的插入操作在 进行,删除操作在 进行. 19. 在循环队列中,队头指针指向队头元素的 位置, 队尾指针指向队尾元素的 位置.20. 在一个顺序栈中,判断队空的条件为 ,判断队满的条件  为 .;;补充题答案: 答:按增长率由小到大的顺序各函数为： (2/3)n， 2100， log2(log2n) ， log2n， log22n， n1/2 ， n2/3， n/log2n， n，nlog2n, (4/3)n， (3/2)n， n!， nn ;二、已知L是无表头结点的单链表，且P结点既不是首 元结点，也不是尾结点，试从下列提供的答案中选  择合适的语句序列。;;五、（1）画出执行下列各行语句后各指针及链表的示意图。 ListNode *L=new ListNode( ); P=L; for(i=1; i=4; i++) { ListNode *Q=new ListNode( ); P-link=Q; P=P-link; P-data=2*i-1; } P-link=NULL; for(i=4; i=1; i--) { Insert(2*i, i+1); for(i=1; i=3; i++) { Remove(i); } ;六、简述以下算法的功能。 （1）void A(Link L ) { //L是无表头结点的单链表