东南大学数据结构试卷.doc-资料库

495af24b-024d-43d6-8030-c879c0beeb11.doc.pdf-第1页.png

第1页 / 共10页

495af24b-024d-43d6-8030-c879c0beeb11.doc.pdf-第2页.png

第2页 / 共10页

495af24b-024d-43d6-8030-c879c0beeb11.doc.pdf-第3页.png

第3页 / 共10页

495af24b-024d-43d6-8030-c879c0beeb11.doc.pdf-第4页.png

第4页 / 共10页

495af24b-024d-43d6-8030-c879c0beeb11.doc.pdf-第5页.png

第5页 / 共10页

495af24b-024d-43d6-8030-c879c0beeb11.doc.pdf-第6页.png

第6页 / 共10页

495af24b-024d-43d6-8030-c879c0beeb11.doc.pdf-第7页.png

第7页 / 共10页

495af24b-024d-43d6-8030-c879c0beeb11.doc.pdf-第8页.png

第8页 / 共10页

自觉遵守考场纪律如考试作弊此答卷无效线封密名姓号学东南大学考试卷（ A 卷）课程名称数据结构考试学期 1 0 - 1 1 - 3 得分适用专业吴健雄学院 610 考试形式闭卷考试时间长度 120 分钟一、选择题（每题 1 分，共 5 分） 1．设有一个二维数组 A[m][n]，如果 A[0][0]的首地址为 644(10 进制)，A[2][2]的首地址为 676，每个元素占一个字节，则 A[4][5]的首地址为（）。 A．692 D．724 B．626 C．709 2．若让元素 1，2，3 依次但并非连续进栈，则哪种出栈次序是不可能的（） A．3，2，1 C．3，1，2 B．2，1，3 D．1，2，3 3．设完全二叉树有 82 个结点，从根结点开始顺序编号，根节点为 1 号，其他结点自上向下，同一层次自左向右连续编号。则第 41 号结点的双亲结点的编号为（） A．20 B．21 C．81 D．82 4．采用对半搜索算法搜索长度为 n 的有序表，元素的平均搜索长度为（） A．O(n2) B．O(n) C．O(n log2n) D．O(log2n) 5．采用邻接表存储的图的深度优先遍历算法类似于二叉树的（） A．中序遍历 B．前序遍历 C．后序遍历 D．按层次遍历二、判断题（每题 1 分，共 5 分） 1．邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（） 2．直接选择排序是一种不稳定的排序方法。（） 3．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。在设计再散列函数时，要求计算出的值与表的大小 m 互质。（） 4．连通分量是无向图中的极小连通子图。（） 5．若有一个叶子节点是二叉树中某子树的前序遍历结果序列的最后一个结点，它一定是该子树的中序遍历结果序列的最后一个结点。（）共 10 页第 1页

三、填空题（每空 1 分， 10 分） 1．每次从表的无序部分取出一个元素，把它插入到表的有序部分的适当位置，此种排序方法叫作（1）把它与表的有序部分的后一元素交换，此种排序方法叫作（2）排序；每次从表的无序部分中挑选出一个最小或最大元素，排序。 2．中缀表达式“a*b/(x+2)+25”所对应的后缀表达式为（3） 3．后缀表达式“ab/c-de*+ac*-”所对应的中缀表达式为（4） 4．对于一个具有 n 个顶点和 e 条边的有向图和无向图，在其对应的邻接表中，所含边结点数分别为（5）和（6）条。 5．当向最小堆插入一个新元素时，应该首先成为堆的(7) 元素，然后逐层(8) 需要把(9) 调整，直到调整到适当位置。当从一个最小堆删除一个元素时，元素填补到堆顶位置，然后逐层(10) 调整，直到调整到适当位置。四、简答简述题（每题 8 分，共 24 分） 1．已知一棵树的广义表表示为：A(B(E(K,L),F),C(G(M,N)),D(H(O),I,J)) 请绘出该树的示意图，并画出其链式结构图。示意图：链式结构图：共 10 页第 2页

2．待排序序列有 6 个元素[21,25,49,25*,16,08]，以第 1 个元素 21 作为基准开始进行快速排序。首先绘出第 1 趟排序的详细过程，然后绘出各趟排序的结果。第 1 趟排序的详细过程：各趟排序的结果（只需给出每一趟排序开始状态和每一趟排序后的结果）： 3．根据下列条件绘出学生必修课程的 AOV 网络图、采用邻接表表示并给出入度表。建立入度为 0 的顶点栈(不一定借用入度表)及其在建立 AOV 网络拓扑排序过程中的变化。用图解法一步一步完成拓扑排序。最后给出课程学习次序的拓扑有序 AOV 网络。共 10 页第 3页

课程代号 C1 C2 C3 C4 C5 C6 C7 C8 C9 课程名称高等数学程序设计基础离散数学数据结构高级语言程序设计编译方法操作系统普通物理计算机原理先修课程 C1、C2 C3、C2 C2 C5、C4 C4、C9 C1 C8 共 10 页第 4页

五、综合算法题（每空 2 分，共 56 分） 1．以下是最大堆的定义、插入与删除操作，请完善以下各程序段。 templateclass Maxheap:public MaxPQ{ Element* heap; int n; int MaxSize; public: Maxheap(int sz=Defaultsize); //创建空堆，最多可以容纳sz个元素 void Insert(Element& item); Element* Delete(Element& x); void show(); }; templateMaxheap::Maxheap(int sz){ MaxSize=sz; n=0; heap=(1) ; //建立堆，heap[0]不用 } templatevoid Maxheap::Insert(Element& x){ int i; if(n==MaxSize){ cerr<<"heap is full.\n"; return; } n++; for(i=n;i>1;){ if(x<=(2) (3) (4) } (5) //i==1表示已达到根节点 ) break;//新元素的关键字不大于结点i的双亲的关键字 ;//heap[i]未占用，将双亲结点元素移到结点i中 ; ; //i继续向上 //x的位置定了，再放数值进去 } templateElement* Maxheap::Delete(Element& x){ int i,j; if(!n){ cerr<<"heap is empty.\n"; return NULL; } x=heap[1]; 共 10 页第 5页

Element k=heap[n]; //候补的结点为最大下标元素，原来应该将它放在堆顶， n--; for(i=1,j=2;j<=n;){ //为了简化算法，暂时放在工作对象k中 //堆元素数减1 //j是i的子女 if(jvoid BinaryTree::PreOrder1(void (*visit) (BinTreeNode *t) ) { //非递归前序遍历 LinkedStack*> S; BinTreeNode *p = root; S.Push (NULL); while (p != NULL) { visit(p); if (p->rightChild != NULL) (12) if (p->leftChild != NULL) (13) (14) } } //访问结点 //预留右指针在栈中 //进左子树 //左子树为空，由堆栈弹出 ; ; ; template void BinaryTree::InOrder1(void (*visit) (BinTreeNode *t)) { //非递归中序遍历 LinkedStack*> S; BinTreeNode *p = root; do { 共 10 页第 6页

while (p != NULL) { (15) (16) } if (!S.IsEmpty()) { (17) (18) } ; ; //该子树沿途结点进栈 //遍历指针向左下移动 //栈不空时退栈 visit (p); ; //退栈, 访问 ; //遍历指针进到右子女 } while (p != NULL || !S.IsEmpty ()); } 3．完善/邻接矩阵存储的图的类定义（无向图）的一些成员函数 template class Graphmtx : public Graph{ public: //图的邻接矩阵类定义 Graphmtx(int sz = maxSize); ~Graphmtx(){ delete []VertexList; delete []Edge; } T getValue(int i){ //构造函数 //析构函数 //取顶点i的值, i不合理返回0 return i >= 0 && i < numVertices ? VertexList[i] : 0; } E getWeight(int v1, int v2){ //取边(v1,v2)上的权值，若边不合理，则返回0 return v1 != -1 && v2 != -1 ? Edge[v1][v2] : 0; } int getFirstNeighbor(int v); //取顶点v的第一个邻接顶点 int getNextNeighbor(int v, int w); //返回该邻接顶点的编号，若不存在则返回-1 //取v的邻接顶点w的下一邻接顶点 //返回下一个邻接定点的编号，若不存在或参数不合理则返回-1 bool insertVertex(const T &vertex); //插入顶点vertex //接受一个参数，表示插入顶点的值，返回true表示插入成功 bool insertEdge(int v1, int v2, E cost);//插入边(v1, v2),权值为cost，返true表示插入成功 bool removeVertex(int v);//删去顶点v和所有与它相关联的边，返回true表示删除成功 bool removeEdge(int v1, int v2); int getVertexPos(const T &vertex){//给出顶点vertex在图中的位置，若不存在则返回-1 //在图中删去边(v1,v2),返回true表示删除成功 for (int i = 0; i < numVertices; i++){ if (VertexList[i] == vertex){ return i; 共 10 页第 7页

} } return -1; } private: T *VertexList; E **Edge; //顶点表 //邻接矩阵 }; template Graphmtx::Graphmtx(int sz):Graph(sz){ int i, j; VertexList = new T[maxVertices]; Edge = (int **) new int *[maxVertices]; for (i = 0; i < maxVertices; i++){ Edge[i] = new int[maxVertices]; } for (i = 0; i < maxVertices; i++){ for (j = 0; j < maxVertices; j++){ Edge[i][j] = maxWeight; //创建顶点表数组 //创建邻接矩阵数组 //邻接矩阵初始化 } } } //给出顶点位置为v的第一个邻接顶点的位置, 如果找不到, 则函数返回-1。 template int Graphmtx::getFirstNeighbor(int v) { if (v != -1){ for (int col = 0; col < numVertices; col++){ if ((19) return col; ){ } } } return -1; } //给出顶点v的某邻接顶点w的下一个邻接顶点 template int Graphmtx::getNextNeighbor(int v, int w){ if (v != -1 && w != -1){ 共 10 页第 8页

资料库

东南大学数据结构试卷.doc

相关推荐

行业

热门标签

最新资料