湖大计学考研系列文章目录

目录

前言

一、选择题（共10个，每个2分）

二、简答题（共4个，共计30分）

三、计算题（共4个，共计50分）

四、程序题（共4个，共计50分）

下载链接

前言

        专业课不像数学与英语一样，有真题，有模拟卷。随着湖大不再公布真题后，真题只有回忆版，回忆版也只能看出知识点，但并不能当做模拟考试。而网上其他的数据结构的试卷有三个问题，第一，题型上并不能与866数据结构相匹配。第二，考察的重点和分值也不匹配。第三，很多试卷并没有答案，或者答案并不清楚。因此，大多数人（比如我）参加最后初试时候并没有做过任何训练，并不清楚时间分配等等考场问题。基于此，加上我对866数据结构的理解，参考了王道，湖大本科题库，湖大期末题，给出了一份完全与866数据结构相匹配的试卷，在分值，重点，题型都与22年的考研试卷一模一样。这份试卷可以完全当成考试用，帮助你感受考场氛围及把握考场时间，希望能对你们有帮助。本着开源思想，这份试卷及答案的免费下载链接在本文的最后。

一、选择题（共10个，每个2分）

1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（      ）。

x = 2;
while (x < n / 2){
    x = 2 * x; 
}

 A. O(logn)                  B .O(n)                        C .O(nlogn )                           D .O(n^{2})

  • 答案：A
  • 考察知识点：时间复杂度计算
  • 解析：设循环次数为T(n)，当T(n) = 1时，x=4，T(n) = 2时，x=8，.......，可以得出x=2^{T(n)+1}。当x < n/2时，T(n) < log_2^n - 1。所以时间复杂度为O(T(n)) = O(logn)
  • PS：时间复杂度866数据结构基本必考，大多数是一个选择+一个简答，所以一定要会。

2.已知指针指向一个带头结点的非空循环单链表，p是尾指针，q是临时指针。现要删除该链表的第一个元素，正确语句序列是（      ）。

A. L->next=L->next->next; q=L->next; free(q);

B. q=L->next; L->next=L->next->next; free(q);

C. q=L->next; L->next=q->next; if (p!=q) p=L; free(q);

D. q=L->next; L->next=q->next; if (p==q) p=L; free(q);

  • 答案：D
  • 考察知识点：链表插入，删除顺序问题
  • 解析：这道题可能会有很多人选B，但没有考虑一种特殊情况，当这个循环单链表只有一个结点的时候，删除之后，需要把尾指针指向头结点。

3.有一个顺序共享栈share[0: n-1]，其中第一个栈顶指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈栈满的条件是（      ）。

A. top2-top1==1              B. top1-top2==1              C. top1==top2                 D. top2-top1==0

  • 答案：A
  • 考察知识点：共享栈

4.设一个栈的输入序列为a，b，c，d，则出栈顺序不可能是（      ）。

A. a, b, c, d                      B. d, c, b, a                      C. a, c, d, b                      D. d, a, b, c

  • 答案：D
  • 考察知识点：出栈顺序问题
  • 解析：出栈顺序的题目有两个顺序一定是可以的，一个就是输入顺序（abcd），另一个是逆置的输入顺序（dcba），而是逆置的顺序是固定的。
  • PS：出栈顺序题目也基本是必考了，选择和大题都会考。

5.已知一棵二叉树的后序序列为DABEC，中序序列为DEBAC，则先序序列为（      ）。

A.  ACBED                   B. DECAB                      C. DEABC                      D. CEDBA

  • 答案：D
  • 考察知识点：二叉树遍历
  • 解析：只需要通过后序+中序将二叉树构造出来，然后写出先序序列就可以。
  • PS：二叉树遍历题目也基本是必考了，选择和大题都会考。

6.用DFS遍历一个无环有向图，并在DFS算法出栈返回时，打印出相应的顶点，则输出的顶点序列是（      ）。

A.  逆拓扑有序的          B. 拓扑有序的               C. 无序的                       D. 无法确定

  • 答案：A
  • 考察知识点：图拓扑排序
  • 解析：DFS会一直往深处找，直到找到出度为0的结点。如果此时出栈返回，则会得到逆拓扑序列。

7.采用邻接表存储的图的深度优先遍历算法类似于二叉树的（      ）算法 。

A.  先序遍历                 B. 中序遍历                   C. 后序遍历                   D. 层次遍历

  • 答案：A
  • 考察知识点：图的DFS与二叉树遍历关系
  • BFS与二叉树遍历又是什么关系呢？

8.已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多的是（      ）。

A.  4                              B.  5                              C.  6                              D.  7

  • 答案：B
  • 考察知识点：折半查找
  • 解析：折半查找在查找不成功时和关键字比较次数最多为树的高度，\left \lceil log_2{(n+1)} \right \rceil

9.用散列查找方法处理冲突会出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是（      ）。

A.  存储效率                 B. 散列函数                   C. 装填因子                   D. 平均查找长度

  • 答案：D
  • 考察知识点：散列查找
  • 解析：产生堆积现象，即产生了冲突，对存储效率，散列函数，装填因子都无影响，但平均查找长度会增大。

10.在以下排序方法中，最耗费内存的是（        ）。

A.  快速排序                 B. 堆排序                       C. 二路归并排序            D. 直接插入排序

  • 答案：C
  • 考察知识点：内部排序算法比较
  • 解析：快速排序空间复杂度为O(logn)，堆排序和直接插入排序为O(1)，二路归并排序为O(n)。

二、简答题（共4个，共计30分）

1.（5分）分析下列程序段的时间复杂度（要求给出具体的分析过程）。

void sort(int j,int n){
    int i,temp;
    if(j<n){
        for(i=j;i<=n;++i)
            if(a[i]<a[j])
                swap(a[i],a[j]);
        ++j;
        sort(j,n);
    }
}
  • 答案： O(n^{2})
  • 考察知识点：时间复杂度计算
  • 解析：sort是一个递归排序过程，这里假设T(n) 是排序n各元素要的时间。纵观代码，主要花费时间在递归调用sort()上。如果第一次调用，处理元素个数n-1，即对剩下n-1个元素进行排序，所需时间就是T(n-1) 。又sort()在for循环中，就需要n-1次比较。
  • 列出方程：

        T(1)=0 ,n=1

        T(n)=T(n-1)+n-1 ,n>1

  • 求解：

        T(n)=[T(n-2)+(n-2)]+(n-1)

​         =[T(n-3)+(n-3)]+(n-2)+(n-1)

        ​ ...

        ​ =(T(1)+1)+2+3+...+n-1

​         =0+1+2+...+n-1

​         =n(n-1)/2

​         =O(n²)

2.（5分）—组记录的关键码为{46, 79, 56, 38, 40, 84}，则利用快速排序的方法，给出第一趟排序的结果。

  • 答案： 40，38，46，56，79，84
  • 考察知识点：快速排序

3.（10分）设输入序列为A,B,C,D,E通过栈操作，在可能的出栈次序中，第一个出栈元素为C且第二个出栈元素为D出栈顺序有哪几个？

  • 答案： CDEBA、CDBEA、CDBAE三种
  • 考察知识点：出栈顺序
  • 解析：CD出栈后，栈中还剩下BA，此时有三种情况。
  1. E进栈后出栈，出栈序列为CDEBA
  2. B出栈，E进栈后出栈，出栈序列为CDBEA
  3. B出栈，A出栈，E进栈后出栈，出栈序列为CDBAE

4.（10分）已知一棵二叉树的后序遍历序列为：HGDBEFCA，中序遍历序列为:：HGDBAECF。请画出该二叉树，并写出其前序遍历序列。

  • 答案： 前序：ABDGHCEF，二叉树如图所示
  • 考察知识点：二叉树遍历顺序
  • 解析：只需要通过后序+中序将二叉树构造出来，然后写出先序序列就可以。

三、计算题（共4个，共计50分）

1.已知有七个顶点（顶点编号1~7）的有向带权图，邻接矩阵如图所示

（1）（5分）请画出该图，并给出从顶点1出发的深度优先遍历序列。

（2）（5分）将该图视为无向图，利用Prim或者Kruskal算法求出最小生成树（需要画出每一步结果）。

（3）（10分）写出该图所有拓扑排序结果。

  • 答案： 

        1. 从1出发的深度优先遍历序列：1,2,3,5,7,4,6

        2. 如图所示

        3. 拓扑排序：1,2,4,6,3,5,7      1,4,2,6,3,5,7        1,4,6,2,3,5,7

  • 考察知识点：图DFS、邻接矩阵、MST、拓扑排序

 

2.已知一个整数序列为91，27，54，13，66，15，48，62，现在要对其进行从大到小排序。

（1） （5分）归并排序算法是稳定的排序算法吗？请对以上数据完成二路归并排序，写出每一趟排序的结果。

（2） （5分）堆排序算法是稳定的排序算法吗？若采用堆排序方法进行排序，请画出初始堆结构和删除序列中最大值之后的堆结构。

  •  答案：

        1. 二路归并排序是稳定排序算法

                第1趟：91,27,54,13,66,15,62,48

                第2题：91,54,27,13,66,62,48,15

                第3趟：91,66,62,54,48,27,15,13

        2. 堆排序不是稳定算法，图1是初始堆结构，图2是删除最大值后堆结构

  • 考察知识点：归并排序、堆排序

 

3.已知一组元素为（37，24，42，7，2，40，42，32，120）

（1）（5分）画出按元素排列次序依次插入生成的一棵二叉搜索树。

（2）（5分）画出在第（1）中生成的二叉搜索树中删除37后的树结构。

  • 答案：（1）如图所示（2）1或者2都可以，画出一种即可。
  • 考察知识点：BST逐步生成及其删除
  • 需要注意的是：怎么处理相同值，866与王道略有偏差，王道给BST定义中就不会有相同值的情况，但在866中，会考察相同值情况。

 

4.使用散列函数H（key）= key%11，把数据（1，13，12，34，38，33，27，22）依次插入散列表，使用线性探测法

（1） （5分）画出该散列表，求出在等概率情况下，查找成功的平均查找长度。

（2） （5分）查找关键字22和16，需要依次与哪些关键字进行比较。

  • 答案：

        1. 散列表如图所示，ASL成功 = 21/8

        2. 查找22，需要与33,1,13,12,34,38,27,22比较

            查找16，需要与38,27,22比较

  • 考察知识点：散列查找
  • 解析：

H(1) = 1%11 = 1，关键字1存放在地址1

H(13) = 13%11 = 2，关键字13存放在地址2

H(12) = 12%11 = 1，发生冲突，H1=2，发生冲突，H2=3，关键字12存放在地址3

H(34) = 34%11 = 1，发生冲突，H1=2，发生冲突，H2=3，发生冲突，H3=4，关键字34存放在地址4

H(38) = 38%11 = 5，关键字38存放在地址5

H(33) = 33%11 = 0，关键字33存放在地址0

H(27) = 27%11 = 5，发生冲突，H1=6，关键字27存放在地址6

H(22) = 22%11 = 0，发生冲突，H1=1，....... H7=7，关键,22存放在地址7

ASL=（1+1+1+3+4+1+2+8）/ 8 = 21/8

四、程序题（共4个，共计50分）

1.（10分）设将n （n > 1）个整数存放到一个单链表L中，设计一个在时间和空间两方面尽可能高效的算法：将L中的顺数第K个节点的值与倒数第K个节点的值进行交换（K < n/2），要求:

（1） 写出算法伪代码，关键之处给出注释。

（2） 给出算法时间度和空间复杂度分析。

时间复杂度：O(n)、空间复杂度：O(1)

解析：此题来自21湖大本科期末题，和2009年408代码题基本一样，算法设计的基本思想是：定义两个指针p,q，先让p移动，等到p移动到第k个结点的时候，让p,q同时移动，直到p移动到最后，q便移动到倒数第k个。

ListNode* swapNodes(ListNode* head, int k) {
//找到正数第k个节点和第k-1个节点，
//找到倒数第k个节点和倒数第k+1个节点交换，返回头节点
        ListNode* pPK = head;//正数第k节点
        ListNode* pNK = head, * pK = head;//倒数第K个节点,pK为游标
        
        for(int i = 2;i <= k;i++)
        {
            pPK = pPK->next;
            pK = pK->next;
        }
        
        while(pK->next)
        {
            pNK = pNK->next;
            pK = pK->next;
        }
        
        swap(pPK->val,pNK->val);
        
        return head;
    }

2.（10分）假设字符数组A中存储了一个算术表达式，算术表达式中可以包含2种括号：圆括号“(”和“)”，“{”和“}”，且这两种括号可以按照任意的次序嵌套使用，如：()、{() }是括号匹配的，而()}不是括号匹配的。设计一个算法，判断该算术表达式是否括号配对出现。要求:

（1） 写出算法伪代码，关键之处给出注释。

（2） 给出算法时间度和空间复杂度分析。

 时间复杂度：O(n)、空间复杂度：O(n)

解析：此题来自20湖大本科期末题，基本思想：遇到左括号就入栈，遇到右括号就弹出栈顶元素进行匹配，若匹配，则接着扫描，不匹配或者栈空，则匹配失败。扫描结束后，若栈空。则匹配，不空，则说明有多的左括号。

bool MatchBrackets(){
    const int MAZSIZE = 1024; //栈的最大容量
    char s[MAXSIZE]; // 简化栈结构
    int top = 0; // 初始化
    ch = getchar();
    while (ch ！= EOF){
        switch(ch){
        case'(','{':
            s[top++] = ch; // 所有左括号入栈
            break;
        case')':
            if (top == 0 or s[--top]!='(') return false; // 栈空，或者不匹配
        case'}':
            if (top == 0 or s[--top]!='{') return false;
        }
        ch = getchar(); // 获取下一个字符
    }
    if (top == 0) return turn; // 正好匹配
    else return false; // 栈中尚有未匹配的左括号
}

3.（10分）编写一个算法，判断给定的二叉树是否是二叉排序树，要求:

（1） 写出算法伪代码，关键之处给出注释。

（2） 给出算法时间度和空间复杂度分析。

时间复杂度：O(n)、空间复杂度：O(n)

解析：此题来自王道，早年湖大考研真题也考过。基本思想：对于BST来说，中序序列是递增有序的，因此，对给定的二叉树进行中序遍历，若始终能保持前一个值比后一个值小，则说明是BST。

//判断是否为二叉排序树 
KeyType predt=-32769;
bool Judge(BinaryTree* root){
    if(root == NULL){//树为空则为二叉排序树 
        return true;
    }
    bool bst_l,bst_r;
    bst_l = Judge(root->lchild,predt);//判断左子树是否为二叉排序树
    if(!bst_l || predt >= root->data){
        return false;
    }
    predt = root->data;
    bst_r = Judge(root->rchild,MAX);//判断右子树是否为二叉排序树
    return bst_r;
}

 4.（20分）设图G=（V，E），对任一顶点k，称E(k)=max{d(i, k)}（i∈V）为顶点k的偏心度。显然，偏心度最小的顶点即为图G的中心点，求图G的中心点。要求:

（1） 写出算法伪代码，关键之处给出注释。

（2） 给出算法时间度和空间复杂度分析。

时间复杂度：O(n^3)、空间复杂度：O(n^2)

解析：此题是22年866原题，一模一样。代码采用湖大本科图的ADT。

DEFINE maxvalue 99999;
int distance(Graph *G){
    int D[G->n()][G->n()]; // 邻接矩阵
    for (int i = 0; i < G->n(); i++){
        for (int j = 0; j < G->n(); j++){
            D[i][j] = G->weight(i,j);
        }
    }
    
    // Flyod
    for (int k = 0; k < G->n(); k++){
        for (int i = 0; i < G->n(); i++){
            for (int j = 0; j < G->n(); j++){
                if (D[i][j] > D[i][k] + D[k][i]){
                    D[i][j] = D[i][k] + D[k][i];
                }
            }
        }
    }
    
    int min = maxvalue;
    for (int i = 0; i < G->n(); i++){
        int s = 0;
        // 顶点i到其他各个顶点最短路径中最长
        for (int j = 0; j < G->n(); j++){
            if (D[i][j] < maxvalue && D[i][j] > s){
                s = D[i][j];
            }
        if (s < min){
            k = i;
            min = s;
        }
    }
    return k;
}

下载链接

湖南大学866数据结构模拟卷1及答案-算法与数据结构文档类资源-CSDN文库https://download.csdn.net/download/qq_45331246/86731507

# 经验分享 # 数据结构
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

avatar 开放原子开发者工作坊

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

avatar 开放原子开发者工作坊

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

avatar 开放原子开发者工作坊