《数据结构第2章典型例题解析》由会员分享，可在线阅读，更多相关《数据结构第2章典型例题解析（9页珍藏版）》请在金锄头文库上搜索。
1、第2章线性表典型例题解析一、选择题1 .线性表是具有n个(n0) 的有限序列。A表元素 B .字符 C .数据元素D .数据项【分析】线性表是具有相同数据类型的n (n0)个数据元素的有限序列，通常记为(ai, a2,，an),其中n为表长,n=0时称为空表。【答案】C2 .顺序存储结构的优点是 。A存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示【分析】顺序存储结构是采用一组地址连续的存储单元来依次存放数据元素，数据元素 的逻辑顺序和物理次序一致。因此，其存储密度大。【答案】A3 .带头结点的单链表 head为空的判断条件是 。A head=NULLB. he
2、ad- next=NULLC. head-next=headD. head!=NULL【分析】链表为空时，头结点的指针域为空。【答案】B4 .若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素， 则采用 存储方式最节省运算时间。A单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表【分析】根据题意要求，该线性表的存储应能够很方便地找到线性表的第一个元素和最 后一个元素，A和B都能很方便地通过头指针找到线性表的第一个元素，却要经过所有元素 才能找到最后一个元素；选项C双链表若存为双向循环链表，则能很方便地找到线性表的第一个元素和最后一个元素，但存储效率要低些
3、，插入和删除操作也略微复杂；选项D可通过尾指针直接找到线性表的最后一个元素，通过线性表的最后一个元素的循环指针就能很方便 地找到第一个元素。【答案】D5 .若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算， 则利用 存储方式最节省时间。A顺序表B.双链表C.带头结点的双循环链表D.单循环链表【分析】某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运 算。因此不需要移动线性表种元素的位置。根据题意要求，该线性表的存储应能够很方便地 找到线性表的任一指定序号的元素和最后一个元素，顺序表是由地址连续的向量实现的，因 此具有按序号随机访问的特点。链表需要通过指
4、针才能找到线性表的莫以指定序号的元素， 需要一定的时间开销。【答案】A6 .设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用 最节省 时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表【分析】根据题意要求，该线性表的存储应能够很方便地找到线性表的最后一个元素和 最后一个元素的前驱元素，A和B都不能很方便地通过头指针找到线性表的第一个元素；选项C可以方便地找到最后一个元素，单不能很快地找到其前驱元素；选项D为双向循环链表，可以很方便地找到线性表的最后一个元素，通过其前驱指针，从而可以方便地找到其前驱元 素。【答案】D7 .静态链表中指针表示的是 。A 内存地
5、址B .数组下标C .下一元素地址D .左、右孩子地址【分析】静态链表采用的是链式方式存储线性表，以数组方式存储链表的数据，指针域 存储的是该结点逻辑上的后继结点的相对地址(即在数组中的下标)，也称为静态指针。【答案】B8 .链表不具有的特点是 。A插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比【分析】链表是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据 元素之间的线性关系，对每个数据元素，除了存放数据元素自身的信息之外，还需要和存放 其后继元素所在的存储单元的地址。链表不具有按序号随机访问第i个元素的特点，必须通过标识链表的
6、头指针(或尾指针)“顺藤摸瓜”才能找到第 i个结点。【答案】B9 .线性表的静态链表存储结构与顺序存储结构相比优点是 。A所有的操作算法简单B.便于插入和删除C.便于利用零散的存储器空间D.便于随机存取【分析】静态链表采用的是链式方式存储线性表，因此其具有链式存储的特点。【答案】B10 .若长度为n的线性表采用顺序存储结构，在其第 i个位置插入一个新元素算法的时 间复杂度为。A Qlog 2n)B. Q1)C. O(n)D, Qn2)【分析】在第i个位置上插入新元素需要从最后一个元素开始后移直到第i个元素后移为止，后移元素的次数为 n-i+1,即时间复杂度为 Qn)。【答案】C11 .线性表(
7、a1,a2,an)以链接方式存储时，访问第 i个位置元素的时间复杂性A 3)B. qi)C. Qn)D. Qi-1)【分析】线性表以链接方式存储时，访问第 i个位置元素从第一个元素开始移动指针到 第i个元素，移动指针的次数为 n-i+1,即时间复杂度为 O( n) o12 .将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 A nB. 2n-1C. 2nD. n-1【分析】当一个表的最小元素大于另一个表的最大元素时比较次数为最少，共需n次。【答案】A13 .非空的循环单链表 head的尾结点p满足。A p-next=headB. p-next=NULL C. p=NULLD. p
8、=head【分析】非空的循环单链表head的尾结点的后继指针指向链表的头结点。【答案】A14 .在双循环链表p所指结点之后插入 S所指结点的操作是 -prior=p - next;A p- next=s; s - prior=p; p -next - prior=s; s-prior=p; s - next=p - next;B. p- next=s; p - next - prior=s; sC. s-prior=p; s-next=p - next; p - next=s; p-next -prior=s;D. s- prior=p; s-next=p - next; p - next -
9、prior=s; p - next=s;【分析】由于要将s所指结点插入到p所指结点之后，p结点为s结点的前驱，s结点为 p结点的新后继，而结点 p的原后继结点为结点 s的后继结点，结点 s为结点p的原后继结点的前驱结点So在选项A、B和C中均是先执行操作 p- next=s ,就是修改了结点 p的后继 结点s,然后再执行操作 p- next - prior=s ,因此，无法使得结点 s为结点p的原后继结点 的前驱结点，这样的赋值会使s结点为其自身的前驱。应先执行操作p- next - prior=s ,再 执行操作p-next=s 。【答案】D15.在一个单链表中，已知 q所指结点是p所指结点
10、的前驱结点，若在 q结点和p结点 之间插入s结点，则执行。A s- next=p - next;p -next=s;B. p-next=s - next;s - next=p;C. q- next=s; s - next=p;D. p- next=s; s -next=q;【分析】由于是将s所指结点插入到 q和p所指结点之间，即使其为q所指结点的后继结点，为p所指结点的前驱结点，因此 s-next的取值应为p, p-next的取值无需改动， q-next的取值应改为s,故A B和D均是错误的。【答案】C、判断题1 .线性表的特点是每个元素都有一个前驱和一个后继。【分析】线性表是一种逻辑结构，其
11、数据元素属于相同数据类型，之间的关系是线性关 系。线性表中除第一个数据元素和最后一个数据元素外，外每个元素都有一个前驱和一个后 继。【答案】错误2 .顺序存储的线性表可以按序号随机存取。【分析】因为顺序表在内存是用地址连续的空间存储的，设a的存储地址为Loc(ai),每个数据元素占d个存储地址，则第i个数据元素的地址为：Loc( ai)=Loc( a i)+( i -1) x d 1 i prior=p-prior;p-prior=s;s-next=p;【解答】只能是 s-prior -next=s; 而不能为“p- prior - next=s; 。因为在上面的第二条语句中已经改变了结点 结点，而不是操作前的前驱结点。在下面的语句顺 s-prior=p-prior;P前插入一个结点s,请完成有关操作。图2-11 第1题图p的前驱结点，结点 p的前驱结点已经为s 可有两个答案进行选择。p-prior=s;s-next=p;读者做这种题时，最好予以图示，不易出错。A0. n-1中(表长为n,设为全局2 .已知线性表非递减有序，存储于一个一维数组 量)，下面算法的功能是什么void del(DataType
