《数据结构习题课》由会员分享，可在线阅读，更多相关《数据结构习题课（9页珍藏版）》请在金锄头文库上搜索。
1、完美WORD格式1、试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。 答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。链表的头指针是一指向链表开始结点的指针（没有头结点时），单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指 针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个 位置上的操作与在表其他位置上的操作一致（都是在某一结点之后）。2、 何时选用顺序表、何时选用链表作为线性表的存储结构为宜？答：在实际应用中，应根据具体问题的要求和性质来选择
2、顺序表或链表作为线性表的存储结 构，通常有以下几方面的考虑：1）基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为 了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采 用动态链表作为存储结构为好。2）基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等操作时，宜采用链表做存储结构。 并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。?具体的移动次数取决于哪两个n/2个结点，删除一个结点需平均n以及需插入或删除的位置i。i3、在
3、顺序表中插入和删除一个结点需平均移动多少个结点 因素？答：在等概率情况下，顺序表中插入一个结点需平均移动 移动（n-1）/2个结点。具体的移动次数取决于顺序表的长度 越接近n则所需移动的结点数越少。4、为什么在单循环链表中设置尾指针比设置头指针更好？答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和 终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是 rear-next-next 和rear, 查找时间都是 0（1）。若用头指针来表示该链表，则查找终端结点的时间为O（n）。5、在单链表、双链表和单循环链表中，若仅知道指
4、针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去？若可以，其时间复杂度各为多少？答：我们分别讨论三种链表的情况。1）单链表。当我们知道指针 p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。2）双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O（1）。3）单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置（直接后继），又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应
5、为O（n）。6、下述算法的功能是什么？Lin kList Demo(L in kList L)/ L是无头结点单链表ListNode *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;return L;/ Demo答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。7、 不带头结点的单链表head为空的判定条件是()。A head=NULL B 、head-next=NULLC、head-next=
6、head D 、head!=NULL8、 在一单链表中，已知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;9、 在一个单链表中，若p所指的结点不是最后结点，在 p之后插入s结点，则执行（）。A s-next=p;p-next=s;B、s-next=p-next;p-next=s;C s_next=p-next;p=s;D p_next=s;s-next=p;10、 在一个单链表中，若删除
7、p所指结点的后续结点，则执行（）。A、p-next=p-next-next;B p=p-next;p-next=p-next-next;C、p-next=p-next;D p=p-next-next;11、从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要平均比较()个结点？A nB n/2C、(n-1)/2D (n+1)/212、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是()。A O(1) B O(n)C、O(n2)D O(nlog 2n)13、给定有n个元素的向量，建立一个有序单链表的时间复杂度是()。2A O(1) B O(n)C、O(
8、n) D O(nlog 2n)14、带有一个头结点的单链表head为空的条件是15、对于一个具有n个结点的单链表，在已知p所指结点之后插入一个新结点的时间复杂度为;在给定值为x的结点后插入一个新结点的时间复杂度是 。16、设顺序表L是一个非递减有序表， 试写一算法，将x插入L中，并使L仍是一个有序表。解：因已知顺序表L是递增有序表，所以只要从头找起找到第一个比它大(或相等)的结点数据，把x插入到这个结点所在的位置就是了。算法如下：void Insertin creaseList(Sqlist *L,Datatype x) int i;for( i=0;ilength & L-dataix;i+
9、);查找并比较，分号不能少ListI nsert (*L,i,x);II调用顺序表插入函数/ In serti ncreaseList17、设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。解：与上题相类似，只要从头找到第一个比x小(或相等)的结点数据，在这个位置插入就可以了。算法如下：void in sertDecreaseList(Sqlist *L,Datatype x) int i;for (i=0;ile ngth & L-dataix;i+); /查找ListI nsert(*L,i,x);/调用顺序表插入函数 in sertDecreaseList18、 写一
10、算法在单链表上实现线性表的ListLe ngth(L) 运算。解：求单链表长只能用遍历的方法了，从头数到尾。算法如下：int ListLength( LinkList L ) int len=0; ListNode *p;p=L;/设该表有头结点while (p-n ext) p=p-n ext;len+;return len;/ ListLe ngth19、 已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法 将这两个链表连接在一起，请分析你的算法的时间复杂度。解：算法如下：LinkList Link( LinkList L1 , LinkList L2 )/将两
11、个单链表连接在一起ListNode *p, *q;p=L1; q=L2;while ( p- next ) p=p- next; /查找终端结点p-next = q-next ;/将L2的开始结点链接在L1之后return L1 ;/ Li nkList Li nk分析：本算法的主要操作时间花费在查找L1的终端结点上，与L2的长度无关，所以本算的法时间复杂度为：m+1=0(m)20、删除带头结点单链表 L中的元素x。解：算法如下：Void delete(Li nkList & L,ElemType x) p=L-n ext; pre=L;while(p) if(p-data=x) pre_n
12、ext=p-n ext; free(p); p=pre _n ext; else pre=p; p=p-n ext; /delete21、已知：A=(a1,a 2,a n-i ,a n) B=(b 1,b 2,bn-i,bn)均为顺序表，试编写一个比较A、B大小的算法。解：算法目标是分析两表的大小，所以不应破坏原表。表的大小指的是词典顺序”，而非表的长度。基本操作为：同步比较两个表中相应的数据元素。假设：int compare(SqList La,SqList Lb)循环条件：(i=La.Le ngth)&( i=Lb.Le ngth)主要操作为：if (La.elemi=Lb.elemi)
13、i+; else if (La.elemi La.Le ngth)&( iLb.Le ngth) return 0; (iLb .Len gth) return 1; (iLa .Len gth )&(idatanext; if (p) while (p&p-datan ext;q=pre _n ext; pre_n ext=p;while(q!=p)q=p时，删除的为一个元素 s=q; q=q- next; free(s); /释放中间结点23、写一算法将单链表中值重复的结点删除，使所得结果表中各结点值均不相同。解：本题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值比较， 发现相同
14、的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。第二种算法是将单链表按值的大小排序，排好后的结点按相同的删除。具体算法略。24、试编写在带头结点的单链表中删除(一个)最小值结点的(高效)算法。void delete (Lin klist &L )题目分析本题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。LinkList Delete( LinkList L )/ L是带头结点的单链表，本算法删除其最小值结点。 p=L-next ;/ p为工作指针，指向待处理结点。假定链表非空。pre=L ;/ pre指向最小值结点的前驱。q=p ;/ q指
