数据结构第2章典型例题解析

数据结构典型例题解析第2章线性表典型例题解析一、选择题1．线性表是具有n个（n≥0）的有限序列。A．表元素B．字符C．数据元素D．数据项【分析】线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为(a1,a2,…,an)，其中n为表长，n=0时称为空表。【答案】C2．顺序存储结构的优点是。A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示【分析】顺序存储结构是采用一组地址连续的存储单元来依次存放数据元素，数据元素的逻辑顺序和物理次序一致。因此，其存储密度大。【答案】A3．带头结点的单链表head为空的判断条件是。A．head==NULLB．head-next==NULLC．head-next==headD．head!=NULL【分析】链表为空时，头结点的指针域为空。【答案】B4．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表【分析】根据题意要求，该线性表的存储应能够很方便地找到线性表的第一个元素和最后一个元素，A和B都能很方便地通过头指针找到线性表的第一个元素，却要经过所有元素才能找到最后一个元素；选项C双链表若存为双向循环链表，则能很方便地找到线性表的第一个元素和最后一个元素，但存储效率要低些，插入和删除操作也略微复杂；选项D可通过尾指针直接找到线性表的最后一个元素，通过线性表的最后一个元素的循环指针就能很方便地找到第一个元素。【答案】D5．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表【分析】某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运第2章线性表算。因此不需要移动线性表种元素的位置。根据题意要求，该线性表的存储应能够很方便地找到线性表的任一指定序号的元素和最后一个元素，顺序表是由地址连续的向量实现的，因此具有按序号随机访问的特点。链表需要通过指针才能找到线性表的莫以指定序号的元素，需要一定的时间开销。【答案】A6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表【分析】根据题意要求，该线性表的存储应能够很方便地找到线性表的最后一个元素和最后一个元素的前驱元素，A和B都不能很方便地通过头指针找到线性表的第一个元素；选项C可以方便地找到最后一个元素，单不能很快地找到其前驱元素；选项D为双向循环链表，可以很方便地找到线性表的最后一个元素，通过其前驱指针，从而可以方便地找到其前驱元素。【答案】D7．静态链表中指针表示的是。A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址【分析】静态链表采用的是链式方式存储线性表，以数组方式存储链表的数据，指针域存储的是该结点逻辑上的后继结点的相对地址（即在数组中的下标），也称为静态指针。【答案】B8．链表不具有的特点是。A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比【分析】链表是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据元素之间的线性关系，对每个数据元素，除了存放数据元素自身的信息之外，还需要和存放其后继元素所在的存储单元的地址。链表不具有按序号随机访问第i个元素的特点，必须通过标识链表的头指针（或尾指针）“顺藤摸瓜”才能找到第i个结点。【答案】B9．线性表的静态链表存储结构与顺序存储结构相比优点是。A．所有的操作算法简单B．便于插入和删除C．便于利用零散的存储器空间D．便于随机存取【分析】静态链表采用的是链式方式存储线性表，因此其具有链式存储的特点。【答案】B10．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为。A．O(log2n)B．O(1)C．O(n)D．O(n2)【分析】在第i个位置上插入新元素需要从最后一个元素开始后移直到第i个元素后移为止，后移元素的次数为n-i+1，即时间复杂度为O(n)。数据结构典型例题解析【答案】C11．线性表（a1,a2,…,an）以链接方式存储时，访问第i个位置元素的时间复杂性为。A．O(i)B．O(1)C．O(n)D．O(i-1)【分析】线性表以链接方式存储时，访问第i个位置元素从第一个元素开始移动指针到第i个元素，移动指针的次数为n-i+1，即时间复杂度为O(n)。【答案】C12．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。A．nB．2n-1C．2nD．n-1【分析】当一个表的最小元素大于另一个表的最大元素时比较次数为最少，共需n次。【答案】A13．非空的循环单链表head的尾结点p满足。A．p-next==headB．p-next==NULLC．p==NULLD．p==head【分析】非空的循环单链表head的尾结点的后继指针指向链表的头结点。【答案】A14．在双循环链表p所指结点之后插入s所指结点的操作是。A．p-next=s;s-prior=p;p-next-prior=s;s-prior=p-next;B．p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;C．s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;D．s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;【分析】由于要将s所指结点插入到p所指结点之后，p结点为s结点的前驱，s结点为p结点的新后继，而结点p的原后继结点为结点s的后继结点，结点s为结点p的原后继结点的前驱结点s。在选项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所指结点的前驱结点，若在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．线性表的特点是每个元素都有一个前驱和一个后继。【分析】线性表是一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关第2章线性表系。线性表中除第一个数据元素和最后一个数据元素外，外每个元素都有一个前驱和一个后继。【答案】错误2．顺序存储的线性表可以按序号随机存取。【分析】因为顺序表在内存是用地址连续的空间存储的，设a1的存储地址为Loc(a1)，每个数据元素占d个存储地址，则第i个数据元素的地址为：Loc(ai)=Loc(a１)+(i-1)×d1≤i≤n这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点。【答案】正确3．链表中的头结点仅起到标识的作用。【分析】头结点是附加在第一个元素结点之前的一个结点，当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点，为空表时，该指针域为空。其作用是为了运算上的方便。【答案】错误4．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。【分析】链表是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据元素之间的线性关系，对每个数据元素，除了存放数据元素自身的信息之外，还需要存放其后继元素所在的存储单元的地址。链表中结点的存储空间可以是不连续的，但结点内部的存储空间必须是连续的。【答案】错误5．在单链表中和在顺序表中插入一个元素其时间复杂度均为O(n)，因此说它们的执行时间是相等的。【分析】大O记法表示时间渐近复杂度，是指一个算法中的时间耗费，往往是问题规模n的函数T(n)，当n趋向于无穷大时，T(n)的数量级称为算法的时间渐近复杂度。虽然两种存储结构下的插入操作时间复杂度均为O(n)，但由于两者的基本操作不同，因此不能说它们的执行时间是相等的。【答案】错误6．所谓静态链表就是一直不发生变化的链表。【分析】静态链表是指以数组方式存储链表的数据，数组的每个元素包含有数据域data和指针域next，其存储的是该结点逻辑上的后继结点的相对地址（即在数组中的下标）。其存储空间不发生变化，而其内容可以发生变化。【答案】错误7．静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。【分析】静态链表是指以数组方式存储链表的数据，对链表进行插入和删除运算时，只需改变指针，不需移动数据。【答案】正确8．静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素数据结构典型例题解析的时间与i无关。【分析】因为静态链表的存取特性与动态链表是一样的，只能顺序地找到第i个元素，不能随机地存取第i个元素，故其存取表中第i个元素的时间与i有关。【答案】错误9．静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。【分析】因为静态链表是以数组方式存储链表的数据，数组空间大小在数组定义时就已确定，一般不会发生变化。【答案】正确10．取线性表的第i个元素的时间同i的大小有关。【分析】存取线性表中数据元素的时间开销与其存储结构有关。顺序存储结构具有按序号随机访问的特点，同i的大小无关。【答案】错误三、简答题1．如图2-11所示的双向链表中，欲在结点p前插入一个结点s，请完成有关操作。s-prior=p-prior;p-prior=s;s-next=p;【解答】只能是“s-prior-next=s;”而不能为“p-prior-next=s;”。因为在上面的第二条语句中已经改变了结点p的前驱结点，结点p的前驱结点已经为s结点，而不是操作前的前驱结点。在下面的语句顺序下，可有两个答案进行选择。s-prior=p-prior;p-prior=s;s-next=p;读者做这种题时，最好予以图示，不易出错。2．已知线性表非递减有序，存储于一个一维数组A[0..n-1]中（表长为n，设为全局量），下面算法的功能是什么？voiddel(DataTypeA[]){inti,j;i=1;while(i=n-1)if(A[i]!=A[i+1])i++;else{for(j=(i+2);jn;j++)A[j-1]=A[j];n--;}}xyzps图2-11第1题图第2章线性表【解答】由于一维数组中的元素按元素非递减有序排列，值相同的元素必为相邻的元素，因此依次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找。故算法功能是删除一维数组中多余的值相同的元素。3．下述算法的功能是什么？LinkListDemo(LinkListL){//L是无头结点的单链表LNode*q,*p;if(L&&L-next){q=L;L=L-next;p=L;while(p-next)p=p-next;p-next=Q;q-next=NULL;}returnL;}【解答】算法的功能是把单链表的第一个结点从表头移到了链尾。返回的L指向原链表的第二个结点。若原链表表示的线性表是(a1,a2,…,an)，则操作后表示的线性表为(a2,a3,…,an,a1)。4．试描述头指针、头结点、