第一单元(算法分析+线性表)_T.doc

第一单元课后自测练习题知识点范围：第1章绪论、第2章线性表一、选择题1在数据结构中，从逻辑上可以把数据结构分为 。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D内部结构和外部结构2数据结构在计算机内存中的表示是指 。A数据的存储结构 B数据结构 C数据的逻辑结构 D数据元素之间的关系3在数据结构中，与所使用的计算机无关的是数据的 结构。A逻辑 B存储 C逻辑和存储 D物理4在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 。A数据的处理方法 B数据元素的类型 C数据元素之间的关系 D数据的存储方法5算法分析的目的是 ，算法分析的两个主要方面是 。（1）A找出数据结构的合理性 B研究算法中的输入和输出的关系C分析算法的效率以求改进 D分析算法的易读性和文档性（2）A空间复杂度和时间复杂度 B正确性和简明性 C可读性和文档性 D数据复杂性和程序复杂性6下面程序段的时间复杂度是 。 s =0;for( I =0; in; i+) for(j=0;jn;j+)s +=Bij;sum = s ;7下面程序段的时间复杂度是 。for( i =0; in; i+) for(j=0;jm;j+)Aij 0;8下面程序段的时间复杂度是 。i 0；while（inext =NULL Chead-next =head D head!=NULL11带头结点的单链表head为空表的判定条件是 。Ahead = NULL B head-next =NULL Chead-next =head D head!=NULL12需要分配较大空间，插入和删除需要移动元素的线性表，其存储结构是 。A单链表 B链表 C线性链表 D顺序存储结构13在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 。AO（1） BO（n） CO（n2） DO（nlog2n）14在一个长度为n（n1）的单链表上，设有指向头结点的指针head和指向数据结点的指针p，执行 操作与链表的长度有关。A删除单链表中的第一个元素B删除单链表中的最后一个元素C在单链表第一个元素前插入一个新元素D在单链表最后一个元素后插入一个新元素15在长度为n的顺序表的第i个位置上插入一个元素（1 i n+1），元素的移动次数为： 。An i + 1 Bn i Ci Di 1 16设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（）。(A) s-next=p-next；p-next=-s；(B) q-next=s； s-next=p；(C) p-next=s-next；s-next=p；(D) p-next=s；s-next=q；17下面关于线性表的叙述中，错误的是哪一个？ 。A线性表采用顺序存储，必须占用一片连续的存储单元B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链式存储，不必占用一片连续的存储单元D线性表采用链式存储，便于进行插入和删除操作。18线性表是具有n个 的有限序列。A字符 B数据元素 C数据项 D表元素19在n个结点的线性表的顺序存储结构中，算法的时间复杂度是O（1）的操作是 。A访问第i（1=i=n）个结点B在第i（1=i=n）个结点后插入一个新结点C删除第i（1=inext=s；s-next=p-next B s-next=p-next ；p-next=s;Cp-next=s；p-next=s-next Dp-next=s-next；p-next=s24线性表的顺序存储结构是一种 。A随机存取的存储结构 B顺序存取的存储结构C索引存取的存储结构 DHash存取的存储结构25下面程序的时间复杂为 for（i=1，s=0； i=n； i+） t=1；for(j=1；jnext = s; s-next = p-next; ( )14线性表的顺序存储结构比链式存储结构更好。（）15对链表进行插入和删除操作时不必移动链表中结点。()四、计算题在如下数组A中链式存储了一个线性表L，表头指针为A 0.next，试写出该线性表L的表示。 A 0 1 2 3 4 5 6 7 data605078903440next3572041五、阅读算法1. LinkList mynote(LinkList L) /L是不带头结点的单链表的头指针 if(L&L-next) q=L；L=Lnext；p=L； S1： while(pnext) p=pnext； S2： pnext=q；qnext=NULL； return L； 请回答下列问题： （1）说明语句S1的功能； （2）说明语句组S2的功能； （3）设链表表示的线性表为（a1,a2, ,an）,写出算法执行后的返回值所表示的线性表。六、编写算法编写函数模块CountX统计出单链表L中结点的