05哈工程数据结构真题.pdf

可编辑

哈尔滨工程大学

05年招收硕士研究生入学考试试题

科目名称：数据结构试题编号：429共3页

一．判断题（每小题1分，共10分）

1．若一个算法中的语句频度之和为T（n）=1024n+4nlogn，则算法的时间复

杂度为0（nlogn）

2．串是一种特殊的线性表。

3．两个栈共享一个向量空间的优点是其中一个栈可用该空间一半或一半以

上。

4．广义表是非线性数据结构，因为表中的元素可以是子表。

5．二叉树的中序序列中，结点A在结点B之前的条件是A是B的祖先。

6．若一个有向图的拓扑排序没有包括全部顶点，则说明该图存在有向回路。

7．具有几个顶点e条边的无向图，若用邻接矩阵作为存储结构，则求任一

顶点的度数的时间复杂度为0（e）.

8．哈希法既是一种查找方法，又是一种存储方法。

9．希尔排序是属于插入排序的改进方法。

10．在单链表上可以实现简单选择排序，但难以实现堆（选择）排序。

二．填空题（每小题2分，共20分）

1．在字符串S=“structure”中，以t为首字符的子串有——个。

2．N阶的下三角阵按行序为主序存储，每个元素占L个单元，若已知首地址

为loc(A),则元素Aij(0≤j≤i≤n-1)的存储地址loc（Aij）为——

00

精品文档，欢迎下载

可编辑

3．已知一个栈的入栈序列是1，2，3，……，n，其输出序列为P1，P2，P3，……，

Pn。若P1=n，则Pi为——

4．已知广义表LS=（a,（b,c,d），e）运用head和tail函数取出LS中的原

子b的运算是——

5．在一棵具有h层的满三叉树中，结点总数为——

6．已知在一棵含有n个结点的树中，只有度为3和度为0的结点，则树中

度为0的结点数为——

7．设树T的度为4，其中度为1，2，3，4的结点树分别为4，2，1，1，则

听众叶子数为——

8．在含有20个关键字的4阶B-树中进行查找，至多访问——个结点。

9．将m个互为冲突（具有相同的哈希地址）的记录存入哈希表，处理冲突

采用伪随机探测法。最多需要探测——次。

10．将30个记录分成5块，进行分块查找，平均查找长度是——。

三，单选题（每小题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