1、02331 数据结构 2023 年 4 月真题1、【单选题】、【单选题】算法的空间复杂度表示的是算法的空间复杂度表示的是A:算法的可读性B:算法的难易程度C:执行算法所耗费的时间D:执行算法所耗费的存储空间答案：D解析：那么，又如何来评价这些算法的优劣，进而从中选择好的算法呢？显然，算法的“正硒性”是首先要考虑的。所谓一个算法的正确性，是指对于一切合法的输入数据，该算法经过有限时间的执行都能得到正确的结果。此外，应主要考虑如下几点：（1）执行算法所耗费的时间，即时间复杂性。（2）执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性。（3）算法应易于理解、易于编程，易于调试等，即可读性和可操作
2、性。P372、【单选题】、【单选题】对需要频繁插入和删除元素的线性表，适合的存储方式是对需要频繁插入和删除元素的线性表，适合的存储方式是A:顺序存储B:链式存储C:索引存储D:散列存储答案：B解析：链式存储是对于需要频繁插入和删除元素的线性表来说比较适合的存储方式。链式存储使用指针将元素按照顺序连接起来，每个元素包含一个指向下一个元素的指针，这样在插入和删除元素时只需要改变指针的指向，而不需要移动其他元素。相比之下，顺序存储需要移动元素来腾出空间或填补空缺，效率较低。因此，对于需要频繁插入和删除元素的线性表，链式存储方式更加高效。3、【单选题】、【单选题】线性表的两个元素，如果逻辑上相邻，则线
3、性表的两个元素，如果逻辑上相邻，则A:顺序存储和链式存储时都一定相邻B:顺序存储和链式存储时都一定不相邻C:顺序存储时一定相邻，链式存储时不一定相邻D:顺序存储时不一定相邻，链式存储时一定相邻答案：C解析：对于顺序存储方式，线性表中逻辑上相邻的两个元素在物理存储上也是相邻的，即它们在内存中是连续存储的。这是因为顺序存储方式将线性表的元素按照顺序依次存放在一块连续的内存空间中。而对于链式存储方式，线性表中逻辑上相邻的两个元素在物理存储上不一定相邻，它们可以在内存中的任意位置。链式存储方式使用指针将元素连接起来，每个元素包含一个指向下一个元素的指针，因此元素的物理存储位置可以是离散的。因此，顺序存
4、储方式适合于需要频繁访问元素的场景，而链式存储方式适合于需要频繁插入和删除元素的场景。4、【单选题】、【单选题】在头指针为在头指针为 headhead 的单链表中，判断指针变量的单链表中，判断指针变量 p p 指向终端结点的条件是指向终端结点的条件是A:p-next-next=headB:p-next=headC:p-next-next=NULLD:p-next=NULL答案：D5、【单选题】、【单选题】若栈的进栈序列为若栈的进栈序列为 5,4,3,2,15,4,3,2,1，则经过出入栈操作可能获得的出栈序列是，则经过出入栈操作可能获得的出栈序列是A:4,5,1,3,2B:3,5,4,2,1C
5、:2,1,3,5,4D:4,3,5,1,2答案：D6、【单选题】、【单选题】在三维数组在三维数组 a7410a7410中，每个数组元素占用中，每个数组元素占用 2 2 个存储单元，所有数组元素个存储单元，所有数组元素存放在一个连续的存储空间中，则该数组需要的存储单元总数是存放在一个连续的存储空间中，则该数组需要的存储单元总数是A:560B:280C:42D:21答案：A7、【单选题】、【单选题】下列广义表中，表长为下列广义表中，表长为 3 3 的是的是A:(a,b,c)B:(a,(b,c),(d,e,f)C:(a,b,c,(d,e,f)D:(a,(b,c,d,e,f)答案：B8、【单选题】、【
6、单选题】深度为深度为 k(kk(k1)1)的满二叉树所包含的结点数是的满二叉树所包含的结点数是A:k+1B:2kC:2k-1D:2k+1答案：C9、【单选题】、【单选题】下列选项中，能唯一确定一棵二叉树的两个遍历序列是下列选项中，能唯一确定一棵二叉树的两个遍历序列是A:前序遍历序列和层次遍历序列B:后序遍历序列和层次遍历序列C:前序遍历序列和中序遍历序列D:前序遍历序列和后序遍历序列答案：C10、【单选题】、【单选题】下列关于连通的无向带权图下列关于连通的无向带权图 G G 的叙述中，正确的是的叙述中，正确的是A:图 G 的生成树至少含有一个回路B:图 G 的最小生成树总是唯一的C:图 G 的
7、邻接矩阵不一定是对称矩阵D:图 G 的生成树的边数等于顶点数减 1答案：D11、【单选题】、【单选题】下列排序方法中，不稳定的是下列排序方法中，不稳定的是A:堆排序B:冒泡排序C:归并排序D:直接插入排序答案：A12、【单选题】、【单选题】对图进行拓扑排序，可以得到的拓扑序列是A:BADCEBB:BACDEAC:ACBDEDED:ABDCE答案：D13、【单选题】、【单选题】下列选项中，能使用二分查找算法的是下列选项中，能使用二分查找算法的是A:顺序存储的线性表(4,16,5,6,55,89,34,25)B:顺序存储的线性表(4,5,6,16,25,34,55,89)C:散列存储的线性表(4,
8、5,6,16,25,34,55,89)D:链式存储的线性表(4,5,6,16,25,34,55,89)答案：B14、【单选题】、【单选题】在下列查找算法中，平均查找长度与数据规模基本无关的是在下列查找算法中，平均查找长度与数据规模基本无关的是A:顺序查找B:散列查找C:二分查找D:B 树中的查找答案：B15、【单选题】、【单选题】假设散列表长假设散列表长 m=10,m=10,散列函数散列函数 H(key)=key%9H(key)=key%9。表中已有。表中已有 3 3 个结点：个结点：H(23)=5,H(31)=4,H(17)=8,H(23)=5,H(31)=4,H(17)=8,其余位置为空。
9、现采用线性探查法处理冲突，依次存储关键字其余位置为空。现采用线性探查法处理冲突，依次存储关键字 4 4和和 3636 时需要探查的次数分别是时需要探查的次数分别是A:1 和 1B:2 和 1C:3 和 1D:1 和 3答案：C16、【问答题】、【问答题】设循环队列保存在数组设循环队列保存在数组 QNQN中，中，frontfront 和和 rearrear 分别为队头和队尾指针，初分别为队头和队尾指针，初始时始时 front=rear=0,front=rear=0,约定指针约定指针 rearrear 指向的单元始终为空，请用指向的单元始终为空，请用 C C 语言分别描述下列操作：语言分别描述下列
10、操作：(1)(1)将数据元素将数据元素 x x 入队。入队。(2)(2)将队首元素出队，并保存到变量将队首元素出队，并保存到变量 myDatamyData 中。中。(3)(3)计算队列中当前数据计算队列中当前数据元素的个数，并保存到变量元素的个数，并保存到变量 DLenthDLenth 中。中。答案：(1)数据元素 X 入队:if(rear+1)%N=front)printf(Queue overflow)elseQrear=x;rear=(rear+1)%N;(2)队首元素出队并保存到变量 myData.中:if(rear=front)printf(“Queue empty”)elsemyD
11、ata=Qfront;front=(front+1)%N;(3)当前队列长度DLenth=(N+rear-front)%N(或DLenth=(rear=front)?rear-front:N+rear-front)17、【问答题】、【问答题】已知稀疏矩阵 M 如下，采用三元组表存储。(1)请给出三元组表的类型定义。(2)写出矩阵 M 按列优先存储的三元组表。答案：18、【问答题】、【问答题】已知待排序记录的关键字序列为已知待排序记录的关键字序列为(45,37,75,18,53,31,48,37)(45,37,75,18,53,31,48,37)，请回答下列，请回答下列问题。问题。(1)(1)画
12、出其对应的完全二叉树画出其对应的完全二叉树 T T。(2)(2)将将 T T 调整为对应的大根堆，给出大根堆序列。调整为对应的大根堆，给出大根堆序列。答案：19、【问答题】、【问答题】将百分制成绩分成五个等级，已知成绩的对应关系及分布情况如下表所示。请回答下列问题。(1)根据哈夫曼树的基本原理，画出成绩评定判定树 T。(2)求树 T 的 WPL。答案：20、【问答题】、【问答题】单链表类型定义如下：单链表类型定义如下：typedeftypedef structstruct nodenodeDataTypeDataType data;data;structstructnodenode*next;
13、*next;LinkNode;LinkNode;typedeftypedef LinkNodeLinkNode*Linklist;*Linklist;函数函数 f30f30 的功能是删除带头结的功能是删除带头结点的单链表中点的单链表中 datadata 值为值为 x x 的全部结点，请在空白处填上适当内容将算法补充完整。的全部结点，请在空白处填上适当内容将算法补充完整。voidvoidf30(Linklistf30(Linklist head,DataTypex)head,DataTypex)LinkNodeLinkNode*p,*q,*s;*p,*q,*s;p=head;q=p=head;q
14、=（1 1）;while(q!=NULL)while(q!=NULL)if(if(（2 2）)s=q;q=q-next;s=q;q=q-next;p-next=q;free(s);p-next=q;free(s);elseelsep=q;p=q;q=q=（3 3）;答案：(1)p-next(2)q-data=x(3)q-next21、【问答题】、【问答题】二叉树的二叉链表类型定义如下：#define char DataTypetypedefstruct nodeDataType data;struct node*lchild,*rchild;BinTNode;typedef BinTNode*
15、BinTree;阅读下列函数并回答问题。void f31(BinTreebt)if(bt!=NULL)f31(bt-rchild);f31(bt-lchild);printf(%c,bt-data);(1)给出如图所示的二叉树 T,写出执行函数 f31(T)后得到的输出序列。(2)对于二叉树中的任意结点 N 及它的左子树 L 和它的右子树 R,f31 的遍历次序是什么？答案：(1)FDECBA(2)RLN 次序(或先序遍历的逆)22、【问答题】、【问答题】阅读下列函数并回答问题。阅读下列函数并回答问题。voidvoid f32(intf32(int r,intr,int N)N)intint
16、i,j,temp;i,j,temp;for(i=1;ifor(i=1;itemp=ri;temp=ri;j=i-1;j=i-1;while(tempwhile(temprj+1=rj;rj+1=rj;j=j-1;j=j-1;rj+1=temp;rj+1=temp;(1)(1)若若 t8=(3,12,5,78,6,9,4,35),t8=(3,12,5,78,6,9,4,35),写出执行函数写出执行函数 f32(t,8)f32(t,8)后数组后数组 t t中的各元素。中的各元素。(2)(2)函数函数 f32f32 的功能是什么？的功能是什么？答案：(1)3,4,5,6,9,12,35,78(2)直
17、接插入排序23、【问答题】、【问答题】函数函数 f33f33 实现二分查找，请回答下列问题。实现二分查找，请回答下列问题。(1)(1)在空白处补充适当内容，在空白处补充适当内容，使函数功能完整。使函数功能完整。(2)(2)如果待查序列如果待查序列 R R 为为(4,5,6,16,25,34,55,89)(4,5,6,16,25,34,55,89)，分别给出执，分别给出执行行f33(R,9,8)f33(R,9,8)和和 f33(R,34,8)f33(R,34,8)的返回值。的返回值。intint f33(SeqListf33(SeqList R,KeyTypeR,KeyType k,intk,i
18、nt n)n)intintlow=0,mid,high=n-1;low=0,mid,high=n-1;while(low=high)while(lowk(2)-1 和 524、【问答题】、【问答题】二叉树的二叉链表类型定义如下：二叉树的二叉链表类型定义如下：typedeftypedef structstruct nodenodeintint data;data;structstruct nodenode*lchild,*rchild;*lchild,*rchild;BinNode;BinNode;typedeftypedef BinNodeBinNode*BinTree;*BinTree;编写
19、函编写函数数f34(BinTreef34(BinTree Bt),Bt),返回二叉树返回二叉树 BtBt 中数据元素的最大值。中数据元素的最大值。函数的原型为：函数的原型为：intint f34(BinTreef34(BinTreeBt)Bt)。答案：#define Min-65525int f34(BinTree BT)int lvalue,rvalue,maxvalue;if(BT=NULL)return Min;if(BT!=NULL)lvalue=f34(BT-lchild);rvalue=f34(BT-rchild);maxvalue=(lvaluervalue)?lvalue:rv
20、alue;maxvalue=(maxvalueBT-data)?maxvalue:BT-data;return maxvalue;25、【填空题】、【填空题】顺序存储和链接存储方法中，无需连续分配存储空间的是（）。顺序存储和链接存储方法中，无需连续分配存储空间的是（）。答案：链接存储26、【填空题】、【填空题】设顺序表首元素的存储地址是设顺序表首元素的存储地址是 40004000，每个数据元素占，每个数据元素占 8 8 个存储单元，则个存储单元，则第第1111 个元素的存储地址是（）。个元素的存储地址是（）。答案：408027、【填空题】、【填空题】若在长度为若在长度为 n n 的顺序表中删除
21、第的顺序表中删除第 i i 个元素个元素(1(1i in),n),则需要向前移动的元素则需要向前移动的元素个数是（）。个数是（）。答案：n-i28、【填空题】、【填空题】顺序栈存放在数组顺序栈存放在数组 SmSm中，中，Sm-1Sm-1保存栈底元素，用栈顶指针保存栈底元素，用栈顶指针 top=mtop=m 表示表示栈空，则栈满的条件是（）。栈空，则栈满的条件是（）。答案：top=029、【填空题】、【填空题】限制在表的一端插入数据、在表的另一端删除数据的线性表是（）。限制在表的一端插入数据、在表的另一端删除数据的线性表是（）。答案：队列30、【填空题】、【填空题】广义表广义表 A=(a,b,c
22、,(e,f,g,h),head(tail(tail(A)=A=(a,b,c,(e,f,g,h),head(tail(tail(A)=（）（）.答案：c31、【填空题】、【填空题】以权值分别为以权值分别为 1,3,5,71,3,5,7 的四个叶子结点构成的哈夫曼树，其带权路径长的四个叶子结点构成的哈夫曼树，其带权路径长度度WPLWPL 是（）。是（）。答案：2932、【填空题】、【填空题】若选用的排序算法不稳定，则关键字相同的两个记录在排序前后的相对次序若选用的排序算法不稳定，则关键字相同的两个记录在排序前后的相对次序（）。（）。答案：不确定33、【填空题】、【填空题】由由 m m 个结点构成的二叉排序树，其可能的最大深度是（）。个结点构成的二叉排序树，其可能的最大深度是（）。答案：m34、【填空题】、【填空题】已知图 G 的邻接表 A 如题图所示。根据 A 中边表的次序，从顶点 v3 出发进行深度优先搜索遍历，得到的深度优先搜索序列是（）。答案：v3,v5,v4,v2,v1
