内容发布更新时间 : 2024/7/5 4:49:26星期一 下面是文章的全部内容请认真阅读。

弘成无锡数字化学习中心

批次

层次：专升本

专业：计算机科学与技术

姓名：刘鹏亮

学号：15940673

1 / 12

第一次作业

三、主观题(共3道小题)

14. 数据的物理结构包括 的表示和 的表示。

参考答案：线性结构 , 非线性结构

15. 数据逻辑结构包括 、 、 和 四种，树结构和图结构统称为 。

参考答案： 集合 、 线性结构 、 树 、 图 、非线性结构

16. 数据结构研究的是 和 以及它们之间的相互关系，并对于这种结构定义相应的 ，设计出相应的 。

参考答案： 逻辑结构 ， 物理结构 ， 运算 ，算法

第二次作业

三、主观题(共22道小题)

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

参考答案：n-i+1

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

参考答案： n-i

26. 在单链表中设置头结点的作用是 。

参考答案：简单插入、删除算法

27. 在单链中要删除某一指定结点，必须找到该结点的 结点。

参考答案：直接前驱

28. 访问单链表中的结点，必须沿着 依次进行。

参考答案：指针域

29. 在双链表中每个结点有两个指针域，一个指向 ，一个指向 。

参考答案：直接前驱结点 ，直接后继结点

30. 在 链表中，删除最后一个结点的算法时间复杂度为O(1)。

参考答案： 双向循环

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

参考答案：O(n)

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

插入算法把一个元素插入到表尾，则整个算法的时间复杂度为 。 参考答案：O(n) ， O(n2)

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

参考答案： 双向

2 / 12

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

参考答案： 双向

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

是 。

参考答案：O(n) ， O(n)

2

36. 求线性表的顺序存储和链式存储的长度的算法时间复杂度分别是 和 。

参考答案：

O(1) , O(n)

37. 在一个带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？ 参考答案：相同

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

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

参考答案：

此可以实现随即访问线性表的数据元素，即数据访问的时间复杂度为O(1)。

顺序表存储方式为数据分配连续的存储单元，数据元素按逻辑顺序依次存储到相应存储单元中，使得逻辑相

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

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

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

41. 在单链表、双向循环链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相

间复杂度各为多少。

参考答案：要实现删除p结点的操作，必须找到其前驱结点，修改其指针域的值使其指向p的后继结点，以实现O(n)，双循环链表删除P结点的时间复杂度为O(1)。

此不知道头指针就无法找到结点p的前驱结点。双向循环链表和单循环链表可以可以实现删除p结点。单循环链

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

参考答案：

对带头结点的链表，在表的任何结点之前插入结点或删除任何位置的结点，所要做的都是修改前一个结点的杂些。

表中任何元素结点都有前驱结点。如果没有头结点，在首元结点前插入结点或删除首元结点都要修改头指针，其

其次，带头结点的链表结构，初始化后的头指针就固定了，除撤销算法外，所有算法都不会修改头指针

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

参考答案：

int listlenght(linklist L) { int length=0; P=L->next; while(p) { length++;

3 / 12

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&<(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.elem[i++]=L.elem[j]; j++; } L.longth=i; }

第三次作业

三、主观题(共50道小题)

60. 循环队列的引入，目的是为了克服 。

参考答案： 顺序队列的假溢出

61. 区分循环队列的空与满有3种方法，它们是 、 、 。

参考答案：少用一个元素 、 设空满标志 、 用计数器记录队列中元素个数

4 / 12