数据结构(高起专)阶段性作业3
数据结构(高起专)阶段性作业3
总分: 100分考试时间:分钟
单选题
1. 不含任何结点的空树_____。(4分)
(A) 是一棵树
(B) 是一棵二叉树
(C) 是一棵树也是一棵二叉树
(D) 既不是树也不是二叉树
参考答案：C
2. 把一棵树转换为二叉树后，这棵二叉树的形态是_____。(4分)
(A) 惟一的
(B) 有多种
(C) 有多种，但根结点都没有左孩子
(D) 惟一的，且根结点没有右孩子
参考答案：A
3. 二叉树是非线性数据结构，所以_____。(4分)
(A) 它不能用顺序存储结构存储
(B) 它不能用链式存储结构存储
(C) 顺序存储结构和链式存储结构都能存储
(D) 顺序存储结构和链式存储结构都不能使用
参考答案：C
4. 具有10个叶结点的二叉树中有_____个度为2的结点。(4分)
(A) 8
(B) 9
(C) 10
(D) 11
参考答案：B
5. 有关二叉树下列说法正确的是_____。(4分)
(A) 二叉树的度为2
(B) 一棵二叉树的度可以小于2
(C) 二叉树中至少有一个结点的度为2
(D) 二叉树中任何一个结点的度都为2
参考答案：B
6. 要连通具有n个顶点的有向图，至少需要_____条边。(4分)
(A) n-l
(B) n
(C) n+l
(D) 2n
参考答案：B
7. 下列哪一种图的邻接矩阵是对称矩阵？_____。(4分)
(A) 有向图
(B) 无向图
(C) AOV网
(D) AOE网
参考答案：B
判断题
8. 二叉树是度为2的有序树。(5分)
正确错误
参考答案：错误
解题思路：
9. 二叉树的遍历结果不是唯一的。(5分)
正确错误
参考答案：正确
解题思路：
10. 由一棵二叉树的前序序列和后序序列可以唯一确定它。(5分)
正确错误
参考答案：错误
解题思路：
11. 在n个结点的无向图中，若边数大于n-1,则该图必是连通图。(5分)正确错误
参考答案：错误
解题思路：
12. 有向图的邻接矩阵是对称的。(5分)
正确错误
参考答案：错误
解题思路：
13. 带权无向图的最小生成树必是唯一的。(5分)
正确错误
参考答案：错误
解题思路：
填空题
14. 树是一种___(1)___ 数据结构，树型结构中数据元素之间的关系是___(2)___ 的关系。(6分)
(1). 参考答案: 非线性
(2). 一对多或者多对一
(1). 4
(1).
(1). 18
(2). 参考答案: 5
18. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为___(7) ___ 。(3分)
(1). 53
(1). 2
(1).
(1). 邻接矩阵
(2). 参考答案: 邻接表
(3). 边集数组
(1). 最小生成树
(1).
数据结构第3次作业
1. 填空题 (1) 顺序栈s的数据存储在数组element中，则栈满的条件是____________,栈空的条件是。 (2) 顺序栈ｓ进行出栈操作后，要执行的语句是top____。s进行进栈操作前，要执行的语句是top______运算。 (3) 元素进入队列的一端是____________；队列出队的一端是____________。 (4)顺序队列q满的条件是，顺序队列q空的条件 是。 (5) 空串的长度等于，非空串的长度等于。 2. 选择题 (1) 串是一种特殊的线性表，其特征体现在_____。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符 (2) 栈是限定在__________处进行插入或删除操作的线性表。 A. 端点 B. 栈底 C. 栈顶 D. 中间 (3) 在栈顶一端可进行的全部操作是___________。 A. 插入 B.删除 C. 插入和删除 D. 进栈 (4) 4个元素按A、B、C、D顺序连续进S栈，进行x=pop()运算后，x的值是___________, 栈顶元素的值是. A. A B. B C. C D. D (5) 栈的特点是__________。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不进不出 (6) 顺序栈存储空间的实现使用___________。 A. 链表 B. 数组 C.循环链表 D. 变量 (7) 一个顺序栈一旦说明，其占用空间的大小___________。 A. 已固定 B. 可以改变 C. 不能固定 D. 动态变化 (8) 栈与一般线性表的区别主要在___________方面。 A. 元素个数 B. 元素类型 C. 逻辑结构 D. 插入、删除元素的位置 (9) 栈s经过下列运算后s.get()的值是___________, s.isEmpty( )的值是___________。 s.push(a);s.push(b);s.pop(); A. a B. b C. 1 D. 2
哈工大-测试技术与仪器-大作业一
Harbin Institute of Technology 测试技术与仪器大作业一 设计题目：信号的分析与系统特性 院系：英才学院 班级： 1036*** 姓名： ****** 学号： ********** 时间： 2013.07.01 工业大学
一、设计题目 二、求解信号的幅频谱和相频谱 )1-(cosn (-A)e 1e 1(t)e 10 2 t jn -0 t jn -0 2 t jn -0 02 02 00ππ ωωωn A j dt T dt A T dt x T C T T n T T =+ = = ?? ? -- 当???±±±=,5,3,1n 时，π n A j C n 2-= 当???±±±=6,4,2,0，n 时，0=n C 幅频谱函数为： π n A C n 2= ，???±±±=,5,3,1n πn A C A n n 42==，???=,5,3,1n 相频谱函数为： ,...5,3,12 --arctan arctan ==∞==n C C nR nI n ，）（π ? ,...5,-3,-1-2 arctan arctan ==∞+==n C C nR nI n ，）（π? 双边幅频图：
单边幅频图： 双边相频图： 单边相频图： 三、频率成分分布情况 方波由离散的频率成分组成。基频为0 02T π ω= ,其余频率为基频的奇数倍。 四、系统)(s H 的伯德图
1）一阶系统传递函数1 1 )(+= s s H τ，0.008s τ=，伯德图为： -40-30 -20 -10 M a g n i t u d e (d B )10 10 10 10 10 P h a s e (d e g ) Bode Diagram Frequency (rad/s) 二阶系统2 2240)(n n n s s s H ωζωω++= ，ζ= 0.65，n ω= 100。伯德图为： -60-40-20020 40M a g n i t u d e (d B )10 10 10 10 10 P h a s e (d e g ) Bode Diagram Gm = Inf dB (at Inf rad/s) , P m = 11.9 deg (at 634 rad/s) Frequency (rad/s)
数据结构第三章习题答案
第三章习题 1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答： ⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？ ⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。（即写出 以“S”表示进栈、以“X”表示出栈的栈操作序列）。 2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。如果对这个队列重复执行下列4步 操作： （1）输出队首元素； （2）把队首元素值插入到队尾； （3）删除队首元素； （4）再次删除队首元素。 直到队列成为空队列为止，得到输出序列： （1）A、C、E、C、C （2） A、C、E （3） A、C、E、C、C、C （4） A、C、E、C 3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？ 4.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操 作数栈和运算符栈的变化过程： A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ 5.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1& 序列2’ 模式的字符序列。其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。 6.假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式且书写 正确的表达式转换为逆波兰式。 7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针）， 试编写相应的队列初始化、入队列和出队列的算法。 8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分 头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。
南京工业大学 数据结构 作业答案 作业6
第六次作业 1. 假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题： （1）画出描述折半查找过程的判定树； （2）若查找元素54，需依次与哪些元素比较？ （3）若查找元素90，需依次与哪些元素比较？ （4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。 2. 设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。 K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，试回答下列问题： （1）画出哈希表的示意图； （2）若查找关键字63，需要依次与哪些关键字进行比较？ （3）若查找关键字60，需要依次与哪些关键字比较？ （4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 3. 在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。 4. 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。 1.假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题： （5）画出描述折半查找过程的判定树； （6）若查找元素54，需依次与哪些元素比较？ （7）若查找元素90，需依次与哪些元素比较？ （8）假定每个元素的查找概率相等，求查找成功时的平均查找长度。 解： （1）先画出判定树如下（注：mid=?(1+12)/2?=6）： 30 5 63 3 7 42 87 4 24 54 72 95 (2) 查找元素54，需依次与30, 63, 42, 54 等元素比较； (3) 查找元素90，需依次与30, 63,87, 95, 72等元素比较； （4）求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次； 但最后一层未满，不能用8×4，只能用5×4=20次， 所以ASL＝1/12（17＋20）＝37/12≈3.08
在线作业答案北航《测试技术基础》在线作业三15秋满分答案
北航《测试技术基础》在线作业三15秋满分答案单选题判断题多选题 一、单选题（共 10 道试题，共 30 分。） 1. 电容式传感器中，灵敏度最高的是（）。 A. 面积变化型 B. 介质变化型 C. 极距变化型 D. 电压变化型 -----------------选择：C 2. 二阶装置引入合适阻尼的目的是（）。 A. 系统不发生共振 B. 使得读数稳定 C. 获得较好的幅频、相频特性 D. 以上都不对 -----------------选择：C 3. 自相关函数是一个（）函数。 A. 奇 B. 偶 C. 非奇非偶 D. 三角 -----------------选择：B 4. 测试装置的脉冲响应函数与它的频率响应函数间的关系是（）。 A. 卷积 B. 傅氏变换对 C. 拉氏变换对 D. 微分 -----------------选择：B 5. 描述周期信号的数学工具是（）。 A. 相关函数 B. 傅氏级数 C. 傅氏变换 D. 拉氏变换 -----------------选择：B 6. 为提高电桥的灵敏度，可采取的方法是（）。 A. 半桥双臂各串联一片电阻应变片 B. 半桥双臂各并联一片电阻应变片 C. 适当提高电桥的电源电压 D. 增大应变片的初始电阻值
7. 电涡流式传感器是利用（）材料的电涡流效应工作的。 A. 金属导电 B. 半导体 C. 非金属 D. PVF2 -----------------选择：A 8. 对连续信号进行采样时，采样频率越高，当保持信号的记录的时间不变时，则（）。 A. 泄漏误差就越大 B. 量化误差就越小 C. 采样点数就越多 D. 频域上的分辨率就越低 -----------------选择：C 9. 傅氏级数中的各项系数是表示各谐波分量的（）。 A. 相位 B. 周期 C. 振幅 D. 频率 -----------------选择：C 10. 石英晶体的压电系数比压电瓷的（）。 A. 大得多 B. 相接近 C. 小得多 D. 不能决定 -----------------选择：C 北航《测试技术基础》在线作业三 单选题判断题多选题 二、判断题（共 10 道试题，共 30 分。） 1. 测试系统的灵敏度越高测量性能越好。 A. 错误 B. 正确 -----------------选择：A 2. 对于电压放大器来说，当改变电缆的型号尺寸，输出电压将不改变。 A. 错误 B. 正确 -----------------选择：A 3. 选择好的窗函数对信号进行截断，可以减少能量泄漏。 A. 错误 B. 正确
完整版数据结构习题集第3章栈和队列
第3章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ） A、HS->next=s; B、s->next=HS->next；HS->next=s; C、s->next=HS；HS=s; D、s->next=HS；HS=HS->next; 4.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C） A 、x=HS；HS=HS->next; B 、HS=HS->next；x=HS->data; C 、x=HS->data；HS=HS->next; D 、s->next=Hs；Hs=HS->next; 5.表达式a*(b+c)-d 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ B ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为空的条件是（） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队列为满的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从 队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（） A、1，5 B、2, 4 C、4，2 D、5，1 11.用单链表表示的链式队列的队头在链表的（）位置 A、链头 B、链尾 C、链中 12.判定一个链队列Q（最多元素为n 个）为空的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13.在链队列Q 中，插入s 所指结点需顺序执行的指令是（） A 、Q.front->next=s；f=s; B 、Q.rear->next=s；Q.rear=s;
数据结构作业及答案
第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3;
作业-《数据结构习题集(C语言版)严蔚敏》答案汇编
第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={
测试技术作业答案
习题 1-2 求正弦信号t x t x ωsin )(0=的绝对均值x u 和均方根值rms x 。 解：dt t x T u T x ?=2 0sin ||2/1 ω 200|)cos (||2T t T x ωω-= )cos 0(cos 2||20ππ -=x π | |20x = ?=T rms dt t x T x 0 20)sin (1ω ＝ ? -T dt t T x 0 2 02 2cos 1ω ＝ 2 2 0T T x ?＝2 2 0x
1-3 求指数函数)0,0()(≥>=-t a Ae t x at 的频谱 解：指数函数为非周期函数，用傅立叶变换求其频谱。 ?+∞ ∞---=dt e Ae f X ft j at π2)( ? +∞ +-= )2(dt Ae t f j a π ∞ ++-+-= 0)2(|2t f j a e f j a A ππ f j a A π2+= 幅频谱表示式：22)(ω ω+=a A A 相频谱表示式：a arctg ω ω?-=)( 2-2 用一个时间常数为0.35s 的一阶装置去测量周
期分别为1s 、2s 和5s 的正弦信号，问幅值误差将是多少？ 解：1）一阶系统的频率响应函数为： 1 1)(+= τωωj H 幅频表示式：1 )(1 )(2 += τωωA 2）设正弦信号的幅值为x A ，用一阶装置测量 正弦信号，测量幅值（即一阶装置对正弦信号的输出）为)(ωA A x 幅值相对误差为： )(1) (ωωA A A A A x x x -=- 3）因为T 1 =ω T=1s 、2s 、5s ，则ω=2π、π、2π/5(rad) 则A(ω)分别为：=+?1 )235.0(1 2 π0.414 673.01 )35.0(1 2 =+?π 915.01 )5 235.0(1 2 =+?π
数据结构作业标准答案
第一章 单选题 1、下列关于算法的基本特征，说法不正确的是（）。能行性是算法中的每一个步骤必须能够实现且能达到预期的目的。算法的确定性是指算法中的每一个步骤必须是有明确的定义，不允许模棱两可。 算法的有穷性是指算法必须能在有限的时间内做完。算法与提供情报无关。 [D] 教师批改：D 2、算法的时间复杂度取决于（）。问题的规模待处理的数据的初态 问题的难度 A 和B [D] 教师批改：D 3、下列选项中，不是算法基本特征的是（）。可行性有穷性 确定性高效率 [D] 教师批改：D 4、通常一个好的算法应达到的目标中，不包括（）。正确性可读性 技巧性健壮性 [C] 教师批改：C 5、在一般的计算机系统中，基本的运算和操作不包括（）。语法处理算术运算 关系运算数据传输 [A] 教师批改：A 6、工程上常用的分治法是（）。列举法归纳法 减半递推技术回溯法 [C] 教师批改：C 多选题 7、算法设计的要求包括（）。 正确性可读性 健壮性唯一性 [ABC] 教师批改：A，B，C 8、算法的时间复杂度应该与（）无关。 所使用的计算机程序设计语言 基本运算的执行次数程序编制者 [ABD] 教师批改：A，B，D 9、下列关于算法的描述中，不正确的有（）。 算法即是计算机程序算法是解决问题的计算方法 算法是排序方法算法是解决问题的有限运算序列 [ABC] 教师批改：A，B，C 填空题 16、所谓算法是指（）。 教师批改：解题方案的准确而完整的描述 17、算法的基本特征有（）、（）、（）和（） 教师批改：能行性、确定性、有穷性和拥有足够的情报。
18、一个算法通常由两种基本要素组成，它们是（）和（）。 教师批改：算法中对数据的运算和操作。 算法的控制结构。 19、工程上常用的几种算法设计方法有列举法、（）、（）、（）、（）和回溯法。 教师批改：归纳法、递推、递归、减半递推技术。 20、算法的复杂度主要包括（）复杂度和（）复杂度。 教师批改：时间、空间 综合题 21、设给定3个整数a，b，c，试写出寻找这3个整数的中数的算法；并分析在平均情况与最坏情况下，该算法分别要做多少次比较？ 寻找这3个整数的中数的算法用C语言描述如下（中数m由函数值返回）： int mid ( int a, int b, int c) { int m 。m=a 。 if ( m>=b ) { if (m>=c) { if ( b>=c ) m=b 。else m=c 。} } else { if ( m<=c) { if (b>=c) m=c。else m=b 。} } return ( m ) 。 } 假设a，b，c中的每一个数为中数的概率相等（均为1/3）。由于当a为中数时需要比较2次，b或c为中数时均需要比较3次，因此，在平均情况下上述算法所需要的比较次数为 2*（1/3）+3*（1/3）+3*（1/3）= 8/3 即在平均情况下，上述算法需要比较8/3次。 在最坏情况下，上述算法需要比较3次（当b或c为中数时）。 第二章 选择题 1、下列排序方法中，哪一个是稳定的排序方法（）。归并排序稀尔排序 堆排序快速排序 [A] 教师批改：A 2、设输入序列为1，2，3，4，借助一个栈得到的输出序列可以是（）。3，4，1，2 4，2，1，3 4，1，2，3 1，3，4，2 [D] 教师批改：D 3、用数组A[m]存放循环队列的元素值，若其头尾指针分别为front和rear，则循环队列中当前元素的个数为（）。(rear+front)%m (rear-front+m)%m (rear-front)%m (rear-front+1)%m [D] 教师批改：B 4、对于下三角矩阵A，若采用一个一维数组B以行为主顺序存放压缩矩阵A，则A43存放在（）中. B7 B8 B9 B10 [C] 教师批改：C 5、深度为5的二叉树至多有（）个结点。16 32
数据结构习题
《数据结构》习题集 第一章序论 思考题： 1.1简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型、抽象数据类型 作业题： 1.2设有数据结构（D，R），其中 D={d1, d2, d3, d4 } R={r1, r2} r1={ (5) x=n; y=0; //n是不小于1的常数 while(x>=(y+1)*(y+1)){ △y++; } (6) x=91; y=100; while ( y>0 ) { △if(x>100) { x-=10; y--; } else x++ ; } (7) for( i=0; i #include LinkList r = h->next; while(r != NULL) { printf("%d ",r->data); r = r->next; } putchar('\n'); } void InsertList(LinkList h, int x, int y) { LinkList s, p, q; s = new Lnode; s->data = y; q = h; p = q->next; while((p!=NULL) && (p->data != x)) { q = p; p = p->next; } s->next = p; q->next = s; } void DeleteList(LinkList h, int x) { LinkList p, q; q = h; p = q->next; while((p != NULL) && (p->data != x)) { q = p; p = p->next; } if(p == NULL) printf("no"); else { q->next = p->next; delete(p); printf("yes"); } } 第1章 1.下面（B ）方式可以查看“cp”命令的帮助。 A：cp -? B：cp -h C：cp -a D：cp --h 2.在vi 中从“可视模式”切换到“命令模式”使用（ B）。A：: B：ESC C：Ctrl+L D：Ctrl+Q 3.下面（D ）是“ssh”命令正确的使用方法。 A：ssh -l 192.168.159.159 B：ssh -o 192.168.159.159 C：ssh -a 192.168.159.159 D：ssh 192.168.159.159 4.关于“mkdir -p /fringe/oliva”命令说法正确的是（C ）。A：“-p”是该命令的参数B：该命令没有使用选项C：“-p”是该命令的选项D：该命令没有使用参数5.使用（ A）可以使当前行出现上一行的最后一组参数。A：Ctrl+K B：ESC+. C：Ctrl+L D：ESC+> 6.下列不属于Linux 桌面环境的是（AB ）。 A：Fluxbox B：JDK C：GNOME D：KDE 7.下列关于Linux 桌面环境说法正确的是（D ）。 A：在虚拟终端可以使用Ctrl+F1可以回到Linux桌面环境B：一个系统中只可以安装一种Linux桌面环境 C：Linux桌面环境是Linux运行不可缺少的内容 D：Linux桌面环境不是Linux运行不可缺少的内容 8.在vim 中使用（ D）可以保存并退出当前编辑的文件。A：:w B：:q! C：:q D：:wq 9.使用（D ）可以清除屏幕所有内容。 A：ESC B：ESC+C C：Ctrl+U D：Ctrl+L 10.下列关于telnet 服务说法正确的是（ D）。 A：在RHEL5中默认就安装了telnet 服务 B：telnet 服务在数据传输过程中会对数据进行加密 C：telnet 服务只能在Linux 系统之间使用 D：telnet 服务在数据传输过程中不会对数据进行加密 第2章 1.下面（）命令可以分屏显示“/var/log/message”的内容。A：cat B：file 第三章栈、队列和数组 一、名词解释： 1.栈、栈顶、栈底、栈顶元素、空栈 2.顺序栈 3.链栈 4.递归 5.队列、队尾、队头 6.顺序队 7.循环队 8.队满 9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上（下）三角矩阵 二、填空题： 1.栈修改的原则是_________或称________，因此，栈又称为________线性表。在栈顶 进行插入运算，被称为________或________，在栈顶进行删除运算，被称为________ 或________。 2.栈的基本运算至少应包括________、________、________、________、________五 种。 3.对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。 4.对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。 5.一般地，栈和线性表类似有两种实现方法，即________实现和________实现。 6.top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1 表示________，此时作进栈运算，则产生“________”。 7.以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。 int InitStack(SqStackTp *sq) { ________; return(1);} 8.以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。 Int Push(SqStackTp *sq,DataType x) { if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} else{________________: ________________=x; return(1);} } 9.以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。 Int Pop(SqStackTp *sq,DataType *x) {if(sp->top==0){error(“下溢”);return(0);} else{*x=________________; ________________; return(1);} } 10. 以下运算实现在顺序栈上判栈空，请在________________处用适当句子予以填充。 Int EmptyStack(SqStackTp *sq) {if(________________) return(1); else return(0); } 11.以下运算实现在顺序栈上取栈顶元素，请在________________处用适当句子予以填充。 Int GetTop(SqStackTp *sq,DataType *x) {if(________________) return(0); 一、单项选择题（每小题2分，共32分） 题目1 假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）。选择一项： A. 17 B. 16 C. 15 D. 47 题目2 二叉树第k层上最多有（）个结点。 选择一项： A. 2k B. 2k-1 C. 2k-1 D. 2k-1 题目3 设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（）。选择一项： A. debac B. abdec C. abedc D. debca 将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（）。 选择一项： A. 36 B. 35 C. 33 D. 34 题目5 如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。 选择一项： A. 平衡二叉树 B. 完全二叉树 C. 哈夫曼树 D. 二叉树 题目6 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（）。 选择一项： A. 7 B. 6 D. 4 题目7 在一棵度具有5层的满二叉树中结点总数为（）。 选择一项： A. 31 B. 32 C. 16 D. 33 题目8 利用n个值作为叶结点的权生成的哈夫曼树中共包含有（）个结点。 选择一项： A. 2*n B. n C. 2*n-1 D. n+1 题目9 利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子结点中的最长带权路径长度为（）。 选择一项： A. 16 B. 18 2.6．数据的存储结构主要有哪两种？它们之间的本质区别是什么？ 答：主要有：顺序存储结构和链式存储结构两种。 区别: 顺序存储结构是借助元素在存储器的相对位置来表示数据间的逻辑关系，而链式存储结构是借助指针来表示数据间的逻辑关系。 2.7 设数据结构的集合为D={d1,d2,d3,d4,d5},试指出下列各关系R所对应的数据结构B=(D,R)中哪些是线性结构，哪些是非线性结构。 （1）R={(d1,d2),(d2,d4),(d4,d2),(d2,d5),(d4,d1)}; ( 2 ) R={(d5,d4),(d4,d3),(d3,d1),(d1,d2)}; ( 3 ) R={(di,di+1)|i=4,3,2,1}; ( 4 ) R={(di,dj)|i 2.〉链表：扩展性强，易于删除，添加；内存中地址非连续；长度可以实时变化；适用于需要进行大量增添或删除元素操作而对访问元素无要求的程序。 （2）缺点 顺序表：插入，删除操作不方便；扩展性弱；不易删除，添加。 链表：不易于查询，索引慢。 （3）顺序表和链表的优缺点是互相补充的关系。 2.17 试比较单向链表与双向链表的优缺点。 答：（1）优点 单向链表：耗存储空间小； 双向链表：可以从任何一点开始进行访问; （2）缺点： 单向链表：访问时必须从头开始，耗时。 双向链表：耗存储空间大。 （3）两者为互补关系 2.22 CQ[0:10]为一循环队列，初态front=rear=1,画出下列操作后队的头，尾指示器状态： （1）d,e,h,g,入队； （2）d,e出队； （3）I,j,k,l,m入队； （4）b出队； 3.1 选择题 第3章线性表的链式存储 （1）两个有序线性表分别具有n个元素与m个元素且n≤m，现将其归并成一个有序表，其最少的比较次数是（ A ）。 A．n B．m C．n? 1D．m + n （2）非空的循环单链表 head 的尾结点（由 p 所指向）满足（ C ）。 A．p->next==NULL B．p==NULL C．p->next==head D．p==head （3）在带头结点的单链表中查找x应选择的程序体是（ C ）。 A．node *p=head->next; while (p && p->info!=x) p=p->next; if (p->info==x) return p else return NULL; B．node *p=head; while (p&& p->info!=x) p=p->next; return p; C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p; D．node *p=head; while (p->info!=x) p=p->next ; return p; （4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。 A．必须是连续的C．一定是不连续的B．部分地址必须是连续的D．连续不连续都可以 （5）在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（ B ）。 A．O(1) B．O(n)C．O(n2)D．O(n log2n )（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（D ）。 A．仅修改队头指针 C．队头、队尾指针都要修改B．仅修改队尾指针 D．队头,队尾指针都可能要修改 （7）若从键盘输入n个元素，则建立一个有序单向链表的时间复杂度为（ B ）。 A．O(n)B．O(n2)C．O(n3)D．O(n× log2n)（8）下面哪个术语与数据的存储结构无关（D）。 A．顺序表B．链表C．散列表D．队列 （9）在一个单链表中，若删除 p 所指结点的后续结点，则执行（ A ）。 A．p->next=p->next->next; B．p=p->next; p->next=p->next->next; C．p->next=p->next; D．p =p->next->next; （10）在一个单链表中，若 p 所指结点不是最后结点，在 p 之后插入 s 所指结点，则执行（ B ）。 A．s->next=p;p->next=s; B．s->next=p->next;p->next=s; C．s->next=p->next;p=s; D．p->next=s;s->next=p; 3.2 设计一个算法，求一个单链表中的结点个数。 【答】：单链表存储结构定义如下（相关文件：linklist.h） 数据结构课程作业_A 一、单选题。 1.(7分)对完全二叉树叙述正确的是（ C ）。 A.完全二叉树就是满二叉树 B.完全二叉树和满二叉树编号不对应 C.完全二叉树同一层上左子树未满不会有右子树 D. 以上都不正确 知识点：第六章 解析第六章第二节二叉树的性质 C ）。 2.(7分)堆的形状是一棵 （A. 二叉排序树 B.满二叉树 C.完全二叉树 D.一般的二叉树 知识点：第十章 解析第十章第四节堆排序 ）。 3.(7分)设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（B A. 8 B.7 C.6 D. 5 知识点：第六章 解析第六章第六节二叉树的性质 D ） 4.(7分)以下数据结构中哪一个是非线性结构？ （A. 队列 B.栈 C.线性表 D.二叉树 知识点：第一章 解析第一章第二节综合题目 A ）。 5.(7分)线性表的顺序存储结构是一种?的存储结构 （A. 随机存取 B.顺序存取 C.索引存取 D.散列存取 知识点：第二章 解析第二章第二节综合题目 C ）。 6.(7分)带头节点的单链表L为空的判定条件是 （ A. L==null B.L->data==null C.L->next==null D.L->next==data 知识点：第二章 解析第二章第三节线性链表 7.(7分)设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键 C ）。 字45为基准而得到一趟快速排序的结果是 （A. 40，42，45，55，80，83 B.42，40，45，80，85，88 C.42，40，45，55，80，85 D.42，40，45，85，55，80 知识点：第十章 解析第十章第三节综合题目 8.(7分)设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20 A ）。 为基准记录的一趟快速排序结束后的结果为 （ A. 10，15，14，18，20，36，40，21 B.10，15，14，18，20，40，36，21 C.10，15，14，20，18，40，36，2l D.15，10，14，18，20，36，40，21 知识点：第十章数据结构第一次作业
习题集
数据结构练习题第三章栈、队列和数组习题及答案
大大数据结构形考作业3
第二章数据结构习题作业
数据结构(第二版)习题答案第3章
数据结构课程三套作业及答案分析