全国2012年1月 数据结构导论试题 课程代码:02142 一、单项选择题(本大题共15小题,每小题2分,共30分) 1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( )A.集合 B.线性结构 C.树形结构 D.图状结构 2.下面算法程序段的时间复杂度为( ) for ( int i=0; ifor ( int j=0; ja[i][j]=i*j; A. O(m2) B. O(n2) C. O(mn) D. O(m+n) 3.线性结构是( )A.具有n(n≥0)个表元素的有穷序列 B.具有n(n≥0)个字符的有穷序列 C.具有n(n≥0)个结点的有穷序列 D.具有n(n≥0)个数据项的有穷序列 4.单链表中删除由某个指针变量指向的结点的直接后继,该算法的时间复杂度是( ) A. O(1) B. O(n) C. O(log2n) D. O(n) 5.关于串的叙述,正确的是( ) A.串是含有一个或多个字符的有穷序列 B.空串是只含有空格字符的串 C.空串是含有零个字符或含有空格字符的串 D.串是含有零个或多个字符的有穷序列 6.栈的输入序列依次为1,2,3,4,则不可能的出栈序列是( )A.1243 B. 1432 C. 2134 D.4312 7.队列是( )A. 先进先出的线性表 B. 先进后出的线性表 C. 后进先出的线性表 D.随意进出的线性表 8.10阶上三角矩阵压缩存储时需存储的元素个数为( ) A.11 B.56 C.100 D.101 9.深度为k(k≥1)的二叉树,结点数最多有( )A.2k 个 B.(2k -1)个 C.2k-1个 D.(2k+1)个 10.具有12个结点的二叉树的二叉链表存储结构中,空链域NULL的个数为( )A. 11 B.13 C. 23 D. 25 11.具有n个顶点的无向图的边数最多为( )A.n+1 B.n(n+1) C.n(n-1)/2 D.2n(n+1)
12.三个顶点v1,v2,v3的图的邻接矩阵为010001010,该图中顶点v3的入度为( )A. 0 B. 1 C. 2 D.
3 13.顺序存储的表格中有60000个元素,已按关键字值升序排列,假定对每个元素进行查找的概率是相同的,且每个元素的关键字值不相同。用顺序查找法查找时,平均比较次数约为( )A.20000 B.30000 C.40000 D.60000 14.外存储器的主要特点是( ) A.容量小和存取速度低 B.容量大和存取速度低 C.容量大和存取速度高 D.容量小和存取速度高 15.在待排数据基本有序的前提下,效率最高的排序算法是()A.直接插入排序 B.直接选择排序C.快速排序D.归并排序 二、填空题(本大题共13小题,每小题2分,共26分) 16.数据的不可分割的最小标识单位是______,它通常不具有完整确定的实际意义,或不被当作一个整体对待。 17.运算分为加工型运算和引用型运算,读取操作是______ 运算。 18.带有头结点的单向循环链表L(L为头指针)中,指针p所指结点为尾结点的条件是 ______。 19.在双链表中,前趋指针和后继指针分别为prior和next。若使指针p往后移动两个结点,则需执行语句 ______。 20.元素s1,s2,s3,s4,s5,s6依次进入顺序栈S,如果6个元素的退栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少为 ______。 21. 稀疏矩阵一般采用的压缩存储方法是______ 。 22. 在一棵树中,______ 结点没有双亲。 23.一棵具有n个结点的完全二叉树中,从树根起,自上而下、自左至右给所有结点编号。设根结点编号为1,若编号为i的结点有父结点,那么其父结点的编号为 ______。 24.二叉树的二叉链表存储结构中判断指针p所指结点为叶子结点的条件是______。 25.边稀疏的无向图采用 ______存储较省空间。 26.除第一个顶点和最后一个顶点相同外,其余顶点不重复的回路,称为 ______。 27.二分查找算法的时间复杂度是 ______。 28.要将序列{51,18,23,68,94,70,73}建成堆,则只需把18与 ______相互交换。 三、应用题(本大题共5小题,每小题6分,共30分) 29.将题29图所示的一棵二叉树转换成对应的森林。
题29图 题31图 题32图 30.给定权值{3,9,13,5,7},构造相应的哈夫曼(Huffman)树,并计算其带权路径长度。 31.写出题31图的邻接矩阵和每个顶点的入度与出度。 32. 二叉排序树的各结点的值依次为20~28,请在题32图中标出各结点的值。 33.用冒泡排序法对数据序列(55,38,65,97,76,138,27,49)进行排序,写出排序过程中的各趟结果。 四、算法设计题(本大题共2小题,每小题7分,共14分) 34.设线性表A =(a1, a2, …,am),B=(b1, b2, …,bn),试写一个按下列规则合并A,B为线性表C的算法,使得 C=(a1, b1, …, am ,bm ,bm+1, …,bn) 当m≤n时; 或者 C=(a1, b1, …, an ,bn ,an+1, …,am) 当m>n时。 线性表A,B和C均以带头结点的单链表作为存储结构,且C表利用A表和B表中的结点空间构成。(注意:单链表的长度值m和n均未显式存储。) 35. 二叉树的二叉链表类型定义如下: typedef struct btnode { datatype data; struct btnode *lchild,*rchild; } bitreptr; 写出后根遍历根指针为t的二叉树的递归算法( void postorder (bitreptr *t) )。 全国2011年10月 数据结构导论试题 课程代码:02142 一、单项选择题(本大题共15小题,每小题2分,共30分) 1.设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈S,元素退栈后即进入队列Q,若6个元素的出队序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少为( )A.2 B.3 C.4 D.6 2.设计一个判别表达式中左右括号是否配对出现的算法,采用的最佳数据结构为( ) A.线性表的顺序存储结构 B.队列 C.线性表的链式存储结构 D.栈 3.下列程序段的时间复杂度为( ) i=0;s=0; while(sA.O(n) B.O(log2n) C.O(n) D.O(n2) 4.设A是n×n的对称矩阵,将A的对角线及对角线上方的元素Aij(1≤i,j≤n,i≤j)以列优先顺序存放在一维数组元素B[1]至B[n(n+1)/2]中,则元素Aij(i≤j)在B中的位置为( ) A.i(i-l)/2+j B.j(j-l)/2+i C.j(j-l)/2+i-1 D.i(i-l)/2+j-1 5.在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形不可能出现的是( ) A.G中有弧 B.G中有一条从Vi到Vj的路径 C.G中没有弧 D.G中有一条从Vj到Vi
的路径
6.下列序列中,由第一趟快速排序可得到的序列(排序的关键字类型是字符串)是( ) 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] 7.不稳定的排序方法是( )A.直接插入排序 B.冒泡排序 C.堆排序 D.二路归并排序 8.设散列表表长m=14,散列函数为h(k)=k%11,表中已有4个记录,如果用二次探测法处理冲突,关键字为49的记录的存储位置是( ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 15 38 61 84 A.3 B.5 C.8 D.9 9.若元素1,2,3依次进栈,则退栈不可能出现的次序是( ) A.3,2,1 B.2,1,3 C.3,1,2 D.1,3,2 10.直接插入排序的时间复杂度是( )A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n) 11.稀疏矩阵是指( ) A.元素少的矩阵 B.有少量零元素的矩阵 C.有少量非零元素的矩阵 D.行数、列数很少的矩阵 12.深度为k(k≥1)的二叉树,结点数最多有( )A.2k B.2k-1 C.2k-1 D.2k-1-1 13.由带权为9,2,5,7的四个叶子结点构造一棵哈夫曼树,该树的带权路径长度为( )A.23 B.37 C.44 D.46 14.有n个顶点的有向完全图的弧数为( )A.n2 B.2n C.n(n-1) D.2n(n+1) 15.图的深度优先搜索类似于二叉树的( )A.先根遍历 B.中根遍历 C.后根遍历 D.层次遍历 二、填空题(本大题共13小题,每小题2分,共26分) 16.下列程序段的时间复杂度为_________。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) x++; 17.数据结构中结点按逻辑关系依次排列形成一条“锁链”的结构是_________。 18.在表长为n的顺序表上做删除运算,平均要移动的结点个数为_________。 19.在带有头结点的单循环链表head中,指针p所指结点为尾结点的条件是_________。 20.队列又称为_________的线性表。 21.顺序栈被定义为结构类型,含有两个域:data和top,则对栈*sq进行初始化的操作是_________。 22.对于任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n2=_________。 23.一棵具有n个结点的二叉树,采用二叉链表存储,则二叉链表中指向孩子结点的指针有_________个。 24.若连通图G的顶点个数为n,则图G的生成树的边数为_________。 25.一个具有n个顶点的无向图的边数最多为_________。 26.中根遍历二叉排序树所得到的结点访问序列是键值的_________序列。 27.冒泡排序的平均时间复杂度为_________。 28.将序列{60,20,23,68,94,70,73}建成堆,则只需把20与_________互相交换。 三、应用题(本大题共5小题,每小题6分,共30分) 29.如题29图所示,在栈的输入端元素的输入顺序为A,B,C,D,进栈过程中可以退栈,写出在栈的输出端以A开头和以B开头的所有输出序列。
题29图 题30图 题31图 题32图 30.一棵二叉树如题30图所示,写出该二叉树的先根遍历序列、中根遍历序列和后根遍历序列。 31.将题31图所示的一棵二叉树转换成森林。 32.对于有向无环图: (1)叙述求拓扑排序算法的基本步骤; (2)对于题32图,写出它的4个不同的拓扑排序序列。 33.判别以下序列是否为堆。如果不是,则把它调整为堆。 (1)(100,86,48,73,35,39,42,57,66,21);(2)(12,70,33,65,24,56,48,92,86,33)。 四、算法设计题(本大题共2小题,每小题7分,共14分) 34.n个结点的完全二叉树按结点编号将值顺序存放在一维数组元素A[1]至A[n]中,试编写算法实现将顺序存储结构转换为二叉链表存储结构,其中根结点由tree指向。 35.试写出冒泡排序算法。