东北大学数据结构期末考试题

第一部分 选择题(30分)

一、选择题（20分）

1．组成数据的基本单位是（ ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量

2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ ）。

(A) 线性结构

(B) 树型结构 (C) 图型结构 (D) 集合

3．数组的逻辑结构不同于下列（ ）的逻辑结构。 (A) 线性表 (B) 栈 (C) 队列 (D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（ ）个。

(A) 2i (B) 2i (C) 2i-1 (D) 2i-1

5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ ）。

(A) p->next=p->next->next (C) p=p->next->next

(B) p=p->next (D) p->next=p

6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ ）。 (A) 6 (B) 4 (C) 3

第一部分 选择题(30分)

一、选择题（20分）

1．组成数据的基本单位是（ ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量

2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ ）。

(A) 线性结构

(B) 树型结构 (C) 图型结构 (D) 集合

3．数组的逻辑结构不同于下列（ ）的逻辑结构。 (A) 线性表 (B) 栈 (C) 队列 (D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（ ）个。

(A) 2i (B) 2i (C) 2i-1 (D) 2i-1

5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ ）。

(A) p->next=p->next->next (C) p=p->next->next

(B) p=p->next (D) p->next=p

6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ ）。 (A) 6 (B) 4 (C) 3

东北大学96考研题

一、（25分）每小题5分 1． 根据下图完成：

1） 画出该图的十字链表存储结构图。 2） 写出其拓扑排序的输出序列。 3） 写出图的强连通分量（支）。 4） 写出到的所有路径及简单路径。

2.给定8个权值集合（2，5，3，10，4，7，9，18）画出含有8个叶子结点的最佳三叉

归并树，并计算出

3.知含有8个结点的一棵二叉树，按先序、中序、后序进行遍历后，有些结点序号不清

楚如下图示。要求构造出一棵符合条件的二叉树。 先根序遍历 --- 2 3 --- 5 --- 7 8 中根序遍历 3 --- 4 1 --- 7 8 6 后根序遍历 --- 4 2 --- 6 5 1

4.根据给定的关键字集合（20，15，40，35，45，25，50，30，10）顺序输入 1） 构造一棵完全二叉树； 2） 画出整理好的一棵堆树；

3） 画出一棵输出一个排序记录后的二叉树； 4） 画出重新调整好的堆树。

5.下图给出的是一棵三阶B树，处理时每次只能读一个结点到内存。要求：

① 计算出由图中结构用计算机查找到关键字（35）的记录并将其删掉，需进行

多少次读/写才能完成？

② 画出删除

东北大学96考研题

一、（25分）每小题5分 1． 根据下图完成：

1） 画出该图的十字链表存储结构图。 2） 写出其拓扑排序的输出序列。 3） 写出图的强连通分量（支）。 4） 写出到的所有路径及简单路径。

2.给定8个权值集合（2，5，3，10，4，7，9，18）画出含有8个叶子结点的最佳三叉

归并树，并计算出

3.知含有8个结点的一棵二叉树，按先序、中序、后序进行遍历后，有些结点序号不清

楚如下图示。要求构造出一棵符合条件的二叉树。 先根序遍历 --- 2 3 --- 5 --- 7 8 中根序遍历 3 --- 4 1 --- 7 8 6 后根序遍历 --- 4 2 --- 6 5 1

4.根据给定的关键字集合（20，15，40，35，45，25，50，30，10）顺序输入 1） 构造一棵完全二叉树； 2） 画出整理好的一棵堆树；

3） 画出一棵输出一个排序记录后的二叉树； 4） 画出重新调整好的堆树。

5.下图给出的是一棵三阶B树，处理时每次只能读一个结点到内存。要求：

① 计算出由图中结构用计算机查找到关键字（35）的记录并将其删掉，需进行

多少次读/写才能完成？

② 画出删除

“数据结构”期末考试试题

一、单选题(每小题2分，共12分)

1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL；

D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边

C.n(n—1)／2条有向边 D.n(n一1)条有向边

3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n)

C.O(1Ogzn) D.O(n2)

4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48

C． 72 D． 53

5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。

A.整形 B.引用型

工程热力学 考试必用 带老师详细点评

东北大学2006级《工程热力学》期末考试试题分析

总体来看，考试结果很不理想。反映出学生在学习中头脑僵化，不会将知识融会贯通，把学习精力主要放在背诵概念、定理和类型题上。学生还严重缺乏实践经验，即使日常生活应当了解的实际只是他们也茫然无知，反映到学习上就造成无法将理论与实际结合起来，当结合实际讲解时他们反而觉得负担更重——要背的东西增加了。

1．请根据热力学第一定律（教科书41页式（2–9）），计算图1中加热蒸汽的流量。如果该换热器在运行过程中有2%的散热损失，那么

达到同样的加热效果所消耗的蒸汽量增加多少？

如果将疏水（蒸汽凝结水）送到水出口并与水混

合，那么达到同样的加热效果所消耗的蒸汽量为

多少？（20分）

本题计算对象是火力发电厂的回热加热器，

教科书上没有，但是教学中作为实际例子贯彻始

终，由于简单，故没有在课堂上举例计算。结果绝大部分学生不会，给分题成为丢分题。调查发现，相当多的同学不知道这个图形代表什么意思，因为在课堂上它是整个发电系统的一部分。了解图形含义的学生则把背下来的复杂公式硬往上套，把简单的事情弄复杂而且还错了。

2．国产N300-16.67/535/535型汽轮发电机组新蒸汽参数为16.67MPa，5

2005年－2006学年第二学期“数据结构”考试试题（A）

姓名学号(序号)_ 答案隐藏班号

要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。

一、单项选择题（每小题2分，共20分）

1．数据的运算a 。

A.效率与采用何种存储结构有关

B.是根据存储结构来定义的

C.有算术运算和关系运算两大类

D.必须用程序设计语言来描述

答：A。

2. 链表不具备的特点是 a 。

A.可随机访问任一结点

B.插入删除不需要移动元素

C.不必事先估计存储空间

D.所需空间与其长度成正比

答：参见本节要点3。本题答案为：A。

3. 在顺序表中删除一个元素的时间复杂度为 c 。

A.O(1)

B.O(log2n)

C.O(n)

D.O(n2)

答：C。

4．以下线性表的存储结构中具有随机存取功能的是 d 。

A. 不带头结点的单链表

B. 带头结点的单链表

C. 循环双链表

D. 顺序表

解 D。

5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。

A.edcba

B.decba

C.dceab

D.abcde

答：C。

6. 循环队列qu的队空条件是 d 。

A. (qu.rear+1)%Max

数据结构的基本概念

选择题

（1） 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构

中的数据元素之间的逻辑关系是由（ ）表示的。 A．线性结构 B．非线性结构 C．存储位置 D．指针

（2） 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产，子女可以继承父亲

或母亲的遗产；子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A．树 B．图 C．线性表 D．集合

（3） 计算机所处理的数据一般具有某种内在联系，这是指（ ）。 A．数据和数据之间存在某种关系 B．元素和元素之间存在某种关系 C．元素内部具有某种结构 D．数据项和数据项之间存在某种关系

（4） 在数据结构中，与所使用的计算机无关的是数据的（ ）。 A．树 B．图 C．线性表 D．集合

（5） 在存储数据时，通常不仅要存储各数据元素的值，还要存储（ ）。 A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法

（6） 在链接存储结构中，要求（ ）。

A．每个结点占用一片连续的存储区域 B．所有结点占用一片连续的存储

数据结构的基本概念

选择题

（1） 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构

中的数据元素之间的逻辑关系是由（ ）表示的。 A．线性结构 B．非线性结构 C．存储位置 D．指针

（2） 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产，子女可以继承父亲

或母亲的遗产；子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A．树 B．图 C．线性表 D．集合

（3） 计算机所处理的数据一般具有某种内在联系，这是指（ ）。 A．数据和数据之间存在某种关系 B．元素和元素之间存在某种关系 C．元素内部具有某种结构 D．数据项和数据项之间存在某种关系

（4） 在数据结构中，与所使用的计算机无关的是数据的（ ）。 A．树 B．图 C．线性表 D．集合

（5） 在存储数据时，通常不仅要存储各数据元素的值，还要存储（ ）。 A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法

（6） 在链接存储结构中，要求（ ）。

A．每个结点占用一片连续的存储区域 B．所有结点占用一片连续的存储

数据结构的基本概念

选择题

（1） 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构

中的数据元素之间的逻辑关系是由（ ）表示的。 A．线性结构 B．非线性结构 C．存储位置 D．指针

（2） 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产，子女可以继承父亲

或母亲的遗产；子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A．树 B．图 C．线性表 D．集合

（3） 计算机所处理的数据一般具有某种内在联系，这是指（ ）。 A．数据和数据之间存在某种关系 B．元素和元素之间存在某种关系 C．元素内部具有某种结构 D．数据项和数据项之间存在某种关系

（4） 在数据结构中，与所使用的计算机无关的是数据的（ ）。 A．树 B．图 C．线性表 D．集合

（5） 在存储数据时，通常不仅要存储各数据元素的值，还要存储（ ）。 A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法

（6） 在链接存储结构中，要求（ ）。

A．每个结点占用一片连续的存储区域 B．所有结点占用一片连续的存储