南邮《数据结构A》2017/2018学年第二学期期末考试回忆

2018.6.29  16:00-17:50数据结构考试

刚考完，趁着还有记忆，回忆一下考试题目。

先总结一下：考试总体还是比较简单的。有考到很细的知识点，复习时要过一遍书，知识点要多看看。毕竟数据结构考编程不多，重要的是算法思想。

一、填空题（10*2'=20'）

只记得几个了。

1.告诉你AVL树的先序遍历，让你写出中序遍历。我一开始还傻傻地画图，后来一想到AVL树也叫排序树，瞬间就知道答案了，中序遍历是递增序列。

2.f(n)=50n+50log2n+50nlog2n，求时间复杂度：O(nlog2n)

3.循环队列队列满的时候，元素个数：maxSize-1

4.线性表采用查找次数比较多，问用哪种存储结构：顺序存储结构。

5.中缀表达式求值：7。

6.5阶B-树根结点的度最少为：2。

7.A[10][20]首地址是200，每个元素占一个单位，问A[6][12]地址：332。

8.考了一个概念：尴尬，忘了考的是冲突还是同义词了。

冲突：不同关键字经过散列函数映射到相同地址的现象。

同义词：不同关键字经过散列函数映射到相同地址。

我写的是冲突，好像应该填同义词？？？(难过.jpg)

二、选择题（10*2'=20'）

1.循环队列为空的条件：front==rear。

2.书上原题：i=1;x=0;do{x++;i=3*i;}while(i<n)；求渐进时间复杂度：O(log3n)

3.拓扑排序：采用邻接表是O(n+e)

4.单链表插入的程序段，p插在q后面：p->link=q->link;q->link=p;

5.以行优先规则存储矩阵元素，存储下三角元素，a23的下标为：3*(3+1)/2+2=8

6.Dijkstra算法：一共n个顶点，问下面哪句话是错的(这题一直不确定，一开始选的B，后来改的A)

A.运算一次可以得到任意两点的最短距离

B.运算n次可以得到任意两点的最短距离

C.运算一次可以得到指定点到其他n-1个顶点的最短距离

D.采用邻接矩阵存储，O(n2)

三、简答题

1.二次探测法

2.AVL树插入

3.哈夫曼树构建过程，并求WPL。

4.Prime算法，并求最小代价，答案好像是87。

5.写出快速排序的前两趟结果。

四、程序填空题（5*2'=10'）

考的是书上的简单选择排序。

1：list.D[i].key < list.D[minIndex].key(翻书发现还要写.key？？？)

2：minIndex = i

3：startIndex < list->n-1(我好像写的是startIndex < list->n)

4：FindMin(*list,startIndex)(参数传递要写*list？我写的是list)

5：startIndex++

一直不怎么喜欢书上这个简单选择排序，都是直接三个函数并在一起写成一个函数用的，这下吃亏了。

五、算法设计题（1*10'=10'）

求任意顶点v的入度。(这题还好，上午刚写过这个算法)

typedef struct ENode{
    int adjVex;
    struct ENode *nextArc;
}ENode;

typedef struct{
    int n;
    ENode **A;
}LGraph;

int Degree(LGraph g,int v){
    int i,d = 0;
    ENode *p;
    for(i = 0;i < g.n;i ++){
        for(p = g.A[i];p;p = p->nextArc){
            if(p->adjVex == v){
                d ++;
            }
        }
    }
    return d;
}

其实还是有很多难的知识点没有考的，比如：B-树的删除、二叉树遍历的应用、关键路径、图的遍历(DFS和BFS)、稀疏矩阵等等。

总结：考完感觉还行，对着课本回忆了一下题目，发现错了好多，有点小难过，没上95的话下学期跟着大二重修一下刷下分，本来想考100的。