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

时间:2023-01-14 06:27:13 阅读: 最新文章 文档下载
说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。
计算机专业课(数据结构)2004 年试题

一.

判断题 [每题一分,共10分]

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

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

灵活因此不常用

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

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

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

暂存操作数和运算符。

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

特殊的数据结构。

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

以用队列的数据结构

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

也可以用队列。

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

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

稳定的排序方法效率高

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

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

A.M个B.M个连续的C.N+M个D。N+M个连续的 3.五节车厢以编号12345顺序进入铁路调度站[栈]可以得到――组。

A.34512B.24135C.36421D.1352

4.设广义表L=((A,B)(C,D)),Head和Tail分别对广义表的取头和取尾操作,则Tailead[Tail[L]的结果是___

A.b B. d C.(d) (cd)

5.以数组A[][]‘以行序为主’存储,则A[2] [4]的首地址为_

A.60 B.72 C.120 D150

6.树用孩子兄弟表示法,每个接点有两个指针域,分别指向‘第一个孩子’‘下一个兄弟’。若指向‘下一个兄弟’的指针有N个为空,则该树有__非终端点。 A.[N/2]B.N-1C.ND.+

7.设哈夫曼编码的长度不超过4,若已对两个字符编码为1和01,则还可以对__个字符编码。 A.2B.3C.4D5

8.用两种不同的方法构造图的最小生成树,选边的顺序与

选点时输出边的不同,所得到的最小生成树____ A.是相同的B.是不同的C.可能是相同的可能是不同 9.具有N个关键字的M阶B-树,有__个叶子[查找不成功]结点。

A.N+1B.N-1C.M*ND。[M/2]* 10.当一组排记录已经有序时,使用快速排序时的效率与__排序相同

A.选择B.基数C.归并D西尔 二.计算机题[每题6分,共30分]

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

2.将三对角距阵[Aij n*n的三条对角线上的元素逐列存与数组A[1。。3][]中,使得A[1][1]和A[3][N]为空,A[U][V]=Aij.请给出U,V的下标表达式[用IJ来表示]

3.已知一棵5阶4层[根为第一层,叶子为第4层]的B-树,至少有多少关键字?至多有多撒个关键字?

4.有N个结点的二叉树进行后序遍历,若在算法中使用栈,则栈中最多时候多少项?最少时多少项?

5.对长度为2K次方的有序表进行折半查找,最多比较多少?查找失败平均次数多少?

三.综合题 [每题8分,共40分]

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

2.对关键字序列(444060117060552299887733)平衡二叉树。

3.设哈希表长为11(0……10),哈希函数为K MOD 11,处理冲突随即探测再散列法,首个随即数为9请依次将序列(38827430X)哈希表

4.对关键字序列(4839668775122852561023)

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

五.算法题[116分,2317]

1N个结点的二叉树用两个一维数组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.wddqw.com/doc/fcaa6802581b6bd97f19ea49.html