2013-2014第1学期数据结构模拟考试题

装密年级：专业：班级：订封姓名：学号：线线重庆邮电大学20xx－20xx学年《数据结构》模拟考试题注意：答案写到后面的答题纸上，按要求答题，并请保持字迹清楚，容易阅读。一、选择题（每题2分，共30分）1.栈和队列的共同点有（？）。A．都是先进先出B．都是后进先出C．不会删除中间的元素D．完全没有共同点2.链表不具有的特点是（？）。A.可随机访问任一元素B.插入、删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比3.在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依相同次序从该缓冲区中取出数据打印。该缓冲区作为数据结构是一个（？）结构。A.栈B.队列C.哈希表（HashTable）D.线性表4.设计一个判别表达式中左、右括号是否配对出现的算法，采用（？）数据结构最佳。A.栈B.队列C.顺序结构线性表D.链式结构线性表5.若某栈的输入序列为1,2,3,…,n，输出序列的第一个元素为n，则第2个输出元素为（？）。A.1B.n-1C.nD.都有可能6.首先访问某结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为（？）A.前序遍历B.后序遍历C.中序遍历D.层次遍历7.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlog2n)的是（？）。A.快速排序B.冒泡排序C.直接选择排序D.堆排序8.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个元素的时间复杂度为（？）（1=i=n+1）。A.O(0)B.O(1)C.O(n)D.O(n2)9.已知数据表A中每个元素距其最终位置不远，则采用（？）排序算法最节省时间。A.堆排序B.直接插入排序C.快速排序D.简单选择排序10.任何一个无向连通图的最小生成树（？）。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在11.下列序列中，（？）是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。A.[da,ax,eb,de,bb]ff[ha,gc]B.[cd,eb,ax,da]ff[ha,gc,bb]C.[gc,ax,eb,cd,bb]ff[da,ha]D.[ax,bb,cd,da]ff[eb,gc,ha]12．对包含N个元素的散列表进行查找，平均查找长度（）A、为O(log2N)B、为O(N)C、不直接依赖于ND、三者都不是13.给定下列有向图和初始结点V1,按深度优先遍历的结点序列为(？)A、V1，V3，V4，V5，V2B、V1，V2，V3，V4，V5C、V1，V2，V5，V3，V4D、V1，V2，V4，V5，V314.串是（？）。A.不少于一个字母的序列B.任意个字母的序列C.不少于一个字符的序列D.有限个字符的序列15．有n个球队参加的某联赛按单循环方式进行比赛，那么共需要进行（？）场比赛。A．n(n-1)/2B.nC.n(n-1)D.n+1题号一二三四五六总分分数评卷人装密年级：专业：班级：订封姓名：学号：线线二、填空题（每题2分，共20分）1．采用特殊字符作为串的结束，串S=“WinFilename”需要至少长度为（?）的字符数组存放。2．已知数组A[1..10,1..10]为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存储在起始地址为1000的连续内存单元中，则元素A[5，6]对应的地址为（?）。3．已知完全二叉树的第5层有3个结点(根结点为第1层)，则其结点数是（?）4．已知二叉树中叶子结点数为12，仅有一个孩子的结点数为5，则总结点数是（?）。5．具有12个结点的完全二叉树的高度（空树高度为0）为（?）。6．高度（空树高度为0）为5的AVL树，其结点数最少是（?）。7．在链式结构的线性表中插入元素的算法复杂度是（?）。8．已知一个无向图的邻接矩阵表示，计算第j个结点的度的方法是（?）。9．G为无向图，如果从G的某个顶点出发进行一次遍历，即可访问图的每个顶点，则该图一定是（?）图。10．对于键值序列{12,13,11,18,60,15,7,18,25,100}，建里初始堆，必须从键值为（?）的结点开始对每个结点进行一次堆调整。三、问答题。（每题6分，共24分）1．直接选择排序是选出n个数据元素中最小的（或最大的），与最左（右）边的数据元素相交换，然后按同样的办法考虑剩下的n-1数据元素直到只剩下一个数据元素为止。请分析直接选择排序算法的时间复杂度。2．已知关键字序列为36,31,20,32,66,48,依次将各元素插入到一棵初始为空的二叉排序树，画出对应的二叉排序树。3．已知二叉树如左下图，试写出后序遍历结果。3题图4题图4．现有森林如右上图，请画出对应的二叉树。四、算法应用、分析题（共18分）1.图G各顶点的连接关系及相应权值如下图所示。（1）画出图的邻接表存储图示（2）并从顶点1开始对图进行广度优先遍历，写出遍历结果；（3）使用Kruskal算法求该图的最小生成树，给出的形成过程。（11分）2.设Hash函数为H(K)=Kmod7，哈希表的地址空间为0，．．．，6，开始时哈希表为空，用平方探测法解决冲突，请画出依次插入键值9，14，10，30，56后的哈希表。五、算法设计题。（共8分）已知二叉树用二叉链表存储，试编写一函数实现计算该树的高度。请定义必要的数据结构。54153326264673