数据结构错题.doc

《数据结构错题.doc》由会员分享，可在线阅读，更多相关《数据结构错题.doc（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、如有侵权，请联系网站删除，仅供学习与交流数据结构错题【精品文档】第 8 页一、图【1】各边权值不同的无向连通图的最小生成树是唯一的【2】当各边上的权值( 均相等 )时,BFS算法可用来解决单源最短路径问题解析：当权值相同，则最短路径问题转化为求边数最少的问题，BFS可以保证求得源点到汇点的最少边数【3】无向图：若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图。无向图G的极大连通子图称为G的最强连通分量有向图：有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。有向图的极大强连通子图称为G的强连通分量。【

2、4】无向图存储：邻接矩阵、邻接表、多重邻接表有向图存储：邻接矩阵、邻接表、十字链表【5】若有向图不存在回路,即使不用访问标志位同一结点也不会被访问两次()解析：错误。如果一个点的入度大于1的话，就有可能被多次访问【6】有向图是否有环的判定算法，主要有深度优先和拓扑排序两种方法。【7】一个AOV网应该是一个有向无环图 ，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行。既然AOV网是一个有向无环图，则其必然存在拓扑序列。【8】关键路径：1）顶点表示事件，弧表示活动 2）如果顶点A-B有弧，如果让弧表示为L，则A为L的弧尾，B为L的弧头，即有箭头的那一端叫头。【9】若无向图G = （

3、V.E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（）解析：任何情况都连通的最少边数表示边分布最浪费的最少边情况，取点数减一的完全图6*5/2=15再加一条边得结果16【10】AOE网的定义：在带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图简称为AOE网。从定义上来看，很容易看出两种网的不同，AOV网的活动以顶点表示，而AOE网的活动以有向边来表示，AOV网的有向边仅仅表示活动的先后次序。纵观这两种网图，其实它们总体网络结构是一样的，仅仅是活动所表示的方式不同，因此可以猜想从AOV网转换成AOE网应该是可行的。AOV网不能有环。A

4、OE网一定是有向无环图【11】关键活动延期完成，必将延期整个工程完成时间。如果有多条关键路径，此时延期的关键活动所在路径成为关键路径，其他原关键路径变为非关键路径。关键活动提前完成，不一定使整个工程提前完成。因为关键路径可能不唯一，一条路径上的关键活动提前，只能使这条路径变为非关键路径，其他关键路径不受影响。【12】图G的拓扑序列唯一，则其弧数必为n-1(其中n为G的顶点数)解析：错误。有向图的邻接矩阵上三角全为1即可达到拓扑唯一，那么边数为n(n-1)/2【13】无向图的邻接矩阵可用一维数组存储。解析：正确。习惯上无向图的邻接矩阵一般用二维数组存储，这样使用方便。当然，任意二维数组都是可以用

5、一维数组存储的，只是用起来不方便。【14】既使有向无环图的拓扑序列唯一，也不能唯一确定该图。解析：正确。如果顶点有多个直接后继，排序结果通常不唯一，所以拓扑排序的结果唯一的情况是，每个顶点有唯一的前驱后继关系。【15】用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点的个数有关，而与图的边数无关。这种说法（ 正确 ）【16】设G是一个具有6个顶点,11条边的图，其每个顶点的度为3或4，则图G是什么图？（A）A、G是平面图； B、G不连通； C、G为偶图(也称二部图)； D、G不是哈密顿图。【17】p个顶点p条边的连通图中至少有多少个生成树？解析：3个。p个顶点p

6、条边的连通图中至少有多少个生成树，连通图相当于在树上多加了一条边，所以其中必然会有一个回路，生成树的数量应该等于回路的边数，如果不考虑重边和自环的情况最小的回路必然是3。【18】完全偶图(也称完全二部图) 既是欧拉图又是哈密顿图的充分必要条件是下列哪一个？m=n且m与n都是偶数；二、树【1】不含任何结点的空树（ 是一棵树也是一棵二叉树 ）。【2】如果T1是由有序树T转换而来的二叉树,那么T中结点的前序就是T1中结点的前序,T中结点的后序就是T1中结点的中序【3】树中的结点和图中的顶点就是指数据结构中的数据元素解析：对。数据元素是数据的基本单位。在计算机中作为一个整体考虑和处理。在有些情况下，数

7、据元素也称为元素、记录等，数据元素用于完整的描述一个对象，如图中的顶点。数据项是组成数据元素的、有独立含义的、不可分割的最小单位。如学生基本信息中的学号、姓名、性别等都是数据项。【4】如果有N个节点用二叉树结构来存储，那么二叉树的最小深度是多少？解析：以2为底2N的对数，向下取整【5】二叉树在线索化后，仍不能有效求解的问题是（）。解析：后序线索二叉树中求后序后继。后序线索二叉树的遍历仍需要借助栈，但其他二者却不需要。【6】设F是一个森林,B是由F变换得到的二叉树。若F中有n个非终端结点,则B中右指针域为空的结点有( n+1 )个【7】在线索化二叉树中，节点t没有左子树的充要条件是（ t-lta

8、g=1 ）【8】在中序线索二叉树中,每一非空的线索均指向其祖先结点()解析：中序遍历的顺序为：左、根、右，所以对于每一非空的线索，左子树结点的后继为根结点，右子树结点的前驱为根结点，再递归的执行上面的过程，可得非空线索均指向其祖先结点。【9】若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ 11 ）解析：性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)=0度结点数(n0) + 1度结点数(n1) + 2度结点数(n2)。由此，得到等式一。(等式一) n=n0+

9、n1+n2另一方面，0度结点没有孩子，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：n1+2n2。此外，只有根不是任何结点的孩子。故二叉树中的结点总数又可表示为等式二。(等式二) n=n1+2n2+1由(等式一)和(等式二)计算得到：n0=n2+1。原命题得证！三、数组【1】关于 int a10; 问下面哪些不可以表示 a1 的地址？A、a+sizeof(int) B、&a0+1 C、(int*)&a+1 D、(int*)(char*)&a+sizeof(int)解析：A 不正确， 在32位机器上相当于指针运算 a + 4【2】int a23 = 0;printf(%x %

10、x %xn, a0, a1, &a12);printf(%x %x %xn, a, a + 1, &a + 1);输出：1da6e790 1da6e79c 1da6e7a4 1da6e790 1da6e79c 1da6e7a8【3】下面有关数据结构的说法是正确的？A、数组和链表都可以随机访问 B、数组的插入和删除可以 O(1)C、哈希表没有办法做范围检查 D、以上说法都不正确解析：B。在数组的开头或结尾插入和删除 是O(1),但正常情况下为O(n)所以说数组的插入和删除复杂度可能是O(1)。【4】一个非空广义表的表尾()A、不能是子表 B、只能是子表 C、只能是原子 D、是原子或子表解析：B。

11、（1）数据结构对广义表的表头和表尾是这样定义的： 如果广义表LS=（a1,a2.an）非空，则 a1是LS的表头，其余元素组成的表（a2,a3,.an）是称为LS的表尾。根据定义，非空广义表的表头是一个元素，它可以是原子也可以是一个子表，表尾则必定是子表。例如:LS=(a,b),表头为a,表尾是（b）而不是b.另外：LS=（a)的表头为a，表尾为空表(). （2）非空广义表，除表头外，其余元素构成的表称为表尾，所以非空广义表尾一定是个表【5】在Java中,下列说法错误的有（ BCD ）A、数组是一种对象 B、数组属于一种原生类 C、int number = 31,23,33,43,35,63;

12、 D、数组的大小可以任意改变【6】广义表(a,b,c),d,e,f)的长度是4()解析：错误；长度：去掉一层括号剩下的是几部分。 深度：去掉几层括号可以到最后一部分。比如： 例如E(a,(a,b),(a,b),c)的长度和深度分别为1和4【7】对n个记录的线性表进行快速排序为减少算法的递归深度,以下叙述正确的是()A、每次分区后,先处理较短的部分 B每次分区后,先处理较长的部分C、与算法每次分区后的处理顺序无关 D、以上三者都不对解析：A；在快速排序中，需要使用递归来分别处理左右子段，递归深度可以理解为系统栈保存的深度,先处理短的分段再处理长的分段，可以减少时间复杂度；如果按长的递归优先的话，

13、那么短的递归会一直保存在栈中，直到长的处理完。短的优先的话，长的递归调用没有进行，他是作为一个整体保存在栈中的，所以递归栈中的保留的递归数据少一些。【8】若要删除 book 表中的所有数据，如下哪些语法是错误的？A、drop table book; B、truncate table book; C、delete from book; D、delelet *from book;解析：A： drop table book 是删除整个表，题目的潜在意思是删除表中的数据而并非删除整个表。因此A错。B： truncate table book 是删除表中的数据，删除速度比delete更快，无法撤回（回退

14、）。C： delete from book 删除数据表中的数据，可以回退，可添加where 子句。D：语法错误。四、链表【1】当静态链表采用数组实现时，插入与删除操作仍需移动元素，这种说法（）解析：错误。静态链表采用数组实现链表的存储，用空间换取时间，删除与插入需要改的是游标。【2】静态链表中指针表示的是（ 数组下标 ）静态链表中指针表示的是( 下一元素在数组中的位置 )【3】以下属于逻辑结构的是( C )A、顺序表 B、哈希表 C、有序表 D、单链表解析：从大的方面来说，数据结构是反映数据的一种形式，它具体分为逻辑结构和物理结构，1，逻辑结构：它是表现数据之间的一种关系的结构，分为线性结构和

15、非线性结构；2，物理结构：它是表现数据的是如何存储的结构，计算机内部是如何安排该数据的存储，通常分为顺序结构，链式结构，索引结构，哈希结构；该题中，顺序表，哈希表，单链表均是存储结构；而有序表从字面意思是表达了数据之间是以升序或者降序的关系存在，感觉也是在考察语文功底，明显有序表是逻辑上的关系。【4】在有n个结点的二叉链表中，值为非空的链域的个数为（ ）。解析：在有N个结点的二叉链表中必定有2N个链域。除根结点外，其余N-1个结点都有一个父结点。所以，一共有N-1个非空链域，其余2N-（N-1）=N+1个为空链域。【5】一个长度为99的循环链表，指针A和指针B都指向了链表中的同一个节点，A以步

16、长为1向前移动，B以步长为3向前移动，一共需要同时移动多少步A和B才能再次指向同一个节点_。解析：设A走x步 那么B就走3x步 两个要碰到 所以有(3x-x)%99=0 x取99【6】队列和栈都是运算受限的线性表,只允许在表的两端进行运算()解析：错误。前半句是对的，后半句不对 栈只能在一端操作，队列可以在两端操作五、队列【1】已知循环队列存储在一维数组A0.n-1中，且队列非空时 front 和 rear 分别指向队头和队尾元素。若初始时队列为空，且要求第 1 个进入队列的元素存储在 A0处，则初始时 front和 rear 的值分别是（ ）。解析：首先根据循环队列的公式，插入元素，fron

17、t不变，rear=(rear+1)%n。在本题中，即(rear+1)%n=0，可得rear=n-1。此时队列中只有一个元素，则front与rear应该指向同一个位置，即front也应该为0。综上，front=0， rear=n-1【2】以下开源软件中经常被用作队列的是哪个？（BD）A、MongoDB B、Redis C、Memcached D、kafka【3】循环队列的存储空间为 Q(1:50)，初始状态为 front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又插入一个元素，则循环队列中的元素个数为（ ）。A、1，或50且产生上溢错误 B、51 C、2

18、6 D、2解析：循环队列是队列的一种顺序存储结构，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。入队运算时，队尾指针进1（即rear+1），然后在rear指针指向的位置插入新元素。当front=rear=25时可知队列空或者队列满，此后又插入了一个元素，如果之前队列为空，插入操作之后队列里只有一个元素，如果插入之前队列已满(50个元素)，执行插入则会产生溢出错误。故本题答案为A选项。六、哈希【1】采用线性探测法处理散列时的冲突,当从哈希表删除一个记录时,不应将这个记录的所在位置置空,因为这会影响以后的查找解析：正确。如果初始地址在置空位置，查找失败 如果

19、初始位置不在置空位置，查找过程中遇到置空位置，探测失败，查找失败【2】HASH函数冲突处理方式（1）开放定值法 这个方法分为几种其中一种是线性探索，就是这个值有冲突就向下一个寻址依次加1向后直到不冲突为止，但是这样有的时候会造成效率偏低。所以还有的时候会使用二次探索法就是使用平方的方式等。（2）拉链法 这个方法就是使用链表处理冲突，只要有冲突就增加一个链表节点。（3）双哈希法 就是这个hash函数有冲突，就换一个hash函数试试。（4）建立公共溢出区 这种方法就是将哈希表分为基本表和溢出表，凡是有冲突的就直接放到溢出区。【3】若装填因子a为1,则向哈希表中散列元素时一定会产生冲突解析：错误。装

20、填因子为1，表明装入的元素个数与表长相等装填因子 a = 装入的元素个数/哈希表的长度若采用链地址法处理，则向哈希表中散列元素时不一定会产生冲突；【4】设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到Hash表中需要做几次线性探测？解析：第一个关键字直接插入，第二个关键字要做1次探测，所以类推n个关键词要做0+1+2+.+(n-1) = n*(n-1) / 2 【5】采用哈希表组织100万条记录，以支持字段A快速查找，则（ C ）A、理论上可以在常数时间内找到特定记录 B、所有记录必须存在内存中C、拉链式哈希最坏查找时间复杂度是O（n） D、哈希函数的选择跟A无关解析

21、：A，记录共有100万条，一般的哈希表长度不可能做这么长，因此要解决散列冲突问题，因此一般不能在常数时间内找到记录B，哈希查找可以在外存中查找，可以用哈希表映射到文件，分级查找C，最坏情况是所有记录的散列值都冲突，这样就退化为线性查找，时间复杂度为O（n）D，哈希函数的选择跟A关系密切，跟A的字段类型有关，哈希函数设计的好坏也影响着查找的速度【6】现有一完全的P2P共享协议，每次两个节点通讯后都能获取对方已经获取的全部信息，现在使得系统中每个节点都知道所有节点的文件信息，共17个节点，假设只能通过多次两个对等节点之间通讯的方式，则最少需要（ 30 ）次通讯【7】常用构造散列函数的方法有：直接定

22、址法，数字分析法，折叠法，平方取中法，乘余取整法减去法，基数转换法，除留余数法，随机乘数法，字符串数值哈希法，旋转法，伪随机数法【8】设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( 9 )【9】有一组关键字为77,28,38,41,45,1,9,31,99,51,23,47,68,61.1,请构造一个hash函数，形式为H（key）=key mod p，装填因子a=0.8，用链地址法解决冲突；2计算等概率情况下查找成功的平均查找长度；3计算等概率情况下查找

23、失败的平均查找长度（空指针的比较不计入）。解析：装填因子 a 的定义知道，a=n/m 其中n 为关键字个数，m为表长m = n / a = 14 / 0.8 = 17.5(取18) 取17比较好，一般都是取素数77%18=5 41%18=5 23%18=5 1/328%18=10 138%18=2 145%18=9 9%18=9 99%18=9 1/31%18=1 131%18=13 147%18=11 168%18=14 161%18=7 151%18=15 1查找成功的平均查找长度：20/14 查找失败的平均查找长度：14/18查找成功时，分母为哈希表元素个数，查找不成功时，分母为哈希表长

24、度。七、字符串【1】n 个字符构成的字符串，假设每个字符都不一样，问有多少个子串？解析：长度为 1 的字符串 n 个长度为 2 的 n-1 个长度为 3 的 n-2 个长度为 n 的 1 个然后 n+(n-1)+(n-2)+.+1 =n(n+1)/2，再加一个空串串ababaaababaa的next数组为()解析：i 0 1 2 3 4 5 6 7 8 9 10 11 s a b a b a a a b a b a a nexti -1 0 0 1 2 3 1 1 2 3 4 5答案为011234223456先计算前缀nexti的值： （字符串匹配是 从头开始的 和 从尾开始的字符串进行匹配是

25、否重复 ）nexti的值主要是看si之前的字符串中重复的子串长度。next0 = -1，定值。 next1是看s1之前的字符串“a”中重复的子串长度为0，故next1 = 0。next2是看s2之前的字符串“ab”中重复的子串长度为0，故next2 = 0。next3是看s3之前的字符串aba中重复的子串长度，s0与s2重复，长度为1，故next3 = 1。next4是看s4之前的字符串abab中重复的子串长度，s01与s23重复，长度为2，故next4 = 2。next5是看s5之前的字符串ababa中重复的子串长度，s012与s234重复，长度为3，故next5 = 3。next6是看s6

26、之前的字符串ababaa中重复的子串长度，s0与s5重复(因为多了一个a，无法找到长度为3的重复字符串，这只能是s0和s5重复)，长度为1，故next6 = 1。同样的，求next7和next8、next9、 next10、 next11 分别为1和2、3、4、5。字符串ababaabab的nextval为()解析：i 0 1 2 3 4 5 6 7 8s a b a b a a b a bnext -1 0 0 1 2 3 1 2 3nextval0 = -1;s1=b != snext1=s0=a; nextval1=next1=0;s2=a = snext2=s0=a, nextval2

27、=nextval0=-1;s3=b = snext3=s1=b, nextval3=nextval10;s4=a = snext4=s2=a, nextval4=nextval2=-1;s5=a != snext5=s3=b, nextval5=next5=3;s6=b = snext6=s1=b, nextval6=nextval1=0;s7=a = snext7=s2=a, nextval7=nextval2=-1;s8=b = snext8=s3=b, nextval8=nextval3=0;nextval -1 0 -1 0 -1 3 0 -1 0有的时候下标从1开始即 0 1 0 1 0 4 1 0 1八、时间复杂度计算