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

2023-01-14 06:27:14 第一文档网 [ 字体：小中大 ] [

阅读： ] [

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。下载word有问题请添加QQ：admin处理，感谢您的支持与谅解。

【#第一文档网# 导语】以下是®第一文档网的小编为您整理的《哈尔滨工程大学数据结构 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.dywdw.cn/598a64d5920ef12d2af90242a8956bec0975a565.html