A）p->next=HL->next; HL->next=p B）p->next=HL; HL=p C）p->next=HL; p=HL D）HL=p; p->next=HL （3）对线性表，在下列哪种情况下应当采用链表表示？（ ）
A）经常需要随机地存取元素 B）经常需要进行插入和删除操作 C）表中元素需要占据一片连续的存储空间 D）表中元素的个数不变
（4）一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（ ）。
A）2 3 1 B）3 2 1 C）3 1 2 D）1 2 3
（5）每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（ ）。
A）冒泡排序 B）简单选择排序C）希尔排序 D）直接插入排序 （6）采用开放定址法处理散列表的冲突时，其平均查找长度（ ）。
A）低于链接法处理冲突 B）高于链接法处理冲突 C）与链接法处理冲突相同 D）高于二分查找
（7）若需要利用形参直接访问实参时，应将形参变量说明为（ ）参数。
A）值 B）函数 C）指针 D）引用
（8）在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ ）。
A）行号 B）列号 C）元素值 D）非零元素个数 （9）快速排序在最坏情况下的时间复杂度为（ ）。
A）O(log2n) B）O(nlog2n) C）O(n) D）O(n2) （10）从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）。
A）O(n) B）O(1) C）O(log2n) D）O(n2) 二、（本题8分）
已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 三、（本题8分）
请画出如下图所示的邻接矩阵和邻接表。
四、（每小题4分，共8分）
设有如下图所示的AOE网（其中vi（i=l，2，?，6）表示事件，弧上表示活动的天数）。
v26v14v48217v311v693v5 （1）找出所有的关键路径。
（2）v3事件的最早开始时间是多少。 五、（本题8分）
如果在1000000个记录中找出两个最小的记录，你认为采用什么样的排序方法所需的关键字比较次数最少？最多比较多少次？
5
六、（本题8分）
假设把n个元素的序列（a1,a2,…an）满足条件ak 七、（每小题4分，共8分） 设内存有大小为6个记录的缓冲区供内排序使用，文件的关键字序列为｛29,50,70,33,38,60,28,31,43,36,25,9,80,100,57,18,65,2,78,30,14,20,17,99），试列出： （1）用内排序求出初始归并段； （2）用置换一选择排序求初始归并段。 八、（本题8分） 已知一组关键字为（19,14,23,1,68,20,84,27,55,11,10,79），哈希函数：H(key)=key MOD 13，哈希地址空间为0~12，请构造用链地址法处理冲突的哈希表，并求平均查找长度。 九、（本题9分） 已知关键字序列{23，13，5，28，14，25}，试构造二叉排序树。 十、（本题15分） 编写一个算法求二又树的深度。 模拟试题（四） 一、单项选择题（每小题 2 分，共20分） （1）以下数据结构中哪一个是线性结构？（ ） A）有向图 B）栈 C）二叉树 D）B树 （2）若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（ ）存储方式最节省时间。 A）单链表 B）双链表 C）带头结点的双循环链表 D）单循环链表 （3）（ ）不是队列的基本运算。 A）在队列第i个元素之后插入一个元素 B）从队头删除一个元素 C）判断一个队列是否为空 D）读取队头元素的值 （4）字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（ ）个不同的字符串？ A）15 B）14 C）16 D）21 （5）由权值分别为4,7,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（ ）。 A）11 B）37 C）19 D）53 以下6-8题基于下面的叙述：若某二叉树结点的中序遍历的序列为A、B、C、D、E、F、G，后序遍历的序列为B、D、C、A、F、G、E。 （6）则该二叉树结点的前序遍历的序列为（ ）。 A）E、G、F、A、C、D、B B）E、A、G、C、F、B、D C）E、A、C、B、D、G、F D）E、G、A、C、D、F、B （7）该二叉树有（ ）个叶子。 A）3 B）2 C）5 D）4 （8）该二叉树的按层遍历的序列为（ ）。 A）E、G、F、A、C、D、B B）E、A、C、B、D、G、F C）E、A、G、C、F、B、D D）E、G、A、C、D、F、B （9）下面的二叉树中，（ ）不是完全二叉树。 6 （10）设有关键码序列(q,g,m,z,a)，（ ）序列是从上述序列出发建的小根堆的结果。 A）a,g ,m,q,z B）a,g,m,z,q C）g,m,q,a,z D）g, m, a,q,z 二、（本题8分） 试述顺序查找法、折半查找法和分块查找法对被查找的表中元素的要求，对长度为n的查找表来说，三种查找法在查找成功时的查找长度各是多少？ 三、（本题8分） 设有一个输入数据的序列是{ 46, 25, 78, 62, 12, 80 }，试画出从空树起，逐个输入各个数据而生成的二叉排序树。 四、（本题8分） 给定一个关键字序列｛24，19，32，43，38，6，13，22｝，请写出快速排序第一趟的结果；堆排序时所建的初始堆；然后回答上述两种排序方法中哪一种方法使用的辅助空间最小，在最坏情况下哪种方法的时间复杂度最差？ 五、（本题8分） A[0][-5]的存储地址为1000，设二维数组A[0:10,-5:0]，按行优先顺序存储，每个元素占4个单元， 则A[9][-2]的存储地址为多少？ 六、（本题8分） 用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。 七、（本题8分） 请说明对一棵二叉树进行前序、中序和后序遍历，其叶结点的相对次序是否会发生改变？为什么？ 八、（本题8分） 对于如下图所示的G，用Kruskal算法构造最小生成树，要求图示出每一步的变化情况。 九、（本题9分） 已知一棵二叉树的先序序列与中序序列分别如下，试画出此二叉树。 先序序列：ABCDEFGHIJ 中序序列：CBEDAGHFJI 十、（本题15分） 已知二叉排序树采用二叉链表存储结构，根结点的指针为T，请写出递归算法，从小到大输出该二叉排序树中所有关键字值≥K的结点的关键字的值。 模拟试题（五） 一、单项选择题（每小题 2 分，共20分） （1）队列的特点是（ ）。 7 A）先进后出 B）先进先出 C）任意位置进出 D）前面都不正确 （2）有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行（ ）遍分配与收集。 A）n B）d C）r D）n - d （3）在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（ ）。 A）都不相同 B）完全相同 C）先序和中序相同，而与后序不同 D）中序和后序相同，而与先序不同 （4）限定在一端加入和删除元素的线性表称为（ ）。 A）双向链表 B）单向链表 C）栈 D）队列 （5）快速排序执行一遍之后，已经到位的元素个数是（ ）。 A）1 B）3 C）n 4 D）n 2（6）设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树上的结点个数为n，森林F中第一棵树的结点个数是（ ）。 A）m-n-1 B）n+1 C）m-n+1 D）m-n （7）设有198个初始归并段，如采用K-路平衡归并三遍完成排序，则K值最大为（ ）。 A）12 B）13 C）14 D）15 （8）下面关于广义表的叙述中，不正确的是（ ）。 A）广义表可以是一个多层次的结构 B）广义表至少有一个元素 C）广义表可以被其他广义表所共享 D）广义表可以是一个递归表 （9）设二叉树根结点的层次为0，一棵深度（高度）为k的满二叉树和同样深度完全二叉树各有f个结点和c个结点，下列关系式不正确的是（ ）。 A）f>=c B）c>f C）f=2k+1-a D）c>sk-1 （10）从L=((apple,pear),(orange,banana))中，取出banana元素的表达式为（ ）。 A）head(tail(L)) B）head(head(tail(L))) C）tail(head(tail(L))) D）head(tail(head(tail(L)))) 二、（每小题4分，共8分） 写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 三、（每小题4分，共8分） 试对如下图中的二叉树画出其： （1）顺序存储表示； （2）二叉链表存储表示的示意图。 四、（每小题4分，共8分） 判断以下序列是否是小根堆? 如果不是，将它调整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 8
相关推荐：
loading