数据结构模拟试卷9

1、数据结构模拟试卷九一、 选择题1 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_存储方式最节省运算时间。A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表2 串的长度是_。A.串中不同字母的个数 B.串中不同字符的个数 C.串中所含字符的个数，且大于0 D.串中所含字符的个数3 若用数组S1.n作为两个栈S1和S2的共用存储结构，对任何一个栈，只有当S1.n全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是_。A. S1的栈底位置为0，S2的栈底位置为n+1B. S1的栈底位置为0，S2的栈底位置为n/2C. S1的栈底位置为1

2、，S2的栈底位置为nD. S1的栈底位置为1，S2的栈底位置为n/24 队列操作的原则是_。 A.先进先出 B.后进先出 C.只能进行插入 D只能进行删除5 有64个结点的完全二叉树的深度为_（根的层次为1）。A.8 B.7 C.6 D.56 在有n个结点的二叉链表中，值为非空的链域的个数为_。A.n1 B.2n-1 C.n+1 D.2n+17 带权有向图G用邻接矩阵A存储。则顶点I的入度等于A中_。A.第I行非的元素之和 B.第I列非的元素之和 C.第I行非且非0的元素个数 D.第I列非且非0的元素个数8 在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为_。A.

3、o(n) B.o(log2n) C.o(nlog2n) D.o(n2)9 若表R在排序前已按键值递增顺序排序，则_算法的比较次数最少。A.直接插入排序 B.快速排序 C.并归排序 D.选择排序10 下列排序算法中，_排序在某趟结束后不一定能选出一个元素放到其最终的位置上。A.选择 B.冒泡 C.并归 D.堆二、 判断题1 在带头结点的单循环链表中，任一结点的后继指针均不空。2 线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间复杂度都是o(n)，因而两种存储方式的插入、删除运算所花费的时间相同。3 在栈为空的情况下，不能作为栈操作，否则产生下溢出。4 对矩阵压缩存储的方法是用三元组表

4、存储矩阵元素。5 在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为0。6 如果有向图G（V,E）的拓扑序列唯一，则图中必定仅有一个顶点的入度为0，一个顶点的出度为0。7 向二叉排序树中插入一个结点，所需比较的次数可能大于此二叉排序树的高度。8 在索引顺序表的查找中，对索引表既可采用顺序查找方法，也可采用二分查找方法。9 在快速排序算法中，以待排序的n个记录中的第一个记录的键值为基准，将所有记录分为两组，该记录就在这两组的中间，这也是该记录的最终位置。10 在一个大根堆中，最小元素不一定在最后。三、 填空题1 在单链表中，若要在指针P所指结点之后插入由指针S所指的结点

5、，则需执行下列语句：S.next：P.next；_；2 在带有头结点的双链表L中，指针P所指结点是第一个元素结点的条件是_。3 设sq1.maxsize为一个顺序存储的栈，变量top指示栈顶元素的位置。能作为栈操作的条件是_。如要把栈顶元素弹出并送到x中，则需执行下列语句：_。4 3个结点可构成_棵不同形态的树。5 树t的存储结构为二叉链表bt，树t中的一个非叶子结点在bt中满足条件_。6 设有向图G的邻接矩阵为A，如果图中不存在弧，则aI,j的值为_。7 如果含n个顶点的图是一个环，则它有_棵生成树。8 对有17个元素的有序表A1.17作二分查找，在查找值等于A8的元素时，被比较的元素的下标

6、依次为_。9 二叉排序树的结点及指针类型如下：type bitre=bnodebnode=record data:datatype lchild,rchild:bitre end;请在下面算法划线处填上适当内容，以完成在二叉排序树t中查找键值为k的结点。Function search(t:bitre;k:datatype):bitre;Begin If t=nil then return(t) Else case T.data=k; return(t); T.datak; ; T.dataP2,P1P3,P1P4,P2P3,P2P5,P3P6,P4P6,P5P6。其中符号“”表示先于关系，例如P1P3表示只有在P1完成只会才能进行P3的工作。请给出工程P的四种可能的施工顺序。4 设散列表的长度为9，散列函数为H(x)I div 3，其中I为键值x中第一个字母在字母表中的序号，若键值的输入序列为jan，feb，mar，apr,may,jun,jul,aug,sep,oct,nov,dec，用拉链法处理冲突，要求：（1） 构造散