广工数据结构期末试卷

浙江大学宁波理工学院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，b和c的值 不是依次非递增的，则通过交换，令其为非递增。 ***********/

void Descend(int &a, int &b, int &c) /* 通过交换，令 a >= b >= c */ { int t;

if(a<=b){t=a;a=b;b=t;} if(b<=c){t=b;b=c;c=t;} if(a<=b){t=a;a=b;b=t;} }

/**********

【题目】试编写算法求一元多项式 P(x) = a0 + a1x + a2x^2 + ... + anx^n

的值P(x0)，并确定算法中每一语句的执行次数和整个算法 的时间复杂度。 **********/

float Polynomial(int n, int a[], float x)

/* 求一元多项式的值P(x)。 */ /* 数组a的元素a[i]为i次项的系数，i=0,...,n */ { int i,j;float p=0,t=1; for(i=0;i<=n;i++) {

p=a[i]*t+p; t=t*x ; } return p; }

/**********

【题目】已知k阶裴波那契序列的定义为 f(0)=0, f(1)=0, ..., f(k-2)=0, f

徐州工程学院试卷

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

汕 头 职 业 技 术 学 院

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

_…__…__…__…__…__…__…__…__…_：…名…姓…… __…__…__…__…__…__…__…_：…号线..学… _…__…__…__…__…__…__ 订.__…__…：…级…班… …__…__装_..__…__…__…__…__…__…__…__…：…业…专… _…__…__…__…__…__…__…：…级…年……诚信应考 考出水平 考出风格

浙江大学城市学院

2013 — 2014 学年第 2 学期期末考试试卷

《 数据结构 》

开课单位： 计算分院 ；考试形式：闭卷；考试时间： 2014 年 06 月 29日； 所需时间： 120 分钟 题序 一 二 三 四 五 六 七 总 分 得分 评卷人 注：试卷答案必须写在答卷上，写在试卷上不得分。

得分 一．判断题(有5条是正确的，将正确的编号写在答卷上，每空 1 分，共 5 分)

1. 数据结构的逻辑结构独立于其存储结构。 2. 某算法的时间复杂度是O（n2），表明该算法的执行时间是问题规模n的平方。 3. 在数据结构中，从逻辑上可以把数据结构分成顺序结构和链式结构。

4. 顺序表可以利用一维数组表示

汕 头 职 业 技 术 学 院

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

汕 头 职 业 技 术 学 院

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