数据结构作业一满分

1、1.       在线性表的下列存储结构中，读取元素花费的时间最少的是A.      单链表  B. 双向链表  C.循环链表  D.顺序表说明：顺序表总从链表访问快，因为顺序表元素都是按顺序排列在一起的。而链表的元素是分散的，要访问它的某一个元素，必须先访问它前面的元素。 2.       顺序表是线性表的 

2、;A.链式存储结构      B.    顺序存储结构      C. 索引存储结构  D.散列存储结构说明：顺序存储指在内存中是一个连续的整块，这是定义，没啥说的。 3. 以下关于线性表的说法不正确的是( )。  A、线性表中的数据元素可以是数字、字符、记录等不同类型。B、线性表中包含的数据元素个数不是任意的。  C、线性表根据存储结构分可以有顺

3、序表、链表、动态表D、存在这样的线性表：表中各结点都没有直接前趋和直接后继说明：A，我认为可以是任何类型（暂时没想出反例）B，这句话不太好理解，估计原题的意思是为了说明：线性表是能得到确切的元素个数。C，线性表只包括顺序表和链表。而动态表，没听说过这种说法。D，线性表为空，好像就符合题意。4在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。A) 基地址      B) 结点大小     C) 向量大小   &

4、#160; D)基地址和结点大小说明：这里任意结点是指给出这个结点的索引(index)，则其地址为：base + index * sizeof(node)，这里base为基地址，sizeof(node)为结点大小，假设index从0开始计数（C/C+都是从0开始，如果其它语言从1开始，只要将index-1代替index就可以了）5在等概率情况下，顺序表的插入操作要移动( )结点。A) 全部               B)&#

5、160;一半         C) 三分之一               D) 四分之一说明：插入和删除操作，平均约要移动全部元素的1/2，在P25，有推导公式，记住结果就行了。6在( )运算中，使用顺序表比链表好。  A) 插入      

6、0;  B) 删除               C) 根据序号查找               D)  根据元素值查找说明：插入、删除操作都是链表快。根据元素值查找，都是要遍历每个元素，进行比对，直到找到为止，两者效率应该相等。根据序号查找

7、，也就是根据索引index，顺序表的访问时间为常量，比链表要快，这与第4题是同一个知识点。7在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。  A)  O(1)              B)  O(n)              

8、;C)  O(n2)          D)  O(log2n)说明：插入前要遍历之前的每一个元素，直到找到位置为止，这个定位过程，都是O(n)8( )适合作为经常在首尾两端操作线性表的存储结构。  A)  顺序表    B) 单链表         C) 循环链表&#

9、160;        D) 双向链表说明：常用操作无非包括插入、删除、读取三种方式。顺序表的插入效率太低，不予考虑。对于BCD三种链表（循环链表没说是双向的，我们这里只认为是普通方式，即单向循环）。对首端的操作差不多。但对尾端就不一样了。比如要删除尾结点t ，则必须先找到它的前一个结点s。前两者，只有遍历整个链表，才能找到s。而在双向链表中，只要用s = t->prior就可以表示它的前一个结点了。9 非空的循环单链表head的尾节点（由r所指向）满足A)  

10、;   r->next=NULL       B)    r=NULL         C)    r->next=head         D)   r=head说明：这是定义，最后一个结点的下一

11、结点为头结点。 10设线性表（a1,a2,a3···an）按顺序存储,且每个元素占有m个存储单元，则元素ai的地址为A      LOC(a1) + i×m ，其中LOC(a1)表示元素a1的地址B      LOC(a1) + (i-1)×m，C      LOC(a1) + (i2)×mD    

12、;  元素ai的地址无法计算说明：见第4题，这里从1开始，所以要减去111线性表若采用链式存储结构时，要求内存中可用存储单元的地址  A)    必须是连续的             B)  部分地址必须是连续的C)    一定是不连续的       

13、0;   D)  连续或不连续都可以说明：其每个结点的地址，都是malloc()出来的，这是系统调用，可能连续也可能不连续，不过一般情况下，都是不连续的。12. 下列图1单链表执行R->data=P->next->data语句后，P->next->data值为：A. 2          B. 5        

14、60;   C.7             D. 3 图1说明：只是将P->next->data赋值给别人了，自己没变化。13在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，    则执行：    A.Snext=P;Pnext=S       B.

15、Snext=Pnext;Pnext=S  C.Snext=Pnext; P=S      D.Pnext=S;Snext=P说明：链表插入的标准操作。要注意的是，这两步别写反了，否则链就断开了。14.单链表表示的整数数列如下: 值Pànextànext->data为: A. 19      B. 47        C. 64

16、60;       D. 93说明：Pànext就是指向64那个结点，Pànextànext就是指向93那个结点，其data自然就是93了15. 在( )链表中，不能从任一结点出发访问到表中的所有结点的是：A) 单链表       B) 单向循环链表     C) 双向循环链表        D) 循环链表说明：循环链表和双链表都行，只有单链表不行。 16、在双向循环链表的*p结点之后插入*s结点的操作是：（）A)     p->next=s; s->prior=p; p->next->prior=s; s->next=p->nextB)      p->next=s; p->next->prior=s; s->prior=p; s->