哈工大数据结构期末试卷

浙江大学宁波理工学院200_9_–2010_学年_二_学期

《数据结构（乙）》课程期末考试试卷（A）

开课分院： 信息分院 ，考试形式：开卷

考试日期：__ 2010___年__6__月__ 24__日，考试所需时间： 120 分钟

考生姓名 学号 考生所在分院： 专业班级： . 题序 题型 得分 评卷人 一 问答题 二 程序编写题 总 分 一、简答题（本大题共10小题，每小题2分，共60分）

1.设字符a,b,c,d,e,f,g的使用权值分别是15，5，36，2，22，12，8，画出Huffman树，并写出a,b,c,d,e,f,g的Huffman编码。（6分）

0371001015ae1022012f0702d15b2711518g63136c

2．已知二叉树的先序序列和中序序列分别为ABDHIEJKCFLMG和HDIBJEKALFMCG。（1）画出该二叉树；（2）画出（1）中求得的二叉树对应的森林。(10分)

命题（组）老师签名：____________________ 年 月 日

分院主管教学院长或首席主讲教授签名：___________

哈尔滨工业大学（威海）2011/2012学年秋季学期

教师姓名：________________学生姓名：_________________学号：_____________________班号：________________ 大 学 物 理 A 试题卷（B卷）

? 卷面满分70分。考试时间2小时。

? 铅笔答题者、姓名学号书写不当者，试卷无效。 题号 一 二 三-1 三-2 三-3 三-4 卷面 合计 分数 平时成绩

总 成 绩 一、得分

一、 选择题（共20分，每小题2分，答案写在下表中） 小题 答案 1 2 3 4 5 6 7 8 9 10 1. 设某种气体的分子速率分布函数为f (v)，则速率在v 0─v1区间内的分子的平均

速率为： (A) (C)

??v1v0v1vf?v?dv??0f?v?dv． (B)

?v1v0vf?v?dvv1v0?f?v?dv．

v0v1v0vf?v?dv． (D) v?vf?v?dv.

2. 一定量的理想气体，经历某过程后，

哈尔滨工业大学（威海）2011/2012学年秋季学期

教师姓名：________________学生姓名：_________________学号：_____________________班号：________________ 大 学 物 理 A 试题卷（B卷）

? 卷面满分70分。考试时间2小时。

? 铅笔答题者、姓名学号书写不当者，试卷无效。 题号 一 二 三-1 三-2 三-3 三-4 卷面 合计 分数 平时成绩

总 成 绩 一、得分

一、 选择题（共20分，每小题2分，答案写在下表中） 小题 答案 1 2 3 4 5 6 7 8 9 10 1. 设某种气体的分子速率分布函数为f (v)，则速率在v 0─v1区间内的分子的平均

速率为： (A) (C)

??v1v0v1vf?v?dv??0f?v?dv． (B)

?v1v0vf?v?dvv1v0?f?v?dv．

v0v1v0vf?v?dv． (D) v?vf?v?dv.

2. 一定量的理想气体，经历某过程后，

徐州工程学院试卷

徐州工程学院数据结构期末试卷A答案

2009 — 2010 学年第 二 学期 课程名称 数据结构

试卷类型 期末 考试形式 闭卷 考试时间 100 分钟 命 题 人 鞠训光 2010 年 6 月 7 日 使用班级 08电本

教研室主任 年 月 日 教学院长 年 月 日 姓 名 班 级 学 号 .

题号 总分 得分

一 20 二 15 三 15 四 10 五 40 六 七 八 总分 一、填空题 （共 8 小题，每空 1 分，共计 20 分）

1．栈和队列都是线性_结构；对于栈只能在_栈顶_ 插入和删除元素

厦门大学《＿数据结构＿》课程期末试卷 信息科学与技术学院计算机科学系2004年级＿＿＿专业

主考教师：＿＿＿＿试卷类型：（A卷/B卷）

一、试设计算法在O(n)时间内将数组A[1..n]划分为左右两个部分，使得左边的所有元素奇数，右边的所有元素均为偶数，要求所使用的辅助存储空间大小为O(1)。 解：该题算法的主要思路如下：

（1）设置两个指针i和j，其中i=1，j=n。 （2）当i

i不断自加从左往右找到第一个偶数 j不断自减从右往左找到第一个奇数 A[i]与A[j]交换

（3）算法结束 Adjust(int A[1..n]) { int i=1, j=n; while (i=1) j--; if (i>n || j

算法的时间复杂性为O(n)，辅助存储空间为O(1)。

二、写一个算法将一带头结点的单链表逆转，要求利用原表结点空间，不允许申请新的结点空间。 解：

方法一：建立一个新的单链表，其中的结点从原表得来，即每个原表中得到一个结点，就要将此结点插入新链表中。由于要将表逆转，原表的头结点成为新链表的头结点，每次从原表中得到一个结点，此结点插在头结点之后，作为新链表的第一个结点。 void InverLinkedList( Li

数 据 结 构B 期末试卷

班级 学号 姓名 得分

题号 分数 一 二 三 四 五 六 一、解答题：（共82分）

1、下列程序段或函数的时间复杂度。（10%）

（1） for (int k=0;k

for (int j=0;j

（3） int Prime(int n) （4）k=1; x=0;

{ int k=2 , x=(int)sqrt(n) ; do {

while (k<=x) { x++; k*=2; if (n % k= =0) break; }

k++; } while (k

if (k>x) return 1; else return 0; }

2、有A、B、C、D四个元素依次入栈，即入栈序列唯一，问共能得到多少种出栈序列？能否得到以下四种出栈序列：ABCD、BDAC、CBDA、DBAC。对能得到的序列，请写出Push、Pop序列；对不能得到的序列，请说明理由。（6%）

3、矩阵Am*n以行优先方式从1

厦门大学《＿数据结构＿》课程期末试卷 信息科学与技术学院计算机科学系2009年级＿＿＿专业

主考教师：陈怡疆 庄朝晖 试卷类型：（B卷）

一、（本题10分）请根据下面的描述写出销售部门的数据结构（用C语言）：假设一个销售部门有n个职员（最多不超过N个，N为100），其中有一个是销售经理。每个职员都各自有一些客户，客户的个数不固定，不同职员的客户不重叠。 二、（本题15分）

（1）线性表和广义表的主要区别点是什么？已知广义表: C=(a,(b, (a,b)), ((a,b), (a,b))), 则tail(head(tail(C))) =？

（2）满足什么条件可以实施二分查找？二分查找的时间复杂度是多少？ 三、（本题10分）给定一组权值（5，9，11，2，6，16），试设计相应的哈夫曼树。 四、（本题15分）某带权有向图如下：

A 1 B 1 E 始点 3 2 3 2 C 1 F 5 G 终点 3 D 1

（1）写出深度优先搜索结点访问序列，并画出深度优先生成树（当有多种选择时，编号小的结点优先）；

（2）写出该图的拓扑序列（当有多种选择时，编号小的结点优先）； （3）将该图作为AOE网络，写出求关键路径的过程。 五、（本题10分）已知

《数字逻辑 》A卷

1

一、选择：（每题3分，共计30分）

1、表示任意两位无符号十进制数需要 二进制数。

A．6 B．7 C．8 D．9 2、标准或-与式是由 构成的逻辑表达式。

A．与项相或 B. 最小项相或 C. 最大项相与 D.或项相与 3、从JK触发器是 。

A. 在CP的上升沿触发

B. 在CP的下降沿触发

C. 在CP = 1的稳态下触发 D. 与CP无关

4、R、S是RS触发器的输入端，则约束条件为 。

A. RS = 0 B. R + S = 0 C. RS = 1 D. R + S = 1

5、触发器的现态为0，在CP作用后仍然保持0状态，那么激励函

数的值应该是 。 A. J = 1, K = 1

数字电子技术 （A卷）

一、 填空题：（每空2分，共30分）

（1）（11100.011）2 =( 28.6 )10 =( )8421BCD

（2） (204.125) 10 =( ) 2 =( )8 =( )16

（3）字母TTL代表( )。

（4） 三态门的输出状态共有( )三个状态。

（5）将模拟信号转换为数字信号需经过（ ）四个步骤。 （6）触发器的触发方式可分为电平触发和（ ）触发。 （7） 逻辑门电路输出端可驱动同类门电路的个数称为( )。

（8） 将Y?(A?B?C)(A?B?C) 化为最小项形式为（ ）。 （9） （ ）（译码器，编码器）的特点是在任一时刻只有一个输入有效。 （10）一位半加器具有( )个输入和两个输出。

（11）已知A/D转换器的分辨率为8位，其输入模拟电压范围为

0～5V，则当输入

汕 头 职 业 技 术 学 院

2008-2009学年第一学期期末试卷（A）

课程名称 数据结构 学分_____ 拟题人 何汉阳 审题人___________ 系(校区) 计算机系 班级_____________ __ 学号_____ 姓名_ _________

题 号 得 分 一 二 三 四 五 六 七 八 总 分 评卷人

一、选择题（每小题2分，共40分）

1．数据的__________包括集合、线性结构、树型结构和图状结构四种基本类型。 A)算法描述 B)基本运算 C)逻辑结构 D)存储结构

2．数据的存储结构包括顺序、___________、索引和散列四种基本类型。 A)向量 B)数组 C)集合 D)链接

3．下面____________的时间复杂性最好，即执行时间最短。

3

A)O(n) B)O(nlog2n) C)O(log2n) D)O(n)

4．在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)位置插入一个新元素时，需要从后向前依次后移_________个元素。