最新数据结构第二章试题

第2章线性表一选择题1．下述哪一条是顺序存储结构的优点？（）【北方交通大学 2001 一、4（2分）】A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）【北方交通大学 2001 一、14（2分）】A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3．线性表是具有n个（）的有限序列（n>0）。

【清华大学 1998 一、4（2分）】A．表元素 B．字符 C．数据元素 D．数据项 E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

【哈尔滨工业大学 2001二、1（2分）】A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

【南开大学 2000 一、3】A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。

A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表【合肥工业大学 2000 一、1（2分）】7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。

则采用（）存储方式最节省运算时间。

【北京理工大学 2000一、1（2分）】A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表8. 静态链表中指针表示的是（）. 【北京理工大学 2001 六、2（2分）】A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址9. 链表不具有的特点是（）【福州大学 1998 一、8 (2分)】A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比10. 下面的叙述不正确的是（）【南京理工大学 1996 一、10（2分）】A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关11. 线性表的表元存储方式有(（1）)和链接两种。

数据结构Java版第二章习题在学习数据结构的过程中，第二章的习题往往是巩固和深化对相关概念理解的重要环节。

这一章可能涵盖了诸如数组、链表、栈、队列等基本数据结构的知识。

先来说说数组，这是一种最简单也最常见的数据结构。

在 Java 中，数组是一组相同类型元素的有序集合。

它的优点很明显，比如可以通过索引快速访问元素，查找操作的时间复杂度为 O(1)。

但缺点也不能忽视，比如数组的长度固定，插入和删除元素可能需要移动大量元素，导致时间复杂度较高。

来看一道关于数组的习题：给定一个整数数组，找出其中出现次数最多的元素。

这就需要我们遍历数组，使用一个辅助的数据结构（比如哈希表）来记录每个元素出现的次数，最后找出出现次数最多的那个元素。

再说说链表，链表是由一系列节点组成的，每个节点包含数据和指向下一个节点的引用。

相比于数组，链表在插入和删除操作上具有优势，时间复杂度为 O(1)。

但查找操作的时间复杂度为 O(n)。

有这样一道链表的习题：实现一个链表的反转。

这就需要我们改变链表节点的指针指向，依次将每个节点的 next 指针指向前一个节点，从而实现链表的反转。

接下来是栈，栈是一种特殊的线性表，遵循后进先出（LIFO）的原则。

在 Java 中，可以使用数组或者链表来实现栈。

比如有这样一道关于栈的习题：判断一个表达式中的括号是否匹配。

我们可以将左括号入栈，遇到右括号时弹出栈顶的左括号进行匹配，如果最后栈为空，则括号匹配成功。

然后是队列，队列遵循先进先出（FIFO）的原则。

在实际应用中，比如排队系统、任务调度等都可以用到队列。

例如，有这样一道队列的习题：实现一个循环队列。

这就需要我们处理好队列的头尾指针，以及队列满和空的判断条件。

在解决这些习题的过程中，我们不仅要熟练掌握各种数据结构的特点和操作方法，还要具备良好的逻辑思维和代码实现能力。

同时，通过不断地练习和思考，我们能够更加深入地理解数据结构的本质，为今后解决更复杂的问题打下坚实的基础。

7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。

则采用（）存储方式最节省运算时间。

【北京理工大学 2000 一、1（2分）】A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表8. 静态链表中指针表示的是（）. 【北京理工大学 2001 六、2（2分）】A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址9. 链表不具有的特点是（）【福州大学 1998 一、8 (2分)】A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比10. 下面的叙述不正确的是（）【南京理工大学 1996 一、10（2分）】A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关11. 线性表的表元存储方式有(（1）)和链接两种。

试指出下列各表中使用的是何种存储方式：表1是(（2）)存储方式；表2是(（3）)存储方式；表3是(（4）)存储方式；表4是(（5）)存储方式。

表左的s指向起始表元。

供选择的答案：A.连续B.单向链接C.双向链接D.不连接E.循环链接F.树状G.网状H.随机I.顺序J.顺序循环【上海海运学院 1995 二、1（5分）】12.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。

所以，它存取表中第i个元素的时间与i无关。

(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是（）【南京理工大学 2000 一、3（1.5分）】A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）13. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1Rlink=p;p->Llink->Rlink=q;q->Llink=q；B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;24．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。

《数据结构》第1-2章练习题一、选择1、通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。

以下解释错误的是( )A、正确性算法应能正确地实现预定的功能(即处理要求)B、易读性算法应易于阅读和理解以便于调试修改和扩充C、健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果D、高效性即达到所需要的时间性能2、以下说法正确的是 ( )A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、数据结构是带有结构的数据元素的集合3、对于顺序表，以下说法错误的是（）A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中数组的下标可以看成是元素的相对地址4、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作A、条件判断B、结点移动C、算术表达式D、赋值语句5、对于顺序表的优缺点，以下说法错误的是（）A、无需为表示结点间的逻辑关系而增加额外的存储空间B、可以方便地随机存取表中的任一结点C、插入和删除运算较方便D、容易造成一部分空间长期闲置而得不到充分利用6、链表不具有的特点是：A、可随机访问任一个元素B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表长度成正比7、若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（）存储方式节省时间A、单链表B、双向链表C、单循环链表D、顺序表顺序表可以随机存取8、设指针P指向双链表的某一结点，则双链表结构的对称性可用（）式来刻画A、p->prior->next->==p->next->nextB、p->prior->prior->==p->next->priorC、p->prior->next->==p->next->priorD、p->next->next==p->prior->prior9、以下说错误的是（）A、对循环来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表B、对单链表来说，只有从头结点开始才能扫描表中全部结点C、双链表的特点是找结点的前趋和后继都很容易D、对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。

数据结构第二章习题数据结构第二章习题2.1.1 向量1．定义向量指的是所有元素都是同一类型结点的线性表。

向量的定义如下：typeof ElemType vector[n0]这里的ElemType 可以是任何相应的数据类型如int, float 或char 等，在算法中，我们规定ElemType 缺省是int 类型。

向量中的元素个数n 小于或等于某一整数n0。

说明在C语言中，数组的下标是从0开始的，但为了描述算法简洁，本书中的向量规定从下标1开始，这样，读者可不必考虑下标0的数组值。

2．向量的建立输入n个整数，产生一个存储这些整数的向量A的函数如下：void create ( A, n)vector A;int n;{int i;for (i=0;i<=n;i++)scanf (“%d’,A[i])；}3．向量的存储方法向量通常的存储方法是顺序存储，每个元素在存储中占用的空间大小相同，若第一个元素存放的位置是LOC(k1), 每个元素占用的元素大小为s，则元素k i 的存放位置为：LOC(k i)= LOC(k1)+s * (i-1)任给一个i，便可以很快计算出LOC(k i)，因此，对顺序存储的向量要查找任何一个元素都很方便。

单项选择题1．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是①。

A) 110 B) 108 C) 100 D)1204．向量的插入在一个有n个元素的向量A中的第i个元素之前插入一个元素x的函数如下：void insert (A,n,x)vector A;int n,x;{int j;if (I<1 || i>n) printf (“值错误！\n”);else{for (j=n;j>=i;j--) A[j+1]=A[j]; /*将第i个元素及其后的元素后移*/A[j]=x;n++; /向量长度增1*/}}5．向量的删除在一个有n个元素的向量A中删除第i个的函数如下：void delete (A,n)vector A;int n;{int j;if (I<1 || i>n)printf (“i值错误！\n”);else{for (j=1;j<=n;j++) A[j]=a[j+1]; /*第i个元素之后的元素前移*/ n---;}}6. 向量的查找在一个有n个元素的向量A中查找元素值为x的元素的函数如下：void find(A, n,x)vector A;int n, x;{int j；i=1;while(I<=n&& A[i]<>x)I++;if(I<=n)printf(“找到了！\n”);elseprintf(“未找到\n”);}2.2.1 向量习题解析1、已知一个向量A，其中的元素按值非递减有序排列，编写一个函数插入一个元素x后保持该向量仍按递减有序排列。

第2章 自测练习题参考答案3.在一个顺序表中，若表的第一个元素的存储地址是210，每一个元素的长度为3，则第5个元素的存储地址是多少？解：210+（5-1）*3=222 4．在长度为n 的顺序表中插入一个元素时,等概率情况下的平均移动元素次数是多少？ 解：n/25.写出带表头结点的单链表H 为空表的条件。

解：H->next==NULL6.写出在单链表中某P 结点后插入S 结点的语句。

解：S->next=P->next; P->next=S;7.画出执行下列各行语句后各指针及链表的示意图。

L=(LNode*)malloc(sizeof (LNode)); p=L;for(i=1;i<=4;i++)｛p->next=(LNode*)malloc(sizeof(LNode)); p=p->next; P->data=i*2-1; ｝p->next=NULL; 解：8.输出带表头结点的非空单向循环链表} 9. s=0;p=H->next;while( P ){s=s+ p->data ; p=p->next; }天然气旅馆天然气旅馆天然气旅馆return s; }10.有以下算法：void algo(LNode *H1,LNode *H2){ p=H1;while(p->next!=NULL) p=p->next; p->next=H2; }其中H1和H2分别是两个不同单链表的头指针。

此算法完成什么功能？ 解：将单链表H2连接到单链表H1后。

11.仔细阅读下面的算法，简述算法的功能。

void algo2(LNode *s,LNode *q){ p=s;while(p->next!=q) p=p->next; p->next=s; }void algo1(LNode *pa,LNode *pb){/*pa,pb 分别指向循环单链表中的两个结点*/ algo2(pa,pb); algo2(pb,pa); }解：将原表分成两个分别以p1和p2为头指针的循环单链表。

数据结构与算法上机作业第二章线性表一、选择题1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间复杂度为。

A. O(log2n)B. O(1)C. O(n)D. O(n2)2、以下关于线性表的说法中，不正确的是。

A. 线性表中的数据元素可以是数字、字符、结构等不同类型B. 线性表中包含的数据元素个数不是任意的C.线性表中的每一个结点都有且只有一个直接前驱和直接后继（单项链表）D.存在这样的线性表：表中各结点都没有直接前驱和直接后继（数组实现）3、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为。

A. O(1)B. O(n)C. O(n2)D. O(log2n)4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为。

A. nB. (n-1)/2C. n/2D. (n+1)/2已经有N个点了,再加一个就是N+1个.假设新加的结点插在第i位,那么后面N+1-i个结点都要往后移动.i的取值服从1到N+1的平均分布,即概率是1/(N+1).求期望得N/2,即平均要移动N/2个结点期望有计算公式，这里等于(N+1-1)*1/(N+1)+(N+1-2)*1/(N+1)+(N+1-3)*1/(N+1)+...+(N+1-N-1)*1/(N+1)=N/25、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度(及x同元素的平均比较次数，假定查找每个元素的概率都相等)为。

A. nB. n/2C. (n+1)/2D. (n-1)/26、在顺序表中，只要知道，就可以求出任一结点的存储地址。

A. 基地址B. 结点大小C. 向量大小D. 基地址和结点大小7、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是。

A. nB. 2n-1C. 2nD. n-18、线性表采用链表存储时其存储地址要求。

A. 必须是连续的B. 部分地址必须是连续的C. 必须是不连续的D. 连续的和不连续的都可以9、下面关于线性表的描述中，错误的是。

《数据结构》第二章线性表习题一、单项选择题1. 线性表是________。

A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。

A．n-i B．n-i+l C．n-i-1 D．i3. 线性表采用链式存储时，其地址________。

A．必须是连续的B．一定是不连续的C．部分地址必须是连续的D．连续与否均可以4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。

A．n/2 B．n C．（n+1）/2 D．（n-1）/25. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。

A． p->next=s; s->prior=p;p->next->prior=s; s->next=p->next;B． s->prior=p; s->next=p->next;p->next=s; p->next->prior=s;C． p->next=s; p->next->prior=s;s->prior=p; s->next=p->next;D． s->prior=p; s->next=p->next;p->next->prior=s; p->next=s;6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。

A．p->next=p->next->next; B．p=p->next; C．p=p->next->next; D．p->next=p;7. 在一个长度为n的顺序表中向第i个元素(0< i<n+l )之前插入一个新元素时，需向后移动______个元素。

数据结构第二章答案第二章习题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是给定的两个参变量，它们的值为任意的整数）。