石家庄铁道大学2024-2025学年《数据结构》期末试卷（A卷）

石家庄铁道大学2024—2025学年《数据结构》期末试卷（A卷）石家庄铁道大学2024—2025学年《数据结构》期末试卷（A卷）满分：100分考试时长：110分钟一、单项选择题（每题2分，共20分）数组A[0..4,−1..−3,5..7]中含有元素的个数（）

A．55B．45C．36D．16某数在计算机中用8421码表示为011110001001，其真值为（）

A．789B．789HC．1929D．11110001001B下列关于虚拟存储器的论述中，正确的是（）

A．对应用程序员透明，对系统程序员不透明

B．对应用程序员不透明，对系统程序员透明

C．对应用程序员、系统程序员都不透明

D．对应用程序员、系统程序员都透明设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（）个。

A．n-1B．nC．n+1D．n+2数据结构是具有（）的数据元素的集合。

A．性质相同B．特定关系C．相同运算D．数据项下列语句执行次数为（）c

intm=0,i,j;

for(i=1;i<=n;i++)

for(j=1;j<=2*i;j++)

m++;A．n(n+1)B．nC．n+1D．n2

7.在长度为n的顺序表中，向第i个位置插入新元素，需要后移元素个数为（）

A．n−iB．n−i+1C．iD．i−1

8.若进栈序列为1,2,3,4，则不可能得到的出栈序列是（）

A．3,2,1,4B．2,4,1,3C．2,1,4,3D．1,3,2,4

9.一棵含n个结点的完全二叉树，树的高度为（）

A．⌊log2⁡n⌋B．⌊log2⁡n⌋+1

C．⌈log2⁡n⌉D．⌈二、填空题（每空2分，共20分）数据结构三要素：逻辑结构、\\\\\\\\、数据运算。栈是\\\\\\\\的线性表；队列是\\\\\\__的线性表。单链表设置头结点的目的是为了统一\\\\\\__的操作。树的先根遍历等价于对应二叉树的\\\\\\__遍历。无向图邻接矩阵是\\\\\\__矩阵。快速排序最坏时间复杂度\\\\\\\\，平均时间复杂度\\\\\\\\。一棵二叉树叶子结点数为5，度为2的结点数为\\\\\\\\。有序表适合\\\\\\__查找，无序表只能顺序查找。拓扑排序只适用于\\\\\\__图。三、判断题（每题1分，共10分，对打√，错打×）顺序存储结构随机访问效率高，插入删除效率低。（）循环队列可以解决假溢出问题。（）二叉树的叶子结点只能出现在最下一层。（）邻接表存储稀疏图更节省空间。（）冒泡排序是稳定排序。（）中序遍历二叉搜索树，得到递增有序序列。（）哈希查找不需要比较关键字。（）两个栈共享数组空间时，栈底设在数组两端。（）带权路径长度最小的二叉树是哈夫曼树。（）图的深度优先遍历借助队列实现。（）四、简答与计算题（共30分）1.（6分）已知二叉树先序：ABDECF；中序：DBEAFC。画出二叉树，并写出后序序列。

2.（8分）给定关键字序列：23,12,35,8,40,28，散列函数H(k)=k，线性探测解决冲突，构造散列表，并计算平均查找长度。

3.（8分）画出无向图最小生成树（Kruskal算法）。

顶点：{1,2,3,4,5}

边：(1-2,6)、(1-3,1)、(2-3,5)、(2-4,3)、(3-5,2)、(4-5,4)

4.（8分）写出快速排序第一趟划分结果，初始序列：49,38,65,97,76,13,27。五、算法设计题（每题10分，共20分）编写C语言算法，删除单链表中值等于x的所有结点（带头结点）。c

typedefstructLNode{

intdata;

structLNode*next;

}LNode,*LinkList;

voidDelX(LinkListL,intx);编写递归算法，统计二叉树中叶子结点的个数。c

typedefstructBiTNode{

intdata;

structBiTNode*lchild,*rchild;

}BiTNode,*BiTree;

intCountLeaf(BiTreeT);参考答案一、单选1.B2.A3.A4.C5.B

6.A7.B8.B9.B10.B二、填空存储结构（物理结构）先进后出；先进先出表头插入/删除先序对称O(n24二分（折半）有向无环（DAG）三、判断1.√2.√3.×4.√5.√

6.√7.×8.√9.√10.×四、计算题二叉树：

根A，左孩子B，右孩子C；

B左D，右E；C左F。

后序：DEBFCAH(k)=k

H(23)=2，H(12)=5，H(35)=0，H(8)=1，H(40)=5，H(28)=0

散列表：

0:35,28

1:8

2:23

3:空

4:空

5:12,40

查找长度：1,1,1,1,2,2

ASL=(1+1+1+1+2+2)/6=8/6=4/3Kruskal最小生成树总权值：1+2+3+4=10

选中边：1-3(1)、3-5(2)、2-4(3)、4-5(4)基准49，一趟划分结果：

{27,38,13},49,{76,97,65}

序列：27,38,13,49,76,97,65五、算法参考代码1删除所有值为x的结点c

voidDelX(LinkListL,intx)

{

LNode*p=L,*q;

while(p->next!=NULL)

{

if(p->next->data==x)

{

q=p->next;

p->next=q->next;

free(q);

}

else

p=p->next;

}

}2统计叶子结点c

intCountLeaf(BiTreeT)

{