数据结构-线性表-习题

第二章 线性表一、选择题1. 线性表是（ ）A一个有限序列，可以为空B一个有限序列，不可以为空C一个无限序列，可以为空D一个无限序列，不可以为空2. 一维数组与线性表的特征是（ ）。 A前者长度固定，后者长度可变 B两者长度均固定 C后者长度固定，前者长度可变 D两者长度均可变 3. 用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个是( ). A当前结点所在地址域B指针域 C空指针域D空闲域 4. 用链表表示线性表的优点是（ ）。 A便于随机存取B便于进行插入和删除操作 C占用的存储空间较顺序表少D元素的物理顺序与逻辑顺序相同 5. 在具有 n 个结点的单链表中，实现_的操作，其算法的时间复杂度都是O（n）。 A遍历链表和求链表的第i个结点D删除地址为P的结点的后继结点B在地址为P的结点之后插入一个结点 C删除开始结点6. 下面关于线性表的叙述中，错误的是（ ）。 A线性表采用顺序存储必须占用一片连续的存储单元 B线性表采用顺序存储便于进行插入和删除操作 C线性表采用链式存储不必占用一片连续的存储单元 D线性表采用链式存储便于进行插入和删除操作7. 已知单链表的每个结点包括一个指针域next，它指向该结点的后继结点。现要将指针 q 指向的新结点插入到指针 p 指向的结点之后，下面的操作序列中正确的是（ ）。A . q = p-next; p-next = q-next ;B . p-next = q-next;q = p-next ; C . q-next = p-next; p-next = q ; D . p-next = q; q-next = p-next ; 8. 设 al，a2， a3为三个结点； p , 10 , 20 代表地址，则如下的链表存储结构称为（ ）。A链表B单链表C双向循环链表D双向链表 9. 单链表的存储密度（ ）。 A大于 1 B等于1C小于1D不能确定 10. 己知一个顺序存储的线性表，设每个结点需占 m 个存储单元，若第一个结点的地址al ，则第i个结点的地址为（ ）。A. al+(i-1)*mB. al+i*mC. al-i*mD. al+(i+1)*m 11. 在 n 个结点的顺序表中，算法的时间复杂度是 O(l）的操作是（ ）。 A访问第i个结点（1in）和求第 i 个结点的直接前驱（2in) B在第 i 个结点之后插入一个新结点（1in-1） C删除第 i 个结点（ 1in ) D将 n 个结点从小到大排序 12. 在线性表中（ ）只有一个直接前驱和一个直接后继。 A首元素B中间元素C尾元素D所有元素 13. 对具有 n 个结点的线性表进行查找运算，所需的算法时间复杂度为（ ）。 A. 0 (n2)B. 0 (nlog2n)C. O (log2n)D. O (n) 14. 线性表采用顺序存储的缺点是（ ）。 A存储密度降低B只能顺序访问 C元素的逻辑顺序与物理顺序不一致D插入、删除操作效率低 15. 以下链表结构中，从当前结点出发能够访问到任一结点的是（ ）。A单向链表和双向链表B双向链表和循环链表 C单向链表和循环链表D单向链表、双向链表和循环链表 16. 线性表是具有 n 个（ ）的有限序列。 A数据项B数据元素C表元素D字符 17. 若长度为 n 的线性表采用链式存储结构，访问其第 i 个元素的算法时间复杂度为（ ）。A. 0 ( l )B. 0 ( n )C. 0 ( n2 )D. 0 ( log2n )18. 指针 P 指向循环链表 L 的首元素的条件是（ ）。 A. PLB. L-nextPC.P-next= =NULLD. P-nextL 19. 指针 P 所指的元素是双循环链表 L 的尾元素的条件是（ ）。 A. PLB. P-priorLC. PNULLD. P-nextL 20. 不带头结点的单链表L为空的条件是( )A. L!NULLB. LNULLC. L-nextNULLD. L-nextL21. 带头结点的单链表L为空的条件是( )A. L!NULLB. LNULLC. L-nextNULLD. L-nextL22. 两个指针 P 和 Q ，分别指向单链表的两个元素， P 所指元素是 Q 所指元素前驱的条件是（ ）。 A. P-nextQ-nextB. P-nextQC. Q-nextPD. PQ 23. 在长度为 n 的顺序表中，若要删除第 i (1in ）个元素，则需要向前移动元素的次数为（ ）。 A. 1B. n一iC. n一i+1D. n一i一l 24. 在长度为 n 的顺序表中第 i (1in）个位置上插入一个元素时，为留出插入位置所需移动元素的次数为（ ）。A. n-iB. iC. ni+1D. n-i-l 25. 假定己建立以下动态链表结构，且指针 Pl 和 P2 已指向如图所示的结点：则以下可以将 P2 所指结点从链表中删除并释放该结点的语句组是( )A. pl-next=p2-next; free (pl);B. pl=p2; free (p2);C. pl-next=p2-next；free (p2);D. pl=p2-next; free (p2); 26. 若已建立如图所示的单向链表，则以下不能将 s 所指的结点插入到链表尾部，构成新的单向链表的语句组是（ ）。A . s-next = a-next-next ; a-next-next = s ;B . a = a-next; a-next =s ; s-next = NULL ;C . s-next = NULL ; a = a-next; a-next = s ;D . a = a-next ; s-next = a-next ; a-next = s-next ;27. 有如下函数，其中形参 hl 和 h2 分别指向 2 个不同链表的第一个结点，此函数的功能是（ ）。Void fun( struct node * hl , struct node * h2 ) struct node * t ; t = hl ;while ( t-next ! 0 ) t = t-next ; t-next = h2 ; A将链表 h2 接到链表 h1 后B将链表 h1 接到链表 h2 后 C找到链表 hl 的最后一个结点由指针返回D将链表 hl 拆分成两个链表 二、判断题1. 循环链表不是线性表. ( )2. 线性表就是顺序存储的表。( ) 3. 线性表只能用顺序存储结构实现。( ) 4. 链表中的头结点仅起到标识的作用。( )5. 线性表的链式存储结构优于顺序存储。( ) 6. 顺序存储的线性表可以实现随机存取。( ) 7. 顺序存储方式只能用于存储线性结构。( )8. 链表的每个结点都恰好包含一个指针域。( )9. 所谓静态链表就是一直不发生变化的链表。( )链表中的结点可含多个指针域,分别存放多个指针。 10. 集合与线性表的区别在于是否按关键字排序。( ) 11. 取线性表的第i个元素的时间同i的大小有关. ( ) 12. 顺序存储结构的主要缺点是不利于插入或删除操作。( )13. 线性表的特点是每个元素都有一个前驱和一个后继。( ) 14. 对任何数据结构链式存储结构一定优于顺序存储结构。( ) 15. 顺序存储方式的优点是存储密度大，插入、删除效率高。( ) 16. 为了很方便的插入和删除数据，可以使用双向链表存放数据。( ) 17. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 18. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 19. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 20. 线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。( ) 21. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。( ) 22. 在线性表的顺序结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。( ) 23. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。( ) 24. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 ( ) 25. 在单链表中，任何两个元素的存储位置之间都有固定的联系，所以可以从头结点开始查找任何一个元素。( )26. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。( )三、填空题1. 顺序表中逻辑上相邻的元素在物理位置上相邻。2. 在链表中逻辑上相邻的元素的物理位置相邻。3. 带头结点的双循环链表L为空表的条件是：。4. 在单链表p结点之后插入s结点的操作是：。5.6. 顺序表相对于链表的优点有和。7. 在双链表中要删除已知结点*p ，其时间复杂度为。8. 在顺序表中访问任意一个结点的时间复杂度均为。9. 链接存储的特点是利用来表示数据元素之间的逻辑关系。10. 带头结点的双循环链表L中只有一个元素结点的条件是：11. 在单链表L中，指针p所指结点有后继结点的条件是：12.13. 在单链表中除首结点外，任意结点的存储位置都由结点中的指针指示。14. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：15.16. 在 n 个结点的单链表中要删除已知结点*p ，需要找到.其时间复杂度为。17. 链表相对于顺序表的优点有和操作方便；缺点是存储密度。18. 建立单链表的算法时间复杂度 ；建立有序单链表的算法时间复杂度 。19. 在单链表中设置头结点的作用是。20. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共个，单链表为个。21. 在一个长度为n的顺序表中第i个元素（1=inext ; do s= s ；p = p-next ; while ( p ! )；return s; 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19. 己知 head 指向一个带有头结点的单向链表，链表中每个结点包含整型数据域（ data ) 和指针域（ next ）。以下算法用来查找链表所有结点中数据域值最大的结点的位置，由指针 s 传回调用程序。请填空。struct link char data ; struct link *next;main ( )struct link * head , * q ; findmax ( head , & q ) ;printf ( max = % d n , q-data ) ; findmax ( struct link * head , struct link * * s ) struct link * p ; p = h ead-next ; * s = p ; while （ ） p ; if ( p-data )* s=p ; 20. 设线性表顺序存储结构定义如下：# define MAXSIZE 20typedef int datatypetype struct datatype data MAXSIZE + l ; int last ; sequenlist ; 函数 int 1ocate2 ( sequenlist * L , int x ) ；利用在表头设立监视哨的算法，实现在顺序表 L 中查找值为 x 的元素的位置。请填空。 int locate2 ( sequenlist * L , int x ) int i =