2016春北交《数据结构(专)》在线作业二.doc

北交《数据结构（专）》在线作业二 一、单选题（共 38 道试题，共 95 分。） 1. 设无向图的顶点个数为n，则该图最多有（）条边。 . n-1 . n(n-1)/2 . n(n+1)/2 . 0 正确答案： 2. 线性表是一个具有n个（）的有限序列。 . 表元素 . 字符 . 数据元素 . 数据项 正确答案： 3. 队列操作的原则是（ ）。 . 先进先出 . 后进先出 . 只能进行插入 . 只能进行删除 正确答案： 4. 某二叉树结点的前序序列为、、、、、G、F，中序遍历为、、、、、F、G。 该二叉树结点的后序序列为 ( )。 . ,,,,F,G, . ,,,F,,G, . ,G,F,,,, . ,G,,,,F, 正确答案： 5. 算法的时间复杂度是指（ ）。 . 执行算法程序所需要的时间 . 算法程序的长度 . 算法执行过程中所需要的基本运算次数 . 算法程序中的指令条数 正确答案： 6. 数组中，每个元素的长度为3个字节，行下标I 从1到8,列下标j从1到10，从首地址S开始连续存放在存储器内，存放该数组至少需要的单元数为（ ）。 . 80 . 100 . 240 . 270 正确答案： 7. 队列的删除操作是在（ ）进行。 . 队首 . 队尾 . 队前 . 队后 正确答案： 8. 当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ ）语句修改top指针。 . top++ . top=0 . top-- . top=N 正确答案： 9. 顺序表中逻辑上相邻的节点其物理位置也（ ）。 . 一定相邻 . 不必相邻 . 按某种规律排列 . 无要求 正确答案： 10. 带头节点的单链表 h 为空的判定条件（ ）。 . h=NULL . h-nxt=NULL . h-nxt=h . h!=h 正确答案： 11. 若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用( )存储方式最节省时间。 . 顺序表 . 单链表 . 双链表 . 单循环链表 正确答案： 12. 若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（ ）方法比较次数最少。 . 直接插入排序 . 快速排序 . 归并排序 . 直接选择排序 正确答案： 13. 串的长度是（ ）。 . 串中不同字符的个数 . 串中不同字母的个数 . 串中所含字符的个数且字符个数大于0 . 串中所含字符的个数 正确答案： 14. 下列关于栈的叙述正确的是（ ）。 . 栈是非线性结构 . 栈是一种树状结构 . 栈具有先进先出的特征 . 栈具有后进先出的特征 正确答案： 15. 设有向图有n个顶点和条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。 . O（nlog2） . O（n+） . O(n*) . O(n*n) 正确答案： 16. 由两个栈共享一个向量空间的好处是（ ）。 . 减少存取时间，降低下溢发生的机率 . 节省存储空间，降低上溢发生的机率 . 减少存取时间，降低上溢发生的机率 . 节省存储空间，降低下溢发生的机率 正确答案： 17. 从一棵_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（ ）。 . 原树高度加1 . 原树高度减1 . 原树高度 . 不确定 正确答案： 18. 队列的插入操作是在（ ）进行。 . 队首 . 队尾 . 队前 . 队后 正确答案： 19. 串的逻辑结构与（ ）的逻辑结构不同。 . 线性表 . 栈 . 队列 . 树 正确答案： 20. 判定一个顺序栈（最多元素为m个）为空的条件是（ ）。 . top＝＝0 . top＝＝m . top!＝0 . top!＝m 正确答案： 21. 一个队的入队序列是1，2，3，4 ，则队列的输出序列是（ ）。 . 4，3，2，1 . 1，2，3，4 . 1，4，3，2 . 3，2，1，4 正确答案： 22. 设一数列的顺序为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 正确答案： 23. 设有一个二元数组[m][n]，假设[0][0]存放位置在644(10)，[2][2]存放位置在676 (10)，每个元素占一个空间，则[4][5]在（ ）位置，(10)表明用10进数表示。 . 692(10) . 626(10) . 709(10) . 724(10) 正确答案： 24. 下列那种排序需要的附加存储开销最大（）。 . 快速排序 . 堆排序 . 归并排序 . 插入排序 正确答案： 25. 若给定的关键字集合为{20，15，14，18，21，