有顶点的度数之和等于所有边数的（）倍。
A12
B1
C2
D4
15．下列排序算法中，其中（）是稳定的。
（A）堆排序，冒泡排序
（B）快速排序，堆排序
（C）直接选择排序，归并排序
（D）归并排序，冒泡排序
二、填空题。在题中“”处填上答案。（本大题共7小题，得分每空1分，总计12分）。
1．数据的逻辑结构被分为____________________线性结构_________________________________四种。2．下面程序段中带下画线的语句的执行次数的数量级是___________。fori
ti0imi
第2页，共7页
f浙江科技学院考试试卷
fori
tj0j
j
aijij
3．若用一个大小为6的数组来实现循环队列，且当前rear和fro
t的值
分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear的值
为___________，fro
t的值为____________。
4．一组记录的排序码为48241853162640，采用冒泡排序法进行排序
升序，则第一趟排序需要进行记录交换的次数是__________。
5．给定表（6535038761908170512897275462），用筛选法建
立初始堆大堆，则初始堆表为
。
6．设有
个结点的完全二叉树，如果按照从自上到下、从左到右从1开
始顺序编号，则第i个结点（非根结点）的双亲结点编号为______________，
右孩子结点的编号为_____________。
7已知一有向图的邻接表存储结构如下图：从顶点1出发，深度优先（DFS）
遍历的输出序列是
，
广度优先（BFS）遍历的输出序列是
。
三、程序填空题。在题中“”处填上答案。（本大题共3小
得分题，每空3分，总计18分）1下面程序段的功能实现数据x进栈，要求在下划线处填上正确
的语句。
typedefstructi
ts100i
ttopsqstack
voidpushsqstackstacki
tx

ifstacktopMaxsize1
pri
tf“overflow”
else
____________________
____________________
2下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的
语句。
typedefstruct
odei
tkey
第3页，共7页
f浙江科技学院考试试卷
struct
odelchildstruct
oderchildbitreebitreebstsearchbitreeti
tkiftNULLretur
0elsewhiletNULLiftkeyk
_____________elseiftkeyk
ttlchildelse_____________3下面程序段的功能是实现快速排序的划分算法，请在下划线处填上正确的语句。typedefstructi
tkeyI
foTypeotheri
foRecTypetypedefRecTypeSeqListN1i
tPartitio
SeqListRi
tii
tjRecTypepivotRiwhileijwhileijRjkeypivotkeyjifijRiRjwhile____________________________________iifij_________________________________Ripivotretur
i四、应用题。（共4小r