讯享网

 <p>第二章线性表</p><p>一、选择题</p><p>1.线性表是（）</p><p>A．一个有限序列，可以为空B．一个有限序列，不可以为空</p><p>C．一个无限序列，可以为空D．一个无限序列，不可以为空</p><p>2.一维数组与线性表的特征是（）。</p><p>A．前者长度固定，后者长度可变B．两者长度均固定</p><p>C．后者长度固定，前者长度可变D．两者长度均可变</p><p>3.用单链表方式存储的线性表，存储每个结点需要两个域，一个数据域，另一个</p><p>是( ).</p><p>A．当前结点所在地址域B．指针域</p><p>C．空指针域D．空闲域</p><p>4.用链表表示线性表的优点是（）。</p><p>A．便于随机存取B．便于进行插入和删除操作</p><p>C．占用的存储空间较顺序表少D．元素的物理顺序与逻辑顺序相同5.在具有 n 个结点的单链表中，实现___的操作，其算法的时间复杂度都是O（n）。</p><p>A．遍历链表和求链表的第i个结点D．删除地址为P的结点的后继结点B．在地址为P的结点之后插入一个结点 C．删除开始结点</p><p>6.下面关于线性表的叙述中，错误的是（）。</p><p>A．线性表采用顺序存储必须占用一片连续的存储单元</p><p>B．线性表采用顺序存储便于进行插入和删除操作</p><p>C．线性表采用链式存储不必占用一片连续的存储单元</p><p>D．线性表采用链式存储便于进行插入和删除操作</p><p>7.已知单链表的每个结点包括一个指针域next，它指向该结点的后继结点。现</p><p>要将指针 q 指向的新结点插入到指针 p 指向的结点之后，下面的操作序列中正确的是（）。</p><p>A . q = p->next; p->next = q->next ;</p><p>B . p->next = q->next; q = p->next ;</p><p>C . q->next = p->next; p->next = q ;</p><p>D . p->next = q; q->next = p->next ;</p><p>8.设 a l，a2， a3为三个结点； p , 10 , 20 代表地址，则如下的链表存储结构</p><p>称为（）。</p><p>A．链表B．单链表C．双向循环链表D．双向链表</p><p>9.单链表的存储密度（）。</p><p>A．大于 1 B．等于1 C．小于1D．不能确定</p><p>10.己知一个顺序存储的线性表，设每个结点需占 m 个存储单元，若第一个结点</p><p>的地址al ，则第i个结点的地址为（）。</p><p>A. al+(i-1)*m</p><p>B. al+i*m</p><p>C. al-i*m</p><p>D. al+(i+1)*m</p><p>11.在 n 个结点的顺序表中，算法的时间复杂度是 O(l）的操作是（）。</p><p>A．访问第i个结点（1≤i≤n）和求第 i 个结点的直接前驱（2≤i≤n) B．在第 i 个结点之后插入一个新结点（1≤i≤n-1）</p><p>C．删除第 i 个结点（ 1≤i≤n )</p><p>D．将 n 个结点从小到大排序</p><p>12.在线性表中（）只有一个直接前驱和一个直接后继。</p><p>A．首元素B．中间元素C．尾元素D．所有元素</p><p>13.对具有 n 个结点的线性表进行查找运算，所需的算法时间复杂度为（）。</p><p>A. 0 (n2)</p><p>B. 0 (nlog2n)</p><p>C. O (log2n)</p><p>D. O (n)</p><p>14.线性表采用顺序存储的缺点是（）。</p><p>A．存储密度降低B．只能顺序访问</p><p>C．元素的逻辑顺序与物理顺序不一致D．插入、删除操作效率低</p><p>15.以下链表结构中，从当前结点出发能够访问到任一结点的是（）。</p><p>A．单向链表和双向链表B．双向链表和循环链表</p><p>C．单向链表和循环链表D．单向链表、双向链表和循环链表16.线性表是具有 n 个（）的有限序列。</p><p>A．数据项B．数据元素C．表元素D．字符</p><p>17.若长度为 n 的线性表采用链式存储结构，访问其第 i 个元素的算法时间复杂</p><p>度为（）。</p><p>A. 0 ( l )</p><p>B. 0 ( n )</p><p>C. 0 ( n2 )</p><p>D. 0 ( log2n )</p><p>18.指针 P 指向循环链表 L 的首元素的条件是（）。</p><p>A. P＝＝L</p><p>B. L->next＝＝P</p><p>C.P->next= =NULL</p><p>D. P->next＝＝L</p><p>19.指针 P 所指的元素是双循环链表 L 的尾元素的条件是（）。</p><p>A. P＝＝L</p><p>B. P->prior＝＝L</p><p>C. P＝＝NULL</p><p>D. P->next＝＝L</p><p>20.不带头结点的单链表L为空的条件是( )</p><p>A. L!＝NULL</p><p>B. L＝＝NULL</p><p>C. L->next＝＝NULL</p><p>D. L->next＝＝L</p><p>21.带头结点的单链表L为空的条件是( )</p><p>A. L!＝NULL</p><p>B. L＝＝NULL</p><p>C. L->next＝＝NULL</p><p>D. L->next＝＝L</p><p>22.两个指针 P 和 Q ，分别指向单链表的两个元素， P 所指元素是 Q 所指元素</p><p>前驱的条件是（）。</p><p>A. P->next＝＝Q->next</p><p>B. P->next＝＝Q</p><p>C. Q->next＝＝P</p><p>D. P＝＝Q</p><p>23.在长度为 n 的顺序表中，若要删除第 i (1≤i≤n ）个元素，则需要向前移</p><p>动元素的次数为（）。</p><p>A. 1</p><p>B. n一i</p><p>C. n一i+1</p><p>D. n一i一l</p><p>24.在长度为 n 的顺序表中第 i (1≤i≤n）个位置上插入一个元素时，为留出插</p><p>入位置所需移动元素的次数为（）。</p><p>A. n-i</p><p>B. i</p><p>C. n–i+1</p><p>D. n-i-l</p><p>25.假定己建立以下动态链表结构，且指针 Pl 和 P2 已指向如图所示的结点：则</p><p>以下可以将 P2 所指结点从链表中删除并释放该结点的语句组是( )</p><p>A. pl->next=p2->next; free (pl);</p><p>B. pl=p2; free (p2);</p><p>C. pl->next=p2->next；free (p2);</p><p>D. pl=p2->next; free (p2);</p><p>26.若已建立如图所示的单向链表，则以下不能将 s 所指的结点插入到链表尾部，</p><p>构成新的单向链表的语句组是（）。</p><p>A . s->next = a->next->next ; a->next->next = s ;</p><p>B . a = a->next; a->next =s ; s->next = NULL ;</p><p>C . s->next = NULL ; a = a->next; a->next = s ;</p><p>D . a = a->next ; s->next = a->next ; a->next = s->next ;</p><p>27.有如下函数，其中形参 hl 和 h2 分别指向 2 个不同链表的第一个结点，此</p><p>函数的功能是（）。</p><p>Void fun( struct node * hl , struct node * h2 ){</p><p>struct node * t ;</p><p>t = hl ;</p><p>while ( t->next ! ＝'0' )</p><p>t = t->next ; t->next = h2 ;</p><p>}</p><p>A．将链表 h2 接到链表 h1 后B．将链表 h1 接到链表 h2 后</p><p>C．找到链表 hl 的最后一个结点由指针返回 D．将链表 hl 拆分成两个链表</p><p>二、判断题</p><p>1.循环链表不是线性表. ( × )</p><p>2.线性表就是顺序存储的表。( × )</p><p>3.线性表只能用顺序存储结构实现。( × )</p><p>4.链表中的头结点仅起到标识的作用。( √ )</p><p>5.线性表的链式存储结构优于顺序存储。( × )</p><p>6.顺序存储的线性表可以实现随机存取。( √ )</p><p>7.顺序存储方式只能用于存储线性结构。( √ )</p><p>8.链表的每个结点都恰好包含一个指针域。( × )</p><p>9.所谓静态链表就是一直不发生变化的链表。( × )1</p><p>10.集合与线性表的区别在于是否按关键字排序。( × )</p><p>11.取线性表的第i个元素的时间同i的大小有关. ( × )</p><p>12.顺序存储结构的主要缺点是不利于插入或删除操作。( √ )</p><p>13.线性表的特点是每个元素都有一个前驱和一个后继。( × )</p><p>14.对任何数据结构链式存储结构一定优于顺序存储结构。( × )</p><p>15.顺序存储方式的优点是存储密度大，插入、删除效率高。( × )</p><p>16.为了很方便的插入和删除数据，可以使用双向链表存放数据。( × )</p><p>17.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( × )</p><p>18.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( × )</p><p>19.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( √ )</p><p>20.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。</p><p>( √ )</p><p>21.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。</p><p>( × )</p><p>22.在线性表的顺序结构中，插入和删除元素时，移动元素的个数与该元素的位置有</p><p>关。( × )</p><p>1链表中的结点可含多个指针域,分别存放多个指针。</p>