数据结构习题及答案(共48页).doc

《数据结构习题及答案(共48页).doc》由会员分享，可在线阅读，更多相关《数据结构习题及答案(共48页).doc（48页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据结构习题习题一一、选择题1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（B）和运算的学科。 A结构 B关系 C运算 D算法2、在数据结构中，从逻辑上可以把数据结构分成（C）。 A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D逻辑结构和存储结构3、线性表的逻辑顺序和存储顺序总是一致的，这种说法（B）。 A正确 B不正确 C无法确定 D以上答案都不对4、算法分析的目的是（C）。 A找出算法的合理性 B研究算法的输人与输出关系 C分析算法的有效性以求改进 D分析算法的易懂性二、填空题1、数据 是信息的载体，是对客观事物的

2、符号表示，它能够被计算机识别、存储、加工和处理，数据 是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。 2、数据元素是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。3、数据项是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为_数据项。 4、简而言之，数据结构是数据之间的相互关系，即数据的组织形式。 5、数据的逻辑结构是指数据之间的逻辑关系。逻辑结构是从逻辑关系上描述数据，它与具体存储无关，是独立于计算机的。因此逻辑结构可以看作是从具体问题抽象出来的数学模型。

3、 6、数据的存储结构指数据元素及其关系在计算机存储器内的表示。存储结构是逻辑结构在计算机里的实现，也称之为映像。 7、数据的运算是指对数据施加的操作。它定义在数据的逻辑结构之上，每种逻辑结构都有一个数据的运算。常用的有：查找、排序、插人、删除、更新等操作。 8、数据逻辑结构可以分为四种基本的类型，集合结构中的元素除了仅仅只是同属于一个集合_，不存在什么关系。 9、数据逻辑结构的四种基本类型中，线性结构_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。 10、数据逻辑结构的四种基本类型中，树形结

4、构中的元素是一种一对多的关系。 11、图型结构或图状结构是一种多对多的关系。在这种逻辑结构中，所有结点均可以有多个前驱和多个后继。 12、有时也可将树型结构、集合和图型结构称为非线性结构，这样数据的逻辑结构就可以分为线性结构和非线性结构两大类。 13、顺序存储方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。 14、链接存储方式是种存储方法，不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。 15、索引存储方式又可以分为稠密索引和稀疏索引。若每个结点在索引表

5、中都有一个索引项，则该种索引存储方式称为稠密索引_；若一组结点在索引表中只对应一个索引项，则索引存储方式称为稀疏索引。在稠密索引中，索引项的地址指示结点所在的位置，而稀疏索引中，索引项的地址指示一组结点的起始位置。 16、散列存储方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。 17、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组有限序列，其中每个指令表示一个或多个操作。18、算法的有穷_性是指算法必须能够在执行有限个步骤之后结束，并且每个步骤都必须在有穷的时间内完成。 19、算法的确定性是指算法中的每一个步骤

6、必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到相同的输出结果。 20、算法的可行性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的基本运算执行有限_次来实现，即算法的具体实现应该能够被计算机执行。 21、判断一个算法的好坏主要以下几个标准：正确性，可读性_、健壮性、效率。 22、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机运行时间的长短和所占据空间的大小。 23、空间复杂度（SPace ComPlexity）也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用存储

7、空间的大小。三、判断题 1、顺序存储方式只能用于存储线性结构。（）树型结构也可以用顺序方式进行存储。 2、数据元素是数据的最小单位。（）数据元素是数据的基本单位，数据项是数据的最小单位。 3、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言描述，则算法实际上就是程序了。（）算法用各种计算机语言描述表现为一个程序，但是不等于程序，程序逻辑不一定能满足有穷性。 4、数据结构是带有结构的数据元素的集合。（对）5、数据的逻辑结构是指各元素之间的逻辑关系，是用户根据需要而建立的。（对） 6、数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。（对） 7、数据的物理

8、结构是指数据在计算机中实际的存储形式。（对） 8、具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。（对）四、综合题 1、用大O形式表示下面算法的时间复杂度： for（i=0；im；i十十） for（j=0；jn；j） Aij=i*j； O(mn)。 2、写出下面算法的时间复杂度： i0； s=0； while(sn） i+; s+=i; O() 3、写出以下算法的时间复杂度： for（i0; im; i）for（j0 ; jt; j） cij=0；for（i=0；im；i） for（j=o; jt; j+） for（k=0；kn；k） cijaik*bkj; O(mnt)。4、写

9、出下面算法的时间复杂度：i=1;while（in） i=i*3; log3(n)。5、求下面函数中各条语句的频度和算法的时间复杂度：prime（int n） int i2； while (ni）！=0isqrt(n) ) i+; if（isqrt(n) ) printf（”d is a prime number.n”，n）； else printf（”d is not a prime number.n”，n）； O() 习题二一、选择题 1在一个长度为n的顺序表中删除第i个元素（0i=0）个数据元素的_有限序列。其中n为数据元素的个数，定义为线性表的长度。当n为零时的表称为空表。4所谓顺序表（

10、Sequential LISt）是线性表的顺序存储结构，它是将线性表中的结点按其逻辑顺序依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在地址相邻的存储单元中。5单链表不要求逻辑上相邻的存储单元在物理上也一定要相邻。它是分配一些任意的存储单元来存储线性表中的数据元素，这些存储单元可以分散在内存中的任意的位置上，它们在物理上可以是一片连续的存储单元，也可以是不连续的。因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的逻辑关系。6线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的数据域；另一部分用来存放元素的

11、指向直接后继元素的指针(即直接后继元素的地址信息)，称为指针域或链域。7线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种非顺序存储结构，又称为非顺序映像。8如果将单链表最后一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了循环链表。9为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了双向链表。10双向链表某结点的指针P，它所指向结点的后继的前驱与前驱的后继都是p所指向的结点本身。11在单链表中，删除指针P所指结点的后继结点的语句是P-next=p-next-next_。12在双循

12、环链表中，删除指针P所指结点的语句序列是P-prior-nextp-next及P-next-prior=P-prior _。13单链表是线性表的链接存储表示。14可以使用双链表表示树形结构。15向一个长度为n的向量的第i个元素(lin+1）之前插人一个元素时，需向后移动n-i+1个元素。16删除一个长度为n的向量的第i个元素（lin）时，需向前移动n-i个元素。17在单链表中，在指针P所指结点的后面插人一个结点S的语句序列是S-next=P-next; P-next=S18在双循环链表中，在指针P所指结点前插人指针S所指的结点，需执行语句p-prior-next=S;s-prior=p-pri

13、or;s-next=p;p-prior=s;19取出广义表A（x，（a，b，c，d）中原子c的函数是head(tail(tail(head(tail(head(A)。20在一个具有n个结点的有序单链表中插人一个新结点并使之仍然有序的时间复杂度为O(n)。21写出带头结点的双向循环链表L为空表的条件(L=L-Next) & (L=L-Prior)。22线性表、栈和队列都是线性_结构。23向栈中插人元素的操作是先移动栈顶针，再存人元素。三、判断题1线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（错）2在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。(错) 3顺序存储

14、的线性表不可以随机存取。（错） 4单链表不是一种随机存储结构。（对）5顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关。(错) 6顺序存储结构是动态存储结构，链式存储结构是静态存储结构。（错）7线性表的长度是线性表所占用的存储空间的大小。（错）8双循环链表中，任意一结点的后继指针均指向其逻辑后继。（错）9线性表的惟一存储形式是链表。（错）四、综合题1编写一个将带头结点单链表逆置的算法。void reverse_list( linklist * head )/*逆置带头结点的单链表*/linklist *s, *p;p=head-next;/*p指向线性表的第一个元素*/he

15、ad-next=NULL; /*初始空表*/while ( p != NULL ) s=p;p=p-next;s-next=head-next;head-next=s; /*将s结点插入逆表*/ /*reverse_list*/2ha和hb分别是两个按升序排列的、带头结点的单链表的头指针，设计一个算法，把这两个单链表合并成一个按升序排列的单链表，并用hC指向它的头结点。linklist *combine_list( linklist *ha, linklist *hb )/*ha, hb分别是两个按升序排列的,带有头结点的单链表的头指针，设计一个算法，把这两个单链表合并成一个按升序排列的单链表

16、,并用hc指向它的头结点*/linklist *hc, *pa, *pb, *pc, *p, *q, *r;hc=(linklist *)malloc(sizeof(linklist); /*建立hc头结点*/p=hc;pa=ha-next;free(ha); /*释放ha头结点*/pb=hb-next;free(hb);/*释放hb头结点*/while (pa!=NULL & pb!=NULL )q=(linklist *)malloc (sizeof (linklist); /*产生新结点*/if (pb-datadata)q-data=pb-data;pb=pb-next;elseq-d

17、ata=pa-data;pa=pa-next;if (pa-data=pb-data) /*将相同的元素删除*/r=pb;pb=pb-next;free(r);p-next=q; /*将结点链入c链表*/p=q;while(pa!=NULL)/*a链表非空*/q=(linklist *)malloc (sizeof (linklist);q-data=pa-data;pa=pa-next;p-next=q;p=q;while(pb!=NULL) /*b链表非空*/q=(linklist *)malloc (sizeof (linklist);q-data=pb-data;pb=pb-next;

18、p-next=q;p=q;p-next=NULL;return(hc); /*返回*/3有一个带头结点的单链表，头指针为head，编写一个算法countlist（）计算所有数据域为X的结点的个数（不包括头结点）。int count_list(linklist *head )/*在带头结点的单链表中计算所有数据域为x的结点的个数*/linklist *p;int n;p=head-next; /*p指向链表的第一个结点*/n=0;while (p!=NULL)if (p-data=x)n+;p=p-next;return(n);/*返回结点个数*/ /*count_list*/4在一个带头结点的

19、单链表中，头指针为head，它的数据域的类型为整型，而且按由小到大的顺序排列，编写一个算法insertxlist（），在该链表中插人值为x的元素，并使该链表仍然有序linklist *insertx_list(linklist *head, int x)/*在带头结点的单链表中插入值为x的元素，使该链表仍然有序*/linklist *s, *p, *q;s=(linklist *)malloc(sizeof(linklist); /*建立数据域为x的结点*/s-data=x;s-next=NULL;if (head-next=NULL | xnext-data ) /*若单链表为空或x小于链表

20、第一个结点的数据域*/s-next=head-next;head-next=s;elseq=head-next;p=q-next;while( p != NULL & xp-data )q=p;p=p-next;s-next=p;q-next=s; /*if*/ /*insertx_list*/。5在一个带头结点的单链表中，head为其头指针，p指向链表中的某一个结点，编写算法swapinlist（），实现p所指向的结点和p的后继结点相互交换。linklist *swapin_list(linklist *head, linklist *p)/*在带头结点的单链表中，实现p所指向的结点和p的后

21、继结点相互交换*/linklist *q, *r, *s;q=p-next; /*q为p的后继*/if (q !=NULL) /*若p有后继结点*/if (p=head) /*若p指向头结点*/head=head-next;s=head-next;head-next=p;p-next=s;else /*p不指向头结点*/r=head; /*定位p所指向结点的前驱*/while (r-next != p)r=r-next;r-next=q; /*交换p和q所指向的结点*/p-next=q-next;q-next=p;return(head);else /*p不存在后继*/return(NULL)

22、;/*swapin_list*/6有一个带头结点的单链表，所有元素值以非递减有序排列，head为其头指针，编写算法deldylist（）将linklist *deldy_list(linklist *head)/*在带头结点的非递减有序单链表，将该链表中多余的元素值相同的结点删除*/linklist *q;if (head-next!= NULL)/*判断链表是否为空*/p=head-next;while (p-next != NULL )if ( p-data != p-next-data )p=p-next;else q=p-next;/*q指向p的后继*/p-next=q-next; /

23、*删除q所指向的结点*/free(q); /*释放结点空间*/ /*while*/ /*if*/return(head); /*deldy_list*/该链表中多余元素值相同的结点删除。7在带头结点的单链表中，设计算法dellistmaxmin，删除所有数据域大于min，而小于max的元素。linklist *dellist_maxmin(linklist *head, int min, int max )linklist *p, *q;q=head;p=head-next;while(p!=NULL) /*结点不空*/if (p-datadata=max) /*不满足删除条件*/q=p;p=

24、p-next;else/*满足删除条件*/q-next=p-next;free(p);q=q-next; /*dellist_maxmin*/8设计一个将双链表逆置的算法invertdblinklist（），其中头指针为head，结点数据域为data，两个指针域分别为prior和next。将双链表逆置的算法invert_dblinklist的算法如下所示：void invert_dblinklist( linklist *head )/*将head指向的双链表逆置*/dblinklist *p, *q;p=head;doq=p-next;p-next=p-prior;p-prior=q;p=q

25、;while( p!=head ) /*invert_dblinklist*/习题三一、选择题 l一个栈的序列是：a，b，c，d，e，则栈的不可能输出的序列是（C）。Aa，b，c，d，e Bd，e，c，b，a Cd，c，e，a，b De，d，c，b，a 2若一个栈的输人序列是1，2，3，n，输出序列的第一个元素是n，则第k个输出元素是（ C）。 Ak Bn-k-1 Cn-k+1 D不确定3判定一个栈S（最多有n个元素）为空的条件是（ B ）。 AS-top！0 BS-top= =0 CS-top!=n DS-top= =n4判定一个栈S（最多有n个元素）为满的条件是（D ）。 AS-top!=

26、0 BS-top= =0 CS-top!=n DS-top= =n5向一个栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（ B ）。 Atop-next=S； BS-next=top；top=S； CS-nexttop-next；top-nextS；DS-nexttop；topS-next；6向一个带头结点、栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（ C ）。 Atop-next=S； BS-next=top；top=S； CS-next=top-next；top-next=S； DS-next=top；top=S-next；7判定一个队列Q（最多有n个元素）

27、为空的条件是（ C ）。 AQ-rear-Q-front= =n BQ-rear-Q-front+1= =n CQ-rear = = Q-front DQ-rear +1= = Q-front8判定一个队列Q（最多有n个元素）为满的条件是（A）。 AQ-rear-Q-front= =n BQ-rear-Q-front+1= =n CQ-rear = = Q-front DQ-rear +1= = Q-front9判定一个循环队列Q（最多有n个元素）为空的条件是（ A ）。 AQ-rear = = Q-front BQ-rear = = Q-frontl CQ-front= =(Q-rear +

28、1)n DQ-front= =(Q-rear -1)n10判定一个循环队列Q（最多有n个元素）为满的条件是（ C ）。 AQ-rear = = Q-front BQ-rear = = Q-frontl CQ-front= =(Q-rear +1)n DQ-front= =(Q-rear -1)n11在一个链队列中，假定front和rear分别为头指针和尾指针，则插入一个结点*S的操作是（ C ）。 Afrontfront-next BS-next=rear；rear=S Crear-next=S；rear=S DS-next=front；frontS12在一个链队列中，假定front和rear

29、分别为头指针和尾指针，删除一个结点的操作是（ A ）。 Afront=front-next Brear=rear-next Crear-next=front Dfront-nextrear 13栈与队列都是（ C ）。 A链式存储的线性结构 B链式存储的非线性结构 C限制存取点的线性结构 D限制存取点的非线性结构 14若进栈序列为l，2，3，4，则（ C ）不可能是一个出栈序列。 A3，2，4，1 Bl，2，3，4 C4，2，3，1 D4，3，2，l 15在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打

30、印。该缓冲区应该是一个（ B ）结构。 A堆栈 B队列 C数组 D线性表二、填空回1栈（stack）是限定在表尾一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为栈顶，而另一端称为栈底。不含元素的栈称为空栈。2在栈的运算中，栈的插人操作称为进栈或入栈的删除操作称为退栈或出栈。3根据栈的定义，每一次进栈的元素都在原栈顶元素之上，并成为新的栈顶元素；每一次出栈的元素总是当前的栈顶元素，因此最后进栈的元素总是最先出栈，所以栈也称为后进先出线性表，简称为LIFO表。4栈是一种操作受到限制的线性表，是一种特殊的线性表，因此栈也有顺序和链式_两种存储结构，分别称为、顺序栈_和_链栈。5当

31、栈满的时候，再进行人栈操作就会产生溢出，这种情况的溢出称为上溢_；当栈空的时候，如果再进行出栈操作，也会溢出，这种情况下的溢出称为下溢。6栈的链式存储结构简称为链栈，是一种_特殊的单链表。7人们日常计算用到的表达式都被称为中缀表达式，这是由于这种算术表达式的运算符被置于两个操作数中间。8计算机中通常使用后缀表达式，这是一种将运算符置于两个操作数后面的算术表达式。这种表达式是由波兰科学家谢维奇提出的，因此又称为波兰式。9队列（Queue）也是一种特殊的线性表_，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为队尾，允许删除的一端称为队头。

32、10队列的特点是先进先出，因此队列又被称为先进先出的线性表，或称为FIFO表。11队列的顺序存储结构又称为顺序队列，是用一组地址连续的存储单元依次存放队列中的元素。12由于队列中的元素经常变化，对于队列的删除和插人分别在队头和队尾进行，因此需要设置两个指针分别指向队头元素和队尾元素，这两个指针又称为队头指针和队尾指针。13循环顺序队列（Circular Sequence Queue）经常简称为循环队列，它是将存储顺序队列的存储区域看成是一个首尾相连的一个环，即将队首和队尾元素连接起来形成一个环形表。首尾相连的状态是通过数学上的、取模运算来实现的。14在算法或程序中，当一个函数直接调用自己或通过

33、一系列语句间接调用自己的时候，则称这个函数为递归函数，也称为自调用函数。函数直接调用自己，则称为直接递归调用；当一个函数通过另一个函数来调用自己则称为间接递归调用。15在循环队列中规定：当Q-rear= =Q-front的时候循环队列为空_， 当（Q-rear+1）MAXSIZEfront的时候循环队列为满。16用链表方式表示的队列称为链队列。17已知栈的输人序列为1，2，3，n，输出序列为a1，a2，an，符合a2= =n的输出序列共有n-1。18一个栈的输人序列是12345，则栈的输出序列为43512是不可能的（填是否可能）。19一个栈的输人序列是12345，则栈的输出序列为12345是可

34、能的（填是否可能）。20设sq1maxsize为一个顺序存储的栈，变量top指示栈顶元素的位置，则作入栈操作的条件是top!=maxsize。21设sq1maxsize为一个顺序存储的栈，变量top指示栈顶元素的位置，如果把栈顶元素弹出并送到X中，则需执行语句x=sqtop; top=top-1。22栈的特性是先进后出。23对栈进行退栈时的操作是先取出元素，后移动栈顶指针。24设s1max为一个顺序存储的栈，变量top指示栈顶位置，栈为满的条件是top=max。25设链栈的栈顶指针为top，则栈非空的条件是top!=nil。26已知循环队列用数组data1.n存储元素值，用f，r分别作为头尾指

35、针， 则当前元素个数为(n+r-f)mod n。27在一个循环队列中，队首指针指向队首元素的前一个位置。（前一个或后一个）28队列中允许进行删除的一端称为队首。29链队列实际上是一个同时带有头指针和尾指针的单链表（1n），尾指针指向该单链表的第n个元素。30设双向链表链列为lq，lq的头指针为lq.Front，尾指针为lq.Rear，则队列为空的条件是lq-front=lq-rear。31从循环队列中删除一个元素，其操作是先取出一个元素，后移动栈顶指针。32队列中允许进行插入的一端称为队尾。三、判断题1栈和队列都是限制存取点的线性结构。对 ）2不同的人栈和出栈组合可能得到相同输出序列。错误：不同的入栈和出栈组合得到不同输出序列。