弘成无锡数字化学习中心批次层次：专升本专业：计算机科学与技术姓名：刘鹏亮学号： 15940673# / 12第一次作业二、 主观题(共3道小题)14. 数据的物理结构包括 的表示和 的表示参考答案：线性结构,非线性结构15. 数据逻辑结构包括 、 、 和 四种，树结构和图结构统称为 参考答案：集合、线性结构、树、图、非线性结构16. 数据结构研究的是—和 以及它们之间的相互关系，并对于这种结构定义相应的 ，设计出相应的 参考答案：逻辑结构，物理结构，运算，算法第二次作业三、 主观题(共22道小题)24. 向一个长度为n的顺序表中的第i个元素之前插入一个元素时，需要向后移动 个元素参考答案：n-i+125. 在一个长度为n的顺序表中删除第i个元素时，需要向前移动 元素参考答案： n-i26. 在单链表中设置头结点的作用是 参考答案：简单插入、删除算法 27. 在单链中要删除某一指定结点，必须找到该结点的 结点参考答案：直接前驱28. 访问单链表中的结点，必须沿着 依次进行参考答案：指针域29. 在双链表中每个结点有两个指针域，一个指向 ，一个指向 参考答案：直接前驱结点 ，直接后继结点30. 在 链表中，删除最后一个结点的算法时间复杂度为 0(1)。
参考答案： 双向循环31. 访问一个线性表中具有给定值的时间复杂度的数量级是 参考答案：oim32. 由n个数据元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度插入算法把一个元素插入到表尾，则整个算法的时间复杂度为 参考答案：0(n ，0( n2)33. 在 链表中，可以用表尾指针代替表头指针参考答案： 双向34. 在 链表中，可以用表尾指针代替表头指针参考答案： 双向35. 根据n个数据元素建立对应的顺序表和单链表存储结构，其算法的时间复杂度最好的情况是 ，最参考答案：0(n) ， 0( n2)36. 求线性表的顺序存储和链式存储的长度的算法时间复杂度分别是 和 参考答案：0(1) , 0(n)37. 在一个带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？ 参考答案：相同38. 在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？ 参考答案：不相同39. 阐述顺序表和链表存储方式的特点参考答案：顺序表存储方式为数据分配连续的存储单元， 数据元素按逻辑顺序依次存储到相应存储单元中， 使得逻辑相此可以实现随即访问线性表的数据元素，即数据访问的时间复杂度为 0(1)。
链表存储方式分配的存储单元可以不连续，通过每个结点的指针域来表示数据元素之间的逻辑关系，只能顺40. 若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什么？参考答案：若频繁地对一个线性表进行插入和删除操作， 则该线性表宜采用链式存储结构 因此链式存储结构在移动数据元素，只需要修改结点的指针域就可以改变数据元素之间的逻辑关系41. 在单链表、双向循环链表和单循环链表中，若仅知道指针 p指向某结点，不知道头指针，能否将结点 p从相间复杂度各为多少参考答案：要实现删除p结点的操作，必须找到其前驱结点，修改其指针域的值使其指向 p的后继结点，以实现此不知道头指针就无法找到结点 p的前驱结点双向循环链表和单循环链表可以可以实现删除 p结点单循环链0(n)，双循环链表删除 P结点的时间复杂度为 0(1)42. 对链表设置头结点的作用是什么？参考答案：对带头结点的链表， 在表的任何结点之前插入结点或删除任何位置的结点， 所要做的都是修改前一个结点的表中任何元素结点都有前驱结点如果没有头结点，在首元结点前插入结点或删除首元结点都要修改头指针，其 杂些其次，带头结点的链表结构，初始化后的头指针就固定了，除撤销算法外，所有算法都不会修改头指针43. 已知一个线性表用含头结点的单链表做存储结构，写一个算法求单链表的长度。
参考答案：int listlenght(linklist L){ int len gth=0;P=L->n ext;while(p){ len gth++;p=p->n ext;}return(le ngth);}44. 已知一个顺序表 L,其中的元素按值递增有序排列，设计一个算法插入一个值为 x的元素后保持该顺序表仍0( 1 )参考答案：void in sertsq(sqlist L,elemtype x){ n=L.le ngth-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
参考答案： 顺序队列的假溢出61. 区分循环队列的空与满有 3种方法，它们是 、 、 参考答案：少用一个元素 、设空满标志 、用计数器记录队列中元素个数 62. 栈和队列的区别是 , , 参考答案：栈只能在表一端进行插入和删除操作，队列限制在表的一端进行插入操作，在另一端进行删除操作 63. —个栈的输入序列是 12345，则栈的输出序列 43512是 参考答案：错误的64. 设栈采取顺序存储结构，栈中已有 i-1个元素，则第i个元素进栈操作的算法时间复杂度是 参考答案：0( 1)65. 栈的特点是【① 】，队列的特点是【② 】；栈和队列都是【③ 】若入栈序列是1,是不可能的出栈序列；若进队列的序列是 1，2，3, 4，则【⑤ 】是可能的出队序列参考答案：① 后进先出 ②先进先出③限制存取点的线性结构④ 3,2,1,4⑤ 1,2,3,466. 若用不带头结点的单链表表示栈，则创建一个空栈要执行的操作是 参考答案：top=NULL67. 从循环队列中删除一个元素的操作是 参考答案：Q.fron t=(Q.fro nt+1)%QSize68. 从循环队列中插入一个元素的操作是 。
参考答案： Q.rear=(Q.rear+1)%QSize 69. 判断链队列中只有一个结点的条件是 参考答案：Q.fron t-> next==Q.rear70. 如果栈的最大长度难以估计，最好使用 参考答案：链栈71. 为什么说栈是一种后进先出表？参考答案：因为栈是限定在表的一端进行插入和删除操作，所以后入栈的数据元素总是先出栈，所以说栈是一种72. 对于一个栈，其输入序列是 A,B,C，试给出全部可能的输出序列参考答案：可能的出栈序列是： ABC ACB BAC BCA CBA73. 何谓队列上溢？何为假溢出现象？有哪些解决假溢出问题的方法，并分别阐述其工作原理 参考答案：队列上溢指在队列的顺序存储分配中，按照队列的操作规则，需要进队的元素因找不到合适的存储单元而无假溢出指在队列的顺序存储分配中，分配给队列的存储空间有存储单元未被占用，但按照操作规则而使进队解决假溢出问题的方法是在队列的顺序存储分配中， 分配给队列的存储空间可以循环使用， 其进本原理是用队列的存储空间长度进行取模运算即：入队操作：Q.rear=(Q.rear+1)%MSize出队操作：Q.fro nt=(Q.fro nt+1)%MSize74. 队列可以用单循环链表来实现，故可以只设一个头指针或只设一个尾指针，请分析用哪种方案最合适。
参考答案：使用循环链表来表示队列， 设置尾指针比较合适， 因为入队操作可以直接在尾结点后进行插入操作， 出队操到链表的头结点，入队出队操作的算法时间复杂度均为杂度为0(n)0(1)若只设头指针，则出队操作的算法时间复杂度为75. 深度为k的完全二叉树至少有 个结点，至多有 个结点参考答案：2k-1 ,2 K-176. 在一棵二叉树中，度为 0的结点个数为n0,度为2的结点个数为n2,则有n0= 参考答案： n2+177. 一棵二叉树第i层最多有 个结点，一棵有 n个结点的满二叉树共有 个结点，共有 _个叶结点参考答案：2i-1 ,2 K-1 , 2K-178.根据二叉树的定义，具有 3个结点的二叉树共有 种不同形态，它们分别是 # / 12# / 1279. 有一棵如下图所示的树，回答下列问题：① 这棵树的根结点是 ② 这棵树的叶子结点是 ③ 结点C的度为 ④ 这棵树的深度是 ⑤ 结点c的孩子结点是 ⑥ 结点c的双亲结点是 ① a② b,e,g,d③ 2④ 4⑤ e,f⑥ a⑦ 380. 树与二叉树的两个主要差别是 、 参考答案：树中结点的最大度没有限制，二叉树结点的最大度限定为 2 、 树的结点无左右之分，二叉树参考答案：前序序列：eadcbifghj中序序列：abcdiefhgj 后序序列：bcidahjgfe82. 给出下图所示的树的二叉树表示。
参考答案：下图为其树的二叉树表示83. 有一份电文共有 5个字符：a,b,c,d,e,它们出现的频率依次为 4, 7, 5, 2, 9,构造对应的哈夫曼树，求哈字符的哈夫曼编码参考答案：# / 1229字符编码:18# / 12011b: 10c: 00 d: 010e: 1184.假设一棵二叉树采用顺序存储结构，如下图所示0 5 10 15 20eafdgcjh ib回答些列问题：① 画出二叉树表示② 写岀先序、中序和后序遍历结果③ 写出结点c的双亲结点和左、右孩子结点④ 画出此二叉树还原成森林的图参考答案：①二叉树表示如下图所示 / 12# / 12# / 12② 先序序列为：eadcbjfghi中序序列为：acbdjefhgi后序序列为：bcjdahigfe③ 结点c的双亲结点是d,左孩子为b,无右孩子# / 12# / 1285.有n个顶点的无向图最多有 条边参考答案：n(n-1)/286. 一个图的 表示法是唯一的，而 表示法是不唯一的 / 12参考答案：邻接矩阵， 邻接表87. 具有10个顶点的无向图，边。