2023年上海海洋大学 信息管理与信息系统《数据结构与算法》期末A卷（真题+标准答案）

2023年上海海洋大学信息管理与信息系统《数据结构与算法》期末A卷（含答案）满分100分｜考试时长110min｜适用：信管本科一、单项选择题（每题2分，共30分，15小题）1、有一个100×90的稀疏矩阵，非0元素有10个，每个int占2字节，三元组存储占用字节（）

A.60B.66C.18000D.33

答案：B

解析：三元组每项（行、列、值）3个int=6B，10个非零：10×6=60；再加矩阵行列总数2个int=6B，合计66B。2、O(nlogn)、稳定排序（）

A.快排B.堆排C.归并排序D.直接插入

答案：C快排、堆排序不稳定；直接插入O(n²)3、链表不具备的特点（）

A.增删无需移动元素B.随机存取C.不用预分配空间D.空间随长度变化

答案：B4、动态分区内存管理常用分配算法不包含（）

A.最先适配B.最优适配C.最坏适配D.哈希分配

答案：D5、栈和队列共同点（）

A.随机存取B.先进先出C.限定端点插入删除D.先进后出

答案：C6、串S="ababaa"，KMP模式串next数组首下标从0开始，next值（）

A.-1,0,0,1,2,1B.0,1,1,2,3,2C.-1,0,1,2,0,1D.以上都错

答案：A7、深度优先遍历二叉树用到的数据结构（）

A.栈B.队列C.数组D.哈希表

答案：A；广度优先→队列8、n个顶点无向连通图最小生成树边数（）

A.nB.n-1C.n+1D.2n

答案：B9、哈希查找冲突解决，开放寻址法不包括（）

A.线性探测B.二次探测C.链地址法D.伪随机探测

答案：C（链地址是拉链法，不属于开放寻址）10、关键字序列{35,22,78,90,12,66}，二分查找66，比较次序（）

A.35,78,66B.90,78,66C.35,90,66D.22,78,66

答案：A11、二叉树叶子结点是度（）的结点

A.=0B.=1C.=2D.≥0

答案：A12、若频繁存取第i元素及前后结点，最优存储（）

A.单链表B.顺序表C.单向循环链表D.链栈

答案：B13、AOE网关键路径（）

A.路径最短B.路径最长C.边最少D.顶点最少

答案：B14、快速排序在最坏时间复杂度（）

A.O(n)B.O(nlogn)C.O(n²)D.O(logn)

答案：C（有序序列最坏）15、带权叶子{2,5,6,8}构造哈夫曼树WPL（）

A.38B.35C.42D.32

答案：A；构造：2+5=7→7+6=13→13+8=21；WPL=7×2+13×2+8×1=38二、填空题（每空1分，共20分）1.数据结构三要素：逻辑结构、存储结构、数据运算。

2.循环队列判满条件：(rear+1)%MaxSize==front。

3.一棵二叉树n0=12，n2=5，则n1=6；公式：n0=n2+1，总节点n=n0+n1+n2。

4.图两种存储：邻接矩阵、邻接表；遍历：DFS深度优先、BFS广度优先。

5.直接插入排序最好时间复杂度O(n)，最坏O(n²)。

6.串U="xyxyxyxxyxy",t="xxy"，INDEX(S,t)=7（下标从1开始）。

7.单链表px指向x结点，py为新y结点，x后插入y：

py->next=px->next;px->next=py;

三、判断题（每题1分，共10分，对√错×）1.栈是先进先出（×，栈LIFO，队列FIFO）

2.完全二叉树可以用数组顺序存储（√）

3.哈希表平均查找和表长无关（×，装填因子影响查找效率）

4.有向图拓扑排序唯一（×，拓扑序列不唯一）

5.中序遍历二叉搜索树得到升序序列（√）

6.三元组只能存稀疏矩阵（√）

7.链式栈没有栈满溢出问题（√，动态分配）

8.归并排序空间复杂度O(n)（√）

9.空二叉树高度为0（√）

10.平衡二叉树左右子树高度差≤1（√）四、程序填空（每空2分，共20分）1.递归逆序整数存入字符数组c

voidRev(intnum,chars[],int&k){

if(num==0)return;

s[k++]=____①____;

Rev(num/10,s,k);

}①：num%10+'0'2.快速排序非递归栈实现（节选）c

#defineMAXN100

intstack[MAXN],top=-1;

voidQuickSort(inta[],intl,intr){

stack[++top]=r;stack[++top]=l;

while(top!=-1){

inti=____②____,j=stack[top--];

intmid=Partition(a,i,j);

if(mid+1<j){stack[++top]=j;stack[++top]=mid+1;}

if(i<mid-1){stack[++top]=mid-1;stack[++top]=i;}

}

}②：stack[top--]3.统计二叉树叶子结点c

intCountLeaf(BiTreeT){

if(T==NULL)return0;

if(T->lchild==NULL&&T->rchild==NULL)

return____③____;

returnCountLeaf(T->lchild)+CountLeaf(T->rchild);

}③：1五、简答与应用题（共20分）1、简答（6分）：简述顺序表与链表优缺点答案：

顺序表：

优点：随机存取、存取O(1)、存储密度高；

缺点：插入删除O(n)、预分配空间易浪费/溢出。

链表：

优点：动态分配、头尾插入删除O(1)；

缺点：无法随机访问、额外存储指针、存储密度低。2、排序演算（7分）：关键字{49,38,65,97,76,13,27}，写出冒泡排序第一趟、直接选择排序第一趟结果冒泡一趟：38,49,65,76,13,27,97（最大值97沉底）简单选择一趟：13,38,65,97,76,49,27（最小13交换首元素）3、构造哈夫曼树（7分）：权{5,3,7,2,9}，画图+计算WPL构造步