单向链表在内存中是连续存储的（单向链表在内存中是连续存储的嘛）

一、1.单项选择题

0. 堆排序的最坏时间复杂度为( )

A．O(n)
B．O(10g₂n)
C．O(nlog₂n)
D．O(n²)

1. 对广义表((a)，(b))进行下面的操作head(head((a)，(b)))后的结果是( )

A．a
B．(a)
C．( )
D．不确定

2. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的前序遍历序列是 ( )

A．a c b e d
B．d e c a b
C．d e a b c
D．c e d b a

3. 判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用( )

A．求关键路径的方法
B．求最短路径的Dijkstra方法
C．广度优先遍历方法
D．深度优先遍历方法

4. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的结点的双亲结点编号为( )

A．42
B．40
C．21
D．20

5. 设数组A[0,m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行入队操作的语句是( )

A．sq.front=(sq.front+1)%m
B．sq.front=(sq.front+1)%(m+1)
C．sq.rear=(sq.rear+1)%m
D．sq.rear=(sq.rear+1)%(m+1)

6. 如果T₂是由有序树T转换而来的二叉树，那么T中结点的后序就是T₂中结点的( )

A．前序
B．中序
C．后序
D．层次序

7. 链栈与顺序栈相比，有一个比较明显的优点即( )

A．插入操作更加方便
B．通常不会出现栈满的情况
C．不会出现栈空的情况
D．删除操作更加方便

8. 串是任意有限个( )

A．符号构成的集合
B．符号构成的序列
C．字符构成的集合
D．字符构成的序列

9. 堆是一个键值序列(k₁，k₂，k…，k₁…，k₀)，对i=1，2…，[n/2]，满足( )

A．k_i≤k_2i≤k_2i+1
B．k_i＜k_2i＜k_2i+1
C．k_i≤k_2i且k≤k_2i+1(2i+1≤n)
D．k_i≤k_2i或k_i≤k_2i+l(2i+1≤n)

10. 带头结点的单链表Head为空的判定条件是( )

A．Head=NULL;
B．Head↑.next=NULL;
C．Head↑.nextHead;
D．Head↑.next=Head↑

11. 如果待排序的记录的规模很大，则在下面的排序方式中，我们最好不要选择使用 ( )

A．快速排序
B．直接插入排序
C．堆排序
D．归并排序

12. 串是一种特殊的线性表，其特殊性体现在( )

A．可以顺序存储
B．数据元素是一个字符
C．可以链接存储
D．数据元素可以是多个字符

13. 线性表若采用链表存储结构时，要求内存中可用存储单元的地址( )

A．必须是连续的
B．部分地址必须是连续的
C．一定是不连续的
D．连续不连续都可以

14. 假设有一个数组，它的行号从0到8，列号从0到10，数组中每个元素所占的存储空间为3个单元，则现在将此数组从某一个地址开始连续存放在一个存储器中，试问至少需要( )个存储单元才能完全将此数组存放进去。

A．240
B．297
C．270
D．300

二、2.填空题

0. 在索引顺序文件中需建立一张指示逻辑记录和物理记录之间的一一对应关系的______。它通常采用______结构来组织。

1. 数组A[1..10，-2..6，2..8]以行优先顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5,0,7]的存储地址为______。

2. 对磁带上的顺序文件进行更新某个记录时，必须______整个文件。而在顺序文件的最后添加新的记录时，则不必______整个文件。

3. 若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点，则它必是孩子树的后序遍历序中的______个结点。

4. 文件的记录均存放在数据集中，数据集中的一个结点称为______，它是一个______操作的基本单位。

5. 设线性表L=(a₁，a₂，…，a_n)(n＞2)，表中元素按值的递增顺序排列。对一个给定的值k，分别用顺序检索和二分法检索查找与k相等的元素，比较次数分别为s和b，若检索不成功，则s和b的数量关系是______。

6. 在按照顺序存储方式存储的数组中，元素aij的存储地址应该是数组的______加上排在aij前面的元素所占用的单元数。

7. ______查找法的平均查找长度与元素个数n无关。

8. 在计算机软件系统中，有两种处理字符串长度的方法：一种是采用______，第二种是设置______。

9. 在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列的初始化时均应该设置为______，当对队列进行插入和删除的操作后，如果头指针和尾指针相等时，队列为______。

三、3.解答题

0. 已知一棵二叉树的前序遍历序列是ABDGCEFH，其中序遍历序列为DGBAECHF。请画出相应的二叉树，并求出对应此二叉树的后序遍历序列，此二叉树是完全二叉树吗?完全二叉树有什么性质(特点)?

1. 已知有一关键字序列为{97,86,53,108,72,34,215,146,11,68}，如果我们采用直接选择排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。

2. 请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图(顶点v_i表示)。

4.判别下列二序列是否为堆，如不是，按照对序列建堆的思想把它调整为堆，用图表示建堆的过程。

(1,5,7,25,21,8,8,42)

四、4.算法阅读题

0. 以下算法假定以线性探测法解决冲突，在闭散列表HL中查找键值为K的结点，成功时回送该位置；不成功时回送标志-1。请分析程序，并在______上填充合适的语句。
int search_closehash(keyt,ype K,closehash HL)
{ d=H(K);  /*计算散列地址*/
   i=d;
   while(HL[i].key!=K&&(i!=d-1)i=______;)/*未成功且未查遍整个HL时继
                         续扫描*/
   if(______)return(i);  /*查找成功*/
   else return(-1);    /*查找失败*/
}

1. 以下为单链表的删除运算，分析算法，请在______处填上正确的语句。
void delete_lklist(1klist head,int i)
   { p=find_lklist(head,i-1)；
    if(______)
     { q=______;
      p—＞next=q—＞next;
      free(q);
     }
   else error("不存在第i个结点")
}

2. 以下为顺序表的定位运算，分析算法，请在______处用正确的语句予以填充。
int locate_sqlist(sqlist L,datatype X)
/*在顺序表L中查找第一个值等于X的结点。若找到回传该结点序号；否则回传0*/{______；
while((i≤L.last)&&(L.data[i-1]!=x))i++;
if(______)return(i);
else return(0);
}

3. 以下为单链表的建表算法，分析算法，请在______处填上正确的语句。
lklist create_iklist2()  /*直接实现的建表算法。*/
   { head=malloc(size);
    p=head;
    scanf("%",&x);
    while(X!="$")
    { q=malloc(size);
     q—＞data=x;
     p—＞next=q;
     ______;
     scanf("%",&x);
    }
     ______;
     return(head);
    }
此算法的量级为______。

五、5.算法设计题

0. 假设在表示一棵二叉树的二叉链表上增加两个域，双亲域用于指示其双亲结点，标志域flag(可取，0…2)的值，用以区分在遍历过程中到达该结点时继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。

到此这篇单向链表在内存中是连续存储的（单向链表在内存中是连续存储的嘛）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！

上一篇：速排小蚂蚁编辑器怎么粘贴文字（小蚂蚁编辑器怎么复制链接）

下一篇：怎么点击图片跳转链接（怎么点击图片跳转链接页面）

版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/62697.html

相关文章：