济南铁道职业技术学院 专升本辅导教材 数据结构

(2)顺序存储方式的优点是存储密度大, 且插入、删除运用算效率高。 (3)链表的每个结点中都恰好包含一个指针。

(4)散列法存储的基本思想是由关键码的值决定数据的存储地址。 (5)散列表的结点中只包含数据元素自身的信息, 不包含任何指针。

(6)负载因子 (装填因子) 是散列法的一个重要参数, 它反映散列表的装满程度。 (7)栈和队列的存储方式既可是顺序方式, 也可是链接方式。

(8)用二叉链表法 (llink -- rlink法) 存储包含n 个结点的二叉树, 结点的2n个指针区域中有n+1 个为空指针。

(9)用相邻矩阵法存储一个图时, 在不考虑压缩存储的情况下, ?所占用的存储空间大小只与图中结点个数有关, 而与图的边数无关。

(10)邻接表法只能用于有向图的存储,而相邻矩阵法对于有向图和无向图的存储都适用。

7．表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、_______________和散列存储方式。

8．下列程序段的时间复杂度为________________。 product = 1; for (i = n;i>0; i--)

for (j = i+1; j

9．文件上的两类主要操作为________________和________________。 10．文件的基本运算包括______________和修改两类。 11．下列程序段的时间复杂性量级是_____________。

for (i=1;i

t=t+1;

12.若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为________。

第二章 课后辅导

例2．1 已知长度为n的非空线性表A采用顺序存储结构，表中数据元素按值的大小非递减排列，请写出删除该线性表中值相同的多余元素的算法。7654321 7654321

算法思想比较简单，只需从表的第一个数据元素开始到最后那个数据元素，反复做以下动作：比较相邻的两个数据元素是否相同，若相同，则删除其中一个；若不相同，则比较下一对相邻元素。算法如下： voidDELETEITEM1(ElemTypeA[]，int n)) {

int j，i=0； while(i

if (A[i]!=A[i+1]) ／x若相邻两个元素不相同。／ i++；

else{ ／*若相邻两个元素相同，则删除其中一个*／ for ( j=i++；i

n--； ／x表长减1 x／

第 6 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

} } }

2

上述算法的时间复杂度为O(n)。对算法进行改进，得到一个时间复杂度为O(n)的 算法不是很困难。这里，设置两个整型变量i与k，它们的初值分别为1与0。若在比较 过程中发现A[i]与A[k]不同，则先将k后移一个位置，然后将A[i]送到A[k]的位置上； 若A[i]与A[k]相同，只是将i后移一个位置。当表中所有元素都处理完毕时，k+1正好 是删除多余元素以后线性表的长度。 改进后的算法如下：

voidDELETEITEM2(ElemTypeA[]，int &n) {

int k，i； if(n>1) { k=0；

for(i=1；i

if(A[i]!=A[k]) ／x若A[i]与A[k]不相同时。／ A[++k]=A[i]；

n=k+1； ／。得到删除以后的表长。／ } }

14．将两个按值有序的非空线性链表合并为一个按值有序的线性链表 设lista与listb分别为两个有序链表第一个链结点的指针。将这两个有序链表合并 为一个有序链表，其第一个链结点的指针为listc。

这里，只需设置三个指针p，q和r，其中，p和q分别指向链表lista和链表listb当前待比较插入的链结点，而r指向链表listc中当前最后那个链结点。然后不断地比较p与q

所指的链结点的数据域值，若p->data < q->data，则将p指的链结点链接到r所指的链结点之后，否则将q指的链结点链接到r所指的链结点之后。当其中一个链表为空时，只 需将另一个链表中剩余的链结点都依次链接到r所指的链结点之后即可。初始时，让

listc指向lista和listb所指向的链结点中值小的那一个链结点。 LinkListMERGELIST(LinkListlista,LinkListlistb) {

LinkList listc，p，q，r； if(lista->dada<=listb->data){ listc=lista； r=lista；

p=lista->link； } else{

listc=listb； r=listb；

q=listb->link；

} ／x listc指向lista和listb所指结点中值小者x／ while(p!=NULL&&q!=NULL){

if(p->data<=q->data){／x若当前p所指结点的值不大于q所指结点的值x／

第 7 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

r->link=p； ／y将p所指结点链接到r所指结点之后x／ r=p；

p=p->link； } else{

r->link=q； ／。将q所指结点链接到r所指结点之后‘／ r=q；

q=q—>link； } }

r->link=p?p=q； ／x插人剩余链结点x／

return(listc)； ／x返回合并后的链表第一个链结点地址x／ }

若两个链表的长度分别为n与m，则上述算法的时间复杂度为O(n十m)。在合并两 个链表为一个链表时不需要另外建立新链表的链结点空间，只需将给定的两个链表中的 链结点之间的链接关系解除，重新按照元素值的非递减关系将所有链结点链接成为一个 链表即可。

例2．5 约瑟夫(Josephu)问题 已知n个人(不妨以编号1，2，3，?，n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列，他的下一个人又从1开始报数，数到m的那个人又出列，依此规则重复下去，直到圆桌周围的人全部出歹，J。

例如，当n：8，m’4，k二3时，出列的顺序依次为6，2，7，4，3，5，1，8。

解决约瑟夫问题可以利用多种数据结构，但比较简单和自然的方法是利用一个具有 n个链结点、且不带头结点的循环链表。将圆桌周围的每一个人对应着该链表中的一个链结点，某个人出列相当于从链表中删除一个链结点。下面的算法就是在该循环链表中不断地报数，不断地删除一个链结点，直到循环链表中还剩一个链结点时游戏结束。整个算法可以分为三个部分： (1)建立一个具有n个链结点且无头结点的循环链表； (2)确定第一个报数点的位置；

(3)不断地从链表中删除一个链结点，直至链表中还有一个链结点。

习 题 2．1

判断题(在你认为正确的题后的括号中打√，否则打X)。 (1)空线性表的特征是表中数据元素都未赋值。 ( )

(2)线性表的顺序存储结构必须占用一片地址连续的存储单元。 ( )

(3)用一维数组存储线性表时，表中第i个元素存放在下标为i的数组元素中。 ( ) (4)采用顺序存储结构的线性表又称为顺序表。 ( )

(5)—个数据元素的地址是指该元素占用的若干存储单元的第一个单元的地址。 ( ) (6)线性表占用的存储单元的数量与表中数据元素的类型有关。 ( ) (7)线性表的顺序存储结构要比链式存储结构节省存储空间。 ( ) (8)线性表的链式存储结构要比顺序存储结构节省存储空间。 ( )

(9)若线性表采用顺序存储结构,线性表的长度等于表中元素的个数与每个元素所占内存单元之乘积。 ( )

第 8 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

(10)若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144则第1个数据元素的存储地址是101。 ( 100 )

(11)在长度为n的顺序表的第i个位置插入一个数据元素，i的合法值为1≤i≤N。 ( ) (12)删除长度为n的顺序表的第i个数据元素，i的合法值为1≤i≤n。 ( ) (13)在长度为n的顺序表中插入一个数据元素的时间复杂度为O(n)。 ( ) (14)线性表的链式存储结构不必占用地址连续的存储空间。 ( ) (15)链表中的每个链结点占用的存储空间不必连续。 ( )

(16)一个链结点的地址是指该链结点占用的若干存储单元的第一个单元的地址。 ( ) (17)非空线性链表的最后那个链结点的指针域不能为空，应该存放NULL。 ( ) (18)所谓空链表是指没有任何链结点的链表。 ( ) (19)任何一个链表都可以根据需要设置一个头结点。 ( ) (20)每个链表的前面都必须设置一个头结点。 ( )

(21)线性链表(单向链表)中的每个链结点只有后继结点，没有前驱结点。 ( ) (22)一个空的链表不占用任何存储空间。 ( )

(23)若指针变量list指向一个空链表，则list中什么也没有。 ( ) (24)无论出现在算法的什么地方，符号p->data表示的意思都一样。 ( ) (25)在算法中，符号p->link表示p所指的下一个链结点的地址。 ( )

(26)删除非空线性链表的第一个链结点只需执行语句list=list->link。 ( )

(27)循环链表的最后那个链结点的指针域中存放着链表最前面那个结点的地址。 ( ) (28)设置一个指针变量，它可以遍历整个循环链表。 ( )

(29)双向链表的头结点指针要比线性链表的头结点指针占用更多的存储空间。 ( ) (30)在链结点数目相同的前提下，双向链表占用的空间是线性链表的2倍。 ( ) 单项选择题。

(1)一个顺序表所占用的存储空间大小与——无关。

A．表的长度 B．元素的存放顺序 C．元素的类型 D。元素中各字段的类型

(2)设存储分配是从低地址到高地址进行的。若每个元素占用4个存储单元，则某元素的地 址是指它所占用的单元的

A．第1个单元的地址 B．第2个单元的地址 C．第3个单元的地址 n第4个单元的地址

(3)若线性表采用顺序存储结构，每个元素占用4个存储单元，第1个元素的存储地址为100， 则第12个元素的存储地址是． 。 A．112 B．144 C．148 0．412

(4)若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值 应该是——。

A．i>O B．i≤n C．1≤i≤n D．1≤i≤n+1

(5)若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，i的合法值应该是 A．i>O B．i≤n C．1≤i≤n D。1≤i≤n十1

(6)若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表 中——个数据元素。

A．n-i B．n+i C．n-i+l D．n-i-1

(7)若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，需要移动 表中——个元素。 。

A．i B．n+i C．n-i+l D．n-i-1

(8)若频繁地对线性表进行插入和删除操作，该线性表应该采用——存储结构。

第 9 页 共 63 页

济南铁道职业技术学院 专升本辅导教材 数据结构

A．散列 B．顺序 C．链式 D．索引 (9)链表中所占用的存储单元地址一定是 。

A．无序的 B．连续的 C．不连续的 D．部分连续的 (10)链表中的每一个链结点所占用的存储单元——。

A．不必连续 B．一定连续 C．部分连续 D．连续与否无所谓 (11)与单链表相比，双向链表的优点之一是 。 A．插入、删除操作更简单 B．可以进行随机访问 C．可以省略头结点指针 D．顺序访问相邻结点更灵活

(12)若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域中存 放的是——。

A．1ist的地址 B．1ist的内容

C．1ist指的链结点的值 D．链表第一个链结点的地址

(13)若list是某带头结点的循环链表的头结点指针，当p(p与list同类型)指向链表的最后那 个链结点时，——。

A．该结点的指针域为空 B．p为空

C．p的内容与头结点的内容相同 D．该链结点指针域内容与list的内容相同

(14)若listl和list2分别为一个单链表与一个双向链表的第一个结点的指针，则——。 A．1ist2比listl占用更多的存储单元 B．1istl与list2占用相同的存储单元

C．1istl和list2应该是相同类型的指针变量D．双向链表比单链表占用更多的存储单元 (15)在表达式中，符号p->link表示——。 A．p所指的链结点的指针域(位置) B．p所指的链结点的指针域的内容

C．p所指的链结点的下一个链结点的地址

D．p所指的链结点的下一个链结点的地址(出现在表达式中)

(16)在一个具有n个链结点的线性链表中查找某一个链结点，若查找成功，需要平均比较 ——个链结点。

A．n B．n／2 C．(n+1)／2 D．(n-1)／Q

(17)从一个具有n个链结点的有序线性链表(即链结点按照数据域值有序链接)中插入一个 新的链结点，并且仍然保持链表有序的时间复杂度为——。 A．O(1) B．O(n) C．O( n(2) ) D．O( log2(n) )

(18)给定具有n个元素的顺序表，建立一个有序线性链表的时间复杂度为——。 A．O(1) B．O(n) C．O( n(2) ) D．O( log2(n) )

(19)在非空线性链表中由p所指的链结点后面插入一个由q所指的链结点的过程是依次执 行——。

A．q->link=p；p->link=q； B．q->link=p->link；p->link=q； C．q->link=p->link；p=q； D．p->link=q；q->link=p；

(20)若删除非空线性链表中由p所指的链结点的直接后继链结点的过程是依次执行 ________.

A．r=p->link；p->link=r；free(r)；

B．r=p->link；p->link=r->link；free(r)； C．r=p->link；p->link=r->link；free(p)； D．p->link=p->link->link；free(p)；

(21)在非空双向循环链表中由q所指的链结点后面插入一个由p所指的链结点的动作依次 为：p->llink=Q；p->rlink=q->rlink；q->rlink=p；——。(空白处为一条赋值

第 10 页 共 63 页