《数据结构导论试题和部分答案》由会员分享，可在线阅读，更多相关《数据结构导论试题和部分答案（12页珍藏版）》请在金锄头文库上搜索。
1、文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持全国2012年1月数据结构导论试题课程代码：02142一、单项选择题（本大题共15小题，每小题2分，共30分）1结点按逻辑关系依次排列形成一条锁链”的数据结构是（）A.集合B.线性结构C.树形结构D.图状结构2下面算法程序段的时间复杂度为（）for（inti=0;im;i+）for（intj=0;j0个表元素的有穷序列B.具有n（n0个字符的有穷序列C.具有n（n0个结点的有穷序列D.具有n（n0个数据项的有穷序列单链表中删除由某个指针变量指向的结点的直接后继，该算法的时间复杂度是（）A.0（1）B.0（n）C.O（log2n）D.0
2、（n）关于串的叙述，正确的是（）A.串是含有一个或多个字符的有穷序列B.空串是只含有空格字符的串C.空串是含有零个字符或含有空格字符的串D.串是含有零个或多个字符的有穷序列栈的输入序列依次为1,2,3,4,则不可能的出栈序列是（）A.1243B.1432C.2134D.43123. 队列是（）A.先进先出的线性表B.先进后出的线性表C.后进先出的线性表D.随意进出的线性表8.10阶上三角矩阵压缩存储时需存储的元素个数为（9. 深度为k（k1的二叉树，结点数最多有（）A.2k个B.（2k-1）个C.2k-1个D.（2k+1）个具有12个结点的二叉树的二叉链表存储结构中，空链域NULL的个数为（）
3、A.11B.13C.23D.2511.具有n个顶点的无向图的边数最多为（)A.n+1B.n(n+1)C.n(n-1)/2D.2n(n+1)01012.三个顶点V1,V2,V3的图的邻接矩阵为)A.0B.1C.2D.3001，该图中顶点V3的入度为（01013. 顺序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字值不相同。用顺序查找法查找时，平均比较次数约为（）D.60000外存储器的主要特点是（）A.容量小和存取速度低B.容量大和存取速度低C.容量大和存取速度高D.容量小和存取速度高在待排数据基本有序的前提下，效率最高的排序算法是
4、（）A.直接插入排序B.直接选择排序C.快速排序D.归并排序二、填空题（本大题共13小题，每小题2分，共26分）14. 数据的不可分割的最小标识单位是，它通常不具有完整确定的实际意义，或不被当作一个整体对待。15. 运算分为加工型运算和引用型运算，读取操作是运算。16. 带有头结点的单向循环链表L（L为头指针）中，指针p所指结点为尾结点的条件是。17. 在双链表中，前趋指针和后继指针分别为prior和next。若使指针p往后移动两个结点，则需执行语句。18. 元素S1，S2，S3，S4，S5，S6依次进入顺序栈S,如果6个元素的退栈顺序为S2，S3，S4，S6，S5，S1，则顺序栈的容量至少为
5、。19. 稀疏矩阵一般采用的压缩存储方法是。20. 在一棵树中，结点没有双亲。21. 棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右给所有结点编号。设根结点编号为若编号为i的结点有父结点，那么其父结点的编号为。22. 二叉树的二叉链表存储结构中判断指针p所指结点为叶子结点的条件是。23. 边稀疏的无向图采用存储较省空间。24. 除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为。25. 二分查找算法的时间复杂度是。26. 要将序列51，18，23，68,94，70，73建成堆，则只需把18与相互交换。三、应用题（本大题共5小题，每小题6分，共30分）将题29图所示的一棵二
6、叉树转换成对应的森林。题29图题31图题32图给定权值3，9，13，5，7，构造相应的哈夫曼（Huffman）树，并计算其带权路径长度。27. 写出题31图的邻接矩阵和每个顶点的入度与出度。28. 二叉排序树的各结点的值依次为2028，请在题32图中标出各结点的值。29. 用冒泡排序法对数据序列（55，38，65，97，76，138，27，49）进行排序，写出排序过程中的各趟结果。四、算法设计题（本大题共2小题，每小题7分，共14分）34.设线性表A=(a1，a2，-，旳)，B=(b1,b2,b），试写一个按下列规则合并A，B为线性表C的算法，使得C=(a1,b1,ma,bm,bm+1,b)当
7、mn时。线性表A，B和C均以带头结点的单链表作为存储结构，且C表利用A表和B表中的结点空间构成。（注意：单链表的长度值m和n均未显式存储。）35.二叉树的二叉链表类型定义如下：typedefstructbtnodedatatypedata;structbtnode*lchild,*rchild;bitreptr;写出后根遍历根指针为t的二叉树的递归算法（voidpostorder（bitreptr*t）全国2011年10月数据结构导论试题课程代码：02142一、单项选择题（本大题共15小题，每小题2分，共30分）1设栈S和队列Q的初始状态为空，元素e1，e2，e3,e4，e5和e6依次通过栈S
8、,元素退栈后即进入队列Q,若6个元素的出队序列是e2，e4，e3，e6，e5，e1,则栈S的容量至少为（）2设计一个判别表达式中左右括号是否配对出现的算法，采用的最佳数据结构为（）A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈3下列程序段的时间复杂度为（）i=0；s=0;while（sn）i+；s=s+i;A.O（n）B.O（log2n）C.O（n）D.O（n2）4设A是nxn的对称矩阵，将A的对角线及对角线上方的元素Aj（1i,jn,ij）以列优先顺序存放在一维数组元素B:1至B:n（n+1）/2中，则元素Aj（ij）在B中的位置为（）A.i（i-l）/2+jB.j（j-l）
9、/2+iC.j（j-l）/2+i-1D.i（i-l）/2+j-15在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）A.G中有弧B.G中有一条从Vi到Vj的路径C.G中没有弧D.G中有一条从Vj到Vi的路径6下列序列中，由第一趟快速排序可得到的序列（排序的关键字类型是字符串）是（）A.da,ax,eb,de,bbffha,gcB.cd,eb,ax,daffha,gc,bbC.gc,ax,eb,cd,bbffda,haD.ax,bb,cd,daffeb,gc,ha不稳定的排序方法是（）A.直接插入排序B.冒泡排序C.堆排序D.二路归并排序7. 设散列表表长m=14，散
10、列函数为h（k）=k%11，表中已有4个记录，如果用二次探测法处理冲突，关键字为49的记录的存储位置是（）012345678910111211538618438. 若元素1,2,3依次进栈，则退栈不可能出现的次序是（）A.3,2,1B.2,1,3C.3,1,2D.1,3,29. 直接插入排序的时间复杂度是（）A.O（n2）B.O（nlog2n）C.O（n）D.O（log2n）稀疏矩阵是指（）A.元素少的矩阵B.有少量零元素的矩阵C.有少量非零元素的矩阵D.行数、列数很少的矩阵10. 深度为k（k1）的二叉树，结点数最多有（）A.2kB.2k-1C.2k-1D.2k-1-113由带权为9，2，5
11、，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）14.有n个顶点的有向完全图的弧数为（）A.n2（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. 队列又称为的
12、线性表。21. 顺序栈被定义为结构类型，含有两个域：data和top，则对栈*sq进行初始化的操作是。22. 对于任何一棵二叉树T,如果其终端结点数为nO,度为2的结点数为n2，则n2=。23. 棵具有n个结点的二叉树，采用二叉链表存储，则二叉链表中指向孩子结点的指针有个。24. 若连通图G的顶点个数为n，则图G的生成树的边数为。25. 个具有n个顶点的无向图的边数最多为。26. 中根遍历二叉排序树所得到的结点访问序列是键值的序列。27. 冒泡排序的平均时间复杂度为。28. 将序列60，20，23，68，94，70，73建成堆，则只需把20与互相交换。三、应用题（本大题共5小题，每小题6分，共
13、30分）如题29图所示，在栈的输入端元素的输入顺序为A，B，C，D，进栈过程中可以退栈，写出在栈的输出端以A开头和以B开头的所有输出序列。aiun题29图题30图题31图题32图棵二叉树如题30图所示，写出该二叉树的先根遍历序列、中根遍历序列和后根遍历序列。29. 将题31图所示的一棵二叉树转换成森林。30. 对于有向无环图：（1）叙述求拓扑排序算法的基本步骤；（2）对于题32图，写出它的4个不同的拓扑排序序列。31. 判别以下序列是否为堆。如果不是，则把它调整为堆。（1）（100，86,48,73,35,39,42,57,66,21）;（2）（12，70,33,65,24,56，48,92,
14、86，33）。四、算法设计题（本大题共2小题，每小题7分，共14分）n个结点的完全二叉树按结点编号将值顺序存放在一维数组元素A:1至An中，试编写算法实现将顺序存储结构转换为二叉链表存储结构，其中根结点由tree指向。32. 试写出冒泡排序算法。全国2011年1月数据结构导论试题课程代码：02142一、单项选择题（本大题共15小题，每小题2分，共30分）1.在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为（）A.O（1）B.O（.n）C.O（log2n）D.O（n）2树形结构中，度为0的结点称为（）A.树根B.叶子C.路径D.二叉树3.已知有向图G=（V,E）,其中V=V1,V2,V3,V4,V5,V6,V7,E=,，则图G的拓扑序列是（）A.V1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V74有关图中路径的定义，表述正确的是（）A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是不同顶点所形成的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合5串的长度是指
