复习题一及答案

第1页共9页复习题一1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为(A)。A.O(n)B.O(n/2)C.O(1)D.O(n2)2.在有向图中每个顶点的度等于该顶点的(C)。A.入度B.出度C.入度与出度之和D.入度与出度之差3.下列排序算法中(C)是不稳定的排序算法。A.冒泡排序B.合并排序C.快速排序.D.插入排序4.在单链表中，q指向待删除结点的前驱，p指向待删除的结点，则删除节点的操作是(B)。A.p=q-next；q-next=p-next;free(p);B.q-next=p;q-next=p-next;free(p);.C.p=q-next;free(p);q-next=p-next;D.p=q-next;p=p-next;free(p);5.栈操作的基本原则(B).A.先进先出B.先进后出第2页共9页C.只能进行插入D.只能进行删除6.设有一个顺序栈S，元素S1，S2，S3，S4，S5，S6依次入栈，若有6个元素出栈的顺序是S2，S3，S4，S6，S5，S1。则该栈的容量至少应该是（B）。A．2B．3C．4D．59.具有50个结点的完全二叉树，编号为19的结点的左孩子编号为(C)A.46B.39C.38D.不存在10.若一棵二叉树具有10个度为2的节点，5个度为1的节点，则度为零的节点个数是(B).A.9B.11C.15D.不确定11.有n个顶点的无向图最多有(B)条边。A.n-1B.n*(n-1)/2C.n*(n+1)/2D.n*n12.对下图G，若从顶点a出发，按深度搜索法，进行遍历，则可能得到的一种顶点序列为(D)，按广度搜索法进行遍历，则可能得到的一种顶点序列为(B)。第3页共9页A.abecfdB.abcefdC.aebcfdD.aedfcb13.在一个无向图中，所有顶点度数之和等于所有边数(B)倍，在一个有向图中，所有顶点入度数之和等于所有顶点出度之和的(C)倍。A.1/2B.2C.1D.4二、填空题：（每空1分，共10分）1.选择合适的存储结构，通常考虑的指标是空间复杂度和_时间复杂度__。2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度__O（n）_为，在表尾插入元素的时间复杂度为____O(1)___。3.在一棵二叉树中，第5层上的结点数最多为___16_。4.设有一空栈S及等待进栈的数据元素序列数据：2，3，4，5，6，7，8，9。依次进行push,push,pop,push,pop,push,push,pop,push,push,pop操作，完成此操作后，栈S的栈顶元素为____7____，栈底元素为____2___。5.在一棵树中，__叶子__结点没有后继结点，__根__节点没有前驱节点。第4页共9页6.假定一棵二叉树的结点个数为10，则它的高度至多为___10___，它的高度至少为____4____。三、判断题：（每小题1分，共10分）1.(X)线性表的特点是每个元素都有一个前驱和一个后继。2.(V)直接选择排序是一种不稳定的排序方法。3.(X)二分查找只适用于有序表，包括有序的顺序表和有序的链表。4.(X)链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。5.(X)通常递归的算法简单、易懂、容易编写，而且执行的效率也高。6.(X)对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。7.(X)二叉树的度数为2。8.(X)在n个顶点的无向图中，若边数大于n-1，则该图必是连通图。9.(X)有e条边的无向图，在邻接表中有e个节点。10.(X)单链表中从任何一个节点出发，都能访问到所有节点。四、解答题：（每小题6分，共30分）1.对于给定的一组记录的关键字：｛23,13,17,21,30,60,58,28,30,90｝，试分别写出用简单选择排序的方法对其进行排序时，每一趟排序后的结果。第5页共9页答：（13）[231721306058283090]（1317）[2321306058283090]（131721）[23306058283090]（13172123）[306058283090]（1317212328）[6058303090]（131721232830）[58603090]（13172123283030）[605890]（1317212328303058）[6090]（131721232830305860）[90]131721232830305860902.写出下面树的前序、中序、后序遍历序列；前序：ABDGHECFIJ中序：GDHBEACIJF后序：GHDEBJIFCA第6页共9页3.设散列表的长度m=13；散列函数为H(X)=Xmodm,给定的关键码序列为19,14,23,01,68,20,84,27,55,11,试分别画出用线性探查法解决冲突时所构造的散列表（闭散列）和开散列方法实现。并求出在等概率的情况下，这两种方法的搜索成功时的平均搜索长度;4.写出下图的的邻接矩阵表示及邻接表表示；第7页共9页5.如下图所示:(1)写出它的邻接表；(2)应用Prim算法(从A出发)，画出最小生成树，写出最小生成树的生成过程。6、对给定的一组权值：3，3，7，7，11，13，17构造一棵Huffman树，并计算出树的带权路径长度。第8页共9页五、算法设计题：（每小题10分，共20分）1.设含有头结点的单链表L的结点结构定义为：typedefstructnode*link;typedefstructnode{ListItemelement;linknext;}Node;假设head为指向表头结点的指针。试写出算法：求单链表中值为最大的结点。2.用邻接矩阵实现赋权有向图，结构定义如下：PTypedefstructgraph*Graph;Structgraph{第9页共9页WitemnoEdge;/*无边标记*/intn;/*顶点数*/inte;/*边数*/Witem**a;/*邻接矩阵*/}AWDgraph;试在邻接矩阵存储结构上实现图的入度的基本操作：InDegree(i,G)，即函数InDegree(i,G)返回赋权有向图G中顶点I的入度。