数据结构第2章典型例题解析
第2章线性表
典型例题解析
一、选择题
1．线性表是具有n个（n≥0）的有限序列。
A．表元素B．字符C．数据元素D．数据项
【分析】线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，通常记为(a1,a2,…,a n)，其中n为表长，n=0时称为空表。
【答案】C
2．顺序存储结构的优点是。
A．存储密度大B．插入运算方便
C．删除运算方便D．可方便地用于各种逻辑结构的存储表示【分析】顺序存储结构是采用一组地址连续的存储单元来依次存放数据元素，数据元素的逻辑顺序和物理次序一致。因此，其存储密度大。
【答案】A
3．带头结点的单链表head为空的判断条件是。
A．head==NULL B．head->next==NULL
C．head->next==head D．head!=NULL
【分析】链表为空时，头结点的指针域为空。
【答案】B
4．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用存储方式最节省运算时间。
A．单链表B．仅有头指针的单循环链表
C．双链表D．仅有尾指针的单循环链表
【分析】根据题意要求，该线性表的存储应能够很方便地找到线性表的第一个元素和最后一个元素，A和B都能很方便地通过头指针找到线性表的第一个元素，却要经过所有元素才能找到最后一个元素；选项C双链表若存为双向循环链表，则能很方便地找到线性表的第一个元素和最后一个元素，但存储效率要低些，插入和删除操作也略微复杂；选项D可通过尾指针直接找到线性表的最后一个元素，通过线性表的最后一个元素的循环指针就能很方便地找到第一个元素。
【答案】D
5．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用存储方式最节省时间。
A．顺序表B．双链表
C．带头结点的双循环链表D．单循环链表
【分析】某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运
算。因此不需要移动线性表种元素的位置。根据题意要求，该线性表的存储应能够很方便地找到线性表的任一指定序号的元素和最后一个元素，顺序表是由地址连续的向量实现的，因此具有按序号随机访问的特点。链表需要通过指针才能找到线性表的莫以指定序号的元素，需要一定的时间开销。
【答案】A
6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用最节省时间。
A. 单链表
B.单循环链表
C. 带尾指针的单循环链表
D.带头结点的双循环链表
【分析】根据题意要求，该线性表的存储应能够很方便地找到线性表的最后一个元素和最后一个元素的前驱元素，A和B都不能很方便地通过头指针找到线性表的第一个元素；选项C可以方便地找到最后一个元素，单不能很快地找到其前驱元素；选项D为双向循环链表，可以很方便地找到线性表的最后一个元素，通过其前驱指针，从而可以方便地找到其前驱元素。
【答案】D
7．静态链表中指针表示的是。
A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址【分析】静态链表采用的是链式方式存储线性表，以数组方式存储链表的数据，指针域存储的是该结点逻辑上的后继结点的相对地址（即在数组中的下标），也称为静态指针。
【答案】B
8．链表不具有的特点是。
A．插入、删除不需要移动元素B．可随机访问任一元素
C．不必事先估计存储空间D．所需空间与线性长度成正比
【分析】链表是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据元素之间的线性关系，对每个数据元素，除了存放数据元素自身的信息之外，还需要和存放其后继元素所在的存储单元的地址。链表不具有按序号随机访问第i个元素的特点，必须通过标识链表的头指针（或尾指针）“顺藤摸瓜”才能找到第i个结点。
【答案】B
9．线性表的静态链表存储结构与顺序存储结构相比优点是。
A．所有的操作算法简单B．便于插入和删除
C．便于利用零散的存储器空间D．便于随机存取
【分析】静态链表采用的是链式方式存储线性表，因此其具有链式存储的特点。
【答案】B
10．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为。
A．O(log2n) B．O(1) C．O(n) D．O(n2)
【分析】在第i个位置上插入新元素需要从最后一个元素开始后移直到第i个元素后移为止，后移元素的次数为n-i+1，即时间复杂度为O(n)。
【答案】C
11．线性表（a1,a2,…,an）以链接方式存储时，访问第i个位置元素的时间复杂性为。
A．O(i) B．O(1) C．O(n) D．O(i-1)
【分析】线性表以链接方式存储时，访问第i个位置元素从第一个元素开始移动指针到第i个元素，移动指针的次数为n-i+1，即时间复杂度为O(n)。
【答案】C
12．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。
A．n B．2n-1 C．2n D．n-1 【分析】当一个表的最小元素大于另一个表的最大元素时比较次数为最少，共需n次。
【答案】A
13．非空的循环单链表head的尾结点p满足。
A．p->next==head B．p->next==NULL C．p==NULL D．p==head 【分析】非空的循环单链表head的尾结点的后继指针指向链表的头结点。
【答案】A
14．在双循环链表p所指结点之后插入s所指结点的操作是。
A．p->next=s; s->prior=p; p->next->prior=s; s->prior=p->next;
B．p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
C．s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
D．s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
【分析】由于要将s所指结点插入到p所指结点之后，p结点为s结点的前驱，s结点为p 结点的新后继，而结点p的原后继结点为结点s的后继结点，结点s为结点p的原后继结点的前驱结点s。在选项A、B和C中均是先执行操作p->next=s，就是修改了结点p的后继结点s，然后再执行操作p->next->prior=s，因此，无法使得结点s为结点p的原后继结点的前驱结点，这样的赋值会使s结点为其自身的前驱。应先执行操作p->next->prior=s，再执行操作p->next=s。
【答案】D
15．在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q结点和p结点之间插入s结点，则执行。
A．s->next=p->next;p->next=s; B．p->next=s->next;s->next=p;
C．q->next=s; s->next=p; D．p->next=s; s->next=q;
【分析】由于是将s所指结点插入到q和p所指结点之间，即使其为q所指结点的后继结点，为p所指结点的前驱结点，因此s->next的取值应为p，p->next的取值无需改动，q->next 的取值应改为s，故A、B和D均是错误的。
【答案】C
二、判断题
1．线性表的特点是每个元素都有一个前驱和一个后继。
【分析】线性表是一种逻辑结构，其数据元素属于相同数据类型，之间的关系是线性关
系。线性表中除第一个数据元素和最后一个数据元素外，外每个元素都有一个前驱和一个后继。
【答案】错误
2．顺序存储的线性表可以按序号随机存取。
【分析】因为顺序表在内存是用地址连续的空间存储的，设a1的存储地址为Loc(a1)，每个数据元素占d个存储地址，则第i个数据元素的地址为：
Loc(a i)=Loc(a１)+(i-1)×d1≤i≤n
这就是说只要知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址来，这也是顺序表具有按数据元素的序号随机存取的特点。
【答案】正确
3．链表中的头结点仅起到标识的作用。
【分析】头结点是附加在第一个元素结点之前的一个结点，当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点，为空表时，该指针域为空。其作用是为了运算上的方便。
【答案】错误
4．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。
【分析】链表是通过一组任意的存储单元来存储线性表中的数据元素的，为建立起数据元素之间的线性关系，对每个数据元素，除了存放数据元素自身的信息之外，还需要存放其后继元素所在的存储单元的地址。链表中结点的存储空间可以是不连续的，但结点内部的存储空间必须是连续的。
【答案】错误
5．在单链表中和在顺序表中插入一个元素其时间复杂度均为O(n)，因此说它们的执行时间是相等的。
【分析】大O记法表示时间渐近复杂度，是指一个算法中的时间耗费，往往是问题规模n 的函数T(n)，当n趋向于无穷大时，T(n)的数量级称为算法的时间渐近复杂度。虽然两种存储结构下的插入操作时间复杂度均为O(n)，但由于两者的基本操作不同，因此不能说它们的执行时间是相等的。
【答案】错误
6．所谓静态链表就是一直不发生变化的链表。
【分析】静态链表是指以数组方式存储链表的数据，数组的每个元素包含有数据域data 和指针域next，其存储的是该结点逻辑上的后继结点的相对地址（即在数组中的下标）。其存储空间不发生变化，而其内容可以发生变化。
【答案】错误
7．静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
【分析】静态链表是指以数组方式存储链表的数据，对链表进行插入和删除运算时，只需改变指针，不需移动数据。
【答案】正确
8．静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素
的时间与i 无关。
【分析】因为静态链表的存取特性与动态链表是一样的，只能顺序地找到第i 个元素，不能随机地存取第i 个元素，故其存取表中第i 个元素的时间与i 有关。
【答案】错误
9．静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。
【分析】因为静态链表是以数组方式存储链表的数据，数组空间大小在数组定义时就已确定，一般不会发生变化。
【答案】正确
10．取线性表的第i 个元素的时间同i 的大小有关。
【分析】存取线性表中数据元素的时间开销与其存储结构有关。顺序存储结构具有按序号随机访问的特点，同i 的大小无关。
【答案】错误
三、简答题
1．如图2-11所示的双向链表中，欲在结点p 前插入一个结点s ，请完成有关操作。
s->prior=p->prior;
p->prior=s;
s->next=p; 【解答】 只能是“s ->prior ->next=s;”而不能为
“p ->prior ->next=s;”。 因为在上面的第二条语句中已经改变了结点p 的前驱结点，结点p 的前驱结点已经为s 结点，而不是操作前的前驱结点。在下面的语句顺序下，可有两个答案进行选择。
s->prior=p->prior;
p->prior=s;
s->next=p;
读者做这种题时，最好予以图示，不易出错。
2．已知线性表非递减有序，存储于一个一维数组A [0..n -1] 中（表长为n ，设为全局量），下面算法的功能是什么？
void del(DataType A[]){
int i,j;
i=1;
while (i<=n-1)
if (A[i]!=A[i+1])
i++;
else{
for (j=(i+2);j A[j-1]=A[j]; n--; } } 图2-11 第1题图 【解答】由于一维数组中的元素按元素非递减有序排列，值相同的元素必为相邻的元素，因此依次比较相邻两个元素，若值相等，则删除其中一个，否则继续向后查找。故算法功能是删除一维数组中多余的值相同的元素。 3．下述算法的功能是什么？ LinkList Demo(LinkList L){ // L是无头结点的单链表 LNode *q,*p; if (L && L->next){ q=L; L=L->next; p=L; while (p->next) p=p->next; p->next=Q; q->next=NULL; } return L; } 【解答】算法的功能是把单链表的第一个结点从表头移到了链尾。返回的L指向原链表的第二个结点。若原链表表示的线性表是(a1,a2,…,a n)，则操作后表示的线性表为(a2,a3,…, a n,a1)。 4．试描述头指针、头结点、开始结点的区别，并说明头指针和头结点的作用。 【解答】头指针是一个指针变量，里面存放的是链表中首结点的地址，并以此来标识一个链表。如链表H，链表L等，表示链表中第一个结点的地址存放在H和L中。 头结点是附加在第一个元素结点之前的一个结点，头指针指向头结点。当该链表表示一个非空的线性表时，头结点的指针域指向第一个元素结点，为空表时，该指针域为空。 开始结点指第一个元素结点。 头指针的作用是用来唯一标识一个单链表。 头结点的作用有两个：一是使得对空表和非空表的处理得以统一。二是使得在链表的第一个位置上的操作和在其他位置上的操作一致，无需特殊处理。 5．在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，而不知道头指针，能否将结点p从相应的链表中删除？若可以，其时间复杂度各为多少？ 【解答】 单链表：若结点p有后继结点，则可将结点p的后继元素数据放入结点p中，再将后继结点删除。时间复杂度为O(1)；若结点p无后继结点，则不可以实现。 双链表：可以实现，时间复杂度为O(1)。 单循环链表：像单链表那样进行操作，也可以从p开始，找结点p的直接前驱，然后再删除p结点，时间复杂度为O(n)。 四、算法设计题 1．设线性表存放在一维数组A[arrsize]的前num个分量中，且递增有序。试写一算法，将x插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。 【分析】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定要将一维数组和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性确定插入元素的插入位置，后面的元素为它让出位置（也可以从高下标端开始一边比较，一边移位），然后插入x，最后修改表示表长的变量。 【算法】 InsertSeq(DataType A[],int *num,DataType x){ //设num为表的最大下标 int i; if (*num==arrsize-1) return 0; else{ i=*num; while (i>=0&&A[i]>x){ //边找位置边移动 A[i+1]=A[i]; i--; } A[i+1]=x; //找到的位置是插入位的下一位 (*num)++; return 1; } } 时间复杂度为O(n)。 2．假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点s的直接前驱结点。 【分析】利用循环单链表的特点，通过s指针可循环找到其前驱结点p及p的前驱结点q，然后可删除结点p。 【算法】 viod delepre(LNode *s){ LNode *p,*q; p=s; while (p->next==s){ q=p; p=p->next; } q->next=s; delete p; } 3．已知两个单链表A与B分别表示两个集合，其元素递增排列，编写一个函数求出A 和B的交集C，要求C同样以元素值递增的单链表形式存储。 【分析】交集指的是两个单链表的元素值相同的结点的集合，为了操作方便，先让单链表C带有一个头结点，最后将其删除掉。算法中指针p用来指向A中的当前结点，指针q用来指向B中的当前结点，将其值进行比较，两者相等时，属于交集中的一个元素，两者不等时，将其较小者跳过，继续后面的比较。 【算法】 LinkNode *inter(LinkList A,B){ LNode *q,*p,*r,*s,*C; C=new LNode; r=C; p=A; q=B; while (p && q ) if (p->data p=p->next; else if (p->data==q->data){ s=new LNode; s->data=p->data; r->next=s; r=s; p=p->next; q=q->next; } else q=q->next; r->next=NULL; r=C->next; delete C; return r; } 4．单链表L是一个递减有序表，试编写一个高效算法，删除表中值大于min且小于max 的结点（若表中有这样的结点），同时释放被删结点的空间，这里min 和max 是两个给定的参数。并分析算法的时间复杂度。 【分析】由于单链表L是一个递减有序表，即由大到小有序，故可从表头开始查找第一个比max小的结点，记住其位置，再接着向后查找第一个不大于min的结点，然后将它们之间的结点删除。 【算法】 LinkList delete(LinkList L,int min,int max){ //设L为带头结点的循环链表 LNode *p,*q,*s,*k; if(L->next){ p=L->next; s=L; while (p->data>=max){ s=p; p=p->next; } //p指向第一个值小于max的结点,s指向其前驱 while (p!=L && p->data>min) //p继续下移 p=p->next; //p 指向第一个值不大于min的结点 while (s->next!=p){ //删除*s 的后继至* p的前驱之间的结点 k=s->next; s->next=k->next; delete k; } } } 前两个while循环和起来最多循环n次，第三个while循环最多循环n次，即删除n个结点，故算法的时间复杂度为O(n)。 5、编写一个算法，将一个头结点指针为a的单链表A分解为两个单链表A和B，其头结点指针分别为a和b，使得A链表中含有原链表A中序号为奇数的元素（头结点紧接的下一个元素为第1个元素），而B链表中含有原链表A中序号为偶数的元素，且保持原来的相对顺序。 【分析】此题用一个while循环来处理，一次循环处理两个结点：将前一个仍留在a中，后一个从a中删除，链接到b的尾部，直到整个链表处理完毕。 【算法】 Int split(LNode *a,LNode *b) //若成功分解，返回1，否则，返回0 //a为指向单链表a的指针，b为指向单链表B的指针 { LNode *cur_a,cur_b,temp; cur_a=a->next; cur_b=Init_List(); if(cur_b==NULL) { Return 0; } *b=cur_b; while(cur_a!=NULL&&(temp=cur_a→next)!=NULL) { cur_a→next=temp→next; cur_a=cur_a→next; cur_b→next=temp; cur_b=cur_b→next; } cur_b→next=NULL; return 1; } 数据结构例题（及答案） 项目一习题(答案) 一选择题 1. 算法的计算量的大小称为计算的(B )。 A( 效率 B. 复杂性 C. 现实性 D. 难度 2.算法的时间复杂度取决于(C ) A(问题的规模 B. 待处理数据的初态 C. A和B 3(从逻辑上可以把数据结构分为(C )两大类。 A(动态结构、静态结构 B(顺序结构、链式结构 C(线性结构、非线性结构 D(初等结构、构造型结构 4(连续存储设计时，存储单元的地址(A )。 A(一定连续 B(一定不连续 C(不一定连续 D(部分连续，部分不连续 5. 以下属于逻辑结构的是(C )。 A(顺序表 B. 哈希表 C.有序表 D. 单链表 二、判断题 1. 数据元素是数据的最小单位。(×) 2. 记录是数据处理的最小单位。(×) 3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系;(×) 4(程序一定是算法。(×) 5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×) 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×) 7. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(?) 8. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (×) 三、填空 1(数据的物理结构包括数据元素的表示和数据元素间关系的表示。 2. 对于给定的n个元素,可以构造出的逻辑结构有集合，线性结构，树形 结构，图状结构或网状结构四种。 3(数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而 逻辑关系是指数据元素之间的关联方式或称“邻接关系”。 4(一个数据结构在计算机中表示(又称映像) 称为存储结构。 5(抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表 示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响 其外部使用。 6(数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。 7. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互 关系，并对与这种结构定义相应的操作(运算)，设计出相应的算法。 ( 一个算法具有5个特性: 有穷性、确定性、可行性，有零个或多个输入、 有一个或多个输8 出。 四、应用题 1. 1. 数据结构是一门研究什么内容的学科, 答:数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象 及对象间的关系和施加于对象的操作等的学科 2. 2. 数据元素之间的关系在计算机中有几种表示方法,各有什么特点, 答:四 种表示方法 栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 数据结构模拟卷(含答案)经典习题 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是__________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 一、选择题(20分) 1．下面关于线性表的叙述错误的是（D ）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 3．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C ）。 (A) 9 (B) 10 (C) 11 (D) 12 4．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（B ）。 (A) O(1) (B) O(log2n) (C) (D) O(n2) 5．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（B ）方法可以达到此目的。 (A) 快速排序(B) 堆排序(C) 归并排序(D) 插入排序 第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。 6.下列四种排序中（D ）的空间复杂度最大。 (A) 插入排序(B) 冒泡排序(C) 堆排序(D) 归并排序 7．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。 (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2) 8．设一棵二叉树的深度为k，则该二叉树中最多有（D ）个结点。 (A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1 9．在二叉排序树中插入一个结点的时间复杂度为（B ）。 (A) O(1) (B) O(n) (C) O(log2n) (D) O(n2) 10．设用链表作为栈的存储结构则退栈操作（B ）。 (A) 必须判别栈是否为满(B) 必须判别栈是否为空 (C) 判别栈元素的类型(D) 对栈不作任何判别 11．下列四种排序中（A ）的空间复杂度最大。 (A) 快速排序(B) 冒泡排序(C) 希尔排序(D) 堆 12．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（C ）。 (A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1 (D) N0=2N1+l 13.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不 超过（A ）。 (A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1) 14．数据的最小单位是（A ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 15．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（D ）。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n) 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i I Single Choice(10 points) 1. ( a )For the following program fragment the running time(Big-Oh) is . i = 0; s = 0; while(s <( 5*n*n + 2)) { i++; s = s + i; } a. O(n) b. O(n2) c. O(n1/2) d. O(n3) 2. ( c )Which is non-linear data structure_____. a. queue c. tree d. sequence list 3.( b )The worst-time for removing an element from a sequence list (Big-Oh) is . a. O(1) b. O(n) c. O(n2) d. O(n3) 4.( d )In a circular queue we can distinguish(区分) empty queues from full queues by . a. using a gap in the array b. incrementing queue positions by 2 instead of 1 a count of the number of elements d. a and c 5.( b )A recursive function can cause an infinite sequence of function calls if . a.the problem size is halved at each step b.the termination condition is missing c.no useful incremental computation is done in each step d.the problem size is positive 6．( c )The full binary tree with height 4 has nodes. a. 15 b. 16 7. ( b )Searching in an unsorted list can be made faster by using . a.binary search 基本概念典型例题 一、单项选择题 [例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。 ①A.算法B. 数据元素C. 数据操作D. 逻辑结构 ②A. 操作B. 映像C. 存储D．关系 解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。 [例6-2]数据的常用存储结构中不包括( )。 A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。 [例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。 ①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。 [例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; 《数据结构与算法》复习题 选择题 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑 B．存储 C．逻辑和存储 D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何 B．结点个数的多少 C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是 O(n2) 。 s =0; for( I =0; i 第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 数据结构练习题及参考答案 《数据结构》练习题 一、解答题（共50分） 1、（8分）假设用于通讯的电文字符集及其出现的频率如下表所 请为这8个字符设计哈夫曼编码，并画出其哈夫曼树，计算 WPL。 2.（8分）若一棵二叉树中序遍历和后序遍历序列分别为： DBEHGAFIC和DHGEBIFCA。试画出这棵二叉树，并写出其 先序遍历和层序遍历序列。 3.（16分）以下无向网络以邻接表为存储结构（假设邻接表的 顶点表按字母a、b、c、d、e、f、g、h的顺序依次存储，邻接表 的边表结点按顶点的下标由小到大链接）。请画出其邻接表，并 写出从顶点f出发，分别进行深度和广度优先遍历的序列，写出用Prime方法从顶点c 开始产生最小生成树的边的序列。 4.（8分）已知键值序列为(44，39，67，25，52，59，43，84，54，58，15，26，12，73，92，69)，取填充因子α=0.8，采用线性探查法处理冲突，试构造散列表。 ⒌（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81)，用希尔排序方法进行排序，d1=5,d2=3,d3=1,则第二趟的排序结果是（）。 ⒍（5分）已知一组记录为(67,88,15,12,60,37,7,31,45,81) ，用堆（大根堆）排序方法进 行排序，第一趟的排序结果是（）。 二、完善程序（共20分，每空2分） 1.假设一组递减有序的原始数据存储在数组r中，存放元素的下标下限为low,下标上限为high,以下是在数组中查找数值为k的折半查找算法。请填空完善程序。 int BinSearch(int r[ ], int low,int high,int k) { int l,h,m; l= low; h= high; while ( ⑴) { m= ⑵; if (k < r[m]) ⑶; else if (k > r[m]) ⑷; else return m; } return 0; } 2. 以下程序功能是将数组r中，从下标first到end之间的元素进行快速排序的分区。请填空，完善程序。 int Partition(int r[ ], int first, int end) { int i,j,t; i=first; j=end; //初始化 while ( ⑸) { while (i 典型题目分类 §1 概述 ［全真模拟试卷３选择题３］数据结构中，与计算机无关的是数据的 Ａ存储结构Ｂ物理结构Ｃ逻辑结构Ｄ物理和存储结构 答案：Ｃ ［全真模拟试卷５选择题１］数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及Ａ数据的存储结构Ｂ计算方法Ｃ数据映象Ｄ逻辑存储 答案：Ａ ［全真模拟试卷５选择题３］在计算机中，算法是指 Ａ加工方法Ｂ解决方案的准确而完整的描述 Ｃ排序方法Ｄ查询方法 答案：Ｂ ［全真模拟试卷１填空题１］算法的基本特征是可行性、确定性、和拥有足够的情报。 答案：有穷性 ［全真模拟试卷６选择题２］算法分析的目的是 Ａ找出数据结构的合理性Ｂ找出算法中输入和输出之间的关系Ｃ分析算法的易懂性和可靠性Ｄ分析算法的效率以求改进 答案：Ｄ ［全真模拟试卷６填空题１］在算法正确的前提下，评价一个算法的两个标准是。答案：时间复杂度和空间复杂度［专家预测试卷３填空题１］算法的工作量大小和实现算法所需的存储单元多少分别称为算法的。 答案：时间复杂度和空间复杂度 ［全真模拟试卷３选择题１］算法的空间复杂度是指 Ａ算法程序的长度Ｂ算法程序中的指令条数 Ｃ算法程序所占的存储空间Ｄ执行过程中所需要的存储空间答案：Ｄ §2 线性表 ［全真模拟试卷６选择题３］线性表Ｌ＝（a1,a2,……,a i,……,a n），下列说法正确的是 Ａ每个元素都有一个直接前件和直接后件 Ｂ线性表中至少要有一个元素 Ｃ表中诸元素的排列顺序必须是由小到大或由大到小 Ｄ除第一个元素和最后一个元素外，其余每个元素都有且只有一个直接前件和一个直接后件 答案：Ｄ ［全真模拟试卷７选择题１］下列叙述正确的是 Ａ线性表是线性结构Ｂ栈和队列是非线性结构 Ｃ线性链表是非线性结构Ｄ二叉树是线性结构 答案：Ａ ［专家预测试卷３选择题１］根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成 Ａ动态结构和静态结构Ｂ紧凑结构和非紧凑结构 Ｃ线性结构和非线性结构Ｄ内部结构和外部结构 答案：Ｃ ［全真模拟试卷３填空题１］数据的逻辑结构有线性结构和两大类。 答案：非线性结构 ［专家预测试卷１选择题３］线性表的顺序存储结构和线性表的链式存储结构分别是 Ａ顺序存取的存储结构，顺序存取的存储结构 Ｂ随机存取的存储结构，顺序存取的存储结构 Ｃ随机存取的存储结构，随机存取的存储结构 Ｄ任意存取的存储结构，任意存取的存储结构 答案：Ｂ ［全真模拟试卷５填空题１］长度为ｎ的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为。 答案：ｎ/2 §3 栈和队列 ［全真模拟试卷１选择题１］栈和队列的共同特点是 Ａ都是先进先出Ｂ都是后进先出 Ｃ只允许在端点处插入和删除元素Ｄ没有共同点 答案：Ｃ ［全真模拟试卷２选择题３］如果进栈序列为e1,e2,e3,e4，则可数据结构经典例题
经典数据结构面试题(含答案)
数据结构模拟卷(含答案)经典习题培训讲学
经典数据结构面试题(含答案)
数据结构课后习题及解析第二章
大数据结构经典复习题(仅供参考)
数据结构模拟卷(含答案)经典习题
数据结构经典例题
经典数据结构上机题_答案解析
数据结构例题解析(1)
数据结构典型例题
数据结构经典题目c语言代码
数据结构(C语言)【经典题库】含标准答案
数据结构第一章课后习题与答案
数据结构经典算法试题
数据结构课后习题详解(超完整,超经典)
数据结构练习题及
[IT认证]全国计算机等级考试《数据结构》典型试题