数据结构模拟试卷9.docVIP

数据结构模拟试卷九 选择题 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用___________存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表 串的长度是___________。 A.串中不同字母的个数 B.串中不同字符的个数 C.串中所含字符的个数，且大于0 D.串中所含字符的个数 若用数组S[1..n]作为两个栈S1和S2的共用存储结构，对任何一个栈，只有当S[1..n]全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是___________。 S1的栈底位置为0，S2的栈底位置为n+1 B. S1的栈底位置为0，S2的栈底位置为n/2 C. S1的栈底位置为1，S2的栈底位置为n D. S1的栈底位置为1，S2的栈底位置为n/2 队列操作的原则是___________。 A.先进先出 B.后进先出 C.只能进行插入 D只能进行删除 有64个结点的完全二叉树的深度为___________（根的层次为1）。 A.8 B.7 C.6 D.5 在有n个结点的二叉链表中，值为非空的链域的个数为___________。 A. n－1 B.2n-1 C.n+1 D.2n+1 带权有向图G用邻接矩阵A存储。则顶点I的入度等于A中___________。 A.第I行非的元素之和 B.第I列非的元素之和 C.第I行非且非0的元素个数 D.第I列非且非0的元素个数 在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为___________。 A.o(n) B.o(log2n) C.o(nlog2n) D.o(n2) 若表R在排序前已按键值递增顺序排序，则___________算法的比较次数最少。 A.直接插入排序 B.快速排序 C.并归排序 D.选择排序 下列排序算法中，___________排序在某趟结束后不一定能选出一个元素放到其最终的位置上。 A.选择 B.冒泡 C.并归 D.堆 判断题 在带头结点的单循环链表中，任一结点的后继指针均不空。 线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间复杂度都是o(n)，因而两种存储方式的插入、删除运算所花费的时间相同。 在栈为空的情况下，不能作为栈操作，否则产生下溢出。 对矩阵压缩存储的方法是用三元组表存储矩阵元素。 在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为0。 如果有向图G＝（V,E）的拓扑序列唯一，则图中必定仅有一个顶点的入度为0，一个顶点的出度为0。 向二叉排序树中插入一个结点，所需比较的次数可能大于此二叉排序树的高度。 在索引顺序表的查找中，对索引表既可采用顺序查找方法，也可采用二分查找方法。 在快速排序算法中，以待排序的n个记录中的第一个记录的键值为基准，将所有记录分为两组，该记录就在这两组的中间，这也是该记录的最终位置。 在一个大根堆中，最小元素不一定在最后。 填空题 在单链表中，若要在指针P所指结点之后插入由指针S所指的结点，则需执行下列语句：S^.next：＝P^.next；___________； 在带有头结点的双链表L中，指针P所指结点是第一个元素结点的条件是___________。 设sq[1..maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置。能作为栈操作的条件是___________。如要把栈顶元素弹出并送到x中，则需执行下列语句：___________。 3个结点可构成___________棵不同形态的树。 树t的存储结构为二叉链表bt，树t中的一个非叶子结点在bt中满足条件___________。 设有向图G的邻接矩阵为A，如果图中不存在弧Vi,Vj，则a[I,j]的值为___________。 如果含n个顶点的图是一个环，则它有___________棵生成树。 对有17个元素的有序表A[1..17]作二分查找，在查找值等于A[8]的元素时，被比较的元素的下标依次为___________。 二叉排序树的结点及指针类型如下： type bitre=^bnode bnode=record data:datatype lchild,rchild:bitre end; 请在下面算法划线处填上适当内容，以完成在二叉排序树t中查找键值为k的结点。 Function search(t:bitre;k:datatype):bitre; Begin If t=