2009年计算机统考数据结构部分真题解析
一、单项选择题
1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将
要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是______。
A.栈
B.队列
C.树
D.图
【解析】B。考察栈和队列的特点。C和D直接排除，缓冲区的特点需要先进先出，若用栈，则先进入缓冲区的数据则要排队到最后才能打印，不符题意，所以只有队列符合题意。
2.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立
即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是______。
A.1
B.2
C.3
D.4
【解析】C。考察栈的最大深度。时刻注意栈的特点是先进后出。下面是出入栈的详细
栈内的最大深度为3，故栈S的容量至少是3。
3.给定二叉树图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右
子树。若遍历后的结点序列是3, 1, 7, 5, 6, 2, 4，则其遍历方式是______。
1
23
45
67
A.LRN
B.NRL
C.RLN
D.RNL
【解析】D。考察二叉树的遍历。L表示左分支，R表示右分支，N表示根。分析遍历后的结点序列，可以看出根结点是在中间被访问的，而且右子树结点在左子树之前，则遍历的方法是RNL。本题考查的遍历方法并不是二叉树遍历的三种基本遍历方法，对于考生而言，重要的是要掌握遍历的思想。
4.下列二叉排序树中，满足平衡二叉树定义的是______。
A. B. C. D.
【解析】B。考察平衡二叉树的定义。根据平衡二叉树的定义有，任意结点的左右子树高度差的绝对值不超过1。而其余三个答案均可以找到不符合的结点。
5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数
最多是_____。
A.39
B.52
C.111
D.119
【解析】C。考察完全二叉树的特点。完全二叉树比起满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层上有叶结点。第6层有叶结点则完全二叉树的高度可能为6或7，显然树高为7时结点更多。若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺失了8×2＝16个叶结点，故完全二叉树的结点个数最多为27-1-16=111个结点。
6.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原
来的森林中，u和v可能具有的关系是______。
Ⅰ．父子关系
Ⅱ．兄弟关系
Ⅲ．u的父结点与v的父结点是兄弟关系
A.只有Ⅰ
B.Ⅰ和Ⅱ
C.Ⅰ和Ⅲ
D.Ⅰ、Ⅱ和Ⅲ
【解析】B。考察森林和二叉树的转换。森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。
情形Ⅰ：若结点v是结点u的第二个孩子结点，在转换时，结点v就变成结点u第一个孩子的右孩子，符合要求。
情形Ⅱ：结点u和v是兄弟结点的关系，但二者之中还有一个兄弟结点k，则转换后，结点v就变为结点k的右孩子，而结点k则是结点u的右孩子，符合要求。
情形Ⅲ：结点v的父结点要么是原先的父结点或兄弟结点。若结点u的父结点与v的父结点是兄弟关系，则转换之后，不可能出现结点u是结点v的父结点的父结点。
7.下列关于无向连通图特性的叙述中，正确的是_____。
Ⅰ．所有顶点的度之和为偶数
Ⅱ．边数大于顶点个数减1
Ⅲ．至少有一个顶点的度为1
A.只有Ⅰ
B.只有Ⅱ
C.Ⅰ和Ⅱ
D.Ⅰ和Ⅲ
【解析】A。考察无向连通图的特性。每条边都连接了两个结点，则在计算顶点的度之时，这条边都被计算了两次，故所有顶点的度之和为边数的两倍，显然必为偶数。而Ⅱ和Ⅲ则不一定正确，如：对顶点数N≥1无向完全图不存在一个顶点的度为1，并且边数与顶点数的差要大于1。
8.下列叙述中，不符合m阶B-树定义要求的是______。
A.根节点最多有m棵子树
B.所有叶结点都在同一层上
C.各结点内关键字均升序或降序排列
D.叶结点之间通过指针链接
【解析】D。考察m阶B-树的定义。A、B和C都是B-树的特点，而答案D则是B+树的特点。
9.已知关键序列5, 8, 12, 19, 28, 20, 15, 22是小根堆（小顶堆），插入关键字3，调整后得到
的小根堆是______。
A.3, 5, 12, 8, 28, 20, 15, 22, 19
B.3, 5, 12, 19, 20, 15, 22, 8, 28
C.3, 8, 12, 5, 20, 15, 22, 28, 19
D.3, 12, 5, 8, 28, 20, 15, 22, 19
【解析】A。考察小根堆的调整操作。小顶堆在逻辑上可以用完全二叉树来表示，根据关键序列得到的小顶堆的二叉树形式为下图左图：
5
8
19 2228
12
2015
3
5
8
22
28
12
2015
19
插入关键字3时，先将其放在小顶堆的末端，再将该关键字向上进行调整，得到的结果如上图右边所示。所以，调整后的小顶堆序列为：3, 5, 12, 8, 28, 20, 15, 22, 19。
10.若数据元素序列11, 12, 13, 7, 8, 9, 23, 4, 5是采用下列排序方法之一得到的第二趟排序后
的结果，则该排序算法只能是______。
A.起泡排序
B.插入排序
C.选择排序
D.二路归并排序
【解析】B。考察各排序算法的特点。解答本题之前要对不同排序算法的特点极为清楚。对于起泡排序和选择排序而言，每一趟过后都能确定一个元素的最终位置，而由题目中所说，前两个元素和后两个元素均不是最小或最大的两个元素并按序排列。答案D中的二路归并排序，第一趟排序结束都可以得到若干个有序子序列，而此时的序列中并没有两两元素有序排列。插入排序在每趟排序结束后能保证前面的若干元素是有序的，而此时第二趟排序后，序列的前三个元素是有序的，符合其特点。故正确答案是B。
二、综合应用题
1.带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点
到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：
(1)设最短路径初始时仅包含初始顶点，令当前顶点u 为初始顶点；
(2)选择离u 最近且尚不在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u = v；
(3)重复步骤2，直到u 是目标顶点为止。
请问上述方法能否求得最短路径？若该办法可行，请证明之；否则，请举例说明。
【解析】：利用该方法求得不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从A 到C 的最短路径是A->B->C，事实上其最短路径是A->D->C。
2.已知一个带有表头结点的单链表，结点结构为：
data link
假设该单链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data 域的值，并返回1；否则，只返回0。要求：
(1)描述算法的基本设计思想；
(2)描述算法的详细实现步骤；
(3)根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或Java语言实现），关键之处请给出简要注释。
【解析】本题详细解析如下：
(1)算法的基本设计思想：问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第k个结点的位置。算法的基本设计思想是：定义两个指针变量p和q，初始时均指向头结点的下一个结点（链表的第一个结点）。p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到最后一个结点时，q指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描。
(2)算法的详细实现步骤：
①count=0，p和q指向链表表头结点的下一个结点；
②若p为空，转⑤；
③若count等于k，则q指向下一个结点；否则，count=count+1；
④p指向下一个结点，转②；
⑤若count等于k，则查找成功，输出该结点的data域的值，返回1；否则，说明k值超过了线性表的长度，查找失败，返回0；
⑥算法结束。
(3)算法实现：
typedef struct Node{
ElemType data;
struct Node *next;
} *Pointer;
Pointer LinkList;
int Search_k(Pointer &list, int k)
//查找链表list倒数第k个结点，并输出该结点data域的值
{
p = list->next;
q = list->next; //指针p、q指示第一个结点
int count = 0;
while (p!=NULL)
{ //遍历链表直到最后一个结点
if (count count++; //计数，若count else q = q->next; p = p->next; //之后让p、q同步移动 } //while if (count return 0; //查找失败返回0 else { //否则打印并返回1 printf ("%d", q->data); return 1; } } //Search_k 提示：算法程序题，如果能够写出数据结构类型定义、正确的算法思想都会至少给一半以上分数，如果能用伪代码写出自然更好，比较复杂的地方可以直接用文字表达。 2010年计算机统考数据结构部分真题解析 一、单项选择题 1.若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次 进行退栈工作，则不可能得到的出栈序列是______。 A.dcebfa B.cbdaef C.bcaefd D.afedcb 【解析】D。考察出栈序列。 A可由in, in, in, in, out, out, in, out, out, in, out, out得到； B可由in, in, in, out, out, in, out, out, in, out, in, out得到； C可由in, in, out, in, out, out, in, in, out, in, out, out得到； D可由in, out, in, in, in, in, in, out, out, out, out, out得到；但要求不允许连续三次退栈操作，D错。 2.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺 序是______。 A.bacde B.dbace C.dbcae D.ecbad 【解析】C。考察受限的双端队列的出队序列。 A可由左入，左入，右入，右入，右入得到； B可由左入，左入，右入，左入，右入得到； D可由左入，左入，左入，右入，左入得到； 所以不可能得到C。 3.下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是______。 A. B. C. D. 【解析】D。考察线索二叉树的基本概念和构造。题中所给二叉树的后序序列为dbca。结点d无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b；结点b无左子树，左链域指向其前驱结点d；结点c无左子树，左链域指向其前驱结点b，无右子树，右链域指向其后继结点a。正确选项为D。 4.在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树 中，关键字37所在结点的左、右子结点中保存的关键字分别是______。 24 13 3753 90 A.13, 48 B.24, 48 C.24, 53 D.24, 90 【解析】C。考察平衡二叉树的插入算法。插入48以后，该二叉树根结点的平衡因子由-1变为-2，失去平衡，需进行两次旋转（先右旋后左旋）操作。 5.在一棵度数为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点， 10个度为1的结点，则树T的叶结点个数是______。 A.41 B.82 C.113 D.122 【解析】B。考察树结点数的特性。设树中度为i（i=0, 1, 2, 3, 4）的结点数分别为N i，树中结点总数为N，则树中各结点的度之和等于N-1，即N = 1+N1+2N2+3N3+4N4 = N0+ N1+N2+N3+N4，根据题设中的数据，即可得到N0 = 82，即树T的叶结点的个数是82。 6.对n（n>=2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是______。 A.该树一定是一棵完全二叉树 B.树中一定没有度为1的结点 C.树中两个权值最小的结点一定是兄弟结点 D.树中任一非叶结点的权值一定不小于下一层任一结点的权值 【解析】A。考察哈夫曼树的特性。哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。哈夫曼树中没有度为１的结点，B正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C正确；哈夫曼树中任一非叶结点P的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P的左右子树根结点处于同一层的结点中，若存在权值大于结点P权值的结点Q，那么结点Q的兄弟结点中权值较小的一个应该与结点P作为左右子树构造新的二叉树，综上可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。 7.若无向图G=（V，E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边 数最少是_____。 A.6 B.15 C.16 D.21 【解析】C。考察图的连通性。要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通，首先需要G的任意六个结点构成完全连通子图G1，需15条边，然后再添一条边将第7个结点与G1连接起来，共需16条边。 8.对下图进行拓扑排序，可以得到不同的拓扑序列的个数是_____。 A.4 B.3 C.2 D.1 【解析】B。考察拓扑排序序列。题中图有三个不同的拓扑排序序列，分别为abced, abecd, aebcd。 9.已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个 不存在的元素，则比较次数最多的是_____。 A.4 B.5 C.6 D.7 【解析】B。考察折半查找的过程。具有n 个结点的判定树的高度为log2n，本题中顺序表的长度为16，高度为5，所以最多比较5 次。 10.采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是______。 A.递归次数与初始数据的排列次数无关 B.每次划分后，先处理较长的分区可以减少递归次数 C.每次划分后，先处理较短的分区可以减少递归次数 D.递归次数与每次划分后得到的分区处理顺序无关 【解析】D。考察快速排序。递归次数与各元素的初始排列有关。如果每一次划分后分区比较平衡，则递归次数少，如果划分后分区不平衡，则递归次数多。递归次数与处理顺序无关。 11.对一组数据（2, 12, 16, 88, 5, 10）进行排序，若前三趟排序结果如下： 第一趟：2, 12, 16, 5, 10, 88 第二趟：2, 12, 5, 10, 16, 88 第三趟：2, 5, 10, 12, 16, 88 则采用的排序方法可能是______。 A.冒泡排序法 B.希尔排序法 C.归并排序法 D.基数排序法 【解析】A。考察各种排序算法的过程。看第一趟可知仅有88 被移到最后。 如果是希尔排序，则12, 88, 10 应变为10, 12, 88。因此排除希尔排序。 如果是归并排序，则应长度为2 的子序列是有序的，由此可排除归并。 如果是基数排序，则16, 5, 10 应变为10, 5, 16，由此排除基数。 可以看到，每一趟都有一个元素移到其最终位置，符合冒泡排序特点。 二、综合应用题 1.将关键字序列(7, 8, 30, 11, 18, 9, 14)散列存储到散列表中，散列表的存储空间是下标从0 开始的一个一维数组。散列函数为：H(key)=(key×3)MOD T，处理冲突采用线性探测再散列法，要求装载因子为0.7。 问题： (1)请画出所构造的散列表。 (2)分别计算等概率情况下，查找成功和查找不成功的平均查找长度。 【解析】： (1)由装载因子0.7，数据总个数为7得存储的一维数组为7/0.7=10。所以构造的散列表为：H(7)=(7*3)MOD 10=1，H(8)=4，H(30)=0，H(11)=3，H(18)=4（冲突），H(18)=(H(18)+1)MOD (2)查找成功的ASL = (1+1+1+1+2+1+1)/ 7=8/7 查找不成功的ASL = (7+6+5+4+3+3+1+2+1+1)/ 10=3.3 2.设将n(n>1)个整数存放到一维数组R中。设计一个在时间和空间两方面尽可能高效的算 法。将R 中的序列循环左移P （0 (1)给出算法的基本设计思想。 (2)根据设计思想，采用C 或C++或JAVA 语言描述算法，关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。 【解析】： (1)算法的基本设计思想：可以将这个问题看做是把数组ab 转换成数组ba （a 代表数组的前p 个元素，b 代表数组中余下的n-p 个元素），先将a 逆置得到a -1b ，再将b 逆置得到a -1b -1，最后将整个a -1b -1逆置的到（a -1b -1）-1=ba 。设Reverse 函数执行将数组元素逆置的操作，对abcdefgh 向左循环移动3（p=3）个位置的过程如下： Reverse(0, p-1)得到cbadefgh ； Reverse(p, n-1)得到cbahgfed ； Reverse(0, n-1)得到defghabc ； 注：Reverse 中，两个参数分别表示数组中待转换元素的始末位置。 (2)使用C 语言描述算法如下： void Reverse(int R[], int from, int to) { int i, temp; for(i = 0; i <(to-from+1)/2; i++) { temp = R[from+i]; R[from+i] = R[to-i]; R[to-i] = temp; } }// Reverse void Converse(int R[], int n, int p) { Reverse(R, 0, p-1); Reverse(R, p, n-1); Reverse(R, 0, n-1); } (3)上述算法中三个Reverse 函数的时间复杂度分别为O(p 2), O(np 2) 和O(n 2)，故所设计的算法的时间复杂度为O(n)，空间复杂度为O(1)。 另解一，借助辅助数组来实现： 算法思想：创建大小为p 的辅助数组S ，将R 中前p 个整数依次暂存在S 中，同时将R 中后n-p 个整数左移，然后将S 中暂存的p 个数依次放回到R 中的后续单元。 时间复杂度为O(n)，空间复杂度为O(p)。 另解二，源自《编程珠玑》巧妙的杂技表演： 算法思想：先将x[0]内容移到临时变量temp 中，然后将x[i]移到x[0]中、x[2i]移到x[i]中，依次类推（将x 中所有下标都对n 取模），直到我们又回到从x[0]中提取元素，不过在这时我们要从temp 中提取元素，然后结束该过程。举例：设p=3。 初始，令temp=0。7→4，(7+3)%8=2→7，5→2，(5+3)%8=0=temp→5。（下划线表示下次要移向的位置）这样，序列就变成了我们想要的：3 4 5 6 7 0 1 2。 算法的时间复杂度为O(n)，空间复杂度为O(1)。 2011年计算机统考数据结构部分真题解析 一、单项选择题 1. 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是______。 x = 2; while (x< n/2) x = 2*x; A.2O(log n) B.O(n) C.2O(n log n) D.2O(n ) 【解析】A 。考察算法的时间复杂度。程序中，执行频率最高的语句为“x=2*x ”。由频度统计法可知，基本操作执行的次数即为程序的时间复杂度，因此可设基本操作执行k 次结束，则有： 执行第1次：x=2?2=21+1=4； 执行第2次：x=4?2=22+1=8； ?? 执行第k 次：x=2k+1； 由循环结束条件知：x 2. 元素a, b, c, d, e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元 素都出栈，则在所有可能的出栈序列中，以d 开头的序列个数是 。 A.3 B.4 C.5 D.6 【解析】B 。考察栈的基本操作。若要保证出栈序列以d 开头，则前三个元素必连续进栈，中间不能出现出栈的情况，然后d 出栈，此时栈内元素由底到顶为a, b, c ，栈外元素为e ，出栈序列中元素为d 。 因为a, b, c 三个元素在栈内的顺序已定，由栈的先进后出原则，其在出栈序列中的相对位置必为?c ?b ?a ?；加上d 的位置已定，所以出栈待定序列必为d ?c ?b ?a ?。显然在栈外的e 可以再任何时候出栈入栈，即可以出现在以上待定序列中任何一个省略号的位置，即出栈序列可为： 1：d, e, c, b, a ；2：d, c, e, b, a ；3：d, c, b, e, a ；4：d, c, b, a, e 。 3. 已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front 和rear 分别指向队头和队 尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front 和rear 的值分别是 。 A.0, 0 B.0, n-1 C.n-1, 0 D.n-1, n-1 【解析】B 。考察队列的基本操作。插入元素时，front 不变，rear+1。而插入第一个元素后，队尾指针要指向尾元素，显然，rear 初始时应该为n-1，front 为0。 4. 若一棵完全二叉树有768个结点，则该二叉树中叶子结点的个数是 。 A.257 B.258 C.384 D.385 【解析】C 。考察二叉树的性质。由完全二叉树的高度和结点个数的关系可得本完全二 叉树的高度为10。第10层上的结点个数为768-（29-1）=257（这些全为叶子结点）；第9层上的非叶结点个数为（257-1）/2+1=129；则第9层上的叶子结点个数为：29-1-129=127；则叶子结点总数为：257+127=384。 5.若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1，则该二叉树的 中序遍历序列不会是。 A.1, 2, 3, 4 B.2, 3, 4, 1 C.3, 2, 4, 1 D.4, 3, 2, 1 【解析】C。考察二叉树的遍历。满足题干的二叉树必须满足树中不存在双分支结点。则可以画出以下二叉树排除选项： A：1 2 3 4 B： 1 2 3 4 D： 1 2 3 4 可以看出A, B, D三项都是可以的。 6.已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结 点的个数是。 A.115 B.116 C.1895 D.1896 【解析】D。考察树与二叉树的转换。可以采用特殊情况法求解。可举以下特例： 共 1895 个 中 间 结 点 共116个叶结点 如上图，则对应的二叉树中仅有前115个结点有右孩子。 7.对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是。 A.95, 22, 91, 24, 94, 71 B.92, 20, 91, 34, 88, 35 C.21, 89, 77, 29, 36, 38 D.12, 25, 71, 68, 33, 34 【解析】A。考察二叉排序树的查找。由选项A做出路径的一部分，发现91的左子树中出现了大于91的94，则A是错误的。 95 22 91 24 94 8.下列关于图的叙述中，正确的是。 ①回路是简单路径 ②存储稀疏图，用邻接矩阵比邻接表更省空间 ③若有向图中存在拓扑序列，则该图不存在回路 A.仅① B.仅①、② C.仅③ D.仅①、③ 【解析】C。考察图的相关知识。若路径中除了开始点和结束点可以相同之外，其余顶点都不相同，则称这条路径为简单路径。若一条路径中第一个顶点和最后一个顶点相同，则这条路径为回路。邻接矩阵不管图是稀疏还是稠密，所取空间都是相同的，因此不如邻接表存储稀疏图更合适。用拓扑排序可以判断图中是否存在回路，如果一个图可以完成拓扑排序，则此图不存在回路。 9.为提高散列（Hash）表的查找效率，可采取的正确措施是。 ①增大装填因子 ②设计冲突少的散列函数 ③处理冲突时避免产生聚集现象 A.仅① B.仅② C.仅①、② D.仅②、③ 【解析】B。考察散列表的相关知识。要提高查找效率，就要减少散列表的冲突，因此②是正确的措施。对于①装填因子增大，则相应表中空闲位置就少，更容易产生冲突，因此 ①不对。聚集现象是不可避免的，因此③不对。 10.为实现快速排序算法，待排序序列宜采用的存储方式为。 A.顺序存储 B.散列存储 C.索引存储 D.链式存储 【解析】A。考察快速排序的相关知识。快速排序需要定位运算，采用顺序存储方式。 11.已知序列25、13、10、12、9是大根堆，在序列尾部插入新元素18，将其在调整为大 根堆，调整过程中元素之间进行的比较次数是。 A.1 B.2 C.4 D.5 【解析】B。考察堆的建立。按照堆的建立算法，可知答案为B。 二、综合应用题 1.已知有一个6个顶点（顶点编号为0～5）的有向带权图G，其邻接矩阵A为上三角矩 阵，它的压缩存储如下： 要求： (1)图G的邻接矩阵A； (2)画出有向带权图G； (3)求图G的关键路径，并计算关键路径的长度。 【解析】本题考察图的存储以及关键路径求解的综合知识。 (1)由题意可知，邻接矩阵为上三角矩阵，其结构图如下所示： 其中“？”表示待定元素。 0 ？？？？？ ∞0 ？？？？ ∞∞0 ？？？ ∞∞∞0 ？？ ∞∞∞∞0 ？ ∞∞∞∞∞0 可以看出第一行到第五行待定元素个数分别为5, 4, 3, 2, 1，由此可以知道其压缩矩阵第1个到第5个值依次为第1行的5个待定元素，第6个到第9个依次为第2行的4个待定元素，第10个到第12个依次为第3行的3个待定元素，第13个到第14个依次为第4行的2个待定元素，第15个元素为第5行的待定元素。结果如下图所示： A= (2)由邻接矩阵A 容易做出有向带权图，如下： (3)由上图容易求得图的关键路径为<0,1>, <1,2>, <2,3>, <3,5>，其长度为16。 2. 一个长度为L （L ≥1）的升序序列S ，处在第L /2????个位置的数称为S 的中位数。例如，若序列S 1=（11, 13, 15, 17, 19），则S 1的中位数为15。两个序列的中位数是含它们所有 元素的升序序列的中位数。例如：S 2=（2, 4, 6, 8, 10），则S 1和S 2的中位数为11。现有两个等长的升序序列A 和B ，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A 和B 的中位数。要求： (1)给出算法的基本设计思想。 (2)根据设计思想，采用C 或C++或Java 语言描述算法，关键之处给出注释。 (3)说明你所设计算法的时间复杂度和空间复杂度。 【解析】本题考察基本算法的灵活运用。 (1)算法的设计思想： 分别求出两个升序序列A 和B 的中位数，设为a 和b 。 ①若a=b ，则a 或b 即为两个序列A 和B 的中位数。 容易验证，如果将两个序列归并排序，则最终序列中，排在子序列ab 之前的元素为先前序列中排在a 和b 之前的元素，排在子序列ab 之后的元素为先前序列中排在a 和b 之后的元素，所以子序列ab 一定位于合并序列中间，因为a=b ，所以a 或b 即为两个序列的中位数。 ②否则（假设a 用归并排序后的序列来验证，归并排序后必然出现形如“………a …b ………”的序列，中位数必然位于a 和b 之间。因此可以做如下处理: 舍弃序列A 的中位数a 左边的一半元素，同时舍弃序列B 的中位数b 右边的一半元素，在保留的两个序列升序序列中求出新的中位数，这个中位数为原序列A 和B 的中位数。 重复此过程，知道两个序列都只含有一个元素，则较小者则为A 和B 的中位数。 (2)算法实现： int Search(int A[],int B[],int n) 0 4 6 ∞ ∞ ∞ ∞ 0 5 ∞ ∞ ∞ ∞ ∞ 0 4 3 ∞ ∞ ∞ ∞ 0 ∞ 3 ∞ ∞ ∞ ∞ 0 3 ∞ ∞ ∞ ∞ ∞ 0 { int L1, H1, L2, H2, m1, m2; L1=0; H1=n-1; L2=0; H2=n-1; while ((L1!=H1) || (L2!=H2) ) { m1 = (L1+H1)/2; m2 = (L2+H2)/2; if (m1==m2) return A[m1]; if (m1 { //分别考虑奇数和偶数，保持两个子数组元素个数相等if ((L1+H1)%2==0) //若元素个数为奇数个 { L1 = m1; //舍弃A中间点以前部分且保留中间点 H2 = m2; //舍弃B中间点以后部分且保留中间点} else { //元素个数为偶数个 L1 = m1+1; //舍弃A中间点及其以前部分 H2 = m2; //舍弃B中间点以后部分且保留中间点 } } else { If ((L1+H1)%2==0) //若元素个数为奇数个 { H1 = m1; //舍弃A中间点以后部分且保留中间点 L2 = m2; //舍弃B中间点以前部分且保留中间点} else { //元素个数为偶数个 H1 = m1+1; //舍弃A中间点及其以后部分 L2 = m2; //舍弃B中间点以前部分且保留中间点 } } } return (A[L1] } (3)算法效率分析： O(log)，空间复杂度为O(1)。 该算法的时间复杂度为n 2 数据结构和软件工程简介 数据结构的基本概念 ?数据是描述客观事物并能为计算机加工处理的符号的集合。数据元素是数据的基本单位，即数据集合中的个体。有些情况下也把数据元素称为结点、记录等。一个数据元素可由一个或多个数据项组成。数据项是有独立含义的数据最小单位，有时也把数据项称为域、字段等。 ?数据结构（Data Structure）是指数据元素的组织形式和相互关系。数据结构一般包括以下三方面的内容。 1、数据的逻辑结构 ?数据的逻辑结构从逻辑上抽象地反映数据元素间的结构关系，它与数据在计算机中的存储表示方式无关。 因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 ?数据的逻辑结构有两大类： ?线性结构——线性结构的逻辑特征是：有且仅有一个始端结点和一个终端结点，并且除两个端点结点外的所有结点都有且仅有一个前趋结点和一个后继结点。线性表、堆栈、队列、数组、串等都是线性结构。 ?非线性结构——非线性结构的逻辑特征是：一个结点可以有多个前趋结点和后继结点。如树形结构、图等 2、数据的物理结构 ?数据的物理结构是逻辑结构在计算机存储器里的映像，也称为存储结构。 ?数据的存储结构可用以下四种基本存储方法体现： ?顺序存储方法——把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构称为顺序存储结构。 ?链式存储方法——不要求逻辑上相邻的结点在物理位置上也相邻，结点之间的逻辑关系是由附加的指针字段表示的。由此得到的存储结构称为链式存储结构。 ?索引存储方法——在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项。索引项由关键字和地址组成，关键字是能惟一标识一个结点的那些数据项，而地址一般是指示结点所在存储位置的记录号。 ?散列存储方法——根据结点的关键字直接计算出该结点的存储地址。 ?用不同的存储方法对同一种逻辑结构进行存储映像，可以得到不同的存储结构。四种基本的存储方法也可以组合起来对数据逻辑结构进行存储映像。 3、数据的运算 ?数据的运算是指对数据施加的操作。它是定义在数据的逻辑结构上的，但运算的具体实现要在物理结构上进行。数据的每种逻辑结构都有一个运算的集合，常用的运算有检索、插入、删除、更新、排序等 线性表： 1．顺序表 ?当线性表采用顺序存储结构时称之为顺序表。在顺序表中，数据元素按逻辑次序依次放在一组地址连续的存储单元里。由于逻辑上相邻的元素存放在内存的相邻单元里，所以顺序表的逻辑关系蕴含在存储单元的邻接关系中。在高级语言中，可以直接用数组实现。 2. 单链表 ?采用链式存储结构的链表是用一组任意的存储单元来存放线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的，甚至可以是零星分布在内存中的任何位置上，从而可以大大提高存储器的使用效率。 ?在线性链表中，每个元素结点除存储自身的信息外，还要用指针域额外存储一个指向其直接后继的信息（即后继的存储位置：地址）。 3. 栈与队列 栈与队列是两种特殊的线性表。即它们的逻辑结构与线性表相同，只是其插入、删除运算仅限制在线性表的一端或两端进行。 （答案仅供参考如有不对请自己加以思考） 第一章计算机网络体系结构 一、习题 1．比特的传播时延与链路带宽的关系（）。 A．没有关系 B. 反比关系 C. 正比关系 D. 无法确定 2.计算机网络中可以没有的是（）。 A. 客服机 B. 操作系统 C. 服务器 D.无法确定 3.在OSI参考模型中，提供流量控制的层是第（1）层；提供建立、维护和拆除端到端连接的层是（2）；为数据分组提供在网络中路由功能的是（3）；传输层提供（4）的数据传送；为网络层实体提供数据发送和接收功能和过程的是（5）。 （1）A. 1、2、3 B. 2、3、4 C. 3、4、5 D. 4、5、6 （2）A. 物理层 B. 数据链路层 C. 会话层 D. 传输层 （3）A. 物理层 B. 数据链路层 C. 网络层 D.传输层 （4）A. 主机进程之间 B. 网络之间 C. 数据链路层 D. 物理线路层 （5）A. 物理层 B. 数据链路层 C. 会话层 D. 传输层 4.计算机网络的基本分类方法主要有两种：一种是根据网络所使用的传输技术；另一种是根据（）。 A. 网络协议 B. 网络操作系统 C. 覆盖范围与规模 D. 网络服务器类型与规模 5.计算机网络从逻辑功能上可分为（）。 Ⅰ.资源子网Ⅱ.局域网Ⅲ.通信子网Ⅳ.广域网 A.Ⅱ、Ⅳ B.Ⅰ、Ⅲ B. Ⅰ、Ⅳ D. Ⅲ、Ⅳ 6. 计算机网络最基本的功能是（）。 Ⅰ. 流量控制Ⅱ.路由选择 Ⅲ. 分布式处理Ⅳ. 传输控制 A. Ⅰ、Ⅱ、Ⅳ B.Ⅰ、Ⅲ、Ⅳ C. Ⅰ、Ⅳ D. Ⅲ、Ⅳ 7.世界上第一个计算机网络是（）。 A.ARPANET B. 因特网 C. NSFnet D. CERNET 8. 物理层、数据链路层、网络层、传输层的传输单位（或PDU）分别是（）。 Ⅰ.帧Ⅱ. 比特Ⅲ.报文段Ⅳ.数据报 A.Ⅰ、Ⅱ、Ⅳ、Ⅲ B. Ⅱ、Ⅰ、Ⅳ、Ⅲ C. Ⅰ、Ⅳ、Ⅱ、Ⅲ D. Ⅲ、Ⅳ、Ⅱ、Ⅰ 9.设某段电路的传播时延是10ms，带宽为10Mbit/s，则该段电路的时延带宽积为（）。 A.2×105 bit B.4×105 bit C.1×105 bit D. 8×105 bit 山东建筑大学计算机科学与技术学院 课程设计说明书 题目：基于逆邻接表的有向图基本操作的实现课程：数据结构 院（部）：计算机学院 专业：计科 班级：133 学生姓名：潘含笑 学号：20131111092 指导教师：李盛恩 完成日期：2015.07.03 目录 课程设计任务书.................................................. I 课程设计任务书................................................. II 逆邻接链表实现有向图.. (3) 一、问题描述 (3) 二、数据结构 (3) 三、逻辑设计 (3) 四、编码 (5) 五、测试数据 (14) 六、测试情况 (16) 逆邻接链表实现有向图 (17) 一、问题描述 (17) 二、数据结构 (17) 三、逻辑设计 (17) 四、编码 (18) 五、测试数据 (24) 七、测试情况 (24) 结论 (26) 课程设计指导教师评语 (28) 山东建筑大学计算机科学与技术学院 课程设计任务书 指导教师（签字）：教研室主任（签字） 山东建筑大学计算机科学与技术学院 课程设计任务书 指导教师（签字）：教研室主任（签字） 逆邻接链表实现有向图 二、数据结构 三、逻辑设计 1、总体思路 先实现Network类，通过队列实现BFS，通过堆栈实现DFS和拓扑排序。再构建Graph类，并继承Network类实现以逆邻接链表为存储结构的有向图。 2、模块划分（以图示的方法给出各个函数的调用关系） 3、函数或类的具体定义和功能Network类： 数据结构中栈的介绍 1.栈的概念 栈（Stack）是一种特殊的表，这种表只在表的一端进行插入和删除操作。允许插入和删除数据元素的这一端称为栈顶；而另一固定的一端称为栈底。不含任何元素的栈称为空栈。 栈的修改是按后进先出的原则进行的。栈又称为后进先出(Last In First Out)表，简称为LIFO表。 如图1所示：假设一个栈S中的元素为a n,a n-1,..,a1，则称a1为栈底元素，a n为栈顶元素。 图1 图 2 2.栈的存储与操作 由于栈是一个特殊的表，可以用一维数组来实现栈。同时设立指针t（称为栈顶指针）来指示栈顶元素的当前位置。 我们用一个数组s[1..m]来表示一个栈时，将栈底固定在数组的底部，即s[1]为最早入栈的元素，并让栈向数组上方(下标增大的方向)扩展。当t=0时，表示这个栈为一个空栈。当t=m时，表示这个栈已满。 可以用下列方式定义栈： const m=栈表目数的上限; type stack=array[1..m] of stype; {栈的数据类型} var s:stack; t:integer; {栈顶指针} 进栈、出栈操作的过程和函数（假设栈元素的数据类型为整型）： (1)进栈过程（push） ①若t≥m时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）； ②置t=t+1（栈指针加１，指向进栈地址）； ③S(t)=x，结束（x为新进栈的元素）； procedure push(var s:stack; x:integer;var t:integer); begin if t=m then writeln('overflow') else begin 目录 第一章计算机系统结构基本概念 (2) (一) 概念 (2) (二) 定量分析技术 (3) (三) 计算机系统结构发展 (4) (四) 计算机的并行性 (5) 第二章计算机指令集结构 (7) 一. 指令集结构的分类 (7) 二. 寻址方式 (7) 三. 指令集结构的功能设计 (8) 四. 指令格式的设计 (10) 五. MIPS指令集结构 (10) 第三章流水线技术 (14) 一. 流水线的基本概念 (14) 二. 流水线的性能指标 (14) 三. 流水线的相关与冲突 (16) 四. 流水线的实现 (18) 第四章指令集并行 (18) 付志强 第一章计算机系统结构基本概念 (一)概念 什么是计算机系统结构:程序员所看到的计算机属性,即概念性结构与功能特性. 透明性:在计算机技术中,把本来存在的事物或属性,但从某种角度看又好像不存在的概念成为透明性. 常见计算机系统结构分类法 冯氏分类法(冯泽云):按最大并行度对计算机进行分类. Flynn分类法:按指令流和数据流多倍性进行分类 ①单指令流单数据流 ②单指令流多数据流 ③多指令流单数据流(不存在) ④多指令流多数据流 付志强 (二)定量分析技术 Amdahl定律:加快某部件执行速度所能获得的系统性能加速比,受限于该部件的执行时间占系统中总执行时间的百分比. 加速比=系统性能 改进后 系统性能 改进前 = 总执行时间 改进前 总执行时间 改进后 加速比依赖于以下两个因素 ①可改进比例 ②部件加速比 CPU性能公式 CPU时间 CPU时间=执行程序所需时间的时钟周期数x时钟周期时间(系统频率倒数) CPI(Cycles Per Instruction) CPI =执行程序所需时钟周期数/所执行指令条数 ∴CPU时间= IC x CPI x 时钟周期时间 可知CPU性能取决于一下三个方面 ①时钟周期时间:取决于硬件实现技术和计算机组成 付志强 计算机网络系统是一个集计算机硬件设备、通信设施、软件系统及数据处理能力为一体的,能够实现资源共享的现代化综合服务系统。计算机网络系统的组成可分为三个部分,即硬件系统,软件系统及网络信息系统。 1. 硬件系统 硬件系统是计算机网络的基础。硬件系统有计算机、通信设备、连接设备及辅助设备组成,如图1.6.4所示。硬件系统中设备的组合形式决定了计算机网络的类型。下面介绍几种网络中常用的硬件设备。 ⑴服务器 服务器是一台速度快,存储量大的计算机,它是网络系统的核心设备,负责网络资源管理和用户服务。服务器可分为文件服务器、远程访问服务器、数据库服务器、打印服务器等,是一台专用或多用途的计算机。在互联网中,服务器之间互通信息,相互提供服务,每台服务器的地位是同等的。服务器需要专门的技术人员对其进行管理和维护,以保证整个网络的正常运行。 ⑵工作站 工作站是具有独立处理能力的计算机,它是用户向服务器申请服务的终端设备。用户可以在工作站上处理日常工作,并随时向服务器索取各种信息及数据,请求服务器提供各种服务(如传输文件,打印文件等等)。 ⑶网卡 网卡又称为网络适配器,它是计算机和计算机之间直接或间接传输介质互相通信的接口,它插在计算机的扩展槽中。一般情况下,无论是服务器还是工作站都应安装网卡。网卡的作用是将计算机与通信设施相连接,将计算机的数字信号转换成通信线路能够传送的电子信号或电磁信号。网卡是物理通信的瓶颈,它的好坏直接影响用户将来的软件使用效果和物理功能的发挥。目前,常用的有 10Mbps、100Mbps和10Mbps/100Mbps自适应网卡,网卡的总线形式有ISA和PCI 两种。 北京理工大学珠海学院实验报告 ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY 班级软件工程3班学号 150202102309姓名郭荣栋 指导教师余俊杰成绩 实验题目栈的实现与应用实验时间 一、实验目的、意义 （1）理解栈的特点，掌握栈的定义和基本操作。 （2）掌握进栈、出栈、清空栈运算的实现方法。 （3）熟练掌握顺序栈的操作及应用。 二、实验内容及要求 1.定义顺序栈，完成栈的基本操作：建空栈、入栈、出栈、取栈顶元素（参见教材45页）。 2. 调用栈的基本操作，将输入的十进制数转换成十六进制数。 3. 调用栈的基本操作，实现表达式求值，如输入3*（7-2）#，得到结果15。 三、实验结果及分析 （所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。） 四、程序清单(包含注释) 1、2. #include typedef int SElemType; typedef int Status; typedef struct{ SElemType *base; SElemType *top; int stacksize; }Sqstack; void StackTraverse(Sqstack S) { while (S.top != S.base) { cout << *(S.top-1) << endl; S.top--; } } Status InitStack(Sqstack &S){ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base){ exit(OVERFLOW); } https://www.doczj.com/doc/5615688747.html,/homepage/KnuthRes ume.htm 1938年12月7日，Donald E. Knuth 出生 于美国威斯康星州密尔沃基市。其父是个中学教 师，经常在星期天到教堂演奏管风琴，小Knuth 耳濡目染，日后也成为教师，业余爱好也是弹管风 琴。 ☆1956年进入俄亥俄州克利夫兰的凯斯理工学院（现并入凯斯西储大学），学习物理。 1957年大学一年级暑假在学校打工，接触到当时很先进的IBM650 计算机，对其产生浓厚的兴趣。 ☆1958年改学数学，并从此与计算机结缘。 ☆1960年毕业，因为成绩过于出色，校方打破惯例，Knuth 被同时授予学士和硕士学位。随后进入加州理工学院数学系。 1960-1968年，兼任Burroughs 公司顾问。 1961年结婚，夫人小他一岁。现有一儿一女。 1963年取得博士学位，并留校任助理教授。 1964-1967年，兼任美国计算机协会刊物《程 序设计语言》编辑。 1966年升为副教授。 ☆1968年（30岁）任教于斯坦福大学计算机科学系，正教授。同年，开始撰写著名的《计算机程序设计艺术》一书。 ☆1968年《计算机程序设计艺术》第一卷《基本算法》出版。 ☆1969年，第二卷《半数字化算法》出版。 1971年获首届美国计算机协会格蕾丝·赫柏奖。 ☆1973年，第三卷《排序与搜索》出版。同年还出版了第一卷的第二版。有人曾说，看了这部书后，再谈起编程序都会变得谦虚谨慎。比尔·盖茨曾说：“如果你能读懂整套书的话，请给我发一份你的简历。”同年，当选为美国科学艺术学院院士。截至到1973年的第一卷第二版，采用都是的活字排版印刷，这需要经验丰富的活字排版工人。 ☆1974年（36岁），因在算法分析和编程语言设计方面的突出贡献，荣获美国计算机协会图灵奖，是历史上最年轻的获奖者。图灵奖被称为计算机界的诺贝尔奖。《计算机程序设计艺术》一书与牛顿的《自然哲学的数学原理》等书一起，被评为“世界历史上最伟大的十种科学著作”之一。 1975年当选为美国国家科学院院士。 ☆1976年出版第二卷第二版时采用了计算机排版技术。但是，当时的计算机排版与活字排版效果相差甚远，而且前后两卷的字体、版式和文本格式等都不一致。非常失望的Knuth 暂停了第二卷第二版的出版，决心自己设计一个比活字排版更加优美和适用的排版软件，这就是后来的TeX 。 1977年5月开始构造后来被称为 TeX 的文字处理系统，他研究了古今的排版技术，把其中最优越的部分引入TeX 中，连TeX 中 第一部分：计算机系统组成及说明 一、计算机系统组成 一个完整的计算机系统通常是由硬件系统和软件系统两大部分组成的。（一）硬件（hardware） 硬件是指计算机的物理设备，包括主机及其外部设备。具体地说，硬件系统由运算器、控制器、存储器、输入设备和输出设备五大部件组成。 ①存储器。存储器是计算机用来存放程序和原始数据及运算的中间结果和最后结果的记忆部件。 ②运算器。运算器对二进制数码进行算术或逻辑运算。 ③控制器。控制器是计算机的“神经中枢”。它指挥计算机各部件按照指令功能的要求自动协调地进行所需的各种操作。 ④输入/输出设备（简称I/O设备）。计算机和外界进行联系业务要通过输入输出设备才能实现。输入设备用来接受用户输入的原始数据和程序，并将它们转换成计算机所能识别的形式（二进制）存放到内存中。输出设备的主要功能是把计算机处理的结果转变为人们能接受的形式，如数字、字母、符号或图形。 （二）软件（software） 软件是指系统中的程序以及开发、使用和维护程序所需要的所有文档的集合。包括计算机本身运行所需的系统软件和用户完成特定任务所需的应用软件（三）硬件和软件的关系 硬件是计算机的基础，软件对硬件起辅助支持作用，二者相辅相成，缺一不可，只有有了软件的支持，硬件才能充分发挥自己的作用。 二、计算机工作原理 （一）冯·诺依曼设计思想 计算机问世５０年来，虽然现在的计算机系统从性能指标、运算速度、工作方式、应用领域和价格等方面与当时的计算机有很大的差别，但基本体系结构没有变，都属于冯·诺依曼计算机。 冯·诺依曼设计思想可以简要地概括为以下三点： ①计算机应包括运算器、存储器、控制器、输入和输出设备五大基本部件。 ②计算机内部应采用二进制来表示指令和数据。每条指令一般具有一个操作码和一个地址码。其中，操作码表示运算性质，地址码指出操作数在存储器的位置。 ③将编好的程序和原始数据送入内存储器中，然后启动计算机工作，计算机应在不需操作人员干预的情况下，自动逐条取出指令和执行任务。 冯·诺依曼设计思想最重要之处在于他明确地提出了“程序存储”的概念。他的全部设计思想，实际上是对“程序存储”要领的具体化。 1 课程设计介绍 1.1课程设计项目简介 家谱是一种以表谱形式，记载一个以血缘关系为主体的家族世系繁衍和重要人物事迹的特殊图书载体。家谱是中国特有的文化遗产，是中华民族的三大文献之一，属珍贵的人文资料，对于历史学，民俗学，人口学，社会学和经济学的深入研究，均有不可替代的重要功能。本项目对家谱管理进行简单的模拟，以实现查看祖先和子孙个人信息、插入家族成员等功能。 1.2课设题目分析 本程序的实质是完成对家谱成员信息的建立、查找、插入等功能。可以首先定义家族成员的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。 本程序包含以下几个模块 （1）建立家族关系树。此模块将构建一个家族关系，对数据初始化，构造关系树并录入数据一遍后续程序使用。 （2）添加新成员。此模块将添加一个新成员，实现对家族关系的修改。 （3）家族关系的查询。此模块将实现对家族不同关系的查询（4）主程序模块。此模块实现整个程序的进入和进出，以及各种初始化处理。 （5） 1.3课程题目原理与数据结构 因为家族的成员之间存在一个对多个的层次结构关系，所以不能用线性表来表示和实现。家谱从形状上看像一颗倒长的树，所以用树结构来表示比较合适。树形结构是一类非常重要的非线性数据结构，直观看来树是以分支关系定义的层次结构。 因此本课程设计可以采用的数据结构有树状结构和队列。树状结构采用三叉链表来实现，队列采用链式队列实现。 1.4功能分析说明图 2 分析与实现 2.1 基本数据结构和栈队的操作 2.1.1 结点基本数据结构和链队的定义 /*家族关系树实现*/ #include 车间定岗定编组织结构图(doc 42页) 生产部各单位/车间定岗定编组织结构图(新) 生产部各单位/车间定岗定编组织结构图（一车间） 一车间 甲乙拌造 机 二号机三 号 机 四 号 机 五 号 机 六 号 机 七 号 机 八 号 机 九 号 机 十 号 机 机 长 助 手 技 术 仓 管 一号机 岗 位名称姓 名 岗位职责作业要求 相关制度 表格 车间主管1、协助生产经理开展各项工作 2、每天早晚跟踪班组长的工作安排，并落实班组长的职责 3、做好车间的工具、设备、原材料的管理，每月对车间易损耗物品进行申购和跟踪 4、负责车间管理人员、操作工、技术指导，培训和协调班组之间的沟通工作，宣传公司各项方针政策 5、保证产品质量、提高产量、节能降耗，树立车间管理人员的责任感 6、服从公司领导安排，完成公司领导交待的各项工作任务 7、保证公司的一切生产进行完全按照公司管理文件及相关规定执行； 8、负责组织本部门有关人员研究解决生产过程中存在的工艺技术和质量问题，支持召开每周生产作业例会 9、建议任免本部门班组长及相关人员，经公司批准执行； 10、对车间班组长及相关技术操作工进行考核 11、负责建立自查制度，对生产全过程监督 12、负责对本部门现场工作的全过程监督及5S的推行 13、负责对本部行政及人事安排。 班长1、负责本班人员的技能培训指导能够达到更好的技能 2、负责人事及人员调动安全生产随时人员调动或替补 3、负责原料物料跟踪，杜绝浪费及质量 监督 节约成本，工艺流程顺利 4、负责车间临时突发事件把事情或事情的可发性降到最低 5、负责员工考勤及时报给统计 机长1、协助班组会日常工作 2、认真完成车间下达的工作安排 3、工作遇到问题向班长反映 4、负责对新员工的培训 拌料员1、根据车间下达的订单按比例拌料 2、负责对原材料情况的上报 3、负责对拌料区的卫生工作 造粒1、负责对粉碎过的废料加工 2、负责将加工好的原料入库 机修1、负责对车间机器的维修及零件的申购 2、负责对车间机器的保养 3、负责对记录表的存放 《计算机系统结构》课程教学大纲 一、课程基本信息 课程代码: 课程名称：计算机系统结构 英文名称：Computer Architecture 课程类别: 专业课 学时：72(其中实验18学时) 学分: 3.5 适用对象: 计算机科学与技术、网络工程专业 考核方式：考试（其中平时成绩占30%，期末考试成绩占70%） 先修课程：计算机组成原理、操作系统 二、课程简介 本课程是计算机专业一门重要的专业基础课，对于培养学生的抽象思维能力和自顶向下、系统地分析和解决问题的能力有非常重要的作用。其目标是使学生掌握计算机系统结构的基本概念、基本原理、基本结构、基本设计和分析方法，并对计算机系统结构的发展历史和现状有所了解。通过学习本课程，能把在“计算机组成原理”等课程中所学的软、硬件知识有机地结合起来，从而建立起计算机系统的完整概念。 This course is a computer professional important foundation for the professional class, for training students in abstract thinking, and top-down, System analysis and the ability to solve problems is a very important role. The goal is to enable students to master computer system structure the basic concepts, basic principles and basic structure, basic design and analysis methods and computer system architecture and the history of the development of an understanding of the status quo. Through the study of this course, can in "Principles of Computer Organization", y the school curriculum of the software and hardware knowledge combined organic, Computer systems in order to establish the integrity of the concept. 三、课程性质与教学目的 《计算机系统结构》的教学对象为计算机相关专业的高年级本科生专业技术基础课程，目的是介绍计算机体系结构的概念、技术和最新动态，着重介绍软，硬件功能分配以及如何最佳、最合理地实现软、硬件功能分配。要求了解基本概念、基本原理、基本结构和基本分析方法。使学生对计算机系统结构、组成和实现有一个整体掌握。 四、教学内容及要求 第一单元计算机系统结构的基本概念 数据结构 概述 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 目录[隐藏] [编辑本段] 基本简介 数据结构在计算机科学界至今没有标准的定义。个人根据各自的理解的不同而有不同的表述方法： Sartaj Sahni在他的《数据结构、算法与应用》一书中称：“数据结构是数据对 例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。 Clifford A.Shaffer在《数据结构与算法分析》一书中的定义是：“数据结构是ADT （抽象数据类型 Abstract Data Type）的物理实现。” Lobert L.Kruse在《数据结构与程序设计》一书中，将一个数据结构的设计过 程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。 [编辑本段] 重要意义 一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。 在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。 选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。 [编辑本段] 研究内容 在计算机科学中，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。 “数据结构”作为一门独立的课程在国外是从1968年才开始设立的。1968年美 国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》 第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、 计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。 计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：信息的表示，信息的处理。 ????????? ? ????? ?????=01 000000010010100000 010********* Edge 第8章 图 8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n 个顶点的无向完全图中，边的条数为n(n -1)/2。 【解答】 【证明】 在有n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有n -1 条边与其他n -1个顶点相连，总计n 个顶点有n(n -1)条边。但在无向图中，顶点i 到顶点j 与顶点j 到顶点i 是同一条边，所以总共有n(n -1)/2条边。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。 【解答】 判断一个有向图是否强连通，要看从任一顶点出发是否能够回到该顶 点。右面的有向图做不到这一点，它不是强连通的有向图。各个顶点自成强连通分量。 所谓简单路径是指该路径上没有重复的顶点。 从顶点A 出发，到其他的各个顶点的简单路径有A →B ，A →D →B ，A →B →C ，A →D →B →C ，A →D ，A →B →E ，A →D →E ，A →D →B →E ，A →B →C →F →E ，A →D →B →C →F →E ，A →B →C →F ，A →D →B →C →F 。 从顶点B 出发，到其他各个顶点的简单路径有B →C ，B →C →F ，B →E ，B →C →F →E 。 从顶点C 出发，到其他各个顶点的简单路径有C →F ，C →F →E 。 从顶点D 出发，到其他各个顶点的简单路径有D →B ，D →B →C ，D →B →C →F ，D →E ，D →B →E ，D →B →C →F →E 。 从顶点E 出发，到其他各个顶点的简单路径无。 从顶点F 出发，到其他各个顶点的简单路径有F →E 。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。 【解答】 (1) 邻接矩阵 1个顶点的 无向完全图 2个顶点的 无向完全图 3个顶点的 无向完全图 4个顶点的 无向完全图 5个顶点的 无向完全图 生产部职能与组织结构 一、生产部职责 生产部在企业的生产经营过程中，主要承担着制订分解企业各阶段的生产计划，并对生产计划的执行情况进行监督控制的职责。其具体职责体现在以下五个方面。 （一）制订生产计划 1．进行企业产能、设备负荷及生产人员的配置。 2．制定企业生产指标。 3．编制企业年度综合生产计划。 4．分解年度、季度、月度生产计划，明确各生产单位、车间的生产任务，以及各种型号产品的投入产出期和投入产出量。 5．制定各产品的生产周期、在制品定额和生产批量等标准。 （二）执行生产计划 1．执行生产计划，进行生产物料、设备、人员、信息、工艺的有机配合，确保按时、保质地完成生产任务。 2．车间生产材料、半成品、成品的管理。 3．编排生产单位、车间的作业流水线，配备相应的人员，安排所需的设备、材料的。 4．监督生产现场的作业，加大管理力度。 5．处理生产异常情况，根据实际情况灵活地调整生产计划。 （三）进行生产控制 1．依据生产计划对生产过程进行监控。 2．按月组织在制品盘点，消除过量储备和损坏丢失现象，减少资金占用。 3．不定期检查生产人员执行操作规程、工艺规程的情况，防止质量事故和安全事故的发生。 4．生产过程中对具体工艺、技术问题的研讨与处理。 5．监控生产系统中的各类管理制度的实施，加强安全生产教育，减少生产事故的发生。 6．生产过程中的环境保护与污染治理。 （四）统计生产信息 1．统计和分析各生产单位和车间的生产进度数据、各个产品的物料消耗数据和各产品所用工时数据，为生产决策提供依据。 2．检查、复核并监督各生产单位、车间的统计报表。 3．追踪生产进度、产品数量及成品数量。 4．及时统计各生产单位存在的问题及需求，以便及时解决存在的问题和改进生产决策。 （五）外协管理 1．编制外协计划，确定外协品的交货时间、数量、地点等。 2．选择并考核外协厂家，不定期地对其进行评估。 3．统计外协品的供应信息，根据实际情况调整外协计划。 二、生产部组织结构 生产部可依据企业的类型、规模、经营范围等的不同选择不同的结构模式，设置不同的管理层次、职能小组并进行人员配置。 （一）小型企业生产部组织结构 小型企业生产部组织结构如图1-1所示。 图1-1 小型企业生产部组织结构示例 （二）中型企业生产部组织结构 1．中型企业生产部组织结构如图1-2所示。 图1-2 中型企业生产部组织结构示例 2．中型企业生产部组织结构也可采用如图1-3所示的形式。 体系结构高性能的追求 计算机体系结构是选择并相互连接硬件组件的一门科学和艺术，在人们不断探索研究的过程中，一直在追求计算机的功能、性能、功率以及花费的高度协调，以期达到各方面的最佳状态，在花费、能量、可用性的抑制下，实现计算机的多功能、高性能、低功率、少花费的一个新时代。 根据当前体系结构的发展现状，要实现以上全部要求的一台计算机，还存在着诸多的限制条件，包括逻辑上的以及硬件上的。本篇综述针对2008年的ISCA会议上的几篇论文，经过仔细研读，深刻剖析，这些文章将现在计算机体系结构发展遇到的各种瓶颈列出，并给出了相关的意见及可行的解决方案。 计算机的体系结构范围很广，定义也很宽泛，它包含了指令集的设计、组织、硬件与软件的边界问题等等，同时涉及了应用程序、技术、并行性、编程语言、接口、编译、操作系统等很多方面。作为各项技术发展的中心，体系结构一直在不断地朝前发展。 纵观计算机体系结构一路发展的历史，从60年代中期以前，最早的体系结构发展的早期时代，计算机系统的硬件发展很快，通用硬件已经很普遍，但是软件的发展却很滞后，刚刚起步，还没有通用软件的概念。从60年代中期到70年代中期，体系结构有了很大进步。多道程序、多用户系统引入了人机交互的新概念，开创了计算机应用的新境界，使硬件和软件的配合上了一个新的层次，但是此时的软件由于个体化特性很难维护，出现了“软件危机”。从20世纪70年代中期开始，分布式系统开始出现并流行，极大地增加了系统的复杂性，出现了微处理器并获得了广泛应用。如今计算机的体系结构发展已经进入了第四代，硬件和软件得到了极大的综合利用，迅速地从集中的主机环境转变成分布的客户机／服务器(或浏览器／服务器)环境，新的技术不断涌现出来。尽管如此，计算机在总体上、功能上需要解决的问题仍然存在。随着RISC技术、Cache等创新技术的发展，不仅仅在专业领域，越来越多的PC机也在向此靠拢。在每一次进步与创新的同时使组件的成本降到最低成为最需要考虑的问题。 此次会议上发表的几篇论文，分别从以下几个方面对计算机体系结构的发展与改进进行了探究。 一、新一代服务器的发展 在《Understanding and Designing New Server Architectures for Emerging Warehouse-Computing Environments》一文中，提出了一个改善服务器性能的方案。这篇论文旨在试图理解和为新兴的“仓库计算”环境设计下一代服务器。文中有两个主要的 本章主要介绍了如下一些基本概念： ?数据结构：数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。 ?数据：数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。 ?结点：结点也叫数据元素，它是组成数据的基本单位。 ?逻辑结构：结点和结点之间的逻辑关系称为数据的逻辑结构。 ?存储结构：数据在计算机中的存储表示称为数据的存储结构。 ?数据处理：数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。 ?数据类型：数据类型是指程序设计语言中各变量可取的数据种类。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。 本章主要介绍了如下一些基本概念： 线性表：一个线性表是n≥0个数据元素a0，a1，a2，…，an-1的有限序列。 线性表的顺序存储结构：在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。 线性表的链式存储结构：线性表的链式存储结构就是用一组任意的存储单元——结点（可以是不连续的）存储线性表的数据元素。表中每一个数据元素，都由存放数据元素值的数据域和存放直接前驱或直接后继结点的地址（指针）的指针域组成。 循环链表：循环链表(Circular Linked List)是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，从表中任一结点出发都可找到表中其他的结 循环链表：循环链表(Circular Linked List)是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，从表中任一结点出发都可找到表中其他的结点。 双向链表：双向链表中，在每一个结点除了数据域外，还包含两个指针域，一个指针（next）指向该结点的后继结点，另一个指针（prior）指向它的前驱结点。 除上述基本概念以外，学生还应该了解：线性表的基本操作（初始化、插入、删除、存取、复制、合并）、顺序存储结构的表示、线性表的链式存储结构的表示、一元多项式Pn(x)，掌握顺序存储结构（初始化、插入操作、删除操作）、单链表（单链表的初始化、单链表的插入、单链表的删除）。 本章主要介绍了如下一些基本概念： 栈：是一种只允许在一端进行插入和删除的线性表，它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底(bottom)。栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出栈。因此，栈也被称为“后进先出”的线性表。 栈的顺序存储结构：利用一组地址连续的存储单元依次存放自栈底到栈顶的各个数据元素，称为栈的顺序存储结构。 双向栈：使两个栈共享一维数组stack[MAXNUM]，利用栈的“栈底位置不变，栈顶位置动态变化”的特性，将两个栈底分别设为-1和MAXNUM，而它们的栈顶都往中间方向延伸的栈称为双向栈。 工厂组织框架图及岗位职责说明 1 目的 为了质量管理体系的有效运行，规定组织内部各职能部门和各级人员的岗位质量职责和适任条件，以便于对人力资源的管理、信息的交流、加强沟通、增进理解、协调行动。 2 适用范围 适用于公司内对质量管理体系的管理层、各职能部门和各级有关人员的岗位质量职责、权限的规定，以及各岗位的适任条件。 3职责 总经理： 1. 贯彻执行国家有关法律、法规和有关质量方面的方针政策； 2. 主持制订公司质量方针和质量目标，对质量承诺并确保实施； 3. 坚持满足顾客要求的重要观念，建立质量管理体系； 4. 任命企业相关负责人，确定各级机构和人员并明确规定各级职责、权限和相互关系，确保组织内的沟通有效性； 5. 负责定期组织管理评审、确保质量管理体系持续的适宜、充分和有效； 6. 审批重大质量政策及质量改进决策； 7. 授权质管部质量管理人员独立行使对产品质量进行监视、测量和报告的职能和权限。 业务副总 一、管理工作 1、负责制订年度、月度营销目标计划； 2、负责跟进目标计划的实施； 3、负责营销实绩的管理，并督导所属文员进行统计、归类并存档； 4、负责监督所属部门对于营销目标的执行情况，并制订月度营销实绩报告； 二、市场信息管理 1、负责市场调查及预测工作的实施，制订应对准备策略； 2、负责做好交易往来客户名簿的登记管理制度，并指导实施； 3、负责做好竞争对手调查名簿的登记管理制度，并指导实施； 4、负责依据市场状况和公司发展宗旨，对本行业市场信息及营销进行整合； 三、绩效管理 1、根据营销目标计划，制订月度考核计划，并配合行政部进行考核的实施； 2、负责制订本部门的岗位责任制，辅助提升全体营销人员的业务素质水平； 第3章计算机网络体系结构 ?本章内容 ?计算机的网络体系结构 ?网络参考模型 ?五层网络参考模型 3.1 计算机网络体系结构 ?发展历程 ?分层原理 ?基本概念 发展历程 ?网络体系结构提出的背景——计算机网络的复杂性、异质性 ?不同的通信介质——有线、无线等 ?不同种类的设备——主机、路由器、交换机、复用设备等 ?不同的操作系统——UNIX、Windows等 ?不同的软/硬件、接口和通信约定（协议） ?不同的应用环境——固定、移动等… ?不同种类业务——分时、交互、实时等 ?宝贵的投资和积累——有形、无形等 ?用户业务的延续性——不允许出现大的跌宕起伏 ?程序设计 ?把一个大的程序分解为若干个层次的小模块来实现，如操作系统。 ?邮政系统 ?邮递员、邮政分局、邮政总局、邮政运输 ?银行系统 ?物流系统 ?…… 2. 分层原理 ?计算机网络中也采用了分层方法。——把复杂的问题划分为若干个较小的、单一的局部问题，在不同层上予以解决。 ?网络的层次结构方法要解决的问题： ?网络应该具有哪些层次？每一层的功能是什么？（分层与功能） ?各层之间的关系是怎样的？它们如何进行交互？（服务与接口） ?通信双方的数据传输要遵循哪些规则？（协议） ?计算机网络中，层、协议和层间接口的集合被称为计算机网络体系结构。 ?换句话说：体系结构包括三个内容：分层结构与每层的功能、服务与层间接口、协议。 ?最早的网络体系结构源于IBM 的SNA ?其他的网络体系结构还有DEC的DNA等 ?由国际化标准组织ISO 制定的网络体系结构国际标准是OSI/RM ?实际中应用最广泛的是TCP/IP体系结构 ?事实上的（de facto）标准 层次结构方法的优点 ?独立性强——耦合程度低 ?上层只需了解下层通过层间接口提供什么服务——黑箱方法。 ?适应性强 ?只要服务和接口不变，每层的实现方法可任意改变。 ?易于实现和维护 ?把复杂的系统分解成若干个涉及范围小、功能简单的子单元： ?使系统的结构清晰，实现、调试和维护变得简单和容易。 ?使设计人员能专心设计和开发所关心的功能模块。 3. 基本概念 ?实体：任何可以发送或接收信息的硬件/软件进程。 ?协议：通信双方在通信中必须遵守的规则。 ?对等层：两个不同系统的同级层次。 ?对等实体：分别位于不同系统对等层中的两个实体 ?接口：相邻两层之间交互的界面，定义相邻两层之间的操作及下层对上层的服务。?服务：某一层及其以下各层的一种能力，通过接口提供给其相邻上层。 网络分层体系结构 通信协议 ?人际交流的协议: ?人类之间 ?“我有一个问题。” ?“现在几点了?” ?…说明发送的消息 ?… 说明接收到某消息后所应采取的行动 ?… 说明动作的次序 通信协议的三要素 ?语义 ?对协议中各协议元素的含义的解释，例如： ?在HDLC协议中，标志Flag(7EH)表示报文的开始和结束 ?在BSC协议中，SOH(01H)表示报文的开始，STX(02H)表示报文正文的开始， ETX(03H)表示报文正文的结束 ?语法数据结构和软件工程简介
第一章 计算机网络体系结构
山东建筑大学数据结构设计介绍
数据结构中栈的介绍
计算机体系结构知识点
计算机网络系统组成
数据结构栈的定义及基本操作介绍
数据结构创始人介绍
第一部分计算机系统组成及说明
数据结构课程教学设计(家族关系查询系统)
车间定岗定编组织结构图(doc 42页)
《计算机系统结构》课程教学大纲
数据结构百度百科
数据结构-图习题介绍
生产部职能与组织结构
计算机体系结构综述
数据结构中的名词解释
(完整版)工厂组织架构图及岗位职责说明
第3章 计算机网络体系结构
相关主题
文本预览