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

}

下载文档

网友关注

给妈妈的一封信

小学总务考核标准11

广东省深圳市西丽幼儿园分园装修工程可行性研究报告-广州中撰咨询

2010-2011学年北京市海淀区高三第二学期期末练习(语文)答案

洋县理光复印土管局大门北：幼儿园校安全工作日志

关于幼儿园转让协议

黄道婆

苏州园林

陕西艺术幼儿园音乐活动教研心得(3.14)

2011-2012学年吉林省长春外国语学校初二上学期第二次月考语文试卷答案

留守儿童之家读书活动安排意见

母亲节所思

《回忆鲁迅先生》

2011-2012学年四川仁寿联谊学校七年级下学期半期检测政治试卷(带解析)答案

登鲁的故事

小学古诗词归类整理

兰德公司“T项目”研究及其对我国学前教育的启示

中班美术教学计划

对“留守学生”教育问题思考

网友关注视频

冀教版英语五年级下册第二课课程解读

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

第8课对称剪纸_第一课时(二等奖)(沪书画版二年级上册)_T3784187

化学九年级下册全册同步人教版第22集酸和碱的中和反应（一）

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

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

小学英语单词

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

苏科版数学七年级下册7.2《探索平行线的性质》

冀教版小学数学二年级下册第二单元《余数和除数的关系》

3.2 数学二年级下册第二单元表内除法（一）整理和复习李菲菲

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

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

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

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

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

第五单元民族艺术的瑰宝_15. 多姿多彩的民族服饰_第二课时(市一等奖)(岭南版六年级上册)_T129830

二次函数求实际问题中的最值_第一课时(特等奖)(冀教版九年级下册)_T144339

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

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

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

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

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

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

七年级下册外研版英语M8U2reading

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

【部编】人教版语文七年级下册《过松源晨炊漆公店（其五）》优质课教学视频+PPT课件+教案，江苏省

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

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

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

精品推荐

营造良好的企业文化

分类导航

生物学

刘先勇

此文档贡献者

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

教育资源为主的文档平台

文档分类