数据结构第2次作业

上传者：刘先勇
|
上传时间：2015-05-12
|
密次下载

数据结构第2次作业

主观题(共22道小题)

24. 向一个长度为n的顺序表中的第i个元素之前插入一个元素时，需要向后移动个元素。

25. 在一个长度为n的顺序表中删除第i个元素时，需要向前移动元素。

26. 。 27. 在单链中要删除某一指定结点，必须找到该结点的 28. 访问单链表中的结点，必须沿着指针域依次进行。

29. 在双链表中每个结点有两个指针域，一个指向直接前驱结点，一个指向直接后继结点。

30. 在O(1)。

31. 访问一个线性表中具有给定值的时间复杂度的数量级是。

32. 由n个数据元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为 O(n) ，若每次都调用插入算法把一个元素插入到表尾，则整个算法的时间复杂度为 O(n2。

33. 在链表中，可以用表尾指针代替表头指针。

34. 在链表中，可以用表尾指针代替表头指针。

35. 根据n个数据元素建立对应的顺序表和单链表存储结构，其算法的时间复杂度最好的情况是 O(n) ，最坏的情况是 O(n2。

36. 求线性表的顺序存储和链式存储的长度的算法时间复杂度分别是 37. 在一个带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？相同。

38. 在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？不相同。

39. 阐述顺序表和链表存储方式的特点。

答：顺序表存储方式为数据分配连续的存储单元，数据元素按逻辑顺序依次存储到相应存储单元中，使得逻辑相邻的数据元素物理也相邻，因此可以实现随即访问线性表的数据元素，即数据访问的时间复杂度为O(1)。

链表存储方式分配的存储单元可以不连续，通过每个结点的指针域来表示数据元素之间的逻辑关系，只能顺序访问线性表中的数据元素。

40. 若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什么？

答：若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用链式存储结构。因此链式存储结构在插入和删除数据元素时不需要移动数据元素，只需要修改结点的指针域就可以改变数据元素之间的逻辑关系。

41. 在单链表、双向循环链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删除？若可以，时间复杂度各为多少。

答：要实现删除p结点的操作，必须找到其前驱结点，修改其指针域的值使其指向p的后继结点，以实现删除结点p。单链表不行，因此不知道头指针就无法找到结点p的前驱结点。双向循环链表和单循环链表可以可以实现删除p结点。单循环链表删除p结点的时间复杂度为O(n)，双循环链表删除P结点的时间复杂度为O(1)。

42. 对链表设置头结点的作用是什么？

答：对带头结点的链表，在表的任何结点之前插入结点或删除任何位置的结点，所要做的都是修改前一个结点的指针域，因为在带头结点的链表中任何元素结点都有前驱结点。如果没有头结点，在首元结点前插入结点或删除首元结点都要修改头指针，其算法要比不带头结点的算法复杂些。

其次，带头结点的链表结构，初始化后的头指针就固定了，除撤销算法外，所有算法都不会修改头指针，可以减少出错的可能性。

43. 已知一个线性表用含头结点的单链表做存储结构，写一个算法求单链表的长度。

答：

int listlenght(linklist L)

{ int length=0;

P=L->next;

while(p)

{ length++;

p=p->next;

}

return(length);

}

44. 已知一个顺序表L，其中的元素按值递增有序排列，设计一个算法插入一个值为x的元素后保持该顺序表仍然递增有序，且空间复杂度为0（1）。

答： void insertsq(sqlist L,elemtype x)

{ n=L.length-1;

if(LT(L.elem[n],x)

{ n++;

L.elem[n]=x;

}

else{

while(n>=0&&LT(x,L.elem[n])

{ L.elem[n+1]=L.elem[n];

n--;

}

L.elem[n+1]=L.elem[n];

}

return;

45. 写一个算法，从顺序表中删除值为x的所有元素。答：

void delallsq(Sqlist &L)

{ int i=0,j=0;

while(j<L.length)

{ if(L.elem[j]!=x)

L.elem[i++]=L.elem[j]; j++;

}

L.longth=i;

}

下载文档

网友关注

2015年11月16日幼儿园社会领域教育的特点与实施Word

2017年山西会计从业资格证《电算化》多项题练习(3)答案

纳林湖景区推介2016Word

新人教数学二年级下册课本上所有的应用题及精选

网友关注视频

北师大版数学四年级下册第三单元第二节小数点搬家

沪教版牛津小学英语（深圳用）四年级下册 Unit 3

人教版历史八年级下册第一课《中华人民共和国成立》

外研版英语三起6年级下册（14版）Module3 Unit1

冀教版小学英语四年级下册Lesson2授课视频

小学英语单词

沪教版牛津小学英语（深圳用）五年级下册 Unit 10

3月2日小学二年级数学下册（数一数）

冀教版小学数学二年级下册1

19 爱护鸟类_第一课时(二等奖)(桂美版二年级下册)_T3763925

外研版八年级英语下学期 Module3

第19课我喜欢的鸟_第一课时(二等奖)(人美杨永善版二年级下册)_T644386

冀教版英语四年级下册第二课

二年级下册数学第三课搭一搭⚖⚖

苏科版八年级数学下册7.2《统计图的选用》

【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案，辽宁省

沪教版八年级下册数学练习册21.3（2）分式方程P15

【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案，天津市

冀教版小学数学二年级下册第二单元《有余数除法的简单应用》

【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案，安徽省

苏科版数学八年级下册第八章第二节可能性的大小

【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案，安徽省

冀教版英语三年级下册第二课

外研版英语三起5年级下册（14版）Module3 Unit2

六年级英语下册上海牛津版教材讲解 U1单词

沪教版牛津小学英语（深圳用）五年级下册 Unit 12

冀教版小学英语五年级下册lesson2教学视频(2)

苏科版数学八年级下册9.2《中心对称和中心对称图形》

沪教版牛津小学英语（深圳用）四年级下册 Unit 8

冀教版小学数学二年级下册第二单元《有余数除法的竖式计算》

精品推荐

营造良好的企业文化

分类导航

生物学

刘先勇

此文档贡献者

2015-05-12
贡献时间
密
下载次数

教育资源为主的文档平台

文档分类