黑龙江省2010年专升本考试试题分析(包括英语、高数、数据结构)考试原题讲解

计算。

思路是把前两项作为一项a，sin3x作为b，再利用函数乘积的求导法则。当算完内部再计算a内的乘积求导，最后写出展开后大答案即可。 3.求

?301dx

x?1?x?四、综合题：17’

2用y?x及y?x所围图形的面积及旋转一周后所得体积。

1 6五．证明：10’

x当x?0时，证明不等式e?1?ln?1?x?。

思路：利用函数的单调性。

第三章 数据结构

数据结构整体上看试卷一共分为五道大题，一是单项选择题共计10道20分；二是填空题10道20分；三是简答，4道 20分；四是应用题3道18分；五是算法设计，2道22分；总计100分。

试题分析 一 单项选择：20’

1.稀疏矩阵的压缩方法有两种，即（ ） A.二维数组和三维数组 B.三元组和散列 C．三元组和十字链表 D.散列和十字链表 2.深度为6的完全二叉树至多有（ ）个结点。

A．60 B.61 C.63 D.64

3.在有n个叶子结点的哈夫曼树中，其所有结点的总数为（ ）. A不确定 B.n-1 C.2n D.2n-1

4.长度为n的顺序存储的线性表，当任何位置上删除一个元素的概率相等时，插入一个元素所需移动的平均个数为（ ）。 A. (n+1)/2 B.(n-2)/2 C.n/2 D.（n-1）/2

5.判别一个表达式中括号是否模式匹配的过程，需要使用的数据结构是（）。

A．二叉树 B.栈 C. 队列 D.线性链表 6.什么排序与比较次数无关（）。

7类似给定二叉树的中序序列为BDCEAFHG和后序序列DECBHGFA，求前序序列是( ). 8.不记得了 9.不记得了 10．不记得了

二．填空：20’

1.给定二维数组A[1][1] 的存储地址为1000，若每个元素占用4个存储单元，求A[1][4]的存储地址为( ). 2.n个结点的无向图最多有（ ）条边。

3.对有序表（16，20，23，34，48，55.60.78）用二分查找法查找55，所需的比较次数为（ ）。

4.连通分量指的是无向图中的（ ）. 5.哈希表的装填因子?定义为?=

表中元素个数?越小发生冲突的可，

表长能性越小，而?越大，发生冲突的可能性就越大，那么装填因子的值应（ ?1 ）。

6.无向图的邻接矩阵是一个（对称）矩阵。

7.给定一组数据{7,5,2,4}以它构造一颗哈夫曼树，则带权路径长度wpl的值为（ 35）。

8.堆可以表示为一棵（完全二叉树）。 9.不记得了 10.不记得了 三．简答：20’

1．给定循环链表，用两种方法表示栈满和栈空，请简要回答？ 2.图有哪四种存储结构，各适应什么样的图？

3.AOE网的活动即使再提高速度也会受到限制，为什么？ 4.什么是二叉排序树？ 四．应用题：

1.给定序列{45，62，35，77，92，55，14，25，40，72}用快速排序

法和归并排序各写出排序后的一趟结果。 2.

施

工

路

线

问

题

：

假

定

给

定

了

p1>p2,p1>p3,p3>p5,p5>p7,p4>p7,p3>p6,p6>p7等等，问怎么施工的。 3.给定结点位置，要把哪个结点插入到哪，此题就是让写出插入指定结点的语句。 五．算法设计：22’ 1.按层遍历二叉树的结点。

2.折半查找的算法，给定从v[0]至v[n].