- 顺序存储结构和链式存储结构都可以进行顺序存取。[T/F]
顺序存储结构可以进行顺序存取和随机存取;
链式存储结构只可以进行顺序存取。
- 散列存储结构能反应数据之间的逻辑关系。[T/F]
散列存储通过散列函数映射到物理空间,不能反应数据之间的逻辑关系。
- 链式存储设计时,结点内的存储单元地址不一定连续。[T/F]
链式存储设计师,各个不同结点的存储空间可以不连续,但结点内的存储单元地址必须连续
4.在一个设有头指针和尾指针的单链表中,删除表尾元素的时间复杂度与表长无关 [T/F]
必须从头开始找到表尾结点的前驱,其时间与表长有关
5.设线性表有n个元素,删除所有值为x的元素在单链表上实现要比顺序表上实现效率更高[T/F]
该操作在单链表和顺序表上实现的时间复杂度都为\(O(n)\),但后者要移动很多元素,因此单链表上效率更高。
- 给定有n个元素的一维数组,建立一个有序单链表的最低时间复杂度是?
方法一:先建立链表,再依次拆元素建立有序表,则每插入一个元素就需要遍历链表寻找插入位置,时间复杂度为\(O(n^2)\)
方法二:先将数组拍好序,再构建链表。数组排序的最好时间复杂度是\(O(nlogn)\),构建链表的时间复杂度是\(O(n)\),故该方法的时间复杂度为\(O(nlogn)\)
故最低时间复杂度是\(O(nlogn)\)
- 对于带头结点和不带头结点的单链表,判空条件分别为?
带头结点:
head->next==NULL
不带头结点:head==NULL
- 为了方便插入和删除数据,可以使用双链表存放数据 [T/F]
采用双链表能很方便地方问前驱和后继。
- 设有两个长度为n的循环单链表,若要求两个循环单链表的头尾相接的时间复杂度为
O(1)
,则对应两个寻环单链表各设置一个指针,分别指向()
无论哪种相接方式,循环单链表相接过程中,都需要知道两个链表各自的头结点和尾结点。又因为要求时间复杂度为
O(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);
标签:结点,例题,线性表,复杂度,next,链表,单链,数据结构,指针 From: https://www.cnblogs.com/SXWisON/p/18306872正确答案为D。注意到循环双链表的尾结点在表空时为头结点,否则为最后一个结点。因此对于只有一个结点的循环双链表,删除结点操作需要特殊处理。选项C没有针对该情形做处理。