《数据结构》全真模拟试题与解答.doc

《《数据结构》全真模拟试题与解答.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、全真模拟试题一、单项选择题（在每个小题的4个备选答案中，选出正确的答案，并将其号码填在题后的括号内。每小题2分，共24分）1．一个具有n个顶点的无向完全图的边数为（　）①n(n+1)/2②n(n-1)/2③n(n-1)④n(n+1)2．在索引顺序表中查找一个元素，可用的且最快的方法是（　）①用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找②用顺序查找法确定元素所在块，再用二分查找法在相应块中查找③用二分查找法确定元素所在块，再用顺序查找法在相应块中查找④用二分查找法确定元素所在块，再用二分查找法在相应块中查找3．

2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（　）存储方式最节省运算时间。①单链表　②双链表　③带头结点的双循环链表　④容量足够大的顺序表4．串是（　）①一些符号构成的序列　②有限个字母构成的序列③一个以上的字符构成的序列　④有限个字符构成的序列5．堆排序在最坏情况下，其时间复杂性为（　）①O(nlog2n)　②O(n2)　③O(log2n2)④O(log2n)6．快速排序的记录移动次数（　）比较次数，其总执行时间为O(nlog2n)。①大于　②大于等于　③小于等于　④小于　　7．一

3、棵二叉树有n个结点，要按某顺序对该二叉树中的结点编号，（号码为1-n），编号须具有如下性质：二叉树中任一结点V，其编号等于其左子树中结点的最大编号加1。而其右子树中结点的最小编号等于V的编号加1。试问应按（　）遍历顺序编号。①前根　②中根　③后根　④层次　　8.3个结点可构成（　）个不同形态的二叉树。①2　②3　③4　④5　　9．对有n个记录的有序表采用二分查找，其平均查找长度的量级为（　）①O(log2n)　②O(nlog2n)　③O(n)　④O(n2)10．对有n个记录的表按记录键值有序的顺序建立二叉树，在这种情况下

4、，其平均查找长度的量级为（　）①O(n)　②O(nlog2n)　③O(1)　④(log2n)11．栈操作的原则是（　）①先进先出　②后进先出　③栈顶插入　④栈顶删除12．设矩阵A是一对称矩阵(aij=aji,1<=i,j<=8)，若每个矩阵元素占3个单元，将其上三角部分（包括对角线）按行序为主序存放在数组B中，B的首地址为1000，则矩阵元素a67的地址为（　）①1031　②1093　③1096　④1032二、判断题（判断下列各题是否正确，正确在括号内打“√”，错的打“×”。每小题1分，共10分）1．如果两个串含有相同的

5、字符，则这两个串相等。　　（　）2．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。　（　）3．在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每一块中元素个数有关。（　）4．在顺序表中取出第i个元素所花费的时间与i成正比。　　（　）5．在栈满情况下不能作进栈运算，否则产生“上溢”。　　　　(　）6．二路归并排序的核心操作是将两上有序序列归并为一个有序序列。　（　）7．对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点.（　

6、）8．二叉排序树或者是一棵空二叉树，或者是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值;若它的右子树非空，则根结点的值小于其右孩子的值。（　）9．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（　）10．一个有向图的邻接表和逆邻接表中表结点的个数一定相等。　（　）三、填空题（每空2分，共26分）1．在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：＿＿＿＿＿＿＿＿；L->next=U->next；free(U)；2．有一个长度为20的

7、有序表采用二分查找方法进行查找，共有＿＿＿＿＿＿个元素的查找长度为3。3．采用冒泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为＿＿＿＿＿。若A的初始状态为递减排列，则记录的交换次数为＿＿＿＿＿＿＿。4．在无头结点的双链表中，指针P所指结点是第一个结点的条件是＿＿＿＿＿＿。5．G为无向图，如果从G的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是＿＿＿＿＿图。6．如果一个有向图中没有＿＿＿＿＿＿，则该图的全部顶点可能排成一个拓扑序列。7．深度为8（根的

8、层次号为1）的满二叉树有＿＿＿＿＿＿个叶子结点。8．将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为＿＿＿＿＿＿＿。9．设某闭散列表HT未满，散列函数H（KEY）为键值第一字母在字母表中的序号，处理冲突方法为线性探测法，请在下列算法划线处填上适当内容，以实现按键值第一字