2021-2022-1 数据结构期末试卷¶

2021级

一、选择题(每小题4分)¶

【1】线性表存储时，其地址( )

A. 必须是连续的

B. 部分地址必须是连续的

C. 一定是不连续的

D. 连续与否均有可能

【2】栈在( )中有所应用。

A. 递归调用

B. 函数调用

C. 表达式求值

D. 前三个选项都有

【3】在单链表指针为 \(p\) 的结点之后插入指针为 \(s\) 的结点，正确的操作是：( )

A. p->next=s; s->next=p->next;

B. s->next=p->next; p->next=s;

C. p->next=s; p->next=s->next;

D. p->next=s->next; p->next=s;

【4】双向链表中有两个指针域，Llink 和 Rlink，分别指回前驱及后继，在双向链表指针 \(p\) 的结点前插入一个指针为 \(q\) 的结点操作是( )

A. p->Llink=q; q->Rlink=p; p->Llink->Rlink=q; q->Llink=q;

B. p->Llink=q; p->Llink->Rlink=q; q->Rlink=p; q->Llink=p->Llink;

C. q->Rlink=p; q->Llink=p->Llink; p->Llink->Rlink=q; p->Llink=q;

D. q->Llink=p->Llink; q->Rlink=p; p->Llink=q; p->Llink=q;

【5】若用一个大小为6的数组来实现循环队列，且当前 rear 和 front 的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为多少？( )

A. 1和5

B. 2和4

C. 4和2

D. 5和1

【6】有如下一个函数：

int f(int a, int &b, int *c){
    a++;
    b++;
    *c = *c + 1;
    return a;
}

和如下一个 main 函数：

int main(){
    int a, b;
    int *c;
    a = 5; b = 10; c = 15;
    int d = f(b, c, &a);
    return 0;
}

那么 main 函数执行后变量 main 函数中 \(a, b, c, d\) 的值分别为：

A. 5, 10, 15, 5

B. 6, 11, 16, 6

C. 5, 6, 11, 6

D. 6, 10, 16, 11

【7】请阅读以下代码，请问 printinput(5) 的输出为( )。

void printinput(int n){
    if(n <= 0) return;
    printinput(n - 3);
    printinput(n - 1);
    cout << n;
}

A. 345

B. 22345

C. 12112345

D. 211234

【8】哈希函数可以减少冲突，但仍不可避免，通常处理冲突的方法有( )。

A. 链地址法和直接定址法

B. 线性探测再散列法和二次探测再散列法

C. 开方定址法和链地址法

D. 线性探测再散列法和链地址法

【9】若有18个元素的有序表存放在一维数组 A[19] 中，第一个元素放在 A[1] 中，现进行二分查找，则查找 A[3] 的比较序列的下标依次为( )

A. 1, 2, 3

B. 9, 5, 2, 3

C. 9, 5, 3

D. 9, 4, 2, 3

【10】设有序数组中有1000个元素，则二分查找元素最多需要比较多少( )次。

A. 25

B. 10

C. 7

D. 1

【11】设有 \(m\) 个关键字具有相同的哈希函数值，则用线性探测法把这个关键字映射到大小为 \(n\) 的哈希表中需要做( )次哈希探测（将一个关键字映射到一个哈希表的空位置时也算作一次哈希探测）。

A. \(m^2\)

B. \(n\)

C. \(m \times (m+1)/2\)

D. \(m \times (m-1)/2\)

【12】设用链式结构实现栈，指针变量 top 指向当前链式栈的栈顶，则删除栈顶元素的操作应该为( )

A. top = top + 1;

B. top = top - 1;

C. top->next = top;

D. top = top->next;

【13】以下哪一个术语与数据的存储结构无关？

A. 栈

B. 哈希表

C. 数组

D. 双向链表

二、递归(12分)¶

有下面的递归函数。

#include <iostream>
using namespace std;

int fib(int n){
    if(n <= 0) return 0;
    else if(n == 1) return 1;
    else{
        cout << n << endl;
        return fib(n - 1) + fib(n / 2);
    }
}

int main(){
    cout << fib(5) << endl; 
    return 0;
}

(1) 计算上述程序中 fib 函数一共被调用多少次(4分)

(2) 依次写出函数所有的输出。(4分)

(3) 上述代码计算效率不高是因为递归过程中有很多重复计算，通过减少重复计算可以提高。试改造上述代码，提高计算效率。允许使用其他的变量、函数、数据结构等。请使用注释的形式进行说明。书写模糊或者混乱者不得分。请在答案中写出完整的代码。(4分)

三、栈(12分)¶

设用一个数组 \(S\) (设大小为 MAX)作为两个栈的共享空间，请设计共享方法，设两个栈分别为栈A、栈B。可以画图说明，基于 \(S\) 数组，请分别说明以下，栈A、栈B分别的 push, pop, top 操作如何实现，以及栈A、栈B判断栈空和栈满的实现。

四、迷宫问题(12分)¶

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

matrix 数组：

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

(1) 用队列和广度优先搜索(BFS)的方法对迷宫进行探索，也就是从 src 点开始，对迷宫进行扩展，假设 src 起点为扩展的第 0 层，数组中 matrix[1][0] 位置为扩展的第 1 层，如此，请画出数组中直到找到 des 为止时每个节点所扩展的层数(6分)。

0层	-1	-1	-1
1层	-1	-1
		-1	-1
	-1
			-1	1

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

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

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

注：下面矩阵中空白位置的初始值为 0。

五、算法设计(12分)¶

有如下一个数组 [21, 33, 43, 58, 59, 65, 72, 82, 99]

(1) 如果要在该数组中通过二分查找查找元素 43，请写出完整的查找过程(4分)。

(2) 为该数组构建大小为 10 的哈希表，哈希函数为 \(h(key) = key \% 10\)，并用开放地址法-线性探测法处理冲突，从左到右依次将数组中元素加入到哈希表中，请画出所构建的哈希表。并写出元素 43 在哈希表中的查找过程(4分)。

(3) 设现有数组变为 [21, 21, 45, 45, 59, 59, 59, 65, 72, 72, 99]，即数组中存在重复元素，现要用二分查找求某个元素在数组中第一次出现的位置，比如 45 在数组中第一次出现的位置是 2 (数组下标从 0 开始计算)，请写出下面的代码，其中 \(k\) 为要查找的元素，array 为数据，length 为数组长度，允许自己增加变量，请用注释进行说明，如有必要，也可用示例数组说明你用的方法，表达模糊或者混乱者不得分。(4分)

int GetFirst(int k, int *array, int length)

2021-2022-1 数据结构 期末试卷¶