第一章作业
一、选择题
1.被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的
这种关系称为( )。
A. 规则
B. 结构
C. 集合
D. 运算
2.在Data_Structure=(D,S)中，D是( )的有限集合。
A. 数据元素
B. 算法
C. 数据操作
D.数据对象
3.计算机所处理的数据一般具有某种关系，这是指( )之间存在的某种关系。
A. 数据与数据
B. 数据元素与数据元素
C. 元素内数据项与数据项
D. 数据文件内记录与记录
4.顺序存储表示中数据元素之间的逻辑关系是由( )表示的。
A. 指针
B. 逻辑顺序
C. 存储位置
D. 问题上下文
5.链接存储表示中数据元素之间的逻辑关系是由( )表示的。
A. 指针
B. 逻辑顺序
C. 存储位置
D. 问题上下文
6.从逻辑上可将数据结构分为( )。
A. 动态结构和静态结构
B. 紧凑结构和非紧凑结构
C. 内部结构和外部结构
D. 线性结构和非线性结构
7.以下选项属于线性结构的是( )。
A. 广义表
B. 二叉树
C. 串
D. 稀疏数组
8.以下选项属于非线性结构的是( )。
A. 广义表
B. 队列
C. 优先队列
D. 栈
9.以下属于逻辑结构的是( )
A. 顺序表
B. 散列表
C. 有序表
D. 单链表
10.一个完整的算法应该具有( )等特性。
A. 可执行性、可修改性和可维护性
B. 可行性、确定性和有穷性
C. 确定性、有穷性和可靠性
D. 正确性、可读性和有效性
11.若一个问题既可以用迭代方法也可以用递归方法求解，则( )的方法具有更高的时空效率。
A. 迭代
B. 递归
C. 先递归后迭代
D. 先迭代后递归
12.一个递归算法必须包括( )
A. 递归部分
B. 终止条件和递归部分
C. 迭代部分
D. 终止条件和迭代部
分
13.算法的时间复杂度与( )有关。
A. 问题规模
B. 源程序长度
C. 计算机硬件运行速度
D. 编译后执行程序的
质量
二、指出下列各算法的功能并求出其时间复杂度。
(1)
int Prime(int n){
int i=2,x=(int)sqrt(n); //sqrt(n)为求n的平方根
while(i<=x){
if(n%i==0)break;
i++;
}
if(i>x) return 1;
else return 0;
}
(2)
int sum1(int n){
int p=1,s=0;
for(int i=1;i<=n;i++){
p*=i;s+=p;
}
return s;
}
(3)
int sum2(int n){
int s=0;
for(int i=1;i<=n;i++){
int p=1;
for(int j=1;i<=i;j++) p*=j;
s+=p;
}
return s;
}
(4)
int fun(int n){
int i=1,s=1;
while(s return i; } (5) void mtable(int n){ for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++) cout< cout< } } 第二章作业 一、选择题 1. 在线性表中的每一个表元素都是不可再分的( ) A. 数据项 B. 数据记录 C. 数据元素 D. 数据字段 2. 顺序表是线性表的( )存储表示。 A. 有序 B. 连续 C. 数组 D. 顺序存取 3. 若长度为n 的非空线性表采用顺序存储结构，在表中的第i 个位置插入一个数据元素，i 的合法值 应该是( ) A. n i ≤≤1 B. 11+≤≤n i C. 10-≤≤n i D. n i ≤≤0 4. 若设一个顺序表的长度为n ，那么，在表中顺序查找一个值为x 的元素时，在等概率的情况下， 查找成功的数据平均比较次数为( ) A. n B. 2/n C. 2/)1(+n D. 2/)1(-n 5. 在长度为n 的顺序表的表尾插入一个新的元素的时间复杂度为( ) A. )(n O B. )1(O C. )(2n O D. )(log 2n O 6. 数据结构反映了数据元素之间的结构关系。单链表是一种( )。 A. 顺序存储线性表 B. 非顺序存储非线性表 C. 顺序存储非线性表 D. 非顺序存储线性表 7. 单链表又称为线性链表，在单链表上实施插入和删除操作( ) A. 不需移动结点，不需改变结点指针 B. 不需移动结点，只需改变结点指针 C. 只需移动结点，不需改变结点指针 D. 既需移动结点，又需改变结点指针 8. 已知L 是带头结点的单链表，则删除首元素结点的语句是( ) A. L=L->next; B. L->next=L->next->next; C. L=L->next->next; D. L->next=L; 9. 已知单链表A 长度为m ，单链表B 长度为n ，若将B 链接在A 的末尾，在没有链尾指针的情况下， 算法的时间复杂度应为( )。 A. )1(O B. )(m O C. )(n O D. )(n m O + 10. 给定有n 个元素的一维数组，建立一个有序单链表的时间复杂度是( ) A. )1(O B. )(n O C. )(2n O D. )log (2n n O 二、算法设计 1. 设计一个算法，从顺序表L 中(SqList L)删除具有给定值x(ElemType x)的所有元素。 2. 设计一个算法，从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。 3. 设计一个算法，在非递减有序的带头结点的单链表中删除值相同的多余结点。 第三章作业 一、选择题 1. 用S 表示进栈操作，用X 表示出栈操作，若元素的进栈顺序是1234，为了得到1342的出栈顺序， 相应的S 和X 的操作序列为( ) A. SXSXSSXX B. SSSXXSXX C. SXSSXXSX D. SXSSXSXX 2. 假设一个栈的输入序列是1，2，3，4，则不可能得到的输出序列是( ) A. 1,2,3,4 B. 4,1,2,3 C. 4,3,2,1 D. 1,3,4,2 3. 已知一个栈的进栈序列为1,2,3,…,n ，其输出序列的第一个元素是i ，则第j 个出栈元素是( )。 A. i j - B. i n - C. 1+-i j D. 不确定 4. 已知一个栈的进栈序列为n ,,3,2,1Λ，其输出序列是n p p p p ,,,,321Λ。若n p =1，则i p 的值是( ) A. i B. i n - C. 1+-i n D. 不确定 5. 已知一个栈的进栈序列为n ,,3,2,1Λ，其输出序列是n p p p p ,,,,321Λ。若31=p ，则2p 的值是( ) A.一定是2 B. 一定是1 C.可能是1 D. 可能是2 6. 已知一个栈的进栈序列为n p p p p ,,,,321Λ，其输出序列是n ,,3,2,1Λ。若13=p ，则1p 的值是( ) A.一定是2 B. 可能是2 C.不可能是2 D. 一定是3 7. 已知一个栈的进栈序列为n p p p p ,,,,321Λ，其输出序列是n ,,3,2,1Λ。若33=p ，则1p 的值是( ) A.一定是2 B. 可能是2 C.不可能是1 D. 一定是1 8. 已知一个栈的进栈序列为n p p p p ,,,,321Λ，其输出序列是n ,,3,2,1Λ。若1=n p ，则1p 的值是( ) A. 1+-i n B. i n - C. i D. 不确定 9. 设栈S 和队列Q 的初始状态均为空，元素1,2,3,4,5,6,7，依次进入S 。如果每个元素出栈后立即进 入队列Q ，且7个元素的出队顺序为2,4,3,6,5,1,7，则栈S 的容量至少是( ) A. 1 B. 2 C. 3 D. 4 10.对中缀表达式5 3- - + +求值，在求值过程中扫描到6时，操作数栈和操作符栈的内4(* 2 * 2 6 )3 2 * 容分别是( ) A. 3,2,4,2,2和+,*,(,+,* B. 3,2,4,4和+,*,(,+ C. 3,2,8和+,*,( D. 3,2,8,6和+,*,(,- 二、算法设计题 1. 详见《数据结构题集(C语言版)》第25页3.24。 2. 详见《数据结构题集(C语言版)》第25页 3.25。 第四章作业 11.串是一种特殊的线性表，其特殊性体现在( ) A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链式存储 D. 数据元素可以是多个 字符 12.设有两个串T和P，求P在T中首次出现的位置的运算叫做( )。 A. 求子串 B. 模式匹配 C. 串替换 D. 串连接 13.下面关于串的叙述中，哪一个是不正确的？（） A．串是字符的有限序列B．空串是由空格构成的串 C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储 14.串的长度是指（） A．串中所含不同字母的个数B．串中所含字符的个数 C．串中所含不同字符的个数D．串中所含非空格字符的个数 15.两个串相等的充分必要条件是（） A．串中所含的字符相同B．串中所含字符的个数相同，且对应位置上的字符也相同C．串中所含的字符个数相同D．串中对应位置上的字符相同 6. 已知p=”abcaabbabcabaacbacb”，求出next函数值。 第五章作业 一、选择题 16. 数组通常具有的操作是( ) A. 顺序存取 B. 直接存取 C. 散列存取 D. 索引存取 17. 多维数组实际上是由( )实现的。 A. 一维数组 B. 多项式 C. 三元组表 D. 简单变量 18. 在二维数组A[8][10]中，每一个数组元素A[i][j]占用3个存储空间，所有数组元素相继存放于一个 连续的存储空间中，则存放该数组至少需要的存储空间是( )。 A. 80 B. 100 C. 240 D. 270 19. 一个二维数组A[10][20]按行存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组 元素占1个存储字，则A[6][2]的地址为( ) A. 226 B. 322 C. 341 D. 342 20. 一个二维数组A[10][20]按列存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组 元素占1个存储字，则A[6][2]的地址为( ) A. 226 B. 322 C. 341 D. 342 21. 在二维数组A[9][10]中，每个数组元素占用3个存储单元，从首地址SA 开始按行连续存放，在这 种情况下，元素A[8][5]的起始地址为( ) A. SA+141 B. SA+144 C. SA+222 D. SA+255 22. 将一个n n ?的对称矩阵A 的下三角部分按存放在一个一维数组B 中，A[0][0]存放在B[0]中，那么 第i 行的对角元素A[i ][i ]在B 中的存放位置是( ) A. 2/)3(i i + B. 2/)1(i i + C. 2/)12(i i n +- D. 2/)12(i i n -- 23. 将一个n n ?的对称矩阵A 的上三角部分按存放在一个一维数组B 中，A[0][0]存放在B[0]中，那么 第i 行的对角元素A[i ][i ]在B 中的存放位置是( ) A. 2/)3(i i + B. 2/)1(i i + C. 2/)12(i i n +- D. 2/)12(i i n -- 24. 设A 是一个n n ?的对称矩阵，将A 的对角线及对角线上方的元素以列优先(以列为主序)的方式存 放在一维数组]2/)1([+n n B 中，则矩阵中任一元素),,0(j i n j i a ij ≤<≤在B 中的存放位置是( ) A. i j j ++2/)1( B. 12/)1(-+-i j j C. j i i ++2/)1( D. 12/)1(-+-j i i 25. 设n 阶三对角矩阵A 的三条对角线上的元素被按行压缩存储到一维数组B 中，A[0][0]存放于B[0]。 若某矩阵元素在B 中存放的位置在k ，那么该元素在原始矩阵中的行号i 是( ) A. ??3/)1(-k B. ??3/k C. ??3/)1(+k D. ??3/)1(-k 二、简答题 26. 设有一个3维数组]15][20][10[A ，按行优先存放于一个连续的存储空间中，每个数组元素占4 个存储字，首元素]0][0][0[A 的存储地址是1000，则]9][8][7[A 存放于什么地方。 27. 设有一个二维数组]][[n m A ，假设]0][0[A 存放位置在)10(644，]2][2[A 存放在)10(676，每个元 素占1个存储单元，问)10(]3][3[A 存放在什么位置？脚注(10)表示用十进制表示。 28. 对于一个n n ?矩阵A 的任一元素]][[j i a ，按行存储和按列存储时的地址之差是多少？(假设两种存 储的开始存储地址)0,0(LOC 以及元素所占存储单元数d 相同) 29. 设有n 阶三对角矩阵A ，将其3条对角线上的元素逐行存储到数组]33:0[-n B 中，使得]][[][j i A k B =，且]0][0[]0[A B =，求 (1) 用i ，j 表示k 的下标变换公式。 (2) 用k 表示i ，j 的下表变换公式。 30. 设有一个n n ?的对称矩阵A ，将其下三角部分按行压缩存放于一个一维数组B 中，]0][0[A 存放 于B [0]，试问：(1) 一维数组B 有多少个元素？(2) A 中的任意一个元素]][[j i A 应存于一维数组B 的什么下标位置？ 31. 设有一个n n ?的对称矩阵A ，将其上三角部分按列压缩存放于一个一维数组B 中，]0][0[A 存放 于B [0]，试问：(1) 一维数组B 有多少个元素？(2) A 中的任意一个元素]][[j i A 应存于一维数组B 的什么下标位置？ 第六章作业 一、选择题 32. 一颗有n 个结点的树的所有结点的度数之和为( )。 A.1-n B. n C. 1+n D. n 2 33. 设一颗高度为h 的满二叉树有n 个结点，其中有m 个叶结点，则( ) A.m h n += B. n m h 2=+ C. 1-=h m D. 12-=h n 34. 一颗有124个叶结点的完全二叉树最多有( )个结点。 A. 247 B. 248 C. 249 D. 250 35. 一颗有129个叶结点的完全二叉树最少有( )个结点。 A. 254 B. 255 C. 257 D. 258 36. 设完全二叉树的第6层有24个叶结点，则此树最多有( )个结点。 A. 55 B. 79 C. 81 D. 127 37. 具有1000个结点的完全二叉树的次底层的叶结点个数为( )。 A. 11 B. 12 C. 24 D. 36 38. 用顺序存储的方法将n 个结点的完全二叉树中所有结点按层逐个顺序存放在一维数组][n R 中，当 编号为0的根结点存放于]0[R 时，若结点][i R 有左孩子，则左孩子是( )。 A.]12[-i R B. ]2[i R C. ]12[+i R D. ]22[+i R 39. 用顺序存储的方法将n 个结点的完全二叉树中所有结点按层逐个顺序存放在一维数组][n R 中，当 编号为0的根结点存放于]0[R 时，若结点][i R 有右孩子，则右孩子是( )。 A.]12[-i R B. ]2[i R C. ]12[+i R D. ]22[+i R 40. 二叉树的叶结点在前序、中序和后序遍历过程中的相对顺序( )。 A. 发生改变 B. 不发生变化 C. 无法确定 D. 以上均不对 41. 设n ，m 为一颗二叉树上的两个结点，在该二叉树的中序遍历序列中n 在m 前的条件是( )。 A. n 在m 右方 B. n 是m 的祖先 C. n 在m 左方 D. n 是m 的子孙 42. 设一颗二叉树的前序序列为abdec ，中序序列为dbeac ，则该二叉树的后序遍历顺序是( )。 A. abdec B. debac C. debca D. abedc 43. 设一颗二叉树的中序序列为badce ，后序序列为bdeca ，则该二叉树的前序遍历顺序是( )。 A. adbec B. decab C. debac D. abcde 44. 对二叉树的结点从1开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的 左、右孩子中，其左孩子编号小于其右孩子编号，则可采用( )遍历实现二叉树的结点编号。 A. 先序 B. 中序 C. 后序 D. 层次序 45. 如果T 2是由有序树T 转换成的二叉树，那么T 中结点的先根遍历顺序对应T 2中结点的( )遍历 顺序。 A. 前序 B. 中序 C. 后序 D. 层次序 46. 如果T 2是由有序树T 转换成的二叉树，那么T 中结点的后根遍历顺序对应T 2中结点的( )遍历 顺序。 A. 前序 B. 中序 C. 后序 D. 层次序 47. 用n 个权值构造出来的Huffman 树共有( )个结点。 A. 12-n B. n 2 C. 12+n D. 1+n 48. 由权值为8,4,5,7的4个叶结点构造一颗Huffman 树，该树的带权路径长度为( )。 A. 24 B. 36 C. 48 D. 72 二、简答题 49. 设二叉树根结点所在层次为1，树的深度d 为距离根最远的叶结点所在的层次，试回答以下问题： (1) 试精确给出深度为d 的完全二叉树的不同二叉树的棵数；(2) 试精确给出深度为d 的满二叉树的不同二叉树棵数。 50. 如果一棵树有1n 个度为1的结点，有2n 个度为2的结点，……，有m n 个度为m 的结点，试问有多 少个度为0的结点？ 51. 已知一棵二叉树的前序遍历序列为ABECDFGHIJ ，中序遍历序列为EBCDAFHIGJ 。(1)画出这棵二叉 树；(2)给出这棵二叉树后序遍历序列；(3)画出这棵二叉树转换成对应的树(或森林)。 52. 假定用于通信的电文仅有8个字母A,B,C,D,E,F,G,H 组成，各字母在电文中出现的频率分别为 5,25,3,6,10,11,36,4。试为这8 个字母设计不等长Huffman 编码，并给出该电文的总码数。 三、算法设计 53.设二叉树的存储结构为二叉链表，编写一个递归算法，统计二叉树中度为1的结点个数。 54.设二叉树的存储结构为二叉链表，编写一个递归算法，统计二叉树中度为2的结点个数。 55.设树T以孩子-兄弟链表作为其存储表示，编写一个算法统计树T的叶结点个数。 56.设树T以孩子-兄弟链表作为其存储表示，编写一个算法计算树T的高度。 第七章作业 一、选择题 1. 具有n 个顶点且每一对不同顶点间都有一条边的无向图被称为( )。 A. 完全无向图 B. 无向连通图 C. 无向强连通图 D. 无向树图 2. 一个有n 个顶点的无向图中边数最多有( )条。 A. n B. )1(-n n C. 2/)1(-n n D. n 2 3. 对于具有)1(>n n 个顶点的强连通图，其有向边条数至少是( ) A. 1+n B. n C. 1-n D. 2-n 4. 设G 是一个非连通无向图，有15条边，则该图的顶点数至少有( )个。 A. 5 B. 6 C. 7 D. 8 5. 在一个具有n 个顶点的有向图中，若所有顶点的岀度之和为s ，则所有顶点的入度之和为( )。 A. s B.s -1 C. s +1 D. n 6. 一个有n 个顶点和n 条边的无向图一定是( )。 A. 重连通图 B. 不连通图 C. 无环的 D. 有环的 7. 无向图的邻接矩阵是一个( )。 A. 对称矩阵 B. 零矩阵 C. 上三角矩阵 D. 对角矩阵 8. 有n 个顶点和e 条边的无向图采用邻接矩阵存储，零元素的个数为( )。 A. e B. e 2 C. e n -2 D. e n 22- 9. 带权有向图G 用邻接矩阵A 存储，则顶点i 的入度等于A 中( )。 A. 第i 行非∞的元素之和 B. 第i 列非∞的元素之和 C. 第i 行非∞且非0的元素个数 D. 第i 列非∞且非0的元素个数 10. 设图有n 个顶点和e 条边，采用邻接矩阵时，遍历图的顶点所需时间为( )。 A. )(n O B. )(2n O C. )(e O D. )(ne O 11. 设图有n 个顶点和e 条边，采用邻接表时，遍历图的顶点所需时间为( )。 A. )(e n O + B. )(2n O C. )(e O D. )(ne O 12. 图的深度优先搜索类似于树的( )次序遍历。 A. 先根 B. 中根 C. 后根 D. 层 13. 图的广度优先搜索类似于树的( )次序遍历。 A. 先根 B. 中根 C. 后根 D. 层 14. 采用邻接表存储的图的深度优先搜索算法类似于二叉树的( )。 A. 中序遍历 B. 前序遍历 C. 后序遍历 D. 层次遍历 15. 采用邻接表存储的图的广度优先搜索算法类似于二叉树的( )。 A. 中序遍历 B. 前序遍历 C. 后序遍历 D. 层次遍历 16. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是( )。 A. 强连通图 B. 连通图 C. 有回路 D. 一棵树 17. 如果一个连通网络G 中各边权值互不相同，权重最小的边一定包含在G 的( )生成树中。 A. 最小 B. 任何 C. 广度优先 D. 深度优先 18. 任何一个连通图的最小生成树( )。 A. 只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在 19. 一个有n 个顶点和e 条边的连通图的生成树有( )条边。 A. n B. e C. 1-n D. 1+n 20. 设一个n 个顶点的带权连通图有n n 2log 条边，则应该选通( )算法来求这个图的最小生成树， 从而使计算时间较少。 A. Prim B. Kruskal C. DFS D. BFS 21. 求最短路径的Dijkstra 算法的时间复杂度为( )。 A. )(n O B. )(e n O + C. )(2n O D. )(ne O 22. 求最短路径的Floyd 算法的时间复杂度为( )。 A. )(n O B. )(ne O C. )(2n O D. )(3n O 23. 设有向图具有n 个顶点和e 条边，如果用邻接表作为它的存储结构，则拓扑排序的时间复杂度为( )。 A. )(n O B. )(e n O + C. )(2n O D. )(ne O 24. 设有向图具有n 个顶点和e 条边，如果用邻接矩阵作为它的存储结构，则拓扑排序的时间复杂度 为( )。 A. )log (2e n O B. )(e n O C. )(2n O D. )(ne O 二、应用题 25. 针对图1所示的有向图，画出该图的邻接矩阵、邻接表和逆邻接表。 图1 图2 26. 对图2所示的无向图，从顶点a 开始进行深度优先遍历，给出2个可得到的顶点访问序列；从顶 点a 开始进行广度优先遍历，给出2个可得到的顶点访问序列。 27. 已知一个带权连通图如图3所示，分别使用Prim 算法和Kruskal 算法求其最小生成树。 图3 图4 28. 已知一个带权有向图如图4所示，用Dijkstra 算法求从顶点a 到其余各顶点的最短路径及路径长度。 29. 如图所示的AOE 网，求 (1) 完成此工程最少要多少天(设弧上的权值为天数)； (2) 每项活动i a 的最早开始时间)(i a e 和最迟开始时间)(i a l ； (3) 哪些是关键活动； (4) 是否存在某些活动，当其提高速度后能使整个工程缩短工期? 图5 第九章作业 一、选择题 30. 顺序查找算法适用于( )。 A. 线性表 B. 查找树 C. 查找网 D. 连通图 31. 顺序查找法适用于线性表的( )。 A.散列存储 B.压缩存储 C. 索引存储 D. 顺序或链接存储 32. 采用顺序查找方式查找长度为n 的顺序表时，平均查找长度为( ) A. n B. 2/n C. 2/)1(+n D. 2/)1(-n 33. 如果有5个关键吗{a,b,c,d,e }放在顺序表中，他们的查找概率分别为{0.35,0.25,0.20,.015,0.05}，可使 平均查找长度达到最小的存放方式是( )。 A. d,a,b,c,e B. e,d,c,b,a C. a,b,c,d,e D. a,c,e,d,b 34. 对于长度为n 的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素的查找成功 的平均查找长度为( ) A. 4/n B. 2/n C. 2/)1(+n D. 2/)1(-n 35. 对线性表进行折半查找时，要求线性表必须( ) A. 以顺序方式存储 B. 以链接方式存储 C. 以顺序方式存储，且结点按关键吗有序排列 D. 以链接方式存储，且结点按关键吗有序排列 36. 采用折半查找法查找长度为n 的有序顺序表时，平均查找长度为( ) A. )(n O B. )(log 2n O C. )(2n O D. )log (n n O 37. 对于长度为18的有序顺序表，若采用折半查找，则查找第15个元素的查找次数为( )。 A. 3 B. 4 C. 5 D. 6 38. 已知有序顺序表(13,18,24,35,47,50,62,83,90,115,134)，若采用折半查找法查找值为18的元素时， 查找成功的数据比较次数为( )。 A. 1 B. 2 C. 3 D. 4 39. 使用散列法时确定元素存储地址的依据是( )。 A. 元素的序号 B. 元素个数 C. 关键吗 D. 非码属性 40. 设一个散列表中有n 个元素，用散列法进行查找的平均查找长度是( )。 A. )1(O B. )(n O C. )log (2n O D. )(2 n O 41. 使用散列函数将元素的关键吗映射为散列地址时，常会发生冲突。此时的冲突是指( )。 A. 两个元素具有相同的序号 B. 两个元素的关键码不同，而非关键码相同 C. 不同关键码对应到相同的存储地址 D. 装载因子过大，数据元素过多 42. 计算出的地址分布最均匀的散列函数是( )。 A. 数值分析法 B. 除留余数法 C. 平方取中法 D. 折叠法 43. 将10个元素散列到大小为100000个元素的散列表中，( )产生冲突。 A. 一定会 B. 一定不会 C. 仍可能会 D. 以上都不对 44. 采用线性探测法解决冲突时计算出的一系列“下一个空位”( )。 A. 必须大于等于原散列地址 B. 必须小于等于原散列地址 C. 可以大于或小于但不等于原散列地址 D. 对地址在何处没有限制 45. 包含有4个结点的元素值互不相同的二叉查找树有( )棵。 A. 4 B. 6 C. 10 D. 14 46. 利用逐个数据插入的方法建立序列{35,45,25,55,50,10,15,30,40,20}对应的二叉查找树后，查找元素 20需要进行( )次元素之间的比较。 A. 4 B. 5 C. 7 D. 10 47. 一颗高度为h 的AVL 树，若其每个非叶子结点的平衡因子都是0，则该树共有( )个结点。 A. 121--h B. 12-h C. 121+-h D. 12-h 48. 高度为7的AVL 树最少有( )个结点。 A. 12 B. 21 C. 33 D. 54 49. 高度为7的AVL 树最多有( )个结点。 A. 63 B. 64 C. 65 D. 127 二、应用题 50. 设有一个关键码的输入序列{55,31,11,37,46,73,63}，从空树开始构造AVL 树，画出每加入一个新结 数据结构大作业 作业题目：职工信息管理系统 姓名： 学号： 班级: 指导教师: 日期： 一、主要功能： 这个职工信息管理系统是由C语言编写的程序，它用起来很方便又很灵活。它由输入职工信息，输出职工信息，按职工号，部门号，工资排序，按职工号，部门号，工资来输出职工的所有信息。删除有关职工的所有信息，保存职工的所有信息并退出等11个模块儿组成。 二、实验环境：C语言、C++、C# 等等。 三、功能说明： 下面按步骤来介绍一下，职工信息管理系统的基本操作。 这是运行程序以后出现的主界面。如图（1）所示： 图（1）主界面 1.输入职工的信息 该模块儿的功能是分别输入职工的姓名，职工号，部门号，工资等信息。每次输入职工的所有信息以后，界面上会显示出《输入完成！》的命令。如图（2）所示： 图（2）输入职工信息 2.输出所有的职工信息 该模块儿的功能是显示出有关职工的所有信息。操作如图（3）所示： 图（3）输出所有的职工信息 3.按职工号排序 该模块儿的功能是按职工号排序所有的职工。我们按3的时候，界面上会显示出《排序完成！》的命令。如图（4）所示： 图（4）按职工号排序 4.输出所有的职工号码 该模块儿的功能是显示出已排序好的所有职工的号码。操作如图（5）所示： 图（5）输出所有的职工号 5.按部门号排序 该模块儿的功能是按部门号排序所有职工的部门号。我们按5的时候，界面上会显示出《排序完成！》的命令。如图（6）所示： 图（6）按部门号排序 6.输出所有的部门号 该模块儿的功能是显示出已排序好的所有部门号。操作如图（7）所示： 图（7）输出所有的部门号 7.按职工的工资排序 该模块儿的功能是按工资排序所有职工的工资。我们按7的时候，界面上会显示出《排序完成！》的命令。如图（8）所示： 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（） A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 习题1 一、单项选择题 A1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 C2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 D3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 B4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) CA5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 习题六树和二叉树6.1 单项选择题 (A) (B) (C) (D) 图8.7 4棵二叉树 1. 如图8.7所示的4棵二叉树，_ _不是完全二叉树。 图8.8 4棵二叉树 2. 如图8.8所示的4棵二叉树，__B_是平衡二叉树。 3. 在线索化二叉树中，t所指结点没有左子树的充要条件是B__o A. t —> left二NULL B. t —> ltag=1 C. t —> ltag=1 且t —> left=NULL D. 以上都不对 4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说 法_B__ o A.正确 B. 错误 5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 _A__。 A.正确 B. 错误 6. 由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法 _B_o A.正确 B. 错误 7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为—B__o A. 2h B. 2h-1 C. 2h+1 D. h+1 a 8. 如图8.9所示二叉树的中序遍历序列 B o 图8.9 一棵二叉树 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 9. 已知某二叉树的后序遍历序列是d abec，中序遍历序 列是debac，它的前序遍历 序列是D ___ 。 A. acbed B. decab C. deabc D. cedba 10. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 B 。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 11?假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结 点数为个。B A. 15 B. 16 C. 17 D. 47 12. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是D _____ 。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 13. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、 小于其右孩子的值。这种说法__B__ o A.正确 B. 错误 14. 按照二叉树的定义，具有3个结点的二叉树有_。__种。 A. 3 B. 4 C. 5 D. 6 15. 一棵二叉树如图8.10所示，其中序遍历的序列为 浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验九栈的应用 学生姓名丁汀专业班级信管1006 学号31001444 实验成绩指导老师（签名）日期 一.实验目的和要求 1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。 2、掌握利用栈各种操作来进行具体的实际应用。 3、加强综合程序的分析、设计能力。 二.实验内容 1、共享栈的设置，问题描述如下： 在一个数组空间stack[MaxSize]中可以同时存放两个顺序栈，栈底分别处在数组的两端，当第1个栈的栈顶指针top1等于－1时则栈1为空，当第2个栈的栈顶指针top2等于MaxSize时则栈2为空。两个栈均向中间增长，当有元素向栈1进栈时，使top1增1得到新的栈顶位置，当有元素向栈2进栈时，使top2减1得到新的栈顶位置。当top1==top2-1或top1+1==top2时，存储空间用完，无法再向任一栈做进栈操作，此时可考虑给出错误信息并停止运行。 要求： ⑴给出共享栈的顺序存储类型定义。 ⑵给出共享栈的抽象数据类型定义。 ⑶建立头文件test9_stack.h，包含共享栈的基本操作实现函数；建立主程序文件test9.cpp，在主函数中对共享栈的各个操作进行测试。 2、利用上述共享栈，实现火车车厢的调度模拟 设火车车厢分为三类：硬座、硬卧、软卧，分别用A、B、C表示。下图描述车厢调度的示意图，图中右端为排列无序的车厢，左端为调度后的车厢排列，使得所有软卧车厢在最前面、所有硬卧车厢在中间、所有硬座车厢在最后。 编程模拟上述车厢调度过程。 提示：两个辅助铁轨相当于两个栈，右端车厢进入用相应字符串给出，如“BBACBCAABBCAA”，左端车厢的用新生成的字符串给出。在test9_stack.h 给出模拟函数，并在主函数中进行调用测试。 东北农业大学网络教育学院 数据结构作业题（一） 一、选择题（每题2分，共20分） 1．在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。 A、O(n) B、O (n/2) C、O (1) D、O (n2) 2．带头结点的单链表first为空的判定条件是（）。 A、first == NULL; B、first->link == NULL; C、first->link == first; D、first != NULL; 3．在一棵树中，（）没有前驱结点。 A、分支结点 B、叶结点 C、树根结点 D、空结点 4．在有向图中每个顶点的度等于该顶点的（）。 A、入度 B、出度 C、入度与出度之和 D、入度与出度之差 5．对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。 A、20 B、18 C、25 D、22 6．下列程序段的时间复杂度为（）。 s=0； for(i=1；i 作业1.线性表 （1） 在有序单链表中设计一高效算法删除所有值大于mink 且小于maxk 的元 素；思考题：你能将上述算法改为双向循环链表吗？ （2） 将带表头结点的单链表就地逆置 （3） 将顺序表逆置，要求用最少的附加空间 （4） 在有序顺序表中插入x ，插入后仍为有序的。 作业2. 栈、队列、数组 1．若进栈序列为abcd ，请给出全部可能的出栈序列和不可能的出栈序列。 2．循环队列如何判断队满和队空？ 3．写出下面稀疏矩阵的三元组顺序表和十字链表表示。 4．设A 为n 阶对称阵，采用压缩存储存放于一维数组F[n(n+1)/2]中（从F[0] 开始存放），请分别给出存放上三角阵时任一矩阵元素aij （1≤i,j ≤n ）的地址 计算公式和存放下三角阵时任一矩阵元素aij （1≤i,j ≤n ）的地址计算公式。 作业3.树与二叉树 一、问答题 1、请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 2、已知二叉树的先序遍历序列是EABDCFHGIKJ ，中序遍历序列是 ABCDEFGHIJK ，请构造二叉树，并写出其层次遍历序列和后序遍历序列。 3、将图1所示的森林转换成一棵二叉树。 A B C D G H I J K E F L 图1 4、将如图2所示的二叉树还原成树或森林 400000503008000000000700200000A ?????? ??=???????? A B C D G H I J K E F L L L 图2 5、假设用于通信的电文由7个字母组成，字母在电文中出现的频率分别为 0.17、0.09、0.12、0.06、0.32、0.03、0.21。试为这7个字母设计哈夫曼编码，并计算其带权路径长度。 二、二叉树采用二叉链表存储，试设计算法实现： （1）设计递归算法实现二叉树中所有结点的左右孩子交换。 （2）统计以值为X 的结点为根的子树中叶子结点的数目。 （3）设计算法求二叉树的高 作业4 图 一、简答题： 1. 已知带权无向图如图所示： (1). 根据普里姆（Prim ）算法，求它的从顶点a 出发的最小生成树(写出过程，即添加顶点、边次序)； (2). 根据克鲁斯卡尔（Kruskal ）算法，求该图的最小生成树(写出过程，即添加边次序)。 2．已知带权有向图如图所示： (1). 画出该图的邻接矩阵存储结构； (2). 请写出该图的一个拓扑有序序列； (3). 求从顶点a 到其余各顶点之间的最短路经及最短路经长度，并给出计算过程。 二、编程题： 用类C 语言设计算法判断有向图中是否存在由顶点v s 到v t 的路径（t s ），要求说明有向图的存储方式。 作业5 查找与排序 一、简答题： 1. 设有关键字序列{25，40，33，47，12，66，72，87，94，22，5，58}，散列 表长12，散列函数为h(key)=key%11，用线性探查再散列、链地址法处理冲突，请分别画出散列表，并计算在等概率情况下的查找成功的平均查找长度。 数据结构实验讲义 一实验步骤 随之计算机性能的提高，它所面临的软件开发的复杂度也日趋增加。然而，编制一个10，000行的程序的难度绝不仅仅是一个5，000行的程序两倍，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实习题的复杂度远不如(从实际问题中提出来的)一个“真正的，，软件，但为了培养一个软件工作者所应具备的科学工作的方法和作风，我们制订了如下所述完成实习的五个步骤：’ (一)问题分析和任务定义 通常，实习题目的陈述比较简洁，或者说是有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。注意：本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么?是否接受非法的输入?对非法输入的回答方式是什么等。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式的输入数据。 (二)数据类型和系统设计 在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的规格说明)，各个主要模块的算法，并画出模块之间的调用关系图。详细设计的结果是对数据结构和基本操作的规格说明作出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类c语言写出函数形式的算法框架。在求精的过程中，应尽量避免陷入语言细节，不必过早表述辅助数据结构和局部变量。 (三)编码实现和静态检查 编码是把详细设计的结果进一步求精为程序设计语言程序。程序的每行不要超过60个字符。每个函数体，即不计首部和规格说明部分，一般不要超过40行，最长不得超过60行，否则应该分割成较小的函数。要控制if语句连续嵌套的深度。其他要求参见第一篇的 数据结构课程作业_A 交卷时间：2017-08-09 10:08:51 一、单选题 1. (7分)设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置脚注(10)表示用10进制表示。 A. 688 B. 678 C. 692 D. 696 纠错 得分： 7 知识点：第五章 展开解析 答案 C 解析第五章第二节综合题目 2. (7分)若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 纠错 得分： 0 知识点：第九章 展开解析 答案 D 解析第九章第一节有序表的查找 (7分)设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 纠错 得分： 7 知识点：第七章 展开解析 答案 A 解析第七章第一节综合题目 4. (7分)若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=_____ A. n2+1 B. n2-1 C. n2+2 D. n2-2 纠错 得分： 7 知识点：第六章 展开解析 答案 A 解析第六章第二节二叉树的性质 5. (7分)栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 得分： 7 知识点：第三章 展开解析 答案 A 解析第三章第一节栈的表示和实现 6. (7分)设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A. 25 B. 10 C. 7 D. 1 纠错 得分： 7 知识点：第九章 展开解析 答案 B 解析第九章第一节有序表的查找 7. (7分)设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 A. 20 B. 256 C. 512 D. 1024 纠错 得分： 7 知识点：第六章 展开解析 答案 C 解析第六章第六节二叉树的性质 《数据结构》填空作业题答案 第 1 章绪论（已校对无误） 1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。 2．程序包括两个内容：数据结构和算法。 3.数据结构的形式定义为：数据结构是一个二元组：Data Structure =（ D， S）。 4.数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。 5.数据的逻辑结构可以分类为线性结构和非线性结构两大类。 6.在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。 7.在树形结构中，数据元素之间存在一对多的关系。 8.数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。 9.数据的逻辑结构包括线性结构、树形结构和图形结构 3 种类型，树型结构和有向 图结构合称为非线性结构。 10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑 关系由存储单元位置的邻接关系来体现。 11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑 关系由附加的指针域来体现。 12.数据的存储结构可用 4 种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。 13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。 14.数据结构在物理上可分为顺序存储结构和链式存储结构。 15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数 据的实现方法。 16.数据元素可由若干个数据项组成。 17.算法分析的两个主要方面是时间复杂度和空间复杂度。 18.一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂 度是用该算法在运行过程中所占用的存储空间的大小来度量的。 19.算法具有如下特点：有穷性、确定性、可行性、输入、输出。 20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切 的定义，并在有穷时间内计算出结果。 21. 下面程序段的时间复杂度为㏒ 3n 。 1 形考作业一 题目1 把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。 选择一项： A. 逻辑结构 B. 给相关变量分配存储单元 C. 算法的具体实现 D. 物理结构 题目2 下列说法中，不正确的是（）。 选择一项： A. 数据可有若干个数据元素构成 B. 数据元素是数据的基本单位 诃C.数据项是数据中不可分割的最小可标识单位 产_D.数据项可由若干个数据元素构成 题目3 一个存储结点存储一个（）。 选择一项： A. 数据结构 B. 数据类型 C. 数据项 i_D.数据元素 题目4 数据结构中，与所使用的计算机无关的是数据的（）。 选择一项： 题目5 下列的叙述中，不属于算法特性的是（选 ）°择一项： A. 有穷性 B. 可行性 * C.可读性 D. 输入性 题目6 正确 获得2.00分中的2.00分 ◎ A.研究算法中的输入和输出的关系 B. 分析算法的易懂性和文档性 I 圏 C.分析算法的效率以求改进 D.找出数据结构的合理性 题目7 算法指的是（ ）。 选择一项： A. 排序方法 B. 解决问题的计算方法 C. 计算机程序 * D.解决问题的有限运算序列 题目8 算法的时间复杂度与（ 选择一项： A. 所使用的计算机 因B.数据结构 D. i 题目10 设有一个长度为n 的顺序表，要删除第i 个元素移动元素的个数为（ ）。 选择一项： ）有关。 D. 计算机的操作系统 题目9 设有一个长度为n 的顺序表，要在第i 个元素之前（也就是插入元素作为新表的第 i 个元 素），插入一个元素，则移动元素个数为（ ）。 选择一项: A. n-i+1 3 B. n-i-1 rj C. n-i C.算法本身 /* 家谱管理系统 任务：实现具有下列功能的家谱管理系统 功能要求： 1). 输入文件以存放最初家谱中各成员的信息，成员的信息中均应包含以下内容： 姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡），也可附加其它信息、但不是必需的。 2). 实现数据的存盘和读盘。 3). 以图形方式显示家谱。 4). 显示第n 代所有人的信息。 5). 按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）。 6). 按照出生日期查询成员名单。 7). 输入两人姓名，确定其关系。 8). 某成员添加孩子。 9). 删除某成员（若其还有后代，则一并删除）。 10).修改某成员信息。 11).按出生日期对家谱中所有人排序。 12).打开一家谱时，提示当天生日的健在成员。 要求：建立至少30个成员的数据，以较为直观的方式显示结果，并提供文稿形式以便检查。界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求相关数据要存储在数据文件中。测试数据：要求使用1、全部合法数据；2、局部非法数据。进行程序测试，以保证程序的稳定。 测试数据及测试结果请在上交的资料中写明； */ #include 第1章绪论 1. 填空 （1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 （2）（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 （3）从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 （4）数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 （5）算法具有五个特性，分别是（）、（）、（）、（）、（）。 （6）在一般情况下，一个算法的时间复杂度是（）的函数。 （7）设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链式存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 ⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。 A 树 B 图 C 线性表 D 集合 ⑶算法指的是（）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 ⑷下面（）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 ⑸算法分析的目的是（），算法分析的两个主要方面是（）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性H 数据复杂性和程序复杂性 3. 判断题 （1）算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。 （2）每种数据结构都具备三个基本操作：插入、删除和查找。 （3）逻辑结构与数据元素本身的内容和形式无关。 （4）基于某种逻辑结构之上的基本操作，其实现是唯一的。 4. 分析以下各程序段，并用大O记号表示其执行时间。 习题1 一、单项选择题 1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) 5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性 1．数据的最小单位是（ A ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．下面关于线性表的叙述错误的是（D）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C）。 (A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M 4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。 (A) BADC(B)BCDA (C) CDAB (D) CBDA 5．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C）。 (A) 9 (B) 10 (C) 11(D) 12 6．下面程序的时间复杂为（B） for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} (A) O(n) (B) O(n2)(C) O(n3) (D) O(n4) 7．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（C）。 (A) q=p->next；p->data=q->data；p->next=q->next；free(q)； (B) q=p->next；q->data=p->data；p->next=q->next；free(q)； (C) q=p->next；p->next=q->next；free(q)； (D) q=p->next；p->data=q->data；free(q)； 8．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。 (A)O(n) (B) O(nlog2n) (C) O(1)(D) O(n2) 9．设一棵二叉树的深度为k，则该二叉树中最多有（D ）个结点。 (A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1 10．设用链表作为栈的存储结构则退栈操作（ B ）。 (A) 必须判别栈是否为满(B) 必须判别栈是否为空 (C) 判别栈元素的类型(D) 对栈不作任何判别 11．函数substr(“DATASTRUCTURE”，5，9)的返回值为（A ）。 (A) “STRUCTURE”(B) “DATA” (C) “ASTRUCTUR”(D) “DATASTRUCTURE” 12．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（ C）。 (A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1(D) N0=2N1+l 13．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（B ）。 (A) 空或只有一个结点(B) 高度等于其结点数 (C) 任一结点无左孩子(D) 任一结点无右孩子 14. 深度为k的完全二叉树中最少有（ B ）个结点。 (A) 2k-1-1 (B) 2k-1(C) 2k-1+1(D) 2k-1 数据结构课程设计 题目：长整数四则运算 班级：信管12-1 学号：1201050642 姓名：庄术洁 指导老师：刘晓庆 2014年5月22日 一、需求分析 1、利用双向循环链表实现长整数的存储，每个结点含一个整数变量。任何整形变量的范围是—（2^15—1）~（2^15—1）。输入和输出形式：按中国对于长证书的表示习惯，每四位一组，组间用逗号隔开。 2、测试数据 (1) 0; 0;应输出“0” (2)—2345,6789；—7654,3211；应输出“—1,0000,0000”。 (3)—9999,9999；1,0000,0000,0000；应输出“9999,0000,0001”。 (4)1,0001,0001；—1,0001,0001；应输出“0”。 (5)1,0001,0001；—1,0001,0000；应输入“1”。 (6)—9999,9999,9999；—9999,9999,9999；应输出“—1,9999,9999,9998”。 (7)1,0000,9999,9999；1应输出“1,0001，0000,0000”。 二、概要设计 为上述程序功能，应以有序表实现长整数的存储，为此，需要抽象数据类型：有序表 (8)有序表的抽象数据类型定义为： ADT Dulinklist{ 数据对象： D={ai|ai为带符号整数，1，2,…,n,n>=0} 数据关系：R1={ 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 《数据结构》填空作业题答案 第1章绪论（已校对无误） 1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。 2．程序包括两个内容：数据结构和算法。 3. 数据结构的形式定义为：数据结构是一个二元组：Data Structure =（D，S）。 4. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。 5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。 6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。 7. 在树形结构中，数据元素之间存在一对多的关系。 8. 数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。 9. 数据的逻辑结构包括线性结构、树形结构和图形结构 3 种类型，树型结构和有向图结构合称为非线性结构。 10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。 11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。 12. 数据的存储结构可用 4 种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。 13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。 14. 数据结构在物理上可分为顺序存储结构和链式存储结构。 15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。 16. 数据元素可由若干个数据项组成。 17. 算法分析的两个主要方面是时间复杂度和空间复杂度。 18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂 度是用该算法在运行过程中所占用的存储空间的大小来度量的。 19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出。 20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切 的定义，并在有穷时间内计算出结果。 21. 下面程序段的时间复杂度为㏒3n 。 数据结构课程设计大作业 题目纸牌游戏 专业计算机科学与技术 学生姓名 __________________ 学号 _____________________ 指导教师 __________________ 完成日期 __________________ 信息与工程学院 目录 一、实验内容概述（设计任务与技术要求） (1) 二、实验目的概述（总体设计方案） (1) 三、解题思路的描述（数据结构和算法的设计）： (1) 四、源程序清单（源程序中应该附有必要的注释） (2) 五、程序调试及测试结果 (4) 六、结论 (4) 七、参考文献 (5) 【内容摘要】 编号为1~52的牌，正面向上，从第二张开始，以2为基数，是2的倍数的牌翻一次，直到最 后一张牌；然后，从第三张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从 第四张开始，以4为基数，是4的倍数的牌翻一次，直到最后一张牌；依次类推，知道所有以52 为基数的牌翻过一次。输出：这时正面向上的牌有哪些？ 【关键字】 52张纸牌，倍数，基数，数组 【Abstract 】 Numbered 1 to 52 cards, face up, starting from the second to 2 as the base, is a multiple of 2 cards turning on ce, un til the last card; and the n, begi nning from the third to 3 as the base,is a multiple of 3 cards turning once, un til the last card; and the n start from the fourth to 4 as the base, is a multiple of 4 cards turning once, un til the last card; and so on, that was all of 52base of the card turned over on ce.Output: At this time what the cards face up? 【Key words 】 52 cards, multiple, base, array数据结构大作业含源代码
数据结构第1章作业
数据结构习题及参考答案
数据结构书面作业练习题
数据结构大作业
数据结构作业题及参考答案
数据结构作业
数据结构大作业要求
数据结构课程作业
《数据结构》填空作业题(答案)
数据结构(本)形考作业答案
家谱管理系统 -数据结构大作业
数据结构作业第1章
数据结构习题及参考答案 .
数据结构第一章课后习题与答案
数据结构作业(附答案)
数据结构大作业
数据结构习题与答案
《数据结构》填空作业题(答案)
数据结构大作业-纸牌游戏
相关主题
文本预览