重庆邮电大学05数据结构2017硕士研究生考试真题

中国高端辅导品牌专注教育20年年攻读硕士学位研究生入学考试试题科目名称：数据结构A科目代码：802考生注意事项1、答题前，考生必须在答题纸指定位置上填写考生姓名、报考单位和考生编号。2、所有答案必须写在答题纸上，写在其他地方无效。3、填（书）写必须使用0.5mm黑色签字笔。4、考试结束，将答题纸和试题一并装入试卷袋中交回。5、本试题满分150分，考试时间3小时。中国高端辅导品牌专注教育20年注：所有答案必须写在答题纸上，试卷上作答无效！第1页（共6页）中国高端辅导品牌专注教育20年年攻读硕士学位研究生入学考试试题一、选择题（本大题共20小题，每小题2分，共40分）1．下面程序段的时间复杂度是（）。for(i=0;in;i++)for(j=1;jm;j++)A[i][j]=0;A.O(n)B.O(m+n+1)C.O(m+n)D.O(m*n)2．链表不具有的特点是（）。A.可随机访问任一元素B.插入、删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比3．若某栈的输入序列为1,2,3,…,n，输出序列的第一个元素为n，则第2个输出元素为（）。A.1B.n-1C.nD.都有可能4．判定一个循环队列Q（最多元素为m个）为满队列的条件是（）。A.Q.front==Q.rearB.Q.front!=Q.rearC.Q.front==(Q.rear+1)%mD.Q.front!=(Q.rear+1)%m5．设有两个串T和P，求P在T中首次出现的位置的串运算称作（）。A.联结B.求子串C.字符定位D.子串定位6．将一个A[10][10](下标从0开始计算)的矩阵按行优先顺序存放，每个元素占4个存储单元，并且A[0][5]的存储地址是1020，则A[7][2]的地址是（）。A．1000B．1020C．1108D．12887．一棵含有18个结点的二叉树的高度至少为（）。A.3B.4C.5D.68．已知某非空二叉树采用顺序存储结构，树中结点的数据信息按完全二叉树的层次序列依次存放在一个一维数组中，即则该二叉树的后序遍历序列为（）。A．G,D,B,E,F,H,C,AB．G,B,D,E,H,C,F,AC．G,D,B,H,E,F,C,AD．B,G,D,E,H,C,F,A中国高端辅导品牌专注教育20年．在下列树中，（）是完全二叉树。注：所有答案必须写在答题纸上，试卷上作答无效！第2页（共6页）中国高端辅导品牌专注教育20年．有n个球队参加的某联赛按单循环方式进行比赛，那么共需要进行（）场比赛。A．n(n-1)/2B.nC.n(n-1)D.n+111．下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(n*log2n)的是（）。A.快速排序B.冒泡排序C.直接选择排序D.堆排序12．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个元素的时间复杂度为（）（1=i=n+1）。A.O(0)B.O(1)C.O(n)D.O(n2)13．任何一个无向连通图的最小生成树（A.只有一棵B.有一棵或多棵）。C.一定有多棵D.可能不存在14．具有n个结点的满二叉树，其叶子结点有（）个。A.n/2B.(n-1)/2C.(n+1)/2D.n/2-115．下列排序方法中不稳定的是（）。A.归并排序B.快速排序C.气泡排序D.直接插入排序16．如下图，哪一项是该图的拓扑排序（）？A．1，3，2，4，5B．1，2，3，4，5C．1，2，4，3，5D．1，2，3，5，417．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。A.希尔排序B.起泡排序C.插入排序D.选择排序18．若用一中国高端辅导品牌专注教育20年的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列删除两个元素，再加入一个元素后，rear和front的值分别注：所有答案必须写在答题纸上，试卷上作答无效！第3页（共6页）中国高端辅导品牌专注教育20年年攻读硕士学位研究生入学考试试题为（）。A.1和5B.2和4C.4和2D.5和119．已知一个图如下所示，从顶点a出发进行深度优先遍历可能得到的序列为（）。bacefdA.acefbdB.acbdfeC.acbdefD.acdbfe20．若无向图G有7个顶点，至少需要（）条边，才能保证该图一定是连通图（边可依附任两顶点，但无重复边和自环）。A.6B.16C.31D.42二、填空题（本大题共10小题，每小题3分，共30分）1．有向图G用邻接矩阵A[1..n,1..n]存储，其第i行的所有非0元素的个数等于顶点i的。2．设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳个元素。3．在一棵二叉树中，度为0的结点的个数为n0，度为1的结点的个数为n1，则该二叉树共有个结点。4．某二叉树的先序遍历序列是ABDGCEFH，中序遍历序列是DGBAECHF，那么该二叉树的后序遍历序列是。5．表长为n的线性表，当在任何位置上删除一个元素的概率相等时，删除一个元素需移动元素的平均个数为。6．6阶B-树（B-Tree）中，每个结点至多包含5个关键码，除根和叶结点外，每个结点至少包含个关键码。7．已知完全二叉树的第10层（根结点为第1层）总共只有5个结点，则其叶子结点数是。8．用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R[0,..,n-1]中国高端辅导品牌专注教育20年（下标从0开始计）中，结点R[i]若有双亲节点，则双亲结点的下标是。9．某表达式二叉树按先序遍历的结果为a,b,c,d,-,*,+,e,f,/,-，令a=6,b=3,c=4,d=2,注：所有答案必须写在答题纸上，试卷上作答无效！第4页（共6页）中国高端辅导品牌专注教育20年重庆邮电大学2017年攻读硕士学位研究生入学考试试题e=5,f=1，则该表达式的值等于。10．G为无向图，如果从G的某个顶点出发进行一次遍历，即可访问图的每个顶点，则该图一定是图。三、问答题（本大题共7小题，每小题8分，共56分）1．现有森林如下图，请画出对应的二叉树。2．已知某字符串S中共有8种字符，各种字符分别出现1次、2次、7次、5次、4次、3次、4次和9次，对该字符串用{0,1}进行前缀编码。（1）请画出对应的Huffman树，并给出各字符的前缀编码；（2）请问该字符串S的编码有多少位？3．设一个无向网G的邻接矩阵A如下：4A24217313765896589（1）请根据给定的邻接矩阵A画出网G的图(G中顶点用vi表示)；（2）如果对某个顶点的邻接点的访问顺序按序号从小到大排列，请写出从顶点v1出发，按“深度优先”和“广度优先”搜索方法遍历网G所得到的顶点序列；（3）从顶点v1出发，按照最小生成树的Prim算法，画出网G的一棵最小生成树。中国高端辅导品牌专注教育20年．对一组关键字：49，38，65，97，76，13，27采用快速排序方法进行排序,用第一关键字作支点/参考值(pivot)，请写出快速排序的第一趟的交换过程。注：所有答案必须写在答题纸上，试卷上作答无效！第5页（共6页）中国高端辅导品牌专注教育20年．设Hash函数为H(K)=Kmod7，哈希表的地址空间为0，1，2，3，4，5，6，开始时哈希表为空，用二次探测再散列法解决冲突，请画出依次插入键值9、14、16、6、23、12、18后的哈希表。6．已知关键字序列为40,35,25,36,70,56,依次将各元素插入到一棵初始为空的二叉排序树，画出对应的二叉排序树。7．已知初始序列（52，80，63，44，48，91），写出直接插入排序的各趟排序的结果。四、算法设计、分析题（本大题共2小题，每小题12分，共24分）1．试写一算法，对带头结点的单链表实现就地逆置。（1）结点结构定义如下：typedefstructnode{//结点类型定义intdata;//结点的数据域structnode*next;//结点的指针域}ListNode,*LinkList;（2）先给出算法思想，再描述具体算法，必要时请给予注释说明；2．给定某一二叉树的根结点，请写一个算法判断该树是否为平衡二叉树。（1）二叉树用二叉链表表示，定义如下：typedefstructtnode{intkey;structtnode*lchild,*rchild;}BinNode,*bitree;中国高端辅导品牌专注教育20年(2)先给出算法思想，再描述算法，必要时给予注释说明注：所有答案必须写在答题纸上，试卷上作答无效！第6页（共6页）