安交通大学15年7月《数据结构》考查课试题西交《数据结构》在线作业单选题多选题一、单选题（共40 道试题，共80 分。
）1. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。
A. O(n) O(n)B. O(n) O(1)C. O(1) O(n)D. O(1) O(1)-----------------选择：C2. n个结点的线索二叉树上含有的线索数为（）A. 2nB. n－lC. n＋l-----------------选择：C3. 下面关于算法说法错误的是（）A. 算法最终必须由计算机程序实现B. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的-----------------选择：D4. 若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。
A. 直接插入B. 直接选择C. 堆D. 快速-----------------选择：A5. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（）。
Head(Tail(Head(Tail(Tail(A)))))A. （a）C. aD.d-----------------选择：D6. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。
A. p->next=s;s->next=p->next;B. s->next=p->next;p->next=s;C. p->next=s;p->next=s->next;D. p->next=s->next;p->next=s;-----------------选择：B7. 关键路径是事件结点网络中（）。
A. 从源点到汇点的最长路径B. 从源点到汇点的最短路径C. 最长回路D. 最短回路-----------------选择：A8. 具有10个叶结点的二叉树中有（）个度为2的结点，A. 8B. 9C. 10D. ll-----------------选择：B9. 下列排序算法中，占用辅助空间最多的是：( )A. 归并排序B. 快速排序C. 希尔排序D. 堆排序-----------------选择：A10. 下述文件中适合于磁带存储的是（）。
A. 顺序文件B. 索引文件C. 散列文件D. 多关键字文件-----------------选择：A11. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。
A. 插入B. 选择C. 希尔D. 二路归并-----------------选择：A12. 散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。
A. 最大概率B. 最小概率C. 平均概率D. 同等概率-----------------选择：D13. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。
A. 前序B. 中序C. 后序D. 按层次-----------------选择：C14. （）的遍历仍需要栈的支持.A. 前序线索树B. 中序线索树C. 后序线索树D. 不确定-----------------选择：C15. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。
A. 13B. 33C. 18D. 40-----------------选择：B16. 就平均性能而言，目前最好的内排序方法是( )排序法。
A. 冒泡B. 希尔插入C. 交换D. 快速-----------------选择：D17. 字符串‘ababaabab’ 的nextval 为（）A. (0,1,0,1,04,1,0,1)B. (0,1,0,1,0,2,1,0,1)C. (0,1,0,1,0,0,0,1,1)D. (0,1,0,1,0,1,0,1,1 )-----------------选择：A18. 栈在（）中应用。
A. 递归调用B. 子程序调用C. 表达式求值D. A，Ｂ，Ｃ-----------------选择：D19. 在下面的程序段中，对x的赋值语句的频度为（）FOR i:=1 TO n DOFOR j:=1 TO n DO x:=x+1;A. O(2n)B. O(n)C. O(n2)D. O(log2n)-----------------选择：C20. 从逻辑上可以把数据结构分为（）两大类。
A. 动态结构、静态结构B. 顺序结构、链式结构C. 线性结构、非线性结构D. 初等结构、构造型结构-----------------选择：B21. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（）A. 5B. 6C. 7D. 8-----------------选择：D22. 要连通具有n个顶点的有向图，至少需要（）条边。
A. n-lB. nC. n+lD. 2n-----------------选择：B23. 栈和队都是（）A. 顺序存储的B. 线性结构C. 链式存储的D. 非线性结构-----------------选择：24. 有n个叶子的哈夫曼树的结点总数为（）。
A. 不确定B. 2nC. 2n+1D. 2n-1-----------------选择：25. 一个递归算法必须包括（）。
A. 递归部分B. 终止条件和递归部分C. 迭代部分D. 终止条件和迭代部分-----------------选择：26. 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。
( )A. 选择排序法B. 插入排序法C. 快速排序法D. 堆积排序法-----------------选择：27. 一个算法应该是（）。
A. 程序B. 问题求解步骤的描述C. 要满足五个基本特性D. A和C.-----------------选择：28. 串的长度是指（）A. 串中所含不同字母的个数B. 串中所含字符的个数C. 串中所含不同字符的个数D. 串中所含非空格字符的个数-----------------选择：29. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。
A. 不确定B. n-i+1C. iD. n-i-----------------选择：30. 广义表（（a,b,c,d））的表头是（），表尾是（）。
A. aB. （）C. （a,b,c,d）D. （b,c,d）-----------------选择：31. 广义表运算式T ail(((a,b),(c,d)))的操作结果是（）。
A. (c,d)B. c,dC. ((c,d))D. d-----------------选择：32. 连续存储设计时，存储单元的地址（）。
A. 一定连续B. 一定不连续C. 不一定连续D. 部分连续，部分不连续-----------------选择：33. 适用于折半查找的表的存储方式及元素排列要求为( )A. 链接方式存储，元素无序B. 链接方式存储，元素有序C. 顺序方式存储，元素无序D. 顺序方式存储，元素有序-----------------选择：34. 算法的时间复杂度取决于（）A. 问题的规模B. 待处理数据的初态C. A和BD. 变量个数-----------------选择：35. 线索二叉树是一种（）结构。
A. 逻辑B. 逻辑和存储C. 物理D. 线性-----------------选择：36. 算术表达式a+b*（c+d/e）转为后缀表达式后为（）A. ab+cde/*B. abcde/+*+C. abcde/*++D. abcde*/++-----------------选择：37. 对于栈操作数据的原则是（）A. 先进先出B. 后进先出C. 后进后出D. 不分顺序-----------------选择38. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。
A. 3B. 10C. 15D. 25-----------------选择：39. 动态存储管理系统中，通常可有（）种不同的分配策略。
A. 1B. 2C. 3D. 4-----------------选择：40. 用二分（对半）查找表的元素的速度比用顺序法( )A. 必然快B. 必然慢C. 相等D. 不能确定-----------------选择：西交《数据结构》在线作业单选题多选题二、多选题（共10 道试题，共20 分。
）1. 下面说法正确的是( )。
A. 广义表的表头总是一个广义表B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构D. 广义表可以是一个多层次的结构-----------------选择：2. 下面关于二分查找的叙述不正确的是( )A. 表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序，而且只能从小到大排列C. 表必须有序且表中数据必须是整型，实型或字符型D. 表必须有序，且表只能以顺序方式存储-----------------选择：3. 下面关于串的的叙述中，正确的是？（）A. 串是字符的有限序列B. 空串是由空格构成的串C. 模式匹配是串的一种重要运算D. 串既可以采用顺序存储，也可以采用链式存储-----------------选择：4. 下列关于m阶B-树的说法正确的是( )A. 根结点至多有m棵子树B. 所有叶子都在同一层次上C. 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树D. 根结点中的数据是有序的-----------------选择5. 有关二叉树下列说法不正确的是（）A. 二叉树的度为2B. 一棵二叉树的度可以小于2C. 二叉树中至少有一个结点的度为2D. 二叉树中任何一个结点的度都为2-----------------选择：6. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形可能出现的是（）。
A. G中有弧<Vi，Vj>B. G中有一条从Vi到Vj的路径C. G中没有<Vi,Vj>D. G中有一条从Vj到Vi的路径-----------------选择：7. 下列说法正确的是（）。
A. 图的遍历是从给定的源点出发每一个顶点仅被访问一次B. 图的深度遍历不适用于有向图C. 遍历的基本算法有两种：深度遍历和广度遍历D. 图的深度遍历是一个递归过程-----------------选择：8. 下面几个符号串编码集合中，是前缀编码的是（）A. {0,10,110,1111}B. {11,10,001,101,0001}C. {00,010,0110,1000}D. {b,c,aa,ac,aba,abb,abc}-----------------选择9. 下列哪种图的邻接矩阵不是对称矩阵？（）A. 有向图B. 无向图C. AOV网D. AOE网-----------------选择：10. 下述哪些不是顺序存储结构的优点？（）A. 存储密度大B. 插入运算方便C. 删除运算方便D. 可方便地用于各种逻辑结构的存储表示-----------------选择：。