备战初赛错题记录

线性表若采用链表存储结构，要求内存中可用存储单元地址（ ）。

 A. 必须连续

 B. 部分地址必须连续

 C. 一定不连续

 D. 连续不连续均可

答案：D

解析：在链式存储结构中，存储数据结构的存储空间可以是连续的，也可以是不连续的，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。即你只要用指针标记好位置即可，不用非得连续存储。

 

6 个顶点的连通图的最小生成树，其边数为（ ）。

 A. 6

 B. 5

 C. 7

 D. 4

答案：D

解析：设连通图g的顶点数为n，则g的最小生成树的边数为n-1.最大的不连通的情况，就是其中5个点完全连通而他们均不与最后一个点连通。 此时边的数目为4+3+2+1=10. 当边的数目大于10时,该图必定连通.设连通图G有（n+1）个顶点,若每个顶点连出至少两条边,那么此时至少有n+1条边(任意图上所有顶点度数和等于边数的两倍),结论已经成立.否则,那么至少有一个顶点只连出一条边.不妨设为A,由于去掉这条边AB后不影响其他点的连通性,那么剩下的n个点之间有归纳假设至少有（n-1)条边,所以G至少有n条边.

 最小生成树:1----2---3-----4 -----5 -----6      6不需要再与1连线，通过中间各连线连通。

最大不联通情况：即尽可能的在保持其中一个点孤立的情况下向连通的点间插入边。设被孤立的点为6号点；

则 1号与除六号以外的所有点间都有一条边，总共4条。其它点相同。则1到5之间总共有4+3+2+1=10条边（注意减去重复的边，如1--2和2--1相同）

此时多加一条边，就必须有新的点，因为1至5号点间已经满了。

 

（PS）为什么是一个点被孤立而不是分成两段呢？如：1-2-3-4   5-6  然后再分别向里加边。

因为一个点最多有0条边，两个点最多有一条边，三个点最多有3条边，四个点。。。

可以得出基数n越大，n+1个点所添加的边就越多。如将六个点先分为1-2  3-4-5  6

那么将六号点添加在两个点的段中可以增加2条边，但添加在三个点的段中就可以加3条边，

所以向多的中加，那么将有n个点分为n-1 与 1 两端是最大的不联通情况，此时最多的边数为：n-1+n-2+n-3+...=n*n-（1+n）*n/2;

      

 

具有 n 个顶点，e 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为（ ）。

 A. Θ(n2)

 B. Θ(e2)

 C. Θ(ne)

 D. Θ(n + e) 

答案： D

解析：深度优先和广度优先遍历图的过程实质上是对某个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。当图用邻接矩阵表示时，查找所有顶点的邻接点所需时间为O(n²)。若以邻接表作为图的存储结构，则需要O(e)的时间复杂度查找所有顶点的邻接点。因此，当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度为 O(n+e)。

 

双向链表中有两个指针域，llink 和 rlink，分别指回前驱及后继，设 p 指向链表中的 一个结点，q 指向一待插入结点，现要求在 p 前插入 q，则正确的插入为（ ）。

 A. p->llink = q; q->rlink = p; p->llink->rlink = q;q->llink = p->llink;

 B. q->llink = p->llink; p->llink->rlink = q; q->rlink = p;p->llink = q->rlink;

 C. q->rlink = p; p->rlink = q;p->llink->rlink = q; q->rlink = p;

 D. p->llink->rlink = q; q->rlink = p;q->llink = p->llink; p->llink = q;

答案：D

解析：因为有四个表达式，且前驱后驱都只相邻一个单位，所以我们大胆推测这四个表达式的含义是这样的：

假设有三个点a p q ，将q插入p前，则为：a的后驱为q，q的前驱为a，p的前驱是q，q的后驱是p。

首先，a的后驱为q；a此时为p的前驱，即p->llink=a；要表示a的后驱为q，则a->rlink=q；所以p->llink->rlink=q；

其次，q的前驱为a；p->llink=a；即q->llink=p->llink；

然后，p的前驱是q；p->llink=q；

最后，q的后驱是p；q->rlink=p；

 

以下属于操作系统的有（ ）。

 A. Windows XP

 B. UNIX

 C. Linux

 D. Mac OS

答案：ABCD

补充：Windows，Windows NT，WinX， LIU，PC-DOS，DOS、OS/2、UNIX、XENIX、LINUX、Netware、WIN95、WIN98、WINME、WINNT、WIN2000、WINXP、WIN2003、UNIX、LINEX等等都是操作系统

原文链接:https://www.cnblogs.com/127zero99/p/11697691.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有