第一单元(算法分析线性表)T

1、第一单元课后自测练习题知识点范围：第1章绪论、第2章线性表一、选择题1在数据结构中，从逻辑上可以把数据结构分为 。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D内部结构和外部结构2数据结构在计算机内存中的表示是指 。A数据的存储结构 B数据结构 C数据的逻辑结构 D数据元素之间的关系3在数据结构中，与所使用的计算机无关的是数据的 结构。A逻辑 B存储 C逻辑和存储 D物理4在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 。A数据的处理方法 B数据元素的类型 C数据元素之间的关系 D数据的存储方法5算法分析的目的是 ，算法分析的两个主要方面是 。1A找出数据结构

2、的合理性 B研究算法中的输入和输出的关系C分析算法的效率以求改进 D分析算法的易读性和文档性2A空间复杂度和时间复杂度 B正确性和简明性 C可读性和文档性 D数据复杂性和程序复杂性6下面程序段的时间复杂度是 。 s =0;for( I =0; i<n; i+) for(j=0;j<n;j+)s +=Bij;sum = s ;7下面程序段的时间复杂度是 。for( i =0; i<n; i+) for(j=0;j<m;j+)Aij 0;8下面程序段的时间复杂度是 。i 0；whilei<=ni+；9链表不具备的特点是 。A可随机访问任一结点 B插入删除不需要移动元素

3、C不必事先估计存储空间 D所需空间与其长度成正比10不带头结点的单链表head为空表的判定条件是 。Ahead = NULL B head->next =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个结点的有序单链表中插入一个新结点并仍然保持有序

4、的时间复杂度是 。AO1 BOn COn2 DOnlog2n14在一个长度为nn>1的单链表上，设有指向头结点的指针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->

5、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个结点的线性表的顺序

6、存储结构中，算法的时间复杂度是O1的操作是 。A访问第i1<=i<=n个结点B在第i1<=i<=n个结点后插入一个新结点C删除第i1<=i<=n个结点D以上都不对20假设长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为 。AO(0) BO(1) CO(n) DO(n2)21线性表a1,a2, ,an以链式方式存储，访问第i位置元素的时间复杂度为 。AO(0) BO(1) CO(n) DO(n2)22单链表中，增加一个头结点的目的是为了 。A使单链表至少有一个结点 B标识表结点中首结点的位置C方面运算的实现 D说明单链表是线性

7、表的链式存储23在单链表指针为p的结点之后插入指针为s的结点，正确的操作是 。Ap->next=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下面程序的时间复杂为 fori=1，s=0； i<=n； i+ t=1；for(j=1；j<=

8、i；j+) t=t*j；s=s+t；(A) O(n)(B) O(n2)(C) O(n3)(D) O(n4)二、填空题。1数据逻辑结构包括 、 和 三种类型，树形结构和图状结构合称 。2数据的逻辑结构根据数据间关系分为 、 、 和 4种。3在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点 后续结点，其余每个结点有且只有 个后续结点。4线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。5数据结构的根本存储方法是 、 、 和 存储 。6衡量一个算法的优劣主要考虑正确性、可读性、健壮性和 度与 度 。7评估一个算法的优劣，

9、通常从 和 两个方面考察。8算法的5个重要特性是 、 、 、输入和输出。9在一个长度为n的顺序表中删除第i个元素时，需向前移动 个元素。10在单链表中，要删除某一指定的结点，必须找到该结点的 结点。11在顺序表中插入或删除一个数据元素，需要平均移动 个数据元素，移动数据元素的个数与 有关。12当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用 存储结构。13根据线性表的链式存储结构中每一个结点包含的一个指针个数的线性链表称为 。14顺序存储结构是通过 下标 表示元素之间的关系的；链式存储结构是通过 表示元素之间的关系的。15一个算法的时间复杂度为

10、(n3+n2log2n+14n)/n2，其数量级表示为_ _。三、判断题1在决定选取何种存储结构时，一般不考虑各结点的值如何。2抽象数据类型ADT包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。3抽象数据类型与计算机内部表示和实现无关。 4顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。 5线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。 6对任何数据结构链式存储结构一定优于顺序存储结构。 7顺序存储方式只能用于存储线性结构。 8集合与线性表的区别在于是否按关键字排序。 9线性表中每个元素都有一个直接前驱和

11、一个直接后继。 10线性表就是顺序存储的表。 11取线性表的第i个元素的时间同i的大小有关。 12链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序表中效率高。 13在单链表中，给定任一结点的地址p，那么可用下述语句将新结点s插入结点p的后面 ：p->next = 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=L>next；p=L； S1： while(p>next) p=p>next； S2： p>next=q；q>next=NULL； return L； 请答复以下问题： 1说明语句S1的功能； 2说明语句