第二章 线性表(4)

1．（ ）线性表的顺序存储结构比链式存储结构更好。F 2．( )线性表就是顺序存储的表。× 3．（ ）线性表中的所有元素都有一个前驱元素和后继元素。F 4．（ ）非空的双向循环链表中任何结点的前驱指针均不为空。T 5．（ ）不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。T

6．( )对链表进行插入和删除操作时不必移动链表中结点。T 7．( )线性表只能用顺序存储结构实现。× 8．( )如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。×

9．( )进栈操作时，必须判断栈是否已满。× 10．( )进栈、出栈操作的时间复杂度是O(n)。×

11．( )采用链式结构存储线性表时，其地址可以是不连续的。√ 12．( )线性表中的每个元素都有一个前驱元素和后继元素。× 13．( )采用顺序结构存储线性表时，其地址可以是不连续的。× 14．（ ）如果某数据结构的每一个元素都最多只有一个直接前驱和一个直接后继，则该数据结构必为线性表。√ 15．（ ）线性表的唯一存储形式就是链表。× 16．（ ）线性表不能采用链式存储。× 17．（ ）在单链表中插入结点主要通过移动元素实现。× 18．( )所谓静态链表就是一直不发生变化的链表。× 19．( )集合与线性表的区别在于是否按关键字排序。× 20．（ ）用头部插入结点的方法建立单链表时，插入元素的顺序和链表中的元素顺序相同。× 21．（ ）线性表中的每个元素都有一个前驱元素和后继元素。 × 22．（ ）线性表中每个元素都有一个直接前驱和一个直接后继。× 23．（ ）线性表采用顺序存储表示时，必须占用一片连续的存储单元。√ 24．( )数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。×

25．( )数据的逻辑结构是指数据的各数据项之间的逻辑关系。× 26．( )算法的优劣与算法描述语言无关，但与所用计算机有关。× 27．( )健壮的算法不会因非法的输入数据而出现莫名其妙的状态。√ 28．（ ）算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。×

29．( )数据的物理结构是指数据在计算机内的实际存储形式。√ 30．( )数据结构的抽象操作的定义与具体实现有关。× 31．( )数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。√ 32．（ ）算法独立于具体的程序设计语言，与具体的计算机无关。√ 33．（ ）Huffman树、平衡二叉树都是数据的逻辑结构。√ 34．（ ）抽象数据类型与计算机内部表示和实现无关。√ 35．（ ）在一个设有头指针和尾指针的单链表中,执行删除该单链表中最后一个元素的操作与链表的长度无关。×

36．( )顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。×

11

37．（ ）顺序存储方式只能用于存储线性结构。× 38．( ) 线性表只能用顺序方式存放。X

39．( ) 在带表头结点的双循环链表中，每个结点的前趋和后继指针均不为空。√

40．（ ）顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。×

41．( )顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 42．（ ）在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。×

43. （ ）在单链表中，要取得某元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。× 四、简答题

1．线性结构与非线性结构的差别

前驱与后继之间通常为一对多或多对多的关系。 2．比较顺序表与单链表的优缺点。 顺序表优点：随机查找，存储密度大

顺序表缺点：插入、删除不便，静态分配，表长固定 单链表优点：插入、删除方便，动态分配，表长灵活

单链表缺点：查找不便，存储密度小 3．简要说明算法与程序的区别。

算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实现，与具体的计算机语言有关。

4．说明以下三个概念的关系：头指针，头结点，首元素结点。 头指针指向头结点，头结点的后继域指向首元素结点。

5．设有编码为A，B，C，D的4列火车，依次进入一个栈式结构的站台，试写出这4列火车开出站台的所有可能的顺序。

根据栈的数学性质，n个元素的出栈序列数目恰好符合卡塔南数列。 Cn=C2nn/(n+1)=1/n+1*(2n)!/n!(2n-n)! 这里:

1/n+1*(2n)!/n!(2n-n)!=1/5*8!/(4!*4!)=14 ABCD ABDC ACBD ACDB ADCB BACD BADC BCAD BCDA BDCA CBAD CBDA CDBA DCBA 分析解答：

6．写出在双向链表中，在指针p所指结点前插入一个结点*S的语句序列。 答： 答：（1）S->prior=P->prior; （2）P->prior->next=S; （3）S->next=P; （4）P->prior=S;

7．试叙述一维数组与有序表的异同。

一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中的元素按值排列（非递增或非递减），而一维数组中的元素没有按元素值排列顺序的要求。 8．试比较顺序存储和链式存储的优缺点。

顺序存储查找效率高，插入和删除效率低；链式存储插入和删除效率高，查找效

12

率低。

9．写出线性表(26,45,12,20,30)采用快速排序算法排序后，第一趟排序过程及结果。

20 12 26 45 30。

10．试说明单链表采用头结点的优点。 解决单链表的“第一个结点问题”，使头指针变量不为空。 11. 画出带头结点的单链表、单循环链表和双向循环链表的示意图，并归纳三者的不同之处。

H a1 ??

an H L A B 单链表：只有从头结点出发，才能访问到所有结点。

单循环链表：从任意一结点出发，均可访问到其他结点。

双向循环链表：既可以方便的找到前趋结点，又可方便的找到后继结点。

12．有五个数依次进栈：1，2，3，4，5。在各种出栈的序列中，以3，4先出的序列有哪几个。（３在４之前出栈）。 【解答】34215 ，34251， 34521 13．铁路进行列车调度时，常把站台设计成栈式结构，若进站的六辆列车顺序为：1，2，3，4，5，6， 那么是否能够得到435612， 325641， 154623和135426的出站序列，如果不能，说明为什么不能； 如果能， 说明如何得到(即写出\进栈\或\出栈\的序列)。

【解答】输入序列为123456，不能得出435612和154623。不能得到435612的理由是，输出序列最后两元素是12，因为前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能让栈底元素1在栈顶元素2之前出栈。不能得到154623的理由类似，当栈中元素只剩23，且3在栈顶，2不可能先于3出栈。 得到325641的过程如下：1 2 3顺序入栈，32出栈，得到部分输出序列32；然后45入栈，5出栈，部分输出序列变为325；接着6入栈并退栈，部分输出序列变为3256；最后41退栈，得最终结果325641。 得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出栈，部分输出序列变为13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。

14．若用一个 …… 此处隐藏：3874字，全部文档内容请下载后查看。喜欢就下载吧 ……