哈尔滨工程大学 数据结构 2004年招收研究生入学考试试题

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《哈尔滨工程大学 数据结构 2004年招收研究生入学考试试题》，欢迎阅读！

计算机专业课（数据结构）2004 年试题

一．

判断题 ［每题一分，共１０分］

1． 数据的逻辑结构是用户按使用需要而建立的，与实际的 存储形式无关。

2． 顺序存储结构要求联系的存储区域，在存储管理上不够

灵活因此不常用

3． 在链队列中，除了对头指针外，还必须设队尾指针，否

则无法进行队列的插入操作。

4． 用算符优先求表达式的值，应设两个工作栈，分别用来

暂存操作数和运算符。

5． 字符串既不是线形结构，也不是非线形结构。它是一种

特殊的数据结构。

6． 遍历二叉树的非递归算法，可以用栈作辅助空间，也可

以用队列的数据结构

7． 无向图的邻接多重表表示比邻接表表示节省存储空间。 8． 在拓扑排序算法中，暂存入的度为零的顶点可以用栈，

也可以用队列。

9． 顺序查找长度为N的线形表，起平均查找长度大于任何

一棵N个接点的二叉排序树的平均查找长度。 10． 稳定的排序方法优先于不稳定的排序方法，这是因为

稳定的排序方法效率高

二．单项选择题 [每小题2分，共20分] 1． 数据结构具有___-的数据元素的集合

A．性质相同 B.特定关系Ｃ。相互关系D。数据项 ２．顺序存储线形表的插入算法中，当Ｎ个空间已经满时，可申请再增加分配Ｍ个空间若申请失败，则说明系统没有___可分配的存储空间。

Ａ．Ｍ个Ｂ．Ｍ个连续的Ｃ．Ｎ+Ｍ个Ｄ。Ｎ+Ｍ个连续的 ３．五节车厢以编号１２３４５顺序进入铁路调度站［栈］，可以得到――组。

Ａ．３４５１２Ｂ．２４１３５Ｃ．３６４２１Ｄ.１３５２４

４．设广义表Ｌ＝((Ａ，Ｂ)(Ｃ，Ｄ))，Ｈead和Ｔail分别对广义表的取头和取尾操作，则Ｔail［Ｈead］［Ｔail］［Ｌ］］］的结果是___

Ａ．b Ｂ． d Ｃ．(d) Ｄ(c，d)

５．以数组Ａ［］［］。。。。按‘以行序为主’存储，则Ａ［２］ ［４］的首地址为_

Ａ．６０ Ｂ．７２ Ｃ．１２０ Ｄ１５０

６．树用孩子兄弟表示法，每个接点有两个指针域，分别指向‘第一个孩子’‘下一个兄弟’。若指向‘下一个兄弟’的指针有Ｎ个为空，则该树有__非终端点。 Ａ．［Ｎ／２］Ｂ．Ｎ－１Ｃ．ＮＤ.Ｎ+１

７．设哈夫曼编码的长度不超过４，若已对两个字符编码为１和０１，则还可以对__个字符编码。 Ａ．２Ｂ．３Ｃ．４Ｄ５

８．用两种不同的方法构造图的最小生成树，选边的顺序与

选点时输出边的不同，所得到的最小生成树____ Ａ．是相同的Ｂ．是不同的Ｃ．可能是相同的可能是不同 ９．具有Ｎ个关键字的Ｍ阶Ｂ－树，有__个叶子［查找不成功］结点。

Ａ．Ｎ+１Ｂ．Ｎ-１Ｃ．Ｍ*ＮＤ。［Ｍ／２］*Ｎ １０．当一组排记录已经有序时，使用快速排序时的效率与__排序相同

Ａ．选择Ｂ．基数Ｃ．归并Ｄ西尔 二．计算机题［每题６分，共３０分］

１．对有序表进行顺序查找，算法中设置‘监视哨’请分别求出等概率情况查找成功和不成功时的平均长度。

２．将三对角距阵［Ａij ］n*n的三条对角线上的元素逐列存与数组Ａ［１。。。３］［］中，使得Ａ［１］［１］和Ａ［３］［Ｎ］为空，Ａ［Ｕ］［Ｖ］＝Ａij.请给出Ｕ，Ｖ的下标表达式［用ＩＪ来表示］

３．已知一棵５阶４层［根为第一层，叶子为第４层］的Ｂ－树，至少有多少关键字?至多有多撒个关键字?

４．有Ｎ个结点的二叉树进行后序遍历，若在算法中使用栈，则栈中最多时候多少项?最少时多少项?

５．对长度为２Ｋ次方的有序表进行折半查找，最多比较多少次?查找失败平均次数多少?

三．综合题 ［每题８分，共４０分］

１．已知一个表达式的后缀表示为abcd-*+ef/-，请画出该表达式的二叉树使之先序线索化。

２．对关键字序列(44，40，60，11，70，60，55，22，99，88，77，33)平衡二叉树。

３．设哈希表长为11(0……10)，哈希函数为K MOD 11，处理冲突随即探测再散列法，首个随即数为9，请依次将序列(38，82，74，30，X)哈希表

４．对关键字序列(48，39，66，87，75，12，28，52，56，10，23)

５．从顶点D出发，用普里姆(Prim)算法求出最小生成树，并写出选点的次序。

五．算法题[1题16分，2，3题17分]

1．N个结点的二叉树用两个一维数组L[1……N]和R[1….N]存储，L[K]和R[K]分别指示结点K的左孩子和右孩子，0表示空。试写一个算法判别结点U是否是结点V的子孙。 2．设计一个算法，对带表头结点的非空双向链表的非空双向链表，用简单插入排序的方法，使其按结点从小到大链表，设计结点形式为│prior│ data │next│ ,链表头指针为head。要求:作结点的插入而不是交换数据域的值。

3．设一棵分空的二叉排序树用二叉链表表示，bt为根指针，其左子树的结点都小于右子树的结点，请写一算法，从小到大输出所有大与X的叶子结点。结点形式: lchild

data

rchild

本文来源：https://www.wddqxz.cn/598a64d5920ef12d2af90242a8956bec0975a565.html