数据结构第1、二章习题.docVIP

第一章 习题： (1) 简述数据与数据元素的关系与区别。 (2) 说出数据结构中的四类基本逻辑结构，并说明哪种关系最简单、哪种关系最复杂。 (3) 画出线性结构的示意图。 (4) 画出树形结构的示意图。 (5) 画出图状结构的示意图。 (6) 什么是逻辑结构、存储结构？有哪几种存储结构？ (7) 简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别。 (8) 简述逻辑结构与存储结构的关系。 (9) 通常从哪几个方面评价算法的质量？ (10) 算法的时间复杂度主要有哪几种？按从优到劣的顺序写出各种表示形式。 (11) 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 (12) 下列算法的时间复杂度是 ( ) 。 for （ i=0 ； in ； i++ ） for （ j=0 ； jn ； j++ ） c[i][j]=i+j A. O(1) B. O(n) C. O(log2n) D. O(n2) (13) 下列算法的时间复杂度是 ( ) 。 for （ i=0 ； in ； i++ ） c[i][i]=i+i A. O(1) B. O(n) C. O(log2n) D. O(n2) 第二章 习题： (1) 若某线性表采用顺序存储结构，每个元素占四个存储单元，首地址为100，则下标为11的(第12个)元素的存储地址为（ ） 。 (2) 下列说法正确的是 ( ) 。 A. 线性表的逻辑顺序与存储顺序总是一致的 B. 线性报第链式存储结构中，内存中可用的存储单元可以使连续的，也可以不连续 C. 线性表弟顺序存储结构优于链式存储结构 D. 每种数据结构都具有插入、删除和查找三种基本运算 (3) L是线性表，已知ListLength(L) 的值是 5，运算DeleteList（L，2）后ListLength（L）的值是 ( ) 。 A. 5 B. 0 C. 4 D. 6 (4) 线性表中哪些元素只有一个直接前驱和一个直接后继 ( ) 。 A. 首元素 B. 尾元素 C. 中间元素 D. 所有的元素 (5) 线性表（ L ）经运算 InitList （ L ）后，函数 IEmpty （ L ）的值是 ( ) 。 A. 0 B. ,false C. 1 D. Null (6) 指针 P 指向循环链表 L 的首元素的条件是 ( ) 。 A. P=L B. P-nest=L C. L-nest=P D. P-nest=null (7) 线性表中各元素之间的关系是 ( ) 关系。 A. 层次 B. 网状 C. 有序 D. 集合 (8) 在单链表的一个结点中有 ( ) 个指针。 A. 1 B. 2 C. 0 D. 3 (9) 在双向链表的一个结点中有 ( ) 个指针。 A. 1 B. 2 C. 0 D. 3 (10) 设非空单链表的数据字段为 data ，指针字段为 next ，指针 p 指向单链表中第 i 个结点， s 指向已生成的新结点，现将 s 结点插入到单链表中，使其成为第 i+1 个结点，下列算法段能正确完成上述要求的是 ( ) 。  A. s-next=p-next=s ； B. p-next=s ； s-next=p-next ； C. s-next=p-next ； p-next=s ；交换 p-data 和 s-data ； D. p=s ； s-next=p (11) 设双链表中结点的前趋指针的字段分别为t1和rl，则删除双链表中指针s所指结点的操作为 ( ) 。  A. s-t1-r1=s-t1 ； s-r1=s-r1 ； B. s-t1-r1=s-r1 ； s-r1=s-t1 ； C. s-r1=s-t1 ； s-t1=s-r1-t1 ； D. s-t1=s-t1-r1 ； s-r1=s-t1 ； (12) 假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针字段，现要把一个指针s所指的新结点作为非空双链表中 q