数据结构试题（华南理工大学）数据结构试题.doc

《数据结构》试题 选择题（从下列答案选项中选出一个正确答案，每小题2分) 线性表就是顺序表，这种说法（ B ）。 A．正确 B．错误 若已知一个栈的入栈序列是1, 2, 3, 4, 5，不可能得到的输出序列是（ B ）。 A．2,3,4,1,5? B． 5,4,1,3,2 ? C．2,3,1,4,5 D．1,5,4,3,2 串的逻辑结构与（ C ）的逻辑结构不同。 栈 队列 树 线性表 如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（B） 正确 错误 设有两个串P和Q，求Q在P中首次出现的位置的操作称为（ B ）。 A.连接 B.模式匹配 C.求子串 D.求串长 已知模式串t=“abcaabbcabcaabdab”，该模式串的next数组值为（ A ）。 -1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1 0，1，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1 -1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，7，1， -1，0，0，0，1，1，2，3，0，1，2，3，4，5，6，0，1 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（ B ）。 13 33 18 40 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法（ B ）。 正确 错误 树形结构的特点是：一个结点可以有（B）。 A、多个直接前趋 B、多个直接后继 C、多个前趋 D、一个后继 在一棵高度为h的满三叉树中，结点总数为（B） A、3h-1 B、(3h-1)/2 C、(3h-1)/3 D、3h 设森林T中有4棵树，结点个数依次为n1, n2, n3, n4，当把森林T转换成一棵二叉树后，二叉树根结点的右子树上有（ C ）个结点。 A．n1-1 B．n1 C．n1+n2+n3 D．n2+n3+n4 任何一个无向连通图的最小生成树（ C ）。 A．只有一颗 B．有一颗或多棵 C．一定有多棵 D．可能不存在 一个无向连通图的生成树是含有该连通图的全部顶点的（A）。 A、极小连通子图 B、极小子图 C、极大连通子图 D、极大子图 在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为零，这种说法(? ??B )。 正确 错误 对于关键字序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为（ B ）的结点开始。 A．100 B．60 C．12 D．15 下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlog2n）的是（A） A、堆排序 B、冒泡排序 C、直接选择排序 D、快速排序 下列排序算法中，（C）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 在平衡二叉树中插入一个结点后造成了不平衡，设最小不平衡子树之根为A,并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作（ C ）型调整使其平衡。 A．LL B．LR C．RL D．RR 常采用下面几种方式解决散列法中出现的冲突问题（ A ）。 A．数字分析法、除余法、平方取中法 B．数字分析法、除余法、线性探测法 C．数字分析法、线性探测法、多重散列法 D．线性探测法、多重散列法、链地址法 填空题（每空2分） 以下程序段的时间复杂度是_____________ ，其中n为正整数。 void fun(int n) { int i=1,k=100; while(in) { k=k+1; i+=2; } } 对于长度为n的顺序表，插入或删除元素的平均时间复杂度为_________________。对于顺序栈或顺序队列，插入或删除元素的时间复杂度为_______________。 一个n×n的对称矩阵若采用压缩存储，需要存储___________________________个元素。 设栈S和队列Q的初始状态为空，元素a，b，c，d，e，f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序为b，d，c，f，e，a，则栈S的容量至少应该是________________。 判定一个环形队列qu（最多元素为MaxSize）为空的条件是__________________________________________，判定环形队列qu为满队列的