《数据结构与算法》在线作业.doc

数据结构与算法在线作业一、单选题（共 50 道试题，共 100 分。）1. 一个队的入队序列是1，2，3，4 ，则队列的输出序列是（）。A. 4，3，2，1B. 1，2，3，4C. 1，4，3，2D. 3，2，1，4正确答案：B 满分：2 分2. 当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（ ）语句修改top指针。A. top+B. top=0C. top-D. top=N正确答案：A 满分：2 分3. 若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用()存储方式最节省时间。A. 顺序表B. 单链表C. 双链表D. 单循环链表正确答案：A 满分：2 分4. 在一个循环队列中，队首指针指向队首元素的( )位置。A. 后一个B. 前一个C. 当前D. 以上都不是正确答案：B 满分：2 分5. 若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（ ）方法比较次数最少。A. 直接插入排序B. 快速排序C. 归并排序D. 直接选择排序正确答案：A 满分：2 分6. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非叶结点，则B中右指针域为空的结点有（ ）个。A. n-1B. nC. n+1D. n+2正确答案：C 满分：2 分7. 含5个节点(元素值均不相同)的二叉搜索树有（）种。A. 54B. 42C. 36D. 65正确答案：B 满分：2 分8. 具有2000个节点的二叉树，其高度至少为（ ）。A. 9B. 10C. 11D. 12正确答案：C 满分：2 分9. 向顺序栈中压入新元素时，应当（ ）。A. 先移动栈顶指针，再存入元素B. 先存入元素，再移动栈顶指针C. 先后次序无关紧要D. 同时进行正确答案：A 满分：2 分10. 下列那种排序需要的附加存储开销最大（ ）。A. 快速排序B. 堆排序C. 归并排序D. 插入排序正确答案：C 满分：2 分11. 设有一个二元数组Amn，假设A00存放位置在644(10)，A22存放位置在676 (10)，每个元素占一个空间，则A45在（）位置，(10)表明用10进数表示。A. 692(10)B. 626(10)C. 709(10)D. 724(10)正确答案：C 满分：2 分12. 设有一个10阶的对称矩阵A，采用压缩存储方式，以列序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（）。A. 13B. 33C. 18D. 40正确答案：B 满分：2 分13. 数据结构课程主要研究以下三方面的内容，它们是（）。A. 数据、数据元素、数据类型B. 数据元素、数据类型、算法实现C. 数据元素、数据的逻辑结构、数据的存储结构D. 数据的逻辑结构、数据的存储结构、数据的运算正确答案：D 满分：2 分14. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。A. 必须是连续的B. 部分地址必须是连续的C. 一定不是连续的D. 连续不连续都可以正确答案：D 满分：2 分15. 按照二叉树的定义，具有3个结点的二叉树有（ ）种。A. 3B. 4C. 5D. 6正确答案：C 满分：2 分16. 具有65个结点的完全二叉树其深度为（ ）。A. 8B. 7C. 6D. 5正确答案：B 满分：2 分17. 若线性表最常用的操作是存取第i个元素及其前趋的值，则采用（ ）存储方式节省时间。A. 单链表B. 双链表C. 单循环链表D. 顺序表正确答案：D 满分：2 分18. 结构化程序设计的3种结构是（）。A. 顺序结构、选择结构、转移结构B. 分支结构、等价结构、循环结构C. 多分支结构、赋值结构、等价结构D. 顺序结构、选择结构、循环结构正确答案：D 满分：2 分19. 设单链表中指针P指着结点A ，若要删除A之后结点（若存在），则需要修改指针的操作为（）。A. p-next=p-next-nextB. p=p-nextC. p=p-next-nextD. P-next=p正确答案：A 满分：2 分20. 如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快。A. 起泡排序B. 快速排序C. 简单选择排序D. 堆排序正确答案：D 满分：2 分21. 设有1000个元素，用二分法查找时，最大比较次数是（ ）。A. 1B. 7C. 10D. 25正确答案：C 满分：2 分22. 已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。A. acbedB. decabC. deabcD. cedba正确答案：D 满分：2 分23. 组成数据的基本单位是（）。A. 数据项B. 数据类型C. 数据元素D. 数据变量正确答案：C 满分：2 分24. 组成数据结构的基本单位是（ ）。A. 数据项B. 数据类型C. 数据元素D. 数据变量正确答案：C 满分：2 分25. 向二叉搜索树中插入一个元素时，其时间复杂度大致为( )。A. O(2n)B. O(n)C. O(1)D. O(n2n)正确答案：A 满分：2 分26. 设有两个串（S1和S2），求S1在S2中首次出现的位置的运算称为（ ）。A. 连接B. 模式匹配C. 求子串D. 求串长正确答案：B 满分：2 分27. 以下关于队列的叙述中哪一条是不正确的（）。A. 先进先出B. 既能用顺序存储，也能用链接存储C. 适用于二叉树的对称序周游算法的实现D. 适用于树的层次次序周游算法的实现正确答案：C 满分：2 分28. 关于有向图的邻接表和逆邻接表表示法，下列结论正确的是（）。A. 用邻接表表示法计算入度比较方便B. 用邻接表表示法计算入度和出度都方便C. 用逆邻接表表示法计算入度和出度都不方便D. 用逆邻接表表示法计算入度比计算出度方便正确答案：D 满分：2 分29. 在一个长度为n 的线性表中，删除值为x 的元素时需要比较元素和移动元素的总次数为（）。A. （n+1）/2B. n/2C. nD. n+1正确答案：C 满分：2 分30. 若需要利用形参直接访问实参，则应把形参变量说明为( )参数。A. 指针B. 引用C. 值D. 都不是正确答案：B 满分：2 分31. 下列数据组织形式中，（）的各个结点可以任意邻接。A. 集合B. 树形结构C. 线性结构D. 图状结构正确答案：D 满分：2 分32. 两个串相等的充分必要条件是（）。A. 两个串的长度相等B. 两个串对应位置的字符相等C. 两个串的长度相等且对应位置的字符相同D. 以上条件都不正确正确答案：C 满分：2 分33. 从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（ ）。A. 原树高度加1B. 原树高度减1C. 原树高度D. 不确定正确答案：B 满分：2 分34. 带头节点的单链表 head 为空的判定条件（）。A. head=NULLB. head-next=NULLC. head-next=headD. head!=head正确答案：B 满分：2 分35. 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ ）。A. O（nlog2e）B. O（n+e）C. O(n*e)D. O(n2)正确答案：B 满分：2 分36. 如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。下列选项中，（ ）就是不稳定的排序方法。A. 起泡排序B. 归并排序C. 直接插入法排序D. 简单选择排序正确答案：D 满分：2 分37. 某二叉树结点的前序序列为E、A、C、B、D、G、F，对称序列为A、B、C、D、E、F、G。 该二叉树结点的后序序列为 ()。A. B,D,C,A,F,G,EB. B,D,C,F,A,G,EC. E,G,F,A,C,D,BD. E,G,A,C,D,F,B正确答案：A 满分：2 分38. 具有65个结点的完全二叉树的高度为（ ）。（根的层次号为0）A. 8B. 7C. 6D. 5正确答案：C 满分：2 分39. 适于对动态查找表进行高效率查找的组织结构是（）。A. 有序表B. 分块有序表C. 三叉排序树D. 线性链表正确答案：C 满分：2 分40. 二叉树第i层上至多有（ ）结点。A. 2iB. 2 iC. 2i-1D. 2 i-1正确答案：D 满分：2 分41. 假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( )。A. O(n)B. O(e)C. O(n+e)D. O(n*e)正确答案：C 满分：2 分42. 设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针操作为（ ）。A. p-next=p-next-nextB. p=p-nextC. p=p-next-nextD. p-next=p正确答案：A 满分：2 分43. 在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（ ）。A. HL=p;p-next=HL;B. p-next=HL;HL=p;C. p-next=HL;p=HL;D. p-next=HL-next;HL-next=p;正确答案：B 满分：2 分44. 树最适合用来表示（）。A. 有序数据元素B. 无序数据元素C. 元素之间具有分支层次关系的数据D. 元素之间无联系的数据正确答案：C 满分：2 分45. Substr(DATA STRUCTURE，5，9)=（ ）。A. STRUCTUREB. ASTUCTURC. DATA STRUCTRUED. DATA正确答案：A 满分：2 分46. 栈和队都是（）。A. 顺序存储的线性结构B. 限制存取点的线性结构C. 链式存储结构D. 限制存取点的非线性结构正确答案：B 满分：2 分47. 设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（ ）。A. 3，2，5，6，4，1B. 1，5，