东南大学数据结构试卷 - 图文

自觉遵守考场线

纪律

名姓

如考封试作弊此密

答卷无效

号学

东

南大学考试卷（A卷）

课程名称数据结构

考试学期

08-09-3

得分

适用专业

吴健雄学院电类

考试形式

半开卷考试时间长度

120分钟

一、选择题（每题1分，共5分）

1．下面有关链栈的描述，对常规情况正确的是

（

）

A．在链头插入，链尾删除。 B

．在链尾插入，链头删除。

C．在链尾插入，链尾删除。

D．在链头插入，链头删除。

2．对线性表进行对半搜索时，要求线性表必须（）

A．以数组方式存储 B．以数组方式存储并按关键码排序C．以链表方式存储

D

．以链表方式存储并按关键码排序

3．对包含n个元素的散列表进行搜索，平均搜索长度为（） A．O(log2n) B

．O(n) C

．不直接依赖于

n D

．三者均不是

4．在同一个有向图中，所有结点的入度和与出度和之比为（

）

A．1 B

．2 C

．1/2 D

．都不对

5．在具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。

A．n B

．n+1 C

．n-1 D

．n/2

二、判断题（每题

1分，共5分）

1．链式存储的线性表所有存储单元的地址可连续可不连续。（）2．存储有向图的邻接矩阵是对称的，所以可以仅存矩阵上三角部分。（）3．在采用闭散列法解决冲突时，不要立刻做物理删除，否则搜索时会出错。（）4．二叉树中序遍历结果序列的最后一个结点必是前序遍历的最后一个结点。（）5．堆排序的时间复杂度是

O(n log

2

n)，但需要额外存储空间。

（）

三、填空题（每空1分，第1空、第2空为2分，共11分）

1．中缀表达式“(a+b)*d+e/(f+a*d)+c)”所对应的后缀表达式为

（1）

2．后缀表达式“ab&&ef>!||

”所对应的中缀表达式为（2）

3．高度为h的二叉树最多可以有多少结点（4．若对一棵完全二叉树从

元素的左孩子结点为亲结点为(6)

3）

a中，则a[i]

，双

0开始编号，并按此编号把它顺序存储到一维数组(4)

。

，右孩子结点为(5)

5．对用邻接矩阵表示的图进行任何一种遍历时，其时间复杂度为

对用邻接表表示的图进行任何一种遍历时，其时间复杂度为6．折半插入排序的时间复杂度为

(9)

。

(7) (8)

。

。

四、简答简述题（每题8分，共24分）

1．设有一组关键码输入序列{55，31，12，37，46，73，63，02，07}，从空树开始构造

平衡二叉搜索树，画出每加入一个新结点时的二叉树形态，需标出平衡因子。包括发生不平衡时，旋转的各步的二叉树形态，并标注旋转类型。

2．已知一棵二叉树的前序遍历的结果为ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，试。

画出这棵二叉树。请用图表示逐步形成二叉树的过程（也可以用文字）

3．请用Kruskal算法，逐步画出下面有权无向图的最小生成树。必须每次添加一条边。

0

281

1

011

1

4165

1526

2

5

2

418

1

24

22

3

五、综合算法题（每空2.5分，共55分）

1．完善改进的归并排序算法。*this是一个待排序的表，而表

L2是一个辅助的工作表，帮

助完成排序的中间步骤，最终完成

*this的排序。所谓改进指在把元素序列复制到辅助表

中时，把第2个表的元素顺序逆转，这样两个待归并的表从两端开始处理，向中间归并。可以省去检查子表是否结束的判断。

template void Orderedlist::MergeSort(int left, int right){

Orderedlist L2;

improvedMergeSort(L2, left, right);

//对序列进行归并排序

}

template

void Orderedlist::improvedMergeSort(Orderedlist

int mid = (left + right)/2;

improvedMergeSort(L2, left, mid); improvedMergeSort(L2, mid + 1, right); //(1) ; }

template

void Orderedlist::improvedMerge(Orderedlist &L2, int left, int mid, int right){

int s1 = left, s2 = right, t = left, k ; 指针

for (k = left; k <= mid; k++){

(2) ;}

for (k = mid + 1; k <= right; k++){

(3) ;}

while (t <= right){

//归并过程//反向复制//正向复制

//s1,s2是检测指针，t是存放&L2, int left,

int right){

//从中间划分为两个子序列//对左侧子序列进行归并排序对右侧子序列进行归并排序//二路归并

if(L2.slist[s1] <= L2.slist[s2]) (4) ;else (5) ;}}

2．完成二叉树前序遍历的非递归算法和层次序遍历算法操作。

//非递归前序遍历。每访问一个结点后，在向左子树遍历下去之前，利用栈记录该结点的右子女结点的地址，以便在左子树退回时可以直接从栈顶取得右子树的根结点，继续右子树的前序遍历。

template void BinaryTree::PreOrder1(void *t) ) {

LinkedStack*> S; BinTreeNode *p = root; S.Push (NULL);

while (p != NULL) {

visit(p);

if (p->rightChild != NULL) (6) ; //

预留右指针在栈中

//访问结点

(*visit)

(BinTreeNode

if (p->leftChild != NULL)

(7) ;

else (8) ; }}

//层次序遍历。在访问二叉树某一层结点时，把下一层结点指针预先记忆在队列中，利用队列安排逐层访问的次序。因此每当访问一个结点时，将它的子女依次加到队尾。然后访//进左子树

//左子树为空，由堆栈弹出

问已在队头的结点。

template void BinaryTree::levelOrder (void (*visit) (BinTreeNode *t)) { if (root == NULL) return;

LinkedQueue * > Q; BinTreeNode *p = root; visit (p);

(9) ; while ( (10) ) { Q.DeQueue (p);

if (p->leftChild != NULL) {

visit (p->leftChild); (11) ;

}

if (p->rightChild != NULL) {

visit (p->rightChild); (12) ;

} }}

3．完成利用最大堆实现的优先级队列类定义。注意heap[0]不用，从heap[1]templateclass Maxheap{

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;

开始