计算机考研_顺序表相关题目

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了计算机考研_顺序表相关题目，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3924字，纯文字阅读大概需要6分钟。

内容图文

题目来自摘自《22王道考研的数据结构》， 仅用作本人复习参考用

题目1

1. 从顺序表中删除具有最小值的元素(假设唯一), 并由函数返回被删元素的值.空出的位置由最后一个
   元素填补, 若顺序表为空,则显示出错信息并退出运行.

bool Del_Min(SqList &L, ElemType &value)
{
    if(!L.length) 
    {
        printf("error msg");
        return false;
    }

    int pos = 0;
    int min = L.data[0];
    for(int i = 0; i < L.length; ++i)
        if(min > L.data[i]) pos = i, min = L.data[i];

    value = min;
    if(pos != L.length - 1) L.data[pos] = L.data[L.length - 1];   // 这里的if可以不必进行判断,因为就算是最后一个元素,也会在下面--中被删除.
    L.length--;
    return true;
}

题目2

2. 设计一个高效的算法,将顺序表L的所有元素逆置,要求算法的空间复杂度为O(1).

void Reverse(sqList &L)
{
    int i = 0, j = L.length - 1;
    while(j > i)
        swap(L.data[i++], L.data[j--]);
}

题目3

3. 对长度为n的顺序表L,编写一个时间复杂度为O(n),空间复杂度为O(1)的算法,该算法删除线性表中所有值为x的数据元素 */

void del_x_1(Sqlist &L, Elemtype x)                       // 解法1   直接删除法
{
    int k = 0;
    for(int i = 0; i < L.length; ++i)   
        if(L.data[i] != x) L.data[k++] = L.data[i];
    L.length = k;
}


void del_x_2(Sqlist &L, Elemtype x)                      // 解法2    构建法 
{
    int k = 0;
    for(int i = 0; i < L.length; ++i)
        if(L.data[i] != x) L.data[i - k] = L.data[i];
        else ++k;
    L.length = L.length - k;
}

题目4

4. 从有序顺序表删除其值在给定值s与t之间(要求s < t)的所有元素, 若s或t不合理或顺序表为空,则显示出错信息并退出运行

//注意:这里s和t不一定是顺序表中的元素, 只是给定的这个范围.

bool fun(Sqlist &L, Elemtype s, Elemtype t)
{
    int i, j;
    if(s >= t || !L.length) return false; 
    for(i = 0; i < L.length && L.data[i] < s; ++i);   // 寻找大于等于s的第一个元素. 
    if(i > L.length) return false;
    for(j = i; j < L.length && L.data[j] <= t; ++j);  // 寻找大于t的第一个元素
    while(j < L.length)  L.data[i++] = L.data[j++];
    L.length = i;
    return true;
}

题目5

5. 从顺序表中删除其值在给定值s与t之间(包含s和t, 要求s<t)的所有元素,若s或t不合理或顺序表为空,则显示错误并退出 */

bool fun(Sqlist &L, Elemtype s, Elemtype t)
{
    if(!L.length || s >= t) return false;

    int k = 0;
    for(int i = 0; i < L.length; ++i)
        if(L.data[i] < s || L.data[i] > t) L.data[k++] = L.data[i];

    L.length = k;
    return true; 
}

题目6

6. 从有序顺序表中删除所有其值重复的元素, 使表中所有元素均不相同(Lc26)*/

bool fun(Sqlist &L)
{
    if(!L.length) return false;
    int k = 0;

    for(int i = 0; i < L.length; ++i)
        if(!k || L.data[i] != L.data[k - 1]) L.data[k++] = L.data[i];
    L.length = k;
}

题目7

7. 将两个有序顺序表合并为一个新的有序顺序表, 并由函数返回结果顺序表 */

Sqlist Merge(Sqlist &L1, Sqlist &L2)
{
    Sqlist L;
    int n1 = 0, n2 = 0, l_n = 0;

    while(n1 < L1.length && n2 < L2.length)
    {
        if(L1[n1] < L2[n2]) L[l_n++]  = L1[n1++];
        else  L[l_n++] = L2[n2++];
    }

    while(n1 < L1.length)  L[l_n++] = L1[n1];
    while(n2 < L2.length)  L[l_n++] = L2[n2];
    L.length = l_n;
    return L;
}

题目8

8. 已知在一维数组A[m+n]中依次存放两个线性表(a1,a2,a3,…,am)和(b1,b2,b3,…,bn).试编写一个函数,将数组中两个顺序表的位置互换, 即将(b1,b2,b3,…,bn)放到(a1,a2,a3,…,am)的前面 .

相关题目: Acwing 77. 翻转单词顺序

void Reverse(int *Arr, int l, int r)
{
    int i = l, j = r;
    while(i < j) swap(Arr[i++], Arr[r--]);
}

void fun(int *arr, int m, int n)
{
    Reverse(arr, 0, m + n - 1);
    Reverse(arr, 0, n - 1);
    Reverse(arr, n, m + n - 1);
}

题目9

9. 线性表(a1,a2,a3,…,an)中的元素递增有序切按顺序存储于计算机内.要求设计一个算法,完成用最少时间在表中查找数值为x的元素, 若找到,则将其与后继元素位置相交换, 若找不到则将其插入表中并使表中顺序仍然递增有序 */

void fun(Sqlist &L, Elemtype x)
{
    int l = 0, r = L.length - 1;

    if(x > L.data[r])                       // 特判, 若此时比最大一个元素大, 直接插入最后 
    {
        L.data[r + 1] = x;
        L.length++;
        return;
    }

    while(r > l)                             // 二分查找找到第一个大于等于x的元素 
    {
        int mid = (l + r) / 2;
        if(L.data[mid] >= x) r = mid;
        else l = mid + 1;
    }

    if(L.data[l] == x)                        // 找到
    {
        if(l == L.length - 1) return;          // 最后一个元素并无后继 
        swap(L.data[l], L.data[l + 1]);
    }
    else         // 找不到
    {
        for(int i = L.length; i > l; --i)  L.data[i] = L.data[i - 1];
        L.data[l] = x;
        L.length++;
    }
}

内容总结

以上是互联网集市为您收集整理的计算机考研_顺序表相关题目全部内容，希望文章能够帮你解决计算机考研_顺序表相关题目所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---