数据结构c语言版考研试题及答案

数据结构c语言版考研试题及答案数据结构C语言版考研试题及答案一、选择题（20分，共10题，每题2分）1.以下关于数据结构的描述中，错误的是（）A.数据结构是数据对象中数据元素之间关系的集合B.数据结构包括数据的逻辑结构和物理结构C.数据的物理结构是数据在计算机内存中的存储方式D.数据结构只研究数据的逻辑结构，不考虑数据的存储方式答案：【D】解析：数据结构既研究数据的逻辑结构，也研究数据的物理结构，因此D选项错误。数据的物理结构是数据在计算机内存中的存储方式，包括顺序存储、链式存储等，因此C选项正确。数据结构是数据对象中数据元素之间关系的集合，包括逻辑结构和物理结构两个方面，因此A和B选项正确。2.在长度为n的顺序表中，删除第i个元素的时间复杂度为（）A.O(1)B.O(n)C.O(i)D.O(n-i)答案：【D】解析：在顺序表中删除第i个元素后，需要将第i+1个元素到第n个元素依次前移一位，移动的元素个数为n-i，因此时间复杂度为O(n-i)。选项A是错误的，因为删除操作不是常数时间；选项B是错误的，因为不是所有情况都需要移动n个元素；选项C是错误的，因为移动的元素个数与i的关系不是线性的。3.以下关于链式存储结构的描述中，正确的是（）A.链式存储结构需要预先分配存储空间B.链式存储结构可以随机存取任意元素C.链式存储结构插入和删除操作的时间复杂度均为O(1)D.链式存储结构中每个节点包含数据域和指针域答案：【D】解析：链式存储结构的特点是每个节点包含数据域和指针域，通过指针链接各个节点，因此D选项正确。链式存储结构不需要预先分配存储空间，可以动态申请，因此A选项错误。链式存储结构不支持随机存取，只能顺序存取，因此B选项错误。链式存储结构中插入和删除操作的时间复杂度取决于操作位置，如果已知插入或删除位置的前驱节点，则时间复杂度为O(1)，否则需要查找前驱节点，时间复杂度为O(n)，因此C选项错误。4.在栈的顺序存储结构中，判断栈"空"的条件是（）A.top==0B.top==1C.top==-1D.top==MAXSIZE答案：【C】解析：在栈的顺序存储结构中，通常使用top指针表示栈顶元素的位置。当top等于-1时，表示栈中没有元素，即栈为空。选项A和B是错误的，因为栈空时top通常不会等于0或1。选项D是错误的，因为top等于MAXSIZE时表示栈满，而不是栈空。5.以下关于队列的描述中，错误的是（）A.队列是一种先进先出的线性表B.循环队列可以解决假溢出问题C.循环队列中判断队"空"的条件是front==rearD.循环队列中判断队"满"的条件是front==rear答案：【D】解析：队列是一种先进先出的线性表，因此A选项正确。循环队列通过将存储空间首尾相连，可以解决假溢出问题，因此B选项正确。循环队列中判断队"空"的条件是front==rear，因此C选项正确。循环队列中判断队"满"的条件通常是front==(rear+1)%MAXSIZE，而不是front==rear，因为front==rear时也可能是队空状态，因此D选项错误。6.以下关于二叉树的描述中，错误的是（）A.二叉树中每个节点最多有两个子节点B.任何一棵二叉树都可以通过先序遍历和中序遍历唯一确定C.满二叉树一定是完全二叉树D.二叉树的叶子节点个数等于度为2的节点个数加1答案：【B】解析：二叉树中每个节点最多有两个子节点，这是二叉树的定义，因此A选项正确。并非任何一棵二叉树都可以通过先序遍历和中序遍历唯一确定，当二叉树中有重复元素时可能无法唯一确定，因此B选项错误。满二叉树一定是完全二叉树，因此C选项正确。二叉树的叶子节点个数等于度为2的节点个数加1，这是二叉树的一个重要性质，因此D选项正确。7.在二叉排序树中，查找一个关键字为key的节点的时间复杂度为（）A.O(1)B.O(logn)C.O(n)D.取决于二叉排序树的形状答案：【D】解析：在二叉排序树中，查找一个关键字为key的节点的时间复杂度取决于二叉排序树的形状。如果二叉排序树是平衡的，时间复杂度为O(logn)；如果二叉排序树退化为单支树，时间复杂度为O(n)。因此，选项D是正确的。选项A是错误的，因为查找操作不是常数时间。选项B是错误的，因为只有在平衡的二叉排序树中查找时间复杂度才是O(logn)。选项C是错误的，因为只有在最坏情况下，即二叉排序树退化为单支树时，查找时间复杂度才是O(n)。8.以下关于图的存储结构的描述中，错误的是（）A.邻接矩阵适合表示稠密图B.邻接表适合表示稀疏图C.邻接矩阵的空间复杂度为O(n²)，其中n为顶点数D.邻接表的空间复杂度为O(n)，其中n为顶点数答案：【D】解析：邻接矩阵适合表示稠密图，因为其空间复杂度为O(n²)，当图较稠密时，空间利用率较高，因此A选项正确。邻接表适合表示稀疏图，因为其空间复杂度为O(n+e)，其中n为顶点数，e为边数，当图较稀疏时，空间利用率较高，因此B选项正确。邻接矩阵的空间复杂度为O(n²)，其中n为顶点数，因此C选项正确。邻接表的空间复杂度为O(n+e)，其中n为顶点数，e为边数，而不是O(n)，因此D选项错误。9.以下关于排序算法的描述中，错误的是（）A.快速排序的最坏时间复杂度为O(n²)B.希尔排序的时间复杂度为O(nlogn)C.归并排序的空间复杂度为O(1)D.堆排序是不稳定的排序算法答案：【C】解析：快速排序的最坏时间复杂度为O(n²)，当每次划分都极不平衡时会出现这种情况，因此A选项正确。希尔排序的时间复杂度取决于增量序列的选择，平均时间复杂度为O(nlogn)，但最坏情况下可能达到O(n²)，因此B选项不完全正确。归并排序的空间复杂度为O(n)，需要额外的存储空间来合并有序子序列，而不是O(1)，因此C选项错误。堆排序是不稳定的排序算法，因为相同的元素可能在堆调整后改变相对位置，因此D选项正确。10.以下关于查找算法的描述中，正确的是（）A.二分查找要求数据元素有序存储B.二分查找的时间复杂度为O(n)C.哈希查找的时间复杂度为O(1)D.平衡二叉树的查找时间复杂度为O(n)答案：【A】解析：二分查找要求数据元素有序存储，这是二分查找的前提条件，因此A选项正确。二分查找的时间复杂度为O(logn)，而不是O(n)，因此B选项错误。哈希查找的平均时间复杂度为O(1)，但在最坏情况下可能达到O(n)，因此C选项不完全正确。平衡二叉树的查找时间复杂度为O(logn)，而不是O(n)，因此D选项错误。二、填空题（15分，共5题，每题3分）1.在长度为n的顺序表中，插入一个元素的平均时间复杂度为_______。答案：【O(n)】解析：在顺序表中插入一个元素，需要移动插入位置之后的所有元素。平均情况下，插入位置在表的中间，需要移动约n/2个元素，因此时间复杂度为O(n)。易错警示：有些考生可能会误认为插入操作的时间复杂度为O(1)，这是错误的，因为顺序表的插入操作需要移动元素。2.在栈的顺序存储结构中，通常使用一个变量_______来表示栈顶元素的位置。答案：【top】解析：在栈的顺序存储结构中，通常使用一个变量top来表示栈顶元素的位置。当栈为空时，top通常初始化为-1；当栈非空时，top指向栈顶元素的位置。定义：栈是一种特殊的线性表，只允许在一端进行插入和删除操作，允许插入和删除的一端称为栈顶，另一端称为栈底。3.二叉树的遍历方式有前序遍历、中序遍历、后序遍历和_______。答案：【层序遍历】解析：二叉树的遍历方式有前序遍历、中序遍历、后序遍历和层序遍历。前序遍历的顺序是根节点、左子树、右子树；中序遍历的顺序是左子树、根节点、右子树；后序遍历的顺序是左子树、右子树、根节点；层序遍历是按照层次从上到下、从左到右遍历二叉树。4.在图的邻接矩阵表示中，无向图的邻接矩阵是一个_______矩阵。答案：【对称】解析：在图的邻接矩阵表示中，无向图的邻接矩阵是一个对称矩阵，因为无向图中的边没有方向，如果顶点i和顶点j之间存在边，则邻接矩阵中的元素matrix[i][j]和matrix[j][i]都等于1（或边的权值）。而易错警示：有向图的邻接矩阵通常不是对称的，因为边有方向。5.快速排序的平均时间复杂度为_______，最坏时间复杂度为_______。答案：【O(nlogn)，O(n²)】解析：快速排序的平均时间复杂度为O(nlogn)，这是在每次划分都比较平衡的情况下。最坏情况下，当每次划分都极不平衡时（例如，输入数组已经有序或逆序），时间复杂度退化为O(n²)。计算过程：快速排序的时间复杂度取决于递归的深度，平均情况下递归深度为log₂n，每层处理n个元素，因此平均时间复杂度为O(nlogn)；最坏情况下递归深度为n，每层处理n个元素，因此最坏时间复杂度为O(n²)。三、判断题（10分，共5题，每题2分）1.顺序表的存储密度高于链表的存储密度。（）答案：【√】解析：顺序表的存储密度高于链表的存储密度。存储密度是指数据元素本身所占用的存储空间与整个结构所占用的存储空间的比值。顺序表中每个元素只存储数据本身，不需要额外的指针域，因此存储密度为1；链表中每个元素除了存储数据本身外，还需要存储指向下一个元素的指针，因此存储密度小于1。2.循环队列中，当front等于rear时，队列一定为空。（）答案：【×】解析：循环队列中，当front等于rear时，队列可能为空，也可能为满。为了避免这种歧义，通常采用牺牲一个存储单元的方法来判断队列是否为满，即当front等于(rear+1)%MAXSIZE时，队列为满；当front等于rear时，队列为空。易错警示：有些考生可能会认为front等于rear时队列一定为空，这是错误的，因为在循环队列中，当队列满时也可能出现front等于rear的情况。3.任何一棵二叉树都可以通过先序遍历和中序遍历唯一确定。（）答案：【×】解析：并非任何一棵二叉树都可以通过先序遍历和中序遍历唯一确定。当二叉树中有重复元素时，不同的二叉树可能具有相同的先序遍历序列和中序遍历序列，因此无法唯一确定。只有当二叉树中的元素都不相同时，才能通过先序遍历和中序遍历唯一确定。4.在二叉排序树中，查找一个元素的平均时间复杂度为O(logn)。（）答案：【×】解析：在二叉排序树中，查找一个元素的平均时间复杂度取决于树的平衡性。如果二叉排序树是平衡的，查找时间复杂度为O(logn)；但如果二叉排序树退化为单支树，查找时间复杂度为O(n)。因此，不能简单地认为查找时间复杂度为O(logn)。定义：二叉排序树是一种特殊的二叉树，其中每个节点的左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。5.希尔排序是一种稳定的排序算法。（）答案：【×】解析：希尔排序是一种不稳定的排序算法。在希尔排序中，通过增量序列将待排序序列分成若干子序列进行排序，相同元素可能在不同的子序列中被移动，导致它们的相对位置发生变化，因此希尔排序是不稳定的。公式：希尔排序的时间复杂度取决于增量序列的选择，平均时间复杂度为O(nlogn)，但最坏情况下可能达到O(n²)。四、简答题（25分，共5题，每题5分）1.简述顺序表和链表的区别。答案：【顺序表和链表的主要区别在于存储方式和操作特点。存储方式上，顺序表在内存中占用连续的存储空间，而链表的节点在内存中可以是非连续的。操作特点上，顺序表的随机访问时间复杂度为O(1)，但插入和删除操作需要移动元素，时间复杂度为O(n)；链表的随机访问时间复杂度为O(n)，但插入和删除操作只需修改指针，时间复杂度为O(1)。此外，顺序表的存储密度高，不需要额外的指针域，而链表的存储密度低，需要额外的指针域。顺序表需要预先分配存储空间，而链表可以动态分配存储空间。】解析：顺序表和链表是线性表的两种不同存储方式。顺序表在内存中占用连续的存储空间，可以通过下标直接访问元素，因此随机访问时间复杂度为O(1)。但插入和删除操作需要移动大量元素，时间复杂度为O(n)。链表的节点在内存中可以是非连续的，每个节点包含数据域和指针域，通过指针链接各个节点。链表的随机访问需要从头节点开始遍历，时间复杂度为O(n)，但插入和删除操作只需修改指针，时间复杂度为O(1)。顺序表的存储密度为1，不需要额外的指针域，而链表的存储密度小于1，需要额外的指针域。顺序表需要预先分配存储空间，大小固定，而链表可以动态分配存储空间，大小可变。2.简述栈和队列的异同点。答案：【栈和队列的相同点在于它们都是特殊的线性表，都受到限制的插入和删除操作。不同点在于栈是一种后进先出（LIFO）的线性表，只能在栈顶进行插入和删除操作；而队列是一种先进先出（FIFO）的线性表，只能在队尾进行插入操作，在队头进行删除操作。栈的主要应用包括函数调用表达式求值、括号匹配等；队列的主要应用包括广度优先搜索、任务调度等。】解析：栈和队列都是特殊的线性表，它们都受到限制的插入和删除操作。栈是一种后进先出（LIFO）的线性表，只能在栈顶进行插入和删除操作。栈的主要操作包括入栈（push）和出栈（pop），时间复杂度均为O(1)。栈的主要应用包括函数调用、表达式求值、括号匹配等。队列是一种先进先出（FIFO）的线性表，只能在队尾进行插入操作，在队头进行删除操作。队列的主要操作包括入队（enqueue）和出队（dequeue），时间复杂度均为O(1)。队列的主要应用包括广度优先搜索、任务调度、缓冲区管理等。易错警示：有些考生可能会混淆栈和队列的操作特点，需要明确栈是后进先出，队列是先进先出。3.简述二叉树的性质及其应用。答案：【二叉树的主要性质包括：1）二叉树中第i层上的节点数最多为2^(i-1)；2）深度为k的二叉树最多有2^k-1个节点；3）对于任何一棵二叉树，如果度为0的节点数为n0，度为2的节点数为n2，则n0=n2+1；4）具有n个节点的完全二叉树的深度为⌊log₂n⌋+1。二叉树的主要应用包括表达式求值、哈夫曼编码、二叉排序树、堆等。二叉排序树是一种特殊的二叉树，用于高效查找；堆是一种特殊的完全二叉树，用于优先队列的实现。】解析：二叉树是一种重要的数据结构，具有许多有用的性质。二叉树中第i层上的节点数最多为2^(i-1)，因为每个节点最多有两个子节点。深度为k的二叉树最多有2^k-1个节点，这是满二叉树的节点数。对于任何一棵二叉树，如果度为0的节点数为n0，度为2的节点数为n2，则n0=n2+1，这是二叉树的一个重要性质。具有n个节点的完全二叉树的深度为⌊log₂n⌋+1，因为完全二叉树是一种特殊的二叉树，除了最后一层外，其他各层节点数都达到最大，且最后一层的节点都连续集中在左边。二叉树的应用非常广泛，包括表达式求值、哈夫曼编码、二叉排序树、堆等。二叉排序树是一种特殊的二叉树，其中每个节点的左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值，用于高效查找。堆是一种特殊的完全二叉树，分为最大堆和最小堆，用于优先队列的实现。4.简述图的两种主要存储结构及其适用场景。答案：【图的两种主要存储结构是邻接矩阵和邻接表。邻接矩阵使用一个二维数组表示图，其中matrix[i][j]表示顶点i和顶点j之间的关系。邻接矩阵适合表示稠密图，即边数接近顶点数平方的图，因为其空间复杂度为O(n²)，其中n为顶点数。邻接表使用一个数组存储每个顶点的邻接表，其中每个邻接表存储与该顶点相邻的所有顶点。邻接表适合表示稀疏图，即边数远小于顶点数平方的图，因为其空间复杂度为O(n+e)，其中n为顶点数，e为边数。】解析：图的存储结构主要有邻接矩阵和邻接表两种。邻接矩阵使用一个二维数组表示图，其中matrix[i][j]表示顶点i和顶点j之间的关系。对于无向图，邻接矩阵是对称的；对于带权图，matrix[i][j]可以存储边的权值。邻接矩阵的空间复杂度为O(n²)，其中n为顶点数，适合表示稠密图，因为当图较稠密时，空间利用率较高。邻接表使用一个数组存储每个顶点的邻接表，其中每个邻接表存储与该顶点相邻的所有顶点。邻接表的空间复杂度为O(n+e)，其中n为顶点数，e为边数，适合表示稀疏图，因为当图较稀疏时，空间利用率较高。此外，邻接表还便于遍历图的邻接点，适合图的遍历算法。易错警示：有些考生可能会混淆邻接矩阵和邻接表的适用场景，需要明确邻接矩阵适合稠密图，邻接表适合稀疏图。5.简述快速排序的基本思想及其时间复杂度。答案：【快速排序的基本思想是选择一个基准元素（pivot），将待排序序列分为两部分，使得左边的元素都小于基准元素，右边的元素都大于基准元素，然后对左右两部分递归进行快速排序。快速排序的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n²)，空间复杂度为O(logn)（递归栈空间）。快速排序是一种不稳定的排序算法，但平均情况下性能较好，是实际应用中常用的排序算法之一。】解析：快速排序是一种高效的排序算法，其基本思想是分治法。首先选择一个基准元素（pivot），通常选择序列的第一个元素、最后一个元素或中间元素。然后通过一趟排序将待排序序列分为两部分，使得左边的元素都小于基准元素，右边的元素都大于基准元素。这一过程称为划分（partition）。最后对左右两部分递归进行快速排序，直到子序列长度为1或0时停止。快速排序的平均时间复杂度为O(nlogn)，这是在每次划分都比较平衡的情况下。最坏情况下，当每次划分都极不平衡时（例如，输入数组已经有序或逆序），时间复杂度退化为O(n²)。快速排序的空间复杂度为O(logn)，主要是递归栈的空间。快速排序是一种不稳定的排序算法，因为相同元素可能在划分过程中改变相对位置。尽管如此，快速排序在实际应用中仍然是一种常用的排序算法，因为其平均性能较好。五、算法设计题（20分，共2题，每题10分）1.设计一个算法，判断一个单链表是否有环。如果有环，返回环的入口节点；如果没有环，返回NULL。答案：【```ctypedefstructListNode{intval;structListNodenext;}ListNode;ListNodedetectCycle(ListNodehead){if(head==NULL||head->next==NULL){returnNULL;}ListNodeslow=head;ListNodefast=head;//使用快慢指针判断是否有环while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;if(slow==fast){//有环，找环的入口slow=head;while(slow!=fast){slow=slow->next;fast=fast->next;}returnslow;}}//无环returnNULL;}```】解析：判断单链表是否有环可以使用快慢指针法。定义两个指针slow和fast，初始时都指向链表头节点。slow每次移动一步，fast每次移动两步。如果链表有环，则fast和slow最终会在环中相遇；如果链表无环，则fast会先到达链表末尾。当slow和fast相遇时，说明链表有环。此时，将slow重新指向链表头节点，然后slow和fast每次都移动一步，它们再次相遇的节点就是环的入口节点。这是因为当slow和fast第一次相遇时，fast比slow多走了环的整数倍长度。设环的长度为L，环的入口节点到相遇点的距离为x，相遇点到环的入口节点的距离为y，则L=x+y。当fast和slow第一次相遇时，fast走了2(x+y)，slow走了x+y，所以fast比slow多走了x+y，即环的长度L。因此，当slow重新指向链表头节点，并与fast同时以相同速度移动时，它们会在环的入口节点相遇。易错警示：有些考生可能会在找到相遇点后直接返回，而没有继续寻找环的入口节点，这是错误的。另外，有些考生可能会忽略链表为空或只有一个节点的情况，需要特别处理。2.设计一个算法，实现归并排序，并分析其时间复杂度和空间复杂度。答案：【```c//合并两个有序子数组voidmerge(intarr[],intleft,intmid,intright){intn1=mid-left+1;intn2=right-mid;//创建临时数组intL[n1],R[n2];//复制数据到临时数组for(inti=0;i<n1;i++){L[i]=arr[left+i];}for(intj=0;j<n2;j++){R[j]=arr[mid+1+j];}//合并临时数组inti=0,j=0,k=left;while(i<n1&&j<n2){if(L[i]<=R[j]){arr[k]=L[i];i++;}else{arr[k]=R[j];j++;}k++;}//复制剩余元素while(i<n1){arr[k]=L[i];i++;k++;}while(j<n2){arr[k]=R[j];j++;k++;}}//归并排序主函数voidmergeSort(intarr[],intleft,intright){if(left<right){intmid=left+(right-left)/2;//递归排序左半部分mergeSort(arr,left,mid);//递归排序右半部分mergeSort(arr,mid+1,right);//合并已排序的子数组merge(arr,left,mid,right);}}```】解析：归并排序是一种基于分治法的排序算法，其基本思想是将待排序序列分成两个子序列，分别对子序列进行递归排序，然后将已排序的子序列合并成一个有序序列。归并排序的主要步骤包括：1）将序列分成两个子序列；2）递归地对子序列进行归并排序；3）合并两个已排序的子序列。合并操作是归并排序的关键步骤，它需要创建临时数组来存储子序列，然后比较两个子序列的元素，将较小的元素放入原数组中，直到所有元素都被合并。归并排序的时间复杂度为O(nlogn)，其中n为序列的长度。这是因为归并排序将序列分成logn层，每层需要O(n)的时间进行合并。归并排序的空间复杂度为O(n)，因为需要创建临时数组来存储子序列。归并排序是一种稳定的排序算法，因为相同元素在合并过程中会保持它们的相对位置。易错警示：有些考生可能会忽略合并过程中剩余元素的处理，导致排序结果不正确。另外，有些考生可能会错误地计算归并排序的空间复杂度，认为它是O(1)，这是错误的，因为归并排序需要额外的存储空间来合并子序列。六、综合应用题（10分，共1题）1.设计一个算法，实现LRU（最近最少使用）缓存机制，要求get和put操作的时间复杂度均为O(1)。答案：【```ctypedefstructDLinkedNode{intkey;intvalue;structDLinkedNodeprev;structDLinkedNodenext;}DLinkedNode;typedefstruct{intcapacity;intsize;DLinkedNodehead;DLinkedNodetail;DLinkedNodehashTable;inthashSize;}LRUCache;//创建双向链表节点DLinkedNodecreateDLinkedNode(intkey,intvalue){DLinkedNodenode=(DLinkedNode)malloc(sizeof(DLinkedNode));node->key=key;node->value=value;node->prev=NULL;node->next=NULL;returnnode;}//初始化LRU缓存LRUCachelRUCacheCreate(intcapacity){LRUCachecache=(LRUCache)malloc(sizeof(LRUCache));cache->capacity=capacity;cache->size=0;//创建头尾节点，简化边界条件处理cache->head=createDLinkedNode(0,0);cache->tail=createDLinkedNode(0,0);cache->head->next=cache->tail;cache->tail->prev=cache->head;//初始化哈希表cache->hashSize=capacity2;//哈希表大小设为容量的两倍，减少冲突cache->hashTable=(DLinkedNode)calloc(cache->hashSize,sizeof(DLinkedNode));returncache;}//哈希函数inthash(intkey,inthashSize){returnkey%hashSize;}//将节点添加到链表头部voidaddToHead(LRUCachecache,DLinkedNodenode){node->prev=cache->head;node->next=cache->head->next;cache->head->next->prev=node;cache->head->next=node;}//从链表中移除节点voidremoveNode(DLinkedNodenode){node->prev->next=node->next;node->next->prev=node->prev;}//将节点移动到链表头部voidmoveToHead(LRUCachecache,DLinkedNodenode){removeNode(node);addToHead(cache,node);}//获取缓存中的值intlRUCacheGet(LRUCacheobj,intkey){inthashIndex=hash(key,obj->hashSize);DLinkedNodenode=obj->hashTable[hashIndex];//在哈希表中查找节点while(node!=NULL){if(node->key==key){//找到节点，将其移动到链表头部moveToHead(obj,node);returnnode->value;}node=node->next;}return-1;}//向缓存中添加或更新键值对voidlRUCachePut(LRUCacheobj,intkey,intvalue){inthashIndex=hash(key,obj->hashSize);DLinkedNodenode=obj->hashTable[hashIndex];//检查键是否已存在while(node!=NULL){if(node->key==key){//键已存在，更新值并移动到链表头部node->value=value;moveToHead(obj,node);return;}node=node->next;}//键不存在，创建新节点DLinkedNodenewNode=createDLinkedNode(key,value);//如果缓存已满，删除尾节点（最近最少使用的节点）if(obj->size==obj->capacity){DLinkedNodetailNode=obj->tail->prev;removeNode(tailNode);//从哈希表中删除尾节点inttailHashIndex=hash(tailNode->key,obj->hashSize);DLinkedNodeprev=NULL;DLinkedNodecurr=obj->hashTable[tailHashIndex];while(curr!=NULL){if(curr->key==tailNode->key){if(prev==NULL)