大连理工大学2022年考研数据结构试题.docx

《大连理工大学2022年考研数据结构试题.docx》由会员分享，可在线阅读，更多相关《大连理工大学2022年考研数据结构试题.docx（5页珍藏版）》请在第一文库网上搜索。

1、大连理工大学2023年考研数据结构试题1 .线性表的运算中，挨次存储构造比例链式存储构造好。A.插入B.删除C.按号查找D.按元素值查找2 .此程序的简单度为for(inti=0；i50,m5时，时间简单度的为：A.快速排序B.归并排序C.基数排序D.直接插入排序5 .挨次查找长度为n的挨次表，查找胜利的平均检索长度为A.n8 .n/2C.(n-1)/2D.(n+1)/26 .一颗二叉树，头序序列为ABCDEFG,中序序列为CBDAEGF,后序为A.CDBGFEAB.CDBFGEAC.CDBAGFED.BCDAGFE7 .一颗度为3的树，度为3的节点为三个，度为2的节点为1个,度为1的节点1个

2、，度为O的节点个。A.68 .7C.8D.98 .m阶B-树中，某一节点插入一个新关键字引起裂开，则该节点原有关键字个。A. Im/2IB. Im/21-1C. mD. m-1E. Im/2-IF. |m/21-19 .两个长度为n的递增有序表，合并成一个长度为2n的递增有序表，最少需要进展关键字比拟次。A.1B.n-1C.nD.2n10 .有向图G,n个顶点，邻接矩阵存储于二维数组中，顶点i的度为A. (i=0n-1)AijB. (j=0n-1)AijC. (i=0n-1)Aij+(j=0n-1)AijD. (j=0n-1)(AijAji)二、问答题1. (6)n阶对称阵(aij)nn,采纳

3、压缩存储存放于一维数组FW中，从F0开头存储，给出矩阵的压缩存储方式及任一矩阵元素aij(0=i,jzzn-1)的地址计算公式，并求算m.2. (5)挨次队列如何解决假溢出问题。3. (8)已知一组关键字(10,26,14,25,17,36,37,44,27,34,60)设哈希函数H(x)=x%13,表长m=13,请写出用线性探测法处理冲突构造所得的哈希表。并求出在等概率状况下,查找胜利时的平均检索长度。4. (6)给定一个由n个关键字不同的记录构成的序列，你能否用比2n-3少的比拟次数找出n个元素中的值和最小值？假如有，请描述你的方法。最快需要多少次比拟？(无需写算法)三、用类C语言完成设计1. (15)什么是堆？设计算法判定给定的存于数组r中的n个数据是否为堆。2. (15)设u、V是有向图的两个顶点，设计算法判读有向图中是否存在从顶点u到V的长度为k的简洁路径。要求给出图的存储形式及其类型定义。3. (10)设二叉树以二叉链表形式存放。一颗二叉树的繁茂程度定义为各层节点数的值与树的高度的乘积。试设计一个高效算法，求二叉树的繁茂程度。