2014年北方工业大学数据结构期中考试卷

2014年北方工业大学数据结构期中考试卷

北方工业大学 《数据结构II》课程期中试卷

2014年春季学期

开课学院： 理学院 考试方式：闭卷 A卷 考试时间：50 分钟

班级 姓名 学号 装 一、 单项选择题（每题4分，共24分）

1. 对一个算法的评价，不包括如下（ ）方面的内容。

A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度

2. 下列不属于线性结构的是（ ）

订 A. 栈 B. 队列 C. 串 D. 二叉树

3. 对线性表，在下列哪种情况下应当采用链表表示？( )

A．经常需要随机地存取元素 B．经常需要进行插入和删除操作

C．表中元素需要占据一片连续的存储空间 D．表中元素的个数不变

4. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( )

A．2 3 1 B． 3 2 1

C．3 1 2 D． 1 2 3

5． 已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边， 应该（ ）

A．将邻接矩阵的第i行删除 B．将邻接矩阵的第i行元素全部置为0

C．将邻接矩阵的第i列删除 D．将邻接矩阵的第i列元素全部置为0 线

6. 栈和队列的共同特点是( )

A．只允许在端点处插入和删除元素 B．都是先进后出

C．都是先进先出 D．没有共同点

2014年北方工业大学数据结构期中考试卷

二、按要求做题（15分）

LinkList mynote(LinkList L)

{//L是不带头结点的单链表的头指针

if(L&&L->next){

q=L；L=L－>next；p=L；

S1： while(p－>next) p=p－>next；

S2： p－>next=q；q－>next=NULL；

}

return L；

}

请回答下列问题：

（1）说明语句S1的功能；

（2）说明语句组S2的功能；

（3）设链表表示的线性表存放的数据为（1,2, …,10）, 写出算法执行后的返回值所表

示的线性表。

三．运算题(共61分)

1. (18分)（i）已知一棵二叉树的中序遍历DBGEACF，后序遍历为DGEBFCA，求这棵二叉树及其前序遍历。

(ii) 给定一个二叉树前序和后序遍历，能恢复出二叉树吗？为什么？

(iii) 写出下面这棵树的中序和后序遍历

2014年北方工业大学数据结构期中考试卷

2. (5分) 计算运行下列程序后m的值：

n=10; m=0;

for(i=1;i<=n;i++)

for(j=2*i; j<=n; j++)

m=m+2;

3. （10分） 编号为1,2,3的三辆列车，顺序开进一个链式结构的站台，则开出车站的顺序可能有哪些？共有多少种？

4．（10分）请画出图的邻接矩阵和邻接表。

2014年北方工业大学数据结构期中考试卷

5.（18分）设给定一个权值集合W=(3, 4，5, 6， 8) （i） 要求根据给定的权值集合构造一棵哈夫曼树

（ii） 计算哈夫曼树的带权路径长度及相应的哈夫曼编码。 （iii） 简要介绍构造哈夫曼树的算法

本文来源：https://www.bwwdw.com/article/dzz4.html