三、主观题(共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. 在 链表中，可以用表尾指针代替表头指针。 | 参考答案： 双向 | |
| | 34. 在 链表中，可以用表尾指针代替表头指针。 | 参考答案： 双向 | |
| | 35. 根据n个数据元素建立对应的顺序表和单链表存储结构，其算法的时间复杂度最好的情况是 ，最坏的情况是 。 | 参考答案：O(n) ， O(n2) | |
| | 36. 求线性表的顺序存储和链式存储的长度的算法时间复杂度分别是 和 。 | 参考答案： O(1) , O(n) | |
| | 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&<(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; } | |
| | 第三次作业 | | | |
|
三、主观题(共50道小题) |
60. 循环队列的引入，目的是为了克服 。 | 参考答案： 顺序队列的假溢出 | |
| |
61. 区分循环队列的空与满有3种方法，它们是 、 、 。 | 参考答案：少用一个元素 、 设空满标志 、 用计数器记录队列中元素个数 | |
| |
62. 栈和队列的区别是 ， ， 。 | 参考答案：栈只能在表一端进行插入和删除操作，队列限制在表的一端进行插入操作，在另一端进行删除操作 | |
| |
63. 一个栈的输入序列是12345，则栈的输出序列43512是 。 | 参考答案：错误的 | |
| |
64. 设栈采取顺序存储结构，栈中已有i-1个元素，则第i个元素进栈操作的算法时间复杂度是 。 | 参考答案：O（1） | |
| |
65. 栈的特点是【① 】，队列的特点是【② 】；栈和队列都是【③ 】若入栈序列是1，2，3，4 ，则【④ 】是不可能的出栈序列；若进队列的序列是1，2，3，4，则【⑤ 】是可能的出队序列。 | 参考答案： ①后进先出 ② 先进先出 ③ 限制存取点的线性结构④ 3,2,1,4 ⑤ 1,2,3,4 | |
| |
66. 若用不带头结点的单链表表示栈，则创建一个空栈要执行的操作是 。 | 参考答案：top=NULL | |
| |
67. 从循环队列中删除一个元素的操作是 。 | 参考答案：Q.front=(Q.front+1)%QSize | |
| |
68. 从循环队列中插入一个元素的操作是 。 | 参考答案： Q.rear=(Q.rear+1)%QSize | |
| |
69. 判断链队列中只有一个结点的条件是 。 | 参考答案：Q.front->next==Q.rear | |
| |
70. 如果栈的最大长度难以估计，最好使用 。 | 参考答案：链栈 | |
| |
71. 为什么说栈是一种后进先出表？ | 参考答案：因为栈是限定在表的一端进行插入和删除操作，所以后入栈的数据元素总是先出栈，所以说栈是一种后进先出表。 | |
| |
72. 对于一个栈，其输入序列是A,B,C,试给出全部可能的输出序列。 | 参考答案： 可能的出栈序列是：ABC、ACB、BAC、BCA、CBA。 | |
| |
73. 何谓队列上溢？何为假溢出现象？有哪些解决假溢出问题的方法，并分别阐述其工作原理。 | 参考答案： 队列上溢指在队列的顺序存储分配中，按照队列的操作规则，需要进队的元素因不到合适的存储单元而无法进入队列。 假溢出指在队列的顺序存储分配中，分配给队列的存储空间有存储单元未被占用，但按照操作规则而使进队的数据元素无法进队的现象。 解决假溢出问题的方法是在队列的顺序存储分配中，分配给队列的存储空间可以循环使用，其进本原理是用表示队头和队尾指针与分配给队列的存储空间长度进行取模运算。即： 入队操作：Q.rear=(Q.rear+1)%MSize 出队操作：Q.front=(Q.front+1)%MSize | |
| |
74. 队列可以用单循环链表来实现，故可以只设一个头指针或只设一个尾指针，请分析用哪种方案最合适。 | 参考答案： 使用循环链表来表示队列，设置尾指针比较合适，因为入队操作可以直接在尾结点后进行插入操作，出队操作时可以根据尾指针很容易到链表的头结点，入队出队操作的算法时间复杂度均为O(1)。若只设头指针，则出队操作的算法时间复杂度为O(1)，入队操作的算法时间复杂度为O(n)。 | |
| |
75. 深度为k的完全二叉树至少有 个结点，至多有 个结点。 | 参考答案：2K-1 ,2K-1 | |
| |
76. 在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2,则有n0= 。 | 参考答案： n2+1 | |
| |
77. 一棵二叉树第i层最多有 个结点，一棵有n个结点的满二叉树共有 个结点，共有 个叶结点。 | 参考答案：2i-1 ,2K-1 , 2K-1 | |
| |
| |
发表评论