2016年武汉科技大学856数据结构(C语言版)考研真题(A卷)

(总分：150.00，做题时间：180分钟)

一、选择题(总题数：10，分数：20.00)

1.以下说法正确的是（ ）。（分数：2.00）

A.数据元素是数据的最小单位 B.数据项是数据的基本单位

C.数据结构是带有结构的各数据项的集合

D.一些表面上很不相同的数据可以有相同的逻辑结构 √ 解析：

2.在顺序表（长度为 127）中插入一个元素平均要移动（ ）个元素。（分数：2.00） A.8 B.63.5 √ C.63 D.7 解析：

3.若完全二叉树的结点总数为 1001，则度为 1 的结点有（ ）个。（分数：2.00）

A.0 √ B.1 C.500 D.501 解析：

4.二叉树先序遍历 x 在 y 之前，后序遍历 x 在 y 之后，则 x 是 y 的（ ）。（分数：2.00）

A.左兄弟 B.右兄弟 C.祖先 √ D.后裔 解析：

5.二叉树在线索化后，仍不能有效求解的问题是（ ）。（分数：2.00）

A.前序线索二叉树中求前序后继 B.中序线索二叉树中求中序后继 C.中序线索二叉树中求中序前驱 D.后序线索二叉树中求后序后继 √

解析：

6.下列关于 AOE 网的叙述中，不正确的是（ ）。（分数：2.00）

A.某些关键活动提前，则整个工程将会提前完成 √ B.任一关键活动提前，则整个工程将会提前完成 C.所有关键活动提前，则整个工程将会提前完成 D.关键活动不按期完成会影响整个工程的完成时间 解析：

7.12 个数据有序顺序存储，采用二分查找，查找失败时的 ASL 值是（ ）。（分数：2.00）

A.37/12 B.63/13 C.39/12 D.49/13 √ 解析：

8.二叉查找树的查找效率与二叉树的（ ）有关。（分数：2.00） A.高度 B.结点的多少 C.树型 √ D.结点的位置 解析：

9.用函数 H(k)=key%17 构造散列表，则链地址法解决冲突需（ ）个链表。（分数：2.00）

A.17 √ B.13 C.16 D.任意 解析：

10.在快速排序过程中，下列结论正确的是（ ）。（分数：2.00）

A.左、右两个子表都已各自排好序 B.左边的元素都不大于右边的元素 √ C.左边子表长度小于右边子表长度 D.左、右两边元素的平均值相等 解析：

二、填空题(总题数：10，分数：20.00)

11.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它 们之间的（ ）等的学科。（分数：2.00）

填空项1:__________________ （正确答案： 关系和操作 ） 解析：

12.在单链表（长度为 n）给定值 x 的结点后插入新结点的时间复杂度为（

填空项1:__________________ （正确答案： O(n) ） 解析：

13.判断表达式中左右括号是否配对的算法采用（ ）数据结构最佳。（分数：

填空项1:__________________ （正确答案： 栈 ） 解析：

14.设广义表 L=((a,b,c))，则 L 的长度为（ ）。（分数：2.00）

填空项1:__________________ （正确答案： 1 ） 解析：

15.由 4 个结点可以构造出（ ）种不同的二叉树。（分数：2.00）

填空项1:__________________ （正确答案： 14 ） 解析：

）。（分数：2.00） 2.00） 16.用数组 A[0…n-1]存储完全二叉树，则 A[i]的右子女是结点（ ）。（分数：2.00）

填空项1:__________________ （正确答案： A[2i+2] ） 解析：

17.在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。（分数：2.00）

填空项1:__________________ （正确答案： 2 ） 解析：

18.为了实现图的广度优先搜索，除了一个标志数组标志已访问的结点外，还需 （ ）存放被访问的结点以实现遍历。（分数：2.00）

填空项1:__________________ （正确答案： 队列 ） 解析：

19.求图中一个顶点到其它各个顶点最短路径的算法是（ ）算法。（分数：2.00）

填空项1:__________________ （正确答案： Dijkstra ） 解析：

20.具有 12 个记录的序列，采用冒泡排序最少的比较次数是（ ）。（分数：2.00）

填空项1:__________________ （正确答案： 11 ） 解析：

三、综合应用题(总题数：7，分数：70.00)

将三对角矩阵 A[1..n，1..n]的非零元素逐行存放于数组 B[0..3n-3]中，使 得 B[k］=A[i，j］，求：（分数：10）

(1).用 i，j 表示ｋ的变换公式（分数：5）

__________________________________________________________________________________________ 正确答案：( k=2i+j-3 ) 解析：

(2).用ｋ表示 i，j 的变换公式（分数：5）

__________________________________________________________________________________________ 正确答案：(

i=(k+1)/3+1 j=(k+1)/3+(k+1)%3 ) 解析：

设二叉树的顺序存储结构如下：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 e a f d g c j h i b （分数：10.0） (1).画出该二叉树的逻辑结构（分数：2.5）

__________________________________________________________________________________________ 正确答案：(

) 解析：

(2).写出其先序、中序、后序序列（分数：2.5）

__________________________________________________________________________________________ 正确答案：( 先序：eadcbjfghi

中序：abcdjefhgi 后序：bcjdahigfe ) 解析：

(3).画出其后序线索二叉树（分数：2.5）

__________________________________________________________________________________________ 正确答案：(

) 解析：

(4).把它转换成对应的森林（分数：2.5）

__________________________________________________________________________________________ 正确答案：(

) 解析：

给定序列（26,25,20,33,21,24,45,204,42,38,29,31），要用散列法进行存储， 散列函数采用除留余数法，用线性探测法解决冲突，负载因子为 0.6。（分数：10） (1).设计哈希函数（分数：3）

__________________________________________________________________________________________ 正确答案：( 散列函数 H(k)=k%19 ) 解析：

(2).画出哈希表（分数：3）

__________________________________________________________________________________________ 正确答案：(

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 38 20 21 42 24 25 23 45 29 31 33 204 1 1 1 1 1 1 1 2 1 1 1 2 ) 解析：

(3).计算等概率情况下查找成功和失败的平均查找长度（分数：4）

__________________________________________________________________________________________ 正确答案：( 成功：ASL=14/12=7/6

不成功：ASL=(4+3+2+1+6+5+4+3+2+1+2+1+2+1+3+2+1+1+1+1)/20=46/20=2.3 ) 解析：

对有序表(31,34,45,57,,70,72,84,88,91,97,105,124)折半查找，要求（分数：10.0） (1).画出描述折半查找过程的判定树；（分数：2.5）

__________________________________________________________________________________________ 正确答案：(

) 解析：

(2).若查找元素 91，需依次与那些元素比较?（分数：2.5）

__________________________________________________________________________________________ 正确答案：( 72、91 ) 解析：

(3).若查找元素 30，需依次与那些元素比较?（分数：2.5）

__________________________________________________________________________________________ 正确答案：( 72、45、31 ) 解析：

(4).分别求等概率情况下查找成功和不成功时的平均查找长度。（分数：2.5）

__________________________________________________________________________________________ 正确答案：(

查找成功的平均查找长度：（1+2*2+4*3+6*4）/13=41/13 不成功时的平均查找长度：(2*3+12*4)/14=/14=27/7 ) 解析：

已知关键字序列（40，35，61，87，72，16，25，50），（分数：10） (1).写出用快速排序方法升序排列该序列一趟后的结果（分数：2）

__________________________________________________________________________________________ 正确答案：(

快速排序一趟后的结果：25 35 16 40 72 87 61 50 ) 解析：

(2).写出用堆排序进行升序排列时的初始堆（分数：2）

__________________________________________________________________________________________ 正确答案：(

堆排序进行升序初始堆：87 72 61 50 40 16 25 35 ) 解析：

(3).写出堆排序 1 趟以后（交换与调整之后）的结果（分数：2）

__________________________________________________________________________________________ 正确答案：(

堆排序 1 趟以后的结果：72 50 61 35 40 16 25 87 ) 解析：

(4).写出 1 趟冒泡排序后的结果（分数：2）

__________________________________________________________________________________________ 正确答案：(

1 趟冒泡排序后的结果：35 40 61 72 16 25 50 87

) 解析：

(5).写出 1 趟归并排序后的结果（分数：2）

__________________________________________________________________________________________ 正确答案：(

1 趟归并排序后的结果：35 40 61 87 16 72 25 50 ) 解析：

有以下 AOE 网：

（分数：10.0）

(1).求各事件的最早/迟发生时间（分数：2.5）

__________________________________________________________________________________________ 正确答案：(

事件 最早发生时间 最迟发生时间 ) 解析：

V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 0 15 10 65 50 80 160 190 220 250 270 0 15 15 65 205 80 160 205 220 250 270 (2).求各活动的最早/迟开始时间（分数：2.5）

__________________________________________________________________________________________ 正确答案：(

活动 a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10a a11 a12 a13 a14 e 1 ) 解析：

(3).给出其关键路径（分数：2.5）

__________________________________________________________________________________________ 正确答案：(

关键路径：a1->a3->a5->a9->a10->a12->a13 ) 解析：

10 0 0 15 10 65 10 80 190 80 160 50 220 250 190 15 0 5 15 57 65 165 95 205 80 160 205 220 250 210 (4).其拓扑序列共有多少种（分数：2.5）

__________________________________________________________________________________________ 正确答案：( 12 ) 解析：

分别用 Prim 和 kruskal 算法构造最小生成树。（需标示每一步构造过程）

（分数：10.00）

__________________________________________________________________________________________ 正确答案：(

) 解析：

四、算法设计(总题数：3，分数：40.00)

22.设计算法，在不带头结点的单链表 L 上实现删除 data 域值为 x 的所有结点， 返回删除结点的个数； int List_Delete（struct LNode *L，KeyType x）（分数：10.00）

__________________________________________________________________________________________ 正确答案：(

) 解析：

23.采用链式存储实现栈的操作（数据元素类型为 ElemType），包括栈的初始化 InitStack、入栈 Push、出栈 Pop、取栈顶元素 Peek、判栈空 Empty、清空栈 ClearStack 以及返回栈中元素个数 GetLen 等操作，并作简单注释。（分数：15.00）

__________________________________________________________________________________________ 正确答案：(

) 解析：

24.根据给定的 n 个权值可以构造一颗哈夫曼树。若哈夫曼树采用顺序存储结构， 每个结点的数据结构采用如下格式。 Typedef struct

｛ unsigned int weight; //结点的权值

unsigned int parent,lchild,rchild;//分别存放双亲、左右孩子的下标 ｝Huffman; 试设计如下算法 CreatHuffman，根据给定的 n 个权值构造一颗哈夫曼树。 void CreatHuffman(Huffman HT[], int n, int w[]); 其中：HT 为构造的哈夫曼树，n 表示权值个数，w 用来存储所有权值 下图是根据权值 7，5，2，4 所构造出来的哈夫曼树（-1 表示空）。

（分数：15.00）

__________________________________________________________________________________________ 正确答案：(

) 解析：