数据结构导论复习卷

《数据结构导论复习卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构导论复习卷导读：就爱阅读网友为您分享以下“数据结构导论复习卷”的资讯，希望对您有所帮助，感谢您对92to.com的支持!《数据结构导论》复习综合卷一、选择题1．关于算法的描述，不正确的是（B）．．．A.算法最终必须由计算机程序实现B.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界C.健壮的算法不会因非法的输入数据而出现莫名其妙的状态D.算法的优劣与算法描述语言无关再添加两个元素后，rear和front的值分别为（B）9A.1和5B.2和4C.4和2D.5和13．数据的四种基本逻辑结构是指（D）。A．数组、链表、

2、树、图形结构B．线性表、链表、栈队列、数组广义表C．线性结构、链表、树、图形结构D．集合、线性结构、树、图形结构4．数据结构中，通常采用两种方法衡量算法的时间复杂性，即（D）。A．最大时间复杂性和最小时间复杂性B．最好时间复杂性和最坏时间复杂性C．部分时间复杂性和总体时间复杂性9D．平均时间复杂性和最坏时间复杂性5．下列关于线性表的叙述中，不正确的是（C）。A．线性表是n个结点的有穷序列B．线性表可以为空表C．线性表的每一个结点有且仅有一个前趋和一个后继D．线性表结点间的逻辑关系是1:1的联系6．在一个单链表中，若p所指结点不是

3、最后结点，则删除p所指结点的后继结点的正确操作是（C）。A．p=p->nextB．p->next=p->nextC．p->next=p->next->nextD．p->next=p7．栈和队列（C）。9A．共同之处在于二者都是先进先出的特殊的线性表B．共同之处在于二者都是先进后出的特殊的线性表C．共同之处在于二者都只允许在顶端执行删除操作D．没有共同之处8．一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功时的比

4、较次数为（C）A.1B.2C.4D.89．向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行的操作为（B）A.hs—>next=s；B.s—>next=hs；hs=s；C.s—>next=hs—>next；hs—>next=s；9D.s—>next=hs；hs=hs—>next；10．已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（B）A.4C.6B.5D.72．若用一个有6个单元的数组来实现循环队列，rear

5、和front的初值分别为0和3。则从队列中删除一个元素，11．二维数组A[5][6]采用按列为主序的存储方式，每个元素占3个存储单元，若A[0][0]的存储地址是100，则A[4][3]的存储地址是（D）。A．127B．142C．150D．15712．深度为k的二叉树至多有（C）。A．2k个结点B．2k-1个结点C．2k-1个结点9D．2k-1-1个结点13．对于如下图所示二叉树采用中根遍历，正确的遍历序列应为（D）。题8图A．ABCDEFB．ABECDFC．CDFBEAD．CBDAEF14．下面关于生成树的描述中，不正确的是（

6、A）。A．生成树是树的一种表现形式B．生成树一定是连通的C．生成树一定不含有环D．若生成树顶点个数为n，则其边数一定为n-1915．图的邻接表如图所示，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列是（题10图A．V1V2V3V4V5B．V1V2V3V5V4C．V1V4V3V5V2D．V1V3V4V5V216．用于外存储器的数据组织结构散列文件，主要适用于（B）。A．顺序存取B．随机存取C．索引存取D．以上三种都可以17．堆排序属于一种选择排序，其时间复杂性为（B）。A．O（1）B．O（nlog2n）C．O（n）D．

7、O（n2）918．下列排序方法中，属于不稳定的排序方法是（A）。A．直接选择排序法B．冒泡排序法C．基数排序法D．归并排序法19．下列查找方法中，不属于动态的查找方法是（D）。A．二叉排序树法B．平衡树法C．散列法D．斐波那契查找法20．要解决散列引起的冲突问题，常采用的方法有（D）。A．数字分析法、平方取中法B．数字分析法、线性探测法9C．二次探测法、平方取中法D．二次探测法、链地址法9