一判断题(每小题一分，共十分)
1 数据结构，数据元素，数据项在计算机中的映象（表示）分别称为存储结构，结点，数据域。 对。
2 线性表的逻辑顺序与存储顺序总是一致的。 错。
3 广义表的表头或是元素或是一个广义表，而表尾总是一个广义表。 对。
4 拓扑排序是一种内部排序的算法。 错。
5 字符串是一种特殊的线性表，其特殊性体现在数据元素是一个字符。 对。
6 若线索二叉树有n个结点，则必有n+1条不空的指向树中结点的线索。 错。
7 稀疏矩阵的压缩存储方法一般有三元组和十字链表两种。 对。
8 在aoe网中，一定有不止一条关键路径。 错。
9 二维数组是其数据元素为线性表的线性表。 对。
10 一个栈的输入序列是12345，则输出序列43512是可能的。 错。
二单项选择（每小题2分，共20分）
1 数据结构从逻辑上可以分成线性和非线性两种结构。
2 哈希（hash）法查找的基本思想是根据关键字值来决定记录的存储位置。
3 利用栈求表达式（（a-b）-c）-(d-(e-f)),操作数栈须有 4 项。
4 图的广度优先搜索算法类似于二叉树的按层遍历操作。
5 在所有排序方法中关键字比较次数与记录初始排列次序有关的是插入排序。
6 二维数组a的行下标从1到8，列下标从1到10，若每个元素占3个单元，则该数组按“以列序为主序”存放时，a[5][8]的起始位置是 180
7 表达式a*(b+c)-d的后缀表示（逆波兰式）是 abc+*d－
8 在一个具有n个结点的单链表中查找，查找成功时需要平均计较 (n+1)/2 结点。
9 设q[0……n-1]为循环队列，front,rear分别为队列的头，尾，则队列中的元素个数为 (rear-front+n) mod n
10 在各种查找方法中，平均查找长度与结点个数无关的查找方法是二叉树查找。
三计算题（每小题6分，共30分）
1 一颗树有n1个度为1的结点，n2个度为2的结点………nm个度为m的结点，求：该树中终端（叶）结点的个数n0
2 对长度为12的有序表进行折半查找，求查找成功与不成功时各平均比较次数。
3 已知一颗3阶的b－树中含有25个关键字，求该b－树的最小高度和最大高度（不包含叶子层）
4 已知一棵平衡二叉树的深度为6，求树中最少可能的结点数和最多可能的结点数。
5 对n个结点的平衡二叉树，请分别求出当二叉树具有最小深度k和最大深度k时，第k层上的结点数。
四综合题 （每小题8分，共40分）
1 广义表a＝((a),(b,(c,d,e)),请写出其链式存储结构。设链表中有两类结点，表结点形式为 tag=1 hp tp ,其中指针hp和tp分别指向表头。
和表尾，元素（原子）结点形式为 tag＝0 元素值
2 对关键字序列（49，38，65，97，75，13，27，51，55，10）进行希尔排序。若排序三趟，各趟的增量分别为 d1=5 ,d2=3 ,d3=1 ，则请写出每趟的结果及元素移动次数。
3 电文中使用字符a,b,c,d,e,f,他们出现的频率为（4,7,5,2,9,8）,请画出对应的编码哈夫曼树，并求出传送电文的总长度。
4 已知一棵二叉树的中序序列为dajfbgicehk，后序序列为dafbjcikheg,请画出该二叉树，并使其成为先序线索树。
5 对于加权图
用克鲁斯卡尔(kruskal)方法构造最小生成树，并写出选边的次序。
五算法题 （1，2小题各13分，3，4小题各12分，共50分）
1 设用二叉链表表示的二叉树不空，其根指针为root，结点形式为：
lchild data rchild
请写出将二叉树中所有结点的左，右子树相互交换的非递归算法。
2 利用两个栈s1和s2来模拟一个队列。若不存在栈溢出问题，则请写出用栈的操作来实现队列的插入和删除的算法。
3 设计一个算法，在长度为n的（小顶）堆r[1………n]中删除一个元素r[s]（s<=n）产生一个长度为n－1的(小顶)堆，并将r[s]存放于r[n]中。
4 假设循环单链表不空，且无表头结点亦无表头指针，指针p指向链表中某结点。请设计一个算法，将p所指节点的前驱结点变为p所指结点的后继结点。
答案：三、计算题（每小题6分，共30分）
m1．n0=1 + i-1)*ni)
i=22．查找成功平均比较次数：37/12
查找不成功平均比较次数：49/13
3．最小高度：3 最大高度：4
4．最少结点数：20 最多结点数：63
5．最小深度时：n+1-2k-1 最大深度时：1
四、综合题（每小题8分，共40分）
1．a0 d 0 a
0 c 0 b
2．第1趟：13 27 51 55 10 49 38 65 97 76 移动5次。
第2趟：13 10 49 38 27 51 55 65 97 76 移动3次。
第3趟：10 13 27 38 49 51 55 65 76 97 移动5次。
3． 电文总度：87
哈尔滨工程大学招生目录
010材料科学与化学工程学院 联系 82518793 080501材料物理与化学01熔盐物理化学。02纳米材料及纳米技术03功能材料与微结构表征。101思想政治理论 201英语一 202俄语 203日语任选其一 302数学二。820材料科学基础。101思想政治理论 201英语一 202俄语 203日...
2024年哈尔滨工程大学自主招生自荐信
尊敬的哈工大自主招生领导 您好！我是 高三学生 我希望通过贵校的自主招生来实现我在哈尔滨工程大学学习的梦想，感谢您在百忙中抽出时间审阅我的自荐信，以下是我的自我介绍。哈工程作为一所 211工程 重点建设的工科高校，其雄厚的工科实力自然不言而喻，尤其是她 三海一核 船舶工业 海军装备 海洋开发以及核能...
2024年哈尔滨工程大学机械设计试卷答案
机械设计a卷答案及评分标准 02级 一 是非题 正确的在 中写 t 错误的在 中写 f 本大题分20小题，每小题1分，共20分 1 f 2 t 3 f 4 t 5 f 6 f 7 t 8 f 9 t 10 f 11 f 12 f 13 t 14 t 15 t 16 t 17 f 18 f 19 f ...