精华内容
下载资源
问答
  • 在长度为n的顺序表的第i个位置上
    千次阅读
    2022-03-05 15:16:53

    在顺序表中,逻辑上相邻的两个元素物理存储上也一定相邻(对)

    线性表采用顺序存储,必须占用一段地址连续的存储单元(对)

    某顺序表的第一个元素的存储地址是500,每个元素占4个单元,则第8个元素的起始地址是(D)

    A.504 B.508 C.516 D.528

    长度为n的非空线性表采用顺序存储结构,在第i个元素前插入一个数据元素,i的合法值应该是(A)

    A.1<=i<=n+1 B.0<=i<=n+1 C.i>0 D.1<=i<=n-1

    在长度为n的顺序表中的第i(1<=i<=n+1)个元素前插入一个元素,需要移动的元素个数为(B)

    A.n-i B.n-i+1 C.i D.n-i-1

    在长度为n的顺序表中的第i(1<=i<=n+1)个元素前删除一个元素,需要移动的元素个数为(A)

    A…n-i B.n-i+1 C.n-i-1 D.i

    假设删除长度为n的顺序表中的每个元素的概率相同,则删除一个元素平均要移动的元素的个数是(D)
    A.n/2 B.(n+1)/2 C.n D.(n-1)/2

    在长度为n的顺序表中的第i(1<=i<=n+1)个元素前插入一个元素,其算法复杂度为(B)

    A.O(1) B.O(n)C.O(n*n) D.O(logn)(以2为底)

    在长度为n的顺序表中读取第i(1<=i<=n+1)个元素,其算法复杂度为(A)这道题考察的是getelem,不是定位操作locateelem

    A.O(1) B.O(n)C.O(n*n) D.O(logn)(以2为底)

    在长度为n的顺序表中删除第i(1<=i<=n+1)个元素,其算法复杂度为(B)
    A.O(1) B.O(n)C.O(n*n) D.O(logn)(以2为底)

    更多相关内容
  • 数据结构线性表/顺序表新增:在第i个位置插入元素e(动态表+静态表)

    1、顺序表新增:在第i个位置插入元素e

    静态顺序表:

    // 408_sxb.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
    //
    
    #include <iostream>
    using namespace std;
    #define eletype char
    #define maxsize 50
    
    typedef struct SList{
        eletype A[maxsize];
        unsigned lenth = 0;  //长度为定义无符号数
    }SList,*SSList;
    
    void initList(SSList L) {
        if (!L->A) {
            exit(OVERFLOW);
        }
        for (int i = 0; i < 10; i++)
        {
            L->A[i] = i+97;
            L->lenth++;
        }
    }
    
    void printSList(SSList L) {
        cout << "静态表:";
        for (int i = 0; i < L->lenth; i++) {
            cout << L->A[i]<<" ";
        }
        cout << endl;
    }
    
    void AddSList(SSList L,eletype e,int n) {
        for (int i = L->lenth-1; i >=n-1; i--) {
            L->A[i + 1] = L->A[i];
        }
        L->A[n-1] = e;
        L->lenth++;
    }
    
    int main()
    {
        SSList L = new SList;
        initList(L);
        printSList(L);
        AddSList(L, 'z', 4);
        printSList(L);
        return 0;
    }
    
    

    动态顺序表:
    **note:**动态顺序表的结点中的元素一开始没开辟其余的空间还需要自己定义;如不定义就会出现如下错误:
    在这里插入图片描述
    为了使其得要空间,我们可以使用该语句:L->D = (eletype*)malloc(maxsize * sizeof(eletype));
    对于动态链表我们还可以重新为其分配空间语句为:
    :eletype* p; p = (eletype*)realloc(L->D, (maxsize + addsize)*sizeof(eletype));

    // 408_sxb.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
    //
    
    #include <iostream>
    using namespace std;
    #define eletype char
    #define maxsize 50
    #define addsize 50
    
    typedef struct DList {
        eletype* D;
        unsigned length=0;
    }DList,*DDList;
    
    void InitDList(DDList L) {
        if (!L->D)
        {
            exit(OVERFLOW);
        }
    
        if (L->length == maxsize) {
            eletype* p;
            p = (eletype*)realloc(L->D, (maxsize + addsize)*sizeof(eletype));
        }
    
        for (int i = 0; i < 10; i++) {
            //*(L->D + i) = i + 97;
            L->D[i] = i + 97;
            L->length++;
        }
    }
    
    void printDList(DDList L) {
        cout << "动态表:";
        for (int i = 0; i < L->length; i++) {
            cout << *(L->D+i)<<" ";
        }
        cout << endl;
    }
    
    void AddDList(DDList L,int n,eletype e) {
        for (int i = L->length; i >= n - 1; i--) {
            *(L->D + i + 1) = *(L->D + i);
        }
        L->D[n - 1] = e;
        L->length++;
    }
    
    int main()
    {
        DDList L = new DList;
        L->D = (eletype*)malloc(maxsize * sizeof(eletype));
        InitDList(L);
        printDList(L);
        AddDList(L,5,'z');
        printDList(L);
    
        return 0;
    }
    
    
    展开全文
  • 在长度为n的(),删除元素,其算法的时间复杂度O(n) A.只有表头指针的不带表头结点的循环单链表 B.只有表尾指针的不带表头结点的循环单链表 C.只有表尾指针的带表头结点的循环单链表 D.只有表头指针的带...

    在长度为n的()上,删除第一个元素,其算法的时间复杂度为O(n)
    A.只有表头指针的不带表头结点的循环单链表
    B.只有表尾指针的不带表头结点的循环单链表
    C.只有表尾指针的带表头结点的循环单链表
    D.只有表头指针的带表头结点的循环单链表

    答案:A

    分析:
    单链表只能按单方向顺序访问节点,按题目意思,只有当A条件时,并当新元素的节点从表头插入,使得第一个元素的节点在表尾,才成立。这样表头指针顺序访问节点,访问至链表尾部时,复杂度刚好为O(n)。
    在这里插入图片描述
    对于B而言,不带头节点循环链表,表尾指针,如果是头插法则第一元素就是表尾指针rear(假设表尾指针为rear)所指的节点,即当前节点,时间复杂度为O(1)。如果是正常顺序插入节点(即非头插法),由于是循环链表,表尾指针rear指向最后一个元素,rear->next即为第一个元素(因为循环链表,表尾的next是表头,且没有头节点),时间复杂度仍然是O(1),所以B不成立。
    对于C而言,和B情况相似,多了一个表头节点,如果是头插法,则和B一样表尾指针rear所指当前元素即为第一个元素,时间复杂度为O(1)。如果是正常顺序插入节点,则比B多一个头节点,就变成rear->next->next,但时间复杂度仍然是O(1),所以C不成立。
    对于D而言,比A多一个头节点,虽然当头插法时时间复杂度为O(n+1),根据次数化解原则,就为O(n),但是答案不是选D(我也不是很清楚,老师讲解时直接跳过没有解释清楚,希望大佬评论解答,感激!!!)

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

    题目要求:

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

    /*对长度为n的顺序表L,编写一个时间复杂度为O(n),空间复杂度为O(1)的算法
    该算法删除线性表中所有值为x的数据元素*/
    #include <iostream>
    #include <cstring>
    #include<math.h>
    #define MAXSIZE 20
    #define ElemType int//不加分号
    using namespace std;
    typedef struct {
    	ElemType data[MAXSIZE];
    	int length;
    }SqList;
    bool InitList(SqList &L) {
    	memset(L.data, 0, sizeof(L));
    	if (!L.data)
    		exit(0);
    	L.length = 0;
    	return true;
    }
    void CreateList(SqList &L, int n) {
    	for (int i = 0;i<n;i++) {
    		cin >> L.data[i];
    		L.length++;
    	}
    }
    bool DeleteX(SqList &L,ElemType e) {//推荐做法,更容易想
    	//注释部分的做法没有达到空间复杂度为o(1),也不会满足时间复杂度要求
    	/*int x[MAXSIZE];
    	int j=-1;
    	memset(x, 0, sizeof(x));*/
    	int k=0;//用k来记录所有值不是x的元素的下标,边扫描边统计k,并将不等于x的元素向前移动k个位置,最后修改L的长度
    	for (int i = 0;i <L.length;i++) {
    		if (L.data[i] != e) {
    			/*j++;
    			x[j] = i;*/
    			L.data[k] = L.data[i];
    			k++;
    		}
    		
    	} 
    	L.length = k;
    	return true;
    }
    void DeleteX2(SqList &L, ElemType e) {
    	int k = 0, i = 0;//用k来记录等于x的元素的个数,边扫描L边统计k,并将不等于x的元素前移k个位置,最后修改L的长度
    	while (i<L.length)
    	{
    		if (L.data[i] == e)
    			k++;//用k来记录等于x的元素的个数,边扫描L边统计k
    		else
    			L.data[i - k] = L.data[i];//将不等于x的元素前移k个位置
    		i++;
    	}
    	L.length -= k;//修改L的长度
    }
    void PrintList(SqList L) {
    	cout << "表中元素分别为";
    	for (int i = 0;i<L.length;i++)
    		cout << L.data[i] << "  ";
    	cout << endl;
    }
    int main() {
    	SqList L;
    	InitList(L);
    	int n = 0;
    	cout << "请输入要创建的表的长度:" << endl;
    	cin >> n;
    	cout << "请依次输入各个元素:(用空格隔开)" << endl;
    	CreateList(L, n);
    	cout << "请输入想要删除元素的值(即x的值):" << endl;
    	ElemType e;
    	cin >> e;	
    	DeleteX2(L,e);
    	PrintList(L);
    	return 0;
    }

     

    展开全文
  • 在顺序表个位置插入一元素9,实现顺序表插入的基本操作,输出顺序表中所有元素 #include&lt;iostream&gt; using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef...
  • 1.2.3 从顺序表中删除元素

    千次阅读 2021-05-24 05:36:22
    所谓删除长度为n顺序表中的第i个位置的元素,就是指将顺序表第i个位置上的元素去掉。例如顺序表为:删除第i个位置的元素后,该顺序表变为:而此时顺序表A的长度n变为n-1。下面给出从静态顺序表中删除第i个位置...
  • /*对长度为n顺序表L,编写一时间复杂度O(n),空间复杂度O(1)的算法,该算法删除线性表中所有值x的数据元素*/ #define MAXSIZE 50 typedef int ElemType; typedef struct{ ElemType data[MAXSIZE]; int ...
  • c语言实现顺序表的基本操作

    千次阅读 2021-05-23 11:53:27
    原作者:Step by Step经过三天的时间终于把顺序表的操作实现搞定了。(主要是测试部分停留了太长时间)1;线性表顺序存储的概念:指的是内存...顺序表的定义及操作集合:头文件defs.h1 #ifndef _DEFS_H2 #defi...
  • N个元素的顺序表可插入的位置N+1, 移动次数总数0+1+2…+n=(0+n)*(n+1)/2 平均次数 总数/(N+1)= n/2
  • 在顺序表中删除指定位置i=5)的元素,实现顺序表的删除的基本操作,输出顺序表中所有元素 #include&lt;iostream&gt; using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef ...
  • 题目:长度为n顺序表L,编写一时间复杂度O(n),空间复杂度O(1)的算法,该算法删除线性表中所有值x的数据元素。 思想: 记录等于X的值的个数i,遇到不是X的位置就把值放到前面i个位置上 代码展示: #...
  • 【数据结构功法】3话 · 顺序表快速入门

    千次阅读 多人点赞 2022-03-29 22:07:53
    从今天开始,我将正式开启一新的打卡专题——【数据结构·水滴计划】,没错!这是今年半年的一整个系列计划!本专题目的是通过百天刷题计划,通过题目和知识点串联的方式,刷够1000道题!完成对数据结构相关知识...
  • 顺序表指定位置插入元素

    千次阅读 2019-04-26 12:35:33
    本题要求实现一函数,在顺序表第i个位置插入一新的数据元素e,插入成功后顺序表长度加1,函数返回值1;插入失败函数返回值0;函数接口定义: int ListInsert(SqList &L,int i,ElemType e); 其中...
  • //已知顺序表L的长度为n,试编写算法实现在顺序表中删除值elem的数据元素 //(其中n与elem从键盘输入) # include <iostream> # include <stdio.h> # include <stdlib.h> using namespace std; ...
  • 【单选题】在长度为 n顺序表中进行顺序查找,查找失败时需与键值比较次数是 ( ) 。【单选题】一具有n个顶点e条边的图中,所有顶点的度数之和等于 ( )。(5.0分)【填空题】假设有序线性表a[20]进行折半查找,则...
  • 长度为n顺序表L,编写一时间复杂度O(n),空间复杂度O(1)的算法,该算法删除线性表中所有值x的数据元素。 算法思想: 一步:从前往后扫描顺序表,用k纪录当前值x的数据元素的个数 二步:如果扫描...
  • 将两个顺序表合并新的顺序表

    千次阅读 多人点赞 2020-09-04 00:23:58
    问题描述:将两有序顺序表合并新的有序顺序表,并有函数返回结果顺序表。要求时间复杂度O(n) 算法设计思想:首先,按顺序取两个顺序表表头较小的结点存入新的线性表中直到某一表遍历完;然后将还有剩余...
  • typedef struct { int len; type data[MAX]; }sqList; int delsameele3...{ //每遍历一元素时都考虑其向前移动的位数 int k=0; for(int i=0;i&lt;a-&gt;len;i++) if(a-&gt;data[i]!=x) a-...
  • 顺序表中查找元素

    千次阅读 2021-03-12 15:49:16
    题目告知这是一递增有序,要使时间最少,我们可以采取折半查找的方式,这样比顺序查找省时。 代码如下: #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> int findAndExchange(int* arr,int n,...
  • 算法设计思想:用k记录顺序表中不等于x的元素数,即需要保存的元素数,边扫描L边统计k,并将不等于x的元素放在L.data[k]中,最后修改L的长度。 代码及结果: #include<stdio.h> #include "线性表的...
  • 例、设计一删除算法,删除顺序表L中的第i个位置的元素,用引用变量返回。 思路: 由于这函数删除后顺序表L有变,所以L前要有&,且我们要返回的变量一开始初始值0,它也是变化的,所以该变量前面也要加引用...
  • SqListDemo.c/* 线性表的顺序存储实现 */#include#include#include// 定义符号常量#define LIST_INIT_SIZE 50#define LISTINCREMENT 10#define OK 1#define ERROR 0#define OVERFLOW -2// ...// 定义顺序表类型type...
  • 顺序表的基本操作

    千次阅读 2022-04-24 13:38:18
    (4)在指定位置插入元素,即在第i个元素前面插入值x的元素; (5)删除指定元素,即删除第i个元素; (6)删除顺序表中所有值在[x,y]范围内的元素,要求时间复杂度达到O(n); (7)单值化操作,即删除表中重复...
  • #include <iostream> using namespace std; //定义存储 typedef struct LNode { int date; struct LNode *next; } Lnode, *Linklist; //链表初始化 ... //头节点置空 } //输出数据 void output(Li
  • 顺序表的操作实验(数据结构)

    千次阅读 2021-02-21 21:48:47
    2.在顺序表上实现插入、删除和查找操作(验证性内容)。 3.删除有序顺序表中的重复元素(设计性内容)。 4.完成一简单学生成绩管理系统的设计(应用性设计内容)。 四、实验的软硬件环境要求 1.硬件环境要求...
  • 线性表的顺序存储结构——顺序表

    千次阅读 2018-12-13 20:01:48
    顺序表是用一段地址连续的存储单元依次存储线性表的数据元素,因为线性表中每元素的类型相同,通常用一维数组来实现线性表,也就是把线性表中相邻的元素存在数组中相邻的位置(即用物理位置来表现元素间的关系).....
  • 它是用一组地址连续的存储单元依次存储线性表中的数据元素,使得逻辑相邻的两元素物理位置上也相邻。  顺序表的特点: 随机访问。通过首地址和元素序号可时间O(1)内找到指定元素。 存储密度高。每结点...
  • 目录前言一、顺序表的定义二、顺序表的初始化三、顺序表的建立四、顺序表的输出五、顺序表的逆序输出六、顺序表的插入操作七、...顺序表特定区间的元素(四)删除顺序表中重复元素(五)删除有序表中重复元素十、...
  • 顺序表的操作实验

    千次阅读 2021-03-17 20:13:11
    1.建立含n个数据元素的顺序表并输出该表中各元素的值。 2.有序顺序表L中插入元素x使线性表仍然有序。 3.写一函数删除有序顺序表中的重复元素。 四、知识准备 前期要求熟练掌握了C语言的编程规则、方法
  • 顺序表删除元素操作

    千次阅读 2021-09-17 12:26:08
    第i个位置的结点,就是下标为i-1的把他删除 个位置第n个位置都是可以的,不范围内的就不对 不需要就不保留,删了就删了 线性表L上面,删除结果仍由线性表保存 从我们删除的这个位置上...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 269,687
精华内容 107,874
热门标签
关键字:

在长度为n的顺序表的第i个位置上