Luz4年前 (2021-03-08)题库2518

1-1

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

(2分)

T

F

作者

DS课程组

单位

浙江大学

1-1

答案正确

(2 分)

创建提问

---

1-2

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

(2分)

T

F

作者

徐镜春

单位

浙江大学

1-2

答案正确

(2 分)

---

1-3

循环链表不是线性表。

(2分)

T

F

作者

李廷元

单位

民用航空飞行学院

1-3

答案正确

(2 分)

---

1-4

顺序存储的线性表可以随机存取。

(2分)

T

F

作者

李廷元

单位

民用航空飞行学院

1-4

答案正确

(2 分)

---

1-5

链式存储的优点是插入、删除元素时不会引起后续元素的移动，缺点是只能顺序访问各元素。

(2分)

T

F

作者

DS课程组

单位

临沂大学

1-5

答案正确

(2 分)

2-1

在$N$个结点的顺序表中，算法的时间复杂度为O(1)的操作是：

(2分)

A.

访问第$i$个结点（$1\le i\le N$）和求第$i$个结点的直接前驱（$2\le i\le N$）

B.

在第$i$个结点后插入一个新结点（$1\le i\le N$）

C.

删除第$i$个结点（$1\le i\le N$）

D.

将$N$个结点从小到大排序

作者

DS课程组

单位

浙江大学

2-1

答案正确

(2 分)

---

2-2

若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用哪种存储方式最节省时间？

(2分)

A.

双链表

B.

单循环链表

C.

带头结点的双循环链表

D.

顺序表

作者

DS课程组

单位

浙江大学

2-2

答案正确

(2 分)

---

2-3

下面的叙述正确的是( )。

(2分)

A.

线性表在链式存储时，查找第i个元素的时间同i的值成反比

B.

线性表在链式存储时，查找第i个元素的时间同i的值无关

C.

线性表在顺序存储时，查找第i个元素的时间同i 的值成正比

D.

线性表在顺序存储时，查找第i个元素的时间同i的值无关

作者

DS课程组

单位

临沂大学

2-3

答案正确

(2 分)

---

2-4

设h为不带头结点的单向链表。在h的头上插入一个新结点t的语句是：

(2分)

A.

h=t; t->next=h->next;

B.

t->next=h->next; h=t;

C.

h=t; t->next=h;

D.

t->next=h; h=t;

作者

DS课程组

单位

浙江大学

2-4

答案正确

(2 分)

---

2-5

带头结点的单链表h为空的判定条件是：

(2分)

A.

h == NULL;

B.

h->next == NULL;

C.

h->next == h;

D.

h != NULL;

作者

DS课程组

单位

浙江大学

2-5

答案正确

(2 分)

5-1

合并两个排序的整数数组A和B变成一个新的数组。例如，给出A={1,2,3,4}，B={2,4,5,6}，则合并后的数组为 {1,2,2,3,4,4,5,6}。

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    /**
     * @param A and B: sorted integer array A and B.
     * @return: A new sorted integer array
     */
    vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
        vector<int> result;
        int lena = A.size();
        int lenb = B.size();
        int ia = 0, ib = 0;
        while (ia < lena && ib < lenb)
        {
            int val_a = A[ia];
            int val_b = B[ib];
            int val;
            if (val_a <= val_b) {val = val_a; ia++;}
            else {val = val_b; ib++;}            4分;
        }
        while (ia < lena)
        {
            result.push_back(A[ia]);            3分;
        }
        while (3分)
        {
            result.push_back(B[ib]);
            ib++;
        }
        return result;
    }
};

作者

李廷元

单位

民用航空飞行学院

时间限制

400 ms

内存限制

64 MB

5-1

答案正确

(10 分)

---

5-2

下列代码的功能是返回带头结点的单链表L的逆转链表。

List Reverse( List L )
{
    Position Old_head, New_head, Temp;
    New_head = NULL;
    Old_head = L->Next;

    while ( Old_head )  {
        Temp = Old_head->Next;        3分;  
        New_head = Old_head;  
        Old_head = Temp; 
    }    3分;
    return L;
}

作者

DS课程组

单位

浙江大学

时间限制

400 ms

内存限制

64 MB

7-1 两个有序序列的中位数 (24 分)

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,AN−1的中位数指A(N−1)/2的值,即第$\lfloor (N+1)/2\rfloor$个数（A0为第1个数）。

输入格式:

输入分三行。第一行给出序列的公共长度N（0$<$N$\le$100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。

输出格式:

在一行中输出两个输入序列的并集序列的中位数。

输入样例1:

5
1 3 5 7 9
2 3 4 5 6

输出样例1:

4

输入样例2:

6
-100 -10 1 1 1 1
-50 0 2 3 4 5

输出样例2:

1

作者

DS课程组

单位

浙江大学

代码长度限制

16 KB

时间限制

200 ms

内存限制

64 MB

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    vector<int> C;
    vector<int> p;
    int n,data1,data2;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>data1;
        C.push_back(data1);
    }
    for(int i=0; i<n; i++)
    {
        cin>>data2;
        C.push_back(data2);
    }
    sort(C.begin(),C.end());
    cout<<C[n-1];
}