05哈工程数据结构真题

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

1、哈尔滨工程大学05年招收硕士研究生入学考试试题科目名称：数据结构试题编号：429共3页一．判断题（每小题1分，共10分）1．若一个算法中的语句频度之和为T（n）=1024n+4nlogn，则算法的时间复杂度为0（nlogn）2．串是一种特殊的线性表。3．两个栈共享一个向量空间的优点是其中一个栈可用该空间一半或一半以上。4．广义表是非线性数据结构，因为表中的元素可以是子表。5．二叉树的中序序列中，结点A在结点B之前的条件是A是B的祖先。6．若一个有向图的拓扑排序没有包括全部顶点，则说明该图存在有向回路。7．具有几个顶点e条边的无向图，若用邻接矩阵作为存储结构

2、，则求任一顶点的度数的时间复杂度为0（e）.8．哈希法既是一种查找方法，又是一种存储方法。9．希尔排序是属于插入排序的改进方法。10．在单链表上可以实现简单选择排序，但难以实现堆（选择）排序。二．填空题（每小题2分，共20分）1．在字符串S=“structure”中，以t为首字符的子串有——个。2．N阶的下三角阵按行序为主序存储，每个元素占L个单元，若已知首地址为loc(A00),则元素Aij(0≤j≤i≤n-1)的存储地址loc（Aij）为——3．已知一个栈的入栈序列是1，2，3，……，n，其输出序列为P1，P2，P3，……，Pn。若P1=n，则Pi为—

3、—4．已知广义表LS=（a,（b,c,d），e）运用head和tail函数取出LS中的原子b的运算是——1．在一棵具有h层的满三叉树中，结点总数为——2．已知在一棵含有n个结点的树中，只有度为3和度为0的结点，则树中度为0的结点数为——3．设树T的度为4，其中度为1，2，3，4的结点树分别为4，2，1，1，则听众叶子数为——4．在含有20个关键字的4阶B-树中进行查找，至多访问——个结点。5．将m个互为冲突（具有相同的哈希地址）的记录存入哈希表，处理冲突采用伪随机探测法。最多需要探测——次。6．将30个记录分成5块，进行分块查找，平均查找长度是——。三，单

4、选题（每小题2分，共30分）1．算法是指——A．可执行程序。B。问题求解的计算方法。C。系统软件。D。解决问题的有限运算序列。2．从逻辑上可以把数据结构分成——结构。A．动态和静态B．紧凑和非紧凑C．线性和非线性D．内部和外部3．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为——A．0（1）B．0（n）C．0（m）D．0（m+n）4．长度为n（1…n）的顺序循环队列中，front和rear分别指示队首和队尾。判断队列满的条件为——A．rear%n=frontB．front%n+1=rearC．rear%n-1=frontD．rear%n+

5、1=front5．设二叉树有2n个结点，则对于m0个结点的二叉树的先序序列正好相反，则该二叉树一定不是——的二叉树。A．任一结点无左孩子B．任一结点无右孩子C．深度为nD．存在度为2的结点7．二叉树用二叉链表表示，若要将其所有结点的左，右子树相互交换位置，则采用下列——遍历的方法较为合适。A．先序B．中序C．后序D．按层8．对于二叉树的两个结点X和Y，应该选择——两个序列来判断X是否Y的祖先。A．先序和后序B．先序和中序C．中序和后序D．任意两个序列都行9．

6、最小生成树指的是连通图中——A．边数最少的生成树B．顶点相对较少的生成树C．极小连通子图D．所有生成树中权值之和最小的生成树10．具有n个顶点的强连通图至少有——条弧。A．n-1B．nC．2nD．n（n-1）11．对20个有序记录进行折半查找，查找成功的平均查找长度为——A．5B．37/10C．39/10D．41/1012．哈希表长度为m，哈希函数H（K）=K%P，一般来说P应取小于m的最大——A．奇数B．偶数C．素数D．合数13．对动态查找有高效率的查找表组织结构是——A．有序表B．分块有序表C．循环链表DB-树14．当初始数据有序时，不应采用——A．堆

7、排序B．快速排序C．基数排序D．希尔排序15．在n个元素中找出两个最小的元素，当n很大时，采用——方法比较次数较少。A．树型选择排序B．简单选择排序C．归并排序D．快速排序四．综合题（每小题10分，共40分）1．一棵二叉树的先序，中序，后序序列分别如下：（其中有部分结点未显示出来）先序序列：_B_F_ICEH_G中序序列：D_KFIA_EJC_ 后序序列：_K_FBHJ_G_A（1）。将先序，中序，后序序列完整写出来。（2）。画出该二叉树。2．对关键字序列{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec}

8、(1).构造一棵平衡二叉（排序）树（2）。求其查找成功的平均查找长