《福师2021年2月课程考试《数据结构概论》作业考核试题》由会员分享，可在线阅读，更多相关《福师2021年2月课程考试《数据结构概论》作业考核试题（6页珍藏版）》请在金锄头文库上搜索。
1、数据结构概论期末试卷一、单项选择题 (每小题2分，共30分)1.查找n个元素的有序表时，最有效的查找方法是( C ) A.顺序查找 B.分块查找 C.折半查找 D.二叉排序树查找2.具有12个关键字的有序表，查找成功时折半查找的平均查找长度是( A ) A.3.1 B.4 C.2.5 D.53.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( D ) A.O(1) B.O(n) C.O(nlogn) D.O(n2)4.对平均性能而言，以下最好的内排序方法是( D )。 A.冒泡排序 B.希尔排序 C.交换排序 D.快速排序5.链栈与顺序栈相比，比较明显的优点是( D
2、) A.插入操作更加方便 B.删除操作更加方便 C.不会出现下溢的情况 D.不会出现上溢的情况6.二叉树中第5层上的结点个数最多为( C ) A.8 B.15 C.16 D.327.以下数据结构中，( A )是非线性数据结构。 A.树 B.字符串 C.队 D.栈8.一个向量的第一个元素的地址是100，每个元素的长度是2 ，则第五个元素的地址是( B )。 A.102 B.110 C.108 D.1209.已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是( B ) A. 0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D.0 3 1 2（第9题配图：数组的下
3、标为0,1,2,3）10.对于哈希函数H(key)=key%13,被称为同义词的关键字是( D ) A.35和41 B.23和39 C.15和44 D.25和5111.有一个有序表为 1，3，9，12，32，41，45，62，77，88，92，100，用折半查找法，若要找63，要经过( C )次与63比较。 A.12 B.6 C.4 D.512.下述几种排序方法中，稳定的排序算法是( A ) A.直接插入排序 B.快速排序 C.堆排序 D.希尔排序13.具有n个顶点的无向图至少要有( C )条边才能确保是一个连通图。 A.n(n+1) B.n-1 C.n+1 D.n(n-1)14.二叉树是非线
4、性数据结构，所以 ( C ) A.它不能用顺序存储结构存储 B.它不能用链式存储结构存储 C.顺序存储结构和链式存储结构都能存储 D.顺序存储结构和链式存储结构都不能使用15.有8个结点的无向图最多有( C )条边。 A.14 B.28 C.56 D.112二、填空题（每小题2分，共30分）1. 下面程序段的时间复杂度为_0（n）_。 sum=1; for(i=0;sumn;i+) sum+=1;2. 设数组aM(M为最大空间个数)作为循环队列Q的存储空间，front为队头指针(指向第一个存放数据的位置)，rear为队尾指针(指向最后一个存放数据位置的下一个)，则判定Q队列的队满条件是_fro
5、nt=（_rear+1）%m_。3. 若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是FEGHDCB_。4. 散列法存储的基本思想是由_关键码的值_决定数据的存储地址。5. 在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是_6_。6. 设一棵完全二叉树有700个结点，则共有_1_个叶子结点 。7. n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为_1_；若采用邻接表存储时，该算法的时间复杂度为_2_ 。8. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用_堆排序_；若初始记录基本无序，则最好选
6、用_快速排序_。9. 若要求一个稀疏图G的最小生成树，最好用_克鲁斯卡尔（Kruskal）_ 算法来求解。10. 一棵深度为6的满二叉树有 _31_ 个分支结点和_9_个叶子。11.用5个权值3, 2, 4, 5, 1构造的哈夫曼（Huffman）树的带权路径长度是_（1+2）*3+（4+5+3）*2=33_。12. 有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的_（1）_。三、解答题(每小题9分，共27分)1. 已知以下的有向图，用Dijkstra算法求出从顶点1出发到各顶点的最短路径（按步给分）。 答:迪克斯加(Dijkstra)算法(最短路径算法)是由荷兰计算机科学家艾兹格.
7、迪科斯彻发现的.算法解决的是有向图中任意两个顶点之间的最短路径问题。如下：原点 终点 最短 1 2 12=101 2 132=231 3 13=181 3 12453=191 3 1253=151 4 124=151 5 1245=171 5 125=132.待排序的序列为：25,47,36,21,90,84,62,78,15,32。写出用（大根）堆排序的每一趟的结果。答: int main(int argc, char *argv ) int array10= 24, 17, 85, 13, 9, 54, 76, 45int num=s i zeof (array) /si zeof (in
8、t) :for (int i=0; inum-1; i+) for(intj=0;jnum-1-i;j+)if （arrayjarray j+1) int tmp=arrayJ;arrayJ=arrayJ+1;5,63arrayJ+1for(int i=tmp;=0:inum;i+) printf( %d , arrayi) ;if(i=num-1) printf( n;3.一棵度为2的有序树与一棵二叉树有何区别？答:树是有根结点和若干颗子树构成的,一个结点所拥有后件的个数称为结点的度所有结点中最大的度就是树的度树的层次是树的深度度为2的树:树的最大结点的度为2二叉树:不存在度大于2的结点。五
9、种基本形态:空二叉树,仅有根节点的二叉树,左子树为空的二二叉树,右子树为空的二叉树,左右子树均不为空的二叉数二者不等同.四、程序设计题（共13分） 1、已知r为一维数组，其中r0到rn-1为待排序的n个元素，排序好的元素仍放在r0到rn-1中，请写出对该数组进行非递归的直接插入排序算法，取名为insertsort(elemtype r,int n)。 答：1 void insertsort(elemtype r,int n)2 3 int key,i;4 for(i=1;i n;i+)5 6 key=ri;7 j=i-1;8 while(j=Qrjkey)9 10 rj+1=rj;11 j-;12 13 rj+1=key;14 15 6第 6 页 共 6 页 福建师范大学试卷纸
