数据结构第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;

}

下载文档

网友关注

2018重庆公务员面试结构化面试模拟题答案4.27

2018重庆公务员面试结构化面试模拟题5.9

2018重庆公务员面试热点模拟题：“星巴克致癌” 食品安全警钟长鸣

2018重庆公务员面试结构化面试模拟题答案5.16

2018重庆公务员考试行测真题参考答案及解析

重庆公务员结构化面试模拟题4.25

重庆公务员行测判断推理模拟题

2018重庆公务员考试申论1真题答案要点

2018重庆公务员考试申论2真题解读：聚焦农村，难度不大

2018重庆公务员考试申论2真题

2018重庆公务员面试结构化面试模拟题5.10

2018重庆公务员面试热点模拟题：经典名曲被恶搞暴露对历史的淡忘

2018重庆公务员面试热点模拟题：如何看待农村地区的“家庭医生”

2018重庆公务员面试热点模拟题：高校图书馆对外开放谁将受益

重庆公务员行测言语理解模拟题03

重庆公务员申论模拟题：中国式求人

2018重庆公务员面试结构化面试模拟题5.4

2018重庆公务员面试结构化面试模拟题答案5.10

2018重庆公务员考试申论2真题答案要点

2018重庆公务员考试申论亮点：首次分类精准性与难度并存

2018重庆公务员面试结构化面试模拟题5.16

2018重庆公务员面试热点模拟题：如何开展敬老爱老活动

2018重庆公务员面试结构化面试模拟题4.27

重庆公务员面试热点模拟题：如此脆弱的医患关系

2018重庆公务员面试结构化面试模拟题答案5.15

重庆公务员行测言语理解模拟题02

2018重庆公务员面试结构化面试模拟题5.14

2018重庆公务员面试结构化面试模拟题5.8

重庆公务员行测判断推理模拟题答案

2018重庆公务员面试结构化面试模拟题答案5.17

网友关注视频

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

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

北师大版小学数学四年级下册第15课小数乘小数一

沪教版八年级下册数学练习册一次函数复习题B组（P11）

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

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

沪教版八年级下册数学练习册21.4（1）无理方程P18

飞翔英语—冀教版(三起)英语三年级下册Lesson 2 Cats and Dogs

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

沪教版八年级下次数学练习册21.4（2）无理方程P19

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

【获奖】科粤版初三九年级化学下册第七章7.3浓稀的表示

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

第五单元民族艺术的瑰宝_16. 形形色色的民族乐器_第一课时(岭南版六年级上册)_T1406126

精品·同步课程历史八年级上册第15集近代科学技术与思想文化

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

苏教版二年级下册数学《认识东、南、西、北》

8.对剪花样_第一课时(二等奖)(冀美版二年级上册)_T515402

人教版二年级下册数学

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

七年级英语下册上海牛津版 Unit5

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

化学九年级下册全册同步人教版第25集生活中常见的盐（二）

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

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

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

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

青岛版教材五年级下册第四单元（走进军营——方向与位置）用数对确定位置（一等奖）

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

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

精品推荐

营造良好的企业文化

分类导航

生物学

刘先勇

此文档贡献者

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

教育资源为主的文档平台

文档分类