西安交通大学《数据结构与算法》2022-2023学年期末试卷

西安交通大学《数据结构与算法》2022-2023学年第一学期期末试卷一、单选题：（每小题2分，10小题，共20分）1、若进栈序列为1,2,3,4,5,6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为()A.3,2,6,1,4,5B.3,4,2,1,6,5C.1,2,5,3,4,6D.5,6,4,2,3,12、若用邻接矩阵表示一个有向图，则其中每一列包含的"1"的个数为()A.图中每个顶点的入度B.图中每个顶点的出度C.图中弧的条数D.图中连通分量的数目3、下列二叉树中，()可用于实现符号的不等长高效编码。A.最优二叉树B.B-树C.平衡二叉树D.二叉排序树4、在对个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第趟排序之前，无序区中关键字元素的个数为()A.iB.i+1C.n-iD.n-i+l5、若有序表的关键字序列为(b,c,d,e,￡，g,q,r,s,t),则在二分查找关键字b的过程中，先后进行比较的关键字依次为()A.fc,bB.f,d,bC.g.c,bD.g,d,b6、设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列()方法可以达到此目的。A.快速排序B.堆排序C.归并排序D.插入排序7、排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是()A.选择排序B.快速排序C.冒泡排序D.插入排序8、有n个结点的有向完全图的弧数是()A.n2B.2nC.n(n-1)D.2n(n+1)9、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用()A.求关键路径的方法B.求最短路径的Dijkstra方法C.深度优先遍历算法D.广度优先遍历算法10、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s,则执行(A.s→link=p→link,p→link=s,B.p→link=s,s→link=qC.p→link=s→link,s→link=p;D.q→link=s,s→link=p,二、简答题（每题5分，5题，共25分）1.一颗二叉树的前序遍历的结果是1,2,3,4,5,6，中序遍历的结果是3,2,4,6,5,1。请画出这颗二叉树。2.请用Pim算法画出右图最小生成树的生成过程。