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

石家庄铁道大学2023-2024学年《数据结构》期末试卷（A卷）石家庄铁道大学2023-2024学年《数据结构》期末试卷（A卷）满分：100分考试时间：110分钟一、单项选择题（每题2分，共20分）1．下面关于对图的操作的说法不正确的是（）

A．寻找关键路径是关于带权有向图的操作

B．寻找关键路径是关于带权无向图的操作

C．连通图的生成树不一定是唯一的

D．带权无向图的最小生成树不一定是唯一的2．采用（）不会产生内部碎片。

A．分页式存储管理

B．分段式存储管理

C．固定分区式存储管理

D．段页式存储管理3．在双向循环链表中，在p指针所指向的结点前插入一个指针q所指向的新结点，其修改指针的操作是（）

A．p↑.llink：=q；q↑.rlink：=p；p↑.llink↑.rlink：=q；q↑.llink：=q；

B．p↑.llink：=q；p↑.llink↑.rlink：=q；q↑.rlink：=p；q↑.llink:=p↑.llink；

C．q↑.rlink：=p；q↑.llink：=p↑.llink；p↑.llink↑.rlink：=q;p↑.llink：=q;

D．q↑.llink:=p↑.llink；q↑.rlink:=p；p↑.llink：=q；p↑.llink：=q；4．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）

A．都不相同

B．完全相同

C．先序和中序相同，而与后序不同

D．中序和后序相同，而与先序不同5．下列选项中，不可能在用户态发生的事件是（）

A．系统调用

B．外部中断

C．进程切换

D．缺页6．快速排序方法在（）情况下最不利于发挥其长处。

A．要排序的数据量太大

B．要排序的数据中含有多个相同值

C．要排序的数据个数为奇数

D．要排序的数据已基本有序7．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是（）排序。

A．冒泡

B．希尔

C．快速

D．堆8．（）在其最好情况下的算法时间复杂度为O(n)。

A．插入排序

B．归并排序

C．快速排序

D．堆排序9．下列因素中，不会影响信道数据传输速率的是（）

A．信噪比

B．频率宽带

C．调制速率

D．信号传播速度10．以下叙述不正确的是（）

A．后序线索二叉树是不完善的，要对它进行遍历，不需使用栈

B．任何一棵二叉树的后序线索树进行后序遍历时都必须使用栈

C．任何一棵二叉树都可以不用栈实现先序线索树的先序遍历

D．任何一棵二叉树都可以不用栈实现中序线索树的中序遍历二、填空题（每空2分，共20分）11．将下三角矩阵A[1..8，1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占2个单元，则元素A[7，8]的地址为\\\\\\\\。12．如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为\\\\\\\\。13．二叉树结点的对称序序列为A，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E，则该二叉树结点的前序序列为\\\\\\\\，该二叉树对应的树林包括\\\\\\__棵树。14．Prim（普里姆）算法适用于求\\\\\\\\的网的最小生成树；Kruskal（克鲁斯卡尔）算法适用于求\\\\\\__的网的最小生成树。15．已知广义表A=((（a，b），（c），（d，e）))，head（tail（tail（head（A））））的结果是\\\\\\\\。三、应用题（每题10分，共30分）16．数组A中，每个元素A[i，j]的长度均为32个二进位，行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求：

（1）存放该数组所需多少单元？

（2）存放数组第4列所有元素至少需多少单元？

（3）数组按行存放时，元素A[7，4]的起始地址是多少？

（4）数组按列存放时，元素A[4，7]的起始地址是多少？17．一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：

（1）各层的结点的数目是多少？

（2）编号为n的结点的双亲结点（若存在）的编号是多少？

（3）编号为n的结点的第i个孩子结点（若存在）的编号是多少？

（4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？18．含9个叶子结点的3阶B-树中至少有多少个非叶子结点？含10个叶子结点的3阶B-树中至多有多少个非叶子结点？四、程序填空题（每空3分，共15分）19．以下函数实现单链表的初始化，补全代码。c

voidInitLinkList(LinkList*L)

{

*L=(LinkList)malloc(sizeof(LNode));

(*L)->next=（1）______;

(*L)->data=（2）______;//头节点数据域存储链表长度，初始为0

}20．对单链表中元素按插入方法排序的C语言描述算法，L为链表头结点指针。c

typedefstructnode{

intdata;

structnode*next;

}linknode,*link;

voidInsertsort(linkL)

{

linkp,q,r,u;

p=L->next;（1）______;

while(（2）________)

{

r=L;q=L->next;

while(q!=p&&q->data<=p->data)

{

r=q;q=q->next;

}

u=p->next;

（3）________;

r->next=p;

p=u;

}

}五、算法设计题（15分）21．编写算法，在一棵二叉排序树中查找值为x的结点，若查找成功，返回该结点地址；若查找失败，则插入值为x的新结点，并返回新结点地址。参考答案一、单选题BBCBCDCADB二、填空题下三角矩阵只存储i≥j元素，A[7,8]属于上三角，不存储；若题目改为严格下三角，该元素不保存。如果题目印刷为A[8,7]，地址计算结果：1062。二叉树n0=20，n2=n0-1=19；总结点=20+30+19=69。前序序列：EACBDGF；树林数目：1。Prim：稠密图；Kruskal：稀疏图。head(tail(tail(head(A))))=(d,e)。三、应用题解析：每个元素32bit=2个字，行：-1\9共11行，列：1\11共11列。

(1)总单元数：11×11×2=242

(2)第4列共11个元素，单元：11×2=22

(3)行优先：LOC=S+((7-(-1))×11+(4-1))×2=S+182

(4)列优先：LOC=S+((7-1)×11+(4-(-1)))×2=S+146满K叉树结论：

(1)第i层结点数：Ki−1

(2)双亲：⌊(n−2)/K⌋+1

(3)第i个孩子：K(n−1)+i+1

3阶B树（2-3树）：9个叶子，最少非叶结点：410个叶子，最多非叶结点：8四、程序填空(1)NULL(2)0(1)L->next=NULL

(2)p!=NULL

(3)p->next=q五、算法题（C语言）c

BSTNode*SearchInsert(BiTree&T,intx)

{

if(!T)

{

T=(BSTNode*)malloc(sizeof(BSTNode));

T->data=x;

T->lchild=T->rchild=NULL;