2019-2020-2 数据结构期末试卷¶

2019级

一、选择题(9分)¶

假定AA为一个类，a为该类公有的数据成员，x为该类的一个对象，则访问x对象中数据成员a的格式为( )

A. x(a)

B. x[a]

C. x->a

D. x.a

使用引用传参将实参传给形参，下列说法正确的是( )。

A. 实参是形参的备份

B. 实参与形参无联系

C. 形参是实参的备份

D. 实参与形参是同一对象

有如下类定义：

class Foo
{
public:
    Foo(int v): value(v) { } // ①
    ~Foo() {} // ②
private:
    Foo() {} // ③
    int value = 0; // ④
};

其中存在语法错误的行是( )

A. ①

B. ②

C. ③

D. ④

二、程序阅读题(7分)¶

C++

class A
{
public:
    A() {
        X = Y = 0;
        cout << "Default Constructor called" << endl;
    }
    A(int xx, int yy) {
        X = xx; Y = yy;
        cout << "Constructor called" << endl;
    }
    ~A() {
        cout << X << "  " << Y << endl;
        cout << "Destructor called" << endl;
    }
private:
    int X, Y;
};

int main()
{
    A a;
    A *p1 = new A(1, 2);
    delete p1;
    return 0;
}

写出上述程序的打印结果。

三、程序填空题(6分)¶

完成使链表逆置的函数 reverse，返回逆置链表头节点。链表结构如下：

C++

struct Node {
    int val;
    Node *next;
};

Node* reverselist(Node* head) {
    if (head == NULL || ________(1)________) return head;
    Node *p = head;
    Node *q = head->next;
    p->next = NULL;
    Node* temp;
    while (q != NULL) {
        ________(2)________;
        q->next = p;
        p = q;
        q = temp;
    }
    return ________(3)________;
}

四、栈(8分)¶

请设计一种栈式结构，要求实现 Push(入栈)、Pop(出栈)、Min(返回栈中的最小值)三种操作，且时间复杂度均为 \(O(1)\) 并用5, 6, 9, 2这四个数据辅助说明这个栈的设计，及其出栈，入栈和取最小值的操作。

五、迷宫问题(8分)¶

用下述二维数组 matrix[][] 描述迷宫，初始时其中-1表示迷宫的墙，0表示没有墙，可通行。现在起点在 src 位置，终点在 des 位置 (src 位置的值为1，des 位置的值为0)。

-1	-1	-1
-1	-1	0
0	-1	-1
-1	0	0
0	0	-1

现在 Pos src 为起点，通过调用 DFS(src, 1) 函数，请画出完整执行 DFS 函数后的迷宫数组，填写在下面。代码中 Pos 是一个结构体：

C++

struct Pos {
    int row; //表示数组的行
    int col; //表示数组的列
};

void DFS (Pos cur, int step) {
    //迷宫终点找到
    if (cur.row == 0 && cur.col == 4) {
        return;
    }
    //按照左,上,右,下的顺序探索迷宫
    int dir[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
    Pos next;
    for (int z = 0; z < 4; z++) {
        next.row = cur.row + dir[z][0];
        next.col = cur.col + dir[z][1];

        if (next.row >= 0 && next.row <= 4 && next.col >= 0 && next.col <= 4 && matrix[next.row][next.col] == 0) {
            matrix[next.row][next.col] = step + 1;
            DFS(next, step + 1);
        }
    }
}

待填写数组：

-1	-1	-1
-1	-1
	-1	-1
-1
		-1

六、排序(10分)¶

某整型数组A的10个元素依次为 \(\{36, 12, 49, 27, 13, 28, 54, 65, 0, 1\}\)。用下列排序方法，将A中的元素从小到大排序。

(1) 取第一个元素36作为分割数，试写出快速排序第一次分隔后A中的结果。

(2) 用低位优先基数排序法，尝试写出第一次分配和收集后A中的结果。

七、堆(9分)¶

(1) 有数组 \(A = [9, 12, 17, 30, 50, 20, 60, 65, 4, 49]\)，请写出对应的完全二叉树。

(2) 请将该二叉树(数组)调整为小顶堆，写出调整后的数组。

八、二叉树(9分)¶

(1) 写出下述中序遍历的结果(4分)。

(2) 用栈实现非递归的二叉树中序遍历。请首先用文字或伪代码(及注释)描述你的算法思路。根据你的算法思路，用下图中的二叉树描述详细的非递归中序遍历过程，可以画图辅助说明(5分)。

132b8833-6363-4dd4-a81b-5e2bf64f360b

九、最短路径(9分)¶

用迪杰斯特拉算法求解下图中的最短路径。设0为起始点。Dist数组为算法中存储起始点到其他点当前最短路径长度的数组，初始时其他点的距离均为无穷大。请填写下面表格中Dist数组的值，完成前4次算法迭代中 Dist 数组更新。

8fcf97d1-11ec-4ffc-8f70-29cb96d447d3

Dist	Dist[1]	Dist[2]	Dist[3]	Dist[4]	Dist[5]	Dist[6]	Dist[7]
\(i=0\)	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)	\(\infty\)
\(i=1\)
\(i=2\)
\(i=3\)
\(i=4\)

十、哈希表(8分)¶

有下列六个字符：'a', 'b', 'h', 'j', 'k', 'q'，请设计一个任意的哈希函数，并用开放地址法、线性探测的方法构造哈希表，填入下面大小为7的数组中。请写明你用的哈希函数，并画出哈希表。

哈希函数：

哈希表：

十一、算法设计(8分)¶

给定一个数组，数组大小为n，数组中除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素，给出详细的算法描述或者伪代码描述。要求空间复杂度必须为 \(O(1)\)，时间复杂度越低越好。

注：

平均时间复杂度为 \(O(n \log(n))\) 可得一半分，无须复杂度分析。(4分)
平均时间复杂度低于 \(O(n \log(n))\) 可得全部分(8分)，可通过例子辅助说明，但如果描述模糊或者表述不清楚，不得分。并简单地写出平均时间复杂度的测算方法(复杂度分析不用特别严谨，占1分)。

(提示：这里是平均时间复杂度而不是最坏时间复杂度)。

十二、程序设计——二叉树(9分)¶

当前婚育制度下一个家庭最多可以有两个子女，整个家庭的族谱按照辈分由高到低构成了一颗二叉树，给定族谱的二叉树，请根据问题写出对应的代码。

最大继承权： 二叉树中每个节点的值表示对应子女的爱心值，辈分最低并且爱心值最大的子女拥有最大继承权。输入一棵二叉树描述的族谱的根节点，输出该家族拥有最大继承权的子女的爱心值。如需要自己添加函数或者参数，请注释写明。

说明：从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径，最长路径的下的叶节点的辈分最低。如果存在多个辈分最低的子女，输入其中最大的爱心值。

例如：给定二叉树如下图，15和7所表示的子女辈分最低，输出它的最大爱心值：15

代码：

C++

struct BinaryTreeNode
{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;

    BinaryTreeNode() {
        m_pLeft = NULL;
        m_pRight = NULL;
    }
};

//最大继承权子女的爱心值
int Max_Love_Value (BinaryTreeNode* pRoot)
{
    // 请在此处补充代码

}

2019-2020-2 数据结构 期末试卷¶