操作系统： 考虑如下的页访问序列（序列中每一个元素都是页号）： 12345213323454511325

操作系统： 考虑如下的页访问序列（序列中每一个元素都是页号）： 12345213323454511325

《数据结构》试题

一、选择题（每小题2分，共30分）

1． 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。

A、单链表 B、双链表 C、单向循环 D、顺序表

2． 串是任意有限个（ ）

A、符号构成的序列 B、符号构成的集合

C、字符构成的序列 D、字符构成的集合

3． 设矩阵A（aij ，l≤i,j≤ 10）的元素满足：

aij≠0(i≥j, l≤i, j≤ 10)

aij=0 (i
现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9][5]的首址为

A、2340 B、2336 C、2164 D、2160

4． 如果以链表作为栈的存储结构，则退栈操作时（ ）

A、 必须判别栈是否满

B、 对栈不作任何判别

C、 必须判别栈是否空

D、 判别栈元素的类型

5． 设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（ ）

A、front=front+1 B、front=(front+1)% m

C、rear=(rear+1)%m D、front=(front+1)%(m+1)

6． 深度为6（根的层次为1）的二叉树至多有（ ）结点。

A、 64 B、32 C、31 D、63

7． 将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为（ ）

A、24 B、25 C、23 D、无法确定

8． 设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（ ）

A、G’为G 的子图 B、G’为G 的边通分量

C、G’为G的极小连通子图且V’=V D、G’为G的一个无环子图

9． 用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（ ）

A、 一定都是同义词 B、一定都不是同义词

C、都相同 D、不一定都是同义词

10． 二分查找要求被查找的表是（ ）

A、 键值有序的链接表 B、链接表但键值不一定有序

C、 键值有序的顺序表 D、顺序表但键值不一定有序

11． 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（ ）

A、n2 B、nlog2n C、log2n D、n-1

12． 堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|_n/2_|,满足( )

A、ki≤k2i≤k2i+1 B、ki
C、ki≤k2i且ki≤k2i+1(2i+1≤n) D、ki≤k2i 或ki≤k2i+1(2i+1≤n)

13．一个具有n个顶点的无向完全图的边数为（　 ）

A、n(n+1)/2 B、n(n-1)/2 C、n(n-1) D、n(n+1)

14．在索引顺序表中查找一个元素，可用的且最快的方法是（　 ）

A、用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找

B、用顺序查找法确定元素所在块，再用二分查找法在相应块中查找

C、用二分查找法确定元素所在块，再用顺序查找法在相应块中查找

D、用二分查找法确定元素所在块，再用二分查找法在相应块中查找

15．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ 　）存储方式最节省运算时间。

A、 单链表　 B、双链表　

C、带头结点的双循环链表　D、容量足够大的顺序表

二、判断题（每小题1分，共10分）

1．双链表中至多只有一个结点的后继指针为空。（ ）

2．在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（ ）

3．对链表进行插入和删除操作时，不必移动结点。（ ）

4．栈可以作为实现程序设计语言过程调用时的一种数据结构。（ ）

5．在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧。( )i

6．对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。( )

7．“顺序查找法”是指在顺序表上进行查找的方法。（ ）

8．向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（）

9．键值序列{A，C，D，E，F，E，F}是一个堆。

10．二路归并时，被归并的两个子序列中的关键字个数一定要相等。（）

三、填空题（每小题2分，共20分）

1．在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：＿＿＿＿＿＿＿＿；L->next=U->next；free(U)；

2．有一个长度为20的有序表采用二分查找方法进行查找，共有＿＿＿＿＿＿个元素的查找长度为3。

3．采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为＿＿＿＿＿。若A的初始状态为递减排列，则记录的交换次数为＿＿＿＿＿＿＿。

4．在无头结点的双链表中，指针P所指结点是第一个结点的条件是＿＿＿＿＿＿。

5．G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是＿＿＿＿＿图。

6．如果一个有向图中没有＿＿＿＿＿＿，则该图的全部顶点可能排成一个拓扑序列。

7．深度为8（根的层次号为1）的满二叉树有＿＿＿＿＿＿个叶子结点。

8．将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为＿＿＿＿＿＿＿。

9．设某闭散列表HT未满，散列函数H（KEY）为键值第一字母在字母表中的序号，处理冲突方法为线性探测法，请在下列算法划线处填上适当内容，以实现按键值第一字母的顺序输出闭散列表中所有键值的算法。

void printword(keytype HT[m])

{ for(i=1;i<=26;i++)

{ j=i;

while(____________________)

{ if (____________________) printf(“datatype”,HT[j]);

j=(j+1)% m;

}

}

}

10．设有一个链队，结点结构为data|next，front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：

malloc(p)；p->data=x; p->next=NULL；

＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；

＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；

四、简答题：（每小题4分，共20分）

1. 对于一个有10000个结点的二叉树，树叶最多有多少个？最少有多少个？

2. 已知一棵二叉树的中序序列和后序序列分别为： DBGEACHF和DGEBHFCA，则该二叉树的前序序列是什么？

3. 设有1000个无序的元素，需排出前10个最大（小）的元素，你认为采用哪种排序方法最快？为什么？

4. 在KMP算法中，已知模式串为ADABCADADA ，请写出模式串的next[j]函数值。

5. 中序遍历的递归算法平均空间复杂度为多少？

五、 算法设计题（每小题10分，共20分）

1. 试编写一个算法，判断一给定的整型数组a[n]是不是一个堆。

2. 一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一高效算法，求二叉树的繁茂度。

参考答案

一、选择题

1、D 2、C 3、D 4、C 5、D 6、D 7、A 8、B 9、D 10、C 11、D 12、C

13、B　　14、C　　15、D　　

二、判断题

1. √ 2. × 3. √ 4. √ 5. × 6. × 7. × 8. √ 9. √ 10. ×

三、填空题

1．U=L - > next

2．4。　

3．n-1、n(n-1)/2。

4．p - > prior = NULL。

5．连通

6．回路或环

7．28-1 = 27 = 128

8．24

9．HT[j]!=NULL或HT[j]不为空、H(HT[j])=I

10．rear - > next = p、rear = p

四、简答题：

1. 答： 最多是完全二叉树的形态，即5000个叶子；最少是单支树的形态，即1个叶子。

2.答：是：ABDEGCFH

3. 答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，

时间效率为O(nlog2n)； 即O（1000log21000）=O(10000)

锦标赛排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089

堆排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089

若用冒泡排序也较快，最多耗费比较次数为（n-1+n-2+……＋n-10）=10n-55=10000-55=9945（次）

4. 答： 0112112343

5. 答： 要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空间复杂度为O(log2n)

五、 算法设计题

1.解：提示：堆的定义是：ki
void SortA(sqlist &A, int n)

{ if(n==0) return(0); //空表

if (a[1]
{ for( i=1; i2; i++) if (a[i]>a[2*i]|| a[i]>a[2*i+1])return(-1);

return(minleap)

};

else

{ for( i=1; i<=n/2; i++) if (a[i]
return(“maxleap”)

};

}

2. 要用层次遍历以及队列来处理，可以增设一个宽度计数器，在统计完每一层的结点个数之后,再从计数器中挑出最大值。

typedef struct {

BTNode node; int layer;

//layer是结点所在层数

} BTNRecord, r ;

int Width(Bitree T ){ //求树宽

int count[ ]; //增开count向量，存放各层对应的结点数

InitQueue(Q); //队列初始化，Q的元素为BTNRecord类型

EnQueue(Q,{T, 0}); //根结点入队, 0 表示count[0]，下标值

while(!QueueEmpty(Q))

{ DeQueue(Q, r); //结点出队

count[r.layer]++; //出队时再把结点对应层的计数器加

if(r.node->lchild) EnQueue(Q,{r.node->lchild, r.layer+1});

if(r.node->rchild) EnQueue(Q,{r.node->rchild, r.layer+1});

} //按层序入队时要随时标注结点所在层号

h=r.layer; //最后一个队列元素所在层就是树的高度

for(maxn=count[0], i=1; h; i++)

if(count[i]>maxn) maxn=count[i]; //求出哪一层结点数最多

return (h*

maxn)} // Width