第3部分 模拟试题及参考答案

第3部分 模拟试题及参考答案

模拟试题1

一、选择题(20分)

1．双向链表中有两个指针域，llink和rlink分别指向前趋和后继，设p指向链表中的一个结点(链表结点数大于2，p不是第一个结点)，现在要求删去p所指结点，则正确的删除是( )。

A) p->rlink->llink=p->llink;p->llink->rlink=p->rlink;free(p); B) free(p);p->rlink->llink=p->llink;p->llink->rlink=p->rlink; C) p->rlink->llink=p->llink;free(p);p->llink->rlink=p->rlink; D) 以上A，B，C都不对。

2．对一组数据(84,47,25,15,21)排序，数据的排列次序在排序过程中的变化为：

1) 84, 47,25,15,21 2) 15, 47,25,84,21 3) 15, 21,25,84,47 4) 15, 21,25,47,84 则采用的排序是( )。 A) 冒泡 B) 选择 C) 快速 D) 插入 3．栈和队列都是( )。 A) 顺序存储的线性结构 B) 链式存储的非线性结构 C) 限制存取点的线性结构 D) 限制存取点的非线性结构

4．设有数组A[i, j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为( )。

A) BA+141 B) BA+180 C) BA+222 D) BA+225

5．设元素X，Y，Z顺序进栈(进栈的过程中允许出栈)，得不到的出栈序列是( )。 A) XYZ B) YZX C) ZXY D)ZYX 6．适用于折半查找的表的存储方式及元素排列要求为( )。 A) 链式方式存储，元素无序 B) 链式方式存储，元素有序 C) 顺序方式存储，元素无序 D) 顺序方式存储，元素有序

7．在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的( )倍。 A) 1/2 B) 2 C) 4 8．归并排序的时间复杂度是( )。

D) 1

A) O(n2) B) O(n) C) O(nlog2n) D) O(log2n) 9．( )遍历一棵二叉排序树所得的结点访问序列是按结点值的递增序列。 A) 先序 B) 中序 C) 后序 D) 以上均不是 10．链表不具有的特点是( )。 A) 插入删除不需要移动元素 B) 可随机访问任意元素 C) 不必要先估计存储空间 D) 所需空间与线性长度成正比

·2· 数据结构简明教程（C语言描述）

二、填空题(20分)

l．计算机执行下面的循环语句时，语句“k++;”的执行次数为___________。

for(i=l;i

for(j=n;j>=i;j--)k++;

2．对任意二叉树T，叶子数为n0，度为2的结点的个数是n2，则n0与n2的关系是 ___________。

3．已知有序表为(12,18,24,35,47,50,62,83,90,134)当用二分法查找90时，需___________次比较成功，查找47时需___________次比较成功，查找100时需___________次才能确定不成功。

4．设F是由T1，T2，T3三棵树组成的森林，与F对应的二叉树为B，已知T1，T2，T3的结点数分别为n1，n2和n3，则二叉树B的左子树中有___________个结点，右子树中有___________个结点。

5．有向图G=(V,E)，其中 V(G)={0,1,2,3,4,5}，用三元组表示弧及弧上的权d。E(G)为{<0,5,100>,<0,2,10>,<1,2,5>,<0,4,30>,<4,5,60>,<3,5,10>,<2,3,50>,<4,3,20>}，则从源点0到顶点3的最短路径长度是_____________，经过的中间顶点是_____________。

6．在直接插入排序、冒泡排序、简单选择排序中，稳定的排序方法为___________。

三、判断题(10分)

1．在某工程的AOE网中，加速其关键路径上的关键活动均可缩短整个工程的完成时间。( ) 2．Hash表的平均查找长度与处理冲突的方法无关。( )

3．完全二叉树中，若一个结点没有左子女，则必是树叶。( )

4．带头结点的链队列执行出队操作不会改变头指针的值，但可能会改变尾指针的值。( ) 5．当待排序记录从小到大排序或者从大到小排序时，快速排序的执行时间最省。( ) 6．有e条边的无向图，其邻接表中有2e个表结点。( )

7．线性表采用链表存储时，结点的存储空间可以是不连续的。( ) 8．所谓取广义表的表尾就是返回广义表中最后一个元素。( ) 9．一棵树中的叶子数一定等于与其对应的二叉树的叶子数。( )

10．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。( )

四、应用题(20分)

1．设哈希函数H(key)=key，用链地址法处理冲突法，在地址空间为0～10的散列区间中，对关键字序列(22,41,53,46,30,13,01,67)构造一个哈希表。

2．已知长度为9的表(19,14,23,01,66,21,83,27,56)，画出以该序列进行堆排序时所建立的第一个小根堆。

3．已知二叉树的中序序列为DGBAECF，后序序列为GDBEFCA，试画出该二叉树的先序线索树。 4．以数据集{3,4,5,8,12,18,20,30}为叶结点，构造一棵哈夫曼树并求其带权路径长度。 5．写出下图所示有向图的所有拓扑排序序列。

B G C D G 6．给定下图，按普里姆算法，画出其最小生成树(从顶点V1开始)。

第3部分 模拟试题及参考答案 ·3·

五、算法设计题(30分)

1．设计一个算法，判别给定二叉树是否为二叉排序树(10分)。

2．设计一个算法，判断以邻接表方式存储的有向图中是否存在从顶点vi到顶点vj的简单路径(10分)。

3．已知一棵以线索链表为存储结构的中序线索二叉树T，设计一个算法，试在该二叉树上求任意结点x的中序后继(10分)。

模拟试题2

一、选择题(20分)

1．广义表L=(A,(B,C))，进行TAIL(L)操作后的结果为( )。

A) C B) B,C C) (B,C) D) ((B,C))

2．一棵3阶树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为( )个。

A) 4 B) 5 C) 6 D) 7

3．在一个图中，所有顶点的度数之和等于所有边数的( )倍 。

A) 1/2 B) 2 C) 1 D) 4

4．下列排序算法中，( )排序在某趟结束后不一定能选出一个元素放到其最终的位置上。 A) 选择 B) 冒泡 C) 归并 D) 堆 5．下列四棵二叉树中( )是一个堆。

6．递归函数调用时，处理参数及返回地址，要用一种称为( )的数据结构。 A) 队列 B) 多维数组 C) 栈 D) 线性表 7．在等概率情况下，顺序查找成功时的平均查找长度为( )。

A) n B) 2n C) n+1 D) (n+1)/2 8．下列排序算法中，其中( )是稳定的。 A) 堆排序，冒泡排序 B) 归并排序，冒泡排序 C) 直接选择排序，归并排序 D) 快速排序，堆排序

9．设输入序列为(A,B,C,D)，借助栈，规定A 最先输出，不可能的输出序列为( )。 A) A,B,D,C C) A,D,B,C

B) A,D,C,B D) A,C,D,B

·4· 数据结构简明教程（C语言描述）

10．设给定权值总数有n 个，其哈夫曼树的结点总数为( )。 A) 2n﹣1 B) 2n C) 2n+1 D) 不确定 二、填空题(20分)

1．数据元素在计算机中有两种基本的存储结构：_____________和_____________。

2．设G为具有n个顶点的无向图，则最多有_____________条边；若G为具有n个顶点的有向图，则最多有_____ …… 此处隐藏：4100字，全部文档内容请下载后查看。喜欢就下载吧 ……