扬州大学试题纸 - 图文

扬州大学试题纸

( 2010 － 2011 学年第 一 学期)

物理学院微电0901、0902；电科0901、0902 班(年)级 课程 计算机软件技术基础 ( A )卷

题目 得分

一 二 三 四 五 六 七 八 总分 部分答案我自己做的，仅供参考！

一、单项选择题 (每题2分共20分)

1. 下面程序段的时间复杂度是( B )。

void func( intn) { inti=1, k=100; while (i

解析：对于循环部分，设其时间复杂度为T(n），则有1+2*T(n)

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->prior B．p->prior=s; p->prior->next=s; s->next=p; s->prior=p->prior C．s->next=p; s->prior=p->prior; p->prior->next=s; p->prior=s

D．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，2 C．2，3，1，4，5 D．1，5，4，3，2

5. 设数组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．6

7.已知二叉树的先序序列为abdgcefh，中序序列为dgbaechf，则后序序列为( D )。

A．bdgcefha B．gdbecfha C．bdgaechf D．gdbehfca 解析：如图：a b c d e f g h

8. 若某图的邻接表中的边结点数目为奇数，则该图( 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条边的无向图的邻接矩阵中，零元素的个数为____n-2e_____。

2

三、简答题（每题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 20 E A F 解：1）

2）先序遍历序列：eadcbjfghi 中序遍历序列：abcdjefhgi

4）

后序遍历序列：bcjdahigfe

3）c的双亲结点为d，左孩子为b，没有右孩子。

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

（1）试为这9符号设计相应的赫夫曼编码，在构造Huffman树的过程中保持左子树根结点权值小于右子树根结点的权值；

（2）求出该Huffman树的带权路径长度(WPL)。 解：（1）如图所示： 210 1 0 122 88 1 0 1 0

41 56 47 66 1 0 1 0 39 27 24 23

0 1 0 1

21 13 18 14

0 1

6 8

（2）带权路径长度WPL=（6+8）*5+（13+18+21)*4+(23+24)*3+(41+56)*2=613.

a=19Va=265.对如图所示的AOE网求出： a1=V24a7=710aaVV58=7V91）各活动的最早开始时间与最迟开始时间。 12=4=12）所有的关键路径。

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

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

表一

事件 最早开始时间 最迟开始时间 V1 0 0 V2 6 6 V3 4 6 表二

活动 最早开始时间 最迟开始时间 时间余量 a1 0 0 0 a2 0 2 2 a3 0 3 3 a4 6 6 0 a5 4 6 2 a6 5 8 3 a7 7 7 0 a8 7 7 0 a9 7 10 3 a10 16 16 0 a11 14 14 0 V4 5 8 V3V4a5V8a11=4a6=2a9=45a3=V6V5 7 7 V6 7 10 V7 16 16 V8 14 14 V9 18 18

本文来源：https://www.bwwdw.com/article/21hd.html