首页 > 其他分享 >数据结构:线性表-例题

数据结构:线性表-例题

时间:2024-07-21 12:18:07浏览次数:13  
标签:结点 例题 线性表 复杂度 next 链表 单链 数据结构 指针

  1. 顺序存储结构和链式存储结构都可以进行顺序存取。[T/F]

顺序存储结构可以进行顺序存取和随机存取;
链式存储结构只可以进行顺序存取。

  1. 散列存储结构能反应数据之间的逻辑关系。[T/F]

散列存储通过散列函数映射到物理空间,不能反应数据之间的逻辑关系。

  1. 链式存储设计时,结点内的存储单元地址不一定连续。[T/F]

链式存储设计师,各个不同结点的存储空间可以不连续,但结点内的存储单元地址必须连续

4.在一个设有头指针和尾指针的单链表中,删除表尾元素的时间复杂度与表长无关 [T/F]

必须从头开始找到表尾结点的前驱,其时间与表长有关

5.设线性表有n个元素,删除所有值为x的元素在单链表上实现要比顺序表上实现效率更高[T/F]

该操作在单链表和顺序表上实现的时间复杂度都为\(O(n)\),但后者要移动很多元素,因此单链表上效率更高。

  1. 给定有n个元素的一维数组,建立一个有序单链表的最低时间复杂度是?

方法一:先建立链表,再依次拆元素建立有序表,则每插入一个元素就需要遍历链表寻找插入位置,时间复杂度为\(O(n^2)\)
方法二:先将数组拍好序,再构建链表。数组排序的最好时间复杂度是\(O(nlogn)\),构建链表的时间复杂度是\(O(n)\),故该方法的时间复杂度为\(O(nlogn)\)
故最低时间复杂度是\(O(nlogn)\)

  1. 对于带头结点和不带头结点的单链表,判空条件分别为?

带头结点:head->next==NULL
不带头结点:head==NULL

  1. 为了方便插入和删除数据,可以使用双链表存放数据 [T/F]

采用双链表能很方便地方问前驱和后继。

  1. 设有两个长度为n的循环单链表,若要求两个循环单链表的头尾相接的时间复杂度为O(1),则对应两个寻环单链表各设置一个指针,分别指向()

无论哪种相接方式,循环单链表相接过程中,都需要知道两个链表各自的头结点和尾结点。又因为要求时间复杂度为O(1),所以两个指针都应指向尾结点

  1. 已知头指针h指向一个带头结点的非空单循环链表,结点结构为[data|next],其中next是指向直接后继结点的指针,p是尾指针,q是临时指针。现要删除该链表的第一个元素,正确的语句序列是?
    A. h->next=h->next->next; q=h->next; free(q)
    B. q=h->next; h->next=h->next->next; free(q)
    C. q=h->next; h->next=q->next; if(p!=q) p=h; free(q);
    D. q=h->next; h->next=q->next; if(p==q) p=h; free(q);

正确答案为D。注意到循环双链表的尾结点在表空时为头结点,否则为最后一个结点。因此对于只有一个结点的循环双链表,删除结点操作需要特殊处理。选项C没有针对该情形做处理。

标签:结点,例题,线性表,复杂度,next,链表,单链,数据结构,指针
From: https://www.cnblogs.com/SXWisON/p/18306872

相关文章

  • 【软考】数据结构与算法基础 - 数组和链表
    一、数组和链表的区别(很简单,但是很常考,记得要回答全面)什么是数组:C++语言中,可以用数组,处理一组数据类型相同的数据,不可以动态定义数组的大小(使用前,必须指定大小。)在实际应用中,用户使用数组之前,无法确定数组的大小只能够将数组定义成足够大小,多余出来空间可能不被使用,......
  • 【数据结构】栈和队列
    数据结构是计算机存储、组织数据的方式。栈和队列是两种常用的线性数据结构,它们在程序设计中扮演着重要角色。一、栈(Stack)栈是一种遵循后进先出(LastInFirstOut,LIFO)原则的数据结构。其主要特点如下:1.基本操作:栈的操作主要有两种——压栈(push)和出栈(pop)。压栈:在栈顶插......
  • 用于匹配两个数据列表中的项目的高效数据结构 - python
    我有两个列表,其中一个列表填充ID,另一个列表填充进程名称。多个进程名称可以共享一个ID。我希望能够创建一个可以使用特定ID的数据结构,然后返回与该ID关联的进程列表。我还希望能够使用特定的进程名称并返回与其连接的ID列表。我知道我可以为此创建一个字典,但是I......
  • Java之集合底层-数据结构
    Java集合之数据结构1概述数据结构是计算机科学中研究数据组织、存储和操作的一门学科。它涉及了如何组织和存储数据以及如何设计和实现不同的数据操作算法和技术。常见的据结构有线性数据结构(含数组、链表、栈和队列等),非线性数据结构(树、图等)。注意:不同的数据结构适用于......
  • 如何建立一颗二叉树?(数据结构:树 + hash表 / 广搜BFS)
    一个二叉树,树中每个节点的权值互不相同。现在给出它的后序遍历和中序遍历,请你输出它的层序遍历。输入格式第一行包含整数 N,表示二叉树的节点数。第二行包含 N 个整数,表示二叉树的后序遍历。第三行包含 N 个整数,表示二叉树的中序遍历。输出格式输出一行 N 个整数,......
  • Known框架实战演练——进销存数据结构
    系统主要包含商品信息、商业伙伴(客户、供应商)信息、业务单表头信息、业务单表体信息、对账单表头信息、对账单表体信息。1.商品信息(JxGoods)该表用于存储公司商品信息。名称代码类型长度必填商品信息JxGoods商品编码CodeText50Y商品名称NameText2......
  • 【数据结构】二叉树———Lesson2
    Hi~!这里是奋斗的小羊,很荣幸您能阅读我的文章,诚请评论指点,欢迎欢迎~~......
  • 几种基本数据结构
    目录前言线性结构链式结构单链表双链表​编辑树形结构前言在我们编写程序时,经常会出现需要存储数据的情况,而数据的存储是有讲究的,数据不是在我们的内存中胡乱存储,为了保证数据在进行修改和查找时更加方便,我们就要学习数据结构(也就是数据的存储结构)线性结构线性结......
  • 数据结构(二叉树-1)
    文章目录一、树1.1树的概念与结构1.2树的相关术语1.3树的表示二、二叉树2.1二叉树的概念与结构2.2特殊的二叉树满二叉树完全二叉树2.3二叉树的存储结构三、实现顺序结构二叉树3.1堆的概念与结构3.2堆......
  • 数据结构 - HashSet
    概述java.util.Set接口和java.util.List接口一样,同样继承自Collection接口,它与Collection接口中的方法基本一致,并没有对Collection接口进行功能上的扩充,只是比Collection接口更加严格了。与List接口不同的是,Set接口中元素无序,并且都会以某种规则保证存入的元素不出......