数据结构期末复习思考题.docVIP

《数据结构》复习思考题 一、基础题 题目 答案 数据结构研究的主要内容是：非数值计算程序设计中数据的 （ ① ）和（ ② ） 以及它们之间（ ③ ）方法。 ①A.操作对象 B.计算方法 C.逻辑结构 D.数据映像 ②A.计算方法 B.数据映像 C.分类方法 D.存储结构 ③A.链接与关系 B.关系与算法 C.数据映像 D.计算方法 ①C ②D ③B 一棵含18个结点的二叉树的高度至少为( ) A.3 B.4 C.5 D.6 C 算法分析的主要目的是对（ ① ）和（ ② ）两个方面进行评价。 ① A. 数据存储的合理性 B. 算法选择的简单性 C. 算法的空间复杂度 D. 算法过程的逻辑性 ② A. 算法的时间复杂度 B. 算法选择的简单性 C. 算法的空间复杂度 D. 算法的正确性与简单性 ①C ②A 具有频繁插入删除操作的线性表，应采用（ ）存储结构效率较高。 A. 矩阵 B. 链表 C. 数组 D. 结构 B 无向图中一个顶点的度是指图中( ) A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数 C.通过该顶点的回路数 D.与该顶点连通的顶点数 B 下列程序段的时间复杂度数量级为__________。 k=1; while(k=n) { k=k*3; } O(log3n) 从算法设计的简单性、时间复杂性和空间复杂性等多种角度考虑，你认为实现图深度优先遍历过程的控制，采用（ ）作为算法辅助存储结构最合适。 A. 队列 B. 堆栈 C. 单向环形链表 D. 双向循环链表 B 一个栈的数据入栈顺序为：ABCDE，指出不可能的出栈序列为（ ）。 A. EDCBA B.DECBA C.DCEAB D.ABCDE C head为无头结点单向向后链表，判断head为空表的判定条件是（） A．head= =NULL B．head=0 C．head-→data= =0 D．head→next= =NULL A 循环队列定义为：int A[m]; 使用A[0]至A[m-1] 作为数据存储区，已知头尾指针分别为front和rear，表明队列中有效数据元素总数（一个正整数）的表达式是（ ）。 A.（rear-front+m）%m B. rear – front +1 C. rear – front -1 D. (rear – front)%m A 带头结点的单链表head为空表的判定条件是（ ）。 A. head-next!=NULL B. head!=NULL C. head-next==NULL D. head==NULL C 一堆栈数据进栈的次序为：1，2，3，4，5确定下述结果中错误的是（）。 A. 5,4,3,2,1 B.1,2,3,4,5 C. 2,3,1,5,4 D.3,1,2,4,5 D 根据数据元素的关键字能够直接确定记录素存储地址的方法称为（ ）。 A．链接存储方法 B．顺序存储方法 C．散列存储方法 D．索引存储方法 C 算法分析的目的是（ ）。 A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 B 在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。 A．插入 B．删除 C．排序 D．定位 D 在按层次遍历二叉树的算法中，借助（ ）辅助数据结构比较合适。 A．队列 B．栈 C．线性表 D．有序表 A 在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是( ) A.快速排序 B.堆排序 C.归并排序 D.基数排序 B 若用数组s[0..n-1]作为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作。为这两个栈选择空间利用的最佳方案，问s1和s2栈顶指针的初值分别为（ ）能更好地利用提供的存储空间？ A．1和n+1 B．1和n/2 C．－1和n D．－1和n+1 C 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ ）。 A．