《数据结构》模拟试卷九

《《数据结构》模拟试卷九》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、，S2的栈底位置为n＋1（2）S1的栈底位置为0，S2的栈底位置为n／2（3）S1的栈底位置为l，S2的栈底位置为n（4）S1的栈底位置为1，S2的残底位置为n／24.队列操作的原则是。（1）先进先出（2）后进先出（3）只能进行插入（4）只能进行删除5．有64个结点的完全二叉树的深度为（根的层次为1）。（1）8（2）7（3）6（4）56.在有n个结点的二叉链表中，值为非空的链域的个数为。（1）n-l（2）2n-l（3）n＋l（4）2n＋17．带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中。（1）第i行非∞的元素之和（2）

3、第i列非∞的元素之和（3）第i行非∞且非0的元素个数（4）第i列非∞且非O的元素个数8.在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为。（1）O（n）（2）O（log2n）（3）O（nlog2n）（4）O（n2）9．若表R在排序前已按键值递增顺序排列，则算法的比较次数最少。（1）直接插入排序（2）快速排序（3）归并排序（4）选择排序10．下列排序算法中，排序在某趟结束后不一定能选出一个元素放到其最终的位置上。（l）选择（2）冒泡（3）归并（4）堆二、判断题（每小题1分，共10分）1．（）在带头结

4、点的单循环链表中，任一结点的后继指针均不空。2．（）线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间复杂度都是O（n），因而两种存储方式的插入、删除运算所花费的时间相同。3．（）在栈为空的情况下，不能作出栈操作，否则产生下溢出。4.（）对矩阵压缩存储的方法是用三元组表存储矩阵元素。5．（）在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为o。6.（）如果有向图G=（V，E）的拓扑序列唯一，则图中必定仅有一个顶点的人度为O，一个顶点的出度为0。7．（）向二叉排序树中插入一个结点，所需比较的次

5、数可能大于此二叉排序树的高度。8．（）在索引顺序表的查找中，对索引表既可采用顺序查找方法，也可采用二分查找方法。9.（）在快速排序算法中，以待排序的n个记录中的第一个记录的键值为基准，将所有记录分为两组，该记录就在这两组的中间，这也是该记录的最终位置。10．（）在一个大根堆中，最小元素不一定在最后。三、填空题（每小题2分，共24分）1．在单链表中，若要在指针P所指结点之后插入由指针S所指的结点，则需执行下列语句：S^.next:=P^.next；。2.在带有头结点的双链表L中，指针P所指结点是第一个元素结点的条件是。3．设sq

6、［1..maxsize］为一个顺序存储的栈，变量top指示栈顶元素的位置。能作入栈操作的条件是。如要把栈顶元素弹出并送到X中，则需执行下列语句。4．3个结点可构成棵不同形态的树。5．树t的存储结构为二叉链表bt，树t中的一个非叶子结点在bt中满足条件。6．设有向图G的邻接矩阵为A，如果图中不存在孤，则A[i，j]的值为。7．如果含n个顶点的图是一个环，则它有棵生成树。8.对有17个元素的有序表A［1..17］作二分查找，在查找值等于A［8」的元素时，被比较的元素的下标依次为。9．二叉排序树的结点及指针类型如下：t

7、ypebitre=^bnode；bnode=recorddata：datatype；Lchild，Rchild：bitreend；请在下面算法划线处填上适当内容，以完成在二叉排序树t中查找键值为K的结点。functionsearch（t：bitre；K：datatype）：bitre；{在t中查找键值为K的结点，成功时返回该结点的指针，否则退回nil}beginift=nilthenreturn（t）elsecaset^.data=K：return（t）；t^.data>K：；t^.data

8、选择排序算法对n个记录进行排序，最坏情况下，记录的交换次数为。四、解答下列各题（共22分）1．对下边的树，分别画出其孩子链表和孩子兄弟链表存储结构。（4分）ABCDEFGH2．已知一棵二叉树的先序序列是ABCDEFGHIJK，中序序列是CDBGFEAHJIK，请构造出该二叉树