数据结构模拟试题一一、判断题（每小题1 分，共15分）1.计算机程序处理的对象可分为数据和非数据两大类。
2.全体自然数按大小关系排成的序列是一个线性表。
3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。
4.顺序栈是一种规定了存储方法的栈。
5.树形结构中的每个结点都有一个前驱。
6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。
7.若某顶点是有向图的根，则该顶点的入度一定是零。
8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。
9.用一维数组表示矩阵可以节省存储空间。
10.广义表的长度与广义表中含有多少个原子元素有关。
11.分块查找的效率与线性表被分成多少块有关。
12.散列表的负载因子等于存入散列表中的结点个数。
13.在起泡排序过程中，某些元素可能会向相反的方向移动。
14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。
15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。
二、填空题（每空1分，共15分）1.顺序表是一种_____________线性表。
2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。
3.栈和队列的区别在于________的不同。
4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。
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个元素放在R[i]中，1≤i≤4 。
若把新插入元素存入R[6]，则________。
A．会产生运行错误B．R[1]~R[6]不构成一个顺序表C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。
当P指向链表最后一个结点时，_________。
A．P所指结点指针字段的值为空B．P的值与H的值相等C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等4. 栈的定义不涉及数据的__________。
A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。
A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,56. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。
A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在7.对于一棵具有n个结点，度为3的树来说，____________。
A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓D．至少在某一层上正好有3个结点8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。
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，依次被比较的是___________。
A．10,16,12,14 B．10,16,12 C．12,16,14 D．10,16,12,1312.含14个结点的平衡二叉排序树，其最大深度是____。
A．4 B．5 C．6 D．713．如果元素R1和R2有相同的排序码，并且进行归并排序前，R1在R2的前面，则当排序结束后，___________。
A．R1有可能在R2的后面B．R1一定在R2的后面C．R1一定在R2的前面D．选择R1或R2中的一个留在线性表中14.下面4个序列中，只有___满足堆的定义。
A．13,27,49,76,76,38,85,97 B．76,38,27,49,76,85,13,97C．13,76,49,76,27,38,85,97 D．13,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 G[n][n];V oid trav(int i){Int j,t;Int M[n],S[n];Cout<<i<<’’;M[i]=1;//做已访问标记T=1;s[t]=I;//进栈Do {(1)_______________While (2)_______________I++;If (i>n) (3)_______Else {Cout <<i<<’’;(4)_______S[++t]=I;}} while(t)}六、算法设计题（每小题12分，共24分）1.假设长度为n的线性表已存放在R[1]~R[n]中，元素类型为整型。
请写一个算法，给每个元素加上一个常数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 分，共15分）1.构成数据的最小单位是数据项。
2.空线性表的一个特性是线性表中各结点尚未赋值。
3.非循环单向链表一定要有表头指针。
4.顺序栈的栈顶指针是一个指针类型的变量。
5.在表示树的双亲数组中，找结点的双亲要比找结点的孩子容易。
6.哈夫曼树中不存在度为1的结点。
7.在图中，与V i相邻的顶点其序号一定是i+1或i-1。
8.如果是不连通的无向图，则在相应的邻接表中一定有空链表。
9.矩阵的行数和列数可以不相等。
10.广义表的深度与广义表中含有多少个子表元素有关。
11.折半查找可以在有序的双向链表上进行。
12.散列查找过程中，关键字的比较次数和散列表中关键字的个数直接相关。
13.对n个元素执行简单选择排序，排序码的比较次数总是n(n-1)/2次。
14.物理记录的大小与逻辑记录的大小成正比。
15.对索引文件，索引表是建立在内存的，数据区是建立在外存的。
二．填空题（每空1分，共15分）1.在程序中，描述顺序表的存储空间一般用________变量。
2.若用Q[0]~Q[100]作为循环顺序队列的存储空间，用“队首指针f的值等于队尾指针r的值”作为队空的标志，则创建一个空队列所要执行的操作是___________。
3.栈和顺序栈的区别仅在于________。
4.n个结点的二叉树最大高度是___，最小高度是___。
5.树的存储方法主要有_____、_____和_____三种。
6.n个顶点的强连通图中至少有___条边。
7.10行20列矩阵若用列优先顺序表来表示，则矩阵中第7行第6列元素是顺序表中第___个元素。
8.在各元素查找概率相等的情况下，在含有14个元素的平衡二叉排序树上查找其中一个元素，元素间的平均比较次数至少是_____次，至多是______次。
9.对n个元素执行快速排序，在进行第一次分组时，元素的移动次数至多是____次，至少是___次。
10.在B-树中，若某结点有i个孩子，则该结点中一定有___个关键字。
三．选择题（每题2分，共30分）1.数据结构的研究内容不涉及________。
A．算法用什么语言来描述B．数据如何存储C．数据的运算如何实现D．数据如何组织2. 若H1是动态单向链表的表头指针，H2是动态双向链表的表头指针，则________。
A．H1和H2占用同样多的内存空间B．H1和H2是同类型的变量C．H2要比H1占用更多的内存空间D．双向链表要比单向链表占用更多的内存空间3. 对于K个带头结点的静态单向链表来说，若各结点类型相同，则K个链表一般可共用_________。
A．同一个数组B．某些数组元素C．同一个表头结点D同一个表头指针4.最不适合用作链接栈的链表是_____________。
A．只有表头指针没有表尾指针的循环双向链表B．只有表尾指针没有表头指针的循环双向链表C．只有表尾指针没有表头指针的循环单向链表D．只有表头指针没有表尾指针的循环单向链表5.栈和队列的共同点在于_____________。
A．都对存储方法作了限制B．都是只能进行插入、删除运算C．都对插入、删除的位置作了限制D．都对插入、删除两种操作的先后顺序作了限制6.如果5个元素的出栈的顺序是1,2,3,4,5，则进栈的顺序可能是_____________。
