数据结构(题目)

一．是非题1.数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。2简单地说,数据结构是带有结构的数据元素的集合。3判断带头结点的非空循环单链表（头指针为L）中指针p所指结点是最后一个元素结点的条件是：p-next==L。4线性表的链式存储结构具有可直接存取表中任一元素的优点。5线性表的顺序存储结构优于链式存储结构。6.在单链表P指针所指结点之后插入S结点的操作是：P-next=S;S-next=P-next;。7对于插入、删除而言，线性表的链式存储优于顺序存储。8.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。9.10线性表的顺序存储结构具有可直接存取表中任一元素的优点。11.栈和队列是操作上受限制的线性表。12.队列是与线性表完全不同的一种数据结构。13.队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。14.栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。15.栈是限定仅在表头进行插入和表尾进行删除运算的线性表。16队列是一种运算受限的线性表1.二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。2.二叉树是一棵结点的度最大为二的树。3.赫夫曼树中结点个数一定是奇数。4在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。5.假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。6.通常，二叉树的第i层上有2i-1个结点。7.中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。8二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。9由树结点的先根序列和后根序列可以唯一地确定一棵树。1邻接多重表可以用以表示无向图，也可用以表示有向图。2可从任意有向图中得到关于所有顶点的拓扑次序。3有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。4.关键路径是AOE网中源点到汇点的最短路径。5.连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。6.一个无向图的连通分量是其极大的连通子图。7.十字链表可以表示无向图，也可用以表示有向图。9.邻接表可以表示有向图，也可以表示无向图。1.二叉排序树的平均查找长度为O(logｎ)。2.二叉排序树的最大查找长度与（LOG2N）同阶。3选用好的HASH函数可避免冲突。4折半查找不适用于有序链表的查找。5二叉排序树的查找和折半查找的时间性能相同。1.对于目前所知的排序方法，快速排序具有最好的平均性能。2对于任何待排序序列来说，快速排序均快于冒泡排序。3在最坏情况下，堆排序的时间性能是O(nlogn),比快速排序好4快速排序具有最好的平均时间性能，它在任何时候的时间复杂度都是O（nlogn）。选择题。从逻辑上可以把数据结构分成()。A.动态结构和静态结构B.顺序组织和链接组织C.线性结构和非线性结构D.基本类型和组合类型下列程序段的时间复杂度为()。s=i=0;while(s=n){i++;s+=i;}A.O(1)B.O(n)C.O(n)D.O(n2)线性表L在()情况下适于使用链表结构实现。A.不需修改L的结构B.需不断对L进行删除、插入C.需经常修改L中结点值D.L中含有大量结点带头结点的单链表L为空的判断条件是。带头结点的循环链表L为空的判断条件是。A.L==nullB.L-next==nullC.L-next==LD.L!=null若顺序表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率：若找到指定的结点，将该结点与其后继（若存在）结点交换位置，使得经常被查找的结点逐渐移至表尾。以下为据此策略编写的算法，请选择适当的内容，完成此功能。顺序表的存储结构为：typedefstruct{ElemType*elem;//数据元素存储空间，0号单元作监视哨intlength;//表长度}SSTable;intsearch_seq(SSTableST,KeyTypekey){//在顺序表ST中顺序查找关键字等于key的数据元素。//若找到，则将该元素与其后继交换位置，并返回其在表中的位置，否则为0。ST.elem[0].key=key;i=ST.length;while(ST.elem[i].key!=key);if(){ST.elem[i]←→ST.elem[i+1]；；}returni;}A.i0B.i=0C.iST.lengthD.i=ST.lengthE.i++F.i--G.A和C同时满足H.B和D同时满足若入栈顺序为A、B、C、D、E，则下列()出栈序列是不可能的。A．A、B、C、D、EB．B、C、D、A、EC．C、D、B、E、AD．D、E、C、A、B递归程序可借助于()转化为非递归程序。a.线性表b.队列c:栈d.数组在下列数据结构中()具有先进先出（FIFO）特性，()具有先进后出(FILO）特性。a．线性表b．栈c．队列d．广义表若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到()的序列。a:1,2,3b:1,3,2c:2,1,3d:2,3,1e:3,1,2f:3,2,1在计算递归函数时，如不用递归过程，应借助于(2)这种数据结构。A.线性表B.栈C.队列D.双向队列若带头结点的链表只设尾结点指针。下列选择中（）最适用于队列。A）单链表B）双向链表C循环单链表D）双向循环链表栈和队列的一个共同点是()。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点循环队列用数组A[0..m-1]存放其元素值，设头尾指针分别为front和rear，则当前队列中的元素个数是()。A.rear-front-1B.Rear-front+1C.(rear-front+m)%mD.Rear-front带头结点的单链表L为空的判断条件是()。A.L==nullB.L-next==nullC.L-next==LD.L!=null假设用于通讯的电文仅由6个字符组成，字母在电文中出现的频率分别为7,19,22,6,32,14。若为这6个字母设计哈夫曼编码（设生成新的二叉树的规则是按给出的次序从左至右的结合，新生成的二叉树总是插入在最右），则频率为7的字符编码是（），频率为32的字符编码是（）。a:00b:01c:10d:11e:011f:110g:1110h:1111对二叉排序树（）可得到有序序列。a:按层遍历b:前序遍历c:中序遍历d:后序遍历设一棵二叉树BT的存储结构如下:12345678lchild23006000dataABCDEFGHrchild05408700其中lchild，rchild分别为结点的左、右孩子指针域，data为结点的数据域。则该二叉树的高度为()；第3层有()个结点（根结点为第1层）。A．2B.3C.4D.5先序遍历图示二叉树可得到（）的序列。a)ABHDEFICGb)HBEDFIACGc)HEIFDBGCA(A)／＼(B)(C)／＼＼(H)(D)(G)／＼(E)(F)＼(I)在有n个结点的二叉树的二叉链表表示中，空指针数（）。a.不定b.n+1c.nd.n-1若某二叉树有20个叶子结点，有20个结点仅有一个孩子，则该二叉树的总结点数是()。A．40B.55C.59D.61已知某二叉树的先序遍历次序为abcdefg中序遍历次序为badcgfe，则该二叉树的后序遍历次序为（）。层次遍历次序为（）。a:abcdefgb:cdebgfac:bdgfecad:edcgfba.图示的三棵二叉树中(c)为最优二叉树。A)B)C)ca27abcddb752445abcd7524已知某二叉树的后序遍历和中序遍历次序分别为DBFGECA和BDACFEG。则其先序遍历次序为（），层次遍历次序为（）。a:abcdefgb:abdcefgc:abcdfegd:abcdegf已知某树的先根遍历次序为abcdefg后根遍历次序为cdebgfa。若将该树转换为二叉树,其后序遍历次序为（）。a:abcdefgb:cdebgfac:cdegbfad:edcgfba设x和y是二叉树中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x在y之后，则x和y的关系是()。A.x是y的左兄弟B.x是y的右兄弟C.x是y的祖先D.x是y的子孙用三叉链表作二叉树的存储结构，当二叉树中有n个结点时，有()个空指针。A.n-1B.nC.n+1D.n+21.在有n个结点的二叉树（二叉链表表示）中，空指针数。A.不定B.n+1C.nD.n-1对一棵完全二叉树进行层序编号。则编号为n的结点若存在右孩子,其位序是()。编号为n的结点若存在双亲,其位置是()。a:n/2b:2nc:2n-1d:2n+1e:nf:2(n+1)设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3，则与森林F对应的二叉树根结点的右子树上的结点个数是()。A.m1B.m1+m2C.m3D.m2+m3下列二叉树中，()可用于实现符号不等长高效编码。a:最优二叉树b:次优查找树c:二叉平衡树d:二叉排序树邻接表存储结构下图的深度优先遍历算法类似于二叉树的()遍历。A.先根B.中根C.后根D.层次设无向图G=(V,E)和G’=(V’,E’)，若G’是G的生成树，则下面不正确的说法是()。A.G’是G的子图B.G’是G的连通分量C.G’是G的无环子图D.G’是G的极小连通子图且V’=V任何一个连通图的最小生成树(27)。A．只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在已知某无向图的邻接表如下所示；(19)是其原图。(20)是按该邻接表遍历所得深度优先生成树。(21)是按该邻接表遍历所得广度优先生成树。0a3211b302c4303d52104e525f43A.abB.abC.abcdcdcdefefefD.abE.abF.abcdcdcdefefef深度优先遍历图使用了数据结构（），而广度优先遍历图使用了数据结构（）。A）数组B）栈C）队列D）线性表a:弧的数目最多b:弧的数目最少c:权值之和最大d:权值之和最小1．深度优先遍历图使用了数据结构（），而广度优先遍历图使用了数据结构（）。A）数组B）栈C）队列D）线性表已知某有向图的邻接表存储结构如图所示。0E21∧1D034∧2C43B120∧4A2∧根据存储结构依教材中的算法其深度优先遍历次序为（）。广度优先遍历此序为（）。各强连通分量的顶点集为（）。a:abcde.b:edcba.c:ecdab.d:ecadb.e:abc及edf:bc及aedg:ab及cedh:ac及bed2．下列查找方法中（）适用于查找单链表。A）顺序查找B）折半查找C）分块查找D）hash查找哈希表的查找效率取决于（）。a:哈希函数b:处理冲突的方法。c:哈希表的装填因子。d:以上都是在Hash函数H(k)=kMODm中，一般来说，m应取()。A.奇数B.偶数C.素数D.充分大的数在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用方法。A.设置监视哨B.链表存贮C.二分查找D.快速查找静态查找表和动态查找表的区别在于()。A.前者是顺序存储，而后者是链式存储B.前者只能进行查找操作，而后者可进行查找、插入和删除操作C.前者只能顺序查找，而后者只能折半查找D.前者可被排序，而后者不能被排序在一个含有n个元素的有序表上进行折半查找，找到一个元素最多要进行()次元素比较。A．log2(n)B.log2(n)+1C.log2(n+1)D.log2(n+1)+11．具有m个结点的二叉排序树，其最大深度为（），最小深度为（）。根据插入次序（80，90，100，110，85，70，75，60，72）建立二叉排序树。图（）是最终变化的结果。8080709075906075851006070851007211072110a:b:9090751008010070801107570851106072856072c:d:若有序表中关键字序列