工学
填空题在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从（）进行查找任何一个元素。
题目
相似问题和答案
第1题：
● 单向链表中往往含有一个头结点，该结点不存储数据元素，一般令链表的头指针指向该结点，而该结点指针域的值为第一个元素结点的指针。以下关于单链表头结点的叙述中，错误的是 （60） 。
（60）A. 若在头结点中存入链表长度值，则求链表长度运算的时间复杂度为O(1)
B. 在链表的任何一个元素前后进行插入和删除操作可用一致的方式进行处理
C. 加入头结点后，代表链表的头指针不因为链表为空而改变
D. 加入头结点后，在链表中进行查找运算的时间复杂度为O(1)
正确答案：D
试题（60）分析
本题考查数据结构基础知识。
含有头结点的单链表如下图所示
在链表中加入头结点后，查找表中某一元素仍然要从头指针出发，顺序找到目标元素或失败时找到表尾为止，时间复杂度与表长成正比。
第2题：
在(58)存储结构中，在元素的存储结构之上另外建立一个元素与其存储位置之间的映射关系。
A．索引(Index)
B．散列(Hash)
C．链表(Link)
D．顺序(Sequence)
解析：索引存储是指在元素的存储结构之上另外建立一个元素与其存储位置之间的索引表。在散列存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系。链表存储结构中，通过节点中的指针映射元素之间的逻辑关系。顺序存储是指逻辑上相邻的元素其存储位置也相邻。
第3题：
在一个长度为n（n＞1）的单链表上，设有头和尾两个指针，执行()操作与链表的长度有关。
A.删除单链表中的第一个元素
B.删除单链表中的最后一个元素
C.在单链表第一个元素前插入一个新元素
D.在单链表最后一个元素后插入一个新元素
第4题：
折半(二分)查找方法对查找表的要求是( )。
A．链表存储结构，元素有序排列
B．链表存储结构，元素无序排列
C．顺序存储结构，元素有序排列
D．顺序存储结构，元素无序排列
解析：二分查找也叫折半查找，其基本思想是：以处于中间位置元素的关键字和给定值比较，如果相等，则查找成功。如果给定值大于中间位置元素，则下一次在后半个子表进行二分查找。如果给定值小于中间位置元素，则下一次在前半个子表进行二分查找。这样通过逐步缩小范围，直到查找成功或子表为空时失败为止。显然，如果要查找的表是无序排列，则查找就没有意义。另外，查找需要能直接定位表中间位置的元素，即实现随即访问，因此只有顺序存储结构能满足此要求，在链表上只能顺序查找。【总结与扩展】二分查找在查找成功时和给定值进行比较的关键字格式至多为[log2n]+1。二分查找在查找不成功时和给定值进行比较的关键字格式最多也不会超过[log2n]+l。当查找的表元素值较大时，二分查找的平均查找长度为log2(n+1)-1。二分查找要求查找表进行顺序存储并且按照关键字有序排列，因此当对表进行元素插入或删除时，需要移动大量的元素。所以二分查找适用于表不易变动，且又经常进行查找的情况。
第5题：
（3）下列叙述中错误的是A. 线性链表的各元素在存储空间中的位置必须是连续的 B.线性链表的头元素一定存储在其元素的前面 C.线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面 D.线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的
【解析】在线性链表中，各元素在存储空间中的位置是任意的，各元素的顺序也是任意的，依靠指针来实现数据元素的前后件关系。
第6题：
下列叙述中正确的是（ ）。
A)线性链表的各元素在存储空间中的位置必须是连续的
B)线性链表的头元素一定存储在其他元素的前面
C)线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面
D)线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的
性链表中，各元素在存储空间中的位置是任意的，各元素的顺序也是任意的，依靠指针来实现数据元素的前后件关系。
第7题：
对具有n个元素的有序序列进行二分查找时，(61)。
A．元素位置越靠近序列前端，查找该元素所需的比较次数越少
B．查找序列中任何一个元素所需要的比较次数不超过[log2(n+1)]
C．查找元素所需的比较次数与元素的位置无关
D．元素位置越靠近序列后端，查找该元素所需的比较次数越少
解析：二分查找过程是：以处于中间位置记录的关键字和给定值比较，若相等，则查找成功；若不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或查找区间的大小为零时(表明查找不成功)为止。对于有11个元素的有序表进行二分查找的过程可用一个二叉树表示，如图6-12所示(结点中的数字表示元素在序列中的序号)。
图6-12所示二叉树表明，若需要查找序列中的第6个元素，则仅需一次元素间的比较。若需查找第3个或第9个元素，则分别需要两次比较。依此类推，查找第1、4、7、10个元素时，分别需要三次比较，查找第2、5、 8、11个元素时，分别需要四次比较。因此，查找元素所需的比较次数与元素在序列中的位置是有关的。显然，选项A或D的说法也是错误的。若序列中有n个元素，则根据二分查找法构造的二叉树的高度不会超过[log2(n+1)]，因此选项B是正确的。
第8题：
下列叙述中正确的是( )。
A．线性链表的各元素在存储空间中的位置必须是连续的
B．线性链表的头元素一定存储在其他元素的前面
C．线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面
D．线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的
解析： 性链表中，各元素在存储空间中的位置是任意的，各元素的顺序也是任意的，依靠指针来实现数据元素的前后件关系。
第9题：
下列叙述中正确的是( )。
A．线性链表中的各元素在存储空间中的位置必须是连续的
B．线性链表中的表头元素一定存储在其他元素的前面
C．线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素—定存储在其他元素的前面
D．线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的
解析：性表的链式存储结构中，各数据结点的存储位置不连续，选项A错误。各结点在存储空间中的位置关系与逻辑关系也不一致，选项B和选项C错误。选项D正确。
第10题：
下列关于线性链表的叙述，正确的是
A．线性链表中的各元素在存储空间中的位置必须是连续的
B．线性链表中的表头元素一定存储在其他元素的前面
C．线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面
D．性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的
解析：线性表的链式存储结构中的结点空间是动态生成的，它们在内存中的地址可以是连续的，也可能是不连续的。