（0012）《数据结构》复习思考题
一、选择题
1、某二叉树的先序序列和后序序列正好相同，则该二叉树一定是( )的二叉树。
A.空或只有一个结点
B.高度等于其结点数
C.任一结点无左孩子
D.任一结点无右孩子
2.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(log2n)的是( )
A.堆排序
B.冒泡排序
C.直接选择排序
D.快速排序
3.下列排序算法中，( )算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。
A.堆排序
B.冒泡排序
C.快速排序
D.SHELL排序
4.一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是( )
A. 2 3 4 1 5
B. 5 4 1 3 2
C. 2 3 1 4 5
D. 1 5 4 3 2
5.设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则其元素个数为( )
A. r-f
B. r-f+1
C. (r-f) mod n+1
D. (r-f+n) mod n
6.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( )存储方式最节省时间。
A.单链表
B.双链表
C.带头结点的双循环链表
D.单循环链表
7.在有n个结点的二叉链表中，值为非空的链域的个数为( )
A. n-1
B. 2n-1
C. n+1
D. 2n+1
8.一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为( )
A. 0
B. 1
C. 2
D.不确定
9.数组A［５］［６］的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［５，５］的地址为( )
A. 1140
B. 1145
C. 1120
D. 1125
10.求最短路径的DIJKSTRA算法的时间复杂度为( )
A. O(n)
B. O(n+e)
C. O(n2)
D. O(n×e)
11.对有18个元素的有序表作二分查找，则查找A［3］的比较序列的下标依次为( )
A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
12.快速排序算法在最好情况下的时间复杂度为( )
A. O(n)
B. O(nlog2n)
C. O(n2)
D. O(log2n)
13.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )
A.堆排序
B.冒泡排序
C.快速排序
D.直接插入排序
14.二叉树在线索化后，仍不能有效求解的问题是( )
A.先序线索二叉树中求先序后继
B.中序线索二叉树中求中序后继
C.中序线索二叉树中求中序前趋
D.后序线索二叉树中求后序后继
15.DFS算法的时间复杂度为( )
A. O(n)
B. O(n3)
C. O(n2)
D. O(n+e)
16.队列操作的原则是( )
A.先进先出
B.后进先出
C.只能进行插入
D.只能进行删除
17.有64个结点的完全二叉树的深度为( )(根的层次为1)。
A. 8
B. 7
C. 6
D. 5
18.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的
左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作( )型调整以使其平衡。A. LL B. LR
C. RL
D. RR
19.数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )排
序算法最节省时间。
A.堆排序
B.希尔排序
C.快速排序
D.直接选择排序
1.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。( )
2.由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。( )
3.在对链队列作出队操作时，不会改变front指针的值。( )
4.若一个栈的输入序列为123…n，其输出序列的第一个元素为n，则其输出序列的每个元素
a i一定满足a i=n-i+1(i=1,2...,n)( )
5.二叉树中的叶子结点就是二叉树中没有左右子树的结点。( )
6.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。( )
7.有向图用邻接矩阵表示后，顶点i的人度等于邻接矩阵中第i列的元素个数。
8.有向图的邻接表和逆邻接表中的结点数一定相同。( )
9.删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。( )
10.图G的拓扑序列唯一，则其弧数必为n-1(其中n为G的顶点数)。( )
11、二路归并排序的核心操作是将两个有序序列归并为一个有序序列。( )
12、二叉树只能采用二叉链表来存储。( )
13、数据项是数据基本单位( )
14、一个无环有向图的拓扑序列必然是唯一的( )
15、任何一个无向连通图的最小生成树只有一个( )
16、已知完全二叉树有64个结点，则整个二叉树没有度为1结点。( )
17、线性表的插入和删除的时间复杂度和存储结构没有关系( )
18、空格串和空串是一样的( )
19、哈夫曼树一定是满二叉树。( )
20、队列只能采用链式存储方式。( )
1、在有n个叶子结点的哈夫曼树中，其结点总数为。
2、将下三角矩阵A「1．．8，1．．8」的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A［7，5］的地址为。
3、高度为5的三阶B-树至少有个结点。
4、具有100个结点的完全二叉树的深度为。
5、在插入和选择排序中，若初始数据基本正序，则选用_________；若初始数据基本反序，则选用__ _______。、
6、二叉排序树上，结点的平衡因子定义为该结点_____ ___子树的高度减去该结点____
_____子树的高度。
7、请列举四种处理哈希冲突的方法：、、、
。
8、一个无向图完全图中，共有条边。
9、对如何一颗二叉树，如果其终端结点数为n0，度为2的结点数为n2，则它们之间的关系应为：。
10、下列排序算法中，稳定的排序算法是（选择排序，堆排序，快速排序，直接插入排序）
11、矩阵压缩存储的基本思想是：____ _____的多个元素只分配一个存储空间，_____ ____不分配空间。
12、在有n个叶子结点的哈夫曼树中，总结点数是__ _____。
13、已知数组A［１０］［１０］为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［５，６］对应的地址是_______。
14、通常从四个方面评价算法的质量：___ ______、_________、___ ______和___ ______。
17、散列技术既是一种___ _____方式，又是一种___ _____方法。
18、在索引非顺序文件中，记录不按关键字顺序排列，因此对每个记录要建立一个索引项，这样的索引表称为_____ ____索引。
19、文件的修改包括：__ _______、_______和更新记录三种操作。
20、树的三种常用存储结构是：、____ _____和___ ______。
四、综合题
1、设散列函数为 H （K ）= K mod 7，散列表的地址空间为 0，…， 6，开始时散列表为空，用线性探测法解决冲突，请画出依次插入键值23，14，9，6，30，12，18后的散列表
2、已知序列{15,18,60,41,6,32,83,75,95}。请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。
3、已知串a=′1234+-*′、b=′1+2-3*4′，请用串的各种基本运算将串a 转换为串b 。规定：运算中不能引入新的字符串，所有的字符串只能从串a 中取得。
4、字符a, b, c, d, e 出现的概率分别为：0.12, 0.40, 0.15, 0.08, 0.25，采用哈夫曼算法构造哈夫曼树进行编码。
5、分别画出和下列树对应的各个二叉树。
6、请给出下图深度优先偏历和广度优先偏历的结果
7、
假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别是0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这8个字母设计哈夫曼编码
8、请画出下图的生成森林
9、求最短路径
10、有序表按关键字排列如下：
7，14，18，21，23，29，31，35，38，42，46，49，52 在表中查找关键码为14和22的数据元素。 11、
记录的关键码序列为：63，90，70，55，67，42，98，83，10，45，58，则构造一棵二叉排序树的过程如下
12、1个元素的关键码分别为 18，27，1，20，22，6，10，13，41，15，25。选取关键码与元素位置间的函数为 f(key)=key mod 11
63
63 90
70
90 63 70
90 63 55
70 90 63 55
67
70
90 63 55 67 42
70
90 63 55 67 42
98
70 90 63 55 67
83
98 42
70 90 63
55 67
83
98 10
42 42 98 70 90 63
45
55 83
67
10 58 42 98 70 90 63
45 55 83
67
10
13、
下面是一趟快速排序的算法，请将算法中空缺的部分填充完整
int partition (sqlist&L, int low, int high)
{
L.r[0]= (1) ;
Pivokey=L.r[low].key;
While ( (2) )
{
while (low
(3) ;
L.r[low]=L.r[high];
While (low ++low; (4) ; } L.r[low]=L.r[0]; } 14、 阅读下面的算法，说明其运算结果。 void Bitree_Revolute(Bitree T) { if(T) { T->lchild <--> T->rchild; if(T->lchild) Bitree_Revolute(T->lchild); if(T->rchild) Bitree_Revolute(T->rchild); } }//Bitree_Revolute 15、用深度优先搜索遍历如图1所示的无向图，试给出以A为起点的顶点访问序列（同一个顶点的多个邻点，按字母顺序访问），并给出一棵最小生成树及所采用的算法和其时间复杂度。（14分） 图1 五、算法题 1、编写按层次顺序（同一层自左至右）遍历二叉树的算法。 2 、试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同 3、设哈希函数为H（key），用链地址法解决冲突，H的值域为0，…，n－1，构造的哈希表类型如下： typedef struct{ keytype key; link next; }*link; link openhash[n]; 请写一函数完成在哈希表HP中查找关键字值等于K的结点的工作，若查找成功，返回该结点的指针，否则返回空指针。 4、设有一个长度为n的由“0”和“1”元素组成的输入序列，存于数组A[n]中。设计一个算法，依次让每个元素通过栈S（容量≥n）而得到一个输出序列，使得输出序列中“0”元素都出现在“1”元素之前。输出序列存入数组B[n]中。 假定已知栈的操作： push(S,x):将元素x推入栈S；（插入） pop(S,x):将栈顶元素存入变量x中；（删除） empty(S):判别栈S是否为空） 5、写出和下列递归过程等价的非递归过程。 V oid test(int sum) { int a; read(a); if (a=0) sum:=1 else { test(sum); sum=sum*a } printe(sum); （0012）《数据结构》复习思考题答案 一、选择题 1、某二叉树的先序序列和后序序列正好相同，则该二叉树一定是( A )的二叉树。 A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子 2.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(log2n)的是( B ) A.堆排序 B.冒泡排序 C.直接选择排序 D.快速排序 3.下列排序算法中，( C )算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。 A.堆排序 B.冒泡排序 C.快速排序 D.SHELL排序 4.一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是( B ) A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 5.设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则其元素个数为( D ) A. r-f B. r-f+1 C. (r-f) mod n+1 D. (r-f+n) mod n 6.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( C )存储方式最节省时间。 A.单链表 B.双链表 C.带头结点的双循环链表 D.单循环链表 7.在有n个结点的二叉链表中，值为非空的链域的个数为( A ) A. n-1 B. 2n-1 C. n+1 D. 2n+1 8.一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为( B ) A. 0 B. 1 C. 2 D.不确定 9.数组A［５］［６］的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［５，５］的地址为( A ) A. 1140 B. 1145 C. 1120 D. 1125 10.求最短路径的DIJKSTRA算法的时间复杂度为( C ) A. O(n) B. O(n+e) C. O(n2) D. O(n×e) 11.对有18个元素的有序表作二分查找，则查找A［3］的比较序列的下标依次为( D ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 12.快速排序算法在最好情况下的时间复杂度为( B ) A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 13.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( D ) A.堆排序 B.冒泡排序 C.快速排序 D.直接插入排序 14.二叉树在线索化后，仍不能有效求解的问题是( D ) A.先序线索二叉树中求先序后继 B.中序线索二叉树中求中序后继 C.中序线索二叉树中求中序前趋 D.后序线索二叉树中求后序后继 15.DFS算法的时间复杂度为( C ) A. O(n) B. O(n3) C. O(n2) D. O(n+e) 16.队列操作的原则是( A ) A.先进先出 B.后进先出 C.只能进行插入 D.只能进行删除 17.有64个结点的完全二叉树的深度为( B )(根的层次为1)。 A. 8 B. 7 C. 6 D. 5 18.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的 左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作( A )型调整以使其平衡。 A. LL B. LR C. RL D. RR 19.数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( C ) 排序算法最节省时间。 A.堆排序 B.希尔排序 C.快速排序 D.直接选择排序 1.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。( √ ) 2.由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。( ×) 3.在对链队列作出队操作时，不会改变front指针的值。( √ ) 4.若一个栈的输入序列为123…n，其输出序列的第一个元素为n，则其输出序列的每个元素 a i一定满足a i=n-i+1(i=1,2...,n)( √ ) 5.二叉树中的叶子结点就是二叉树中没有左右子树的结点。( ×) 6.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。( ×) 7.有向图用邻接矩阵表示后，顶点i的人度等于邻接矩阵中第i列的元素个数。 8.有向图的邻接表和逆邻接表中的结点数一定相同。( ×) 9.删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。( ×) 10.图G的拓扑序列唯一，则其弧数必为n-1(其中n为G的顶点数)。( ×) 11、二路归并排序的核心操作是将两个有序序列归并为一个有序序列。(√) 12、二叉树只能采用二叉链表来存储。( ×) 13、数据项是数据基本单位(√) 14、一个无环有向图的拓扑序列必然是唯一的( ×) 15、任何一个无向连通图的最小生成树只有一个( ×) 16、已知完全二叉树有64个结点，则整个二叉树没有度为1结点。(√) 17、线性表的插入和删除的时间复杂度和存储结构没有关系( ×) 18、空格串和空串是一样的( ×) 19、哈夫曼树一定是满二叉树。( ×) 20、队列只能采用链式存储方式。( ×) 1、在有n个叶子结点的哈夫曼树中，其结点总数为2n-1 。 2、将下三角矩阵A「1．．8，1．．8」的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A［7，5］的地址为1208 。 3、高度为5的三阶B-树至少有31 个结点。 4、具有100个结点的完全二叉树的深度为7 。 5、在插入和选择排序中，若初始数据基本正序，则选用_________；若初始数据基本反序，则选用__插入排序选择排序_______。、 6、二叉排序树上，结点的平衡因子定义为该结点_____左____子树的高度减去该结点____ 右_____子树的高度。 7、请列举四种处理哈希冲突的方法：、、、 。（开放定址法再哈希法链地址法建立一个公共溢出区） 8、一个无向图完全图中，共有1/2*n*(n-1) 条边。 9、对如何一颗二叉树，如果其终端结点数为n0，度为2的结点数为n2，则它们之间的关系应为：n0=n2+1 。 10、下列排序算法中，稳定的排序算法是选择排序直接插入排序（选择排序，堆排序，快速排序，直接插入排序） 11、矩阵压缩存储的基本思想是：____值相同_____的多个元素只分配一个存储空间，_____零元素____不分配空间。 12、在有n个叶子结点的哈夫曼树中，总结点数是__ 2n-1_____。 13、已知数组A［１０］［１０］为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［５，６］对应的地址是___1225____。 14、通常从四个方面评价算法的质量：___正确性______、___易读性______、___强壮性______和___高效率______。 15、在插入和选择排序中，若初始数据基本正序，则选用___插入排序______；若初始数据基本反序，则选用__选择排序_______。 16、二叉排序树上，结点的平衡因子定义为该结点___左______子树的高度减去该结点___右______子树的高度。 17、散列技术既是一种___存储______方式，又是一种___查找______方法。 18、在索引非顺序文件中，记录不按关键字顺序排列，因此对每个记录要建立一个索引项，这样的索引表称为_____稠密____索引。 19、文件的修改包括：__删除_______、___插入______和更新记录三种操作。 20、树的三种常用存储结构是：孩子链表表示法、____孩子兄弟链表示法_____和___双亲表示法______。 四、综合题 1、设散列函数为H（K）= K mod 7，散列表的地址空间为0，…，6，开始时散列表为空，用线性探测法解决冲突，请画出依次插入键值23，14，9，6，30，12，18后的散列表 答案： 2、已知序列{15,18,60,41,6,32,83,75,95}。请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。 答案： 结果如下： 初始序列：15，18，60，41，6，32，83，75，95 第一趟：15，18，41，6，32，60，75，83，95 第二趟：15，18，6，32，41，60，75，83，95 第三趟：15，6，18，32，41，60，75，83，95 第四趟：6，15，18，32，41，60，75，83，95 第五趟：6，15，18，32，41，60，75，83，95 在第五趟排序时已无元素交换，则排序结束。 3、已知串a=′1234+-*′、b=′1+2-3*4′，请用串的各种基本运算将串a转换为串b。规定：运算中不能引入新的字符串，所有的字符串只能从串a中取得。 a1=CONCAT(SUBSTR(a,1,1),SUBSTR(a,5,1)); a2=CONCAT(SUBSTR(a,2,1),SUBSTR(a,6,1)); a3=CONCAT(SUBSTR(a,3,1),SUBSTR(a,7,1)); a4=SUBSTR(a,4,1); a5=CONCAT(a1,a2); a6=CONCAT(a3,a4); b=CONCAT(a6,a4) 4、字符a, b, c, d, e出现的概率分别为：0.12, 0.40, 0.15, 0.08, 0.25，采用哈夫曼算法构造哈 夫曼树进行编码。 答案有很多情况：在此仅提供一种 a: 0001 b: 1 c: 001 d: 0000 e: 01 5、分别画出和下列树对应的各个二叉树。 答案： 6、请给出下图深度优先偏历和广度优先偏历的结果 答案： 深度：v1,v2,v4,v8,v5,v3,v6,v7 广度：v1,v2,v3,v4,v5,v6,v7,v8, 7、假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别是0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这8个字母设计哈夫曼编码 0.07,0110 0.19, 10 0.02,01000 0.06,0101 0.32,00 0.03,01001 0.21, 11 0.10。0111 8、请画出下图的生成森林 结果 9、求最短路径 结果 10、 有序表按关键字排列如下： 7，14，18，21，23，29，31，35，38，42，46，49，52 在表中查找关键码为14和22的数据元素。 ⑴查找关键码为14的过程 low=1 ①设置初始区间high=13 ──────────────────────────── ↑②表空测试，非空； mid=7 ③得到中点，比较测试为a情形↑↑ low=1 high=6 high=mid-1，调整到左半区 ──────────────────────────── ↑②表空测试，非空； mid=3 ③得到中点，比较测试为a情形 ↑↑ low=1 high=2 high=mid-1，调整到左半区 ──────────────────────────── ↑②表空测试，非空； mid=1 ③得到中点，比较测试为b情形 ↑↑ low=2 high=2 low=mid+1，调整到右半区 ──────────────────────────── ↑ ②表空测试，非空； mid=2 ③得到中点，比较测试为c 情形 查找成功，返回找到的数据元素位置为2 ⑵ 查找关键码为22的过程 ↑ ↑ low=1 ①设置初始区间 high=13 ──────────────────────────── ↑ ②表空测试，非空； mid=7 ③得到中点，比较测试为a 情形 ↑ ↑ low=1 high=6 high=mid-1，调整到左半区 ──────────────────────────── ↑ ②表空测试，非空； mid=3 ③得到中点，比较测试为b 情形 ↑ ↑ low=4 high=6 low=mid+1，调整到右半区 ──────────────────────────── ↑ ②表空测试，非空； mid=5 ③得到中点，比较测试为a 情形 ↑↑ low=4 high=4 high=mid-1，调整到左半区 ──────────────────────────── ↑ ②表空测试，非空； mid=4 ③得到中点，比较测试为b 情形 ↑ ↑ high=4 low=5 low=mid+1，调整到右半区 ──────────────────────────── 11、 记录的关键码序列为：63，90，70，55，67，42，98，83，10，45，58，则构造1棵二叉排序树的过程如下 63 63 90 70 90 63 70 90 63 55 70 90 63 55 67 70 90 63 55 67 42 70 90 63 55 67 42 98 70 90 63 55 67 83 98 42 70 90 63 55 67 83 98 10 42 42 98 70 90 63 45 55 83 67 10 58 42 98 70 90 63 45 55 83 67 10 12、1个元素的关键码分别为18，27，1，20，22，6，10，13，41，15，25。选取关键码与元素位置间的函数为f(key)=key mod 11 1. 通过这个函数对11个元素建立查找表如下： 13、 (1)L.r[low] (2)Low (3)–high;或者high=high-1 (4)L.r[high]=L.r[low] 14、此算法的功能为：将二叉树的左右子树交换。 15、深度优先搜索遍历ABEKHIFCGJ 最小生成树及所采用的算法和其时间复杂度。 PRIM算法：O（n2） KRUSKAL算法：O(eloge) 五、算法题 1、编写按层次顺序（同一层自左至右）遍历二叉树的算法。 答案： void LayerOrder(Bitree T)//层序遍历二叉树 { InitQueue(Q); //建立工作队列 EnQueue(Q,T); while(!QueueEmpty(Q)) { DeQueue(Q,p); visit(p); if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); } }//LayerOrder 2 、试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同 int last=0,flag=1; int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0 { if(T->lchild&&flag) Is_BSTree(T->lchild); if(T->data last=T->data; if(T->rchild&&flag) Is_BSTree(T->rchild); return flag; }//Is_BSTree 3、 status SearchHash( openhash HP, keytype k, link &p) { sp=HP[H(k)]; while (sp.next!=NULL && !EQ(k, sp.key)) sp=sp->next; if EQ(k, sp.key) p=sp; else p=null; } 4、status order(elemtype A[n], elemtype &B[n],stack S, int n) { j=0; for(i=0;i { if (A[i]!=0) push(s, A[i]); else {B[j]=A[i]; j++;} } while (!empty(s)) { pop(s, B[j]); j++; } } 5、void test(int &sum) { stack s;int x; scanf(x); initstack(s); while(x){ push(s,x); scanf(x); } sum=0; printf(sum); while (pop(s,x)){ sum+=x; printf(sum); } } 实验2 查找算法的实现和应用?实验目的 1. 熟练掌握静态查找表的查找方法； 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术. ?实验内容 1.用二分查找法对查找表进行查找； 2.建立二叉排序树并对该树进行查找； 3.确定hash函数及冲突处理方法，建立一个hash表并实现查找。 程序代码 #include cout<<"Not present!"; } return 0; } 结果 二叉排序树 #include EBR，叫做扩展MBR（Extended MBR），位于硬盘的某柱面0磁道1扇区 1.簇（cluster） 是DOS给文件系统分配磁盘空间的最小单位。由若干连续的逻辑扇区组成，不同的盘，簇的大小不同，簇是从2开始编号，见表6-1。 逻辑扇区号=（簇号-2）×扇区数/簇+数据区首扇区号 2.BOOT记录： 第一部分：0～2字节为跳转指令，转向启动码区。 第二部分：3～10字节为厂商标识字段，如MSDOS5.0。 第三部分：11～61字节为磁盘参数表（51字节）。 第四部分：62～509字节为启动程序（438字节）。 最后：55,AA字节。 51字节BPB表（BIOS Parameter Block） OB－OC：每扇区字节数(512) OD：扇区数/簇 0E－0F：保留扇区（指Boot区） 10：FAT个数 11－12：根目录最大登记项数 13－14：本分区扇区总数（小于32M的分区，大于32MB时,为0） 15：介质描述符 16－17：每个FAT扇区数 18－19：每道扇区数 1A－1B：磁头数 1C－1F：本分区前的扇区数（隐含扇区，即从0（X）柱0头1扇到0（X）柱1头1扇之间的扇区，由于不能为DOS访问，故称为隐含扇区）。 20－23：大容量盘总扇区数。 24：BIOS设备号（hex：HD=8x） 25：未使用 26：扩展引导标记（29H） 27-2A：卷序列号（随机） 2B-35：卷标，分区标识，如：WIN98 36-3D：文件系统格式（FAT16） 3.FAT（文件配置表） FAT有两个，当第一个损坏时，为人工修复提供方便，DOS不会自动用第二个去修复第一个FAT，而DOS实际上没有用尽2个FAT占用的扇区，因为可作为他用。FAT登记盘上簇的使用情况，登记项有12位、16位和32位之分，下面以16位为例说明FAT的格式。 16位FAT格式： 簇号（表项） 0000H 0001H 0002H … NNNNH 类型保留簇使用簇 含义介质标志记录文件簇号链 本人是今年考上广州大学计算机专业的，说真的，专插本这条路并不好走，很辛苦!但是当你知道自己考上了，那感觉是相当激动的！！ 2011年高考成绩揭晓，我就过了3A二分而已，那时候心情很沉重，只有3条路可以选择，第一是复读第二就是读3A尾的学校第三就是去打工，最后的抉择是报了中山火炬技术学院（全省专科不知道是倒数第二还是倒数第三的学校） 2011年九月带着沉重的心情来到了中山火炬技术学院，这学校名气小的可怜，问了N多人都没人知道这学校，学校也小的可怕，十几分钟就可以走完，当时感觉自己很悲剧，上了这样的学校很没面子，因此痛下决心来不管怎么样要往上爬，从一个师兄那里听说可以插本，考到的话第一学历是本科，但是听说插本很难，比高考，考研究生还要难上百倍，便没怎么想插本了，还是专心学好大专的专业吧 一转眼，2年过去了，到了大三，很多同学都去实习了，我又一次走到人生十字路口上，是去工作还是去插本，经过几天考虑还是决定插本了，因为第一我觉的要进好的企业需要本科第二我不想那么快工作，那时候作出插本决定已经是9月底了，中山火炬技术学校插本的人很少，所以只好通过加插本QQ群来了解插本信息 因为本人不想给家庭负担所以没有参加任何培训班，刚开始复习全靠自己摸索着的，很痛苦，哪里是重点哪里不是重点都不知道，幸亏在进群之后知道考纲这回事，慢慢的走上了复习的正规道路，每天8点就起来看书，除开吃饭上厕所什么的离开一下教室其他都是在教室看书，一直看到晚上10点钟，回到宿舍继续看书，因为宿舍没人，所以看到2点左右才睡觉，每个星期抽出半天去放松，这样才能保证效率，那时候备考时候真是很无聊很痛苦，知道不少人都已经放弃了，但是还是坚持到最后，3月去广州考试，看见考广大计算机人400多人，心里有点怕怕的，但是马上调整好心态，心里说怕什么，大不了考不上去工作呢，在考试那2天就浏览一下书本和总结的考点，考完也不去想考试结果，因为没有什么意义了，四月八出成绩了，当时心里发毛了，因为说不担心那是假的，我是先要我舍友帮我查的，她说过了，我还是担心，最后自己鼓起勇气查的，当我点一下鼠标的那一刻眼睛是闭着的，闭了好久才敢看成绩。当时自己惊叫了起来：过了过了，战争终于结束了。自己也没想到会考的这么好，它见证了我几个月的付出是值得的好了，啰嗦了那么多，不知道说了这么多大家看了是什么心情，写的乱七八糟的，不过都是个人真实感受，现在就分享一下我各科复习经验吧 政治 这个是最恶心的科目，我用最多时间来备考这科，因为高中读的是理科，对它不感冒，但是考了67分，虽然不是很高分，但是我已经很满足了，现在谈谈这科复习方法，我10月开始看政治书的，一天一章的看，看到11月，看了大概四次书本，你会问为什么要看书，很简单，因为政治选择题很坑爹，不少题目是书本的，但是考纲没有的，12月开始之后，我就根据录音去划书，整理笔记，然后开始背，每个白天抽3小时背政治，然后晚上回宿舍打开电脑用 1小时选择题，培养做题感觉，到一月中，开始做历年真题，并把考过的大题给划掉，重点背那些没出的，没背熟的反复的背和默写，要是你学我这样做，我想政治可以个满意的分数。 英语 轴系结构设计实验报告 一、实验目的 1、熟悉并掌握轴系结构设计中有关轴的结构设计，滚动轴承组合设计的基本方法； 2、熟悉并掌握轴、轴上零件的结构形状及功用、工艺要求和装配关系； 3、熟悉并掌握轴及轴上零件的定位与固定方法； 4、了解轴承的类型、布置、安装及调整方法以及润滑和密封方式。 二、实验设备 1、组合式轴系结构设计分析试验箱。 试验箱提供能进行减速器圆柱齿轮轴系，小圆锥齿轮轴系及蜗杆轴系结构设计实验的全套零件。 2、测量及绘图工具 300mm钢板尺、游标卡尺、内外卡钳、铅笔、三角板等。 三、实验步骤 1、明确实验内容，理解设计要求； 已知条件（包括传动零件类型、载荷条件、速度条件）： 直齿圆柱齿轮、圆锥滚子轴承、阶梯轴、载荷变动小、传动平稳 绘制传动零件支撑原理简图： 2、复习有关轴的结构设计与轴承组合设计的内容与方法（参看教材有关章节）； 3、构思轴系结构方案 （1）根据齿轮类型选择滚动轴承型号； 轴承类别：圆锥滚子轴承选择依据：能承受径向和轴向方向的力 （2）确定支承轴向固定方式（两端固定或一端固定、一端游动）； 轴承轴向固定方式：两端固定选择依据：传动平稳 （3）根据齿轮圆周速度（高、中、低）确定轴承润滑方式（脂润滑、油润滑）； 润滑方式：油润滑选择依据：齿轮圆周速度中低 （4）选择端盖形式（凸缘式、嵌入式）并考虑透盖处密封方式（毡圈、皮碗、油沟）； 密封方式：毡圈、端盖凸缘式选择依据：更好的密封轴肩 （5）考虑轴上零件的定位与固定，轴承间隙调整等问题； 如何定位：定位的话可以用轴肩、端盖、套筒、挡圈，圆螺母。 选择依据：用外力对零件进行约束，使零件在轴向无法产生相对位移。 （6）绘制轴系结构方案示意图。 4、组装轴系部件 根据轴系结构方案，从实验箱中选取合适零件并组装成轴系部件、检查所设计组装的轴系结构是否正确。 5、测量零件结构尺寸（支座不用测量），并作好记录。 6、将所有零件放入试验箱内的规定位置，交还所借工具。 7、根据结构草图及测量数据，在图纸上绘制轴系结构装配图，要求装配关系表达正确，注明必要尺寸（如支承跨距、齿轮直径与宽度、主要配合尺寸），填写标题栏和明细表。 8、写出实验报告。 四、实验结果分析 1、轴上各键槽是否在同一条母线上。答：是。 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 数据结构,专科 一、简答题（ 1、假设一个有向图的顶点集合V={c1,c2,c3,c4,c5},弧集 S={ h f c / / \ d k g 后序是hdfbkgcea 3、已知关键字序列{70，83，100，65，10，9，7，32}，现对其 从小到大排序，写出快速排序每一趟结束时的关键字状态。 答#include 譬如第一次结果就是70，83，100，65，10，32，7，9 70比83小，所以位置没变。。 4、设s="I AM A WORKER"，t=" GOOD"，q=" WORKER"。求： StrLength(s)，StrLength(t) ，SubString(s,8,6) ， Index(s,q,1) 。 答：strlength(s)=14；strlength(t)=4；substr(s,8,6)=worker；substr(s,q,1)=o; 5、在单链表中设置头结点有什么作用？ 答：头结点就是在单链表的开始结点之前附加的一个结点，设置头结点的优点有两个：（1）由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其他位置上一样，无须进行其他特殊处理；（2）无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就一样了。 6、设哈希函数H(key)=key MOD 13,用线性探测再散列法解决 冲突。对关键字序列{ 55，19，01，68，23，27，20，84 } 在地址空间为0-10的散列区中建哈希表，画出此表，并求等 概率情况下查找成功时的平均查找长度。 轴系结构设计实验心得体会 轴系结构设计实验心得体会第二篇、实验二、轴系结构设计实验 轴系结构设计实验心得体会 实验二、轴系结构设计实验 一、实验目的 1、熟悉常用轴系零部件的结构； 2、掌握轴的结构设计基本要求； 3、掌握轴承组合结构设计的基本方法。 二、实验设备 ①各种轴； ②轴上零件：齿轮、蜗杆、带轮、联轴器、轴承、轴承座、端盖、套杯、套筒、圆螺母、止退垫圈、轴端挡板、轴用弹性垫圈、孔用弹性垫圈、螺钉、螺母等。 ③工具包括活搬手、游标卡尺、胀钳。 ④铅笔、三角尺等绘图工具自备。 三、概述 轴系结构是机械的重要组成部分，也是机械设计课程的核心教学内容。由于轴系结构设计的问题多、实践性强、灵活性大，因此既是教师讲授的难点，也是学生学习中最不易掌握的内容。本实验通过学生自己动手，经过装配、调整、拆卸等全过程，不仅可以增强学生对轴系零部件结构的感性认识，还能帮助学生深入理解轴的结构设计、轴承组合结构设计的基本要领，达到提高设计能力和工程实践能力的目 的。 四、实验内容 1、每组同学根据轴系简图装配轴系部件； 2、分析并测绘部件，在简图上标出零、部件尺寸； 3、编写实验报告，并画出轴系部件装配草图。 五、实验步骤 ①根据轴系结构设计装配草图，选择相应的零件实物，按装配工艺要求顺序装在轴上，完成轴系结构设计； ②分析轴系结构方案的合理性。分析时应考虑以下问题： a.轴上各键槽是否在同一条母线上； b.轴上各零件是否处于指定位置； c.轴上各零件的轴向、周向固定是否合理、可靠，如防松、轴承拆卸等； d.轴系能否实现回转运动，运动是否灵活； e.轴系沿轴线方向的位置是否确定，轴向力能否传到机座上； f.轴系的轴向位置是否需要调整，需要时，如何调整。 ③在确认实际装配结构无误时，测绘各零件的实际尺寸（底板不测绘，轴承座只测量轴向宽度）； ④将实验零件放回箱内，排列整齐，工具放回原处； ⑤在实验报告上，按1∶1比例完成轴系结构装配图（只标出各段轴的直径和长度，公差配合及其余尺寸不标注，零件序号、标题栏可省略）。 注意：因实验条件限制，本实验忽略过盈配合的松紧程度、轴肩过渡 班级：：学号： 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 二、实验容 定义一个包含学生信息（学号，，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; 数据模型所描述的内容包括三个部分：数据结构、数据操作、数据约束。 1）数据结构:数据模型中的数据结构主要描述数据的类型、内容、性质以及数据间的联系等。数据结构是数据模型的基础，数据操作和约束都建立在数据结构上。不同的数据结构具有不同的操作和约束。 2）数据操作:数据模型中数据操作主要描述在相应的数据结构上的操作类型和操作方式。 3）数据约束：数据模型中的数据约束主要描述数据结构内数据间的语法、词义联系、他们之间的制约和依存关系，以及数据动态变化的规则，以保证数据的正确、有效和相容。 数据模型按不同的应用层次分成三种类型：分别是概念数据模型、逻辑数据模型、物理数据模型。 1、概念数据模型（Conceptual Data Model）：简称概念模型，主要用来描述世界的概念化结构，它使数据库的设计人员在设计的初始阶段，摆脱计算机系统及DBMS的具体技术问题，集中精力分析数据以及数据之间的联系等，与具体的数据管理系统（Database Management System，简称DBMS）无关。概念数据模型必须换成逻辑数据模型，才能在DBMS中实现。 概念数据模型是最终用户对数据存储的看法，反映了最终用户综合性的信息需求，它以数据类的方式描述企业级的数据需求，数据类代表了在业务环境中自然聚集成的几个主要类别数据。 概念数据模型的内容包括重要的实体及实体之间的关系。在概念数据模型中不包括实体的属性，也不用定义实体的主键。这是概念数据模型和逻辑数据模型的主要区别。 概念数据模型的目标是统一业务概念，作为业务人员和技术人员之间沟通的桥梁，确定不同实体之间的最高层次的关系。 在有些数据模型的设计过程中，概念数据模型是和逻辑数据模型合在一起进行设计的。 2、逻辑数据模型（Logical Data Model）:简称数据模型，这是用户从数据库所看到的模型，是具体的DBMS所支持的数据模型，如网状数据模型(Network Data Model)、层次 专升本《数据结构》 一、（共75题,共150分） 1. 数据的基本单位是（）。（2分） A.数据元素 B.记录 C.数据对象 D.数据项 .标准答案：A 2. （）是数据的不可分割的最小单位。（2分） A.数据对象 B.数据元素 C.数据类型 D.数据项 .标准答案：D 3. 算法的空间复杂度是对算法（）的度量。（2分） A.时间效率 B.空间效率 C.可读性 D.健壮性 .标准答案：B 4. （）是限制了数据元素的内部结构仅为一个字符的线性表。（2分） A.栈 B.队列 C.串 D.数组 .标准答案：B 5. 串的长度是指串中所含（）的个数。（2分） A.不同字符 B.不同字母 C.相同字符 D.所有字符 .标准答案：D 6. 采用带头结点双向链表存储的线性表，在删除一个元素时，需要修改指针（）次。（2分） A.1 B.2 C.3 D.4 .标准答案：B 7. 线性表的顺序存储结构是一种（）的存储结构。（2分） A.顺序存取 B.随机存取 C.索引存取 D.Hash存取 .标准答案：B 8. 数组a[1..m]采用顺序存储，a[1]和a[m]地址分别为1024和1150，每个元素占2字节，则m是（）。（2分） A.64 B.32 C.16 D.8 .标准答案：A 9. 深度为h的二叉树，第h层最多有（）个结点。（2分） A.h B.2h-1 C.2h-1 D.2h .标准答案：C 10. m个结点的二叉树，其对应的二叉链表共有（）个非空链域。（2分） A.m B.m+1 C.2m D.m-1 .标准答案：B 11. 下面叙述错误的是（）。（2分） A.顺序表是借助物理单元相邻表示数据元素之间的逻辑关系 B.对于空队列进行出队操作过程中发生下溢现象 C.有向图的邻接矩阵一定是对称的 D.具有相同的叶子个数和具有相同的叶子权值的赫夫曼树不是唯一的 .标准答案：C 12. 以下与数据的存储结构无关的术语是（）。（2分） A.循环队列 B.双向链表 C.哈希表 D.数组 .标准答案：D 13. 在一个长度为n的链式栈中出栈实现算法的时间复杂度为（）。（2分） A.O(1) B.O(log n) C.O(n) D.O(n2) .标准答案：A 14. 在具有k个度数为2的二叉树中，必有（）个叶子结点。（2分） A.k B.k-1 C.2k D.k+1 .标准答案：D 15. 在关键字序列（10,20,30,40,50）中，采用折半法查找20，关键字之间比较需要（）次。（2分） A.1 B.2 C.3 D.4 .标准答案：C 16. 16某二叉树的后序遍历序列和和中序遍历序列均为abcd，该二叉树的前序遍历序列是（）。（2分） A.abcd B.dcba C.acbd D.dbca .标准答案：B 17. n个顶点的无向连通图的生成树，至少有（）个边。（2分） A.n(n-1) B.n(n-1)/2 C.2n D.n-1 .标准答案：D 18. 可以采用（）这种数据结构，实现二叉树的层次遍历运算。（2分） A.队列 B.树 C.栈 D.集合 .标准答案：A 实验一轴系结构组合设计实验 一、实验目的 1. 熟悉并掌握轴、轴上零件的结构形状及功用、工艺要求和装配关系； 2. 熟悉并掌握轴及轴上零件的定位与固定方法，为轴系结构设计提供感性认识； 3. 了解轴承的类型、布置、安装及调整方法，以及润滑和密封方式； 4. 掌握轴承组合设计的基本方法，综合创新轴系结构设计方案。 二、实验设备 1. 组合式轴系结构设计与分析实验箱。箱内提供可组成圆柱齿轮轴系、小圆锥齿轮轴系和蜗杆轴系三类轴系结构模型的成套零件，并进行模块化轴段设计，可组装不同结构的轴系部件。 2. 实验箱按照组合设计法，采用较少的零部件，可以组合出尽可能多的轴系部件，以满足实验的要求。实验箱内有齿轮类、轴类、套筒类、端盖类、支座类、轴承类及联接件类等8类40种168个零件。 3. 测量及绘图工具:直尺、游标卡尺、铅笔、三角板、稿纸等（除游标卡尺外，其余需自带）。 三、实验原理 1. 轴系的基本组成 轴系是由轴、轴承、传动件、机座及其它辅助零件组成的，以轴为中心的相互关联的结构系统。传动件是指带轮、链轮、齿轮和其它做回转运动的零件。辅助零件是指键、轴承端盖、调整垫片和密封圈等一类零件。 2. 轴系零件的功用 轴用于支承传动件并传递运动和转矩，轴承用于支承轴，机座用于支承轴承，辅助零件起联接、定位、调整和密封等作用。 3. 轴系结构应满足的要求 （1）定位和固定要求：轴和轴上零件要有准确、可靠的工作位置； （2）强度要求：轴系零件应具有较高的承载能力； （3）热胀冷缩要求：轴的支承应能适应轴系的温度变化； （4）工艺性要求：轴系零件要便于制造、装拆、调整和维护。 四、实验内容 1. 根据教学要求每组学生可自行选择实验内容（圆柱齿轮轴系、小圆锥齿轮轴系或蜗杆轴系等）； 2. 熟悉实验箱内的全套零部件，根据提供的轴系装配方案（可参考图1-图6），选择相应的零部件进行轴系结构模型的组装； 3. 分析轴系结构模型的装拆顺序，传动件的周向和轴向定位方法，轴的类型、支承形式、间隙调整、润滑和密封方式； 长春大学计算机学院网络工程专业 数据结构实验报告 实验名称：实验二栈和队列的操作与应用 班级：网络14406 姓名：李奎学号：041440624 实验地点：日期： 一、实验目的： 1．熟练掌握栈和队列的特点。 2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用。 3．掌握链队的入队和出队等基本操作。 4．加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境： 注：将完成的实验报告重命名为：班级+学号+姓名+（实验二），（如：041340538张三（实验二）），发邮件到：ccujsjzl@https://www.doczj.com/doc/0214968088.html,。提交时限：本次实验后24小时之内。 阅读程序，完成填空，并上机运行调试。 1、顺序栈，对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 (1)文件SqStackDef. h 中实现了栈的顺序存储表示 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后，base 的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ }SqStack; /* 顺序栈*/ (2)文件SqStackAlgo.h 中实现顺序栈的基本操作（存储结构由SqStackDef.h 定义） Status InitStack(SqStack &S) { /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); /* 存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) { // 返回S 的元素个数，即栈的长度, 编写此函数 本科插班生考试大纲《数据结构与算法》 《数据结构与算法》专业课程考试大纲 考试科目名称：数据结构与算法 一、考试性质 普通高等学校本科插班生招生考试是由专科毕业生参加的选拔性考试。高等学校根据考生的成绩，按已确定的招生计划，德、智、体全面衡量，择优录取。该考生所包含的内容将大致稳定，试题形式多种，具有对学生把握本课程程度的较强识别、区分能力。 二.考试内容及要求 一、考试基本要求 通过数据结构与算法理论的学习，使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术；配合算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力，对理论和实践的操作使学生得到全面的领会和深刻的认识。 二、考核知识点及考核要求 本大纲的考核中，按照“识记”、“领会”、“简单应用”和“综合应用”等四个层次规定应达到的能力层次要求。各能力层次为递进等级关系，后者必须建立在前者的基础上，其含义是： 识记：要求考生知道有关的名词、概念、原理、知识的含义，并能正确认识或识别。 领会：要求在识记的基础上，能把握相关的基本概念、基本原理和基本方法，掌握有关概念、原理、方法的区别与联系。 简单应用：要求在领会的基础上，运用所掌握的基本概念、基本原理和基本方法中的少量知识点，分析和解决一般的理论问题或实际问题。 综合应用：要求在简单应用的基础上，运用学过的多个知识点，综合分析和解决比较复杂的实际问题。 第1章绪论 一、考核知识点 1、数据结构的基本概念 2、抽象数据类型的表示和实现 3、算法的概念和特性 4、算法时间复杂度和空间复杂度分析 二、考核要求 1、识记 （1）数据结构的研究内容 2、领会 （1）抽象数据类型的表示和实现 （2）算法的定义和特性 （3）评价算法优劣的基本标准 3、简单应用 （1）简单数据结构的程序设计 （2）简单数据结构程序的时间复杂度和空间复杂度分析 4、综合应用 （1）数据结构的一些基本概念 （2）算法的时间复杂度分析 第2章线性表 一、考核知识点 1、线性表的类型定义 2、线性表的顺序表示和实现 3、线性表的链式表示和实现 4、线性表的应用 轴系结构的分析与测绘 一、实验目的 1.通过拼装和测绘，熟悉并掌握轴的结构设计以及轴承组合设计 的基本要求和方法。 2.了解并掌握轴系结构的基本形式，熟悉轴、轴承和轴上零件的结构、功能和工艺要求。掌握轴系零、部件的定位和固定、装配与调整、润滑与密封等方面的原理和方法。 二、实验内容 1. 根据选定的轴系结构设计实验方案，按照预先画出的装配草图进行轴系结构拼装。检查原设计是否合理，并对不合理的结构进行修改。 2.测量一种轴系各零、部件的结构尺寸，并绘出轴系结构的装配图， 标注必要的尺寸及配合，并列出标题栏及明细表。 三、实验设备和用具 1.模块化轴段(可组装成不同结构形状的阶梯轴)。 2. 轴上零件：齿轮、蜗杆、带轮、联轴器、轴承、轴承座、端盖、套杯、套筒、圆螺母、轴端挡板、止动垫圈、轴用弹性挡圈、孔用弹性挡圈、螺钉、螺母等。 3. 工具：活搬手、胀钳、内、外卡钳、钢板尺、游标卡尺等。 四、实验步骤 1. 利用模块化轴段组装阶梯轴，该轴应与装配草图中轴的结构尺寸一致或尽可能相近。 2. 根据轴系结构设计装配草图，选择相应的零件实物，按装配工艺要求顺序装到轴上，完成轴系结构设计。 3. 检查轴系结构设计是否合理，并对不合理的结构进行修改。合理的 轴系结构应满足下述要求： 1）轴上零件装拆方便，轴的加工工艺性良好。 2）轴上零件固定(轴向周向)可靠。 4.轴系测绘 1）测绘各轴段的直径、长度及轴上零件的相关尺寸。 2）查手册确定滚动轴承、螺纹联接件、键、密封件等有关标准件的尺寸。 5. 绘制轴系结构装配图 1) 测量出的各主要零件的尺寸，对照轴系实物绘出轴系结构装配图。 2)图幅和比例要求适当(一般按1:1)，要求结构清楚合理，装配关系正确，符合机械制图的规定。 3)在图上标注必要的尺寸，主要有：两支承间的跨距，主要零件的配合尺寸等。 4)对各零件进行编号。并填写标题栏及明细表(标题栏及明细表可参阅配套教材《机械设计课程设计》)。 广东技术师范学院 《计算机科学技术导论》（本科插班生入学考试）考试大纲 （计算机科学学院制定） 一、考试性质与试题命题的原则 《计算机科学技术导论》是广东技术师范学院为计算机科学与技术等专业的本科 插班生入学考试所设置的一个专业课考试科目。它的评价标准是高等学校计算机类专 业高职高专毕业生或相近专业毕业生能达到的及格或及格以上水平，以保证录取的本 科插班生具有一定的计算机科学基础理论及必要的专业技能能力，以利于择优选拔。 考试对象为参加教育部面向全面招生的本科插班生入学考试的高职高专毕业生以及 具有同等学历的报考人员。 《计算机科学技术导论》课程考试的目的和要求是：准确、简明地考核考生对计算机科学体系框架、计算机科学基本知识以及现代计算机发展方向、主要理论和科学方法的掌握和理解水平，衡量他们在理解、掌握和运用这些基本专业理论和知识的基础上，观察、分析和解决技术问题的能力。 二、考试形式及试卷结构 1.考试形式为闭卷、笔试；考试时间为120分钟，试卷满分为100分。 2、试题命制的原则：作为一项选拔性考试，《计算机科学技术导论》考试试题在设计上应具有较高的信度和效度、必要的区分度和合理的难度。命题根据本大纲规定的考试目标和考核内容，考试命题应具有一定的覆盖面且重点突出，侧重考核考生对本学科的基本理论、基本知识和基本技能的掌握程度，以及运用所学的知识解决实际问题的能力。 3.试题对不同能力层次要求的分数比例：识记25%、理解55%，综合应用15%，其他5%。 4.合理安排试题的难度结构。试题难易度分为易、较易、较难、难四个等级。试卷中难易度试题的分布比例，易约占25%，较易约占35%，较难约占20%，难约占10%。 5.试卷的题型有：单项选择题、多项选择题、简答题、改错题、计算题、填空题、综合题等。可根据考核要求，适当安排各种题型数量的比例，达到考核对知识点的识记、理解以及运用水平和能力。 实验四轴系结构设计与分析实验 实验１轴系结构设计实验指导书 一、实验目的 熟悉并掌握轴系结构设计中有关轴的结构设计、滚动轴承组合设计的基本方法。 二、实验设备 1、创意组合式轴系结构设计与分析实验箱。 实验箱由8类40种168件零件组成，能方便的组合出数十种轴系结构方案。具有开设轴系结构设计和轴系结构分析两大项实验功能，对培养和提高学生的机械设计能力、机械结构能力及机构创新能力的具有明显的效果。 2、绘图工具 铅笔、三角板等。 三、实验内容与要求 1、指导教师根据下表可以选择性安排每组的实验内容( 实验题号)或学生自行确定实验方案。 2、进行轴的结构设计与滚动轴承组合设计。 每组学生根据实验题号的要求，进行轴系结构设计，解决轴承类型选择,轴上零件定位固定轴承安装与调节、润滑及密封等问题。 3、绘制轴系结构装配图。 4、每人编写实验报告一份。 四、实验步骤 1、明确实验内容，理解设计要求。 2、复习有关轴的结构设计与轴承组合设计 的内容与方法(参看教材有关章节)。 3、构思轴系结构方案 (1)根据齿轮类型选择滚动轴承型号。 (2)确定支承轴向固定方式(两端固定；一端固定、一端游动)。 (3)根据齿轮圆周速度(高、中、低)确定轴承润滑方式(脂润滑、油润滑)。 (4)选择轴承端盖形式(凸缘式、嵌入式)并考虑透盖处密封方式(毡圈、皮碗、 油沟等)。 (5)考虑轴上零件的定位与固定，轴承间隙调整等问题。 (6)绘制轴系结构方案示意图。 4、组装轴系部件 根据轴系结构方案，从实验箱中选取合适零件并组装成轴系部件、检查所设计组装的轴系结构是否正确。 5、绘制轴系结构草图。 6、将所有零件放入实验箱内的规定位置。 7、写出实验报告。 附：部分轴系结构装配图 轴系结构设计实验报告 实验者：同组者： 班级：日期： 一、实验目的 二、实验内容 实验题号 已知条件 三、实验结果 1、轴系结构装配图（附3号图） 2、轴系结构设计说明（说明轴上零件的定位固定，滚动轴承的安装、调整、 《数据结构》实验报告 实验序号：1 实验项目名称：概论 附源程序清单： 1. #include 2. #include 韩山师范学院2019年本科插班生招生考试 计算机科学与技术 专业 数据结构 试卷（A 卷） 一、单项选择题（每题2分，共30分） 1. 由3个结点可以构造出多少种不同的二叉树？（ ） A ．2 B ．3 C ．4 D ．5 2. 一个栈的输入序列为A B C ，则下列序列中不可能是栈的输出序列的是( )。 A. B C A B.C B A C. C A B D. A B C 3. 算法的时间复杂度取决于（ ） 。 A ．问题的规模 B ．待处理数据的初态 C ．计算机的配置 D ．A 和B 4. 数组的逻辑结构不同于下列（ ）的逻辑结构。 A. 树 B. 栈 C. 队列 D. 线性表 5. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（ ）。 A ．8 B ．63.5 C ．63 D ．7 6. 用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。 A ．队列 B. 栈 C. 树 D ．图 7. 数据的最小单位是（ ）。 A.数据元素 B.数据项 C.数据类型 D. 数据变量 8. 设无向图G中有n个顶点，则该无向图的最小生成树上有（） 条边。 A. 2n B. 2n-1 C. n-1 D. n 9. 为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。 A.栈 B.队列 C.线性表 D.有序表 10. 程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂 度为（）。 n) C.O(n2) D.O(n3/2) A. O(n) B. O(nlog 2 11.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。 A. q=p->next；p->next=q->next；free(q)； B. q=p->next；p->data=q->data；free(q)； C. q=p->next；p->data=q->data；p->next=q->next；free(q)； D. q=p->next；q->data=p->data；p->next=q->next；free(q)； 12. 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则 第15个元素的地址是（）。 A.110 B.108 C.100 D.128 13. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。 A．所有的结点均无左孩子 B．所有的结点均无右孩子 C．只有一个叶子结点 D．是任意一棵二叉树 14. 具有n个顶点的有向图最多有（）条边。 A．n B．n2 C．n(n+1) D．n(n-1) 15. 设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i 的入度为（）。 A.第i行非0元素的个数之和 B. 第i列非0元素的个数之和 C.第i行0元素的个数之和 D. 第i列0元素的个数之和 《数据结构》考试大纲 I 考试的性质与目的 本科插班生考试是由专科毕业生参加的选拔性考试。《数据结构》是计算机科学与技术专业（本科）的一门专业基础课程，考试主要检查考生对常用基本数据结构（顺序表、链表、栈、队列、树、二叉树、图等）的逻辑结构、存储结构和相应算法的掌握程度，以保证后续课程的学习。 II 考试的内容 一、考试基本要求 1、基本理论知识 （l）、数据结构的基本概念和基本术语，算法的描述方法和算法分析的基本概念。 （2）、线性表的基本概念、线性表的基本操作以及这些操作分别在顺序存储和链式存储结构下的实现及复杂度分析。 （3）、栈和队列的定义、存储结构、实现和典型应用。 （4）、串的定义及其基本操作。 （5）、数组的定义、运算和顺序存储。 （6）、树的定义、基本术语和存储结构，二叉树的定义和性质、二叉树的存储结构及其各种操作，哈夫曼树的概念和应用。 （7）、图的定义和术语、图的存储结构及其各种操作。 （8）、各种查找方法的算法、适用范围及时间复杂度的分析。 （9）、多种内排算法的基本思想和算法的时间复杂度分析，不同排序方法的比较。 2、基本技能 （1）、能阅读用类C语言编写的算法。 （2）、能分析算法所完成的功能、运行结果和时间复杂度。 （3）、能根据要求用类C语言编写算法。 二、考核知识点及考核要求 第一章绪论 一、考核知识点 1.数据、数据元素、数据项、数据对象、数据结构、逻辑结构、物理结构、元素、结点等基本概念。抽象数据类型的定义、表示和实现方法。 2.算法、算法的特性、如何用类C语言来描述算法。 3.算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。 二、考核要求 1.识记：有关数据结构的基本概念，四种基本数据结构的特点。 2.理解：四种基本数据结构的基本运算，算法复杂度度量的基本概念。 3.应用：用类C语言描述算法数据结构实验
硬盘数据组织结构
广州大学专插本心得
轴系结构设计与分析实验报告
数据结构实验报告
《数据结构》(专科)已完成
心得体会 轴系结构设计实验心得体会
数据结构实验一 实验报告
数据模型所描述的内容包括三个部分
专升本《数据结构》_试卷_答案
实验一 轴系结构组合设计实验
数据结构实验
2017年中山大学南方学院专插本《数据结构与算法》考试大纲
轴系结构设计实验指导与参考答案图
广东技术师范学院2018年专插本《计算机科学技术导论》考试大纲
四轴系结构设计与分析
数据结构实验1
2019年本科插班生考试试题《数据结构》A试卷
2019广东专插本韩山师范学院《数据结构》考试大纲
相关主题
文本预览