16春地大《数据结构(新)》在线作业一.doc

地大《数据结构(新)》在线作业一 一、单选题（共 25 道试题，共 100 分。） 1. 非空的循环单链表h的尾节点（由p所指向）满足（）。 . p-nxt=NULL . p=NULL . p-nxt=h . p=h 正确答案： 2. 计算机的算法必须具备输入，输出和（）五个特性。 . 可行性，可移植性和可扩充性 . 可行性，确定性和有穷性 . 确定性，有穷性和稳定性 . 易读性，稳定性和安全性 正确答案： 3. 设有向图有n个顶点和条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ ）。 . O（nlog2） . O（n+） . O(n*) . O(n*n) 正确答案： 4. 如果一个树中，结点有3个兄弟，而且为的双亲，则的度为（ ）。 . 1 . 3 . 4 . 5 正确答案： 5. 如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。下列选项中，（ ）就是不稳定的排序方法。 . 起泡排序 . 归并排序 . 直接插入法排序 . 简单选择排序 正确答案： 6. 深度为5的二叉树至多有（）个节点。 . 16 . 32 . 31 . 10 正确答案： 7. 顺序表中逻辑上相邻的节点其物理位置也（ ）。 . 一定相邻 . 不必相邻 . 按某种规律排列 . 无要求 正确答案： 8. 若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（ ）方法比较次数最少。 . 直接插入排序 . 快速排序 . 归并排序 . 直接选择排序 正确答案： 9. 设循环队列Q[1..N-1]的头尾指针为F，R，当插入元素时尾指针R加1，头指针F总是指在队列中第一个元素的前一个位置，则队列中元素计数为（ ）。 . R-F . N-（R-F） . （R-F+N）%N . （F-R+N）%N 正确答案： 10. 对n个记录的文件进行堆排序，最坏情况下的执行时间为( )。 . O(log2n) . O(nlogn) . O(n) . O(n*n) 正确答案： 11. 设有1000个元素，用折半查找时，最大比较次数是（ ）。 . 1 . 7 . 10 . 25 正确答案： 12. 邻接表是图的一种（）。 . 顺序存储结构 . 链式存储结构 . 索引存储结构 . 列存储结构 正确答案： 13. 对某二叉树进行前序遍历的结果为F，中序遍历的结果为F，则后序遍历的结果为（ ）。 . F . F . F . F 正确答案： 14. 若给定的关键字集合为{20，15，14，18，21，36，40，10}，一趟快速排序结束时，键值的排列为()。 . 10，15，14，18，20，36，40，21 . 10，15，14，18，20，40，36，21 . 10，15，14，20，18，40，36，21 . 15，10，14，18，20，36，40，21 正确答案： 15. 若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用()存储方式最节省时间。 . 顺序表 . 单链表 . 双链表 . 单循环链表 正确答案： 16. 判定一个顺序栈（最多元素为m个）为空的条件是（ ）。 . top＝＝0 . top＝＝m . top!＝0 . top!＝m 正确答案： 17. 设F是一个森林，是由F转换得到的二叉树，F中有n个非叶结点，则中右指针域为空的结点有（ ）个。 . n-1 . n . n+1 . n+2 正确答案： 18. 设无向图的顶点个数为n，则该图最多有（ ）条边。 . n-1 . n(n-1)/2 . n(n+1)/2 . 0 正确答案： 19. 设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（ ）。 . 3，2，5，6，4，1 . 1，5，4，6，2，3 . 2，4，3，5，1，6 . 4，5，3，6，2，1 正确答案： 20. 广义表（（）,）的表头是（ ）。 . . . () . (()) 正确答案： 21. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（ ）排序. . 插入 . 交换 . 选择 . 归并 正确答案： 22. 某二叉树结点的前序序列为、、、、、G、F，中序遍历为、、、、、F、G。 该二叉树结点的后序序列为 ()。 . ,,,,F,G, . ,,,F,,G, . ,G,F,,,, . ,G,,,,F, 正确答案： 23. 链表不具有的特点是（）。 . 不必事先估计存储空间 . 可随机访问任一元素 . 插入删除不需要移动元素 . 所需空间与线性表长度成正比 正确答案： 24. 按照二叉树的定义，具有3个结点的二叉树有（ ）种。 . 3 . 4 . 5 . 6 正