itgle.com
已知一个长度为n的单链表中所有节点是递增有序的，以下叙述中正确的是 _______。A．插入一个节点使之有序的算法的时间复杂度为O(1)B．删除最大值节点使之有序的算法的时间复杂度为 O(1)C．找最小值节点的算法的时间复杂度为 O(1)D．以上都不对
题目
已知一个长度为n的单链表中所有节点是递增有序的，以下叙述中正确的是 _______。
A．插入一个节点使之有序的算法的时间复杂度为O(1)
B．删除最大值节点使之有序的算法的时间复杂度为 O(1)
C．找最小值节点的算法的时间复杂度为 O(1)
D．以上都不对
相似考题
更多“已知一个长度为n的单链表中所有节点是递增有序的，以下叙述中正确的是 _______。”相关问题
-
第1题：
● 将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较 (24) 次。
(24) A．1
B．n-1
C．n
D．2n
正确答案：C
【解析】考生首先要明白两个前提：一是要归并的两个表都是递增有序的，且长度都为n，二是题目问的是最少的关键字比较次数，即最好的情况下的比较次数。而最好的情况应该是：一个表的所有关键字都大于(或小于)另一个表的所有关键字，如：(1 2 3 4)与(5 6 7 8)。比较的时候有两个指针分别指向两个表的第一个元素，由于一个表的关键字要都大于另一个表的关键字，所以关键字小的表中的元素挨个与关键字大的表的第一个元素比较后，先被并入到新表中，这时关键字大的表的指针还是指向第一个元素没变，此时只需将关键字大的表复制到新表中即可。所以花费的比较次数就是关键字小的表长，也就是n。 -
第2题：
下列叙述中正确的是( )。
A．对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n
B．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(n／2)
C．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为(log2(下标)n)
D．对长度为n的有序链表进行对分查找，最坏情况—卜需要的比较次数为(nlog2(下标)n)
正确答案：C
解析：二分法查找只适用于顺序存储的有序表，对于长度为n的有序线性表，最坏情况只需比较log2n次。 -
第3题：
●在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是 (53) 。
(53) A．O(1)
B．O(n)
C．O(nlogn)
D．O(n2)
正确答案：B【解析】本题主要考核有序单链表上的插入操作及算法分析。对数据结构的任何操作都不能改变其原有的结构特性。因此，在有序单链表中插入一个新结点后，仍然要保持它的有序性。
插入操作的关键是查找插入位置，主要时间也是花在插入位置的查找上。n个结点的单链表，有，n+1个可能插入的位置，即第一个结点之前和每一个结点之后。在第一个结点之前插入，需比较一次；在第一个结点之后插入需比较两次；…；在第，n个结点之后插入需查找次。如果在每一个位置上作插入的概率相等，即
，则在有序单链表上查找插入位置的平均比较次数为：
-
第4题：
将长度为m的单链表连接在长度为n的单链表之后,单链表的长度为()。A、m+n
B、m*n
参考答案：A
-
第5题：
已知线性表中的元素以值递增有序排列,并以单链表作存储结构(不带表头节点)。试写一算法,删除表中所有大于x且小于y的元素(若表中存在这样的元素)同时释放被删除结点空间。参考答案：#include #include typedef struct list{ int data; struct list *next; }list; void fun(list *head,int list*pre,*p; pre=head; p=pre->next; while(p){ if(p->data>x&&p->datanext=p->next; p=pre->next; else{pre=pre->next; p=pre->next; voidf(type* list,int length) inttop=length; int base=0; type tmp; while(top>base) tmp=list[top];list[top]=list[base]; list[base]=tmp; top--; base++;
-
第6题：
在一个长度为n(n>1)的带头结点的单链表head上,另设有尾指针r(指向尾结点),执行()操作与链表的长度有关。A.删除单链表中的第一个元素
B.删除单链表中的尾结点
C.在单链表的第一个元素前插入一个新结点
D.在单链表的最后一个元素后插入一个新结点
参考答案：B
-
第7题：
将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较(50)次。
A．I
B．n-1
C．n
D．2n
正确答案：C
解析：将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较n次，一个递增有序表的最小元素大于等于另一个递增有序表的最大元素。 -
第8题：
下列叙述中正确的是
A．对长度为n的有序链表进行查找，最坏情况下需要比较的次数为n
B．对长度为n的有序链表进行对分查找，最坏情况下需要比较的次数为n/2
C．对长度为n的有序链表进行对分查找，最坏情况下需要比较的次数为log2n
D．对长度为n的有序链表进行对分查找，最坏情况下需要比较的次数为nlog2n
正确答案：A
解析：有序链表中定位元素需要通过指针逐个查找，所以对分查找的意义不大。选项A正确。 -
第9题：
将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较(64)次。
A．1
B．n-1
C．n
D．2/9
正确答案：C
解析：显然当一个表的所有字符都小于另一个表的所有字符的时候，比较的次数最少。这时，只需把其中一个表的每个字符与另一个表中的每一个字符比较一次，即共需比较n次。 -
第10题：
将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要进行关键字比较(38)次。
A．n
B．n2-1
C．2n-1
D．2n2
正确答案：A
解析：由于两个表有序，最少比较是一个表的最大结点，比另一个表的所有结点小。如{1，2，3}和{4，5，6}。我们只要将表中第一个结点(最小结点)，和另个表中所有结点比较，比较次数为另个表的表长。 -
第11题：
在一个长度为n(n＞1)的带头结点单链表h上，另设有尾指针r(指向尾结点)。与链表的长度有关的操作是()。A.删除单链表中的第一个元素
B.删除单链表中的最后一个元素
C.在单链表第一个元素前插入一个新元素
D.在单链表最后一个元素后插入一个新元素答案：B解析：在单链表中要删除最后一个元素必须找到尾结点的前驱结点的指针。由于单链表只能访问结点的下一个结点，所以根据尾指针不能够直接找到它的前驱结点，只有从头开始依次向下找到尾结点的前驱结点。所以删除单链表中的最后一个元素与链表的长度有关。 -
第12题：
建立一个长度为n的有序单链表的时间复杂度为()
答案：C解析：建立有序单链表的时间复杂度是O(n)，对单链表插入节点时，先遍历单链表，找到插入位置，将节点插入。 -
第13题：
在一个长度为n（n＞1）的单链表上，设有头和尾两个指针，执行()操作与链表的长度有关。
A.删除单链表中的第一个元素
B.删除单链表中的最后一个元素
C.在单链表第一个元素前插入一个新元素
D.在单链表最后一个元素后插入一个新元素
正确答案：B
-
第14题：
（ 1 ）下列叙述中正确的是
A ）对长度为 n 的有序链表进行查找，最坏清况下需要的比较次数为 n
B ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ n/2 ）
C ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ log 2 n ）
D ）对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ nlog 2 n ）
正确答案：C
-
第15题：
在______中，只要指出表中任何一个节点的位置，就可以从它出发访问到表中其他所有的节点。
A．线性单链表
B． 双向链表
C． 线性链表
D． 循环链表
正确答案：D
解析： 在循环链表中，只要指出表中任何一个节点的位置，就可以从它出发访问到表中其他所有的节点，而线性单链表做不到这一点。 -
第16题：
有n个节点的单链表中,算法的时间复杂度是O(1)的操作是()A、访问第i个节点(1≤i≤n)
B、在第i个节点后插入一个新节点(1≤i≤n)
C、访问值为x的节点
D、将n个节点从小到大排序
参考答案：B
-
第17题：
已知一个长度为n的单链表中的所有结点是有序(递增)的,以下叙述中正确的是()。A.插入一个结点使之有序的算法的时间复杂度为O(1)
B.删除最大值结点使之有序的算法的时间复杂度为O(1)
C.找最小值结点的算法的时间复杂度为O(1)
D.以上都不对
参考答案：C
-
第18题：
设带头结点的单链表(L为头指针)中的数据元素递增有序。设计算法,将x插入到链表的适当位置上,并仍保持该表的有序性。参考答案：
-
第19题：
下列叙述中，正确的是
A．对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n
B．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（n／2）
C．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（log2n）
D．对长度为n的有序链表进行对分查找，最坏情况下需要的比较次数为（nlog2n）
正确答案：A
解析：对长度为n的有序链表进行查找，最坏情况是从最小值开始查找最大值(或从最大值开始查找最小值)，这个过程需要比较的次数为n，故选项A正确。对分查找只能针对随机存取的有序表进行，而有序链表只能进行顺序存取，不能进行随机存取，在有序链表上不能进行对分查找，故B、C、D选项都错误。 -
第20题：
在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是(53)。
A．O(1)
B．O(n)
C．O(nlogn)
D．O(n2)
正确答案：B
解析：本题主要考核有序单链表上的插入操作及算法分析。对数据结构的任何操作都不能改变其原有的结构特性。因此，在有序单链表中插入一个新结点后，仍然要保持它的有序性。插入操作的关键是查找插入位置，主要时间也是花在插入位置的查找上。n个结点的单链表，有，n+1个可能插入的位置，即第一个结点之前和每一个结点之后。在第一个结点之前插入，需比较一次；在第一个结点之后插入需比较两次；……；在第，n个结点之后插入需查找次。如果在每一个位罩上作插入的概率相等，即则在有序单链表上查找插入位置的平均比较次数为： -
第21题：
将两个长度为n的递增有序表归并成一个长度为2n的递增有序表，最少需要关键字间的(30)次比较。
A．1
B．n-1
C．n
D．2n
正确答案：C
-
第22题：
（ 1 ）下列叙述中正确的是
A ） 对长度为 n 的有序链表进行查找，最坏情况下需要的比较次数为 n
B ） 对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为（ n /2 ）
C ） 对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为 （ log 2 n ）
D ） 对长度为 n 的有序链表进行对分查找，最坏情况下需要的比较次数为 （ n log 2 n ）
正确答案：A
-
第23题：
设一个有序的单链表中有n个节点，现要求插入一个新节点后使得单链表仍然保持有序，则该操作的时间复杂度为()。
答案：C解析：对单链表进行插入节点的操作，就是对单链表进行查找，找到节点需要插入的位置，然后修改指针，将节点插入单链表。 -
第24题：
在一个长度为n（n＞1）的单链表上，设有头和尾两个指针，执行（）操作与链表的长度有关。
- A、删除单链表中的第一个元素
- B、删除单链表中的最后一个元素
- C、在单链表第一个元素前插入一个新元素
- D、在单链表最后一个元素后插入一个新元素
正确答案:B