数据结构考试卷子(共11页).doc

《数据结构考试卷子(共11页).doc》由会员分享，可在线阅读，更多相关《数据结构考试卷子(共11页).doc（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据结构模拟试题一一、 判断题（每小题1 分，共15分）1. 计算机程序处理的对象可分为数据和非数据两大类。2. 全体自然数按大小关系排成的序列是一个线性表。3. 在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。4. 顺序栈是一种规定了存储方法的栈。5. 树形结构中的每个结点都有一个前驱。6. 在任何一棵完全二叉树中，最多只有一个度为1的分支结点。7. 若某顶点是有向图的根，则该顶点的入度一定是零。8. 如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。9. 用一维数组表示矩阵可以节省存储空间。10. 广义表的长度与广义表中含有多少

2、个原子元素有关。11. 分块查找的效率与线性表被分成多少块有关。12. 散列表的负载因子等于存入散列表中的结点个数。13. 在起泡排序过程中，某些元素可能会向相反的方向移动。14. 按某种逻辑关系组织起来的记录的集合称为逻辑记录。15. 索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。二、 填空题（每空1分，共15分）1. 顺序表是一种_线性表。2. 若用Q1Qm作为非循环顺序队列的存储空间，则对该队列最多只能执行_次插入操作。3. 栈和队列的区别在于_的不同。4. 在高度为h(h0)的二叉树中至少有_个结点，至多有_个结点。5. 若用二叉链表来存储具有m个叶子，n个分支结点

3、的树，则二叉链表中有_个左指针域为空的结点，有_个右指针域为空的结点。6. n个顶点的有根有向图中至少有_条边，至多有_条边。7. 10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第_个元素。8. 在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是_。9. 在归并两个长度为m的有序表时，排序码的比较次数至少是_次，至多是_次。10. 在高度为3的6阶B-树中，至少有_个关键字，至多有_个关键字。三、 选择题（每题2分，共30分）1. 计算机所处理的数据一般具有某种内在联系性，这是指_。A元素和元素之间存在某种关系

4、 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存储

5、结构 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个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图_。A含n个强连通分量 B有唯一的入度为0的顶点 C有多个

6、出度为0的顶点D是abgcehfd一个有根有向图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个结点的平衡二叉排序树，其最大深度是_。A

7、4 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.已知树结点的前序序列是

8、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; Coutin) (3)_Else Cout i;(4)_S+t=I; while(t)六、算法设计题（每小题12分

9、，共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

10、13 3 0 0 0 3 3 1 1 1图1 图2数据结构模拟试题二一判断题（每小题1 分，共15分）1. 构成数据的最小单位是数据项。2. 空线性表的一个特性是线性表中各结点尚未赋值。3. 非循环单向链表一定要有表头指针。4. 顺序栈的栈顶指针是一个指针类型的变量。5. 在表示树的双亲数组中，找结点的双亲要比找结点的孩子容易。6. 哈夫曼树中不存在度为1的结点。7. 在图中，与Vi相邻的顶点其序号一定是i+1或i-1。8. 如果是不连通的无向图，则在相应的邻接表中一定有空链表。9. 矩阵的行数和列数可以不相等。10. 广义表的深度与广义表中含有多少个子表元素有关。11. 折半查找可以在有序的

11、双向链表上进行。12. 散列查找过程中，关键字的比较次数和散列表中关键字的个数直接相关。13. 对n个元素执行简单选择排序，排序码的比较次数总是n(n-1)/2次。14. 物理记录的大小与逻辑记录的大小成正比。15. 对索引文件，索引表是建立在内存的，数据区是建立在外存的。二填空题（每空1分，共15分）1. 在程序中，描述顺序表的存储空间一般用_变量。2. 若用Q0Q100作为循环顺序队列的存储空间，用“队首指针f的值等于队尾指针r的值”作为队空的标志，则创建一个空队列所要执行的操作是_。3. 栈和顺序栈的区别仅在于_。4. n个结点的二叉树最大高度是_，最小高度是_。5. 树的存储方法主要有

12、_、_和_三种。6. n个顶点的强连通图中至少有_条边。7. 10行20列矩阵若用列优先顺序表来表示，则矩阵中第7行第6列元素是顺序表中第_个元素。8. 在各元素查找概率相等的情况下，在含有14个元素的平衡二叉排序树上查找其中一个元素，元素间的平均比较次数至少是_次，至多是_次。9. 对n个元素执行快速排序，在进行第一次分组时，元素的移动次数至多是_次，至少是_次。10. 在B-树中，若某结点有i个孩子，则该结点中一定有_个关键字。三选择题（每题2分，共30分）1.数据结构的研究内容不涉及_。A算法用什么语言来描述 B数据如何存储C数据的运算如何实现 D数据如何组织2. 若H1是动态单向链表的

13、表头指针，H2是动态双向链表的表头指针，则_。AH1和H2占用同样多的内存空间 BH1和H2是同类型的变量CH2要比H1占用更多的内存空间D双向链表要比单向链表占用更多的内存空间3. 对于K个带头结点的静态单向链表来说，若各结点类型相同，则K个链表一般可共用_。A同一个数组 B某些数组元素 C同一个表头结点 D同一个表头指针4.最不适合用作链接栈的链表是_。A只有表头指针没有表尾指针的循环双向链表B只有表尾指针没有表头指针的循环双向链表C只有表尾指针没有表头指针的循环单向链表D只有表头指针没有表尾指针的循环单向链表5.栈和队列的共同点在于_。A都对存储方法作了限制 B都是只能进行插入、删除运算

14、 C都对插入、删除的位置作了限制 D都对插入、删除两种操作的先后顺序作了限制6.如果5个元素的出栈的顺序是1,2,3,4,5，则进栈的顺序可能是_。A3,5,4,1,2 B.1,4,5,3,2 C.2,4,3,1,5 D.5,1,3,2,4 7.若某棵二叉树结点的后序序列和层次序列正好相反，则该二叉树_。A每个结点都没有右孩子 B不存在度为2的结点 C每个结点都没有左孩子 D不存在8.对于一棵具有n个结点，度为3的树来说，树的高度至少是_。Alog32n Blog3(3n-1) Clog3(3n+1) Dlog3(2n+1)9对n个顶点的带权连通图来说，它的最小生成树是指图中任意一个由n-1条

15、_。A权值最小的边构成的子图 B权值之和最小的边构成的子图 C权值之和最小的边构成的连通子图 D权值之和最小的边构成的无环子图10. 所谓特殊矩阵是指_比较特殊。A矩阵元素之间的关系 B矩阵的处理方法C矩阵元素的取值 D矩阵的存储方法11.若长度为n且有n种不同原子的广义表用链接方法存储，则时间复杂度为O（n）的运算是_。A复制一个广义表 B求广义表的长度 C查找某个子表 D查找某个原子12. 待查找元素关键字的值依次是47，且已存入变量k中，如果在查找过程中，和K进行比较的关键字值依次是47,32,46,25,47,则采用的查找方法_。A是一种错误的查找方法 B可能是分块查找 C可能是顺序查

16、找 D可能是折半查找13如果元素R1和R2有相同的排序码，并且进行堆排序前，R1在R2的前面，则当排序结束后，_。AR1一定在R2的前面 BR1一定在R2的后面 CR1有可能在R2的后面 D选择R1或R2中的一个留在线性表中14.下面4种排序方法中，属于稳定的排序方法是_排序和_排序。A堆 B基数 C. 快速 D. 起泡15在线性表中元素很多，且各元素已有序排列的情况下，执行_排序或_排序，排序码比较次数最多。A简单选择 B堆 C归并 D堆四图表题（每小题4分，共8分）1.已知5个叶子结点的权值分别为2，5，5，6，9，13 请画出相应的哈夫曼树。2.对图1所示无向网络，画出从顶点V6开始用普

17、里姆方法构造的最小生成树。五算法填空题（每空2分，共8分）假设待排序的n个元素已存放在顺序表R1Rn中，排序码字段名是key。下面的算法用于对顺序表进行归并排序，请在空内填入适当内容，将算法补充完整。Void mergesort(list R, list S, int i, int j)Int a,b,c,k; If (Ij) K=(i+j)/2;mergesort(R,S,i,k);mergesort(R,S,k+1,j);(1)_While (a=k)&(b=j) If (Ra.key=Rb.key) Sc=Ra; a+; Else (2)_ c+;(3)_ While (b=j) Sc=

18、Rb; b+; c+; (4)_六算法设计题（每小题12分，共24分）1.假设head是某个带头结点单链表的表头指针，每个结点数值字段的类型为整型。写一个算法，从该链表中删除一个值最大的结点，并将该结点的值存入表头结点的数值字段。2.如果一个十进制正整数首位数字不为零，而且从左往右读和从右往读都一样，则称其为回文数。对一个n位的正整数x，反复执行下列操作，有可能得到一个回文数：（1）生成一个位数和x相同的正整数y，其中yi=xn-i+1,i=1,2,3;（2）将y累加到x中。如对于正整数87，按上述方法重复4次后，将得到回文数4884：87+78=165 165+561=726 726+627

19、=1353 1353+3531=4884写一个按上述方法求回文数的算法。要求：x的初始值从键盘输入，其位数最多允许10位。如果得到回文数，就输出这个数，并输出上述步骤重复执行的次数，如果上述步骤重复了30次还得不到回文数，则放弃。数据结构模拟试题三一判断题（每小题1 分，共10分）1. 逻辑结构不同的数据，要采用不同的存储方法来存储。2. 单链表中的结点只有后继，没有前驱。3. 栈和队列具有相同的逻辑特性。4. 二叉树中结点之间的相互关系不能用二元组来表示。5. 关键路径是由权值最大的边构成的。6. 在表示矩阵的三元组顺序表中，各元素的排列顺序与矩阵元素值的大小无关。7. 在广义表中，每个原子

20、必须是单个字符。8. 在平衡二叉排序树中，每个结点的平衡因子值是相等的。9. 只有在线性表的初始状态为逆序排列的情况下，起泡排序过程中，元素的移动次数才会达到最大值。10. 在B+树上可以进行顺序查找。二填空题（每空1分，共10分）1. 若用不带表头结点的单链表来表示链接队列，则只有在_情况下，插入操作既要修改队尾指针的值，也要修改队头指针的值;只有在_情况下，删除操作仅需修改队首指针的值，不需修改队尾指针的值。2. 无向图中边的数目等于邻接矩阵中_。3. 在各元素查找概率相等的情况下，在含有12个元素的二叉排序树上查找其中一个元素，元素间的平均比较次数至少是_次，至多是_次。4. 对12个元

21、素进行快速排序，排序码的比较次数最多是_次。5. 对B+树来说，若某个非根分支结点中有6个关键字，则在它的某个孩子结点中至少有_个关键字，至多有_个关键字。6. 如果在根结点中要查到要找的关键字，则对于B-树来说，下一步应该_，而对于B+树来说，下一步应该_。三单选题（每题2分，共20分）1.线性结构采用链式存储，_。A对插入、删除结点的操作较为有利 B不利于进行顺序访问C逻辑上相邻的结点在存储器中也相邻 D可以用一些不连续的存储区域来存放一个结点2. 某算法的时间复杂度为O（2n），表明该算法的_。A执行时间与2n成正比 B执行时间等于2nC问题规模是2n D问题规模与2n成正比3. 在长度

22、为n的_上，删除最后一个元素，其算法的时间复杂度是O(n)。A只有表头指针的循环双向链表 B只有表头指针的非循环双向链表C只有表尾指针的非循环双向链表 D. 只有表尾指针的循环双向链表4. 在4个元素的进栈序列给定以后，由这4个元素构成的可能出栈序列共有_种。A14 B.16 C.17 D.245. 在任何一棵二叉树中，如果结点a有左孩子b、右孩子c，则在结点的前序序列、中序序列、后序序列中，_。A结点b一定在a的前面 B结点a一定在结点c的前面 C结点b一定在结点c的前面 D结点a一定在结点b的前面6.若二叉树中结点的中序序列是abcdef，则结点的前序序列不可能是_。Adbacef B.

23、acbedf C.efbacd D. bafdce 7. 对稀疏矩阵采用压缩存储，其优点之一是可以_。A减少非零元素的存储空间 B不减少访问非零元素所需时间 C减少矩阵的存储空间 D降低非零元素间逻辑关系的复杂程度8. 设待查找元素关键字的值是47，且已存入变量k中，如果在查找过程中，和k进行比较的关键字值依次是82,72,36,84,47，则所采用的查找方法可能是_。A顺序查找 B分块查找 C折半查找 D平衡二叉排序树查找9在线性表中元素很多且各元素逆序排列的情况下，执行_排序，元素的移动次数最少。A直接插入 B起泡 C简单选择 D折半插入10. 8阶方阵，每个元素占1个单元，按行优先顺序存

24、储，起始地址为100，存储地址为135的那个元素是矩阵中每5行第_列的元素。A2 B3 C. 4 D. 5四图表题（每小题4分，共8分）1.用h(x)=x mod 7作为散列函数，用线性探测法处理冲突，所建立的散列表如下图所示，请将关键字17，27依次填入表中。 0 1 2 3 4 5 6HT151045202.二叉树的表态二叉链表存储结构如下图所示。请给这棵二叉树加上中序线索。 1 2 3 4 5 6 7 8 LlinkDatarlink23050000abcdefgh740600801Root 五算法填表题（10分）在下面的表格中给出一些语句，每个语句都有编号。要求利用这些语句设计一个完整

25、的算法，该算法可对顺序表R1Rn进行选择排序。请按所选语句在算法中出现的先后顺序，将其编号填入空内。1Void sort(int i)2Sort(i+1);3If (i=k)33223245643123456789223图14If (i1)6If (ki)7 If (RjRk)8If (RjRk)9For (j=i+1;j=n;j+)10For (j=I;jnext=s-next，其二是（ ）。3对一般树和森林的后序遍历序列的次序与对应的二叉树的（ ）遍历次序相同。4设二维数组A10.20,5.10按行优先存储，每个元素占4个单元，A10,5的地址为160，则A15,10的地址为（ ）。5线性

26、结构反映结点间的逻辑关系是（ ）的，非线性结构反映结点间的逻辑关系是（ ）的。6赫夫曼树是带权路径长度（ ）的二叉树。7前序为abc且后序为cba的二叉树共有（ ）棵。8已知完全二叉树的高度为8，第7层有10个叶子结点，则二叉树的总结点数至少是（ ）。9已知二叉树有50个叶子结点，且仅有一个孩子的结点数为30，则总结点数为（ ）。10具有m个叶子结点的赫夫曼树共有（ ）个结点。11从一棵二叉树的前序序列和（ ）可唯一确定这棵二叉树。设某二叉树的后序遍历为ABKCBPM，则可知该二叉树的根为（ ）。12设广义表C=(x,(a,b),(x,(a,b),y),则C的长度为（ ），深度为（ ）。13设

27、有一稠密图G，则G采用（ ）存储较省空间。14在插入和选择排序中，若初始数据基本正序，则选用（ ）；若初始数据基本反序，则选用（ ）。15有n结点的二叉链表中，空指针域有（ ）个；利用这些空指针域，存放指向结点在中序次序下的前趋或后继的指针，这种附加的指针称为（ ）。三、（10分）已知一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，Nm个度为m的结点，问该树中有多少个叶子结点。请写出推导过程。四、（15分）给定字母a,b,c,d,e的使用频率为0.09,0.17,0.2,0.23, 0.31。设计以该权值为基础的赫夫曼树，并给出赫夫曼编码。五、（15分）设散列表的长度为13，散列函数

28、为H(K)=K%13，给定的关键字序列为：19，14，23，01，68，20，84，27，55，11，10，79。试画出用线性探测再散列解决冲突时所构成的散列表。并求等概率情况下这种方法查找成功和查找不成功时的平均查找长度。六、（15分）已知奇偶交换排序如下所述：第一趟对序列中所有奇数项i扫描，将ai和ai+1进行比较；第二趟对序列中所有偶数项i扫描，将ai和ai+1进行比较。每次比较时若 aiai+1，则将两者交换。第三趟对所有奇数项，第四趟对所有偶数项，如此重复，直至整个序列有序。1) 写出奇偶交换排序算法，设待排序的n个元素存放在数组a1.n 中。2) 说明你的排序方法的结束条件3) 若

29、待排序的初始序列已按关键字从小到大有序，则关键字的比较次数是多少？七、（10分）已知长度为n的线性表A采用顺序存储结构，并且元素按值大小非递减排列，下面的算法删除线性表中多余的值相同的元素。请在算法中空白处填入适当内容，使之能够正常工作。void DEL(int An) / 设A1An存放着n个元素 int i=1;while (1) do if (Ai!=Ai+1) i+; else /查找满足条件的元素 for (2) Aj-1=Aj;/删除第i+1个元素（满足条件的元素） (3) /修改线性表的长度 八、（15分）设计算法， 已知一棵以二叉链表存储的二叉树，root指向根结点，p指向二叉

30、树中任一结点，编写算法求从根结点到p所指结点之间的路径（要求输出该路径上每个结点的数据）。数据结构模拟试题五一、( 共34分，每题2分)单项选择题1、在非空循环双链表中q所指的结点前插入一个由p所指结点的过程依次为：p-next=q；p-prior=q-prior；q-prior=p；（ ）；Aq-next=p Bq-prior-next=p Cp-prior-next=pDp-next-prior=p E以上答案都不对2、已知有向图G=(V,E)，其中V=v1,v2,v3,v4,v5,v6,v7，E=，G的拓扑序列是（ ）。Av1,v3,v4,v6,v2,v5,v7 Bv1,v3,v2,v6

31、,v4,v5,v7 Cv1,v3,v4,v5,v2,v6,v7 Dv1,v2,v5,v3,v4,v6,v7 E以上答案都不对3、每个存储结点只含有一个数据元素，存储结点均匀地存放在连续的存储空间，使用函数值对应结点的存储位置，该存储方式是（ ）存储方式A 顺序 B链接 C索引 D散列 E以上答案都不对4、对于单链表形式的队列，队空的条件是（ ）AFRnilBFRCFnil且RnilDRF1E以上答案都不对5、采用邻接表存储的图的深度优先遍历算法类似于树的（ ）。A 中根遍历 B先根遍历 C后根遍历 D按层次遍历E以上答案都不对6、对于序列(49,38,65,97,76,13,27,50)按由小

32、到大进行排序，（ ）是初始步长d=4的希尔排序法第一趟的结果。A 49,76,65,13,27,50,97,38B 13,27,38,49,50,65,76,97C 97,76,65,50,49,38,27,13D 49,13,27,50,76,38,65,97E以上答案都不对7、在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（ ）。AO（n）BO（1） CO（n2） DO（log2n）E以上答案都不对8、设n阶方阵是一个上三角矩阵，则需存储的元素个数为（ ）。An Bn*n Cn*n/2 Dn(n+1)/2 E以上答案都不对9、树中所有结点的度等于所有结点数加（ ）。A0 B1

33、 C1 D2 E以上答案都不对10、如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（ ）方法最快。A起泡排序 B快速排序 C堆排序 D直接选择排序E以上答案都不对11、循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为（ ）。A(rear-front+m) mod m Brear-front+1 Crear-front-1 Drear-front E以上答案都不对12、若线性表最常用的运算是查找第i个元素及其前驱的值，则采用（ ）存储方式节省时间。A单链表 B双链表 C单循环连表 D顺序表 E以上答案都不对13、树最适合用来表示（ ）A有序数据元素 B无序数据元素