数据结构习题.doc

数据结构习题第一章 绪论一、单项选择题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分析算法的易懂性和文档性A空间复杂性和时间复杂性 B正确性和简明性 C可读性和文档性 D数据复杂性和程序复杂性6数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科。 A操作对象 B计算方法 C逻辑存储 D数据映象 A结构 B关系 C运算 D算法7数据结构被形式地定义为（K，R），其中K是 的有限集合，R是K上的 的有限集合。 A算法 B数据元素 C数据操作 D逻辑结构 A操作 B映象 C存储 D关系8在数据结构中，从逻辑上可以把数据结构分成 。 A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构二、填空题1.数据的基本单位是 ，最小单位 。2.算法的的特性有 、 、 、输入、输出 。3.数据结构按结点的关系，可分为4种逻辑结构： 、 、树结构、图结构。 4. 数据结构的存储结构包括顺序、_、索引和散列等四种。5算法质量的度量标准有两个： 复杂度和 复杂度。6数据的逻辑结构是从逻辑关系上描述数据，它与数据的_无关，是独立于计算机的。7线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。8下面程序段的时间复杂度是 。 for (i=1; in; i+)for (j=1; jn; j+) x+;for (k=1; kn;k+) x+;9下面程序段的时间复杂度是 。for(i=0; in; i+)for(j=i; jn;j+) x+;10下面程序段的时间复杂度是 。 int Time (int n) count=0; x=2; while (xn/2) x *= 2; count+; return (count) 11下面程序段的时间复杂度是 。 s0； for（i=0；in；i+） for（j=0; jn; j+） s+=bij； sum=s; 12下面程序段的时间复杂度是 。 for (i=1; in; i+)for (j=1; jn; j+) x+;for (k=1; knext = NULL; C. first-next = first; D. first != NULL; 10.用链表表示线性表的优点是( )A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同11.在一个单链表中，已知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;12. 已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（ ）。 A. O(1) B. O(m) C. O(n) D. O(m+n)13设单链表中结点的结构为typedef struct node file:/链表结点定义ElemType data； file:/数据struct node * Link； file:/结点后继指针 ListNode；（1）已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？A. s-link = p； p-link = s；B. s-link = p-link； p-link = s；C. s-link = p-link； p = s；D. p-link = s； s-link = p；（2）非空的循环单链表first的尾结点（由p所指向）满足：A. p-link = NULL；B. p = NULL；C. p-link = first；D. p = first；14线性表采用链式存储时，结点的存储地址（ ） A必须是不连续的 B连续与否均可 C必须是连续的 D和头结点的存储地址相连续15将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（） AO（1） BO（n）CO（m） DO（m+n）16线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 A随机存取 B顺序存取 C索引存取 D散列存取17.下面关于线性表的叙述中，错误的是哪一个？（ ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。18线性表是具有n个（ ）的有限序列（n0）。 A表元素 B字符 C数据元素 D数据项19下面的叙述不正确的是（ ）A线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关20设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表21线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 A随机存取 B顺序存取 C索引存取 D散列存取22下述哪一条是顺序存储结构的优点？（ ）A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示23若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表24设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表25线性表（a1,a2,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ）AO（i） BO（1） CO（n） DO（i-1）26循环链表h的尾结点p的特点是（ ）Apnext=h Bpnext=h-next Cp=h Dp=h-next 27完成在双循环链表结点p之后插入s的操作是（ ）A p-next=s ; s-priou=p; p-next-priou:=s ; s-next=p-next;B p-next-priou=s; p-next=s; s-priou=p; s-next:=p-next;Cs-priou=p; s-next:=p-next; p-next=s; p-next-priou=s ;Ds-priou=p; s-next:=p-next; p-next-priou=s ; p-next=s;28双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（ ）（链中结点数大于2，p不是第一个结点）Ap-llink-rlink=p-llink; p-llink-rlink=p-rlink; dispose(p);Bdispose(p); p-llink-rlink=p-llink; p-llink-rlink=p-rlink;Cp-llink-rlink=p-llink; dispose(p); p-llink-rlink=p-rlink;D以上A，B，C都不对。 二、填空题1向一个长度为n的向量的第i个元素(1in)之前插入一个元素时，需向后移动 _个元素。2线性表（a1,a2，an）以链接方式存储时，在第i个位置删除一个元素的时间复杂度是_ _。3. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_存储结构。4.链表适用于 查找。5.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的_域的值。 6.在一个链式栈中，若栈顶指针等于NULL则为_。 7.在链表中进行插入和 操作的效率比在顺序存储结构中进行相同操作的效率高。8.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的_域的值。 9在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=_。10. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 _个，单链表为_个。11线性表L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。12在单链表中设置头结点的作用是_。13对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为_,在给定值为x的结点后插入一个新结点的时间复杂度为_。14根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_和_；而又根据指针的连接方式，链表又可分成_和_。15. 在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句：s-next=p； s-prior= _；p-prior=s；_=s；16.顺序存储结构是通过_表示元素之间的关系的;链式存储结构是通过_表示元素之间的关系的。17. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 _个，单链表为_个。18. 循环单链表的最大优点是：_。19. 带头结点的双循环链表L中只有一个元素结点的条件是：_20. 在单链表L中，指针p所指结点有后继结点的条件是： 21. 带头结点的双循环链表L为空表的条件是：_。三、判断题1.顺序存储方式只能用于存储线性结构。 2.顺序表和一维数组一样，都可以按下标随机（或直接）访问。3.顺序表用一维数组作为存储结构，因此顺序表是一维数组。4.通常使用两个类来协同表示单链表，即链表的结点类和链表类。5.在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素。6.线性表采用顺序存储表示时，必须占用一片连续的存储单元。7.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。 8线性表的逻辑顺序与物理顺序总是一致的。9线性表的顺序存储表示优于链式存储表示。10线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。四、应用题1线性表的顺序存储表示和链式存储表示的特点比较。2.这是一个统计单链表中结点的值等于给定值x的结点数的算法，其中while循环有错，请重新编写出正确的while循环。 int count ( ListNode * Ha, ElemType x ) / Ha为不带头结点的单链表的头指针int n = 0;while ( Ha-link != NULL ) Ha = Ha-link; if ( Ha-data = x ) n+;return n; 五、算法设计题1设带表头结点的双向链表的定义为typedef int ElemType；typedef struct dnode file:/双向链表结点定义ElemType data； file:/数据struct dnode * lLink， * rLink； file:/结点前驱与后继指针DblNode；typedef DblNode * DblList； file:/双向链表试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域rLink中，并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来。2假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。3. 已知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。4. 顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性表空间足够大。试用类C语言给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。5. 设 Listhead为一单链表的头指针，单链表的每个结点由一个整数域DATA和指针域NEXT组成，整数在单链表中是无序的。编一类C过程，将 Listhead链中结点分成一个奇数链和一个偶数链，分别由P,Q指向，每个链中的数据按由小到大排列。程序中不得使用 NEW过程申请空间。6. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。7. 已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。8. 已知p指向双向循环链表中的一个结点，其结点结构为data、llink、rlink三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。9. 线性表(a1,a2,a3,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法完成：（1） 用最少时间在表中查找数值为x的元素。（2） 若找到将其与后继元素位置相交换。（3） 若找不到将其插入表中并使表中元素仍递增有序。10 已知两个单链表A和B,其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。11在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70），分析算法的时间复杂度。12. 函数reverse()实现将已知不带头结点的单链表的链接顺序颠倒的功能，即第一表元变为最后表元，第二表元变为倒数第二表元，最后表元变为第一表元。函数中h为链表的头指针，q2为第一个尚未颠倒的链表表元，q1为已颠倒链表的第一个链表表元。Typedef struct node int data; struct node *next;node; /链表的形式说明void reverse(node h) node *q1, *q2; ; q1=NULL; while (q2!=NULL) ; ; h=q2; ; =q1; 13. 设有一个表头为first的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点按逆序链接。14阅读下面的算法 LinkList mynote(LinkList L) /L是不带头结点的单链表的头指针 if(L&L-next)q=L；L=Lnext；p=L；S1： while(pnext) p=pnext；S2： pnext=q；qnext=NULL； returnL；请回答下列问题： （1）说明语句S1的功能；（2）说明语句组S2的功能； （3）设链表表示的线性表为（a1,a2, ,an）,写出算法执行后的返回值所表示的线性表。15.一个顺序存储的线性表内存储整数，编写算法，将负整数移到线性表的前边，非负整数移到线性表的后边。Move5（list r，int n）第三章 栈和队列一、单项选择题1. 对于栈操作数据的原则是（ ）。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序1.链式栈与顺序栈相比，一个比较明显的优点是( )A.插入操作更加方便 B.通常不会出现栈满的情况 C.不会出现栈空的情况 D.删除操作更加方便2.在一个顺序存储的循环队列中，队头指针指向队头元素的( )A.前一个位置 B.后一个位置 C.队头元素位置 D.队尾元素的前一位置3.栈和队列都是（ ）。A.顺序存储的线性结构 B.链式存储的线性结构 C.限制存储点的线性结构 D.限制存储点的非线性结构4.设输入序列为1,2,3,4,5，借助一个栈不可能得到的输出序列是( ) 。A.1,2,3,4,5 B.1,4,3,2,5 C.4，1,3,2,5 D.1,3,2,5,4 5. 假定一个带头结点的链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。 A. front = rearB. front != NULL C. rear != NULL D. front = NULL6. 设有一个递归算法如下 int fact(int n) /n大于等于0 if(n0) ? x* f(x-1):2); int i ; i =f(f(1);A2 B. 4 C. 8 D. 无限递归25. 表达式a*(b+c)-d的后缀表达式是( )。Aabcd*+- B. abc+*d- C. abc*+d- D. -+*abcd26. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。A线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈27. 用链接方式存储的队列，在进行删除运算时（ ）。A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改28. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。A仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改29. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。A队列 B多维数组 C栈 D. 线性表30. 假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m31. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 32. 已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有（ ）。 A. dacb B. cadb C. dbca D. bdac E. 以上答案都不对 33. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。 A. (rear+1) MOD n=front B. rear=front Crear+1=front D. (rear-l) MOD n=front34. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。A 6 B. 4 C. 3 D. 2二、填空题1若一个栈以数组V1.n存储，初始栈顶指针为top，元素X的入栈操作为_。2. 栈是一种限定在表的一端进行插入和删除的线性表，又被称为_的线性表。3. 如果一个对象部分地包含自己，或自己定义自己，则称这个对象是_的对象。4.设有一个顺序栈S，元素S1，S2，S3，S4，S5，S6依次进栈，如果6个元素的出栈顺序为S2，S3，S4，S6，S5，S1，则顺序栈的容量至少应为 。5.通常程序在调用另一个程序时，都需要使用一个 来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。6.在一个链式栈中，若栈顶指针等于NULL则为_。 7栈顶的位置是随着_操作而变化的。8在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 ，当删除一个队列元素时，头指针 。 9.循环队列用数组A0.m-1存放其元素值。已知其头尾指针分别是front和rear，则当前队列中的元素个数是 ，判断队空的条件是 。10循环队列Q中，front和rear分别指示队列头元素及队尾元素的位置，最大队列长度为maxsize，则判断队空的条件是 ，队满的条件是 。11.队列的插入操作在 进行，删除操作在 进行。12.在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 ，当删除一个队列元素时，头指针 。 13栈是_ _的线性表，其运算遵循_的原则。14_ _是限定仅在表尾进行插入或删除操作的线性表。15. 设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_，而栈顶指针值是_H。设栈为顺序栈，每个元素占4个字节。16. 当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top1与top2，则当栈1空时，top1为_，栈2空时 ，top2为_，栈满时为_。17两个栈共享空间时栈满的条件_。18在作进栈运算时应先判别栈是否 ;在作退栈运算时应先判别栈是否 ；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为 。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的 分别设在内存空间的两端，这样只有当 时才产生溢出。19. 多个栈共存时，最好用_作为存储结构。20表达式23+(12*3-2)/4+34*5/7)+108/9的后缀表达式是_。21. 循环队列的引入，目的是为了克服_。 22. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_。23区分循环队列的满与空，只有两种方法，它们是_和_。24. 设循环队列存放在向量sq.data0:M中，则队头指针sq.front在循环意义下的出队操作可表示为_，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_。25表达式求值是_应用的一个典型例子。三、判断题1.栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。2.通常递归的算法简单、易懂、容易编写，但执行的效率不高。 3.在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。 4.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 5.用非递归方法实现递归算法时一定要使用递归工作栈。 6队列只允许在表的一端进行插入，而在另一端删除元素。 四、应用题1设有一个顺序栈S，元素s1， s2， s3， s4， s5， s6依次进栈，如果6个元素的出栈顺序为s2， s3， s4， s6， s5， s1，则顺序栈的容量至少应为多少？2. 试推导出当总盘数为n的Hanoi塔的移动次数。3. 用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。4. 举例说明顺序队的“假溢出”现象，并给出解决方案。五、算法设计题1. 设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区O.maxsize-1,为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。2. 设从键盘输入一整数的序列：a1, a2, a3，an,试编写算法实现：用栈结构存储输入的整数，当ai-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。3. 设表达式以字符形式已存入数组En中，#为表达式的结束符，试写出判断表达式中括号（和）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。) 4. 如果允许在循环队列的两端都可以进行插入和删除操作。要求：（1）写出循环队列的类型定义；（2）写出“从队尾删除”和“从队头插入”的算法。5线性表中元素存放在向量A（1,n）中，元素是整型数。试写出递归算法求出A中的最大和最小元素。6. 已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若n等于零，则返回m；第二步：若m小于n，则m与n相互交换；否则，保存m，然后将n送m，将保存的m除以n的余数送n。 （1）将上述过程用递归函数表达出来（设求x除以y的余数可以用x MOD y 形式表示）。（2）写出求解该递归函数的非递归算法。7设计算法以求解从集合1.n中选取k（k=n）个元素的所有组合。例如，从集合1.4中选取2个元素的所有组合的输出结果为：1 2，1 3，1 4，2 3， 2 4，3 4。8假设两个队列共享一个循环向量空间，其类型Queue2定义如下：typedef structDateType dataMaxSize；int front,rear；Queue2；对于i=0或1，fronti和reari分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。 int EnQueue (Queue2*Q,int i,DateType x)/若第 i个队列不满，则元素x入队列，并返回1；否则返回0if(i1)return 0；if(Qreari=Qfront return0；Qdata =x；Qreari= ; return 1； )六、简答题1.（1）什么是递归程序？ （2）递归程序的优、缺点是什么？ （3）递归程序在执行时，应借助于什么来完成？（4）递归程序的入口语句、出口语句一般用什么语句实现？ 2. 当过程P递归调用自身时，过程P内部定义的局部变量在P的2次调用期间是否占用同一数据区？为什么？ 3. 在一个算法中需要建立多个堆栈时可以选用下列三种方案之一，试问：这三种方案之间相比较各有什么优缺点？（1）分别用多个顺序存储空间建立多个独立的堆栈；（2）多个堆栈共享一个顺序存储空间；（3）分别建立多个独立的链接堆栈。第四章 串一、单项选择题1串是一种特殊的线性表，其特殊性体现在（