数据结构试题

《数据结构试题》由会员分享，可在线阅读，更多相关《数据结构试题（12页珍藏版）》请在装配图网上搜索。

1、数据结构试题一 选择题（从下列答案选项中选出一个正确答案，每小题2分)1. 线性表就是顺序表，这种说法（）。A正确B错误2. 若已知一个栈的入栈序列是1, 2, 3, 4, 5，不可能得到的输出序列是（ ）。A2,3,4,1,5 B 5,4,1,3,2 C2,3,1,4,5 D1,5,4,3,23. 串的逻辑结构与（）的逻辑结构不同。A. 栈B. 队列C. 树D. 线性表4. 如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（）A. 正确 B. 错误5. 设有两个串P和Q，求Q在P中首次出现的位置的操作称为（ ）。A.连接B.模式匹配C.求子串D.求串长6. 已知模式串t=“ab

2、caabbcabcaabdab”，该模式串的next数组值为（）。A. -1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1B. 0，1，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1C. -1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，7，1，D. -1，0，0，0，1，1，2，3，0，1，2，3，4，5，6，0，17. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。A. 13B. 33C. 18D. 408. 若采用三元组压缩技术存储稀疏矩阵，只要把每

3、个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法（ ）。A. 正确B. 错误9. 树形结构的特点是：一个结点可以有（）。 A、多个直接前趋 B、多个直接后继 C、多个前趋 D、一个后继10. 在一棵高度为h的满三叉树中，结点总数为（） A、3h-1 B、(3h-1)/2 C、(3h-1)/3 D、3h11. 设森林T中有4棵树，结点个数依次为n1, n2, n3, n4，当把森林T转换成一棵二叉树后，二叉树根结点的右子树上有（ ）个结点。An1-1Bn1Cn1+n2+n3Dn2+n3+n412. 任何一个无向连通图的最小生成树（）。A只有一颗B有一颗或多棵C一定有多棵D可能不存

4、在13. 一个无向连通图的生成树是含有该连通图的全部顶点的（）。 A、极小连通子图 B、极小子图 C、极大连通子图 D、极大子图14. 在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零，这种说法( )。A. 正确B. 错误15. 对于关键字序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为（）的结点开始。A100B60C12D1516. 下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlog2n）的是（） A、堆排序 B、冒泡排序 C、直接选择排序 D、快速排序17. 下列排序算法中，（）排序在某趟结束后不

5、一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆18. 在平衡二叉树中插入一个结点后造成了不平衡，设最小不平衡子树之根为A,并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（ ）型调整使其平衡。ALLBLRCRLDRR 19. 常采用下面几种方式解决散列法中出现的冲突问题（）。A数字分析法、除余法、平方取中法 B数字分析法、除余法、线性探测法 C数字分析法、线性探测法、多重散列法 D线性探测法、多重散列法、链地址法二 填空题（每空2分）1. 以下程序段的时间复杂度是_ ，其中n为正整数。void fun(int n)int i=1,k=100;while(

6、in) k=k+1; i+=2;2. 对于长度为n的顺序表，插入或删除元素的平均时间复杂度为_。对于顺序栈或顺序队列，插入或删除元素的时间复杂度为_。3. 一个nn的对称矩阵若采用压缩存储，需要存储_个元素。4. 设栈S和队列Q的初始状态为空，元素a，b，c，d，e，f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序为b，d，c，f，e，a，则栈S的容量至少应该是_。5. 判定一个环形队列qu（最多元素为MaxSize）为空的条件是_，判定环形队列qu为满队列的条件是_ _ _。6. 已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为_。7. 取出广义表A=(

7、x,y,z),(a,b,c,d)中原子b的函数是_。8. 无向图中的极大连通子图称为该无向图的_。9. 在有序表A1.20中，采用二分查找算法查找元素值等于A12的元素，所比较过的元素的下标依次为_。10. 一个深度为k的，具有最少结点的完全二叉树按层次（同层次从左到右）用自然数依次对结点编号，则编号最小的叶子的序号是_；三 问答题：1. 在单链表中设置头结点的作用是什么？2. 表示一个有1000个顶点、1000条边的有向图的邻接矩阵有多少个矩阵元素?是否稀疏矩阵？3. （已知二叉树的中序序列为DCEFBHGAKJLIM, 后序序列为DFECHGBKLJMIA，画出该二叉树。4. 已知如下一个

8、无向图，要求；（1） 画出该无向图的邻接表；（2） 基于你给出的邻接表，画出以顶点A为出发点遍历图所得到的DFS序列。FDCBEGA5. 下图是用邻接表存储的图，画出此图，并画出由顶点C出发按深度优先遍历该图所得到的DFS生成树。6. 已知关键字的输入序列如下：（46，88，45，39，70，58，101，10，66，34），画出按关键字的输入次序生成的一棵二叉排序树，并求在等概率情况下查找成功的平均查找长度。7. 设有一组关键字序列：（29，18，25，47，58，12，51，10）要按照关键字值递增的次序进行排序。（1）若采用初始增量为4的希尔排序，写出第一趟排序的结果：（2）若采用以第一

9、个元素为基准元素的快速排序法，写出第一趟排序的结果：8. 以下面的数据作为叶子结点的权值构造一颗哈夫曼树，并计算带权路径长度WPL。5，6，7，8，9，10，15，18，229. 已知散列地址空间为至14，散列函数H(K)=K%13，采用线性探查法处理冲突，将下列关键字序列依次存入散列表中，并求出在等概率情况下查找成功的平均查找长度ASL。（240，29，345，189，100，20，21，35，3，208，78，99，45，350） 四 算法填空：请仔细阅读下面的堆排序算法：n个待排序的学生成绩记录存放在一维数组R1.n中，结点类型及相关定义如下： #define n 200 typedef

10、 struct stud int num;char name20;float score; rectype; rectype Rn+1;要求按成绩(score)由高到低排列学生记录，将以下堆排序算法补充完整，使它们能正确工作。SIFT(R, i, m) /在数组Ri.Rm构成的完全二叉树中，已知Ri的左、右子树都是堆，rectype R ; /现将Ri为根的子树也调整为堆int i, m;int j; rectype temp; temp=Ri; j=2*i; while(j=m) if ( (j=1; i-) _ /建初始堆 for(i=n; i=1; i-) /进行n-1趟堆排序 temp

11、=R1; R1=Ri; Ri=temp; SIFT(_); /重建堆 /for /HEAPSORT五 算法设计题（算法中请加上必要的语句注释）数据结构试题一、判断题：（共10分，每题1分）1、深度为h的非空二叉树的第i层最多有2i-1 个结点。（ ）2、在完全二叉树中,若某结点无左孩子,则它必是叶结点。（ ）3、一组权值，可以唯一构造出一棵赫夫曼树。( )4、在n个结点的无向图中,若边数多于n-1,则该图必是连通图。（ ）5、对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶点为起点的出边数目，该顶点的度等于其入度和出度之和。（ ）6、无向图的邻接矩阵是对称的，有

12、向图的邻接矩阵是不对称的。（ ）7、折半查找只适用于有序表，包括有序的顺序表和有序的链表。（ ）8、一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减少冲突。（ ）9、在初始数据为逆序时，冒泡排序所执行的比较次数最多。（ ）10、希尔排序在效率上较直接插入排序有较大的改进。但是不稳定的。（ ）二、填空题：（共20分，每空2分）1、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个_,，且存在一条从根到该结点的_。2、 三个结点的二叉树，最多有_种形状。3、 任何一棵二叉树，若n0，n2分别是度为0，2的结点的个数，则n0和n2的关系为_ _ _。4、设有

13、10个值，构成赫夫曼树，则该赫夫曼树共有_个结点。5、在一个无向图中，所有顶点的度数之和等于所有边数的_倍。6、一个连通图的生成树是该图的_连通子图。若这个连通图有n个顶点, 则它的生成树有_条边。7、如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是_。8、将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫_。三、选择题：（共20分，每题2分）1、设x是一棵树，x是对应于x的二叉树，则x的后序遍历和x的_序遍历相同A.先序 B.中序 C.后序 D.都不是2、设有100个元素，用折半查找法进行查找时，在查找成功的情况下，最大比较次数是_ 。A.1

14、00 B.50 C.99 D.73、设散列表长m=14,散列函数H（K）=K11，已知表中已有4个结点：r(15)=4; r(38)=5; r(61)=6;r(84)=7，其他地址为空，如用线性探查法处理冲突，关键字为49的结点地址是_。A.8 B.3 C.5 D.94、在含有n个项点有e条边的无向图的邻接矩阵中，零元素的个数为_。A.e B.2e C.n2-e D.n2-2e5、图的深度优先遍历类似于树的_。A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历6、下面关于图的存储的叙述中，哪一个是正确的。 _A 用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关B 用邻

15、接矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关8、用某种排序方法对关键字序列（23，72，21，47，15，27，59，35，20）进行排序时，前三趟的结果情况如下_： 23，21，47，15，27，59，35，20，72 21，23，15，27，47，35，20，59，72 21，15，23，27，35，20，47，59，72则所采用的排序方法是_A.选择排序 B.起泡排序C.归并排序 D.快速排序9、将一棵有40个结点的完全二叉树从

16、上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为15的结点的左孩子的编号为_。A.30 B.31 C.16 D.3210、如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是_A.有向完全图 B.连通图C.强连通图D.有向无环图四、应用题：（共28分，每题4分）1、将下图转换为二叉树，对转换后的二叉树进行先序、中序、后序遍历序列。ABCDEFGJ2、什么是赫夫曼（Huffman）树？有一组数值14、21、32、15、28，画出赫夫曼树，并计算其WPL。3、设一个有向图为G=(V,E),其中V=v1,v2,v3,v4，E=, ,画出该有向图，画出相应邻接表，写出从顶点v1出发

17、进行深度优先和广度优先搜索得到的顶点序列。4、用序列（46，88，45，39，70，58，101，10，66，34）建立一个平衡的二叉排序树，画出该树。5、已知一组键值序列为(41，66，73，52，40，37，65，43)，试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。6、已知一组关键字为（26，36，41，38，44，15，68，12，06，51，25），用线性探查法解决冲突构造这组关键字的哈希表。表长取13，哈希函数H(key)=key MOD 13。7、已知一棵三阶的B-树如下图所示，假定依次插入关键字 50，83请画出插入个结点后树的情况：五阅读算法，写出运行结果设队列Q=(1,2,3,4,5,6,7),其中7为队尾元素。请写出调用f1(&Q)后队列Q的状态。 void f1(SqQueue *&q) ElemType x;SqStack st; InitStack(&st);while(!QueueEmpty(q)deQueue(q,x); Push(&st, x);while(!StackEmpty(&st)Pop(&st, x); enQueue(q,x);