数据结构复习思考题.doc

《数据结构》复****思考题
一、基础题
题目
答案
数据结构研究的主要内容是:非数值计算程序设计中数据的( ①)和( ②) 以及它们之间( ③)方法。
①
②
③
①C
②D
③B
一棵含18个结点的二叉树的高度至少为( )

C
算法分析的主要目的是对( ①)和( ②)两个方面进行评价。
① A. 数据存储的合理性 B. 算法选择的简单性
C. 算法的空间复杂度 D. 算法过程的逻辑性
② A. 算法的时间复杂度 B. 算法选择的简单性
C. 算法的空间复杂度 D. 算法的正确性与简单性
①C
②A
具有频繁插入删除操作的线性表,应采用( )存储结构效率较高。
A. 矩阵 B. 链表 C. 数组 D. 结构
B
无向图中一个顶点的度是指图中( )


B
下列程序段的时间复杂度数量级为__________。
k=1;
while(k<=n)
{ k=k*3; }
O(log3n)
从算法设计的简单性、时间复杂性和空间复杂性等多种角度考虑,你认为实现图深度优先遍历过程的控制,采用( )作为算法辅助存储结构最合适。
B
A. 队列 B. 堆栈 C. 单向环形链表 D. 双向循环链表
一个栈的数据入栈顺序为:ABCDE,指出不可能的出栈序列为( )。
A. EDCBA
C
head为无头结点单向向后链表,判断head为空表的判定条件是()
= =NULL =0
-→data= =0 →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 ,2,3,4,5 C. 2,3,1,5,4 ,1,2,4,5
D
根据数据元素的关键字能够直接确定记录素存储地址的方法称为( )。


C
算法分析的目的是( )。


B
在线性表的下列运算中,不改变数据元素之间结构关系的运算是( )。

D
在按层次遍历二叉树的算法中,借助( )辅助数据结构比较合适。


A
在下列排序方法中,平均时间性能为O(nlogn)且空间性能最好的是( )
B

若用数组s[0..n-1]作为两个栈s1和s2的共用存储空间,且仅当s[0..n-1]全满时,各栈才不能进行进栈操作。为这两个栈选择空间利用的最佳方案,问s1和s2栈顶指针的初值分别为( )能更好地利用提供的存储空间?
+1
C.-1和n D.-1和n+1
C
如果求一个连通图中以某个顶点为根的高度最小的生成树,应采用( )。


B
栈和队列都是( )。


A
若用邻接矩阵表示一个有向图,则其中每一列包含的″1″的个数为( )。


B
在一个带权连通图G中,权值最小的边一定包含在G的( )中。

D