数据结构期末考试试卷

A 程序 B 问题求解步骤的描述 C 要满足五个基本特性 D A 和 C.

5、在一棵二叉树的前序周游、后序周游、中序周游所产生的序列中，所有叶结点的先后顺序( )

A 都不相同 B 完全相同 C 前序和对称序相同 D 后序与对称序相同

6、在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。

A O(n) B O(n+e) C O(n2) D O(n3)

7、某内排序方法的稳定性是指( )。

A．该排序算法不允许有相同的关键字 B．该排序算法允许有相同的关键字

C．平均时间为0（n log n）的排序方法 D．以上都不对

8、n个顶点的强连通图中至少含有( )。

A n—l条有向边 B n条有向边

C n(n—1)／2条有向边 D n(n一1)条有向边

9、权值为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。

A 24 B 48 C 72 D 53

10、下面关于哈希(Hash，杂凑)查找的说法正确的是( )

A 哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B 除留余数法是所有哈希函数中最好的

C 不存在特别好与坏的哈希函数，要视情况而定

D 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可

1、算法的5个特性分为 （1） 、 （2） -、 （3） 、 （4） 、一个或多个输入。

2、下面程序段的时间复杂度为__（5）___。(n>1)

sum=1； for (i=0;sum3、假定一棵二叉树的结点数为n，则它的最小深度为 (6) ，最大深度为 (7) 。

4、先根次序周游树林正好等同于按_(8)__周游对应的二叉树，后根次序周游树林正好等同于按__(9)_周游对应的二叉树

5、Prim（普里姆）算法适用于求_（10）__的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求___（11）___的网的最小生成树。

6、对不使用分离链接法的散列表，其装填因子应该低于 (12),称这样的表为_(13)_

7、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1 则排序需___（14）____趟，写出第一趟结束后，数组中数据的排列次序___（15）____。

已知一个带权图的顶点集V和边集G分别为：

V＝{0，1，2，3，4，5,6}；

E={(0，1)8，(0，2)7，(0，3)5，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(4，5)10,(5,6)3}，

则求出该图的最小生成树及最小生成树的权。

3、已知一个后缀算术表达式为

14　3　-3/　6　19　7+* /

（1）请写出对应的中缀算术表达式。

（2）画出在进行后缀表达式求值过程中数值栈的变化。

4 、请回答下列关于图(Graph)的一些问题：

（1） 有 n 个顶点的有向强连通图最多有多少条边?最少有多少条边?

（2） 表示有200 个顶点、200 条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？

（3） ．对于一个有向图，不用拓扑排序，如何判断图中是否存在环？

使用深度优先遍历，按退出dfs过程的先后顺序记录下的顶点是逆向拓扑有序序列。若在执行dfs(v)未退出前，出现顶点u到v的回边，则说明存在包含顶点v和顶点u的环。

1、设记录R[i]的关键字为R[i].KEY（1<=i<=k），树结点T[i]（1<=i<=K-1）指向败者记录，T[0]为全胜记录下标。写一算法产生对应上述R[i]（1<=i<= k）的败者树，要求除R[1..k]和T[0..k-1]以外，只用O(1)辅助空间。 void Adjust(int T[],int s){ //选得最小关键字记录后，从叶到根调整败者树，选下一个最小关键字

//沿从叶子结点R[s]到根结点T[0]的路径调整败者树

t=(s+k)/2; //T[t]是R[s]的双亲结点

while(t>0)

{ if(R[s].key>R[T[t]].key) s<-->T[t]; //s指示新的胜者

t=t/2;

}//while

T[0]=s;

}//Adjust

void CreateLoserTree(int T[])

{ //建立败者树，已知R[0]到R[k-1]为完全二叉树T的叶子结点，存有k个关键字，沿

//从叶子到根的k条路径将T调整为败者树

R[k].key=MINKEY; //MINKEY是最小关键字

for(i=0;i设置T中“败者”的初值

//依次从R[k-1],R[k-2],…,R[0]出发调整败者

for(i=k-1;k>=0;i--) Adjust(T,i);

}//CreateLoserTree

下面关于算法说法错误的是（ ）

A．算法最终必须由计算机程序实现

B.为解决某问题的算法同为该问题编写的程序含义是相同的

C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的

2、程序段(伪代码)

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]对换；

其中 n 为正整数，则最后一行的语句频度在最坏情况下是（ ）

A O（n） B O(nlogn) C O(n3) D O(n2)

3、栈底至栈顶依次存放元素a、b、c。在第四个元素d入栈前，栈中元素可以出栈，则出栈序列可能是（ ）

A abcd B dabc C cbda D cdab

4、在一个单链表中HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行　　　　。

A p.link=q.link;q.link=p; B q.link=p.link;p.link=q;

C p.link=q.link;q=p; D q.link=p.link;p.link=q;

5、二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是（）

A E B F C G D H

、就平均性能而言，目前最好的内排序方法是( )排序法。

A 冒泡 B 希尔插入 C 交换 D 快速

9、若一棵二叉树具有10个度为2 的结点，5个度为1的结点，则度为0的结点个数是（ ）。

A 9 B 11 C 15 D 不确定

一、填空题(每空2分，共30分)

1、数据结构是研讨数据的 ，以及它们之间的相互关系，并对与这种结构定义相应的 ，设计出相应的 。

2、 是限定仅在表尾进行插入或删除操作的线性表。

3、深度为k 的完全二叉树至少有___ ____个结点，至多有___ ____个结点。

5、克鲁斯卡尔算法的时间复杂度为 ,它对 图较为适合

6、Dijkstra 最短路径算法从源点到其余各顶点的最短路径的路径长度按 次序依次产生，该算法弧上的权出现 情况时，不能正确产生最短路径

7、快速排序在平均情况下的时间复杂度为 ，最坏情况下的时间复杂度为 。

三、运算题(每小题6分，共30分)

2、已知一个带权图的顶点集V和边集G分别为：

V＝{0，1，2，3，4，5}；

E={(0，1)2，(0，2)5，(0，3)12，(1，5)6，(2，3) 5，(2，4)13，(3，5)9，

(4，5)10}，

则求出该图的最小生成树及最小生成树的权。

4、已知图的邻接矩阵为：

V1 V2 V3 V4 V5 V6 V7 V8 V9 V10

V1 0 1 1 1 0 0 0 0 0 0

V2 0 0 0 1 1 0 0 0 0 0

V3 0 0 0 1 0 1 0 0 0 0

V4 0 0 0 0 0 1 1 0 1 0

V5 0 1 0 0 0 0 1 0 0 0

V6 0 0 1 0 0 0 0 1 1 0

V7 0 0 0 0 1 0 0 0 1 0

V8 0 0 0 0 0 0 0 0 0 1

V9 0 0 0 0 1 0 0 0 0 1

V10 0 0 1 0 0 0 0 0 0 0

当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出：

（1）以顶点V1 为出发点的唯一的深度优先遍历；

（2）以顶点V1 为出发点的唯一的广度优先遍历；

5、求出下图G=（E，V）中v0到其它顶点的最短路径。

E={v0、v1、v2、v3、v4、v5、v6}

V={、v2>、、v3>、、v0>、、v1>、、v3>、、v4>、

、v4>、、v5>、、v3>}

借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于 key 的记录。设此组记录存放于数组 r[l..h]中。若查找成功，则输出该记录在 r 数组中的位置及其值，否则显示“not find”信息。请编写出算法并简要说明算法思想。