new数据结构复习题

数据结构复习题一、填空数据结构按物理结构可分为线性结构、、和集合。在单链表中，要删除某一指定的结点，必须先找到该结点的()结点。对于一个具有n个结点的单链表，在*p结点后插入一个新结点的时间复杂度是()；在给定值x的结点后插入一个新结点的时间复杂度是()。在线性结构、树形结构和图形结构中，直接前驱和直接后继结点之间分别存在着、1：N和的联系。一棵有n个节点的满二叉树有个度为1的节点。中缀表达式A-(B+C/D)*E的后缀表达式是。具有n个顶点的完全无向图具有条边，利用邻接矩阵表示的完全无向图具有行，若无向图的邻接矩阵vi,vj不存在边，则赋值_______。平衡二叉树是每个结点的左、右子树的高度至多相差______。一个有向图G中若有弧vi,vj、vj,vk和vi,vk,图G的拓扑序列为______________。直接插入排序的时间复杂度是，它(是/否？)稳定的。广义表((a,b),c,d)的表头是，表尾是。限定在同一端进行插入、删除的线性表称为；该端称为。内排序算法中空间复杂度最大的算法是。设顺序栈S为空，若6个元素入栈顺序为a1,a2,a3,a4,a5,a6，出栈顺序为a2,a4,a3,a6,a5,a1，则栈S的容量至少为。G是一个非连通无向图，共有28条边，则该图至少有________个顶点。一棵有n个结点满二叉树有个度为1的结点，有个分支结点和个叶子结点，该满二叉树的深度为。深度为6（根的层次为1）的完全二叉树至多有_________结点，至少有_________结点。G是一个非连通无向图，共有28条边，则该图至少有________个顶点。从邻接矩阵A=010101010中可以看出，该图共有________个顶点。如果是有向图，该图共有________条弧，如果是无向图，则共有________条边。一个有向图G中若有弧vi,vj、vj,vk和vi,vk,则在图G的拓扑序列中，顶点vi,vj和vk的相对位置为______________。二、选择题将s结点插入到p结点之后，实现语句为（）。A.s-next=p-next;p-next=s;B.(*p).next=s;(*s).next=(*p).next;C.s-next=p-next;p-next=s-next;D.s-next=p+1;p-next=s;将一棵有100个节点的完全二叉树从上到下，从左到右编号，根节点的编号为1，则编号为49的节点的右孩子编号是（）。A．97B．98C．99D．100PS带头结点的单链表head为空的判定条件是()。A.head=NULLB.head==NULLC.head-next=NULLD.head-next==NULL（）是C语言中”abcd321ABCD”的子串。A.abcdB.321abC.“abcABC”D.“21AB”若广义表A满足head(A)=tail(A)，则A为A.()B.(())C.((),())D.((),(),())有5个顶点的图，若为连通图，则至少有（）条边。A．3B．4C．5D．6一组记录的关键码为（46,79,56,38,40,84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A.38，40，46，56，79，84B.40，38，46，79，56，84C.40，38，46，56，79，84D.40，38，46，84，56，79有5个顶点的图，若为强连通图，至少有（）条边。A．3B．4C．5D．6下列不属于内排序算法的是（）。A.归并排序B.基数排序C.拓扑排序D.堆排序已知广义表LS=((a,c),(b,d))，运算head和tail函数取出LS中元素b的运算是（）。A．head(tail(LS))B．tail(head(LS))C．head(tail((tail(LS)))D．head(head(tail(LS)))线性链表中各链接点之间的地址（）。A.必须连续B.部分地址必须连续C.不一定连续D.以上答案都错误()是C语言中”abcd321ABCD”的子串。A．abcdB.321ABC.’’abcABC“D.“21AB“若串s=“software“，其子串的个数是()。A．8B.9C.36D.37在一个单链表中，删除*p结点的直接后继结点，则执行（）。A.p=p-nextB.p=p-next-nextC.p-next=pD.p-next=p-next-next前序遍历和后序遍历结果相同的二叉树具有（）特征。A.一般二叉树B.只有左子树的二叉树C.只有右子树的二叉树D.只有根结点的二叉树采用折半查找法查找长度为n的线性表，每个元素的平均查找长度为（）。A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）A.35/12B.37/12C.39/12D.43/12有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当折半查找值82的结点时，（）次比较后查找成功。A.1B.2C.4D.8从平均时间性能上看，()性能最佳，所需时间最省。A．堆排序B．归并排序C．基数排序D．快速排序评价一个算法时间性能的主要标准是（）。A算法易于调试B算法易于理解C算法的稳定性和正确性D算法的时间复杂度若广义表A满足head(A)=tail(A)，则A为A.()B.(())C.((),())D.((),(),())排序算法的稳定性是指（）。A.经过排序之后，能使值相同的数据保持原顺序中的相对位置不变B.经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变C.排序算法的性能与被排序元素的数量关系不大D.排序算法的性能与被排序元素的数量关系密切哈希函数除留余数法，H(k)=k%m的m一般取（）。A．自然数B.整数C.素数D.有理数对线性表进行折半查找时，要求线性表必须（）。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序不带头结点的单链表head为空的判定条件是()。A.head=NULLB.head==NULLC.head-next=NULLD.head-next==NULL有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当折半查找值82的结点时，（）次比较后查找成功。A.1B.2C.4D.8循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是()A.(rear-front+m)%mB.rear-front+1C.rear-front+1D.rear-front若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是()A.1和5B.2和4C.4和2D.5和1将一棵有100个节点的完全二叉树从上到下，从左到右编号，根节点的编号为1，则编号为49的节点的右孩子编号是（）。A．97B．98C．99D．100线性表是具有n个()的有限序列。A.数据元素B.字符C.数据D.数据项若需在O(nlog2n)的时间内完成对数组的排序，且要求稳定，则可选择的排序方法是()A、快速排序B、堆排序C、归并排序D、直接插入排序在下述排序中，所需辅助存储量最多的是()，所需辅助存储量最少的是()，平均速度最快的是()A、快速排序B、归并排序C、堆排序三、应用题线性表链式存储结构有单链表、循环链表、双向链表，试比较它们的优劣。一棵度为2的树与一棵二叉树有何区别？试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。设输入元素为1、2、3、p和a，输入次序为123pa，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可作为高级语言的变量名。求下列中缀表达式后缀表达式1)3+4/(25-6*5)*82)(1+2)*((8-2)/(7-4))给定一组关键字序列：11，78，10，1，3，2，4，21，(1)试生成二叉排序树，求查找成功的ASL(2)若向二叉排序树中插入元素12，删除元素3，则该二叉排序树的变化情况(3)试生成平衡二叉树，求查找成功的ASL(4)若向平衡二叉树中插入元素12，删除元素3，则该平衡二叉树的变化情况设哈希表长度为11，哈希函数H(k)=kMOD11,若输入顺序为（18,10,21,9,6,3,16,25,7）,(1)处理冲突方法为线性探测法，请构造哈希表；(2)处理冲突方法为拉链法，试构造链表。已知(29，18，25，47，58，12，51，10)，给出以下排序方法进行排序时的变化。(1)归并(2)快速(3)希尔用Dijkstra算法计算从源顶点1到其它顶点最短路径。设字符串为“ABEAACCDAACABBBBEAACDDE”，画出相应的Huffman树，并计算其WPL。用prim和kruskal算法分别构造下图所示网络的最小生成树。设有向图G如下图所示，(1)求该图的拓扑序列。(2)添加哪条弧后，可以得到唯一的拓扑序列？已经有向网如下图所示，(1)求各顶点及各边的最早、最晚开始时间(2)求关键路径模式串S=abcaabbabcab,根据KMP算法，求该模式串的next数组值。若目标串T=acbabcaabcaabbabcab，利用KMP算法进行模式匹配时，求每趟的匹配过程。四、算法设计给出10个无序数据{2,5,1,8,9,5,3,7,6,4}，先快速排序或归并排序，再折半查找5。对链式结构的线性表L(带头结点)统计表中的元素个数。试设计一个算法实现二叉树的前序遍历、中序遍历、后序遍历。设计算法求取二叉树的结点个数、叶子结点个数、高度。对链式结构的线性表L(带头结点)进行插入元素、删除元素操作。对栈实现插入元素、删除元素操作。