广东工业大学《数据结构》历年期末考试试卷(含答案)

广东工业大学《数据结构》历年期末考试试卷（含答案）一、选择题（每题2分，共20分）1.下面哪一个不是线性结构的基本特征？（）A.有且只有一个根节点B.每个节点最多有一个前件，最多有一个后件C.有且只有一个终端节点D.每个节点都有多个前件和后件答案：D2.在单链表中，若要删除指针P所指的节点，则执行（）。A.P=P->nextB.P->next=P->next->nextC.P->next=PD.P=P->next->next答案：B3.下面关于二叉树的叙述正确的是（）。A.二叉树中，任何一个节点都有两个子节点B.二叉树中，任何一个节点最多有一个左子节点和一个右子节点C.二叉树中，任何一个节点最多有一个子节点D.二叉树中，任何一个节点都有两个前件答案：B4.下面关于顺序栈的叙述正确的是（）。A.栈底元素最先出栈B.栈顶元素最先出栈C.栈底元素最后出栈D.栈顶元素最后出栈答案：B5.下面哪一个不是队列的基本操作？（）A.入队B.出队C.取队头元素D.取队尾元素答案：D二、填空题（每题2分，共20分）6.在线性表中，插入和删除操作的时间复杂度分别为______和______。答案：O(1)和O(n)7.在双向链表中，每个节点包含三个基本部分：数据域、______和______。答案：前指针域、后指针域8.在二叉树中，若一个节点的度为2，则该节点称为______节点。答案：分支节点9.栈是一种______受限的线性表。答案：先进后出10.队列是一种______受限的线性表。答案：先进先出三、判断题（每题2分，共10分）11.在顺序表中，删除一个元素的时间复杂度为O(n)。（）答案：正确12.在链表中，插入一个元素的时间复杂度为O(1)。（）答案：错误13.在二叉树中，每个节点都有两个子节点。（）答案：错误14.在双向链表中，每个节点都有两个前件和两个后件。（）答案：错误15.在栈中，最先进入栈的元素最后出栈。（）答案：正确四、计算题（每题10分，共30分）16.已知线性表L=(12,3,5,7,9)，编写一个算法实现将线性表L中的所有元素逆置。答案：```voidreverseList(List&L){intn=L.length();for(inti=0;i<n/2;i++){inttemp=L[i];L[i]=L[n-1-i];L[n-1-i]=temp;}}```17.编写一个算法实现判断一个链表是否为循环链表。答案：```boolisCircularList(LinkListL){if(L==nullptr||L->next==nullptr){returnfalse;}LinkListslow=L;LinkListfast=L->next;while(fast!=nullptr&&fast->next!=nullptr){if(slow==fast){returntrue;}slow=slow->next;fast=fast->next->next;}returnfalse;}```18.编写一个算法实现求二叉树的高度。答案：```intgetHeight(BiTreeNoderoot){if(root==nullptr){return0;}intleftHeight=getHeight(root->left);intrightHeight=getHeight(root->right);returnmax(leftHeight,rightHeight)+1;}```五、应用题（每题10分，共20分）19.请举例说明栈和队列在生活中的应用。答案：栈的应用：浏览器的前进和后退功能、函数调用等。队列的应用：银行排队、餐厅排队等。20.请简要阐述二分查找的基本思想及其时间复杂度。答案：二分查找的基本思想：首先将待查找的键值与线性表中间位置的元