2021年哈尔滨工程大学-考研数据结构真题-12

1、精编word文档 下载可编辑哈尔滨工程大学试卷 考试科目: 数据结构a 卷 题号 一 二 三 四 五 总分 分数 评卷人 一、 单项选择题（每空1分，共15分） 1、以下数据结构中，从逻辑结构看，（ ）和其他数据结构不同。a树 b字符串 c队列 d栈 2、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。ao(n) o(n) bo(n) o(1) co(1) o(n) do(1) o(1) 3、有六个元素a，b，c，d，e，f的顺序进栈，（ ）不是合法的出栈序列。adefcba bedcbfa cefdbca dedcfba 4、字符串“abcdef”的子串有（ ）个。a19

2、 b2 c21 d22 5、顺序表中插入一个元素，需要平均移动的元素个数为（ ）。a(n-1)/2 bn/2 c(n+1)/2 dn-1 6、非空的单循环链表head的尾结点（由p所指向）满足（ ）。ap-next=null bp=null cp-next=head dp=head 7、若a是中序线索二叉树中的一个结点，且a不为根，则a的前驱为( )。aa的右子树中最右的结点 ba的左子树中最左的结点 ca的右子树中最左的结点 da的左子树中最右的结点 8、如某二叉树有3个叶子结点，有2个结点仅有一个孩子，则该二叉树中有两个孩子的结点数为（ ）。a29 b3 c31 d19 9、二维数组a的每

3、个元素是由8个字符组成的串，其行下标i=,1,9,列下标j=1,2,1。若a按行序为主序存储，元素a87的起始地址与当a按列序为主序存储时的元素（ ）的起始地址相同（设每个字符占一个字节）。aa79 ba68 ca78 da 69 1、图的深度优先遍历算法类似于二叉树的（ ）。a中序遍历 b先序遍历 c后序遍历 d按层遍历 11、在无向图的邻接表存储结构中，结点的个数是图中边个数的（ ）倍。a1 b2 c3 d4 12、下面关于m阶b-树说法正确的是（ ） 每个结点至少有两棵非空子树。树中每个结点至多有m-1个关键字。所有叶子在同一层上。当插入一个数据项引起b树结点分裂后，树长高一层。a b

4、c d 13、判定一个有向图是否存在回路，可以利用( )方法。a求关键路径的方法 b广度优先遍历算法 c求最短路径的dijkstra方法 d拓扑排序 14、有一个长度为17的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数为（ ）。a53/17 b55/17 c57/17 d59/17 15、在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）。a起泡排序 b选择排序 c快速排序 d插入排序 二、 判断题（每空1分，共1分） 1、算法的设计取决于数据的逻辑结构。( ) 2、栈和线性表的区别在于，它们的操作都限制在表的两端进行操作。( )

5、3、稀疏矩阵压缩存储中，一般只采用三元组表示法进行存储。( ) 4、空格串和空串的长度都为。( ) 5、中序线索二叉树中，所有结点的指针域都不为空。( ) 6、为了很方便的插入和删除数据，可以使用双向链表存放数据。（ ） 7、在二叉树排序树中插入一个新结点，总是插入到叶结点下面。( ) 8、无向图所对应的邻接矩阵一定是对称矩阵，有向图所对应邻接矩阵一定是非对称矩阵。( ) 9、（1，12，23，58，46，29，15，22，77）只可能是一趟简单选择排序之后的结果序列。( ) 1、快速排序的速度在所有排序方法中是最快的。( ) 三、 填空题（每空1分，共1分） 1、一个循环队列q入队列时，指针

6、的操作为（队列长度为m）_。2、6层平衡二叉树至少有_个结点。3、广义表a(a),b,(c,(d),e)，取出原子e的操作是_。4、中缀表达式(a*b+(c-d)/e)*f-(g+h)的后缀表达式是_。5、已知二叉树有3个叶子结点，则该二叉树的总结点数至少是_。6、求图的最小生成树有两种算法， 算法适合于求稀疏图的最小生成树。7、有一个1阶对称阵a.9.1，采用压缩存储方式进行存储 (以行序为主序)，首地址为1，则a89的地址是_。8、一棵完全二叉树有311个结点，则其叶子结点个数为_。9、对关键码序列28，16，32，12，6，2，5，72快速排序，一次划分结果 为 。1、n个顶点构成的有向

7、环，最多为_棵最小生成树。四、 应用题（每题7分，共35分） 1、假设一棵二叉树的后序序列为ckhbijgefda，中序序列为cbkhaigjedf。请画出这棵二叉树，并将其转换为对应的森林。2、对以下关键字序列建立哈希表(sun,mon,tue,wed,thu,fri,sat)，哈希函数为h（k）=（关键字中第一个字母在字母表中的序号）mod 7，用线性探测法处理冲突，求构造一个装填因子为.7的哈希表；并分别计算出在等概率情况下查找成功的平均查找长度。3、已知关键字序列r=11,4,3,2,17,3,19，请按算法步骤（1）构造一棵哈夫曼树，并计算出它的带权路径长度wpl。（2）构造一棵二叉

8、排序树，如果对每个关键字的查找概率相同，求查找成功时的平均查找长度asl。4、下图是带权的有向图g的邻接表表示法，求（1）以结点v1出发广度遍历图g所得的结点序列；（2）从结点v1到结点v8的关键路径。5、给出一组关键字zhao，qian，sun，li，zhou，wu，zheng，wang，写出初始建大顶堆的过程（关键字大小比较以字母表顺序为准）。五、算法设计题（每题15分，共3分） 1、设计算法将一个带头结点的单链表la分解为两个具有相同结构的链表lb、lc，其中lb表的结点为la表中值小于零的结点，而lc表的结点为la表中值大于零的结点。（链表的数据域元素类型为整型，要求lb、lc表利用la表的结点） 2、有这样一棵二叉树，用它表示大家族中已婚男子 的父子、夫妻和兄弟三种关系（如图所示），其存 储结构用二