还剩5页未读,继续阅读
文本内容:
哈尔滨工程大学考研数据结构真题12哈尔滨工程大学___考试科目:数据结构A卷题号一二三四五总分分数评卷人
一、单项选择题(每空1分,共15分)
1、以下数据结构中,从逻辑结构看,()和其他数据结构不同A.树B.字符串C.队列D.栈
2、对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为()A.OnOnB.OnO1C.O1OnD.O1O
13、有六个元素A,B,C,D,E,F的顺序进栈,()不是合法的出栈序列A.DEFCBAB.EDCBFAC.EFDBCAD.EDCFBA
4、字符串“ABCDEF”的子串有()个A.19B.20C.21D.
225、顺序表中插入一个元素,需要平均___的元素个数为()A.n-1/2B.n/2C.n+1/2D.n-
16、非空的单循环链表head的尾结点(由P所指向)满足()A.p-next==NULLB.p==NULLC.p-next==headD.p==head
7、若A是中序线索二叉树中的一个结点,且A不为根,则A的前驱为A.A的右子树中最右的结点B.A的左子树中最左的结点C.A的右子树中最左的结点D.A的左子树中最右的结点
8、如某二叉树有30个叶子结点,有20个结点仅有一个孩子,则该二叉树中有两个孩子的结点数为()A.29B.30C.31D.
199、二维数组A的每个元素是由8个字符组成的串,其行下标i=01…9列下标j=12…10若A按行序为主序存储,元素A
[8]
[7]的起始地址与当A按列序为主序存储时的元素()的起始地址相同(设每个字符占一个字节)A.A
[7]
[9]B.A
[6]
[8]C.A
[7]
[8]D.A
[6]
[9]
10、图的深度优先遍历算法类似于二叉树的()A.中序遍历B.先序遍历C.后序遍历D.按层遍历
11、在无向图的邻接表存储结构中,结点的个数是图中边个数的()倍A.1B.2C.3D.
412、下面关于m阶B-树说___确的是()
①每个结点至少有两棵非空子树
②树中每个结点至多有m-1个关键字
③所有叶子在同一层上
④当插入一个数据项引起B树结点___后,树长高一层A.
①②③B.
②③④C.
②③D.
③
13、判定一个有向图是否存在回路,可以利用方法A.求关键路径的方法B.广度优先遍历算法C.求最短路径的Dijkstra方法D.拓扑排序
14、有一个长度为17的有序表,按折半查找法对该表进行查找,在表内各元素等概率情况下,查找成功所需的平均比较次数为()A.53/17B.55/17C.57/17D.59/
1715、在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是()A.起泡排序B.选择排序C.快速排序D.插入排序
二、判断题(每空1分,共10分)
1、算法的设计取决于数据的逻辑结构
2、栈和线性表的区别在于,它们的操作都限制在表的两端进行操作
3、稀疏矩阵压缩存储中,一般只采用三元组表示法进行存储
4、空格串和空串的长度都为
05、中序线索二叉树中,所有结点的指针域都不为空
6、为了很方便的插入和删除数据,可以使用双向链表存放数据()
7、在二叉树排序树中插入一个新结点,总是插入到叶结点下面
8、无向图所对应的邻接矩阵一定是对称矩阵,有向图所对应邻接矩阵一定是非对称矩阵
9、(10,12,23,58,46,29,15,22,77)只可能是一趟简单选择排序之后的结果序列
10、快速排序的速度在所有排序方法中是最快的
三、填空题(每空1分,共10分)
1、一个循环队列Q入队列时,指针的操作为(队列长度为m)________
2、6层平衡二叉树至少有________个结点
3、广义表Aabcde,取出原子e的操作是________
4、中缀表达式A*B+C-D/E*F-G+H的后缀表达式是________
5、已知二叉树有30个叶子结点,则该二叉树的总结点数至少是________
6、求图的最小生成树有两种算法,算法适合于求稀疏图的最小生成树
7、有一个10阶对称阵A[
0..9][
1..10],采用压缩存储方式进行存储以行序为主序,首地址为100,则A
[8]
[9]的地址是________
8、一棵完全二叉树有311个结点,则其叶子结点个数为________
9、对关键码序列28,16,32,12,60,2,5,72快速排序,一次划分结果为
10、n个顶点构成的有向环,最多为________棵最小生成树
四、应用题(每题7分,共35分)
1、假设一棵二叉树的后序序列为CKHBIJGEFDA,中序序列为CBKHAIGJEDF请画出这棵二叉树,并将其转换为对应的森林
2、对以下关键字序列建立哈希表SUNMONTUEWEDTHUFRISAT,哈希函数为H(K)=(关键字中第一个字母在字母表中的序号)MOD7,用线性探测法处理冲突,求构造一个装填因子为
0.7的哈希表;并分别计算出在等概率情况下查找成功的平均查找长度
3、已知关键字序列R={11432173019},请按算法步骤
(1)构造一棵哈夫曼树,并计算出它的带权路径长度WPL
(2)构造一棵二叉排序树,如果对每个关键字的查找概率相同,求查找成功时的平均查找长度ASL
4、下图是带权的有向图G的邻接表表示法,求
(1)以结点V1出发广度遍历图G所得的结点序列;
(2)从结点V1到结点V8的关键路径
5、给出一组关键字{zhao,qian,sun,li,zhou,wu,zheng,wang},写出初始建大顶堆的过程(关键字大小比较以字母表顺序为准)
五、算法设计题(每题15分,共30分)
1、设计算法将一个带头结点的单链表LA分解为两个具有相同结构的链表LB、LC,其中LB表的结点为LA表中值小于零的结点,而LC表的结点为LA表中值大于零的结点(链表的数据域元素类型为整型,要求LB、LC表利用LA表的结点)
2、有这样一棵二叉树,用它表示大家族中已婚男子的父子、夫妻和兄弟三种关系(如图所示),其存储结构用二叉链表存储,请编写一个查找任意父亲结点值为X的所有___的算法结点结构如下typedefstructBiTNode{TElemTypedata;structBiTNode*lchild*rchild;}BiTNode*BiTree;模板内容仅供参考。