数据结构作业一满分版_第1页
数据结构作业一满分版_第2页
数据结构作业一满分版_第3页
数据结构作业一满分版_第4页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、1.在线性表的下列存储结构中,读取元素花费的时间最少的是A.单链表B.双向链表C.循环链表D.顺序表说明:顺序表总从链表访问快,因为顺序表元素都是按顺序排列在一起的。而链表的元素是分散的,要访问它的某一个元素,必须先访问它前面的元素。2.顺序表是线性表的A.链式存储结构B.顺序存储结构C.索引存储结构D.散列存储结构说明:顺序存储指在内存中是一个连续的整块,这是定义,没啥说的。3.以下关于线性表的说法不正确的是( )。A、线性表中的数据元素可以是数字、字符、记录等不同类型。B、线性表中包含的数据元素个数不是任意的。C、线性表根据存储结构分可以有顺序表、链表、动态表D、存在这样的线性表:表中各结

2、点都没有直接前趋和直接后继说明:A,我认为可以是任何类型(暂时没想出反例)B,这句话不太好理解,估计原题的意思是为了说明:线性表是能得到确切的元素个数。C,线性表只包括顺序表和链表。而动态表,没听说过这种说法。D,线性表为空,好像就符合题意。4在顺序表中,只要知道( ),就可在相同时间内求出任一结点的存储地址。A)基地址B)结点大小C)向量大小D)基地址和结点大小说明:这里任意结点是指给出这个结点的索引(index),则其地址为:base + index * sizeof(node),这里base为基地址,sizeof(node)为结点大小,假设index从0开始计数(C/C+都是从0开始,如

3、果其它语言从1开始,只要将index-1代替index就可以了)5在等概率情况下,顺序表的插入操作要移动( )结点。A)全部B)一半C)三分之一D)四分之一说明:插入和删除操作,平均约要移动全部元素的1/2,在P25,有推导公式,记住结果就行了。6在( )运算中,使用顺序表比链表好。A)插入B)删除C)根据序号查找D)根据元素值查找说明:插入、删除操作都是链表快。根据元素值查找,都是要遍历每个元素,进行比对,直到找到为止,两者效率应该相等。根据序号查找,也就是根据索引index,顺序表的访问时间为常量,比链表要快,这与第4题是同一个知识点。7在一个具有n个结点的有序单链表中插入一个新结点并仍然

4、有序的时间复杂度是( )。A)O(1)B)O(n)C)O(n2)D)O(log2n)说明:插入前要遍历之前的每一个元素,直到找到位置为止,这个定位过程,都是O(n)8( )适合作为经常在首尾两端操作线性表的存储结构。A)顺序表B)单链表C)循环链表D)双向链表说明:常用操作无非包括插入、删除、读取三种方式。顺序表的插入效率太低,不予考虑。对于BCD三种链表(循环链表没说是双向的,我们这里只认为是普通方式,即单向循环)。对首端的操作差不多。但对尾端就不一样了。比如要删除尾结点t,则必须先找到它的前一个结点s。前两者,只有遍历整个链表,才能找到s。而在双向链表中,只要用s = t-prior就可以

5、表示它的前一个结点了。9非空的循环单链表head的尾节点(由r所指向)满足A)r-next=NULLB)r=NULLC)r-next=headD)r=head说明:这是定义,最后一个结点的下一结点为头结点。10设线性表(a1,a2,a3an)按顺序存储,且每个元素占有m个存储单元,则元素ai的地址为ALOC(a1) + im,其中LOC(a1)表示元素a1的地址BLOC(a1) + (i-1)m,CLOC(a1) + (i2)mD元素ai的地址无法计算说明:见第4题,这里从1开始,所以要减去111线性表若采用链式存储结构时,要求内存中可用存储单元的地址A)必须是连续的B)部分地址必须是连续的C

6、)一定是不连续的D)连续或不连续都可以说明:其每个结点的地址,都是malloc()出来的,这是系统调用,可能连续也可能不连续,不过一般情况下,都是不连续的。12.下列图1单链表执行R-data=P-next-data语句后,P-next-data值为:A. 2B.5C.7D. 3图1说明:只是将P-next-data赋值给别人了,自己没变化。13在一个单链表中,若P所指结点不是最后结点,在P之后插入S所指结点,则执行:A.Snext=P;Pnext=SB.Snext=Pnext;Pnext=SC.Snext=Pnext; P=SD.Pnext=S;Snext=P说明:链表插入的标准操作。要注意

7、的是,这两步别写反了,否则链就断开了。14.单链表表示的整数数列如下:值Pnextnext-data为:A. 19B. 47C. 64D. 93说明:Pnext就是指向64那个结点,Pnextnext就是指向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-next=p-nextC)s-prior=p; s-next=p-next; p-

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论