《数据结构与算法》期末练习题(含答案).pdf

《数据结构与算法》期末练习 一 选择题 1．以下与数据的存储结构无关的术语是（ D ）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 2. 算法的时间复杂度取决于（ A ） A．问题的规模 B. 待处理数据的初态 C. A 和 B D. 计算机 cpu 3. 一个栈的输入序列为 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 4. 有关静态链表的叙述： (1) 静态链表既有顺序存储的优点，又有 动态链表的优点。 所以，它存取表中第 i 个元素的时间与 i 无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了， 以后不 能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需 做元素的移动。以上错误的是（ B ） A ．（1），（2 ） B ．（1） C ．（1），（2）,(3) D. （2） 5．对于有 n 个结点的二叉树 , 其高度为（ D ） 2 2 2 A．nlog n B ．log n C ．? log n? |+1 D．不 确定 6．从下列有关树的叙述中 , 选出正确的叙述（ C ） A．二叉树中每个结点有两个子结点 , 而树无此限制 , 因此二叉树是树的特殊情况。 B．当 K≥1 时高度为 K 的二叉树至多有 2k-1 个结点。 C．哈夫曼树是带权路径最短的树 , 路径上权值较大的结点离根较近。 D．在二叉树中插入结点 , 该二叉树便不再是二叉树。 7．设无向图的顶点个数为 n，则该图最多有（ B ）条边。 A．n-1 B ．n(n-1)/2 C ． n(n+1)/2 D ．0 2 E．n 1 2 3 4 5 6 7 1 2 8．已知有向图 G=(V,E) ，其中 V={V ,V ,V ,V ,V ,V ,V } ，E={V ,V , V1,V3, V1 ,V4 , V2 ,V5, V3 ,V5, V3,V6 , V4 ,V6, V5,V7, V6,V7},G 的拓扑序列是（ A ）。 A．V1,V3,V 4 ,V6 ,V2 ,V5 ,V7 B ．V1 ,V3,V2 ,V6 ,V4 ,V5 ,V7 1 3 4 5 2 6 7 1 2 5 3 4 6 7 C．V ,V ,V ,V ,V ,V ,V D ．V ,V ,V ,V ,V ,V ,V 9．下列排序算法中，其中（ D ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 希尔排序，归并排序 D. 归并排序，冒泡排序 10．对一组数据（ 84，47，25，1