数据结构期末模拟试题(带答案)

《数据结构期末模拟试题(带答案)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、模拟试题8一、选择题（每小题1分，共10分）1、设一数列的顺序为1，2，3，4，5，通过栈结构不能排成的顺序数列为。(A)3，2，5，4，1(B)1，5，4，2，3(C)2，4，3，5，1(D)4，5，3，2，12、二叉树的第3层最少有B个结点。(A)0(B)1(C)2(D)33、一个具有n个顶点的连通无向图，其边的个数至少为。(A)n-1(B)n(C)n+1(D)nlogn4、下列排序方法中，比较次数与记录的初始状态无关。(A)直接插入排序(B)起泡排序(C)快速排序(D)直接选择排序5、一棵Huff

2、man树总共有11个结点，则叶子结点有个。(A)5(B)6(C)7(D)96、已知某算法的执行时间为（n+n2）+log2(n+2)，n代表问题规模，则该算法的时间复杂是。(A)O(n)(B)O(n2)(C)O(log2n)(D)O(nlog2n)7、如果一棵树有10个叶子结点，则该树至少有个结点。(A)10(B)11(C)19(D)218、一个100×100的三角形矩阵a采用行优先压缩存储后，如果首元素a[0][0]是第一个元素，那么a[4][2]是第A个元素。(A)13(B)401(C)402(D)

3、403二、判断题（每题1分，共8分，对的打√，错的打×）1、如果某数据结构的每一个元素都最多只有一个直接前驱，则其必为线性表。（）2、快速排序法在最好的情况下时间复杂度是O（n）。（×）3、进栈、出栈操作的时间复杂度为O（n）。（）4、进栈操作时，必须判断栈是否已满。（）5、一个有序的单链表不能采用折半查找法进行查找。（）6、二叉排序树采用先序遍历可以得到结点的有序序列。（）7、对长度为100的有序线性表用二分法查找时，最小比较次数为0。（）8、一棵二叉排序树，根元素肯定是值最大的元素。（）三、填空题（

4、每题2分，共16分）1、数据结构有和两种物理结构。2、某算法在求解一10阶方程组时，运算次数是500，求解一30阶方程组时，运算次数是4500，则该算法的时间复杂度是3、在一个长度为n的顺序表中插入一个元素，最少需要移动个元素，最多需要移动个元素。4、如果某有向图的所有顶点可以构成一个拓扑排序序列，则说明该有向图5、如果指针p指向一棵二叉树的一个结点，则判断p没有左孩子的逻辑表达式为。6、一个数组的长度为20，用于存放一个循环队列，则队列最多只能有元素。7、无向图用邻接矩阵存储，其所有元素之和表示无向图

5、的。8、一个具有n个结点的线性表采用堆排序，在建堆之后还要进行次堆调整。四、简答题（共38分）1、写出线性表（26，4，12，25，30，6，15，20，16，2，18）采用二路归并排序算法排序后，第一趟和第二趟结束时的结果。（5分）2、在如图1所示树中：（1）给出该树的后序遍历的结果。（4分）（2）采用孩子-兄弟法将该树转换成一棵二叉树（5分）3、已知图2是一个有向图（1）画出该有向图的邻接链表。（4分）（2）基于你给出的邻接链表，求从定点F出发的广度优先遍历。（4分）4、用Prim算法（一条顶点一条

6、顶点加入生成树）求图3的最小生成树。（1）从顶点D开始，写出各顶点加入生成树的次序。（4分）（2）画出最终的最小生成树。（4分）5、已知图4是一颗二叉排序树：（1）计算平均查找长度。（4分）（2）画出删除值为46的结点后的二叉排序树。（4分）五、程序填空题（共15分）1、以下是采用冒泡排序法对数组a进行排序，完成程序。（4分）bsort(inta[],intn){intn,j,j,tmp;for(i=______;i>=1;--i){for(j=1;j<=i;++j){if(_______){tmp=a

7、[j];a[j]=a[j+1];a[j+1]=tmp;}}}}2、在单链表（表头指针为head）的元素中找出最后一个值为e的元素，返回其指针;如果找不到，则返回NULL，完成以下程序。（6分）//应去掉“最后一个”typedefstructLinkNode{intdata;StructLinkNode*next;}Node;Node*search_link(Node*head,inte){Node*p,*q;q=_______;for(p=head;_________;p=p->next){if(p->

8、data==e){__________;}}returnq;}3、下列算法是输出一棵二叉树的第i层的所有结点的值。假定根结点是第1层，完成以下程序。（本题5分）typedefstructlinkNode{intdata;StructlinkNode*lchild,*rchild;}Node;voidouti(Node*tree,inti){if(tree==NULL){return;}if(i==1){pintf(“%d”,tree->