精华内容
下载资源
问答
  • 数据结构
  • 数据结构 线性表 练习题 试卷及答案.doc
  • 关于数据结构的绪论和线性表练习题,希望对大家有帮助。15.分析:首先在链表中查找元素值为X的结点,若找到则让freq域的值增1;然后 依次和它的前趋的freq域值比较,若比前freq域值大,和前趋结点位置交换,直到...
  • 三写一个算法合并两个已排序的线性表用两种方法数组表示的线性表顺序表和指针表示的线性表链表 要求1定义线性表节点的结构并定义节点的型和位置的型 2定义线性表的基本操作 3在12的基础上完成本 4在main函数中进行...
  • 精品文档 第二章 线性表 一名 解 1. 性 构 2. 数据 构的 序 3. 序表 4. 表 5. 数据 构的 接 6. 建表 7. 字符串 8. 串 9. 序串 10. 串 二填空 1. 了便于 有 将含 n(n>=0) 个 点的 性 构表示成 (a a, ? a) 其中每 n12 ...
  • 数据结构 主讲人:米晓红 hongxiaomi@163.com 器EE 线性表习题课 要点回顾 1线性表的逻辑特征 令1在非空的线性表,有且仅有一个开始结点a1,它没 有直接前趋,而仅有一个直接后继a2 令2)有且仅有一个终端结点an,它没有...
  • 数据结构线性表习题

    2013-12-23 09:12:52
    这是数据结构中,最基础,也是入门的时候最重要的一章,线性表习题
  • 练习题及解题思路 #include <stdio.h> #include "string.h" #include "ctype.h" #include "stdlib.h" #include "math.h" #include "time.h" #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OK...

    练习题及解题思路

     

    #include <stdio.h>
    #include "string.h"
    #include "ctype.h"
    #include "stdlib.h"
    #include "math.h"
    #include "time.h"
        
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define OK 1
        
    #define MAXSIZE 20 //存储空间初始分配量
        
        typedef int Status;//Status 是函数的类型,其值是函数结果状态代码l,如OK等
        typedef int ElemType;//ElemType 类型根据实际情况而定,这里假设为int
        
        //定义结点
        typedef struct Node{
            ElemType data;
            struct Node *prior;
            struct Node *next;
        }Node;
        
        //类型重定义
        typedef struct Node * LinkList;
    //初始化链表
        Status InitList(LinkList *L){
            *L = (LinkList)malloc(sizeof(Node));
            if (*L == NULL) return ERROR;
            (*L)->next = NULL;
            return OK;
        }
        
        //链表插入
        Status ListInsert(LinkList *L, int i, ElemType e){
            if (i<1) return ERROR;
            LinkList p,temp;
            p = *L;
            
            for (int j=1; j<i; j++) {
                p = p->next;
            }
            
            if (p == NULL) return ERROR;
            
            temp = malloc(sizeof(Node));
            temp->data = e;
            temp->next = p->next;
            p->next = temp;
            
            return OK;
        }
        
        //遍历
        Status ListTraverse(LinkList L)
        {
            LinkList p = L->next;
            while(p)
            {
                printf("%d  ",p->data);
                p = p->next;
            }
            printf("\n");
            return OK;
        }

    题目验证:

     int main(int argc, const char * argv[]) {
    
         Status iStatus;
         LinkList La,Lb,Lc,L;
         InitList(&La);
         InitList(&Lb); 

    题目1:

     1、将2个递增的有序链表合并为一个有序链表;要求结果链表任然使用两个链表的存储空间,不另外占用其他的存储空间。表中不允许有重复的数据


     分析:
     关键词:递增有序链表,不允许有重复数据,保留递增关系(后插法),不占用额外的存储空间意思不能开辟新结点
     
     思路:
     (1)、假设合并的链表为La 和 Lb,合并后的新表使用头指针Lc(Lc的表头结点设为La的表头结点)指向。pa 和 pb分别是La 和 Lb的工作指针,初始化为相应链表的首原结点
     (2)、从首元结点开始,当连个链表La 和 Lb均未到达表尾结点时,依次摘取其中值较小的结点(哪个链表中的小取哪个保证递增顺序),并将其插入Lc 后面。
     (3)、如果两个表中的值相等的时候,只摘取La 表中的元素,删除Lb 中的元素(防止出现野指针,同时防止出现相同的数据)。
     (4)、当一个表达到表尾结点为空时,非空表的剩余元素直接连接在 Lc 表最后(也就是其中一个表遍历并取完值了之后,另一个还没完,就直接把非空的链表剩下的元素全部连接到Lc后面)。
     (5)、最后释放链表lb 的头结点(将Lb释放,防止出现野指针,此时的Lb已经不完整同时留着也无意义)。

    void MergeList(LinkList *La, LinkList *Lb, LinkList *Lc){
    //    1、
        LinkList pa = (*La)->next;
        LinkList pb = (*Lb)->next;
        LinkList pc = *Lc = *La;
        LinkList temp;
        
        while (pa && pb ) {
    //        取较小者(相同的取La的,释放Lb的)链接到pc 后面,对应指针后移,pc也后移
            if (pa->data > pb->data) {
                pc->next = pb;
                pc = pc->next;
                pb = pb->next;
            }else if(pa->data == pb->data){
                pc->next = pa;
                pc = pc->next;
                pa = pa->next;
                temp = pb;
                pb = pb->next;
                free(temp);
                
            }else{
                pc->next = pa;
                pc = pc->next;
                pa = pa->next;
            }
        }
    //    4、将非空的链表剩余元素全部连接到Lc表的最后
        pc->next = pa?pa:pb;
        free(*Lb);
    }

    验证:

        printf("******题目1:********\n");
        //设计2个递增链表La,Lb
        for(int j = 10;j>=0;j-=2)
        {
            iStatus = ListInsert(&La, 1, j);
        }
        printf("La:\n");
        ListTraverse(La);
    
        for(int j = 11;j>0;j-=2)
        {
            iStatus = ListInsert(&Lb, 1, j);
        }
        printf("Lb:\n");
        ListTraverse(Lb);
    
        MergeList(&La, &Lb, &Lc);
        printf("Lc:\n");
        ListTraverse(Lc);
    
    //**************************************************
    La:
    0  2  4  6  8  10  
    Lb:
    1  3  5  7  9  11  
    Lc:
    0  1  2  3  4  5  6  7  8  9  10  11
    

    题目2:

     2、已知连个链表A和B分别标识两个集合。设计一个算法,用于求出A与B的交集,并存储在A链表中;
     例如:
     La = {2,4,6,8}; Lb = {4,6,8,10};
     Lc = {4,6,8}


     分析:
     依次摘取2个表中相等的元素重新进行链接,删除其他不相等的元素。


     思路:
     (1)、假设待合并的链表为La 和 Lb,合并后的新表使用头指针Lc (Lc的表头结点设为La的表头结点)指向。pa 和 pb 分别是La,Lb 的工作指针。初始化为相应链表的首元结点
     (2)、从首元结点开始比较,当两个链表La 表 和Lb 均为到达表尾结点时
     (3)、如果两个表的数据相等,只摘取La 表中的元素,连接到Lc 表的后面,删除Lb 表中的元素。同时pa、pb、pc指针均向后移。
     (4)、如果两个表的数据不相等,判断哪个表中的数据小删除那个表中的数据同时对应表的指针向后移
     (5)、当链表La 和 Lb有一个先到达表尾结点为空时,依次删除非空表中的所有元素。
     (6)、最后释放链表 Lb的头结点

    void Intersection(LinkList *La, LinkList *Lb, LinkList *Lc){
     
        //    pc 指向Lc 的头结点,用La的头结点作为Lc的头结点
        LinkList pa,pb,pc,temp;
        pa = (*La)->next;
        pb = (*Lb)->next;
        pc = *Lc = *La;
     
        while (pa && pb) {
            //        相等,将La中的元素连接到Lc中,然后删除Lb中对应的元素,同时pa、pb、pc都向后移
            if (pa->data == pb->data) {
                pc->next = pa;
                pc = pc->next;
                pa = pa->next;
                temp = pb;
                pb = pb->next;
                free(temp);
            }else if (pa->data < pb->data){
                temp = pa;
                pa = pa->next;
                free(temp);
            }else{
                //删除较小值Lb中的元素
                temp = pb;
                pb = pb->next;
                free(temp);
            }
        }
     
        //    依次删除非空链表中剩余的所有元素
        while (pa) {
            temp = pa;
            pa = pa->next;
            free(temp);
        }
     
        while (pb) {
            temp = pb;
            pb = pb->next;
            free(temp);
        }
     
        //    Lc的尾结点的 next指向NULL
        pc->next = NULL;
        free(*Lb);
    }

    验证

        printf("******题目2:********\n");
        ListInsert(&La, 1, 8);
        ListInsert(&La, 1, 6);
        ListInsert(&La, 1, 4);
        ListInsert(&La, 1, 2);
        printf("La:\n");
        ListTraverse(La);
    
    
        ListInsert(&Lb, 1, 10);
        ListInsert(&Lb, 1, 8);
        ListInsert(&Lb, 1, 6);
        ListInsert(&Lb, 1, 4);
        printf("Lb:\n");
        ListTraverse(Lb);
    
        Intersection(&La, &Lb, &Lc);
        printf("Lc:\n");
        ListTraverse(Lc);
    
    //****************************************
    La:
    2  4  6  8  
    Lb:
    4  6  8  10  
    Lc:
    4  6  8  

     

    题目3:

     3、设计一个算法,将链表中d所有的连接方向“原地旋转”,即要求仅仅利用原表的存储空间。换句话说,要求算法空间复杂度为O(1);
     例如:L = {0,2,4,6,8,10},L逆转后:L = {10,8,6,4,2};


     分析:
     (1)、不能开辟新的空间,只能改变指针的指向。
     (2)、可以考虑逐个摘取结点,利用前插法创建链表的思想,将结点依次插到头结点的后面。
     (3)、因为先插入的结点为表尾,最后插入的结点为表头,即可实现链表的逆转;
     
     思路:
     (1)、利用原有的头结点*L,p为工作指针,初始时p 指向首元结点。
     (2)、因为摘取的结点依次向前插入,为确保链表尾部为空,初始时将头结点的指针域置空
     (3)、从前向后遍历链表,依次摘取结点,在摘取接结点前需要用指针temp 记录后继结点,以防止链接后丢失后继结点;
     (4)、将摘取的结点插入到头结点之后,最后p指向新的待处理结点temp(p=temp);

    void Inverse(LinkList *L){
        LinkList p,temp;
        p = (*L)->next;
        (*L)->next = NULL;
     
        while (p) {
            //        temp指向p的后继结点,防止丢失
            temp = p->next;
            //        p 指向的结点 后继为之前的首元结点,前驱是头结点(也就是插入到头结点之后,头插法)
            p->next = (*L)->next;
            (*L)->next = p;
            //        p向后移动 p = p->next;
            p = temp;
        }
    }


    题目4:

     4、设计一个算法,删除递增有序链表中值大于等于mink 且小于等于maxk(mink,maxk是给定的连个参数,其值可以和表中的元素相同,也可以不同)的所有元素;


     分析:
     递增有序链表,找到对应的上下边界,将其中的值全部删除掉即可。
     
     思路:
     (1)、用指针p 指向链表头结点,temp 用来指向要删除的结点。
     (2)、遍历去查看p 的后继结点,通过p 的后继结点的值判断是否是要删除的结点。
     (3)、如果是要删除的结点,就把p 的后继结点删除,后继指向下下一个结点。不移动p(以后后继已经变了)继续遍历。
     (4)、如果p 后继结点不是要删除的结点,将p 后移。继续遍历

    void DeleteMinMax(LinkList *L, int mink, int maxk){
        LinkList p,temp;
        p = (*L);
     
        //    遍历是用p->next完成
        while (p->next) {
            temp = p->next;
            if (temp->data >= mink && temp->data <= maxk) {
                p->next = temp->next;
                free(temp);
            }else
                p = p->next;
        }
    }

    验证

        printf("******题目3:********\n");
        InitList(&L);
        for(int j = 10;j>=0;j-=2)
        {
            iStatus = ListInsert(&L, 1, j);
        }
        printf("L逆转前:\n");
        ListTraverse(L);
    
        Inverse(&L);
        printf("L逆转后:\n");
        ListTraverse(L);
    
    //******************************************
    L逆转前:
    0  2  4  6  8  10  
    L逆转后:
    10  8  6  4  2  0  

    题目5:

     5、设将n(n>1)个整数存放到一维数组R 中,试设计一个在时间和空间复杂度都尽可能高效的算法;将R 中保存的序列循环左移p 个位置(0<p<n)个位置,即将R 中的数据由(x0,x1,...,xn-1)变换成(xp,xp+1,...,xn-1,x0,x1,...,xp-1);
     例如:pre[10] = {0,1,2,3,4,5,6,7,8,9},
     n = 10,p = 3;
     pre[10] = {3,4,5,6,7,8,9,0,1,2}


    思路:
     (1)、先将n个数据原地逆置 (9,8,7,6,5,4,3,2,1,0)
     (2)、将n个数据拆解成 [9,8,7,6,5,4,3] [2,1,0];
     (3)、将前n-p 个数据和后p 个数据分别原地逆置;[3,4,5,6,7,8,9] [0,1,2]
     
    复杂度分析:
     时间复杂度:O(n);
     空间复杂度:O(1);

    void Reverse(int *pre,int left ,int right){
        
        int i=left,j=right,temp;
        //    数组逆置
        while (i < j) {
            temp = pre[i];
            pre[i] = pre[j];
            pre[j] = temp;
            
            i++;
            j--;
        }
    }
    
    void LeftShift(int *pre,int n,int p){
        
        if (p>0 && p<n) {
            Reverse(pre, 0, n-1);
            Reverse(pre, 0, n-p-1);
            Reverse(pre, n-p, n-1);
        }
    }

    验证

        printf("******题目4:********\n");
        InitList(&L);
        for(int j = 10;j>=0;j-=2)
        {
            iStatus = ListInsert(&L, 1, j);
        }
        printf("L链表:\n");
        ListTraverse(L);
    
        DeleteMinMax(&L, 4, 10);
        printf("删除链表mink与maxk之间结点的链表:\n");
        ListTraverse(L);
    
    //*************************************
    L链表:
    0  2  4  6  8  10  
    删除链表mink与maxk之间结点的链表:
    0  2 

    验证

        int pre[10] = {0,1,2,3,4,5,6,7,8,9};
        LeftShift(pre, 10, 3);
        for (int i=0; i < 10; i++) {
            printf("%d ",pre[i]);
        }
        printf("\n");
    
    //******************************************
    3 4 5 6 7 8 9 0 1 2 

    题目6:

    6、已知一个整数序列A= (a0,a1,a2,...,an-1),其中(0<= ai <=n),(0<= i <=n).若存在ap1 = ap2 = ... = apm = x,且m>n/2(0<=pk<n,1<=k<=m),则称x 为 A的主元素。例如,A = (0,5,5,3,5,7,5,5),则5是主元素;若B=(0,5,5,3,5,1,5,7),则B中没有主元素。假设A 中的n个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出数组元素中的主元素,若存在主元素则输出该元素,否者输出-1。


     分析:
     主元素,是数组中的出现次数超过一半的元素。
     当数组中存在主元素时,所有非主元素的个数和必然少于数组总数的一半。
     用主元素的总数 - 非主元素的总数 > 1;
     
     思路:
     (1)、选取候选主元素,从前向后依次扫描数组中的每个整数。假定第一个整数位主元素,将其保存在key 中,计数为1,若遇到下一个整数仍然等于key,则计数加1.否者计数减1,当计数减到0时,将遇到的下一个整数保存到key中,计数重新标记为1。开始新一轮计数(继续向后依次比较,直到全部数组元素扫码完毕)。
     (2)、判断key中的元素是否是真正的主元素,再次扫描数组。统计key中元素出现的次数,若大于n/2。则是主元素,z否则序列中没有主元素。


    复杂度分析:
     时间复杂度O(n);
     空间复杂度O(1);

    int MainElement(int *A, int n){
        
        //目标: 求整数序列A中的主元素;
        //count 用来计数
        int count = 1;
        //key 用来保存候选主元素, 初始A[0]
        int key = A[0];
        
        //(1) 扫描数组,选取候选主元素
        for (int i = 1; i < n; i++) {
            //(2) 如果A[i]元素值 == key ,则候选主元素计数加1;
            if (A[i] == key) {
                count++;
            }else{
                //(3) 当前元素A[i] 非候选主元素,计数减1;
                if(count >0){
                    count--;
                    
                }else{
                    //(4) 如果count 等于0,则更换候选主元素,重新计数
                    key = A[i];
                    count = 1;
                }
            }
        }
        
        //如果count >0
        if (count >0){
            
            //(5)统计候选主元素的实际出现次数
            for (int i = count = 0; i < n; i++)
                if (A[i] == key) count++;
        }
        
        //(6)判断count>n/2, 确认key是不是主元素
        if (count > n/2) return key;
        else return -1; //不存在主元素
    }

     验证

        printf("******题目6:********\n");
        int  A[] = {0,5,5,3,5,7,5,5};
        int  B[] = {0,5,5,3,5,1,5,7};
        int  C[] = {0,1,2,3,4,5,6,7};
    
        int value = MainElement(A, 8);
        printf("数组A 主元素为: %d\n",value);
        value = MainElement(B, 8);
        printf("数组B 主元素为(-1表示数组没有主元素): %d\n",value);
        value = MainElement(C, 8);
        printf("数组C 主元素为(-1表示数组没有主元素): %d\n",value);
    
    //*************************************************************
    数组A 主元素为: 5
    数组B 主元素为(-1表示数组没有主元素): -1
    数组C 主元素为(-1表示数组没有主元素): -1

     

    题目7:

    7、用单链表保存m 个整数,结点的结构为(data,link),且|data|<=n(n为正整数)。现在要求设计一个时间复杂度尽可能高效的算法,对于链表中的data 绝对值相等的结点,仅保留第一次出现的结点,删除其余绝对值相等的结点。
     例如:
     链表   A= {21,-15,15,-7,15}
     删除后 A= {21,-15,-7}


     分析
     要求设计的是时间复杂度尽量高效,所以可以考虑用空间换时间的方法。
     申请一个空间大小为n+1(0 号单元不使用)的辅助数组。
     保存链表中已出现的数值,通过对链表进行一趟扫描来完成删除


     思路:
     (1)、申请大小为n+1的辅助数组t 并赋值初值为0;
     (2)、从首元结点开始遍历链表,依次检查t[abs(data)] 也就是t[|data|] 的值,若[|data|] 为0,即结点首次出现,则保留该结点,并置t[|data|] = 1,若t[|data|] 不为0,则将该结点从链表中删除
     
    复杂度分析:
     时间复杂度: O(m),对长度为m的链表进行一趟遍历,则算法时间复杂度为O(m);
     空间复杂度: O(n)

    void DeleteEqualNode(LinkList *L,int n){
        
        //目标: 删除单链表中绝对值相等的结点;
        //1. 开辟辅助数组p.
        int *p = alloca(sizeof(int)*n);
        LinkList r = *L;
        
        //2.数组元素初始值置空
        for (int i = 0; i < n; i++) {
            *(p+i) = 0;
        }
        
        //3.指针temp 指向首元结点
        LinkList temp = (*L)->next;
        
        //4.遍历链表,直到temp = NULL;
        while (temp!= NULL) {
            
            //5.如果该绝对值已经在结点上出现过,则删除该结点
            if (p[abs(temp->data)] == 1) {
                
                //临时指针指向temp->next
                r->next = temp->next;
                //删除temp指向的结点
                free(temp);
                //temp 指向删除结点下一个结点
                temp = r->next;
            }else
            {
                //6. 未出现过的结点,则将数组中对应位置置为1;
                p[abs(temp->data)] = 1;
                r = temp;
                //继续向后遍历结点
                temp = temp->next;
            }
        }
    }

    验证

        //21,-15,15,-7,15
        printf("******题目7:********\n");
        InitList(&L);
        ListInsert(&L, 1, 21);
        ListInsert(&L, 1, -15);
        ListInsert(&L, 1, 15);
        ListInsert(&L, 1, -7);
        ListInsert(&L, 1, 15);
    
        DeleteEqualNode(&L, 21);
        ListTraverse(L);
    
    //***************************************
    15  -7  21 

     

    展开全文
  • 习题按类和方法区别

    线性表的顺序表示

    1. 将顺序表所有元素逆置,要求空间复杂度O(1)
      将前一半和后一半交换
    void reverse(SqList &L){
         Elemtype temp;
         for(int i=0;i<L.length/2;i++){
         temp = L.data[i] ;
         L.data[i] = L.data[L.length-i-1];
         L.data[L.length-i-1] = temp;
         }
    }
    
    1. 长度为n的顺序表L,时间复杂度O(N),空间复杂度O(1),删除其中所有值为x的元素
      解法1:使用k记录顺序表中等于x的元素个数,边扫描边统计k,并将不等于x的向前移动K个位置,并修改length的长度。
    LinkList deleteElem(LinkList &L,Elemtype x){
    if(L == NULL)
       return NULL;
    int k=0;
    for(int i=0;i<L.length;i++)
       if(L.data[i] == x){
           k++;
       }
       else{
       L.data[i-k] = L.data[i];//每次只移动当前元素
       }
    }
    L.length =  L.length - k;
    return L;
    }
    

    解法2:记录不等于x的元素个数k,每次只移动一个元素,只将当前元素赋值到k的位置上

    LinkList deleteElem(LinkList &L,Elemtype x){
    if(L == NULL)
       return NULL;
    int k=0;
    for(int i=0;i<L.length;i++)
    {
       if(L.data[i]!=x)
       {
          L.data[k] = L.data[i];
          k++;
       }
    }
    L.length = k;
    return L;
    }
    

    前两种解法都是每次只移动当前的1个元素而不是移动当前元素后面的所有元素,保证时间复杂度O(n),遍历是无法改变的,所以考虑改变遍历里面的操作。
    解法3:设置头尾两个指针同时向中间移动,检测到最左侧的为x的元素,将其与最右侧的非x元素进行交换,但是会改变元素的相对位置

    1. 有序顺序表中删除其值在s和t之间的所有元素,如果s或t不合理或者顺序表为空显示出错信息
      找到第一个大于s的元素,然后找到第一个小于t的元素,将后面的所有元素前移然后更新数组长度。
    //两步操作写在一起
    LinkList delete1(LinkList &L,ElemType s,ElemType t){
         if(L == NULL || s>t)
            return NULL;
         int i=0;
         int k = 0;
         while(i<L.length){
          if(L.data[i] > s && L.data[i] < t)
            k++;
          else
           L.data[i-k] = L.data[i];
           i++;
         }
         L.length = L.length - k;
        return L;
    }
    //两步操作分开
    LinkList delete2(LinkList &L,ElemType s,ElemType t){
         if(L == NULL || s>t)
            return NULL;
         int i,j;
         for(i=0;i<L.length&&L.data[i]<s;i++);
         //在这里加一个判断i是否超出数组的长度更好
         if(i>=L.length)
            return NULL;
         for(j=i;j<L.length&&L.data[j]<t;j++);
         while(j<L.length){
         L.data[i] = L.data[j];
         i++;
         j++;
         }
         L.length = i+1;//最后的元素位置是i代表的,但是长度和游标有+1的区别
         return L;
    }        
    
    1. 从顺序表中删除删除其值在s和t之间的所有元素,如果s或t不合理或者顺序表为空显示出错信息(这里可以用问题3的第一种方法
    LinkList delete(LinkList &L,ElemType s,ElemType t){
         if(L == NULL || s>t)
            return NULL;
         int i=0;
         int k = 0;
         while(i<L.length){
          if(L.data[i] > s && L.data[i] < t)
            k++;
          else
           L.data[i-k] = L.data[i];
           i++;
         }
         L.length = L.length - k;
        return L;
    }
    
    
    1. 有序顺序表中删除所有其值重复的元素,使表中所有元素不同
      利用直接插入排序的思想,从头到尾扫描数组,将从第一个开始的部分看成是一个非重复数组,然后将后面的不断插入,最后的非重复数组的长度直接赋值给length。这里的插入不需要将后面的所有元素前移,直接给非重复数组当前指针指向位置赋值即可,只要有重复必定出现至少两次,不会出现掩盖还未处理的非重复数。
    LinkList delete(LinkList &L){
       if(L ==NULL)
       return NULL;
       int i,j;
       for(i=0,j=1;j<L.length;j++{
           if(L.data[i]!=L.data[j])
             L.data[++i]=L.data[j];
       }
       L.length = i+1;//虽然前面是++i才赋值,但是最后退出的时候是加完之后的被赋值,所以最后并没有多出一个空的,所以i还是要+1
       return L;
    }
    
    1. 如果是无序顺序表,O(n)的算法
      思路一:O(N^2)的有一个比直接后面覆盖前面的要好一些的方法就是内层循环换成从前向当前节点移动的循环
      思路二:使用hash表
      思路三:排序+删除(下面没有代码)
    //如果是两层for循环可以处理当前节点前面的做内层循环,也可以遍历后面的节点做内层循环,时间复杂度O(N)
    LinkList delete1(LinkList &L){
        int i,j;
        for(i=1;i<L.length;i++){
          j=0;
          while(j<i){
            if(L.data[i]==L.data[j])
                 L.data[j]=L.data[i];
             j++;
            }   
          }  
    }
    //如果从后往前推的话只能移动所有元素,不能直接进行一步赋值,因为不能保证后面重复元素出现的次数
    //第一种内层循环是从第一个到当前节点的可以保证重复节点的次数不超过2次,所以可以通过一次赋值进行改变
    LinkList delete2(LinkList &L){
       int i,j;
       for(i=0;i<L.length;i++)
          for(j=i+1;j<L.length;j++)
             if(L.data[i]==L.data[j])
               over
    }
    //使用hash函数,空间复杂度o(N),时间复杂度O(n),使用空间换取时间
    # define Maxsize 10000
    LinkList delete3(LinkList &L){
       int index[Maxsize];
       for(int i=0;i<Maxsize;i++)
         index[i] = 0;
       for(int i=0;i<L.length;i++)
       if(index[L.data[i]]!=0)
           over//当前节点可以被删除,但是具体删除的操作怎么进行呢?
    }
    LinkList delete30(LinkList &L){
         int index[Maxsize];
        for(int i=0;i<Maxsize;i++)
         index[i] = 0;
        for(int i=0;i<L.length;i++)
          index[L.data[i]]++;
        int k =0;
        for(int i=0;i<Maxsize;i++)
          if(index[i]!=0)
             L.data[k]=i;
        L.length = k;
        return L; 
    }
    
    1. 将两个有序顺序表合并成一个有序顺序表
    LinkList merge(LinkList &L1,LinkList &L2){
      int i,j;
      i=0;
      j=0;
      LinkList L3 = NULL;
      L3.length = L2.length+L1.length;
      int k=0;
      while(i<L1.length&&j<L2.length)
      {
         if(L1.data[i]<=L2.data[j])
             L3.data[k]=L1.data[i];
         else
             L3.data[k]=L2.data[j];
         k++;
    }
      while(i<L1.length){
         L3.data[k]=L1.data[i];
         k++;
      }
      while(j<L2.length){
        L3.data[k]=L2.data[i];
         k++;
      }
      return L3;
    }
    
    1. 已知在一维数组A[m+n]中存储着两个线性表,写一个函数将数组中的两个顺序表位置调换
      思路一:直接将前面的m长度的数组向后移动,后面的n数组赋值到从第一个往后的位置
      思路二:利用数组逆序,首先逆序整个数组,然后前面的m个和后面的n个分别逆序
      //如果令开辟一个空间的话直接赋值即可
      //如果不开辟空间可以使用直接插入排序的方法
      //时间复杂度O(nm)
      LinkList reverse1(LinkList &L,int m,int n){
        int i,j,k=0;
        for(i=m;i<m+n-1;i++)
       {int temp = L.data[i];
        for(j=m+k-1;j>=k;j--){
             L.data[j+1]=L.data[j];
          }
          L.data[k] = temp;
          k++;
    }   
     return L;
    }
    //首先将全部元素逆序,然后分别逆序前m个和后n个
    void verse(LinkList &L,int start,int end){
    int temp;
    int middle = (end-start)/2;
    for(int i=start;i<middle;i++)
    {
      temp = L.data[i];
      L.data[i] = L.data[i+middle];
      L.data[i+middle]=temp;
    }
    }
    LinkList reverse2(LinkList &L,int m,int n){
      verse(L,0,m+n);
      verse(L,0,m);
      verse(L,m,m+n);
      return L;
    }
    
    1. 线性表中元素递增有序,要求设计一个算法可以在最少时间在表中查找到值为x的元素,找到后将其与后继元素位置进行交换,找不到将其插入到线性表中但是仍保证递增有序。
      注意:这里遗漏了如果匹配上的x是最后一个元素,则不存在与后继元素交换位置的情况
    LinkList findChange(LinkList &L,ElemType x){
     int left=0;
     int right=L.length-1;
     int middle = (right-left)/2;
     while(left<right){
      if(L.data[middle]==x&&middle!=L.length-1)//这里注意判断条件还要包括不是最后一个元素匹配上
        {
        int temp = L.data[middle];
        L.data[middle]=L.data[middle+1];
        L.data[middle+1]=temp;
    }
      else if(L.data[middle]<x)
      {
          right = middle;
      }
      else{
          left = middle+1;
    }
    //没有找到进行插入,直接插入到left后面就行
    for(int i = L.length-1;i>left ;i++)
    {
        L.data[i+1]=L.data[i]; 
    }
    L.data[left+1]=x;
    }
    return L;
    }
    
    1. 将n个整数存放在一维数组R中,设计一个在时间和空间上都高效的算法。将R中保存的序列循环左移p(0<p<1)个位置。
      思路:和前面的m+n逆序是一样的思路,同理可知一个数组的循环位置改变可以使用两次逆序的方法
      同样也可以适用辅助数组来解,先将前p个暂存在辅助数组中,然后将后面的向左移动,然后将暂存的数组重新复制回原数组。[时间复杂度O(n),空间复杂度O§]
    void verse(LinkList &L,int start,int end){
    int temp;
    int middle = (end-start)/2;
    for(int i=start;i<middle;i++)
    {
      temp = L.data[i];
      L.data[i] = L.data[i+middle];
      L.data[i+middle]=temp;
    }
    }
    void reverse(LinkList &L,int p){
       verse(L,0,L.length);
       verse(L,0,L.length-p);
       verse(L,L.length-p,L.length);
    }
    
    1. 现在有两个等长升序序列,设计一个在时间和空间上都高效的算法,找出两个序列A和B的中位数。(这个不是绝对数学上的中位数,这里有限制是n/2取天棚运算。
    int findMiddle(LinkList &L1,LinkList &L2){
        int left1,left2;
        left1=left2=0;
        int right1,right2;
        right1 = L1.length;
        right2 = L2.length;
        while(left1<=right1&&left2<=right2){
        int middle1=(right1-left1)/2;
        int middle2=(right2-left2)/2;
        int middle = (L1.data[middle1]+L2.data[middle2])/2;
        if(L1.data[middle1]==middle&&L2.data[middle2]==middle)
            return middle;
        if(L1.data[middle1]<middle)
             left1 =  middle1+1;
        else{
            right1 = middle1;}
        if(L2.data[middle2]<middle)
            left2 = middle1+1;
        else{
            right2 = middle2;
            }   
    }
        return middle;
    }
    

    思路:从二者的中位数直接判断
    共分3种情况:
    a、如果数组1的中位数和数组2相等,直接返回
    b、如果数组1的中位数小于数组2的中位数,除去数组1左半部分;除去数组2右半部分
    c、如果数组1的中位数大于数组2的中位数,除去数组2左半部分,除去数组1右半部分
    然后继续比较剩下的部分的两个数组的中位数大小
    注意:这里涉及到求中位数的时候数组元素个数是奇数还是偶数的问题

    int search(int A[],int B[],int n){
      int s1=0,d1=n-1,m1,s2=0;d2=n-1,m2;
      while(s1!=d1&&s2!=d2){
          //m1 = (d1-s1)/2;
         // m2 = (d2-s2)/2;
         m1 = (d1+s1)/2;//这里要使用+,在后半部分的时候求middle的下标就是+才能得到
         m2 = (d2+s2)/2;
         if(A[m1]==B[m2])
            return A[m1];
         else if(A[m1]<B[m2])
         {
            if((s1+d1)%==0)//如果除完说明是偶数,则证明原来的数组是奇数,也就是中间的数直接可以代表中位数,所以这里保留中间的数
             {
             s1 = m1;
             d2 = m2;
    }
    else{//说明原数是偶数,所以不保留中间数
         s1 = m1+1;
         d2 = m2;
    }  
         }
         else{
          if((s2+d2)%2==0){
          s2=m2;
          d1 = m1;
    }else{
          s2 = m2+1;
          d1 = m1;
    }
        
    }
    //直到两个数列中均只有一个元素的时候取较小的元素为中位数
    return A[s1]<B[s2]?A[s1]:B[s2];
    }
    

    ❀13. 已知一个整数序列A=(a0,a2,…,an-1),其中0<=ai<n。如果在该序列中存在一个整数满足该整数在序列中出现的次数大于n/2,则该整数为主元素,试找出该整数序列中的主元素,如果存在输出,否则输出-1
    思路:设置一个Number存储首先选定的可能为主元素的元素,然后设置一个count存储这个元素的出现次数,count更新方式是:如果下一个元素与当前的Number相等则count++,否则count–;如果count更新到0,则换下一个数进行计数,直到扫描完整个数组,然后判断当前的count是否大于n/2 ,从头遍历整个数组重新统计当前count所对应的Number是否是主元素,开始的count只能保证当前的Number是出现次数最多的元素,但是这个元素出现的次数是否大于n/2还是需要重新判断,因为在不等于Number的时候将count–了(这里放到扫描完整个数组再进行判断,最后主元素只能有一个,最后判断一次即可以决定整个数组是否含有主元素)

    int findMax(int A[],int n){
    int k = 0;
    int Number = A[k];
    int count = 0;
    while(k<n-1){
    for(int i = 0;i<n;i++){
       if(A[i] == Number)
         count++;
       else{
        if(--count==0)
           Number = A[++k];
        }
      }
    }
    for(int i=0;i<n;i++)
     if(A[i]==Number)
       count++; 
    if(count > n/2)
      return Number;
    else
      return -1;
    
    展开全文
  • pta 数据结构 线性表习题

    千次阅读 多人点赞 2020-11-19 16:22:55
    学习使我快乐判断选择函数 判断 1-1 对于顺序存储的长度为N的线性表,访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。 T F 1-2 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入...

    学习使我快乐

    判断题

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

    • T
    • F

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

    • T
    • F

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

    • T

    • F

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

    • T

    • F

    选择题

    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个结点从小到大排序

    2-2 对于顺序存储的长度为N的线性表,访问结点和增加结点的时间复杂度为:
    A. O(1), O(1)

    B. O(1), O(N)

    C. O(N), O(1)

    D. O(N), O(N)

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

    B. 单循环链表

    C. 带头结点的双循环链表

    D. 顺序表

    2-4 顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )。

    A. 100

    B. 105

    C. 108

    D. 110

    2-5 下列函数中,哪两个函数具有相同的增长速度:

    A. 2N和N​N

    B. N和2/N

    C. N​2logN和NlogN​2

    D. NlogN​2和NlogN

    2-6 算法的时间复杂度取决于( )。

    A. 问题的规模

    B. 待处理数据的初态

    C. 计算机的配置

    D. A和B

    2-7 已知两个长度分别为m和n的升序链表,若将它们合并为一个长度为m+n的降序链表,则最坏情况下的时间复杂度是( )。

    A. O(n)

    B. O(mn)

    C. O(min(m,n))

    D. O(max(m,n))

    2-8 下列代码的时间复杂度是:

    for(i=0; i<N; i++)
        for(j=0; j<N; j+=1000)
            printf("%d,%d\n", i, j);
    

    A. O(N×j)

    B. O(N)

    C. O(N2)

    D. O(NlogN)

    2-9 下面程序段的时间复杂度是 ( )

    i = 0while(i<=n)
         i = i * 3

    A. O(2n)

    B. O(n)

    C. O(n​2)

    D. O(log​3n)

    2-10 程序段

    FOR  i:=n-1  DOWNTO  1  DO
                FOR j:=1 TO i DO
                   IF A[j]>A[j+1]
                      THEN  A[j]与A[j+1]对换;
    

    其中 n为正整数,则最后一行的语句频度在最坏情况下是( )

    A. O(n)

    B. O(nlogn)

    C. O(n3)

    D.O(n​2)

    2-11 下列叙述中正确的是

    A. 程序执行的效率与数据的存储结构密切相关

    B. 程序执行的效率只取决于程序的控制结构

    C. 程序执行的效率只取决于所处理的数据量

    D. 以上说法均错误

    函数题

    6-2 多项式求值
    本题要求实现一个函数,计算阶数为n,系数为a[0] … a[n]的多项式f(x)=∑ ni=0(a[i] × xi) 在x点的值。

    函数接口定义:

    double f( int n, double a[], double x );
    

    其中n是多项式的阶数,a[]中存储系数,x是给定点。函数须返回多项式f(x)的值。

    裁判测试程序样例:

    #include <stdio.h>
    #define MAXN 10
    double f( int n, double a[], double x );
    int main()
    {
        int n, i;
        double a[MAXN], x;
        scanf("%d %lf", &n, &x);
        for ( i=0; i<=n; i++ )
            scanf(%lf”, &a[i]);
        printf("%.1f\n", f(n, a, x));
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    

    输入样例:

    2 1.1
    1 2.5 -38.7
    

    输出样例:

    -43.1
    

    代码:

    double f( int n, double a[], double x ){
        double ans;
        for (int i = 0; i <= n; ++i) {
            ans+=a[i]*pow(x,i);
        }
        return ans;
    }
    

    **6-3 使用函数判断完全平方数 **
    本题要求实现一个判断整数是否为完全平方数的简单函数。

    函数接口定义:

    int IsSquare( int n );
    

    其中n是用户传入的参数,在长整型范围内。如果n是完全平方数,则函数IsSquare必须返回1,否则返回0。

    裁判测试程序样例:

    #include <stdio.h>
    #include <math.h>
    
    int IsSquare( int n );
    
    int main()
    {
        int n;
        scanf("%d", &n);
        if ( IsSquare(n) ) printf("YES\n");
        else printf("NO\n");
        return 0;
    }
    
    /* 你的代码将被嵌在这里 */
    

    输入样例1:

    10
    

    输出样例1:

    NO
    

    输入样例2:

    100
    

    输出样例2:

    YES
    

    代码

    int IsSquare( int n )
    {
        int h =pow(n,0.5);
        if(pow(h,2)==n)return 1;
        return 0;
    }
    
    展开全文
  • 线性表主要采用哪两种存储结构?它们是如何存储数据元素的? 各有什么优缺点? 答案一 线性表是由n个类型相同的数据元素组成的有限序列,其中,元素类型可以是基本类型或类; 主要采用的有顺序存储结构和链式存储结构 ...

    作业一

    什么是线性表?线性表主要采用哪两种存储结构?它们是如何存储数据元素的?

    各有什么优缺点?

    答案一

    线性表是由n个类型相同的数据元素组成的有限序列,其中,元素类型可以是基本类型或类;

    主要采用的有顺序存储结构和链式存储结构

    顺序存储结构

    是通过数据元素的存储对应一块连续的存储空间,数据元素之间的前驱和后续关系通过数据元素在存储器的相对位置来反映。

    链式存储结构

    数据元素的存储对应的是不连续的存储空间,每个存储节点对应一个需要存储的元素,,元素之间的逻辑关系通过存储节点之间的链接关系反映出来。

    顺序存储的优点和缺点

    优点:存储密度大(=1),存储空间利用率高

    缺点:插入或删除元素时不方便,内存占用大效率不高

    链式存储的优点和缺点

    优点:插入或删除元素时很方便,使用灵活。

    缺点:存储密度小(<1),存储空间利用率低。

    作业二

    为什么顺序表的插入和删除操作必须移动元素?平均需要移动多少元素?

    答案二

    顺序表是连续的,采用的顺序存储结构,那么就意味着在 插入与删除的时候都要将顺序表的顺序进行重新排列

    意味的是,在进行插入操作的时候,必须要将插入值之后的所有值的下标进行重新排列,那么就意味这要占用很大的内存空间去做这样的一件事;再删除操作的时候,也必须要将插入值之后的所有值进行重新排列,和插入操作一样,同样是要占用很大的内存空间

    如果在每一个位置插入元素的概率相同,那么意味着其要做的操作的时间复杂度为O(n),且平均需要移动的元素为n/2

    作业三

    采用单链表求解Josephus问题,写出关键使用的程序代码

    答案三

    问题是这样的,创建一个单链表,里面有n个数据,数据从s开始循环,循环数为d,做出的结构就是每次进行循环都删除一个数据。最后剩下的数据就是逃逸数据

    我将其实例化,瓜田里有n个西瓜,将其围成圆形,每次走过d个西瓜,从第s个西瓜开始吃,走过d个西瓜就将其脚下的吃掉。最后剩下的西瓜成为幸存瓜。

    设计思路

    用一个没有头节点的循环链表处理,先生成一个带有n个节点的单循环链表,然后从s 节点起,从1开始计数,记到d时,将其对应节点从链表中删除,然后被删除节点的下一个节点继续从1开始计数,只到剩下最后一个。

    代码部分

    首先我们肯定要先创建一个瓜的类,为了便于理解,将其命名成了“瓜”

    package Josephus;
    
    public class gua {
    	private int guanum;
    	private gua next;
    	
    	public gua(int num) {
    		this.guanum = num;
    	}
    	public int getGuanum() {
    		return guanum;
    	}
    	public void setGuanum() {
    		this.guanum = guanum;
    	}
    	public gua getNext() {
    		return next;
    	}
    	public void setNext(gua next) {
    		this.next = next;
    	}
    
    }
    

    现在开始编写一下first节点

    package Josephus;
    
    public class chigua {
    	gua first  = new gua(-1);
    }
    

    接下来我们向约瑟夫环里添加数据

    public void add(int num) {
    		if (num<1) {
    			System.out.println("你指定有点毛病,里面没瓜吃个啥");
    		}
    		//这一步是为了保证输入的数值正确并添加娱乐效果
    		gua temp = null;
    		for(int i =1;i<=num;i++) {
    			gua g = new gua(i);
    			if(i==1) {
    				first = g;
    				first.setNext(first);
    				temp = first;
    			}else {
    				temp.setNext(g);
    				g.setNext(first);
    				temp = g;
    				
    			}
    		}
    	}
    

    好,那么现在让约瑟夫环开始转圈

    public void zhuanquan(int start, int length, int guanum) {
    				if(start>guanum||start<1||first==null) {
    					System.out.println("能不能吃点阳间的瓜");
    				}
    				gua temp =first;
    				while(true) {
    					if(temp.getNext()==first) {
    						break;
    					}
    					temp=temp.getNext();
    				}
    				for(int i=0;i<start-1;i++) {
    					first=first.getNext();
    					temp=temp.getNext();
    				}
    				while(true) {
    					if(first==temp) {
    						break;
    					}
    					for(int j=0;j<length-1;j++) {
    						first=first.getNext();
    						temp=temp.getNext();
    					}
    					System.out.println("西瓜"+first.getGuanum()+"被吃掉了");
    					first=first.getNext();
    					temp.setNext(first);
    				}
    				System.out.println("最后留下的西瓜就是西瓜"+first.getGuanum());
    
    		
    		
    	}
    

    现在就是最简单的main函数的部分了,开始直接实例化并调用了,那么我们开始吃瓜吧

    package Josephus;
    
    public class test01 {
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		chigua g = new chigua();
    		g.add(100);
    		g.zhuanquan(1,3,5);
    }
    }
    
    展开全文
  • 数据结构 线性表习题

    2020-04-17 12:12:22
    数据结构 线性表 线性表是最常用且简单的一种数据结构。 typedef struct tagnde{ ElemType date; // 任意数目,组合,类型的数据成员; struct tagnode *Ptr; // 指针域 指向相邻结点 }linknode,*...
  • 数 据 结 构 计算机科学与技术学院 Page 2 2020-3-4 线性数据结构部分综合练习 若某线性表采用顺序存储结构每个元素占四个存储单元首地址为100则下标为11的(第12个)元素的存储地址为 线性表的链式存储结构主要包括 ...
  • 数据结构练习题——线性表

    千次阅读 2021-06-06 18:26:53
    一、判断正误 ( F )1. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。...二、单项选择 ( C )1.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为: (A)存储结构...
  • 这次博客做一个练习题,是我们学校的C++练习题,题目如下: 问题描述: 1)实现链表的排序(升序) 2)实现两个有序链表的合并:A=A∪B,要求合并后仍然有序。 提交前请将所有的提示信息去掉,只保留最后的输出...
  • 关于写这个系列的原因:本人今年考研上岸,加上在校期间学习《数据结构》这门课时候,对数据结构有了好感,对这门课考试的考点把握还不错,所以不想荒废自己的知识,就计划用这种方式总结起来。如果有理解不到位的...
  • 数据结构的顺序实现 3.顺序表 4.链表 5.数据结构的链接实现 6. 建表 7.字符串 8.串 9.顺序串 10.链串 二填空 1.为了便于讨论有时将含n(n>=0)个结点的线性结构表示成(aa,a)其中每个n12a代表一个_a称为_结点a称为_...
  • 今天给大家介绍几道常考的关于数据结构线性表习题。小小拙见,希望对你有帮助哦! 一、移除链表元素 问题描述 删除链表中等于给定值 val 的所有节点。 示例: 输入: 1->2->6->3->4->5->6, val = ...
  • 线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。 线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意...

空空如也

空空如也

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

数据结构线性表练习题

数据结构 订阅