资源描述：
《数据结构考试题5说课讲解.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、精品好文档，推荐学习交流要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。一、单项选择题（每小题2分，共20小题，共计40分）1.某算法的空间复杂度为O(1)，则。A.该算法执行不需要任何辅助空间B.该算法执行所需辅助空间大小与问题规模n无关C.该算法执行不需要任何空间D.该算法执行所需全部空间大小与问题规模n无关2.在长度为n的顺序表中插入一个元素，对应算法的时间复杂度为。A.O(1)B.O(log2n)C.O(n)D.O(n2)3.设线性表中有n个元素，
2、以下运算中，在单链表上实现要比在顺序表上实现效率更高。A.删除指定位置元素的后一个元素B.在最后一个元素的后面插入一个新元素C.顺序输出前k个元素D.交换第i个元素和第n-i+1个元素的值（i=1，2，…，n）4.以下数据结构中元素之间为非线性关系的是。A.栈B.队列C.线性表D.以上都不是5.若一个栈用数组data[1..n]存储，初始栈顶指针top为n+1，则以下元素x进栈的正确操作是。A.top++;data[top]=x;B.data[top]=x;top++;C.top--;data[
3、top]=x;D.data[top]=x;top--;6.若某循环队列有队首指针front和队尾指针rear，在队不满时进队操作仅会改变。A.frontB.rearC.front和rearD.以上都不队7.设循环队列中数组的下标是0～N-1，其队头、队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），则其元素个数为。A.r-fB.r-f-1C.(r-f)％N+1D.(r-f+N)％N8.设树T的度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中的叶子结点个数是。A
4、.5B.6C.7D.89.一棵哈夫曼树中共有199个结点，它用于多少个字符的编码。A.99B.100C.101D.19910.设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为a、b、c、d，将森林F转换为一颗二叉树B，则二叉树B根结点的左子树上的结点个数是。仅供学习与交流，如有侵权请联系网站删除谢谢8精品好文档，推荐学习交流A.a-1B.aC.a+b+cD.b+c+d11.下列关于图的叙述中，正确的是。Ⅰ.回路是简单路径Ⅱ.存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ.若有向图中存在拓扑序列
5、，则该图不存在回路A.仅ⅡB.仅Ⅰ、ⅡC.仅ⅢD.仅Ⅰ、Ⅲ12.以下关于有向图的说法中，正确的是。A.强连通图是任何顶点到其他所有顶点都有边B.完全有向图一定是强连通图C.有向图中任一顶点的入度等于出度D.有向图边集的子集和顶点集的子集可构成原有向图的子图13.无向图的邻接矩阵是一个。A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵14.如果从无向图的任一顶点出发进行一次广度优先遍历即可访问所有顶点，则该图一定是。A.完全图B.连通图C.有回路D.一棵树15.用Dijkstra算法求一个带权有向
6、图G中从顶点0出发的最短路径，在算法执行的某时刻，S={0,2,3,4}，下一步选取的目标顶点可能是。A.顶点2B.顶点3C.顶点4D.顶点716.哈希表中出现冲突是指。A.两个元素具有相同的序号B.两个元素的关键字不同，而其他属性相同C.数据元素过多D.两个元素的关键字不同，而对应的哈希函数值（存储地址）相同17.适合于折半查找的数据组织方式是。A.以链表存储的线性表B.以顺序表存储的任意线性表C.以链表存储的有序线性表D.以顺序表存储的有序线性表18.对有n个记录的表进行直接插入排序，在最好
7、情况下需比较次关键字。A.n-1B.n+1C.n/2D.n(n-1)/219.若数据元素序列{11,12,15,7,8,9,23,1,5}是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是。A.冒泡排序B.直接插入排序C.选择排序D.二路归并排序20.对一组数据(25,84,21,47,15,27,68,35,20)进行排序，前3趟的排序结果如下：第1趟：20，15，21，25，47，27，68，35，84第2趟：15，20，21，25，35，27，47，68，84仅供学习与交流
8、，如有侵权请联系网站删除谢谢8精品好文档，推荐学习交流第3趟：15，20，21，25，27，35，47，68，84则所采用的排序方法是。A.简单选择排序B.希尔排序C.二路归并排序D.快速排序二、问答题（共4小题，共计35分）1.（10分）对于如图1所示的带权无向图，直接给出利用普里姆算法（从顶点0开始构造）和克鲁斯卡尔算法构造出的最小生成树的结果（注意：按求解的顺序给出最小生成树的所有边，每条边用(i，j)表示）。图1一个带权无向图G2.（10分）假设一棵二叉排序树的关键字为单个字母，其后序遍
