数据结构第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山东公务员考试申论（B类）真题解读：中国企业要走出去

2018山东公务员考试申论真题（B类）

2018年421省考申论亮点：农村电商繁荣背后有隐忧

山东公务员面试热点模拟题:提升国家文化软实力

山东公务员考试行测题库：行测言语理解模拟题04

2018年421省考申论亮点：共享热度不减洗衣也变时尚

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

2018年421省考申论亮点：唱响“产业兴旺歌”助推乡村振兴

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

山东公务员面试热点模拟题：如何避免大学生传销悲剧

山东公务员面试热点模拟题：如何采访拦高铁女子的领导

山东公务员面试热点模拟题：电信诈骗发案高发

山东公务员面试热点模拟题：农村成为高价彩礼“重灾区”

历年山东公务员面试考情分析

2018年421省考行测亮点：取材广泛，贴合社会热点

山东公务员面试热点模拟题：反腐倡廉热度从未减

联考10年申论考情大观：看得见的改变，看不见的初心

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

2018年421省考申论亮点：材料选取围绕“互联网+”时效性强

山东公务员面试热点模拟题：禁止燃放烟花爆竹体现社会进步

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

2018山东公务员考试申论亮点：企业走出去直挂云帆济沧海

山东公务员面试热点模拟题：创客空间

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

2018山东公务员考试申论真题（C类）答案要点

2018年421省考申论亮点：乡村建设“去虚向实”旧貌换新颜

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

2018山东公务员考试申论真题（C类）

2018山东公务员考试申论（C类）真题解读：不忘初心好扬帆

2018年421省考申论亮点：“富口袋”更要“富脑袋”

网友关注视频

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

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

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

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

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

小学英语单词

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

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

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

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

人教版二年级下册数学

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

三年级英语单词记忆下册（沪教版）第一二单元复习

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

精品推荐

营造良好的企业文化

分类导航

生物学

刘先勇

此文档贡献者

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

教育资源为主的文档平台

文档分类