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

自 觉 遵 守 考 场 纪 律 名 姓 如 考 试 作 弊 此 答 卷 无 号 效学东 南 大 学 考 试 卷（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．692 B．626 C．709 D．724

2．若让元素1，2，3依次但并非连续进栈，则哪种出栈次序是不可能的（ ） 线 A．3，2，1 B．2，1，3 C．3，1，2 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 离散数学 C1、C2 C4 数据结构 C3、C2 C5 高级语言程序设计 C2 C6 编译方法 C5、C4 C7 操作系统 C4、C9 C8 普通物理 C1 C9

计算机原理 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<<\ return; } n++; for(i=n;i>1;){ //i==1表示已达到根节点

if(x<=(2) ) break;//新元素的关键字不大于结点i的双亲的关键字 (3) ;//heap[i]未占用，将双亲结点元素移到结点i中

(4) ; //i继续向上 } (5) ; //x的位置定了，再放数值进去 }

templateElement* Maxheap::Delete(Element& x){ int i,j; if(!n){ cerr<<\ return NULL; } x=heap[1];

共 10 页 第5页