哈尔滨工程大学-考研数据结构真题-9.doc

《哈尔滨工程大学-考研数据结构真题-9.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、班级：学号：姓名：装订线哈尔滨工程大学试卷考试科目:数据结构A卷题号一二三四五总分分数评卷人一、单项选择题（每空1分，共15分）1.以下数据结构中，哪一个是线性结构（）A．广义表B．二叉树C．稀疏矩阵D．串2.有六个元素按6，5，4，3，2，1的顺序进栈，下列哪一个是合法的出栈序列？（）A．642531B．451326C．346521D．4312563.链式存储结构中，存储单元的地址（）。A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续4.对于栈，操作数据的原则是（）。A．先进先出B．不分顺序C．后进后出D．后进

2、先出5、有一个二维数组A[1:6，0:7]，每个数组元素用相邻的6个字节存储，存储器按字节编址，若按列存储，则A[5，7]的第一个字节的地址是（）。A．42B．276C．282D．2346、广义表（a,(b,c),d,e）的表头是（）。A．aB．a,（b,c）C．（a,（b,c））D．（a）7、算术表达式a+b*（c+d/e）转为后缀表达式后为（）。A．ab+cde/*B．abcde/+*+C．abcde/*++D．abcde*/++8、一棵二叉树高度为h，所有结点的度或为0或为2，则这棵二叉树最少有()个结点。A．2hB．2h

3、-1C．2h+1D．h+19、对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用()次序的遍历实现编号。A．先序B．中序C．后序D．按层次遍历10、一棵二叉树的先序遍历序列为ABCDEFG，它的中序遍历序列可能是（）。A．CABDEFGB．ABCDEFGC．DACEFBGD．ADBCFEG11、一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在

4、数组A中的位置是（）A．A[2i](2i<=n)B．A[2i+1](2i+1<=n)C．A[i-2]D．条件不充分，无法确定12、一个n个顶点的连通无向图，其边的个数至少为（）。A．n-1B．nC．n+1D．nlogn13、下列关于AOE网的叙述中，不正确的是（）。A．关键活动不按期完成就会影响整个工程的完成时间B．任何一个关键活动提前完成，那么整个工程将会提前完成C．所有的关键活动提前完成，那么整个工程将会提前完成D．某些关键活动提前完成，那么整个工程将会提前完成14、下面关于折半查找的叙述正确的是()。A．表必须有序，表可以

5、顺序方式存储，也可以链表方式存储C．表必须有序，而且只能从小到大排列B．表必须有序且表中数据必须是整型，实型或字符型第5页共6页第6页共6页班级：学号：姓名：装订线D．表必须有序，且表只能以顺序方式存储15、在下列排序算法中，（）算法的时间复杂度与初始排序无关。A．直接插入排序B．起泡排序C．快速排序D．直接选择排序一、判断题（每空1分，共10分）1、数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的储存结构。()2、对任何数据结构，链式存储结构一定优于顺序存储结构。()3、栈与队列是一种特殊操作的线性表。()4、若一个

6、广义表的表头为空表，则此广义表亦为空表。()5、二叉树是度为2的有序树。()6、非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子。()7、一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。()8、一个网（带权图）都有唯一的最小生成树。()9、就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。()10、快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。()二、填空题（每空1分，共10分）1、已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：________。2、循环队列

7、用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是_______。3、两个字符串相等的充分必要条件是_______。4、设二维数组A[0..30,1..20]，每个元素占有4个存储单元，存储起始地址为200。如按行优先顺序存储，则元素A[25,18]的存储地址为_______。5、若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为_______。6、设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为_______。7、G是一个非连通无向图

8、，共有28条边，则该图至少有______个顶点。8、在有序表A[1..12]中，采用二分查找算法查等于A[5]的元素，所比较的元素下标依次为__________。9、一棵4阶4层（根为第一层，叶子为第四层）的B-树，最多有个__________关键字。10、快速