湖南大学数据结构期末试卷

1、画出对下列存储于数组中的值执行buildheap后得到的最大值堆： 10 5 12 3 2 1 8 7 9 4

先序遍历为12 10 4 1 2 9 5 8 3 7 中序遍历为1 4 2 10 5 9 12 3 8 7

2、假设某字母表各个字母的权如下：

Q Z F M T S O E 2 3 10 10 10 15 20 30

(a) 按照这个字母表，一个包含n个字母的字符串采用Huffman编码在最差情况下需要多少位？怎样的串会出现最差情况？

在最差的情况下需要5*n位，当所有的字母都是Q或者Z的时候。

（b）按照这个字母表，包含n个字母的字符串采用Huffman编码在最佳情况下需要多少位？怎样的串会出现最佳情况？

在最佳的情况下需要2*n位，当所有的字母都是E或者O的时候。 （c）按照一个字母表，一个字母平均需要多少位？

（2*30 + 2*20 + 3*15 + 3*10 + 3*10 + 4*10 + 5*3+ 5*2）/100 =2.7 ∴ 2.7

3、

浙江大学宁波理工学院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分)

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

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

湖南大学课程考试试卷

课程名称：《混凝土结构设计原理》；试卷编号：A；考试时间：120分钟

题号 应得分 实得分 一 20 二 20 三 20 四 40 五 六 七 八 九 十 总分 100 评分： 评卷人 —————————————————————————————————— 一、判断题（2分/小题×10小题=20分） 【【

】 1、建筑用热轧钢筋都具有明显的流幅，属于软钢。

】 2、对矩形截面小偏心受压构件，除进行弯矩作用作用平面内的偏

心受力外，还应对垂直于弯矩作用平面按轴心受压构件进行验算。

【

】 3、钢筋混凝土受扭构件纵向受力钢筋的布置应尽可能沿构件截面

周边均匀布置。

【

】 4、斜截面破坏的三种破坏形态均属脆性破坏，设计时，斜压破坏

和斜拉破坏均可通过调整配箍率来避免。

【

】 5、建筑工程中，受弯构件斜截面的抗剪通过计算加以控制，斜截

面的抗弯一般不用计算而是通过构造措施加以控制。

【

】 6、受扭构件中，不但箍筋承担扭矩，纵筋也要承担扭矩，如果两

者搭配不当，可能出现部分超筋破坏。

【

】 7、结构设计时，对于剪扭构件，考虑剪扭相关性，主要是指混凝

土承担的扭矩（或剪力）因剪力（或扭矩）的存在而降

徐州工程学院试卷

徐州工程学院数据结构期末试卷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分）已知

2007年a卷

湖南大学 2010-2011 学年第 二 学期

2008级【现代交换原理】考试题

【A 卷参考答案与评分标准】

一、填空题（每空 1 分，共 20 分） 1、 通话设备、转换设备、信令设备 2、 （中央）馈电/集中供电 3、 分级/层、（全）分散、集中控制 4、 传输、交换、终端

5、 实时性、并发性（多道程序）。 6、 传输质量、接续质量、稳定质量 7、 32、8

8、 UNI、NNI 9、 去话汇接

二、选择题（每题 1 分，共 20 分） 1、 D 2、 D 3、 B 4、 B 5、 D 6、 C 7、 C 8、 C 9、 C 10、 A 11、 A 12、 D 13、 C 14、 C 15、 A/B 16、 A 17、 C 18、 D 19、 D 20、 D

2007年a卷

21、

三、判断改错题 (每题 2 分，共 10 分) 1、 错。

a) T 接线器中，输出控制方式的工作特点是顺序写入 SM、控制 SM 中的信息读出。 b) T 接线器中，输入控制方式的工作特点是控制话音信息写入 SM，SM 顺序读出。 2、 错。将小线群组合成大线群。 爱尔兰话务理论中，呼损一定时，线群容量越大线群出线的

平均使用率越高，因此应尽

可能地将小线群

2007年a卷

湖南大学 2010-2011 学年第 二 学期

2008级【现代交换原理】考试题

【A 卷参考答案与评分标准】

一、填空题（每空 1 分，共 20 分） 1、 通话设备、转换设备、信令设备 2、 （中央）馈电/集中供电 3、 分级/层、（全）分散、集中控制 4、 传输、交换、终端

5、 实时性、并发性（多道程序）。 6、 传输质量、接续质量、稳定质量 7、 32、8

8、 UNI、NNI 9、 去话汇接

二、选择题（每题 1 分，共 20 分） 1、 D 2、 D 3、 B 4、 B 5、 D 6、 C 7、 C 8、 C 9、 C 10、 A 11、 A 12、 D 13、 C 14、 C 15、 A/B 16、 A 17、 C 18、 D 19、 D 20、 D

2007年a卷

21、

三、判断改错题 (每题 2 分，共 10 分) 1、 错。

a) T 接线器中，输出控制方式的工作特点是顺序写入 SM、控制 SM 中的信息读出。 b) T 接线器中，输入控制方式的工作特点是控制话音信息写入 SM，SM 顺序读出。 2、 错。将小线群组合成大线群。 爱尔兰话务理论中，呼损一定时，线群容量越大线群出线的

平均使用率越高，因此应尽

可能地将小线群

汕 头 职 业 技 术 学 院

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)位置插入一个新元素时，需要从后向前依次后移_________个元素。