11东南大学大数据结构试卷A

《11东南大学大数据结构试卷A》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用文档东南大学考试卷（A卷）学号姓名密封线课程名称数据结构考试学期10-11-3得分适用专业吴健雄学院610考试形式闭卷考试时间长度120分钟自觉遵守考场纪律如考试作弊此答卷无效一、选择题（每题1分，共5分）1．设有一个二维数组A[m][n]，如果A[0][0]的首地址为644(10进制)，A[2][2]的首地址为676，每个元素占一个字节，则A[4][5]的首地址为（）。A．692B．626C．709D．7242．若让元素1，2，3依次但并非连续进栈，则哪种出栈次序是不可能的（）A．3，2，1B．2，1，

2、3C．3，1，2D．1，2，33．设完全二叉树有82个结点，从根结点开始顺序编号，根节点为1号，其他结点自上向下，同一层次自左向右连续编号。则第41号结点的双亲结点的编号为（）A．20B．21C．81D．824．采用对半搜索算法搜索长度为n的有序表，元素的平均搜索长度为（）A．O(n2)B．O(n)C．O(nlog2n)D．O(log2n)5．采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）A．中序遍历B．前序遍历C．后序遍历D．按层次遍历二、判断题（每题1分，共5分）1．邻接表只能用于有向图的存储，邻

3、接矩阵对于有向图和无向图的存储都适用。（）2．直接选择排序是一种不稳定的排序方法。（）3．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。在设计再散列函数时，要求计算出的值与表的大小m互质。（）4．连通分量是无向图中的极小连通子图。（）5．若有一个叶子节点是二叉树中某子树的前序遍历结果序列的最后一个结点，它一定是该子树的中序遍历结果序列的最后一个结点。（）文案大全实用文档三、填空题（每空1分，10分）1．每次从表的无序部分取出一个元素，把它插入到表的有序部分的适当位置，此种排序方法叫作（1）排序；每

4、次从表的无序部分中挑选出一个最小或最大元素，把它与表的有序部分的后一元素交换，此种排序方法叫作（2）排序。2．中缀表达式“a*b/(x+2)+25”所对应的后缀表达式为（3）3．后缀表达式“ab/c-de*+ac*-”所对应的中缀表达式为（4）4．对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点数分别为（5）和（6）条。5．当向最小堆插入一个新元素时，应该首先成为堆的(7)元素，然后逐层(8)调整，直到调整到适当位置。当从一个最小堆删除一个元素时，需要把(9)元素填补到堆顶位置，然

5、后逐层(10)调整，直到调整到适当位置。四、简答简述题（每题8分，共24分）1．已知一棵树的广义表表示为：A(B(E(K,L),F),C(G(M,N)),D(H(O),I,J))请绘出该树的示意图，并画出其链式结构图。示意图：链式结构图：文案大全实用文档2．待排序序列有6个元素[21,25,49,25*,16,08]，以第1个元素21作为基准开始进行快速排序。首先绘出第1趟排序的详细过程，然后绘出各趟排序的结果。第1趟排序的详细过程：各趟排序的结果（只需给出每一趟排序开始状态和每一趟排序后的结果）：文案大全实

6、用文档3．根据下列条件绘出学生必修课程的AOV网络图、采用邻接表表示并给出入度表。建立入度为0的顶点栈(不一定借用入度表)及其在建立AOV网络拓扑排序过程中的变化。用图解法一步一步完成拓扑排序。最后给出课程学习次序的拓扑有序AOV网络。课程代号课程名称先修课程C1高等数学C2程序设计基础C3离散数学C1、C2C4数据结构C3、C2C5高级语言程序设计C2C6编译方法C5、C4C7操作系统C4、C9C8普通物理C1C9计算机原理C8文案大全实用文档五、综合算法题（每空2分，共56分）1．以下是最大堆的定义、插入

7、与删除操作，请完善以下各程序段。templateclassMaxheap:publicMaxPQ{Element*heap;intn;intMaxSize;public:Maxheap(intsz=Defaultsize);//创建空堆，最多可以容纳sz个元素voidInsert(Element&item);Element*Delete(Element&x);voidshow();};templateMaxheap::Maxhea

8、p(intsz){MaxSize=sz;n=0;heap=(1);//建立堆，heap[0]不用}templatevoidMaxheap::Insert(Element&x){inti;if(n==MaxSize){cerr<<"heapisfull.";return;}n++;for(i=n;i>1;){//i==1表示已达到根节点if(x<=(2))brea