数据结构复习题带答案

一．是非题（共分，每题分）1.数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。(F)（D，S）二元就够了2简单地说,数据结构是带有结构的数据元素的集合。(T)3判断带头结点的非空循环单链表（头指针为L）中指针p所指结点是最后一个元素结点的条件是：p-next==L。(T)4线性表的链式存储结构具有可直接存取表中任一元素的优点。(F)只能顺序存取，不能随机5线性表的顺序存储结构优于链式存储结构。(F)6.在单链表P指针所指结点之后插入S结点的操作是：P-next=S;S-next=P-next;。(F)两句反了7对于插入、删除而言，线性表的链式存储优于顺序存储。(T)8.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(F)链式优点9.栈和队列是操作上受限制的线性表。(T)10.队列是与线性表完全不同的一种数据结构。(F)11.队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(F)12.栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。()F13.栈是限定仅在表头进行插入和表尾进行删除运算的线性表。()F15二叉树是一棵结点的度最大为二的树。(F)16赫夫曼树中结点个数一定是奇数。(T)17在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(T)18假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(F)19.通常，二叉树的第i层上有2i-1个结点。(F)最多可以有20.中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(T)21二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(T)22由树结点的先根序列和后根序列可以唯一地确定一棵树。(T)23邻接多重表可以用以表示无向图，也可用以表示有向图。(F)24可从任意有向图中得到关于所有顶点的拓扑次序。(F)有环的不行25有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(T)26关键路径是AOE网中源点到汇点的最短路径。(F)长27连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。(T)28一个无向图的连通分量是其极大的连通子图。(T)29十字链表可以表示无向图，也可用以表示有向图。(F)30邻接表可以表示有向图，也可以表示无向图。（T）32.二叉排序树的最大查找长度与（LOG2N）同阶。(T)33选用好的HASH函数可避免冲突。(f)34折半查找不适用于有序链表的查找。(T)35.对于目前所知的排序方法，快速排序具有最好的平均性能。(T)36对于任何待排序序列来说，快速排序均快于冒泡排序。(F)37在最坏情况下，堆排序的时间性能是O(nlogn),比快速排序好(T)选择题。从逻辑上可以把数据结构分成()。CA.动态结构和静态结构B.顺序组织和链接组织C.线性结构和非线性结构D.基本类型和组合类型线性表L在()情况下适于使用链表结构实现。BA.不需修改L的结构B.需不断对L进行删除、插入C.需经常修改L中结点值D.L中含有大量结点带头结点的单链表L为空的判断条件是。B带头结点的循环链表L为空的判断条件是。CA.L==nullB.L-next==nullC.L-next==LD.L!=null递归程序可借助于()转化为非递归程序。Ca.线性表b.队列c:栈d.数组在下列数据结构中()具有先进先出（FIFO）特性，C()具有先进后出(FILO）特性。Ba．线性表b．栈c．队列d．广义表若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到()的序列。Ea:1,2,3b:1,3,2c:2,1,3d:2,3,1e:3,1,2f:3,2,1在计算递归函数时，如不用递归过程，应借助于()这种数据结构。BA.线性表B.栈C.队列D.双向队列栈和队列的一个共同点是()。CA.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点循环队列用数组A[0..m-1]存放其元素值，设头尾指针分别为front和rear，则当前队列中的元素个数是()。CA.rear-front-1B.Rear-front+1C.(rear-front+m)%mD.Rear-front4.对字符串s=’data-structure’执行操作replace(s,substring(s,6,8),’bas’)的结果是()。Da:‘database’b:‘data-base’c:‘bas’d:‘data-basucture’5.设有二维数组A5x7,每一元素用相邻的4个字节存储，存储器按字节编址.已知A的起始地址为100。则按行存储时，元素A06的第一个字节的地址是（）D按列存储时，元素A06的第一个字节的地址是（）Aa:220b:200c:140d:1246.对广义表A=（（a,(b)）,(c,()),d）执行操作gettail(gethead(gettail(A)))的结果是：（）。Ba:（）b:（（））c:dd:(d)假设用于通讯的电文仅由6个字符组成，字母在电文中出现的频率分别为7,19,22,6,32,14。若为这6个字母设计哈夫曼编码（设生成新的二叉树的规则是按给出的次序从左至右的结合，新生成的二叉树总是插入在最右），则频率为7的字符编码是（g），频率为32的字符编码是（C）。a:00b:01c:10d:11e:011f:110g:1110h:1111对二叉排序树（）可得到有序序列。Ca:按层遍历b:前序遍历c:中序遍历d:后序遍历在有n个结点的二叉树的二叉链表表示中，空指针数（）。Ba.不定b.n+1c.nd.n-1若某二叉树有20个叶子结点，有20个结点仅有一个孩子，则该二叉树的总结点数是()。CA．40B.55C.59D.61已知某二叉树的先序遍历次序为abcdefg中序遍历次序为badcgfe，则该二叉树的后序遍历次序为（C）。层次遍历次序为（a）。a:abcdefgb:cdebgfac:bdgfecad:edcgfba.图示的三棵二叉树中()为最优二叉树。CA)B)C)ca27abcddb752445abcd7524已知某二叉树的后序遍历和中序遍历次序分别为DBFGECA和BDACFEG。则其先序遍历次序为（b），层次遍历次序为（a）。a:abcdefgb:abdcefgc:abcdfegd:abcdegf已知某树的先根遍历次序为abcdefg后根遍历次序为cdebgfa。若将该树转换为二叉树,其后序遍历次序为（d）。a:abcdefgb:cdebgfac:cdegbfad:edcgfba设x和y是二叉树中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x在y之后，则x和y的关系是()。CA.x是y的左兄弟B.x是y的右兄弟C.x是y的祖先D.x是y的子孙用三叉链表作二叉树的存储结构，当二叉树中有n个结点时，有(D)个空指针。A.n-1B.nC.n+1D.n+2设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3，则与森林F对应的二叉树根结点的右子树上的结点个数是()。DA.m1B.m1+m2C.m3D.m2+m3下列二叉树中，()可用于实现符号不等长高效编码。Aa:最优二叉树b:次优查找树c:二叉平衡树d:二叉排序树邻接表存储结构下图的深度优先遍历算法类似于二叉树的()遍历。AA.先根B.中根C.后根D.层次设无向图G=(V,E)和G’=(V’,E’)，若G’是G的生成树，则下面不正确的说法是()。DA.G’是G的子图B.G’是G的连通分量C.G’是G的无环子图D.G’是G的极小连通子图且V’=V任何一个连通图的最小生成树()。BA．只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在深度优先遍历图使用了数据结构（b），而广度优先遍历图使用了数据结构（C）。A）数组B）栈C）队列D）线性表2．下列查找方法中（）适用于查找单链表。AA）顺序查找B）折半查找C）分块查找D）hash查找c:d:哈希表的查找效率取决于（）。Da:哈希函数b:处理冲突的方法。c:哈希表的装填因子。d:以上都是在Hash函数H(k)=kMODm中，一般来说，m应取()。C+D充分大的素数A.奇数B.偶数C.素数D.充分大的数在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用A方法。A.设置监视哨B.链表存贮C.二分查找D.快速查找静态查找表和动态查找表的区别在于()。BA.前者是顺序存储，而后者是链式存储B.前者只能进行查找操作，而后者可进行查找、插入和删除操作C.前者只能顺序查找，而后者只能折半查找D.前者可被排序，而后者不能被排序在一个含有n个元素的有序表上进行折半查找，找到一个元素最多要进行(B)次元素比较。A．log2(n)B.log2(n)+1C.log2(n+1)D.log2(n+1)+1若有序表中关键字序列为：14，20，25，32，34，45，57，69，77，83，92。对其进行折半查找，则在等概率情况下，查找成功时的平均查找长度是(C)。查找32时需进行(C)次比较。A.1B.2C.3D.4已知哈希表地址空间为A[9]，哈希函数为H(k)=kmod7，采用线性探测再散列处理冲突。若依次将数据序列：76,45,88,21,94,77,17存入该散列表中，则元素17存储的下标为(H)；在等概率情况下查找成功的平均查找长度为(C)。A.0B.1C.2D.3E.4F.5G.6H.7若从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序，则该二叉树是()。AA.二叉排序树B.赫夫曼树C.堆D.平衡二叉树当待排序序列的关键字次序为倒序时，若需为之进行正序排序，下列方案中(C)为佳。A.起泡排序B.快速排序C.直接插入排序D.简单选择排序已知一组待排序的记录关键字初始排列如下：56,26,86,35,75,19,77,58,48,42下列选择中（D）是快速排序一趟排序的结果。（C）是希尔排序（初始步长为3）一趟排序的结果。（A）是初始堆（大堆顶）。A）86,75,77,58,42,19,56,35,48,26.B）26,56,35,75,19,77,58,48,42,86.C）35,26,19,42,58,48,56,75,86,77.D）42,26,48,35,19,56,77,58,75,86.下列排序算法中，()算法可能会出现：初始数据有序时，花费的时间反而最多。DA.堆排序B.起泡排序C.归并排序D.快速排序在下列排序方法中，（c）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)；（d）方法所有情况下时间复杂度均为0(nlogn)。a.插入排序b.希尔排序c.快速排序d.堆排序右图为一棵3阶B-树。20，25在该树上插入元素15后的B-树是()。C10,142135A.15,25B.20,2510,1420,213510,1415,2135C.20D.14,25142510,1520,213510152135三．填空题数据结构通常有下列4类基本结构：集合、、树型结构、图型结构。设单链表中结点形式为datanext，若单链表长度大于等于2，指针p指向表中某个结点且p-next非空，此时若要删除指针p所指的结点，可以通过如下方法进行：将p所指结点的后继的元素值复制到该结点，然后删除其后继结点。相应的语句序列为：；；；线性表的顺序存储结构是以来表示数据元素之间的逻辑关系的。已知P是单链表中某一结点的指针，P既不是首元结点也不是尾元结点，Q是P的前驱结点指针。当删除P结点时，链表的链接可用语句（）实现。算法填空StatusPreordertraverse(BitreeT,Status(*Visit)(Telemtypee)){//先序非递归遍历二叉树。Initstack(S);Push(S,T);While(!stackempty(S)){While(gettop(S,p)&&_______________