精华内容
下载资源
问答
  • --排序算法说明-- 1)当插入第i(i≥1)个数据时,假设前面的0到i-1个数据已经排好序 2)用第i个数据与第i-1、i-2, …的数据顺序进行比较(和顺序查找类似),如果小于,则将第x(x)个数据向后移动(插入位置后的记录向...

    部分题目尚未完成,欢迎补充。

    问题 A: 1.疫苗预约(30分)

    时间限制: 1 Sec  内存限制: 128 MB

    题目描述

    疫苗接种时间分为两个时间段(按24小时制):上午9点到12点,下午13点到18点。

    接种者要先申请,提交预约时间和出生年月日,经过检验符合条件后,系统会生成一个预约码,并且把预约码插入到对应时间段的预约表中。检验条件是接种年龄必须在18岁到59岁之间,检验方法是用2021减去出生年份,如果结果是18到59之间,则符合条件。预约码是固定5位整数,首位表示预约时间段,上午用1表示,下午用2表示,第2到4位数用出生月日表示。

    例如某接种者预约15点接种,出生日期是2000年2月5日,经过检验他是21岁符合要求,生成预约码是20205

    如果接种者要撤销申请,只要输入预约时间和预约码,系统就会在相应预约表删除该预约码。无需考虑预约码不存在的情况。

    提示:本题出于简单化考虑,检验方法与实际无关,无需考虑预约时间、出生日期的非法情况、也不必考虑出生日期相同的情况。

     请编写程序实现疫苗接种预约功能,包括

    1)创建两张顺序表,对应两个时间段,每张顺序表保存已有的预约码

    2)如果是预约申请,根据接种者申请信息做检验,并生成预约码;然后实现顺序表的插入操作,在顺序表末尾插入新的预约码

    3)如果是撤销申请,实现顺序表的删除操作,删除指定的预约码,并移动剩余预约码保证顺序表不会出现空洞

    --程序要求--

    1、程序不允许使用第三方对象实现本题的要求,例如禁止使用STL库或容器类对象等

    2、程序必须创建顺序表,并实现顺序表的插入和删除操作

    输入

    前两行输入两个时间段的已有预约码,每行先输入数字n表示预约码数量,后跟n个整数表示预约码,数据之间用单个空格隔开

    接着一行输入m,表示有m个新预约申请

    接着输入m行,每行包含4个参数(正整数),第一个参数是预约时间(例如上午10点、下午14点等),后三个参数表示出生年月日。如果符合检验条件,根据预约时间,把新预约码插入对应顺序表的末尾。如果不符合检验,不执行插入操作,输出提示信息看样例

    接着一行输入n,表示n个撤销申请

    接着输入n行,每行包含2个参数,表示预约时间和预约码

    输出

    如果有不符合条件的申请,输出提示信息,看样例。如果没有不符合条件的则没有相关输出。

    最后输出两行,表示所有操作后两个时间段的预约码

    样例输入

    5 10102 10304 10516 10718 10910
    4 21101 21213 20308 20506
    2
    9 1950 6 6
    15 2000 2 5
    2 15 21101
    11 10516

    样例输出

    invaild application
    10102 10304 10718 10910
    21213 20308 20506 20205
    #include <iostream>
    using namespace std;
     
    class Table
    {
    public:
        Table* next = NULL;
        int Num = 0;
        Table(){}
        Table(int num) { Num = num; }
        void insert(int num)
        {
            Table* temp = this;
            for (;temp->next;)temp = temp->next;
            temp->next = new Table(num);
        }
        void del(int num)
        {
            Table* temp = this;
            for (;temp->next;)
            {
                if (temp->next->Num == num)
                {
                    Table* p = temp->next;
                    temp->next = temp->next->next;
                    delete p;
                    break;
                }
                temp = temp->next;
            }
        }
        void print()
        {
            Table* temp = this;
            for (;temp->next;)
            {
                cout << temp->next->Num << " ";
                temp = temp->next;
            }
            cout << endl;
        }
    };
     
    int main()
    {
        int a, b;
        cin >> a;
        Table* am = new Table();
        Table* pm = new Table();
        Table* temp = NULL;
        temp = am;
        int num = 0;
        for (int i = 0; i < a; i++)
        {
            cin >> num;
            temp->next = new Table(num);
            temp = temp->next;
        }
        cin >> b;
        temp = pm;
        for (int i = 0; i < b; i++)
        {
            cin >> num;
            temp->next = new Table(num);
            temp = temp->next;
        }
        int m;
        cin >> m;
        int time, year, month, day;
        for (int i = 0; i < m; i++)
        {
            cin >> time >> year >> month >> day;
            if (2021 - year < 18 || 2021 - year>59)
            {
                cout << "invaild application" << endl;
                continue;
            }
            if (time <= 12)am->insert(10000 + month * 100 + day);
            else pm->insert(20000 + month * 100 + day);
        }
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> time >> num;
            if (time <= 12)am->del(num);
            else pm->del(num);
        }
        am->print();
        pm->print();
        temp = am;
        for (;temp->next;)
        {
            Table* q;
            q = temp;
            temp = temp->next;
            delete q;
        }
        delete temp;
        temp = pm;
        for (; temp->next;)
        {
            Table* q;
            q = temp;
            temp = temp->next;
            delete q;
        }
        delete temp;
        return 0;
    }

    ---------------------------------------------------------------------------------------------------------------------------------

    问题 B: 2.预约号查找(30分)

    时间限制: 1 Sec  内存限制: 128 MB

    题目描述

    为了方便管理,现采用哈希查找算法实现对预约号序列的快速查找。预约号都是正整数。

    哈希函数为H(key)=key MOD LEN,LEN是哈希表长度,由输入参数确定。解决冲突方法为二次探测再散列,其中冲突偏移距离D取值为 +1, -1, +4, -4, +9, -9,……i的平方, i的平方负值,依次类推。哈希表采用数组存储,不必考虑哈希表溢出的情况。编写程序,把输入的多个预约号存储在哈希表中,并实现哈希查找。

    --程序要求--

    1)不允许使用第三方对象或函数实现本题的要求

    2)必须按照题目要求实现哈希查找,不得使用其他查找方法

    输入

    第一行输入L,表示哈希表长度

    第二行先输入数字n表示预约号数量,后跟n个整数表示预约号

    第三行先输入数字k表示查找数量,后跟k个整数表示要查找的预约号

    输出

    第1行输出构建的哈希表,哈希表中未存储预约号的空白位置用-1表示

    接着输出k行,每行输出查找结果和比较次数。

    如果查找成功,输出该预约号的位置(即数组下标);如果查找失败,输出提示信息,看样例

    提示:如果查找失败,不必把该预约号插入哈希表中。

    样例输入

    11
    9 19 1 23 14 55 68 11 82 36
    3 68 12 23

    样例输出

    55 1 23 14 36 82 68 -1 19 -1 11
    6 4
    search fail
    2 2
    #include <iostream>
    using namespace std;
    class Node
    {
    public:
        int num = -1;
        Node* next = NULL;
        Node* per = NULL;
        Node() {}
    };
    class Root
    {
    public:
        int len;
        Node* root = new Node();
        Root(int len) { this->len = len; build(); }
        void build()
        {
            Node* temp = root;
            for (int i = 1; i < len; i++)
            {
                temp->next = new Node();
                temp->next->per = temp;
                temp = temp->next;
            }
            temp->next = root;
            root->per = temp;
        }
        void insert(int n)
        {
            int flag = n % len;
            Node* temp = root;
            for (int i = 0; i < flag; i++)temp = temp->next;
            flag = 0;
            Node* q = temp;
            for (int i = 0;; i++, flag = i * i)
            {
                for (int j = 0; j < flag; j++) temp = temp->next;
                if (temp->num == -1)
                {
                    temp->num = n;
                    break;
                }
                temp = q;
                for (int j = 0; j < flag; j++)temp = temp->per;
                if (temp->num == -1)
                {
                    temp->num = n;
                    break;
                }
                temp = q;
            }
        }
        void find(int n)
        {
            int time = 1;
            int pos = 0;
            Node* temp = root;
            int flag = n % len;
            for (int i = 0; i < flag; i++) temp = temp->next, pos++;
            int pos_temp = pos;
            if (temp->num == n)
            {
                cout << pos << " " << time << endl;
                return;
            }
            flag = 1;
            Node* q = temp;
            for (int i = 1;; i++, flag = i * i)
            {
                time++;
                for (int j = 0; j < flag; j++)temp = temp->next, pos++;
                if (temp->num == n)
                {
                    for (; pos < 0; pos += len);
                    cout << pos << " " << time << endl;
                    break;
                }
                pos = pos_temp;
                temp = q;
                time++;
                for (int j = 0; j < flag; j++) temp = temp->per, pos--;
                if (temp->num == n)
                {
                    for (; pos < 0; pos += len);
                    cout << pos << " " << time << endl;
                    break;
                }
                temp = q;
                if (flag > len)
                {
                    cout << "search fail" << endl;
                    break;
                }
                pos = pos_temp;
            }
        }
        void print()
        {
            Node* temp = root;
            for (;;)
            {
                cout << temp->num << " ";
                temp = temp->next;
                if (temp == root)
                {
                    cout << endl;
                    break;
                }
            }
        }
        void del()
        {
            Node* temp = root;
            Node* q = temp;
            for (int i=1;i<len;i++)
            {
                q = temp;
                temp = temp->next;
                delete q;
            }
            delete temp;
        }
    };
    int main()
    {
        int L;
        cin >> L;
        Root hash(L);
        int n, num;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> num;
            hash.insert(num);
        }
        hash.print();
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> num;
            hash.find(num);
        }
        hash.del();
        return 0;
    }

    ---------------------------------------------------------------------------------------------------------------------------------

    问题 C: 3.预约号排序(25分)

    时间限制: 1 Sec  内存限制: 128 MB

    题目描述

    为了管理方便,需要对预约号进行排序。现使用顺序表存储预约号,采用直接插入排序法。

    --排序算法说明--

    1)当插入第i(i≥1)个数据时,假设前面的0到i-1个数据已经排好序

    2)用第i个数据与第i-1、i-2, …的数据顺序进行比较(和顺序查找类似),如果小于,则将第x(x<=i-1)个数据向后移动(插入位置后的记录向后顺移)

    3)找到插入位置即将第i个数据插入

    --程序要求--

    1)必须使用直接插入排序法实现本题的要求

    2)不允许使用第三方对象或函数实现本题的要求

    输入

    第一行输入t表示有t个测试实例

    每个实例对应一行输入,先输入数字n表示预约号数量,后跟n个整数预约号,数据之间用单个空格隔开

    输出

    每个测试实例输出3行,对应第1趟、第2趟和最终的排序结果

    每行输出数据之间用单个空格隔开,末尾数据后面无空格

    提示:在第一趟排序时,因为已排序表为空,所以第一个数据直接插入无比较。所以第一趟排序结果就是原始数据序列。

    样例输入

    2
    6 21 25 48 25 16 8
    6 22 14 33 66 55 11

    样例输出

    21 25 48 25 16 8
    21 25 48 25 16 8
    8 16 21 25 25 48
    22 14 33 66 55 11
    14 22 33 66 55 11
    11 14 22 33 55 66
    #include <iostream>
    using namespace std;
     
     
    int main()
    {
        int T;
        cin >> T;
        while (T--)
        {
            int n;
            cin >> n;
            int* a = new int[n];
            int* b = new int[n];
            for (int i = 0; i < n; i++)
                cin >> a[i];
            for (int i=0;i<n;i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (a[i] < a[j])
                    {
                        if (i > j)
                        {
                            int temp = a[i];
                            for (int k = i; k > j; k--)
                                a[k] = a[k - 1];
                            a[j] = temp;
                            break;
                        }
                        else
                        {
                            int temp = a[i];
                            for (int k = i; k < j; k++)
                                a[k] = a[k + 1];
                            a[j - 1] = temp;
                            break;
                        }
                    }
                }
                if (i < 2)
                {
                    for (int k = 0; k < n; k++)
                        cout << a[k] << " ";
                    cout << endl;
                }
            }
            for (int k = 0; k < n; k++)
                cout << a[k] << " ";
            cout << endl;
            delete[]a;
            delete[]b;
        }
        return 0;
    }

    ---------------------------------------------------------------------------------------------------

    问题 D: 4.岗位管理(15分)

    时间限制: 1 Sec  内存限制: 128 MB

    题目描述

    某公司用二叉树表示岗位管理,其中双亲表示管理岗,管理左孩子和右孩子两个岗位。

    给出一棵二叉树的先序遍历(空树用字符零‘0’表示),表示公司的岗位关系。树结点包含一个数据,是单个大写字母,表示岗位编号。

    公司现在需要查询某个岗位的上下管理关系,即查找某结点的双亲结点、左右孩子结点。

    编写程序构建二叉树,并实现查询功能。

     

    输入

    第一行输入t表示有t个测试实例

    每个实例包含两行输入:

    第1行:二叉树先序遍历序列(空树用字符‘0’表示),无需考虑空树,序列中所有结点编号互不相同

    第2行:要查找的结点编号,无需考虑查找结点不存在的情况。

     

    输出

    每个实例输出两行

    第1行输出该二叉树的后序遍历序列,无需输出空树

    第2行输出三个结果,对应查找结点的双亲结点、左孩子结点、右孩子结点,如果某个结点不存在则输出-1

     

    样例输入

    3
    ABD000C00
    B
    AB00CD00E00
    C
    AB00C00
    A

    样例输出

    DBCA
    A D -1
    BDECA
    A D E
    BCA
    -1 B C
    -------------------------------------------------------------------------------------------------------------

    问题 E: 附加题:不完全拼接(30分)

    时间限制: 1 Sec  内存限制: 128 MB

    题目描述

    一个字符串 r,可以由另一个字符串 s 取自身的子串拼接得到,拼接规则为:

    取 s 的一些前缀依次拼接,并且最后把整个 s 拼至末尾。

    假设 r长度为ns长度为m,字符编号从 1 开始,则拼接规则的数学表示为:

    r[1:n] = s[1:i1] + s[1:i2] + ... + s[1:ik] + s[1:m],其中1 <= i1, i2, .. ik <= ms[1:i]表示取 s 中 1~i 字符构成的子串。

    给出字符串 r ,求能够按此规则拼出 r 的最短的 s 的长度。

    比如 r 为 aaaaac,如果 s 为 aac,那么取 s 的前缀 aaa以及自身 aac 能够拼成 r

    但是发现,如果 s 为 ac,取前缀 aaaa 以及自身 ac 也可以拼成 r ,那么 ac 就是更短的答案。

    输入

    多组数据,每组数据一行,一个非空字符串r,长度不超过 10^5

    输出

    每组数据对应输出一行,一个整数,能够用题目描述规则拼成r的最短字符串s的长度。

    样例输入

    vvm

    baaa

    qqbsk

    accb

    样例输出

    2

    4

    4

    4

    展开全文
  • void Prim(costtype C[n+1][n+1]) {costtype LOWCOST[n+1]; int CLOSEST[n+1]; int i,j,k; costtype min; for(i=2;i<...}}} //O(n²),一般用于顶点不太多的情况
  • 数据结构与算法期末复习(一)

    千次阅读 2019-12-26 09:40:53
    解释:算法的时间复杂度不仅问题的规模有关,还问题的其他因素有关。如某些排序的算法,其执行时间待排序记录的初始状态有关。为此,有时会对算法有最好、最坏以及平均时间复杂度的评价。

    1-1 对于顺序存储的长度为N的线性表,访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。

    • 正确
    • 错误

    答案:正确。

    1-2 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用顺序表存储最节省时间。

    • 正确
    • 错误

    答案:正确。
    解释:题给任一指定序号元素,所以利用顺序表存储最节省时间,时间复杂度均为O(1)。

    1-3 对于顺序存储的长度为N的线性表,删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。

    • 正确
    • 错误

    答案:错误。
    解释:删除第一个元素时间复杂度O(N),插入最后一个元素时间复杂度O(1)。

    1-4 若用链表来表示一个线性表,则表中元素的地址一定是连续的。

    • 正确
    • 错误

    答案:错误。链表是一种物理存储单元上非连续,非顺序的存储结构。

    2-1 在N个结点的顺序表中,算法的时间复杂度为O(1)的操作是:
    A:访问第i个结点(1≤i≤N)和求第i个结点的直接前驱(2≤i≤N)
    B:在第i个结点后插入一个新结点(1≤i≤N)
    C:删除第i个结点(1≤i≤N)
    D:将N个结点从小到大排序
    答案:A。
    解释:顺序表是随机存取结构,选项A中实质是查找第i个结点和第i-1个结点,因此时间复杂度为O(1);选项B和C插入和删除都需要移动元素,时间复杂度为O(n);选项D是排序问题,时间复杂度是O(n)~O(n2)。

    2-2 对于顺序存储的长度为N的线性表,访问结点和增加结点的时间复杂度为:
    A:O(1), O(1)
    B:O(1), O(N)
    C:O(N), O(1)
    D:O(N), O(N)
    答案:B。
    解释:访问结点的实质是查找结点,时间复杂度为O(1),增加结点需要移动元素,时间复杂度为O(N)。

    2-3 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用哪种存储方式最节省时间?
    A:双链表
    B:单循环链表
    C:带头结点的双循环链表
    D:顺序表
    答案:D。
    解释:存取“任一指定序号”的元素,表明是随机存取方式,因此只有顺序表合适。

    2-4 顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )。
    A:100
    B:105
    C:108
    D:110
    答案:C。
    解释:100+(5-1)*2=108 ,就是一个一个数也是108。

    2-5 下列函数中,哪两个函数具有相同的增长速度:
    A:2N和NN
    B:N和2/N
    C:N2logN和NlogN2
    D:NlogN2 和NlogN
    答案:D。
    解释:O(N2logN)>O(NlogN2)=O(NlogN)。

    2-6 算法的时间复杂度取决于( )。
    A:问题的规模
    B:待处理数据的初态
    C:计算机的配置
    D:A和B
    答案:D。
    解释:算法的时间复杂度不仅与问题的规模有关,还与问题的其他因素有关。如某些排序的算法,其执行时间与待排序记录的初始状态有关。为此,有时会对算法有最好、最坏以及平均时间复杂度的评价。

    展开全文
  • 数据结构与算法期末考试复习试题
  • 东北大学数据结构与算法课程期末复习资料,包括知识点汇总、样题及其解析等资料,仅供复习和参考,预祝下载的同学取得好成绩
  • 数据结构与算法复习题 选择题 TOC \o "1-5" \h \z ?在数据结构中从逻辑上可以把数据结构分为 C A.动态结构和静态结构 B ?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 ?数据结构在计算机内存...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,311
精华内容 1,324
关键字:

数据结构与算法期末复习

数据结构 订阅