扬州大学试题纸( 2010 －2011 学年第一学期)物理学院微电0901、0902；电科0901、0902班(年)级课程计算机软件技术基础( A )卷题目一二三四五六七八总分得分部分答案我自己做的，仅供参考！一、单项选择题(每题2分共20分)1. 下面程序段的时间复杂度是( B )。

void func( int n) {int i=1, k=100;while (i<n){k++; i+=2;}}A．O(1) B．O(n) C．O(n2) D．O(log2n)解析：对于循环部分，设其时间复杂度为T(n），则有1+2*T(n)<n,即T(n)<（n-1）/2，故选B。

2. 若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是( C )。

A．i>0 B．i≤n C．1≤i≤n D．1≤i≤n+1解析：见教材P9.3. 在循环双链表的p指结点之前插入s所指结点的操作是( D )。

A．p->prior=s; s->next=p; p->prior->next=s; s->prior=p->priorB．p->prior=s; p->prior->next=s; s->next=p; s->prior=p->priorC．s->next=p; s->prior=p->prior; p->prior->next=s; p->prior=sD．s->next=p; s->prior=p->prior; p->prior=s; p->prior->next=s解析：见教材P20.虽然不同，但是类型一样。

4. 一个栈的输入序列为1，2，3，4，5，则下列序列中不可能是栈的输出序列的是( B )。

A．2，3，4，1，5 B．5，4，1，3，2C．2，3，1，4，5 D．1，5，4，3，25. 设数组A[0…m-1]作为循环队列Q的存储空间，front为头指针，rear为队尾指针，则执行出队操作后其头指针front的值为( B )。

A．front = (front+1) %m B．front = (front+1)%(m-1)C．rear = (rear+1) %m D．rear = (rear+1)% (m-1)6. 利用3，6，8，12，5，7这六个值作为叶子结点的权，生成一棵赫夫曼树，该树的深度为( B)。

A．3 B．4 C．5 D．67.已知二叉树的先序序列为abdgcefh，中序序列为dgbaechf，则后序序列为( D )。

A．bdgcefha B．gdbecfha C．bdgaechf D．gdbehfca解析：如图：ab cd e fg h8. 若某图的邻接表中的边结点数目为奇数，则该图( C )。

A．一定有奇数个顶点B．一定有偶数个顶点C．一定是有向图D．可能是无向图9. 下面关于AOE网的叙述中，不正确的是( D )。

A．若所有关键活动都提前完成，则整个工程一定能够提前完成B．即使所有非关键活动都未按时完成，整个工程仍有可能按时完成C．任何一个关键活动的延期完成，都会导致整个工程的延期完成D. 任何一个关键活动的提前完成，都会导致整个工程的提前完成10. 对于顺序存储的有序表（5，12，20，26，37，42，46，50，64），若采用折半查找表中元素26，( B )次比较后查找成功。

A．2 B．3 C．4 D．5解析：第一次比较[(1+9）/2]=37,第二次比较[（1+4）/2]=12，第三次比较[（3+4）/2]=20，第四次比较[（4+4）/2]=26，查找成功，选C。

二、填空题(每空2分共20分)1. n个元素的线性表，采用顺序存储结构，插入一个元素要平均移动表中__n/2__个元素，删除一个元素最坏情况下要移动___n-1__个元素。

2. 两个串相等的充分必要条件是：______________________。

3. 线索二叉树的左线索指向其____________，右线索指向其_____________。

4. 设一棵完全二叉树有500个结点，则共有____250__个叶子结点，有__249__个度为2的结点。

5.有n个顶点的强连通图最多有_____n(n-1)/2______条边，最少有___n-1_____条边。

6. 在含有n个结点和e条边的无向图的邻接矩阵中，零元素的个数为____n2-2e_____。

三、简答题（每题10分共50分）1.试找出分别满足下面条件的所有二叉树：a).先序序列和中序序列相同；b).中序序列和后序序列相同；c).先序序列和后序序列相同。

解：a）、先序遍历是“根左右”、中序遍历是“左根右”，要“根左右”和“左根右”结果相同，只有去掉“左”从而都是“根右”才行。

故满足条件的有三种情况：空二叉树，只有根的二叉树和只有右子树的二叉树。

b）、中序遍历是“左根右”、后序遍历是“左右根”，要“左根右”和“左右根”结果相同，只有去掉“右”从而都是“左根”才行。

故满足条件的有三种情况：空二叉树，只有根的二叉树和只有左子树的二叉树。

c）、先序遍历是“根左右”、后序遍历是“左右根”，要“根左右”和“左右根”结果相同，且不能去掉“根”，因为二叉树只要有结点，就不可能没有根。

故满足条件的只有两种情况：空二叉树和只有根的二叉树。

2. 对于如下图所示的图，用普里姆算法从顶点1开始求最小生成树，请写出其按次序产生的边；用克鲁斯卡尔算法产生的边次序。

(注：边用(i, j)的形式表示。

)解：（1）应用Prim算法构造最小生成树的过程:（2）用克鲁斯卡尔算法产生的边次序：3.假设二叉树采用顺序存储结构，如图所示1）画出二叉树表示；2）写出先序遍历、中序遍历和后序遍历的结果；3）写出结点C的双亲结点及其左右孩子结点；4）画出此二叉树还原成森林的图。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20E AF D H C JG I B解：1）2）先序遍历序列：eadcbjfghi中序遍历序列：abcdjefhgi后序遍历序列：bcjdahigfe3）c的双亲结点为d，左孩子为b，没有右孩子。

4）4. 假设用于通信的电文由9种不同的符号来组成，这些符号在电文中出现的概率为8，21，24，6，18，23，41，56，13。

（1）试为这9符号设计相应的赫夫曼编码，在构造Huffman 树的过程中保持左子树根结点权值小于右子树根结点的权值；（2）求出该Huffman 树的带权路径长度(WPL)。

解：（1）如图所示：（2）带权路径长度WPL=（6+8）*5+（13+18+21)*4+(23+24)*3+(41+56)*2=613.5.对如图所示的AOE 网求出： 1）各活动的最早开始时间与最迟开始时间。

2）所有的关键路径。

3）该工程完成的最短时间是多少。

4）可通过提高哪些活动的速度来加快工程的进度。

解：表一表二事件 V1 V2 V3 V4 V5 V6 V7 V8 V9 最早开始时间 0 6 4 5 7 7 16 14 18 最迟开始时间66 8710161418活动 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 最早开始时间 0 0 0 6 4 5 7 7 7 16 14 最迟开始时间 0 2 3 6 6 8 7 7 10 16 14 时间余量23233V 1V 2V 3V 4V 5V 6V 7V 8V 9a 2=4a 4=1a 3=5a 1=6a 6=2a 11=4a 10=2a 9=4a 8=7a 5=1a 7=9210 122 8847 41 56 6623 24 39 27 13 21 14 18 6 8 0 0 0 0 0 0 00 1 1 1 1 1 1 1 1（1）各活动的最早开始时间与最迟开始时间如表二。

（2）由表一和表二可知，关键路径有两条：V1，V2，V5，V7，V9和V1，V2，V5，V8，V9.（3）由表一可知该工程完成的最短时间是18天。

（4）由表二可知通过提高活动a1，a4的速度来加快工程的进度。

四、程序填空题（每空2分共10分）利用栈结构后进先出的特性，实现十进数N和八进制数之间的转换。

#include<stdio.h>#include<stdlib.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct{int *base;int *top;int stacksize;}SqStack;void InitStack(SqStack &S){S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));if(!S.base) printf("ERROR!");S.top=S.base;S.stacksize=STACK_INIT_SIZE;}void Push(SqStack &S, int e){if(S.top-S.base>=S.stacksize){S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));if(!S.base) printf("ERROR!");S.top=S.base+S.stacksize;S.stacksize+= STACKINCREMENT;}*S.top++ = e;}void Pop(SqStack &S, int &e){if(S.top==S.base) printf ("ERROR!"); e=* --S.top;}void main( ){int N,e;SqStack S;InitStack(S);scanf("%d",&N );while(N){Push(S,N%8);N=N/8;}while(S.base!=S.top){Pop(S,e);printf("%d",e);}}。