2024年4月2日发(作者：说名)

昆明理工大学2014年硕士研究生招生入学考试试题(A卷)

考试科目代码：818 考试科目名称 ：计算机学科专业基础综合

考生答题须知

1． 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。

请考生务必在答题纸上写清题号。

2． 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。

3． 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。

4． 答题时不准使用涂改液等具有明显标记的涂改用品。

数据结构部分

一、选择题: (25题，每题1分，共25分)

1. 从一个具有n个结点单链表中查找其值等于x结点时，在查找成功时，需平均比较

结点数是 。

(A) n (B) n/2 (C) (n-1)/2 (D) (n+1)/2

2. 下面算法的空间复杂度为 。

float aver(float a[n])

{ int j; for (j=n;j<0;j--) printf(“%8.2f”,a[j]); }

(A) O（1） (B) O（log

2

n） (C) O（n） (D) O（n

2

）

3. 在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度

为 。

(A) O(1) (B) O(n) (C) O(n

2

) (D) O(log

2

n)

4. 在一个单链表中，若要删除*p结点的后继结点，则执行 。

(A) p->next=p->next->next;

(B) p->next=p->next->next; free(p->next);

(C) p->next=p->next->next; q=p->next; free(q);

(D) q=p->next; p->next=p->next->next; free(q);

5. 在一个链队列中，f 和 r 分别为队首尾指针，则进行插入s 结点的操作时执行 。

(A)f->next=s;f=s;(B)r->next=s;r=s;(C)s->next=r;r=s; D)s->next=f;f=s;

做了一个入队操作，新节点当做尾结点

6. 从顺序存储的循环队列中删除一个元素时，是 。

(A) 先移动队首指针，后取出元素 (B) 先取出元素，后移动队首指针

7. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点

数为1个，那么度为0的结点数为 个。

(A) 4 (B) 5 (C) 6 (D) 7

树中结点数等于所有结点度数的和加1

8. 在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶结点数为 个。

(A) 15 (B) 16 (C) 17 (D) 47 15+1

9. 一棵二叉树结点数为18个，则其最小高度为 ，其最大高度为 。

(A) 4,16 (B)5,18 (C) 6,18 (D) 3,18 log2(18)+1

10. 一棵三叉树结点数为50个，则其最小高度为 。

(A) 3 (B) 4 (C) 5 (D) 6

第 1 页 共 7页

昆明理工大学2014年硕士研究生招生入学考试试题

11. 由分别带权为9，2，5，7的四个叶结点构造一棵哈夫曼树，则该树的带权路径长度

是 。

(A) 23 (B)37 (C) 44 (D) 46

12. 已知10个数据元素（54，28，16，34，73，62，95，60，26，43），按照依次插入结点

的方法生成一棵二叉排序树后，则查找值为62的结点所需比较的次数是3；在查找成功

的情况下，查找每个元素的平均比较次数（又称平均查找长度，即查找每个元素时平均

比较的结点数）为 。

(A) 2.5 (B)3.2 (C) 2.6 (D) 2.9

13. 在一个无向图中，所有顶点的度数之和等于所有边数的 倍。

(A) 1/2 (B) 1 (C) 2 (D) 4

14. 有n个顶点的无向图中，要连通全部顶点至少需要 条边。

(A) n (B) (n+1) (C) (n-1) (D) n/2

15. 有n个顶点和e条边的无向图中，若采用邻接表表示，则表头向量的大小为 条边。

(A) n (B) (n+1) (C) (n-1) (D) n/2

16. 在有向图的邻接表中，每个顶点的邻接表链接着该顶点的所有 邻接点；在有向图的

逆邻接表中，每个顶点的邻接表链接着该顶点的所有 邻接点；

(A) 出边，入边 (B) 入边，出边

17. 对于一个具有n个顶点e条边的的图，若采用边集数组表示，则边集数组中的单元数至少

为 个。

(A) n (B) n+e (C) e (D) 2e

1

18. 如图1所示，若从顶点V1出发按广度优先搜索法进行遍历可能得

到的一种顶点序列是 。

3

2

(A) V1,V2,V5,V3,V6,V7,V4

(B) V1,V5,V2,V4,V3,V7,V6 图1

(C) V1,V2,V5,V4,V3,V7,V6

4

(D) V1, V5,V2,V3,V7,V6,V4

19. 如图2所示，在该图的最小生成树中，各边上权值之和是 ；

在该图的最小生成树中，从点V1到点V6的路径是 。

(A) 31 , (V1,V3,V4,V6)

(B) 36 , (V1,V3,V4,V6)

1

(C) 38 , (V1,V4,V6) 图2

8

(D) 43 , (V1,V4,V3,V6)

4

已选定点里离目标定点最近的

20. 如图3所示，该图得到的一种拓扑序列为 。

(A) (V1,V4,V6,V2,V5,V3)

(B) (V1,V2,V3,V4,V5,V6)

（C) (V1,V4,V2,V3,V6,V5) 图3

(D) (V1,V2,V4,V6,V3,V5)

第 2 页 共 7页

5

6

7

12

5

6

4

6

3

8

9

15

10

2

20

5

1

4

2

5

6

3

(1)、找到一个没有后继的顶点(如果有一条边从A指向B,那么B是A的后继)。

(2)、从图中删除这个顶点，在列表的前面插入顶点的标记。

(3)、重复步骤1和2.直到所有的顶点都从图中删除。这时列表显示的顶点顺序就是拓扑排序的结

果。

昆明理工大学2014年硕士研究生招生入学考试试题

第 3 页 共 7页

21. 在对长度为n的顺序存储的有序表进行二分查找时，对应的二分查找判定树的高度

为 。

(A) n (B) log

2

n (C) log

2

(n+1) (D) log

2

(n+1)

22. 顺序查找一个具有n个元素的线性表，其时间复杂度为 ，二分查找为一个具有n个

元素的线性表，其时间复杂度为 。

(A) O(n),O(log

2

n) (B)O(log

2

n),O(log

2

n)

(C) O(n

2

),O(n) (D) O(nlog

2

n),O(log

2

n)

二分查找好比二叉树里树的层数

23. 已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当二分查找值

为90的元素时， 次比较后查找成功；当二分查找值为47的元素时， 次比较

后查找成功。

(A) 1，4 (B) 2，4 (C) 3，2 (D) 4，2

根据二分法查找的查找过程，首先将90与表中中间的元素50进行比较，由于90大于50，

所以在线性表的后半部分查找。第二次与比较的元素是后半部分的中间元素，即90，这时两

者相等，即查找成功。

24. 在顺序存储的线性表A[30]上进行顺序查找的平均查找长度为 。

(A) 15 (B) 15.5 (C) 16 (D) 20 （n+1）/2

25. 已知一个线性表为（38，25，74，63，52，48），假定采用H（K）=K mod 7计算散列地

址进行散列存储时，若利用线性探测的开放定地址法处理冲突，则在该散列表上进行查

找的平均查找长度为 ；若利用链接法处理冲突，则在该散列表上进行查找的平均查

找长度为 。

(A) 1.5,1 (B) 1.7,3/2 (C) 2,4/3 (D) 2.3,7/6

二、综合应用题：(2题，每题25分，共50分)

1. 中缀表达式中，如果不规定运算符的优先级又不加括号，则运算结果不唯一；后缀表达

式中，不规定运算符的优先级又不需括号，就能得到唯一的运算结果。现以中缀表达式：

（8+3*6）/（2+3*5-4）为例，回答如下问题：

1) 利用什么原理实现中缀表达式转换成后缀表达式？（5分）

栈的数据结构

2) 写出中缀表达式转换成后缀表达式的算法思想。（10分）

3) 用上中缀表达式为例，图示表现出其转换成后缀表达式的过程及结果。（10分）

转换方法，对公式字符串进行逐位判断。遇到公式中的变量直接输出，运行符入栈。

入栈时，比较栈顶运算符与入栈运算符的高低，再行出栈和入栈。

中缀表达式转后缀表达式遵循以下原则：

1.遇到操作数，直接输出；

2.栈为空时，遇到运算符，入栈；

3.遇到左括号，将其入栈；

4.遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，

左括号不输出；

5.遇到其他运算符'+''-''*''/'时，弹出所有优先级大于或等于该运算符的栈顶

元素，然后将该运算符入栈；

6.最终将栈中的元素依次出栈

第 4 页 共 7页

2024年4月2日发(作者：说名)

昆明理工大学2014年硕士研究生招生入学考试试题(A卷)

考试科目代码：818 考试科目名称 ：计算机学科专业基础综合

考生答题须知

1． 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。

请考生务必在答题纸上写清题号。

2． 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。

3． 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔），用其它笔答题不给分。

4． 答题时不准使用涂改液等具有明显标记的涂改用品。

数据结构部分

一、选择题: (25题，每题1分，共25分)

1. 从一个具有n个结点单链表中查找其值等于x结点时，在查找成功时，需平均比较

结点数是 。

(A) n (B) n/2 (C) (n-1)/2 (D) (n+1)/2

2. 下面算法的空间复杂度为 。

float aver(float a[n])

{ int j; for (j=n;j<0;j--) printf(“%8.2f”,a[j]); }

(A) O（1） (B) O（log

2

n） (C) O（n） (D) O（n

2

）

3. 在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度

为 。

(A) O(1) (B) O(n) (C) O(n

2

) (D) O(log

2

n)

4. 在一个单链表中，若要删除*p结点的后继结点，则执行 。

(A) p->next=p->next->next;

(B) p->next=p->next->next; free(p->next);

(C) p->next=p->next->next; q=p->next; free(q);

(D) q=p->next; p->next=p->next->next; free(q);

5. 在一个链队列中，f 和 r 分别为队首尾指针，则进行插入s 结点的操作时执行 。

(A)f->next=s;f=s;(B)r->next=s;r=s;(C)s->next=r;r=s; D)s->next=f;f=s;

做了一个入队操作，新节点当做尾结点

6. 从顺序存储的循环队列中删除一个元素时，是 。

(A) 先移动队首指针，后取出元素 (B) 先取出元素，后移动队首指针

7. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点

数为1个，那么度为0的结点数为 个。

(A) 4 (B) 5 (C) 6 (D) 7

树中结点数等于所有结点度数的和加1

8. 在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶结点数为 个。

(A) 15 (B) 16 (C) 17 (D) 47 15+1

9. 一棵二叉树结点数为18个，则其最小高度为 ，其最大高度为 。

(A) 4,16 (B)5,18 (C) 6,18 (D) 3,18 log2(18)+1

10. 一棵三叉树结点数为50个，则其最小高度为 。

(A) 3 (B) 4 (C) 5 (D) 6

第 1 页 共 7页

昆明理工大学2014年硕士研究生招生入学考试试题

11. 由分别带权为9，2，5，7的四个叶结点构造一棵哈夫曼树，则该树的带权路径长度

是 。

(A) 23 (B)37 (C) 44 (D) 46

12. 已知10个数据元素（54，28，16，34，73，62，95，60，26，43），按照依次插入结点

的方法生成一棵二叉排序树后，则查找值为62的结点所需比较的次数是3；在查找成功

的情况下，查找每个元素的平均比较次数（又称平均查找长度，即查找每个元素时平均

比较的结点数）为 。

(A) 2.5 (B)3.2 (C) 2.6 (D) 2.9

13. 在一个无向图中，所有顶点的度数之和等于所有边数的 倍。

(A) 1/2 (B) 1 (C) 2 (D) 4

14. 有n个顶点的无向图中，要连通全部顶点至少需要 条边。

(A) n (B) (n+1) (C) (n-1) (D) n/2

15. 有n个顶点和e条边的无向图中，若采用邻接表表示，则表头向量的大小为 条边。

(A) n (B) (n+1) (C) (n-1) (D) n/2

16. 在有向图的邻接表中，每个顶点的邻接表链接着该顶点的所有 邻接点；在有向图的

逆邻接表中，每个顶点的邻接表链接着该顶点的所有 邻接点；

(A) 出边，入边 (B) 入边，出边

17. 对于一个具有n个顶点e条边的的图，若采用边集数组表示，则边集数组中的单元数至少

为 个。

(A) n (B) n+e (C) e (D) 2e

1

18. 如图1所示，若从顶点V1出发按广度优先搜索法进行遍历可能得

到的一种顶点序列是 。

3

2

(A) V1,V2,V5,V3,V6,V7,V4

(B) V1,V5,V2,V4,V3,V7,V6 图1

(C) V1,V2,V5,V4,V3,V7,V6

4

(D) V1, V5,V2,V3,V7,V6,V4

19. 如图2所示，在该图的最小生成树中，各边上权值之和是 ；

在该图的最小生成树中，从点V1到点V6的路径是 。

(A) 31 , (V1,V3,V4,V6)

(B) 36 , (V1,V3,V4,V6)

1

(C) 38 , (V1,V4,V6) 图2

8

(D) 43 , (V1,V4,V3,V6)

4

已选定点里离目标定点最近的

20. 如图3所示，该图得到的一种拓扑序列为 。

(A) (V1,V4,V6,V2,V5,V3)

(B) (V1,V2,V3,V4,V5,V6)

（C) (V1,V4,V2,V3,V6,V5) 图3

(D) (V1,V2,V4,V6,V3,V5)

第 2 页 共 7页

5

6

7

12

5

6

4

6

3

8

9

15

10

2

20

5

1

4

2

5

6

3

(1)、找到一个没有后继的顶点(如果有一条边从A指向B,那么B是A的后继)。

(2)、从图中删除这个顶点，在列表的前面插入顶点的标记。

(3)、重复步骤1和2.直到所有的顶点都从图中删除。这时列表显示的顶点顺序就是拓扑排序的结

果。

昆明理工大学2014年硕士研究生招生入学考试试题

第 3 页 共 7页

21. 在对长度为n的顺序存储的有序表进行二分查找时，对应的二分查找判定树的高度

为 。

(A) n (B) log

2

n (C) log

2

(n+1) (D) log

2

(n+1)

22. 顺序查找一个具有n个元素的线性表，其时间复杂度为 ，二分查找为一个具有n个

元素的线性表，其时间复杂度为 。

(A) O(n),O(log

2

n) (B)O(log

2

n),O(log

2

n)

(C) O(n

2

),O(n) (D) O(nlog

2

n),O(log

2

n)

二分查找好比二叉树里树的层数

23. 已知一个有序表为（12，18，24，35，47，50，62，83，90，115，134），当二分查找值

为90的元素时， 次比较后查找成功；当二分查找值为47的元素时， 次比较

后查找成功。

(A) 1，4 (B) 2，4 (C) 3，2 (D) 4，2

根据二分法查找的查找过程，首先将90与表中中间的元素50进行比较，由于90大于50，

所以在线性表的后半部分查找。第二次与比较的元素是后半部分的中间元素，即90，这时两

者相等，即查找成功。

24. 在顺序存储的线性表A[30]上进行顺序查找的平均查找长度为 。

(A) 15 (B) 15.5 (C) 16 (D) 20 （n+1）/2

25. 已知一个线性表为（38，25，74，63，52，48），假定采用H（K）=K mod 7计算散列地

址进行散列存储时，若利用线性探测的开放定地址法处理冲突，则在该散列表上进行查

找的平均查找长度为 ；若利用链接法处理冲突，则在该散列表上进行查找的平均查

找长度为 。

(A) 1.5,1 (B) 1.7,3/2 (C) 2,4/3 (D) 2.3,7/6

二、综合应用题：(2题，每题25分，共50分)

1. 中缀表达式中，如果不规定运算符的优先级又不加括号，则运算结果不唯一；后缀表达

式中，不规定运算符的优先级又不需括号，就能得到唯一的运算结果。现以中缀表达式：

（8+3*6）/（2+3*5-4）为例，回答如下问题：

1) 利用什么原理实现中缀表达式转换成后缀表达式？（5分）

栈的数据结构

2) 写出中缀表达式转换成后缀表达式的算法思想。（10分）

3) 用上中缀表达式为例，图示表现出其转换成后缀表达式的过程及结果。（10分）

转换方法，对公式字符串进行逐位判断。遇到公式中的变量直接输出，运行符入栈。

入栈时，比较栈顶运算符与入栈运算符的高低，再行出栈和入栈。

中缀表达式转后缀表达式遵循以下原则：

1.遇到操作数，直接输出；

2.栈为空时，遇到运算符，入栈；

3.遇到左括号，将其入栈；

4.遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，

左括号不输出；

5.遇到其他运算符'+''-''*''/'时，弹出所有优先级大于或等于该运算符的栈顶

元素，然后将该运算符入栈；

6.最终将栈中的元素依次出栈

第 4 页 共 7页