数据结构 机考真题

循环链表表示队列

题干

假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），请完成下列任务：

  1. 队列初始化，成功返回真，否则返回假：
    1
    bool init_queue(LinkQueue *LQ);
  2. 入队列，成功返回真，否则返回假： 
    1
    bool enter_queue(LinkQueue *LQ, ElemType x);
  3. 出队列，成功返回真，且*x为出队的值，否则返回假
    1
    bool leave_queue(LinkQueue *LQ, ElemType *x);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef struct _QueueNode {
    ElemType data;            // 数据域
    struct _QueueNode *next;  // 指针域
} LinkQueueNode, *LinkQueue;

#include <stdio.h>
#include <stdlib.h>

bool init_queue(LinkQueue *LQ)
{

}

bool enter_queue(LinkQueue *LQ, ElemType x)
{

}

bool leave_queue(LinkQueue *LQ, ElemType *x)
{

}

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
bool init_queue(LinkQueue *LQ)
{
    (*LQ) = (LinkQueue)malloc(sizeof(LinkQueueNode));
    if ((*LQ) == NULL)
        return false; //空间分配失败
    (*LQ)->data = 0; // 这一步不必要
    (*LQ)->next = (*LQ); // 循环队列

    return true;
}

bool enter_queue(LinkQueue *LQ, ElemType x)
{
    LinkQueue NewNode = (LinkQueue)malloc(sizeof(LinkQueueNode));
    if (NewNode == NULL || (*LQ) == NULL)
        return false; // 空间分配失败或队列不存在

    // 队列的添加是在队尾进行
    NewNode->data = x;
    NewNode->next = (*LQ)->next; // 新结点连接头结点
    (*LQ)->next = NewNode; // 队尾连接新结点
    (*LQ) = NewNode; // 更新队尾指针

    return true;
}

bool leave_queue(LinkQueue *LQ, ElemType *x)
{
    if ((*LQ) == NULL)
        return false;
    if ((*LQ)->next == (*LQ))
        return false;

    LinkQueue HeadNode = (*LQ)->next; // 头结点位置
    LinkQueue LeaveNode = HeadNode->next; // 要离开的结点

    HeadNode->next = LeaveNode->next; // 将头结点next位置重新调整
    *x = LeaveNode->data; // 注意不要遗漏这一步
    if ((*LQ) == LeaveNode)
        (*LQ) = HeadNode; // 这个判断很关键，如果离开的结点是最后一个结点，就需要修改(*LQ)的指向
    
    free(LeaveNode);

    return true;
}

非递归先序遍历

题干

已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法：
void pre_order(BiTree root);
在遍历过程中，pre_order 函数需要调用 visit_node 函数来实现对结点的访问，该函数声明如下：

void visit_node(BiTNode *node); 二叉树的相关定义如下：

1
2
3
4
5
6
7
typedef int DataType;

typedef struct Node{
    DataType data;
    struct Node* left;
    struct Node* right;
}BiTNode, *BiTree;

遍历所使用栈的相关操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
#define Stack_Size 50
typedef BiTNode* ElemType;
typedef struct{
    ElemType elem[Stack_Size];
    int top;
}Stack;

void init_stack(Stack *S); // 初始化栈
bool push(Stack* S, ElemType x); //x 入栈
bool pop(Stack* S, ElemType *px); //出栈，元素保存到px所指的单元，函数返回true,栈为空时返回 false
bool top(Stack* S, ElemType *px); //获取栈顶元素，将其保存到px所指的单元，函数返回true，栈满时返回 false
bool is_empty(Stack* S);  // 栈为空时返回 true，否则返回 false

请在下方编写代码:

1
2
3
4
5
#include <stdlib.h>

void pre_order(BiTree root) {
  
}

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void pre_order(BiTree root) {
    if (!root)
        return false;
    
    Stack S;
    init_stack(&S);

    BiTree CurrNode = root;
    // 经典的先序遍历，几乎是模板了
    while (!is_empty(&S) || !CurrNode) {
        if (CurrNode) {
            visit_node(CurrNode);
            push(&S, CurrNode);
            CurrNode = CurrNode->left;
        } else {
            pop(&S, &CurrNode);
            CurrNode = CurrNode->right;
        }
    }
}

特地赠送中序遍历和后序遍历大礼包！
中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void in_order(BiTree root) {
    if (!root)
        return;

    Stack S;
    init_stack(&S);

    BiTree CurrNode = root;

    while (!is_empty(&S) || CurrNode) {
        if (CurrNode) {
            push(&S, CurrNode);
            CurrNode = CurrNode->left;
        } else {
            pop(&S, &CurrNode);
            visit_node(CurrNode);
            CurrNode = CurrNode->right;
        }
    }
}

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void post_order(BiTree root) {
    if (!root)
        return;

    Stack S1, S2;
    init_stack(&S1);
    init_stack(&S2);

    BiTree CurrNode = root;
    push(&S1, CurrNode);

    while (!is_empty(&S1)) {
        pop(&S1, &CurrNode);
        push(&S2, CurrNode);

        if (CurrNode->left)
            push(&S1, CurrNode->left);
        if (CurrNode->right)
            push(&S1, CurrNode->right);
    }

    while (!is_empty(&S2)) {
        pop(&S2, &CurrNode);
        visit_node(CurrNode);
    }
}

邻接矩阵

题干

试在邻接矩阵存储结构上实现图的基本操作matrix_insert_vertex和 matrix_insert_arc，相关定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef int VertexType;

typedef enum{
DG, UDG
}GraphType;

typedef struct{
VertexType vertex[MAX_VERTEX_NUM]; //顶点向量
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
int vexnum, arcnum;   //图的当前顶点数和弧数
GraphType type;     //图的种类标志
}MatrixGraph;

int matrix_locate_vertex(MatrixGraph *MG, VertexType vex); //返回顶点 v 在vertex数组中的下标，如果v不存在，返回-1
bool matrix_insert_vertex(MatrixGraph *G, VertexType v);
bool matrix_insert_arc(MatrixGraph *G, VertexType v, VertexType w);

当成功插入顶点或边时，函数返回true，否则（如顶点或边已存在、插入边时顶点v或w不存在）返回false。

请在下方编写代码

1
2
3
4
5
6
7
bool matrix_insert_vertex(MatrixGraph *G, VertexType v){

}

bool matrix_insert_arc(MatrixGraph *G, VertexType v, VertexType w){
  
}

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
bool matrix_insert_vertex(MatrixGraph *G, VertexType v){
    if (G == NULL)
        return false;
    if (G->vexnum >= MAX_VERTEX_NUM || matrix_locate_vertex(G, v) != -1)
        return false;
    
    G->vertex[G->vexnum] = v;
    for (int i = 0; i <= G->vexnum; i++) {
        G->arcs[G->vexnum][i] = 0;
        G->arcs[i][G->vexnum] = 0;
    }
    G->vexnum++;

    return true;
}

//其实这里的题解可以优化，部分条件判断是冗余的
//不妨思考一下怎么优化
bool matrix_insert_arc(MatrixGraph *G, VertexType v, VertexType w){
    if (G == NULL)
        return false;
    
    int v_index = matrix_locate_vertex(G, v);
    int w_index = matrix_locate_vertex(G, w);

    if (v_index == -1 || w_index == -1)
        return false;

    if (G->type == DG) {
        if (G->arcs[v_index][w_index] != 0)
            return false;
        
        G->arcs[v_index][w_index] = 1;
        G->arcnum++;
    }
    else {
        if (G->arcs[v_index][w_index] != 0 || G->arcs[w_index][v_index] != 0)
            return false;

        G->arcs[v_index][w_index] = 1;
        G->arcs[w_index][v_index] = 1;
        G->arcnum++;
    }
    
    return true;
}

顺序表

题干

顺序表相关定义及辅助函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 宏定义
#define MAXSIZE 100
#define OK 1
#define ERROR 0

typedef struct{
  int elem[MAXSIZE];
  int last;
}SeqList;

// 根据格式控制符号串format输出一个整数num，格式控制符号串与printf兼容
void print_num(char* format, int num);

// 根据格式控制符号串format读入一个整数num，格式控制符号串与scanf兼容
void read_num(char* format, int* pnum);

请按要求实现非递减顺序表合并的相关函数

1
2
3
4
5
// 函数声明
void initList(SeqList *L);
void printList(SeqList *L);
void inputData(SeqList *L);
void merge(SeqList *LA, SeqList *LB, SeqList *LC);

其中，

  • initList函数初始化 L 的 last 域为 -1；
  • printList函数调用print_num实现在屏幕上显示顺序表L的元素值；
  • inputData函数调用read_num实现顺序表L的初始化，当读到的数为负数时停止读取数据；
    （要求：printList必须调用print_num函数，inputData必须调用调用read_num，否则检查不通过）；
  • merge函数合并非递减顺序表LA和LB，结果放入非递减顺序表LC中，示例如下：
1
2
3
La=(1 3 5 7 9 11 )
Lb=(2 4 6 8 10 )
Lc(La+Lb)=(1 2 3 4 5 6 7 8 9 10 11 )

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
void initList(SeqList *L) {
    L->last = -1;
}



void printList(SeqList *L) {
    if (L == NULL)
        return;

    for (int i = 0; i <= L->last; i++) {
        print_num("%d", L->elem[i]);
    }
}


void inputData(SeqList *L) {
    if (!L)
        return;

    int CurrInputNum;
    read_num("%d", &CurrInputNum);
    while (CurrInputNum >= 0) {
        L->elem[++L->last] = CurrInputNum;
        read_num("%d", &CurrInputNum);
    }
}

void merge(SeqList *LA, SeqList *LB, SeqList *LC) {
    if (LA == NULL || LA->last == -1) {
        LC = LB;
        return;
    }

    if (LB == NULL || LB->last == -1 ) {
        LC = LA;
        return;
    }

    int AIndex = 0;
    int BIndex = 0;
    int CIndex = 0;

    while (AIndex <= LA->last && BIndex <= LB->last) {
        if (LA->elem[AIndex] <= LB->elem[BIndex]) {
            LC->elem[CIndex] = LA->elem[AIndex];
            AIndex++;
            CIndex++;
        }
        else {
            LC->elem[CIndex] = LB->elem[BIndex];
            CIndex++;
            BIndex++;
        }
    }

    if (AIndex <= LA->last) {
        while (AIndex <= LA->last) {
            LC->elem[CIndex] = LA->elem[AIndex];
            CIndex++;
            AIndex++;
        }
    }

    if (BIndex < LB->last) {
        while (BIndex <= LB->last) {
            LC->elem[CIndex] = LB->elem[BIndex];
            CIndex++;
            BIndex++;
        }
    }

    LC->last = CIndex - 1;
}

树的层序遍历

题干

已知树的定义如下：

1
2
3
4
typedef struct node{
  int data;
  struct node *left, *right;
}node, *tree;

实现函数:

1
void check_tree_level_visit(int keys[], int n);
  • 根据 keys 中输入的顺序，生成一棵二叉排序树。
  • 再按层次遍历方式访问，将访问所得的关键字按顺序保存至keys数组中。
  • n 为 keys 数组的长度（1 ≤ n ≤ 100）。
  • 可以有辅助函数。

样例输入：[36,53,28,68,9,33]
样例输出：[36,28,53,9,33,68]

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
node* CreateNode(int data) {
    node* New = (tree)malloc(sizeof(node));
    if (!New)
        return NULL;
    New->data = data;
    New->left = New->right = NULL;

    return New;
}

void InsertBST(tree* root, int data) {
    if (!root) {
        *root = CreateNode(data);
    }
    else {
        if ((*root)->data < data) {
            InsertBST(&(*root)->right, data);
        }
        else {
            InsertBST(&(*root)->left, data);
        }
    }
}

void LevelOrder(tree T, int keys[], int* index) {
    if (T == NULL)
        return;
    
    tree queue[1000];
    int Front = 0,
    Rear = 0;

    queue[Rear++] = T;

    while (Front < Rear) {
        tree Curr = queue[Front++];

        keys[*index++] = Curr->data;

        if (Curr->left != NULL)
            queue[Rear++] = Curr->left;
        
        if (Curr->right != NULL) 
            queue[Rear++] = Curr->right;
    }
}

void check_tree_level_visit(int keys[], int n) {
    tree T = NULL;

    for (int i = 0; i < n; i++) {
        InsertBST(&T, keys[i]);
    }

    int index = 0;
    LevelOrder(T, keys, &index);
}

线性探测法

题干

线性哈希是一种简单的哈希方法，其中哈希函数为 H(key) = key \mod m，其中 m 是哈希表的长度。当发生冲突时，线性探测法会寻找下一个空闲位置来存储关键字。具体来说，如果位置 H(key) 被占用，则检查 H(key) + 1，然后是 H(key) + 2，依此类推，直到找到一个空位。

函数 void print_hash_array(int arr[],int n); 应该实现以下功能：

  1. 创建一个大小为 13 的哈希表（保证输入数据为13个）。
  2. 遍历给定的关键字数组，对每个关键字应用哈希函数。
  3. 如果哈希位置已被占用，则使用线性探测法找到下一个空闲位置。
  4. 在找到的位置存储关键字。
  5. 打印哈希表的内容，以验证关键字是否正确存储。

样例输入：[1,5,21,26,39,14,15,16,17,18,19,20,111]
样例输出：[26,1,39,14,15,5,16,17,21,18,19,20,111]

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define TABLE_SIZE 13
void print_hash_array(int arr[],int n) {
    int HashTable[TABLE_SIZE];

    memset(HashTable, -1, sizeof(HashTable));

    for (int i = 0; i < n; i++) {
        int key = arr[i];
        int hash = key % TABLE_SIZE;

        while(HashTable[hash] != -1) {
            hash = (hash + 1) % TABLE_SIZE;
        }

        HashTable[hash] = key;
    }

    for (int i = 0; i < TABLE_SIZE; i++) {
        if (HashTable[i] != -1) {
            printf("%d ", HashTable[i]);
        }
    }
    printf("\n");
}

整数移除

题干

有线性表的存储结构表示如下：

1
2
3
4
5
#define MAXLEN 128
typedef struct {
int elem[MAXLEN]; //存储数据的数组。下标从 0 开始。
unsigned len; //数组中数据的个数
} list;

请设计一个算法，其功能是：
在一个给定的线性表中，移除所有能被指定正整数整除的元素
操作完成后的线性表中保留的元素呈连续存储的状态
算法函数原型:
void remove_elem(list \*L, unsigned f);
功能：在线性表 L 中移除所有能被 f 整除的元素。
参数：
L：指向线性表的指针。线性表可能为空。
f：整除因子。测试用例保证 f 不小于 2。 返回值：无

编码约束
时间复杂度：O(L->len)
空间复杂度：O(1)

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void remove_elem(list *L, unsigned f) {
    if (!L)
        return;
    
    int SearchIndex = 0;
    int NewIndex = 0;

    while (SearchIndex < L->len) {
        if (L->elem[SearchIndex] % f != 0) {
            L->elem[NewIndex] = L->elem[SearchIndex];
            NewIndex++; 
        }
        SearchIndex++;
    }

    L->len = NewIndex;
}

共享结点

题干

有单链表表示的线性表结构定义如下：

1
2
3
4
5
6
7
8
9
10
11
//定义节点类型
typedef struct _node {
    int data;           //数据域
    struct _node *next; //指针域
} node;

//定义单链表类型
typedef struct {
    node *head;      //头指针
    unsigned len;    //链表中的节点数量
} list;

现已知有两个上述类型的线性表 La 和 Lb，二者在某个结点处融合在一起。请设计一个算法，计算两个链表共享结点的数量。

算法函数原型
int list_shared(list *La, list *Lb);

  • 功能：计算并返回线性表 La 和 Lb 的共享结点的数量
  • 参数：La 和 Lb 都是指向线性表的指针
  • 返回值：La 和 Lb 共享结点的数目

编码约束

  • 时间复杂度：O(max(La->len, Lb->len))
  • 空间复杂度：O(1)

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int list_shared(list *La, list *Lb) {
    int count = 0;
    // 任何一个链表为空，不可能有重合结点
    if (La->head == NULL || Lb->head == NULL)
        return count;

    node* PtrA = La->head;
    node* PtrB = Lb->head;
    int Len_A = 0;
    int Len_B = 0;

    // 计算各链表的长度
    while (PtrA != NULL) {
        Len_A++;
        PtrA = PtrA->next;
    }
    while (PtrB != NULL) {
        Len_B++;
        PtrB = PtrB->next;
    }
    // 尾结点不相同，无重复结点
    if (PtrA != PtrB)
        return count;

    // 将两个链表上的结点更新到同一位置处
    // 注意此题只会在链表后部分出现重合结点
    // 且重合结点不会再次分叉
    PtrA = La->head;
    PtrB = Lb->head;
    while (Len_A > Len_B) {
        PtrA = PtrA->next;
        Len_A--;
    }
    while (Len_A < Len_B) {
        PtrB = PtrB->next;
        Len_B--;
    }

    // 继续共同向后遍历，两指针一旦相等则说明已达到共同结点
    while (PtrA != PtrB && PtrA && PtrB) {
        PtrA = PtrA->next;
        PtrB = PtrB->next;
    }

    // 开始数重合结点
    while (PtrA) {
        PtrA = PtrA->next;
        count++;
    }
    
    return count;
}

反转字符串

题干

有一个递归函数如下：

1
2
3
4
5
6
7
8
void reverse() {
char c = getchar();
if (c == '.') return;

    reverse();
    putchar(c);

}

其功能是将输入的字符序列（以’.’结尾）倒序输出（不包括’.’）。例如：
输入：abc123.
输出：321cba

另有可用的栈接口函数如下：

1
2
3
void push(stack *S, char x); //将字符 x 压入栈 S。S 是指向栈的指针
char pop(stack *S); //弹栈，返回 S 栈顶数据
bool empty(stack * S); //测试栈 S 是否为空。如果为空，返回 true，否则返回

请设计一个算法，利用栈，消除 reverse()中的递归，但功能不变。

算法函数原型：
void reverse(stack *S);
功能：将输入的字符序列倒序输出。输入以’.’结尾。
参数：S 是指向栈的指针。栈 S 已经初始化。
返回值：无

编码约束:
时间复杂度：无特别要求
空间复杂度：O(1)（不计栈空间）
提示：常量空间复杂度意味着，除了使用栈和单个变量，你不能定义类似于数组这样的辅助存储。

题解

1
2
3
4
5
6
7
8
9
10
11
12
void reverse(stack *S) {
    char c = getchar();
    while (c != '.') {
        push(S, c)
        c = getchar();
    }

    while (!empty(S)) {
        c = pop(S);
        putchar(c);
    }
}

镜像二叉树

题干

设有两棵二叉树t1和t2。如果t2是t1左右翻转得到，那么称二叉树t1和t2互为镜像。
图像链接
二叉树的存储结构如下：

1
2
3
4
typedef struct _btree_node {
char tag; //二叉树结点的字符标签
struct _btree_node *left, *right; //左子树和右子树
} btree_node, *btree;

请设计一个算法，实现一棵二叉树的镜像翻转。

算法函数原型
btree mirror(btree tree);
功能：生成二叉树tree的镜像二叉树，返回镜像二叉树的根结点指针。
参数：tree是指向源二叉树根结点的指针
返回值：指向二叉树tree的镜像二叉树根结点的指针

编码约束
时间复杂度和空间复杂度均无要求

题解

1
2
3
4
5
6
7
8
btree mirror(btree tree) {
  if (!tree) return NULL;
  btree t = (btree) malloc(sizeof(btree_node));
  t->tag = tree->tag;                 // 复制tag
  t->left = mirror(tree->right); // 交换左右子树
  t->right = mirror(tree->left);
  return t;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。