资源描述:
《【精品】数据结构复习思考题.doc》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、《数据结构》复习思考题一.基础题题目答案数据结构研究的主要内容是:非数值计算程序设计中数据的(①)和(②)以及它们Z间(③)方法。®c①A.操作对象B.计算方法C.逻辑结构D.数据映像②D②A.计算方法B.数据映像C.分类方法D.存储结构③B③A.链接与关系B.关系与算法C.数据映像D.计算方法一棵含18个结点的二叉树的高度至少为()CA3B.4C.5D.6算法分析的主要目的是对(①)和(②)两个方面进行评价。®c①A.数据存储的合理性B.算法选择的简单性②AC.算法的空间复杂度D.算法过程的逻辑性②A.算法的时间复杂度B.算法选
2、择的简单性C.算法的空间复杂度D.算法的正确性与简单性具有频繁插入删除操作的线性表,应采用()存储结构效率较高。BA.矩阵B.链表C.数组D.结构无1诃图中一个顶点的度是指图中()BA.通过该顶点的简单路径数B.与该顶点相邻接的顶点数C.通过该顶点的冋路数D.与该顶点连通的顶点数卜列程序段的时间复杂度数量级'人1。O(log3n)k=l;while(k<=n){k=k*3;}从算法设计的简单性、时间复杂性和空间复杂性等多种角度考虑,你认为实现图深度优先遍历过程的控制,采用()作B为算法辅助存储结构最合适。A.队列B.堆栈C.单向环
3、形链表D.双向循环链表一个栈的数据入栈顺序为:ABCDE,指出不可能的出栈序列为()。A.EDCBAB.DECBAC.DCEABD.ABCDEC:head为无头结点单向向后链表,判断head为空表的判定条件是()A.head==NULLB.head=OC.head―data==0D.head—>next==NULLA循环队列定义为:intA[m];使用A[0]至A[m-1]作为数据存储区,已知头尾指针分别为front和rear,表明队列中有效数据元索总数(一个正整数)的表达式是()oA.(rear-front+m)%mB.rear
4、一front+1C.rear一front-1D・(rear一front)%mA带头结点的单链表head为空表的判定条件是()。A.hcad->ncxt!=NULLB.hcad!=NULLC.hcad->ncxt==NULLD.hcad==NULLC:一堆栈数据进栈的次序为:1,2,3,4,5确定下述结果中错误的是()。A.5,4,3,2,1B.1,2,3,4,5C.2,3,1,5,4D.3,1,2,4,5D根拯数拯元素的关键字能够宜接确定记录素存储地址的方法称为()。A.链接存储方法B.顺序存储方法C.散列存储方法D・索引存储方法
5、C算法分析的目的是()。A.辨别数拯结构的合理性B.评价算法的效率C.研究算法中输入与输出的关系D.鉴别算法的可读性B在线性表的下列运算中,不改变数据元索Z间结构关系的运算是()。A.插入B.删除C.排序D.定位D在按层次遍历二叉树的算法中,借助()辅助数据结构比较合适。A.队列B.栈C.线性表D.有序表A在下列排序方法中,平均时间性能为O(nlogn)H.空间性能最好的是()BA.快速排序B.堆排序C.归并排序D.幕数排序若用数组s[O..ml]作为两个栈si和s2的共用存储空间,忖仅当s[O.m・l]全满时,各栈才不能进行进栈
6、操作。为这两个栈选择空间利用的最佳方案,问si和s2栈顶指针的初值分别为()能更好地利用提供的存储空间?A.1和n+1B.1和n/2C.-1和nD.-1和n+1C:如果求一个连通图中以某个顶点为根的高度最小的生成树,应采用()。A.深度优先搜索算法B.广度优先搜索算法C.求最小生成树的prim算法D.拓扑排序算法B栈和队列都是()。A.限制存取位置的线性结构B.顺序存储的线性结构C.链式存储的线性结构D.限制存取位置的非线性结构A若用邻接矩阵表不个冇向图,则其中每列包含的"1”的个数为()。A.图中每个顶点的入度B.图中每个顶点的
7、出度C.图中弧的条数D.图中连通分量的数目B在一个带权连通图G中,权值最小的边一定包含在G的()中。A.最小生成树B.深度优先遍历树C.广度优先遍历树D.深度优先生成森林A如果在排序过程中,每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置,则该排序方法称为()oA.插入排序B.归并排序C.冒泡排序D.堆排序A题目答案对给定字符集和相应权重,构造Huffman树并确定每个字符的Huffman编答案:码,给huffman树的带权路径长度。树的逻辑结构:二、操作丿节点ETADU权重1012794编码:U:000(
8、3位)D:001(3位)e:01(2位)a:ll(2位)t:10(2位)给定数据序列:6,3,9,5,7,8,2,1,4,12,按要求完成下列题目。<1)构造排序二叉树,画出排序二叉树的逻辑结构;(2)给出该二叉树先序、中序和后序遍历的节点序列。树