1、数据结构真题 2013 年 10 月及答案解析(总分：100.01，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.算法的时间复杂度表征的是_ A.算法的可读性 B.算法的难易程度 C.执行算法所耗费的时间 D.执行算法所耗费的存储空间（分数：2.00）A.B.C.D.2.对需要频繁插入和删除结点的线性表，适合的存储方式是_ A.顺序存储 B.链式存储 C.索引存储 D.散列存储（分数：2.00）A.B.C.D.3.在头指针为 head 的循环链表中，判断指针变量 P 指向尾结点的条件是_ A.p-next-next=head B.p-next=head C.p
2、-next-next=NULL D.p-next=NULL（分数：2.00）A.B.C.D.4.迪杰斯特拉(Dijkstra)算法的功能是_ A.求图中某顶点到其他顶点的最短路径 B.求图中所有顶点之间的最短路径 C.求图的最小生成树 D.求图的拓扑排序序列（分数：2.00）A.B.C.D.5.若栈的进栈序列为 1，2，3，4，5，则经过出入栈操作不可能获得的出栈序列是_ A.4，5，3，2，1 B.4，3，5，1，2 C.1，2，3，4，5 D.5，4，3，2，1（分数：2.00）A.B.C.D.6.A 是 74 的二维数组，按行优先方式顺序存储，元素 A00的存储地址为 1000，若每个元
3、素占两个字节，则元素 A33的存储地址为_ A.1015 B.1016 C.1028 D.1030（分数：2.00）A.B.C.D.7.深度为 4 的完全二叉树的结点数至少为_ A.4 B.8 C.13 D.15（分数：2.00）A.B.C.D.8.若采用邻接矩阵 A 存储有向图 G，则结点 k 的入度等于 A 中_ A.结点 k 对应行元素之和 B.结点 k 对应列元素之和 C.结点 k 对应行和列元素之和 D.非零元素之和（分数：2.00）A.B.C.D.9.无向图 G 的邻接矩阵一定是_ A.对称矩阵 B.对角矩阵 C.三角矩阵 D.单位矩阵（分数：2.00）A.B.C.D.10.下列关
4、于有向带权图 G 的叙述中，错误的是_ A.图 G 的任何一棵生成树都不含有回路 B.图 G 生成树所含的边数等于顶点数减 1 C.图 G 含有回路时无法得到拓扑序列 D.图 G 的最小生成树总是唯一的（分数：2.00）A.B.C.D.11.在下列排序算法中，关键字比较次数与初始排列次序无关的是_ A.冒泡排序 B.希尔排序 C.直接插入排序 D.直接选择排序（分数：2.00）A.B.C.D.12.对下图进行拓扑排序，可以得到的拓扑序列是_（分数：2.00）A.B.C.D.13.下列线性表中，能使用二分查找的是 A.顺序存储(2，12，5，6，9，3，89，34，25) B.链式存储(2，12
5、，5，6，9，3，89，34，25) C.顺序存储(2，3，5，6，9，12，25，34，89) D.链式存储(2，3，5，6，9，12，25，34，89)（分数：2.00）A.B.C.D.14.在下列查找方法中，平均查找长度与结点数量无直接关系的是_ A.顺序查找 B.分块查找 C.散列查找 D.基于 B 树的查找（分数：2.00）A.B.C.D.15.下列排序算法中，时间复杂度为 O(nlog2n)的算法是_ A.快速排序 B.冒泡排序 C.直接选择排序 D.直接插入排序（分数：2.00）A.B.C.D.二、B填空题/B(总题数：10，分数：20.00)16.数据的同一种逻辑结构，可以对应
6、多种不同的_。（分数：2.00）填空项 1:_17.若在长度为 n 的顺序表第 i 个元素之前插入一个元素，则需要向后移动的元素个数是_。（分数：2.00）填空项 1:_18.顺序栈存放在 Sm中，S0为栈底，栈顶指针 top 初始值为-1，则栈满的条件是 top=_。（分数：2.00）填空项 1:_19.队列只能在队尾进行插入操作，在队首进行_操作。（分数：2.00）填空项 1:_20.广义表 A=(x，(y，z)，a，b)，则函数 head(laead(tail(A)的值是_。（分数：2.00）填空项 1:_21.以权值分别为 4，3，2，1 的四个叶子结点构成的哈夫曼树，其带权路径长度
7、WPL 是_。（分数：2.00）填空项 1:_22.图的遍历方法有两种，一种是深度优先遍历，另一种是_。（分数：2.00）填空项 1:_23.如果排序算法是稳定的，则关键字相同的两个记录排序前后相对次序_。（分数：2.00）填空项 1:_24.已知散列表表长 m=11，散列函数 h(key)=key%11，表中存有三个关键字 15，27，39，其余地址为空，若采用线性探查法处理冲突，则关键字为 60 的结点保存的地址是_。（分数：2.00）填空项 1:_25.已知图 G 的邻接表如下图所示。 （分数：2.00）填空项 1:_三、B解答题/B(总题数：2，分数：20.00)设 QM是有 M 个元
8、素存储空间的循环队列，若 front 指向队首元素，rear 指向队尾元素的下一位置，请分别用 C 语言描述下列操作。（分数：5.01）(1).将元素 x 入队。（分数：1.67）_(2).将队首元素出队，并保存到变量 y 中。（分数：1.67）_(3).计算当前队列中元素的个数。（分数：1.67）_已知带权图 G=(VE)，其中 V=(A，B，C，D，E)，邻接矩阵如下所列。（分数：15.00）(1).画出对应的图 G。（分数：3.75）_(2).画出图 G 的最小生成树。（分数：3.75）_(3).已知一组待排记录的关键字序列为(15，11，17，59，14，35，13，17，24，84)
9、，请给出对应的小根堆序列。（分数：3.75）_(4).已知二叉树如下图所示，请画出该二叉树的前序线索。 （分数：3.75）_四、B算法阅读题/B(总题数：3，分数：20.00)阅读下列函数并回答问题。typedef struct nodeDataType data; struct node*next; LinkNode;Typedef LinkNode*Linklist; void DeleX(Linklist head, DataType x)LinkNode*p, *q, *s; p=head; q=p-next; while(q!=NULL)if(q-data=x)s=q; q=q-ne
10、xt; free(s); p-next=q; elsep=q; q=q-next; （分数：5.00）(1).执行该函数后，单链表 head 中 data 值为 x 的结点数是多少?（分数：2.50）_(2).该函数的功能是什么?（分数：2.50）_阅读下列函数并回答问题。typedef struct nodeDataType data; struct node*lchild, *rchild; BinTNode; typedef B inTNode*BinTree; void Inorder(BinTree bt)if(bt!=NULL)Inorder(bt-lchild); printf(
11、“%c“, bt-data); Inorder(bt-rchild); （分数：9.99）(1).写出对如下图所示的二叉树执行函数 Inorder 后得到的输出序列。 （分数：3.33）_(2).该函数的功能是什么?（分数：3.33）_(3).下列函数实现直接插入排序，请填写适当内容，使其功能完整。 void f32(int r, int N) int i, j; for(i=2; _; _) r0-ri; j=i-1; while(_) rj+1=rj; j=j-1; rj+1=r0; （分数：3.33）_函数 BinSearch 实现二分查找，请回答下列问题。int BinSearch(S
12、eqList R, KeyType k, int n) int low=0, mid, high=n-1; while(low=high)mid=_; if(Rmid. key=k)return mid; if(Rmid. keyk)high=mid-1; elselow=mid+1; return-1; （分数：5.01）(1).在空白处填写适当内容，使函数功能完整。（分数：1.67）_(2).查找成功时函数的返回值是什么?（分数：1.67）_(3).查找失败时函数的返回值是什么?（分数：1.67）_五、B算法设计题/B(总题数：1，分数：10.00)26.已知： typedef struc
13、t node int data; struct node*next; LinkNode; typedef LinkNode*LinkList; 请编写原型为 int Listisequal(LinkList A, LinkList B)的函数，指针 A、B 分别指向两个带头结点的单链表。函数功能是：若单链表 A、B 中全部对应结点的 data 值相等，则返回 1，否则返回 0。（分数：10.00）_数据结构真题 2013 年 10 月答案解析(总分：100.01，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.算法的时间复杂度表征的是_ A.算法的可读性 B.算
14、法的难易程度 C.执行算法所耗费的时间 D.执行算法所耗费的存储空间（分数：2.00）A.B.C. D.解析：考点 算法的时间复杂度定义 解析 (1)执行算法所耗费的时间，即时间复杂性；(2)执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性；(3)算法应易于理解、易于编程、易于调试等，即可读性和可操作性。因此表征算法时间复杂度的是执行算法耗费的时间，C 正确。2.对需要频繁插入和删除结点的线性表，适合的存储方式是_ A.顺序存储 B.链式存储 C.索引存储 D.散列存储（分数：2.00）A.B. C.D.解析：考点 链式存储方式 解析 应该采用链式存储结构。因为采用链式结构存储线性表，插
15、入和删除操作需要从头结点起查找被插入或删除结点的前驱结点，并修改这些结点的指针域，查找过程平均移动指针域为表长的一半；而采用顺序结构存储线性表，插入和删除操作需要平均移动表中的一半元素。但移动指针域操作比移动元素操作花费的时间少得多。3.在头指针为 head 的循环链表中，判断指针变量 P 指向尾结点的条件是_ A.p-next-next=head B.p-next=head C.p-next-next=NULL D.p-next=NULL（分数：2.00）A.B. C.D.解析：考点 循环链表的特点 解析 循环链表的特点是单链表中最后一个结点(终端结点)的指针域不为空，而是指向链表的头结点，
16、使整个链表构成一个环；循环结束的判断条件不再是 P 或 Pnext 是否为空，而是他们是否等于头指针。因此答案选 B。4.迪杰斯特拉(Dijkstra)算法的功能是_ A.求图中某顶点到其他顶点的最短路径 B.求图中所有顶点之间的最短路径 C.求图的最小生成树 D.求图的拓扑排序序列（分数：2.00）A. B.C.D.解析：考点 迪杰斯特拉(Dijkstra)算法的功能 解析 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算从某个源点到其余各定点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。因此答案为 A。5.若栈的进栈序列为 1，2，3，4，5，则
17、经过出入栈操作不可能获得的出栈序列是_ A.4，5，3，2，1 B.4，3，5，1，2 C.1，2，3，4，5 D.5，4，3，2，1（分数：2.00）A. B.C.D.解析：考点 栈的特点解析 栈是限定仅在表尾进行插入或删除操作的线性表，因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。假设一个栈 S 中的元素为 an，a n-1，a 1，则称 a1为栈底元素，a n为栈顶元素。栈中的元素按 a1，a 2，a n-1，a n的次序进栈。在任何时候，出栈的元素都是栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，因此，栈又称为后进先出(LastI
18、nFirstOut)表，简称为 LIFO 表。A：1 进 2 进 3 进 4 进 4 出 5 进 5 出 3 出 2 出 1 出出栈序列为 45321B：1 进 2 进 3 进 4 进 4 出 3 出 5 进 5 出 2 出 1 出出栈序列为 43521C：1 进 1 出 2 进 2 出 3 进 3 出 4 进 4 出 5 进 5 出出栈序列为 12345D：1 进 2 进 3 进 4 进 5 进 5 出 4 出 3 出 3 出 1 出出栈序列为 54321所以答案选 B。6.A 是 74 的二维数组，按行优先方式顺序存储，元素 A00的存储地址为 1000，若每个元素占两个字节，则元素 A3
19、3的存储地址为_ A.1015 B.1016 C.1028 D.1030（分数：2.00）A.B.C.D. 解析：考点 数组的顺序存储 解析 数组的顺序存储分为行优先存储和列优先存储，数组 Am，n为m 行 n 列的数组，d 为每个元素占的字节数，按行优先顺序存储的二维数组，A0，0是基地址：地址计算公式 LOC(ai，j)=LOC(a00)+in+jd 三维数组 Am，n，p按行优先顺序位于内存中，计算数组元素ai，j，k的地址为 LOC(aij)=LOC(a000)+inp+jp+kd 根据公式带入可知 D 选项正确。7.深度为 4 的完全二叉树的结点数至少为_ A.4 B.8 C.13
20、D.15（分数：2.00）A.B. C.D.解析：考点 完全二叉树 解析 完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 N 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称为完全二叉树。若设二叉树的深度为 h，除第 h 层外，其他各层(1h-1)的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。要想使深度为 4 的完全二叉树节点数最少，那么第一、二、三层的结点数都达到最大，分别为 21-1，22-1，23-1，第四层的结点最多为 24-1，最少为 1，那么整个完全二叉树最少结点数为 8，因此答案选
21、 B。8.若采用邻接矩阵 A 存储有向图 G，则结点 k 的入度等于 A 中_ A.结点 k 对应行元素之和 B.结点 k 对应列元素之和 C.结点 k 对应行和列元素之和 D.非零元素之和（分数：2.00）A.B. C.D.解析：考点 有向图图的邻接矩阵表示法 解析 邻接矩阵是表示图形中顶点之间相邻关系的矩阵，第k 列表示终点为顶点 k 的那些边，非 0 表示这条边存在，入度表示终点为这点的边数之和，即对应列非零元素之和即为结点 k 的入度，因此答案选 B。9.无向图 G 的邻接矩阵一定是_ A.对称矩阵 B.对角矩阵 C.三角矩阵 D.单位矩阵（分数：2.00）A. B.C.D.解析：考点
22、 无向图的邻接矩阵表示法的特点 解析 无向图的邻接矩阵是按主对角线对称的，因此无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称，答案选 A。10.下列关于有向带权图 G 的叙述中，错误的是_ A.图 G 的任何一棵生成树都不含有回路 B.图 G 生成树所含的边数等于顶点数减 1 C.图 G 含有回路时无法得到拓扑序列 D.图 G 的最小生成树总是唯一的（分数：2.00）A.B.C.D. 解析：考点 图的生成树 解析 采用不同的遍历方法可以得到不同的生成树，从不同的顶点出发进行遍历也可以得到不同的生成树，所以图的生成树不是唯一的，因此答案 D 表述错误。树定义为一个无回路的连通图，因此
23、任何一棵生成树都不含有回路，A 正确。一棵具有 n 个顶点的生成树有仅有 n-1 条边，因此生成树所含的边数等于顶点数减 1，B 正确。在 AOV 网中，若不存在回路(环)，所有的活动才排成一个线性序列，C 正确。11.在下列排序算法中，关键字比较次数与初始排列次序无关的是_ A.冒泡排序 B.希尔排序 C.直接插入排序 D.直接选择排序（分数：2.00）A.B.C.D. 解析：考点 内部排序方法的分析比较 解析 关键字比较次数与记录的初始顺序无关的排序方法是选择排序。 (1)若待排序的一组记录数目 n 较小(如 n50)时，可采用插入排序或选择排序。 (2)若 n 较大时，则应用采用快速排序
24、、堆排序或归并排序。 (3)基待排序记录按关键字基本有序时，则适宜选用直接插入排序或冒泡排序。 (4)当 n 很大，而且关键字位数较少时，采用链式基数排序较好。 (5)关键字比较次数与记录的初始排列顺序无关的排序方法是选择排序。12.对下图进行拓扑排序，可以得到的拓扑序列是_（分数：2.00）A.B. C.D.解析：考点 拓扑排序 解析 拓扑排序方法如下： (1)在从有向图中选择一个没有前驱(即入度为 0)的顶点并且输出。 (2)从网中删去该顶点，并且删去从该顶点发出的全部有向边。 (3)重复上述两步，直至全部顶点均已输出，或者当前图中剩余的顶点中没有前趋(入度为 0)顶点为止。 (4)输出剩
25、余的无前趋结点。 由于结点 a 的入度不为 0，因此首先排除 A，D；b 的入度为 0，输出 b，删除顶点 b 和从该点出发的全部有向边，接着找入度为 0 的结点，此时顶点 a 的入度为 0，而顶点 c 的入度不为 0，因此答案选B。13.下列线性表中，能使用二分查找的是 A.顺序存储(2，12，5，6，9，3，89，34，25) B.链式存储(2，12，5，6，9，3，89，34，25) C.顺序存储(2，3，5，6，9，12，25，34，89) D.链式存储(2，3，5，6，9，12，25，34，89)（分数：2.00）A.B.C. D.解析：考点 二分法查找的使用条件 解析 二分法查找要
26、求查找对象的线性表必须是顺序存储结构的有序表，因此排除 B 和 D，又因为 A 选项中不是有序表，因此答案选 C。14.在下列查找方法中，平均查找长度与结点数量无直接关系的是_ A.顺序查找 B.分块查找 C.散列查找 D.基于 B 树的查找（分数：2.00）A.B.C. D.解析：考点 散列表的查找解析 顺序查找成功的平均查找长度为(n+1)/2，折半查找的平均查找长度为 log2(n+1)-1，分块查找的平均查找长度为(n/s)+s)/2)+1，其中 s 为表分块后每一块的记录个数，可见分块查找不仅与表长 n 有关，还与每一块中的记录个数 s 有关，二叉树查找类似于折半查找，哈希表的平均查
27、找长度不是节点个数n 的函数，而是装填因子的函数，与节点个数无关，只依赖于哈希表的装填因子，因此选 C。15.下列排序算法中，时间复杂度为 O(nlog2n)的算法是_ A.快速排序 B.冒泡排序 C.直接选择排序 D.直接插入排序（分数：2.00）A. B.C.D.解析：考点 内部排序方法的时间复杂度解析 排序算法的时间复杂度和空间复杂度如下所列：*时间复杂度为 O(nlog2n)的排序算法有快速、归并、堆排序，因此答案选 A。二、B填空题/B(总题数：10，分数：20.00)16.数据的同一种逻辑结构，可以对应多种不同的_。（分数：2.00）填空项 1:_ （正确答案：物理结构或存储结构）
28、解析：考点 逻辑结构和物理结构的概念 解析 数据逻辑结构描述的是数据元素之间的逻辑关系，数据结构在计算机中的表示(又称映像)称为数据的物理结构，又称存储结构。数据结构的存储结构是和相应的数据在内存中的物理地址之间的关系有关，而逻辑结构只是描述数据之间的关系，同一种逻辑结构可以用多种物理结构存储，可以采用顺序存储或者链式存储等多种方式。可见，数据的同一种逻辑结构，可以对应多种不同的存储结构。17.若在长度为 n 的顺序表第 i 个元素之前插入一个元素，则需要向后移动的元素个数是_。（分数：2.00）填空项 1:_ （正确答案：n-i+1）解析：考点 顺序表上的基本运算 解析 一般情况下，在第 i
29、(1in)个元素之前插入一个元素时，需将第 n 至第 i 个元素向后移动一个位置，第 n 至第 i 个元素一共是 n-i+1 个元素。18.顺序栈存放在 Sm中，S0为栈底，栈顶指针 top 初始值为-1，则栈满的条件是 top=_。（分数：2.00）填空项 1:_ （正确答案：m-1）解析：考点 栈的顺序存储结构 解析 设顺序栈存放在 S.datamaxsize中，栈底位置是 maxsize-1，栈空的条件 S.top=maxsize，栈满的条件 S.top=0；设顺序栈存放在 S.datamaxsize中，栈底位置是-1，栈空条件是 S.top=-1，栈满条件是 S.top=maxsize
30、-1，由此可得答案为 m-1。19.队列只能在队尾进行插入操作，在队首进行_操作。（分数：2.00）填空项 1:_ （正确答案：删除）解析：考点 队列的定义 解析 队列是一种先进先出(FIFO)的线性表，它只允许在表的一端进行插入，在另一端进行删除；在队列中，允许插入的一端叫做队尾，允许删除的一端称为对首。20.广义表 A=(x，(y，z)，a，b)，则函数 head(laead(tail(A)的值是_。（分数：2.00）填空项 1:_ （正确答案：(y，z)）解析：考点 广义表的基本运算解析 广义表一般记作：LS=(a 1，a 2，a n)其中 LS 是广义表的名称，n 是它的长度，a i可
31、以是单个元素也可是广义表，分别称为原子和子表，当广义表非空时，称第一个元素 a1为 LS 的表头，称其余元素组成的广义表(a 2，a 3，a n)为表尾。21.以权值分别为 4，3，2，1 的四个叶子结点构成的哈夫曼树，其带权路径长度 WPL 是_。（分数：2.00）填空项 1:_ （正确答案：19）解析：考点 哈夫曼树的带权路径长度 解析 首先 1 与 2 结合生出 3 节点，再选剩下的 3 与刚生成的3 结合生出 6 节点，剩下的 4 小于 6，所以 4，6 结合生出 10 根节点。对新生成的哈夫曼树进行编码，1的路径 000，2 的路径 001，3 的路径 01，4 的路径为 1，因此
32、WPL=1*3+2*3+3*2+4*1=19。22.图的遍历方法有两种，一种是深度优先遍历，另一种是_。（分数：2.00）填空项 1:_ （正确答案：广度优先遍历）解析：考点 图的遍历方法 解析 图的遍历方法一共有两种，分别是深度优先遍历和广度优先遍历。23.如果排序算法是稳定的，则关键字相同的两个记录排序前后相对次序_。（分数：2.00）填空项 1:_ （正确答案：不变）解析：考点 排序算法基本概念 解析 假定在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且 ri 在 rj 之前，而在排序后的序列中，ri 仍在 rj 之
33、前，则称这种排序算法是稳定；否则称其不稳定。因此如果排序算法是稳定的，那么关键字相同的两个记录排序前后的相对次序是不变的。24.已知散列表表长 m=11，散列函数 h(key)=key%11，表中存有三个关键字 15，27，39，其余地址为空，若采用线性探查法处理冲突，则关键字为 60 的结点保存的地址是_。（分数：2.00）填空项 1:_ （正确答案：7）解析：考点 处理冲突的方法解析 H i=(H(key)+di)MODm，i=1，2，k(k=m-1)，其中 H(key)为散列函数，m 为散列表长，d i为增量序列，可有下列三种取法：d i=1，2，3，m-1，称线性探测再散列；d i=1
34、2，-1 2，2 2，-22，3 2，k 2，(km/2)称二次探测再散列；d=伪随机数序列，称伪随机探测再散列；根据散列函数 h(key)=key%11，求得关键字 15，27，39 的散列值分别为 4、5、6，现有关键字 60，散列值为 5，产生冲突，根据线性探测再散列得到地址 6，仍然冲突，再求下一个地址 7，7 的位置为“空”地址，因此应该填入的地址为 7。25.已知图 G 的邻接表如下图所示。 （分数：2.00）填空项 1:_ （正确答案：v1、v4、v3、v5、v2）解析：考点 图的遍历 解析 深度优先搜索(DFS)类似于树的先根遍历。深度优先遍历图的方法是从图中某顶点 v 出发：
35、(1)访问顶点 v；(2)依次从 v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和 v 有路径相通的顶点都被访问；(3)若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历。三、B解答题/B(总题数：2，分数：20.00)设 QM是有 M 个元素存储空间的循环队列，若 front 指向队首元素，rear 指向队尾元素的下一位置，请分别用 C 语言描述下列操作。（分数：5.01）(1).将元素 x 入队。（分数：1.67）_正确答案：(Qrear=(Qrear+1)%m)解析：(2).将队首元素出队，并保存到变量 y 中。（分数：1.67）_正确答案：(y=Q
36、dataQfront Qfront=(Qfront+1)%m)解析：(3).计算当前队列中元素的个数。（分数：1.67）_正确答案：(Qrear-Qfront+m)%m)解析：考点 循环队列已知带权图 G=(VE)，其中 V=(A，B，C，D，E)，邻接矩阵如下所列。（分数：15.00）(1).画出对应的图 G。（分数：3.75）_正确答案：(对应的带权图 G *)解析：(2).画出图 G 的最小生成树。（分数：3.75）_正确答案：(克鲁斯卡尔算法生成的最小生成树： *)解析：考点 最小生成树(3).已知一组待排记录的关键字序列为(15，11，17，59，14，35，13，17，24，84)
37、，请给出对应的小根堆序列。（分数：3.75）_正确答案：(11，14，13，17，15，35，17，59，24，84)解析：考点 堆排序(4).已知二叉树如下图所示，请画出该二叉树的前序线索。 （分数：3.75）_正确答案：(见下图 *)解析：考点 二叉树的线索化四、B算法阅读题/B(总题数：3，分数：20.00)阅读下列函数并回答问题。typedef struct nodeDataType data; struct node*next; LinkNode;Typedef LinkNode*Linklist; void DeleX(Linklist head, DataType x)LinkN
38、ode*p, *q, *s; p=head; q=p-next; while(q!=NULL)if(q-data=x)s=q; q=q-next; free(s); p-next=q; elsep=q; q=q-next; （分数：5.00）(1).执行该函数后，单链表 head 中 data 值为 x 的结点数是多少?（分数：2.50）_正确答案：(0 个)解析：(2).该函数的功能是什么?（分数：2.50）_正确答案：(该函数的功能是删除单链表中值为 x 的节点。)解析：考点 单链表删除操作 解析 在 DeleX()函数中通过 while 循环，依次遍历单链表 head，q 指向当前比较的节点，p 指向当前节点的前一个节点，在判断的过程中，如果当前节点 q 指向的节点 data值等于 x 则首先将 q 后移，然后删除该节点(pnext=q)；如果不相等，则将 p，q 分别后移一个节点。阅读下列函数并回答问题。typedef struct nodeDataType data; struct
