《模拟试卷DS1》由会员分享，可在线阅读，更多相关《模拟试卷DS1（4页珍藏版）》请在金锄头文库上搜索。
1、模拟试卷一一、单项选择题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）插入删除不需要移动元素（2）不必事先估计存储空间（4）所需空间与线性表长度成正比
2、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,bbff ha,gc （ 2）cd,eb,ax,daffha,gc,bb （3）gc,ax,eb,
3、cd,bbff da,ha （ 4）ax,bb,cd,daffeb,gc,ha 9用 n 个键值构造一棵二叉排序树，最低高度为。（1）n/2 （2）n （3） log2n （4） log2n+110二分查找法要求查找表中各元素的键值必须是排列。（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（）在顺序表中取
4、出第I 个元素所花费的时间与I 成正比。4（）在栈满情况下不能作进栈运算，否则产生“上溢”。5（）二路归并排序的核心操作是将两个有序序列归并为一个有序序列。6（）对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点7（）一个有向图的邻接表和逆邻接表中的结点个数一定相等。8（）在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。9（）二叉排序树或者一棵空树，或者是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其右孩子的值。10（）在执行某个排序
5、算法过程中，出现了排序序列位置相反方向移动，则该算法是不稳定的。三、填空题1在带有头结点的单链表L 中，第一个元素结点的指针是。2在双循环链表中，在指针P 所指结点前插入指针S 所指的结点，需执行下列语句：S-next =P；-Prior= -Prior ；P- prior=S ；=S；3设 S1 maxsize为一个顺序存储的栈，变量top 指示栈顶位置，栈为空的条件是，栈为满的条件是。4具有 100 个结点的完全二叉树的深度为。5有向图 G 用邻接矩阵A1n 存储， 其第 i 行的所有元素之和等于顶点i 的。6在顺序文件中，要存取第i 个记录，必须先存取。7对于下面的二叉树，按中序遍历所得
6、到的结点序列为。8分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增顺序排序，最省时间的是算法，最费时间是算法。9对下图所示的网，执行prim 算法可得到最小生成树，试在下表的空白处填上适当的内容，以说明该算法的执行过程。顶 点1 3 4 U V (U,V) 代价(2,1) (2,3) 4 (2,4) 2 2 1,3,4 (U,V ）代价(2,3) 4 2,4 1,3 (U,V) 代价(3,1) 1 2,4,3 1 (U,V) 代价2,4,3,1 A B C D E F G 1 3 4 2 4 2 1 5 4 第 7 题图第 9 题图10设散列函数为H（key），用拉链（链地址）
7、法解决冲突，ht 的值域为0， n-1，构造的散列表类型如下：struct node T data；struct node *next ；; 请在下列算法划线处填上适当内容，以完成在散列表中查找键值等于的结点，若查找成功，返回该结点的指针，否则返回空指针research(T K) j=H ( K) ; ; while ( p & p - data!=K); if ( p- data= =k) return p; else q=new Node; q - data=k; q- next= htj; htj=q; 四、应用题1、已知二叉树的后序和中序序列如下，构造出该二叉树。后序序列：中序序列：2、有一组关键码序列（38,19,65,13,97,49,41,95,1,73 ）,采用冒泡排序方法由小到大进行排序，请写出每趟的结果。3、设图（V,E）,V=1,2,3,4,5,6,E=,。请写出图中顶点的所有拓扑序列。4、设散列函数为()K mod 7,闭散列表的地址空间为，开始时散列表为空，用线性探测法解决冲突，请画出依次插入键值23,14,9,6,30,12,18 后的散列表。5、对下面两棵二叉树，分别画出它们的顺序存储结构。6、已知图邻接表如下，画出图的所有连通分量。5 4 6 2 1 3 2 3 7 7 7 9 3 6 9 4
