2023-2024-1 数据结构 期末试卷

2023级

---

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

【1】在以下数据结构中,哪种数据结构具有先进先出(FIFO)的特性()?

A. 栈(Stack)

B. 队列(Queue)

C. 链表(Linked List)

D. 树(Tree)

【2】若出栈序列为A,B,C,D,则通过入出栈操作,可能的关于A,B,C,D的入栈顺序为( )。

A. D, B, C, A

B. D, C, B, A

C. D, B, C, A与D,C,B,A都可能。

D. D, B, C, A与D,C,B,A都不可能。

【3】栈的顶部用 top指示,删除栈顶元素的操作是什么(假如push的第一个元素在0位置,第二个元素在1位置)( )。

A、if \((top!=-1)\) top--;

B、if \((top!=-1)\) top++;

C、top++;

D、top--;

【4】若用一个大小为5的数组来实现循环队列,且当前rear和front 的值分别为4和3,当从队列中删除一个元素,再加入两个元素后,rear和front 的值分别为什么?()

A. 1和4

B. 2和4

C. 4和2

D. 以上都不对

【5】请阅读以下代码。请问output(4)的输出为( )。

C++

void output (int n)
{
    if (n<=1)
        return;
    output (n/2);
    printf("%d",n);
    output (n-1);
}

A. 432

B. 243

C. 2432

D. 以上都不对

【6】以下关于递归的说法正确的是( )

A. 在求斐波那契数列时,利用递归的方法比循环的方法在空间的消耗上相同。

B. 递归程序在函数调用时会用到队列的数据结构

C. 使用了剪枝的递归策略在时间效率上一定比相应的非递归实现时间更短。

D. 以上说法都不对。

【7】以下数组中,只允许向右或者向下前进,标记0是允许前进的位置,-1的位置不允许前进,请问从src到des有几条可行的路径( )

src	0	0	0
0	0	-1	0
0	0	0	des

A. 3

B. 4

C. 5

D. 以上都不对

【8】某链表中最常用的操作是在最后一个元素之后插入一个和删除最后一个元素,则采用【】的存储方式是最高效的。

A. 无优化的单链表

B. 循环链表

C. 双链表

D. 带头节点的双循环链表

【9】以下关于哈希表的说法正确的是( )

A. 若采用开放定址法处理冲突,则删除元素只需直接将该元素从哈希表中删去即可。

B. 若采用开放定址法处理冲突+线性探测处理冲突,若哈希表中k个关键字具有同一哈希值,那么这k个关键字在哈希表中的位置一定是连续的。

C. 设散列表的长度为10,散列函数H(n)=n mod 7,初始关键字序列为(33, 24, 8, 17, 21, 10),用链地址法作为解决冲突的方法,平均查找长度是2。

D. 以上说法都不正确。

【10】以下关于二分搜索说法正确的是( )

A. 二分查找要求仅是数据单调递增或者递减即可

B. 对一个有序数组二分查找寻找某个数据时,可能最小的比较次数是1次。

C. 对一个有序数组二分查找时(数组大小>1000),可能最多的比较次数是数组的元素个数。

D. 二分查找要求数组中的任何两个元素都不相同

---

二、链表(10分)

设有一个单链表节点定义如下:

C++

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

一个双链表节点定义如下:

C++

struct Dnode {
    int val;
    Dnode* prior;
    Dnode* next;
};

请写出下述代码。注:以下代码不用写完整函数,只要写出满足要求的相应链表操作即可。

(1) 在单链表中,已知q所指节点是p所指节点的前驱节点,若在q和p之间插入节点s,请写出相应代码。(5分)

(2) 在一个双链表中,请写出在p指向节点之前插入一个节点q的相应代码。(5分)

---

三、递归(14分)

head -> 1 -> 3 -> 5 -> 7 (题三一图)

有一个链表,其结构体定义如下,链表内容如题三一图所示。

定义链表节点结构:

C++

struct ListNode {
    int value;
    struct ListNode* next;
};

现在有一个 rLinkedList 函数,函数定义如下。假设调用 rLinkedList 函数时, head 指针已经被赋值为题三一图中所示的链表头节点。请回答下述问题。

C++

// 函数定义
ListNode* rLinkedList (ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    // 递归地反转剩余部分
    struct ListNode* newHead = rLinkedList (head->next);
    if (newHead != NULL)
        printf("%d,", newHead->value);

    head->next->next = head;
    head->next = NULL;
    return newHead;
}

(1) 现对题三一图中的链表调用:

ListNode* newHead = rLinkedList (head);

请仿照题三一图画出 newHead 指向的链表(4分)。

(2) 对题三一图中的链表调用:

ListNode* newHead = rLinkedList (head);

请画出函数调用图,并给出 rLinkedList 的函数调用次数(5分)。

(3) 对题三一图中的链表调用:

ListNode* newHead = rLinkedList (head);

请写出函数所有的输出(printf的内容)(5分)。

---

四、栈和队列(12分)

给一个数组 array,最多可以存放Max个元素。现在要求在array上同时设计一个循环队列与一个栈,即两者共用 array数组实现。要求: 队列或栈的大小上限都可以达到Max。

请给出你的设计,给出该数据结构的设计方案,必须包括的内容:对数组整体的设计,必要的数据结构参数,入栈,出栈,入队,出队,判断栈或队列满的条件。另外,请使用图和结合例子的形式来描述你的方案。请注意本题的表达十分重要,模糊的描述会得不到分数。本题限制使用其他的数据结构,但对要设计的操作的时间效率不做要求。

---

五、搜索(15分)

有如下一个数组: [15, 18, 23, 38, 58, 60, 68, 80, 90, 99]

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

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

(3) 设有序的整型数组array,数组大小为n,请给出对 array进行二分搜索目标(target)的完整函数,返回target 在 array 中的位置,如果找不到target的值,那么函数需要返回比 target 小的最大数据的位置。比如当上面的数组要寻找59时,因为59不在数组中,那么需要返回比59小的最大数字即58的位置4。可以增加其他函数,但不得使用伪代码(6分)。

C++

int BinarySearch(int *array, int n, int target) {
    // 补充代码
}

---

六 广度&深度优先遍历(13分)

要求对规模为m*n 的二维整数数组A(见表1)从某个位置开始进行扩张。A[i][j]代表第i行第j列的数字。给定r,c和number,r,c为初始元素的行列坐标,number 为待扩张的数字。现给出一种扩张方式,以A[r][c]作为初始元素,找出初始元素上下左右四个方向上数字与初始坐标的相邻元素,并将其改为number+1,接着再进一步对标记为number+1的数字沿着四个方向扩张,将其扩张为 number+2, ... 重复该过程,直到周围没有符合条件的元素。在扩张过程中,已经扩张的元素不会再被扩张,并且数组中为-1的位置不允许扩张。以上扩张的过程称为广度优先遍历。

表 1.

0	0	0	0	-1
0	5	0	-1	0
0	0	0	0	0
0	-1	0	0	-1
0	0	0	-1	0

(1) 现给定二维数组A,见表2。给定初始元素的坐标为(1,1)(表中5所在位置),初始数字为5;并根据上述描述的广度优先遍历过程进行数字扩张。从初始元素开始对数组进行扩展,假设起点为扩展的第1层,按上、下、左、右的顺序访问,逐层扩展。

(i) 下表2已给出扩展到第二层的结果,请继续填充表2,给出扩张结束后的数组(4分)。

表 2.

	6			-1
6	5	6	-1
	6
	-1			-1
			-1

(ii) 广度优先遍历需要结合队列来进行扩张,请给出从A[1][1]扩张到A[3][2]的扩张过程(4分)。

(2) 对表1所示的表,给定初始元素的坐标为(1,1),本题也可以用深度优先遍历进行扩张。描述采用深度优先搜索扩张数字的过程(可以考虑结合扩张后的数组),要求按照上、下、左、右的顺序进行扩张(5分)。