资源描述：
《数据结构模拟试卷(二)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构模拟试卷(二)汗水和丰收是忠实的朋友，勤学和知识是一对最美丽的恋人。数据结构模拟试卷(二)学年学期考核方式闭卷课程名称数据结构A/B卷（）卷课程号学分学时80题号一二三四总分分数阅卷人 姓名：学号：班名：一、单项选择题（每小题2分，共30分）1.线性结构的逻辑特征是除第一个节点和最后一个节点，其它节点都有。A．一个直接前趋和一个直接后继B．多个直接前趋和一个直接后继C．一个直接前趋和多个直接后继D．多个直接前趋和多个直接后继2.算法必须具备输入、输出和。A．计算方法B．排序方法C．解决问题的有限运算步骤D．程式序设计
2、方法3.将递归过程转化为非递归过程需用到。A．栈B．队C．线性表D．链表4.在顺序表上做增、删节点运算的平均时间复杂度是。A．O(1)B．O(n)C．O(log2n)D．O(n2)5.设二维数组A[0...m-1][0...n-1]按行优先顺序存储，则元素A[i][j]的地址为 。 A．LOC(A[0][0])+(i*m+j)B．LOC(A[0][0])+(i*n+j)C．LOC(A[0][0])+[(i-1)*n+j-1]D．LOC(A[0][0])+[(i-1)*m+j-1]6.设目标串T="aababbad
3、bbaa"，模式P="bba"，则该模式匹配的有效位移为。A.4B.5C.7D.107.把长度为m的单链表接在长度为n的单链表之后的算法的时间复杂度为。A．O(m)B．O(n)C．O(m+n)D．O(1)8.在一个单链表中，若P所指节点不是最后节点，在P之后插入S所指节点，则执行。A．S->next=P->next;P->next=S;B．P->next=S->next;S->next=P;C．S->next=P;P->next=S;D．P->next=S;S->next=P; 9.设将整数1,2,3,4,5依次进栈，最
4、后都出栈，出栈可以在任何时刻（只要栈不空）进行，则出栈序列不可能是 。 A．23415B．54132C．23145D．1543210.循环队列是空队列的条件是。A．Q->rear==Q->frontB．(Q->rear+1)%maxsize==Q->frontC．Q->rear==0D．Q->front==0 11.设有一广义表E=（a,b,(c,d)），其长度为。A．2B．3C．4D．512.某二叉树的前序遍历序列为ABDEFC，中序遍历序列为DBEFAC，则后序遍历序列为。A．DFEBCAB．DBECFAC．B
5、DAECFD．DBEFCA13.下列哪项不是利用查找表中数据元素的关系进行查找的方法。A．有序表的查找B．二叉排序树的查找C．平衡二叉树D．散列查找 14.下述几种排序方法中，要求内存量最大的是。A．插入排序B．快速排序C．归并排序D．选择排序15.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。A．1/2B．1C．2D．4 二、填空题(每空2分，共20分)16．数据结构一般包括三个方面内容：数据的，数据的存储结构及数据的运算。17．在包含n个结点的顺序表上做等概率插入运算，平均要移动__
6、___个结点。18．队列的特性是______。19．已知二叉树中叶子数为30，仅有一个孩子的结点数为20，则总结点数为____。20．_______遍历二叉排序树中的结点可以得到一个递增的关键字序列（选填"先序"、"中序"或"后序"）。21．n个节点的连通图至少有_________条边。22．在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑，应最好选择排序。23．带有一个头结点的单链表head为空的条件是（假设指针域的名称为next）_____。24．设一组初始关键字序列为(38，65，97，76，13，27，1
7、0)，则第3趟简单选择排序后的结果为___________________。25．在拓扑排序中，拓扑序列的第一个顶点必定是的顶点。三、简答题（每题6分，共36分）26．已知一棵树边的集合为｛,,,,,,,,,,｝，画出这棵树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶子结点？（3）哪些是结点g的祖先？（4）树的深度是多少？（5）树的度数是多少？ 汗水和丰收是忠实的朋友，勤学和知识是一对最美丽的恋人。27．以下面数
8、据作为叶子结点的权值构造一Huffman树，画出该树并计算出其带权路径长度。 2，4，5，828．给定关键字集合(45,28,52,20,10,35,40,70,30,75,63,32)，（1）从一棵空的二叉搜索树开始，按表中元素的次序构造一棵二叉搜索
