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

}

下载文档

网友关注

2017届松江二模作文范文解析

2014-2015学年浙江省杭州市下城区八年级(上)期末数学试卷答案

盐城市滨海县2017届中考二模数学试题含答案

会展营销实务教学课件 Word 作者肖温雅第四章会展城市营销

南开17春学期《计算机科学导论》在线作业满分答案

网友关注视频

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

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

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

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

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

冀教版小学数学二年级下册第二单元《租船问题》

外研版英语七年级下册module3 unit1第二课时

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

冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣.mp4

30.3 由不共线三点的坐标确定二次函数_第一课时(市一等奖)(冀教版九年级下册)_T144342

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

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

北师大版数学四年级下册3.4包装

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

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

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

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

小学英语单词

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

北师大版八年级物理下册第六章常见的光学仪器（二）探究凸透镜成像的规律

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

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

每天日常投篮练习第一天森哥打卡上脚 Nike PG 2 如何调整运球跳投手感？

冀教版小学数学二年级下册第二单元《有余数除法的整理与复习》

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

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

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

冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣

化学九年级下册全册同步人教版第18集常见的酸和碱（二）

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

精品推荐

营造良好的企业文化

分类导航

生物学

刘先勇

此文档贡献者

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

教育资源为主的文档平台

文档分类