《数据结构与算法》期末练习题(含答案)

《数据结构与算法》期末练习一选择题1．以下与数据的存储结构无关的术语是（D）。A．循环队列B.链表C.哈希表D.栈2.算法的时间复杂度取决于（A）A．问题的规模B.待处理数据的初态C.A和BD.计算机cpu3.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（B）。A.23415B.54132C.23145D.154324.有关静态链表的叙述：(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（B）A．（1），（2）B．（1）C．（1），（2）,(3)D.（2）5．对于有n个结点的二叉树,其高度为（D）A．nlog2nB．log2nC．log2n|+1D．不确定6．从下列有关树的叙述中,选出正确的叙述（C）A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。B．当K≥1时高度为K的二叉树至多有2k-1个结点。C．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。D．在二叉树中插入结点,该二叉树便不再是二叉树。7．设无向图的顶点个数为n，则该图最多有（B）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n28．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,V6,V7},G的拓扑序列是（A）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V79．下列排序算法中，其中（D）是稳定的。A.堆排序，冒泡排序B.快速排序，堆排序C.希尔排序，归并排序D.归并排序，冒泡排序10．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1）8447251521（2）1547258421（3）1521258447(4）152125478411.则采用的排序是(A)。A.选择B.冒泡C.快速D.插入12．以下数据结构中，哪一个是线性结构（D）？A．广义表B.二叉树C.稀疏矩阵D.串13．下面关于线性表的叙述中，错误的是哪一个？（B）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。14.设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D）。A.51234B.45132C.43125D.3215415.设n为正整数.下列程序段中前置以@的语句的频度为（B）。i=1;k=0;do{@k+=10*i;i++;}While(i=n-1);A.n–1B.nC.n+1D.n-216.一棵具有n个结点的完全二叉树的树高度（深度）是（A）A．logn+1B．logn+1C．lognD．logn-117．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（B）。A.不确定B.n-i+1C.iD.n-i18．n个结点的完全有向图含有边的数目（D）。A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）19．稳定的排序方法是（B）A．直接插入排序和快速排序B．折半插入排序和起泡排序C．希尔排序和四路归并排序D．树形选择排序和shell排序20．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为(A)（按递增序）。A．下面的B，C，D都不对。B．9，7，8，4，-1，7，15，20C．20，15，8，9，7，-1，4，7D.9，4，7，8，7，-1，15，2021．以下那一个术语与数据的存储结构无关？（A）A．栈B.哈希表C.线索树D.双向链表22．下面关于串的的叙述中，哪一个是不正确的？（B）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储23.某堆栈的输入序列为a,b，c，d,下面的四个序列中，不可能是它的输出序列的是（D）。A.a，c，b，dB.b,c，d，aC.c,d，b,aD.d,c，a，b24.关于二叉树的叙述：①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。正确的是（D）A．①②③B．②③④C．②④D．①④25．高度为K的二叉树最大的结点数为（C）。A．2kB．2k-1C．2k-1D．2k-1-126．从下列有关树的叙述中,选出正确的叙述（C）A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。B．当K≥1时高度为K的二叉树至多有2k-1个结点。C．用树的前序遍历和中序遍历可以导出树的后序遍历。D．哈夫曼树是带权路径最长的树,路径上权值较大的结点离根较近。27.关键路径是事件结点网络中（A）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路28．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是(A)。A．逆拓扑有序B．拓扑有序C．无序的29．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（C）。A．(38,40,46,56,79,84)B.(40,38,46,79,56,84)C．(40,38,46,56,79,84)D.(40,38,46,84,56,79)30.一个向量的第一个元素的地址是begin，每个元素的长度是k，则第i个元素的地址是(D)A.begin+(k-1)iB.begin+(k-2)iC.begin+kiD.begin+(i-1)k31.有一个有序表为{1，3，9，12，32，41，45，62，77，88，92，100}，用折半查找法，若要找63，要经过(C)次与63比较。A.12B.6C.4D.532.一个序列的初始状态为（46，77，82，53，31，70），今对其进行冒泡排序，当进行两趟冒泡后，序列中的元素排列为(D)。A.（31，46，70，53，77，82）B.（46，77，53，31，70，82）C.（46，31,82，53，77，70）D.(46，53，31，70，77，82)33.将一个长度为n的向量的第i个元素删除时，需要前移(B)个元素。A.iB.n-iC.n+1D.n-i+134.不带表头的单链表，头指针为head，判断其是否为空的条件是(A)A.head==0B.head-next==nullC.head==headD.head-next==head35.在一个单链表中，已知*q是（*q表示指针q所指的结点，以下同）*p的前驱结点，在*q之后插入结点*s，正确的操作步骤序列是(A)。A)q-next=s;s-next=pB)s-next=p-next;q-next=s;C)p-nexr=s;s-next=p;D)p-next=s;s-next=q;36.非空循环链表head的尾结点*p满足下列(C)条件A)head-next==p;B)head==p;C)p-next==head;D)p-next==037.一个栈的输入序列是a,b,c,d,e，则可能的出栈序列是(D)。A.ecdabB)cebdaC)daecbD)abcde38.设栈s的类型为sqstack，判定栈空的条件是(C)。A.s==NULLB)s-top==0C)s.top==0D)s.top==NULL39.深度为5的二叉树至多有个(B)结点。A.12B.31C.14D.1540.已知二叉树的后、中根序列分别是bedfca和badecf，则该二叉树的前根遍历序列是(C)。A)defbcaB)fedbcaC)abcdefD)fedcba41.一个有n个顶点的有向图最多有(B)弧。A)n(n+1)B)n(n-1)C)n(n+1)/2D)n(n-1)/242.具有n个顶点的无向图至少要有(B)条边才有可能是一个连通图。A)n(n+1)B)n-1C)n+1D)n(n-1)43.已知有向图的正邻接链表的存储结构如下，从顶点1出发的按深度优先遍历序列是(B)。A)1234B)1423C)1324D)143244.一个向量的第一个元素的地址是100，每个元素的长度是2，则第五个元素的地址是(C)A)102B)110C)108D)12045.一个循环顺序队列,队头、尾指针的值分别为front,rear，则队列中元素个数为(A)。（maxlen为循环顺序表的长度）A.(rear-front+maxlen)%maxlenB.(rear-front)%maxlenC.rear-front+1D.front-rear+146.一个有n个顶点的图最少有(D)条边。A)n(n+1)B)n(n-1)C)n(n+1)/2D)047.具有5个顶点的无向图至少要有(A)条边才能确保是一个连通图。A)4B)5C)6D)748.设栈s的类型为sqstack，最多可容纳maxlen个元素，则判定栈满的条件是(B)。A.s==maxlen-1B)s.top==maxlen-1C)s-top==maxlen-1D)s.top==049.一个顺序队列q的类型为sqqueue,队头、尾指针分别为front,rear，最多可容纳maxlen个元素，则队空的条件是(C)。A)front==rearB)rear==0C)q.front==q.rearD)rear==maxlen-150.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是(B)A.O(1)B.O(n)C.O(nlogn)D.O(n*n)51.链栈与顺序栈相比，比较明显的优点是(D)A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况52.二叉树中第5层上的结点个数最多为(C)A.8B.154^2^3^3^4^2^4^1234C.16D.3253.下列编码中属前缀码的是(A)A.{1,01,000,001}B.{1,01,011,010}C.{0,10,110,11}D.{0,1,00,11}54.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（B）A．深度优先搜索算法B．广度优先搜索算法C．求最小生成树的prim算法D．拓扑排序算法55.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为(B)A.O(1)B.O(logn)C.O(n)D.O(nlogn)56.对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为(C)A.(n-1)/2B.n/2C.(n+1)/2D.n57.对于哈希函数H(key)=key%13,被称为同义词的关键字是(D)A.35和41B.23和39C.15和44D.25和5158.关于线性表的说法,下面选项正确的是（B）A线性表的特点是每个元素都有一个前驱和一个后继B线性表是具有n(n=0)个元素的一个有限序列C线性表就是顺序存储的表D线性表只能用顺序存储结构实现59.表长为n的顺序存储的线性表，当在任何一个位置上插入或者删除一个元素的概率相等时，删除一个元素需要移动元素的平均个数为（A）A(n-1)/2Bn/2CnDn-160.设双向循环链表中节点的结构为(data,LLink,RLink)，且不带头节点。若想在指针p所指节点之后插入指针s所指节点，则应执行下列哪一个操作？（D）Ap-RLi