数据结构模拟试题一及答案(共4页).docx
精选优质文档-倾情为你奉上数据结构模拟试题一一、 判断题（每小题1 分，共15分）1. 计算机程序处理的对象可分为数据和非数据两大类。2. 全体自然数按大小关系排成的序列是一个线性表。3. 在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。4. 顺序栈是一种规定了存储方法的栈。5. 树形结构中的每个结点都有一个前驱。6. 在任何一棵完全二叉树中，最多只有一个度为1的分支结点。7. 若某顶点是有向图的根，则该顶点的入度一定是零。8. 如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。9. 用一维数组表示矩阵可以节省存储空间。10. 广义表的长度与广义表中含有多少个原子元素有关。11. 分块查找的效率与线性表被分成多少块有关。12. 散列表的负载因子等于存入散列表中的结点个数。13. 在起泡排序过程中，某些元素可能会向相反的方向移动。14. 按某种逻辑关系组织起来的记录的集合称为逻辑记录。15. 索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。二、 填空题（每空1分，共15分）1. 顺序表是一种_线性表。2. 若用Q1Qm作为非循环顺序队列的存储空间，则对该队列最多只能执行_次插入操作。3. 栈和队列的区别在于_的不同。4. 在高度为h(h0)的二叉树中至少有_个结点，至多有_个结点。5. 若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有_个左指针域为空的结点，有_个右指针域为空的结点。6. n个顶点的有根有向图中至少有_条边，至多有_条边。7. 10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第_个元素。8. 在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是_。9. 在归并两个长度为m的有序表时，排序码的比较次数至少是_次，至多是_次。10. 在高度为3的6阶B-树中，至少有_个关键字，至多有_个关键字。三、 选择题（每题2分，共30分）1. 计算机所处理的数据一般具有某种内在联系性，这是指_。A元素和元素之间存在某种关系 B数据和数据之间存在某种关系C元素内部具有某种结构 D数据项和数据项之间存在某种关系2. 假设顺序表目前有4个元素，第i个元素放在Ri中，1i4 。若把新插入元素存入R6，则_。A会产生运行错误 BR1R6不构成一个顺序表C顺序表的长度大于顺序表元素个数，会降低存储空间利用率D顺序表元素序号和数组元素下标不一致，会给使用带来麻烦3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_。AP所指结点指针字段的值为空 BP的值与H的值相等CP所指结点的地址与H的值相等 DP所指结点指针字段的值与H的值相等4. 栈的定义不涉及数据的_。A逻辑结构 B存储结构 C运算 D逻辑结构和存储结构5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是_。A2,4,1,3,5 B3,4,1,5,2 C3,2,4,1,5 D4,1,3,2,56. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_。A只有一个结点 B每个结点都没有左孩子 C每个结点都没有右孩子 D不存在7.对于一棵具有n个结点，度为3的树来说，_。A树的高度至多是n-3 B树的高度至多是n-2 C树的最低高度是log3(n+1)D至少在某一层上正好有3个结点8n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向abgcehfd图_。A含n个强连通分量 B有唯一的入度为0的顶点 C有多个出度为0的顶点D是一个有根有向图9. 特殊矩阵用行优先顺序表表示，_A简化了矩阵元素之间的逻辑关系 B便于按行处理矩阵元素 C无法根据行列号计算矩阵元素的存储地址 D可以节省存储空间10. 对一个非空的广义表来说，_。A可能不含任何原子元素 B至少含一个原子元素 C其长度不小于其中任何一个子表的长度 D至少含一个非空的子表元素11.在有序表（2,4,6,8,10,12,14,16,18,20）上用折半查找方法查找13，依次被比较的是_。A10,16,12,14 B10,16,12 C12,16,14 D10,16,12,1312.含14个结点的平衡二叉排序树，其最大深度是_。A4 B5 C6 D713如果元素R1和R2有相同的排序码，并且进行归并排序前，R1在R2的前面，则当排序结束后，_。AR1有可能在R2的后面 BR1一定在R2的后面 CR1一定在R2的前面 D选择R1或R2中的一个留在线性表中14.下面4个序列中，只有_满足堆的定义。A13,27,49,76,76,38,85,97 B76,38,27,49,76,85,13,97C13,76,49,76,27,38,85,97 D13,27,38,76,49,85,76,9715下面4种排序方法中，属于不稳定的排序方法是_排序和_排序。A快速 B归并 C简单选择 D折半插入四、图表题1.已知树结点的前序序列是abcdefgh ，后序序列是cdebfhga，请画出这棵树的逻辑结构图。2. 采用基数排序法，对排序码序列572,586,413,15,724,529,525,608,37,119按从小到大的次序排序，请写出每趟收集后的线性表。五、算法填空题假设G是n个顶点的连通无向图的邻接矩阵。下面的算法可用于对无向图进行深度遍历。请在空内填入适当内容，将算法补充完整。Const n=10;Int Gnn;Void trav(int i) Int j,t; Int Mn,Sn; Cout<<i<< Mi=1;/做已访问标记 T=1;st=I;/进栈 Do (1)_ While (2)_ I+; If (i>n) (3)_Else Cout <<i<<(4)_S+t=I; while(t)六、算法设计题（每小题12分，共24分）1.假设长度为n的线性表已存放在R1Rn中，元素类型为整型。请写一个算法，给每个元素加上一个常数x，若相加后该元素为0，则将该元素从线性表中删除。2.在一个m行n列的矩阵中，由相邻的并且取值相同的元素所构成的集合称为区域。例如，在图1所示矩阵中存在5个区域。设计算法setcolor(x,y,c)，算法的功能中将x行y列元素所在区域的所有元素的值改为c。例如，对图1所示矩阵执行算法调用setcolor(4,3,1)，应得结果如图2所示。3 0 2 2 0 3 1 2 2 10 0 2 0 0 1 1 2 1 13 0 3 3 0 3 1 3 3 13 0 0 3 0 3 1 1 3 13 3 0 0 0 3 3 1 1 1图1 图2数据结构模拟题一参考答案一.判断题1、× 2、× 3、× 4、 5、× 6、 7、×. 8、 9、× 10、× 11、12、× 13、 14、×. 15、×二填空题1.用顺序方法存储的 2.m 3.运算方法定义 4.h 2h-1 5.m n+1 6.n-1 n(n-1) 7. 147 8. 6.5 9.m 2m-1 10. 5 35三.选择题1.A 2.B 3.D 4.B 5.C 6.B 7.B 8.A 9.D 10.A 11.A 12.B 13.C 14.D 15.A C四.图表题1. abgcehfd2.第一趟：572，413，724，15，525，586，37，608，529，119第二趟：608，413，15，119，724，525，529，37，572，586第三趟：15，37，119，413，525，529，572，586，608，724五.算法填空题：(1) j=St; i=1;(2) (i<=n)&&(Gji=0|Mi=1)(3) t=t-1;(4) Mi=1;六.算法设计题1.const n0=100;int Rn0+1;int n;void add() int i, j; j=1; for (i=1; i<=n; i+) if (Ri!=x) Rj=Ri+x; J=j+1; n=j-1;2. const m=10, n=10, d42=1,0,0,-1,-1,0,0,1; int Gm+1n+1; int c0; void paint(int x, int y, int c) int i , u, v; Gxy=c; for (i=0; i<=3; i+) u=x+di0; v=y+di1; if (u>=1)&&(u<=m)&&(v>=1)&&(v<=n)&&(Guv=c0) paint(u,v,c); 专心-专注-专业
