[模拟]信息学模拟试卷[9套]

模拟试卷一

一、单项选择题

1．若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用___________存储方式最节省运算时间。

(1)单链表 (2)双链表

(3)单循环链表 (4)带头结点的双循环链表 2．设一个栈的输入序列为A，B，C．，D，则借助一个栈所得到的输出序列不可能是________ (1)A，B，C，D (2)D，C，B，A (3)A，C，D，B (4)D，A，B，C 3．串是____________。

(1)不少于一个字母的序列 (2)任意个字母的序列 (3)不少于一个字符的序列 (4)有限个字符的序列 4．链表不具有的特点是_______________。

(1)可随机访问任一元素 (2)插入删除不需要移动元素

(3)不必事先估计存储空间 (4)所需空间与线性表长度成正比 5．在有n个叶子结点的哈夫曼树中，其结点总数为______________。

(1)不确定 (2)2n (3)2n+1 (4)2n-1 6．任何一个无向连通图的最小生成树_____________

(1)只有一棵 (2)有一棵或多棵 (3)一定有多棵 (4)可能不存在

7．将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为_____________。

(1)98 (2)99 (3)50 (4)48

8.下列序列中，_____________是执行第一趟快速排序后得到的序列(排序的关键字类型是字符串)。 (1)[da，ax，eb，de，bb]ff[ha，gc] (2)[cd，eb，ax，da]ff[ha，gc，bb] (3)[gc，ax，eb，cd，bb]ff[da，ha] (4)[ax，bb，cd，da]ff[eb，gc，ha] 9．用n个键值构造一棵二叉排序树，最低高度为___________。

(1)n/2 (2)n (3)[log2n] (4)[log2n+1]

10．二分查找法要求查找表中各元素的键值必须是_______________排列。 (1)递增或递减 (2)递增 (3)递减 (4)无序 11.对于键值序列(12，13，11，18，60，15，7，18，25，100)，用筛选法建堆，必须从键值为__________的结点开始。

(1)100 (2)12 (3)60 (4)15 二、判断题

1．( )串长度是指串中不同字符的个数。

2. ( )数组可以看成是线性结构的一种推广，因此可以对它进行插入、删除等运算。 3．( )在顺序表中取出第i个元素所花费的时间与i成正比。 4．( )在栈满情况下不能作进栈运算，否则产生“上溢”。

5．( )二路归并排序的核心操作是将两个有序序列归并为一个有序序列。

6．( )对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。

7．( )一个有向图的邻接表和逆邻接表中的结点个数一定相等。

8．( )在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。

9.( )二叉排序树或者是一棵空树，或者是具有下列性质的二叉树；若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其右孩子的值。

1

10．( )在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。

三、填空题

1．在带有头结点的单链表L中，第一个元素结点的指针是___________。

2．在双循环链表中，在指针P所指结点前插入指针S所指的结点，需执行下列语句：

S↑.next：= P； S↑．prior：= P↑．prior； P↑．prior：= S； __________：= S；

3.[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是_________，栈为满的条件是______________。

4．具有100个结点的完全二叉树的深度为________________。 5．有向图G用邻接矩阵A[1．．n，1..n]存储，其第i行的所有元素之和等于顶点i的____________。 6．在顺序文件中，要存取第i个记录，必须先存取

A ___________________。

／＼ 7．对于下面的二叉树，按中序遍历所得到的结点序列为

B C

___________________。

／＼ ＼ 为递增序8．分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态

D E F

列的表按递增顺序排序，最省时间的是_____________算法，最费时间的是

／ _____________算法。

H

白处填上9.对下图所示的网，执行prim算法可得到最小生成树，试在下表的空

括当的内容，以说明该算法的执行过程。 1 3 4 U V 顶点

{1,3,4（U，V）（2,1）（2,3） （2,4） {2} ∞ 4 2 } 代价

（U，V）（2,3） 10. {2,4} {1,3} 4 代价 设散

（U，V）(3,1) 列函 {2,3,4} {1} 1 代价 数为

{2,3,4,（U，V）H（key），用拉链（链地址）法解决冲 1} 代价 突，H的值域为0，…，n-1，构造的散列表类型如下：

TYPE link = ↑node； Node = RECORD key：keytype；

next：link； …

END；

Openhash = array[0．．n-1] of link；

请在下列算法划线处填上适当内容，以完成在散列表HP中查找键值等于K的结点，若查找成功，返回该结点的指针，否则返回空指针。

Function research(K：keytype；HP：openhash)：link； BEGIN

I：= H(K)；SUC：= false； _______________________；

2

while(P<>NIL)and(not suc)do if P↑.key<>K

then_______________________ else suc：= true； return(P) END

四、应用题

1．已知二叉树的后序和中序序列如下，构造出该二叉树。

后序序列: ABCDEFG 中序序列：ACBGEDF

2．有一组关键码序列(38，19，65，13，97，49，41，95，1，73)，采用冒泡排序方法由小到大进行排序，请写出每趟的结果。

3．设图G=(V，E)，V={1，2，3，4，5，6}，E={<1，2>，<1，3>，<2，5>，<3，6>，<6，5>，<5，4>，<6，4>}。请写出图G中顶点的所有拓扑序列。

4．设散列函数为H(K)= K mod 7，闭散列表的地址空间为0，…，6，开始时散列表为空，用线性探测法解决冲突，请画出依次插入键值23，14，9，6，30，12，18后的散列表。 5．对下面两棵二叉树，分别画出它们的顺序存储结构。

A A ／＼ ／＼ B C B C ／＼ ／＼ ／＼ ＼ D E F G D E F ／＼ ／ ／＼ I J K I J

6．已知图G的邻接表如下，画出图G的所有连通分量。

五、算法设计题

1．设二叉排序树的根指针为t，每个结点的结构

Lchild Key Rchild 为：

试用类PASCAL语言写出算法以输出二叉排序树中最大的键值。

3

2．设一个环上有若干个整数，现采用单循环链表L存储该环，已知L的结点结构为；

Data next 试画出链表L的结构图，并编写算法判断环上任意两个相邻元素值之差的绝对值是否不超过2。

3．设一棵二叉树以二叉链表来存储，结点结构 设计算法以求此二叉树上度为1的结点个数。

Lchild Data Rchild 为：

4

模拟试卷二

一、选择题(每小题2分，共10分)

在下列备选答案中选出一个正确的，将其号码填在“___________________”上。

1．若线性表最常用的操作是存取第i个元素及其前趋的值，则采用_____________存储方式节省时间。

a．单链表 b．双链我 c．单循环链表 d．顺序表

2．对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_________________次序的遍历实现编号。 a．先序 b．中序 c．后序 d．从根开始的层次遍历

3.某二叉树的先序序列和后序序列正好相反，则该二叉树一定是___________的二叉树。 a．空或只有一个结点 b．高度等于其结点数 c．任一结点无左孩子 d．任一结点无右孩子

4．下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogzn)的是_________。 a．堆排序 b．冒泡排序 c．直接选择排序 d．快速排序

5．下列排序算法中，______________算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。

a．堆排序 b.冒泡排序 c．快速排序 d．SHELL排序 二、判断题(每小题1分，共10分)

判断下列各题是否正确，若正确，在()内打“√”，否则打“X”。

1．( )在循环队列中，若尾指针Rear大于头指针Front，则其元素数为Rear-Front。 2．( )串是n个字母的有限序列(n＞= 0)。

3．( )若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。 4．( )二叉树只能采用二叉链表来存储。

5．( )有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非∞的元素个数。 6．( )图G的某一最小生成树的代价一定小于其他生成树的代价。 7．( )给定结点数的平衡二叉树的高度是唯一的。

8. ( )9阶B树中，除根以外的任一结点中的关键字个数不少于4。 9．( )只有在初始数据表为倒序时，冒泡排序所执行的比较次数最多。 10．( )堆排序中，在输出一个根之后的调整操作中，“临时根”结点的值将被调到“叶子结点”上。 三、填空(每小题2分，共20分)

1． 在单链表中，删除指针P所指结点的后继结点的语句是______________________。 2． 取出广义表A：((x，y，2)，(a，b，c，d))中原子b的函数是_______________。 3． 已知完全-y．树的第八层有8个结点，则其叶子结点数是____________________。 4． 将下三角矩阵A[1．．8，L．8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已

知每个元素占4个单元，则A[?，5]的地址为______________________。 5． 有n个顶点的强连通有向图G至少有_______________条弧。

6． 求最短路径的DIJKSTRA算法的时间复杂度为______________________。 7． 高度为5的三阶B树至少有_______________个结点。

8． 在有序表A[1．.20]中，采用二分查找算法查找元素值等于A[12]的元素，所比较过的元素的

下标依次为 _______________。

9． 直接选择排序算法所执行的元素交换次数最多为 ____________________。

10.下列排序算法中，稳定的排序算法是_______________(选择排序，堆排序，快速排序，直接插入排序)。

四、解答下列各题(30分)

5

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库[模拟]信息学模拟试卷[9套]在线全文阅读。