第一单元 课后自测练习题
知识点范围：第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; i sum = s ; 7．下面程序段的时间复杂度是 。 for( i =0; i 8．下面程序段的时间复杂度是 。 i ＝ 0； while（i<=n） i++； 9．链表不具备的特点是 。 A．可随机访问任一结点 B．插入删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与其长度成正比 1 10．不带头结点的单链表head为空表的判定条件是 。 A．head == NULL B head->next ==NULL C．head->next ==head D head!=NULL 11．带头结点的单链表head为空表的判定条件是 。 A．head == NULL B head->next ==NULL C．head->next ==head D head!=NULL 12．需要分配较大空间，插入和删除需要移动元素的线性表，其存储结构是 。 A．单链表 B．链表 C．线性链表 D．顺序存储结构 13．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 。 A．O（1） B．O（n） C．O（n） D．O（nlog2n） 14．在一个长度为n（n>1）的单链表上，设有指向头结点的指针head和指向数据结点的指针p，执行 操作与链表的长度有关。 A．删除单链表中的第一个元素 B．删除单链表中的最后一个元素 C．在单链表第一个元素前插入一个新元素 D．在单链表最后一个元素后插入一个新元素 15．在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数为： 。 A．n – i + 1 B．n – i C．i D．i – 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； 2 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<=i<=n）个结点 D．以上都不对 2 20．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为 。 A．O(0) B．O(1) C．O(n) D．O(n) 21．线性表（a1,a2, … ,an）以链式方式存储，访问第i位置元素的时间复杂度为 。 A．O(0) B．O(1) C．O(n) D．O(n) 22．单链表中，增加一个头结点的目的是为了 。 A．使单链表至少有一个结点 B．标识表结点中首结点的位置 C．方面运算的实现 D．说明单链表是线性表的链式存储 23．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是 。 A．p->next=s；s->next=p->next B． s->next=p->next ；p->next=s; C．p->next=s；p->next=s->next D．p->next=s->next；p->next=s 24．线性表的顺序存储结构是一种 。 A．随机存取的存储结构 B．顺序存取的存储结构 C．索引存取的存储结构 D．Hash存取的存储结构 25．下面程序的时间复杂为 for（i=1，s=0； i<=n； i++） { t=1； for(j=1；j<=i；j++) t=t*j；s=s+t； } (A) O(n) 二、填空题。 1．数据逻辑结构包括 、 和 三种类型，树形结构和图状结构合称 。 2．数据的逻辑结构根据数据间关系分为 、 、 和 4种。 3．在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点 后续结点，其余每个结点有且只有 个后续结点。 4．线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。 5．数据结构的基本存储方法是 、 、 和 存储 。 6．衡量一个算法的优劣主要考虑正确性、可读性、健壮性和 度与 度 。 7．评估一个算法的优劣，通常从 和 两个方面考察。 8．算法的5个重要特性是 、 、 、输入和输出。 9．在一个长度为n的顺序表中删除第i个元素时，需向前移动 个元素。 10．在单链表中，要删除某一指定的结点，必须找到该结点的 结点。 11．在顺序表中插入或删除一个数据元素，需要平均移动 个数据元素，移动数据元素的个数与 有关。 12．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素 3 22 (B) O(n) 2 (C) O(n) 3 (D) O(n) 4 是，应采用 存储结构。 13．根据线性表的链式存储结构中每一个结点包含的一个指针个数的线性链表称为 。 14．顺序存储结构是通过 下标 表示元素之间的关系的；链式存储结构是通过 表示元素之间的关系的。 15．一个算法的时间复杂度为(n+nlog2n+14n)/n，其数量级表示为___ _____。 三、判断题 1．在决定选取何种存储结构时，一般不考虑各结点的值如何。（） 2．抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。（） 3．抽象数据类型与计算机内部表示和实现无关。（ ） 4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（ ） 5．线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。（ ） 6．对任何数据结构链式存储结构一定优于顺序存储结构。（ ） 7．顺序存储方式只能用于存储线性结构。（ ） 8．集合与线性表的区别在于是否按关键字排序。（ ） 9．线性表中每个元素都有一个直接前驱和一个直接后继。（ ） 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 data next 4 3 22 3 60 5 50 7 78 2 90 0 34 4 40 1 五、阅读算法 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）说明语句组S2的功能； （3）设链表表示的线性表为（a1,a2, …,an）,写出算法执行后的返回值所表示的线性表。 5 六、编写算法 编写函数模块CountX统计出单链表L中结点的值等于给定值X的结点数。 单链表L中结点的数据类型定义： typedef struct node {int data; struct node *next; }LNode; int CountX(LNode* L,int x) 6
因篇幅问题不能全部显示，请点此查看更多更全内容