哈工大2024年春季学期。
数据结构与算法试卷。
一、填空题（每空2分，共20分）
1. 在各字符出现的概率相等情况下，等长编码是最优前缀码。
2．设有两个算法在同一机器上运行，其执行时间分别为100n2和2n，要使前者快于后者，n至少为 15 。
3．采用堆排序、快速排序、冒泡排序，对初态有序的表，最省时间的是_ 堆排序 。
4． 设二叉树结点的先根序列为abdecfgh，中根序列为debafchg,则二叉树中叶结点是_ efh__.
5. 用下标从0开始的n个元素的数组实现循环队列时，为实现下标变量m加1后在数组有效下标范围内循环，可采用的表达式是m= (m+1)/n 。
6. 由带权为3，9，4，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为 51 。
7. 对n个记录的表进行选择排序，在最坏情况下所需要进行的关键字的比较次数为 n（n-1）/2 。
8. 任意一个有n个结点的二叉树，已知它有m个叶结点，则度数为2的结点有 m-1 。
9. n个顶点的连通图用邻接矩阵表示时，该矩阵至少。
有 2n-2 个非零元素。
10. 举出两种磁带文件的分类方法： 平衡归并排序、多阶段归并排序。
二、选择题（每题1分，共10分）
1．设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（ c ）。
(a) 40，42，45，55，80，85 (b) 42，40，45，80，55，85
(c) 42，40，55，80，45，85 (d) 42，40，45，85，55，80
2．数据的最小单位是（ a ）。
(a) 数据项 (b) 数据类型 (c) 数据元素 (d) 数据变量。
3．关键路径是aoe网中( b )
a.从始点到终点的最短路径
b.从始点到终点的最长路径。
c.从始点到终点的边数最多的路径
d.从始点到终点的边数最少的路径。
4．下列说法正确的是（ c ）。
a．最小生成树也是哈夫曼树。
b．最小生成树是唯一的。
．对于n 个顶点的连通无向图，prim算法的时间复杂性为o(n2)
d．kruskal 算法比prim算法更适合边稠密的图 （顶点）
5．设栈s和队列q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈s，一个元素出栈后即进入队列q，若6个元素出列的顺序为e2、e4、e3、e6、e5和e1，则栈s的容量至少应该是（ c ）。
(a) 6 (b) 4 (c) 3 (d) 2
6. 将10阶对称矩阵压缩存储到一维数组a中，则数组a的长度最少为（ c ）。
a) 100 (b) 40 (c) 55 (d) 80
7. 若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序结果，则该排序算法只能是( a )。
a. 插入排序 b.冒泡排序 c. 选择排序 d. 二路归并排序。
8. 设哈希表长m＝14，哈希函数h（key）＝key％11。表中已有4个结点：
addr(15)=4，addr(38)=5 ，addr(61)=6 ，addr(84)=7 其余地址为空 。如果用二次探测再散列处理冲突，关键字为49的结点的地址是（ ）
a．8 b .3 c.5 d. 9
9. 有组记录的输入顺序为（46，79，56，38，40，84），则利用堆排序方法建立的初始堆为( c )
a.79，46，56，38，40，80 b .38，40，56，79，46，84
c. 84，79，56，46，40，38 d. 84，56，79，40，46，38
10. 下列叙述中，不符合m阶b树定义要求的是（ d ）
a. 根结点最多有m棵子树 b. 所有叶结点都在同一层上。
c． 各结点内的关键字有序 d. 叶结点之间通过指针链接。
三、简答题（10分）
带权图（权值非负，表示边连接的两个顶点的距离）的最短路径问。
题是找出初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间的存在路径，现有一种解决该问题的方法：
1）设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；
2）选择离u最近的且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v;
3) 重复步骤2），直到u是目标顶点为止。
请问上述方法能否求得最短路径？若可行请证明之；否则，请举例说明。
四、算法设计：栈、队列的存储结构、基本操作可以直接引用（共30分）
1. 设二叉树采用左右链方式存储， 设计一个判断二叉树是否是二叉排序树的算法。（10分）
2. 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次locatenode(l,x)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。
试写出符合上述要求的locatenode运算的算法。(10分)
3. 给定一个无向连通图，写一个算法找出半径最小的生成树（搜索起点作为生成树的根，树的半径定义为从根到叶子的最大距离）。（10分）
2024年哈工大附中入学试卷
数学。一 填空 每题5分，共计40分 1 计算2.25 0.45 1 2 用 这四个数组成一个算式 可以加括号 使所得的结果恰好为50，请写出一个算式 3 在一个三角形中，已知三个内角之比为1 1 2，且这个三角形最长的边长为4 那么这个三角形的面积是 2 4 某正整数加3能被3整除，加4能被4整除...
哈工大机械原理试卷
一。填空题 本大题共7小题，每空1分，共15分 1.按照两连架杆可否作整周回转，平面连杆机构分为和 2.平面连杆机构的角越大，机构的传力性能越好。3.运动副按接触形式的不同，分为和 4 直齿圆柱齿轮正确啮合条件是两齿轮的和分别相等。5.凸轮从动件按其端部的形状可分为从动件 从动件和。从动件动件。6....
01年哈工大高等数学竞赛试卷
考试时间 120分钟试卷总分 100分。一。已知数列，满足，证明 本题满分6分 二。设，且，求常数。本题满分6分 三。设在内有，且，证明在内有。本题满分6分 四。试问 方程总共有几个实根。本题满分7分 五。设函数在连续且非负，证明。本题满分7分 六。设函数在上连续，在内可微，且，证明存在，使得 本题...