2023数据结构期中测验-2023秋-计算机+未来网络专业

数据结构期中测验

  • 选择题
  • 函数题
    • 6-1 求链式表的表长
    • 6-2 逆序数据建立链表
    • 6-3 删除单链表偶数节点
    • 6-4 求二叉树高度
    • 6-5 先序输出叶结点

为了防止不自觉的朝答案看去，特意用了明黄色字体，如下查看答案：

在这里插入图片描述

选择题

2-1
下述程序段的时间复杂度为（ ）

for（i=0; i<n-1; i++）
    for（j=0; j<n-1-i; j++）
        t=a[j], a[j]=a[j+1], a[j+1]=t;

A.O(1)
B.O(n)
C.O(n2)
D.O(n3 )、

答案：C。
显然，循环执行的次数是（n-1) +(n-2) + ··· +1， O(n2)

2-2
下列对顺序存储的有序表（长度为 n）实现给定操作的算法中，平均时间复杂度为 O(1) 的是：
A.查找包含指定值元素的算法
B.插入包含指定值元素的算法
C.删除第 i（1≤i≤n）个元素的算法
D.获取第 i（1≤i≤n）个元素的算法

答案：D
顺序表获可以通过访问下标取第 i个元素，时间复杂度 O(1)

2-3
将线性表La和Lb头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小。应该使用哪种结构？
A.单链表
B.单循环链表
C.带尾指针的单循环链表
D.带头结点的双循环链表
答案：C
线性表La和Lb头尾连接，要先找La的尾和Lb的头。对于带尾指针的单循环链表，尾结点的next即为头结点；而带头结点的双循环链表虽然也可以通过头结点的prev找到尾结点，题目要求占用辅助空间尽量小，选C

2-4
已知头指针 h 指向一个带头结点的非空单循环链表，结点结构为 data | next，其中 next 是指向直接后继结点的指针，p 是尾指针，q 是临时指针。现要删除该链表的第一个元素，正确的语句序列是：

A.h->next=h->next->next; q=h->next; free(q);
B.q=h->next; h->next=h->next->next; free(q);
C.q=h->next; h->next=q->next; if (p!=q) p=h; free(q);
D.q=h->next; h->next=q->next; if (p==q) p=h; free(q);

答案：D

2-5
假设有5个整数以1、2、3、4、5的顺序被压入堆栈，且出栈顺序为3、5、4、2、1，那么为了获得这样的输出，堆栈大小至少为：
A.2
B.3
C.4
D.5

答案：C

2-6
有六个元素以6、5、4、3、2、1的顺序进栈，问哪个不是合法的出栈序列？
A.2 3 4 1 5 6
B.3 4 6 5 2 1
C.5 4 3 6 1 2
D.4 5 3 1 2 6
答案：B

2-7
若栈采用顺序存储方式存储，现两栈共享空间V[m]：top[i]代表第i（i=1或2）个栈的栈顶；栈1的底在V[0]，栈2的底在V[m-1]，则栈满的条件是：
A.|top[2]-top[1]|==0
B.top[1]+top[2]==m

C.top[1] == top[2]
D.top[1]+1==top[2]
答案：D
栈满的条件是两个栈的栈顶指针相遇。因为在顺序存储结构中，当两个栈的栈顶指针相邻时，表示两个栈的空间已经满

2-8
循环队列的队满条件为 ( )
A.(sq.rear+1) % maxsize ==(sq.front+1) % maxsize
B.(sq.front+1) % maxsize ==sq.rear
C.(sq.rear+1) % maxsize ==sq.front
D.sq.rear ==sq.front

答案：C

2-9
表达式a*(b+c)-d的后缀表达式是：
A.a b c + * d -
B. a b c d * + -
C.a b c * + d -
D.- + * a b c d

答案：A
根据选项的后缀表达式还原即可，A是a(b+c)-d；B是a-(b+cd)；C是a+bc-d；D纯扯淡，一眼顶真是前缀*

2-10
数组A[1…5,1…6]每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为：
A.1120
B.1125
C.1140
D.1145
答案：C
如图，自己算
在这里插入图片描述

2-11
二叉树中第5层（根的层号为1）上的结点个数最多为：
A.8
B.15
C.16
D.32
答案：C
二叉树中第n层结点数最多为2n-1

2-12
一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）个。
A.15
B.16
C.17
D.47
答案：B
对于n个结点的二叉树，n = n0+n1+n2; n0 = n2 + 1，带入求解即可

2-13
以二叉链表作为二叉树的存储结构，在具有 n 个结点的二叉链表中（n>0），空链域的个数为 __
A.n+1
B.n
C.n−1
D.无法确定
答案：A
有n个结点，说明有2n个指针域，又因为n个结点的二叉树有n-1条边，那么空指针域就有2n-(n-1)=n+1

2-14
如果二叉树的后序遍历结果是FDEBGCA，中序遍历结果是FDBEACG，那么该二叉树的前序遍历结果是什么？
A.ABCDEFG
B.ABDFEGC
C.ABDFECG
D.ABDEFCG
答案：C

2-15
设每个d叉树的结点有d个指针指向子树，有n个结点的d叉树有多少空链域？
A.nd
B.n(d−1)
C.n(d−1)+1
D.以上都不是
答案：C
跟2-13一模一样

2-16
已知一棵二叉树的树形如下图所示，其后序序列为{ e, a, c, b, d, g, f }。树中与结点a同层的结点是：
在这里插入图片描述

A.c
B.d
C.f
D.g

答案：B
在这里插入图片描述

2-17
下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是：

A. 在这里插入图片描述

B. 在这里插入图片描述

C. 在这里插入图片描述

D. 在这里插入图片描述
答案：B
因为是后序线索树，选项中树的后序遍历为dbca，因此d的前驱为NULL，排除CD；后继为b，排除A

2-18
具有65个结点的完全二叉树其深度为（根的深度为1）：
A.8
B.7
C.6
D.5
答案：B
具有n个结点的完全二叉树的深度 = ⌊ log2n ⌋ +1

2-19
设一段文本中包含字符{a, b, c, d, e}，其出现频率相应为{3, 2, 5, 1, 1}。则经过哈夫曼编码后，文本所占字节数为：
A.40
B.36
C.25
D.12
答案：C
在这里插入图片描述

2-20
由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为：
A.23
B.37
C.44
D.46
答案：C
同上

函数题

6-1 求链式表的表长

本题要求实现一个函数，求链式表的表长。

函数接口定义：

cint Length( List L );

其中List结构定义如下：

typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode List;

L是给定单链表，函数Length要返回链式表的长度。

裁判测试程序样例：

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

typedef int ElementType;
typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode List;

List Read(); /* 细节在此不表 */

int Length( List L );

int main()
{
    List L = Read();
    printf("%d\n", Length(L));
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：
1 3 4 5 2 -1
输出样例：
5

解：

int Length( List L )
{
    int ret = 0;
    while(L)
    {
        ret++;
        L = L->Next;
    }
    return ret;
}

6-2 逆序数据建立链表

本题要求实现一个函数，按输入数据的逆序建立一个链表。

函数接口定义：

cstruct ListNode *createlist();

函数createlist利用scanf从输入中获取一系列正整数，当读到−1时表示输入结束。按输入数据的逆序建立一个链表，并返回链表头指针。链表节点结构定义如下：

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

裁判测试程序样例：

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

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

struct ListNode *createlist();

int main()
{
    struct ListNode *p, *head = NULL;

    head = createlist();
    for ( p = head; p != NULL; p = p->next )
        printf("%d ", p->data);
    printf("\n");

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：
1 2 3 4 5 6 7 -1
输出样例：
7 6 5 4 3 2 1
解：

struct ListNode* createlist()
{
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = head;
    cur->next = NULL;
    int tmp = 0;
    scanf("%d",&tmp);
    while(tmp != -1)
    {
        cur->data = tmp;
        scanf("%d",&tmp);
        struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
        tmp->next = cur;
        cur = tmp;
        
    }
    return cur->next;
    
}

6-3 删除单链表偶数节点

本题要求实现两个函数，分别将读入的数据存储为单链表、将链表中偶数值的结点删除。链表结点定义如下：

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

函数接口定义：

struct ListNode *createlist();
struct ListNode *deleteeven( struct ListNode *head );

函数createlist从标准输入读入一系列正整数，按照读入顺序建立单链表。当读到−1时表示输入结束，函数应返回指向单链表头结点的指针。

函数deleteeven将单链表head中偶数值的结点删除，返回结果链表的头指针。

裁判测试程序样例：

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

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

struct ListNode *createlist();
struct ListNode *deleteeven( struct ListNode *head );
void printlist( struct ListNode *head )
{
     struct ListNode *p = head;
     while (p) {
           printf("%d ", p->data);
           p = p->next;
     }
     printf("\n");
}

int main()
{
    struct ListNode *head;

    head = createlist();
    head = deleteeven(head);
    printlist(head);

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：
1 2 2 3 4 5 6 7 -1
输出样例：
1 3 5 7
解：

struct ListNode *createlist()
{
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = head;
    cur->data = -1;
    cur->next = NULL;
    int tmp = 0;
    while ( tmp != -1)
    {
        scanf("%d", &tmp);
        if(tmp != -1)
        {
        struct ListNode* ts = (struct ListNode*)malloc(sizeof(struct ListNode));
        cur->next = ts;
        ts->data = tmp;
        ts->next = NULL;
        cur = ts;
        }
    }
    return head->next;
}

struct ListNode *deleteeven( struct ListNode *head )
{
    if(head->next == NULL)
    {
        if(head->data%2 == 0)
            return NULL;
        else
            return head;
    }
    struct ListNode *ret = head;
    while(ret->data%2 == 0)
    {
        struct ListNode* del = ret;
        ret = ret->next;
        free(del);
        if(ret->next == NULL)
        {
            if(ret->data%2 == 0)
                return NULL;
            else
                return ret;
        }
    }
        
    struct ListNode * cur = ret;
    while(cur->next)
    {
        if(cur->next->data%2 == 0)
        {
            struct ListNode* del = cur->next;
            cur->next = cur->next->next;
            free(del);
        }
        else
            cur = cur->next;
    }
    return ret;
}

6-4 求二叉树高度

本题要求给定二叉树的高度。

函数接口定义：

int GetHeight( BinTree BT );

其中BinTree结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

要求函数返回给定二叉树BT的高度值。

裁判测试程序样例：

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

typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

BinTree CreatBinTree(); /* 实现细节忽略 */
int GetHeight( BinTree BT );

int main()
{
    BinTree BT = CreatBinTree();
    printf("%d\n", GetHeight(BT));
    return 0;
}
/* 你的代码将被嵌在这里 */

输出样例（对于图中给出的树）：
在这里插入图片描述
4
解：

int max(int a,int b)
{
    return a>b?a:b;
}
int GetHeight( BinTree BT )
{
    if(BT == NULL)
        return 0;
    return max(GetHeight(BT->Left),GetHeight(BT->Right))+1;
}

6-5 先序输出叶结点

本题要求按照先序遍历的顺序输出给定二叉树的叶结点。

函数接口定义：

void PreorderPrintLeaves( BinTree BT );

其中BinTree结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

函数PreorderPrintLeaves应按照先序遍历的顺序输出给定二叉树BT的叶结点，格式为一个空格跟着一个字符。

裁判测试程序样例：

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

typedef char ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

BinTree CreatBinTree(); /* 实现细节忽略 */
void PreorderPrintLeaves( BinTree BT );

int main()
{
    BinTree BT = CreatBinTree();
    printf("Leaf nodes are:");
    PreorderPrintLeaves(BT);
    printf("\n");

    return 0;
}
/* 你的代码将被嵌在这里 */

输出样例（对于图中给出的树）：

在这里插入图片描述
Leaf nodes are: D E H I
解：

void PreorderPrintLeaves( BinTree BT )
{
    if(BT == NULL)
        return;
    if(BT->Left == NULL && BT->Right == NULL)
    {
        printf(" %c",BT->Data);
        return;
    }
        
    PreorderPrintLeaves(BT->Left);
    PreorderPrintLeaves(BT->Right);
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/139363.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

独立站商品信息是怎么获取的呢

独立站商品信息是怎么获取的呢

独立站商品信息的获取主要通过以下几种方式&#xff1a; 人工收集&#xff1a;卖家可以通过在各个电商平台、网站等渠道进行手动搜索和收集商品信息&#xff0c;包括商品名称、价格、描述、图片等&#xff0c;然后将其导入到自己的独立站中。使用采集工具&#xff1a;目前市面…
阅读更多...
暖手宝上架亚马逊美国站UL499报告测试标准要求

暖手宝上架亚马逊美国站UL499报告测试标准要求

暖手宝是运用物理及化学原理研制的自动取暖保健用品。该产品以其自动生热&#xff0c;有趣&#xff0c;实用等新颖独特的优势&#xff0c;深受欢迎——暖手宝具有自动取暖&#xff0c;理疗保健等多种功能。只要插上电源等上10分钟左右就能发热&#xff0c;最后一种是通过锂电池…
阅读更多...
arcgis--消除坐标系信息的两种方法

arcgis--消除坐标系信息的两种方法

方法一&#xff1a;在【目录】中右击待修改数据&#xff0c;选择【属性】&#xff0c;选择【XY坐标】选项卡&#xff0c;点击清楚按钮。 方法二&#xff1a;在【数据管理工具】-【投影与变换】-【定义投影】中清楚坐标系信息。如下&#xff1a;
阅读更多...
如何用Python实现图像拼接画（把一堆小图拼成大图）

如何用Python实现图像拼接画（把一堆小图拼成大图）

诸神缄默不语-个人CSDN博文目录 在这里的图像拼接画指的是一张大图由很多小图组成&#xff0c;效果就像这样&#xff1a; 原理&#xff1a;将大图拆成很多小块&#xff0c;每一块计算平均颜色&#xff0c;用平均颜色最相近的小图来替代&#xff0c;就可以。 直接遍历就可以&…
阅读更多...
FFmpeg开发简介1

FFmpeg开发简介1

适逢FFmpeg6.1发布&#xff0c;准备深入学习下FFmpeg&#xff0c;将会写下系列学习记录。 在此列出主要学习资料&#xff0c;后续再不列&#xff0c;感谢这些大神的探路和分享&#xff0c;特别是雷神&#xff0c;致敬&#xff01; 《FFmpeg从入门到精通》 《深入理解FFmpeg》 …
阅读更多...
使用Nginx和uwsgi在自己的服务器上部署python的flask项目

使用Nginx和uwsgi在自己的服务器上部署python的flask项目

Nginx 是一个高性能的 HTTP 和反向代理服务。其特点是占有内存少&#xff0c;并发能力强&#xff0c;事实上nginx的并发能力在同类型的网页服务器中表现较好。 Nginx 专为性能优化而开发&#xff0c;性能是其最重要的考量指标&#xff0c;实现上非常注重效率&#xff0c;能经受…
阅读更多...
Structure-Inferred Bi-level Model for Underwater Image Enhancement论文小结

Structure-Inferred Bi-level Model for Underwater Image Enhancement论文小结

背景 随着水下机器人的发展&#xff0c;水下图像增强引起了计算机视觉界越来越多的关注。然而&#xff0c;由于光线在水中传播时会被散射和吸收&#xff0c;水下捕捉到的图像往往存在偏色和能见度低的问题。现有的方法依赖于特定的先验知识和训练数据&#xff0c;在缺乏结构信…
阅读更多...
无人地磅称重系统|自助过磅 料仓联动 自助卸料

无人地磅称重系统|自助过磅 料仓联动 自助卸料

上海思伟无人地磅系统 自助过磅、 自助卸料 、料仓联动 智能、省人、安全 无人监管过磅 对地磅及其相关的所有硬件进行配置和管理&#xff1b; 支持红外、道闸、车牌识别、AI分析、拍照存档、LED语音播报一体机等设备&#xff1b; 实现稳定可靠的无人监管称重功能&#xf…
阅读更多...
安防监控系统EasyCVR v3.4.0版本首页界面更新调整功能大汇总

安防监控系统EasyCVR v3.4.0版本首页界面更新调整功能大汇总

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。平台可拓展性强、…
阅读更多...
C# 智慧医学实验室LIS系统源码，支持预制条码和即时打印条码；支持单工/双工数据采集；支持TAT监测与分析；具备检验智能审核功能，支持自定义多级审核规则

C# 智慧医学实验室LIS系统源码，支持预制条码和即时打印条码；支持单工/双工数据采集；支持TAT监测与分析；具备检验智能审核功能，支持自定义多级审核规则

C#医院检验信息管理系统源码&#xff0c;智慧医学实验室LIS系统源码&#xff0c;云LIS系统源码 医院检验信息管理系统&#xff0c;利用计算机网络技术、数据存储技术、快速处理技术&#xff0c;对检验科进行全方位信息化管理&#xff0c;使检验科达到自动化运行&#xff0c;信息…
阅读更多...
vscode使用flake8设置单行最长字符限制设置失败的问题

vscode使用flake8设置单行最长字符限制设置失败的问题

vscode使用flake8设置单行最长字符限制设置失败的问题 问题描述解决方案 问题描述 如图所示&#xff0c;使用flake8单行字数过长&#xff0c;就会有有红色底的波浪线 一般情况下很多教程都会让你在setting.json里面设置 但是我打开我的setting.json&#xff0c;发现我已经进…
阅读更多...
体验家XMPlus收购NPSMeter，稳固体验管理行业“领头羊”地位

体验家XMPlus收购NPSMeter，稳固体验管理行业“领头羊”地位

2023年9月30日&#xff0c;体验家XMPlus&#xff08;以下简称“体验家”&#xff09;成功完成了对NPSMeter的收购。此次收购是中国客户体验管理&#xff08;CEM&#xff09;赛道进入快速发展以来的首单收购&#xff0c;标志着体验家在CEM领域的进一步扩张&#xff0c;旨在继续完…
阅读更多...
智慧工地管理云平台源码，Spring Cloud +Vue+UniApp

智慧工地管理云平台源码，Spring Cloud +Vue+UniApp

智慧工地源码 智慧工地云平台源码 智慧建筑源码支持私有化部署&#xff0c;提供SaaS硬件设备运维全套服务。 互联网建筑工地&#xff0c;是将互联网的理念和技术引入建筑工地&#xff0c;从施工现场源头抓起&#xff0c;最大程度的收集人员、安全、环境、材料等关键业务数据&am…
阅读更多...
【教3妹学编程-算法题】给小朋友们分糖果 II

【教3妹学编程-算法题】给小朋友们分糖果 II

3妹&#xff1a;1 8得8&#xff0c;2 816&#xff0c; 3 8妇女节… 2哥 : 3妹&#xff0c;在干嘛呢 3妹&#xff1a;双11不是过了嘛&#xff0c; 我看看我这个双十一买了多少钱&#xff0c; 省了多少钱。 2哥 : 我可是一分钱没买。 3妹&#xff1a;我买了不少东西&#xff0c; …
阅读更多...
天津火爆python培训机构从哪里入手？

天津火爆python培训机构从哪里入手？

Python不仅被应用在职场办公中&#xff0c;还被大型互联网公司应用于大型后端开发&#xff0c;随着大数据领域的高速发展&#xff0c;这门高效的编程语言逐渐成为处理数据的最佳编程语言之一。 Python培训班优势 系统性学习&#xff1a;Python培训班会提供结构化的课程体系&a…
阅读更多...
期中之后老师的福音

期中之后老师的福音

老师在期中考试后总是会有一大堆事情要做&#xff0c;批改试卷、统计分数、通知学生成绩等等。今天我就要给大家介绍一个能够减轻老师工作负担、提高工作效率的方法——查询系统 简单来说&#xff0c;成绩查询系统就是能够让学生方便的查询成绩&#xff0c;让老师快捷发布成绩的…
阅读更多...
腾讯云优惠券如何领取？腾讯云服务器怎么买便宜？

腾讯云优惠券如何领取？腾讯云服务器怎么买便宜？

腾讯云深知用户对价格的重视&#xff0c;因此在每年的618、双11、双12等大型促销活动中推出了大量优惠活动。这些优惠活动包括打折、满减、买赠等形式&#xff0c;让用户在购买腾讯云主机服务器时能够享受到更多的实惠。特别是在这些促销活动期间&#xff0c;用户可以通过领取优…
阅读更多...
OpenAI发布会，看看GPT又有哪些大动作！2023.11.7【浓缩精华】

OpenAI发布会，看看GPT又有哪些大动作！2023.11.7【浓缩精华】

ChatGPT GPT-4 Turbo其它applications 北京时间11月7日OpenAI首届开发者大会 GPT-4 Turbo Context length 支持12.8万个上下文contextMore control JSON模式 可复制输出 未来&#xff1a;在API中查看日志Better knowledge 平台启动检索 拥有截至2023年3月的知识New modaliti…
阅读更多...
2023年11月最新视频号下载提取工具？

2023年11月最新视频号下载提取工具？

视频号下载提取器教程&#xff1a; 1. 首先&#xff0c;在微信客户端中搜索并添加"下载小助手儿"并关注获取推送的消息。然后添加视频下载助手为好友&#xff0c;可以帮助你解析视频号链接。 2. 打开微信&#xff0c;并找到你想要提取链接的视频号。进入该视频页面后…
阅读更多...
终端训练模型日志重定向

终端训练模型日志重定向

在终端中要执行模型的训练时&#xff0c;我们有时候既需要把模型执行的日志输出到终端展示&#xff0c;又想把训练日志保存到日志文件中: 假设执行的代码时trian.py python -u train.py | tee -a ./train.log-u&#xff1a;这是 Python 解释器的一个选项&#xff0c;用于强制标…
阅读更多...
最新文章

Copyright @ 2022~2023