数据结构题库

第一章 绪 论一，选择题1组成数据的基本单位是（C）A数据项 B 数据类型 C数据元素 D数据变量2数据结构是研究数据的（ C ）以及它们之间的相互关系。A理想结构，物理结构 B理想结构，抽象结构C物理结构，逻辑结构 D抽象结构，逻辑结构3算法分析的两个主要方面是（ D ）A正确性和简单性 B 可读性和文档性C数据复杂性和程序复杂性 D时间复杂度和空间复杂度4算法分析的目的是（ C ）。A 找出数据结构的合理性 B研究算法中的输入和输出的关系C分析算法的效率以求改进 D分析算法的易懂性和文档性5. 算法的时间复杂度取决于（ C ）A问题的规模 B. 待处理数据的初态 C. A 和 B 以上都不是6一个算法应该是（ B ）。A程序 B问题求解步骤的描述 C要满足五个基本特性 DA 和 C. 7. 下面关于算法说法错误的是（ D ）A算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的8从逻辑上可以把数据结构分为（ C ）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构9程序段 for ( i=n-1;i=1;i-)for (j=1;jAj+1)Aj与 Aj+1对换；其中 n 为正整数，则最后一行的语句频度在最坏情况下是（ D ）A O（n） B O(nlogn) C.O(n 3) DO(n 2) 10连续存储设计时，存储单元的地址（ A ）。A一定连续 B一定不连续 C不一定连续 D部分连续，部分不连续二，判断题1数据结构的抽象操作的定义与具体实现有关。( ) 2数据结构是数据对象与对象中数据元素之间关系的集合。（）3在顺序存储结构中，有时也存储数据结构中元素之间的关系。( )4数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用的需要建立的。（）5算法和程序原则上没有区别，在讨论数据结构是两者是通用的。( )6同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。( )7数据的逻辑结构与数据元素本身的内容和形式无关。（）8算法的优劣与算法描述语言无关，但与所用计算机有关。( )9健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（）10算法可以用不同的语言描述，如果用 C 语言或 PASCAL 语言等高级语言来描述，则算法实际上就是程序了。( )三，填空1数据的物理结构包括 数据元素 的表示和 数据元素间关系 的表示。2. 对于给定的 n 个元素,可以构造出的逻辑结构有 集合 ，线性结构， 树形结构 ，_图状结构或网状结构 _四种。3一个数据结构在计算机中表示（又称映像） 称为存储结构。4抽象数据类型的定义仅取决于它的一组_逻辑特性_，而与_ 在计算机内部如何表示和实现 _无关，即不论其内部结构如何变化，只要它的_ 数学特性 _不变，都不影响其外部使用。5线性结构中元素之间存在一对一关系,树形结构中元素之间存在 一对多关系, 图形结构中元素之间存在 多对多关系。6一个算法有 5 个特性:有穷性、确定性、可行性，有零个或多个输入、有一个或多个输出。7已知如下程序段for（i= n；i=i;j-)s; 10. 下面程序段的时间复杂度为_O(n)_。(n1) sum=1；for (i=0;sumnext=h B. p-next=NIL C. p-next-next=h D. p-data=-12下面关于线性表的叙述中，错误的是哪一个？（ B ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。3线性表是具有 n 个（ C ）的有限序列（n0）。 A表元素 B字符 C数据元素 D数据项 4若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表5某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表6设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表7在带有头结点的单链中插入一个新结点时不可能修改（ A ）。A头指针 B头结点指针域 C开始结点指针域 D其它结点指针域8 双向链表中有两个指针域，llink 和 rlink，分别指向前驱及后继，设 p 指向链表中的一个结点，q 指向一待插入结点，现要求在 p 前插入 q，则正确的插入为（ D ）。 A. p-llink=q; q-rlink=p; p-llink-rlink=q; q-llink=p-llink;B. q-llink=p-llink; p-llink-rlink=q; q-rlink=p; p-llink=q-rlink; C. q-rlink=p; p-rlink=q; p-llink-rlink=q; q-rlink=p;D. p-llink-rlink=q; q-rlink=p; q-llink=p-llink; p-llink=q;9对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是（ B ）。Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL10在顺序表中查找第 i 个元素的时间效率最高的算法时间复杂度是（ A ）。AO(1) BO( ) CO(log 2n) DO(n) n11最好的情况下，在顺序表中按值查找一个元素的算法时间复杂度是（ D ）。AO(n) BO( ) CO(log 2n) DO(1) 12. 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为（ C ）(1link=head Bp-link=NIL Cp=NIL Dp= head二，判断1. 链表中的头结点仅起到标识的作用。( ) 2线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( )3顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( )4顺序存储方式只能用于存储线性结构。( )5线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。 ( )6. 线性表的特点是每个元素都有一个前驱和一个后继。( )7. 取线性表的第 i 个元素的时间同 i 的大小有关。 ( )8. 循环链表不是线性表。( )9. 线性表就是顺序存储的表。( )10. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )三，填空1当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序 存储结构。2线性表 L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（n-1）/2。3在一个长度为 n 的顺序表中第 i 个元素（1next=p-next、f-prior=p、p-next-prior=f、p-next=f。6. 在双向链表结构中，若要求在 p 指针所指的结点之前插入指针为 s 所指的结点，则需执行下列语句：s-next=p； s-prior=p-prior；p-prior=s；s-prior-next=s；7.顺序存储结构通过物理上相邻 表示元素之间的关系;链式存储结构通过指针表示元素之间的关系。8. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 4 个，单链表为 2 个。9. 已知指针 p 指向单链表 L 中的某结点，则删除其后继结点的语句是：u=p-next; p-next=u-next; free(u); ,时间复杂度是 O(1) ; 。10. 带头结点的双循环链表 L 中只有一个元素结点的条件是 L-next-next=L 。四，算法设计1 试写一算法在带头结点的单链表结构上实现线性表操作 LOCATE（L，X）。LNode* Locate(LinkList L,int x)/链表上的元素查找,返回指针for(p=l-next;pp=p-next);return p;/Locate 2试写一算法在带头结点的单链表结构上实现线性表操作 LENGTH（L）。int Length(LinkList L)/求链表的长度for(k=0,p=L;p-next;p=p-next,k+);return k;/Length3试写一算法实现顺序表的就地逆置，即利用原表的存储空间将线性表（a 1, a2, ,an）逆置为（a n, an-1, ,a1）。void reverse(SqList iA.elemj;/reverse 4试写一算法，对单链表实现就地逆置void LinkList_reverse(Linklist 为简化算法,假设表长大于 2p=L-next;q=p-next;s=q-next;p-next=NULL;while(s-next)q-next=p;p=q;q=s;s=s-next; /把 L 的元素逐个插入新表表头q-next=p;s-next=q;L-next=s;/LinkList_reverse分析:本算法的思想是,逐个地把 L 的当前元素 q 插入新的链表头部,p 为新表表头.5 . 设线性表 A =（a 1， a2， ,an），B=（b 1, b2, ,bn），试写一个按下列规则合并 A，B 为线性表 C 的算法，即使得C=（ a1, b1, , am ,bm ,bm+1, ,bn）当 mn 时；线性表 A，B 和 C 均以单链表作存储结构，且 C 表利用 A 表和 B 表中的结点空间构成。注意：单链表的长度值 m 和 n 均未显式存储。void merge1(LinkList q=B-next;C=A;while(pp-next=q; /将 B 的元素插入if(s)t=q-next;q-next=s; /如 A 非空,将 A 的元素插入p=s;q=t;/while/merge1第三章 栈和队列一，选择1. 对于栈操作数据的原则是（ B ）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序2. 已知输入序列为 abcd 经过输出受限的双向队列后能得到的输出序列有（ B ）。A. dacb B. cadb C. dbca D. badc 3. 最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是 （ B ）。A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front4 当利用大小为 n 的数组顺序存储一个栈时，假定用 top= =n 表示栈空，则向这个栈插入一个元素时首先应执行语句修改 top 指针。（ B ）Atop+ Btop- Ctop=0 Dtop5. 若已知一个栈的入栈序列是 1,2,3,n，其输出序列为 p1,p2,p3，p N,若 pN是 n，则 pi是( D )。A. i B. n-i C. n-i+1 D. 不确定6. 一个递归算法必须包括（ B ）。A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分7. 执行完下列语句段后，i 值为：（ B ）int f(int x) return (x0) ? x* f(x-1):2);int i ;i =f(f(1);A2 B. 4 C. 8 D. 无限递归8. 设栈 S 和队列 Q 的初始状态为空，元素 e1，e2，e3，e4,e5 和 e6 依次通过栈 S，一个元素出栈后即进队列 Q，若 6 个元素出队的序列是 e2，e4，e3,e6,e5,e1 则栈 S 的容量至少应该是( C )。A 6 B. 4 C. 3 D. 29. 栈和队列的共同点是（ C ）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点10. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。A线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈11. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( D )。A仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改12. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ C ）的数据结构。A队列 B多维数组 C栈 D. 线性表13. 假设以数组 Am存放循环队列的元素,其头尾指针分别为 front 和 rear，则当前队列中的元素个数为（ A ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m14. 循环队列存储在数组 A0.m中，则入队时的操作为（ D ）。A. rear=rear+1 B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 15. 若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为多少？( B) A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和 1 二，判断1. 任何一个递归过程都可以转换成非递归过程。（ ）2. 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。（ ）3. 队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ ）4. 循环队列也存在空间溢出问题。（ ）循环队列只是一个大小为 maxsize 的数组 空间有限 自然存在溢出问题5. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（ ）三，填空1栈是限定仅在表尾进行插入或删除操作的线性表。3中缀表达式 3*（x+2）-5 所