数据结构试题

（

) 1.线性表采用顺序存储结构，元素长度为4，首地址为100，下标为12的(13)元素的存储地址为148。

正确。第0个元素的地址是100，那么第I个元素的地址就是100+4 * i .将12代入148。

（

) 2.不能在任何类型的线性链表上执行随机访问。

错误。例如，只要知道序列表的头地址和每个数据元素占用的存储单元数，就可以找到第I个数据元素的存储地址，这也是根据数据元素的序号随机访问序列表的特点。

（

) 3.顺序堆栈是指定元素进入堆栈的顺序的堆栈。

错误。按照存储结构将栈分为顺序栈和链式栈，其中栈的顺序存储结构简称为顺序栈，是一个操作受限的序列表，但并没有规定元素进入栈的顺序。

（

4.循环列表中的每个元素都有一个后继元素。

正确。注意这里可能有笔误，应该写成“循环列表”而不是“循环列表”。

（

5.删除二叉树中的一个节点，重新插入，就得到原来的二叉排序树。

错误。

2.填空。

6.下列程序的时间复杂度是_ _ _ _ _ _。

为

(int

I = 1；

我& lt= m；

i++)

为

(int

j = 1；

j & lt= n；

j++

)

S+=i

规则1: for循环:for循环的运行时间最多是for循环中语句(包括test)的运行时间乘以迭代次数。

规则2:嵌套循环:从内向外分析这些循环。一组嵌套循环中一条语句的总运行时间是该语句的运行时间乘以该组循环中所有循环的大小的乘积。

对于这里嵌套的For循环，按照上面的规则，时间复杂度为O(m*n)。

7.在序列表的i(1≤i≤n+1)位置插入一个元素，长度为n，元素移动的次数为_ _ _ _ _ _ _ _ _ _ _。

从第I个元素(原)到第N个元素，每个元素后移一位，一个* * *，需要n+1-i次。

8.在一个有n个节点的有序单链表中插入一个新节点，并保持插入的单链表有序，操作的时间复杂度在_ _ _ _ _ _量级。

求节点位置，o(n)；单链表插入操作，o(n)；总时间复杂度为O(n+n)=O(n)。

9.如果用S [1] ~ S [n]作为两个顺序栈的* * *相同存储空间，左右栈顶分别为t1和t2，则判断一个栈能否插入新元素的条件是_ _ _ _ _ _ _ _ _ _ _ _ _ _。

当程序中同时使用两个堆栈时，可以将两个堆栈的底部设置在向量空间的两端，这样两个堆栈就可以分别延伸到中间。当一个栈中的元素多于向量空间的一半时，只要另一个栈中的元素不多，前者就可以占用后者的部分存储空间。

这里判断一个栈能否插入新元素的条件是& amp；t1！= & ampt2

10.假设森林T中有三棵树，第一、二、三棵树的节点数分别为N1、N2和N3。森林转换成二叉树后，其根节点的左子树上有_ _ _ _ _ _ _ _ _个节点。

将森林转化为二叉树的具体方法如下:①

把森林里的每一棵树都变成二叉树；②

因为转换后的二叉树的根节点的右子树都是空的，所以每棵二叉树的根节点都可以看作是从左到右连接的兄弟，形成一棵二叉树。

个人觉得这里可以填三个答案，n1-1或者n2-1或者n3-1。

11.在加权有向图的邻接矩阵中，第I行非零元素的个数等于_ _ _ _ _ _ _ _ _ _ _ _ _ _。

当节点Vi与节点Vj相邻时，A(i，j)取非零值。

12.在各种搜索方法中，平均搜索长度与节点数n无关的搜索方法是_ _ _ _ _ _ _ _ _ _。

哈希查找。