复习题一及答案.doc

复习题一及答案.doc

ID:58862918

大小:54.00 KB

页数:9页

时间:2020-09-22

复习题一及答案.doc_第1页
复习题一及答案.doc_第2页
复习题一及答案.doc_第3页
复习题一及答案.doc_第4页
复习题一及答案.doc_第5页
资源描述:

《复习题一及答案.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、复习题一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

2、;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.先进后出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.若一棵二叉树具

3、有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)。A.abecfdB.abcefdC.aebcfdD.aedfcb13.在一个无向图中,所有顶点度数之和等于所有边数(B)倍,在一个有向图中,所有顶点入度数之和等于所有顶点出度之和的(C)倍。

4、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的栈顶元

5、素为____7____,栈底元素为____2___。5.在一棵树中,__叶子__结点没有后继结点,__根__节点没有前驱节点。6.假定一棵二叉树的结点个数为10,则它的高度至多为___10___,它的高度至少为____4____。三、判断题:(每小题1分,共10分)1.(X)线性表的特点是每个元素都有一个前驱和一个后继。2.(V)直接选择排序是一种不稳定的排序方法。3.(X)二分查找只适用于有序表,包括有序的顺序表和有序的链表。4.(X)链式存储在插入和删除时需要保持物理存储空间的顺序分配,不需要保持数据元素之间的逻辑顺序。5.(X)通

6、常递归的算法简单、易懂、容易编写,而且执行的效率也高。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},试分别写出用简单选择排序的方法对其进行排序时,每一趟排序

7、后的结果。答:(13)[231721306058283090](1317)[2321306058283090](131721)[23306058283090](13172123)[306058283090](1317212328)[6058303090](131721232830)[58603090](13172123283030)[605890](1317212328303058)[6090](131721232830305860)[90]131721232830305860902.写出下面树的前序、中序、后序遍历序列;前序:ABDG

8、HECFIJ中序:GDHBEACIJF后序:GHDEBJIFCA3.设散列表的长度m=13;散列函数为H(X)=Xmodm,给定的关键码序列为19,14,23,01,68,20,84,27,55,11,试分

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。