【在线】17春北航《算法和数据结构》在线作业一.docVIP

一、单选题（共 25 道试题，共 100 分。） V 1. 栈操作的原则是（　） A. 栈顶删除 B. 先进先出 C. 后进先出 D. 栈顶插入 2. 单链表表示法的基本思想是指针P表示结点间的逻辑关系，则以下说法错误的是 A. 任何指针都不能用打印语句输出一个指针型变量的值 B. 如果要引用(如访问)p所指结点，只需写出p(以后跟域名)即可 C. 若想修改变量p的值(比如让P指向另一个结点)，则应直接对p赋值 D. 对于一个指针型变量P的值。只需知道它指的是哪个结点 3. 在一个单链表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; 4. 用某种排序方法队线性表（25，84，21，47，15，27，68，35，20）进行排序，元素序列变化如下：（1）25，84，21，47，15，27，68，35，20 （2）20，15，21，25，47，27，68，35，84 （3）15，20，21，25，35，27，47，68，84 （4）15，20，21，25，27，35，47，68，84 所采用的排序方法是（ ）。 A. 选择排序 B. Shell排序 C. 归并排序 D. 快速排序 5. 由两个栈共享一个向量空间的好处是（ ）。 A. 减少存取时间，降低下溢发生的机率 B. 节省存储空间，降低上溢发生的机率 C. 减少存取时间，降低上溢发生的机率 D. 节省存储空间，降低下溢发生的机率 6. 快速排序的记录移动次数（　 ）比较次数，其总执行时间为O(nlog2n)。 A. 大于 B. 大于等于 C. 小于等于 D. 小于 7. 线性链表不具有的特点是（）。 A. 随机访问 B. 不必事先估计所需存储空间大小 C. 插入与删除时不必移动元素 D. 所需空间与线性表长度成正比 8. 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（ ） A. n2 B. nlog2n C. log2n D. n-1 9. 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（）。 A. 行号 B. 列号 C. 元素值 D. 地址 10. 串是任意有限个（ ） A. 符号构成的序列 B. 符号构成的集合 C. 字符构成的序列 D. 字符构成的集合 11. 若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。 A. 3，2，1 B. 2，1，3 C. 3，1，2 D. 1，3，2 12. 顺序队列的人队操作应为 ( ) A. sq.rear=sq.rear+1 sq.data[sq.rear]=x B. sq.data[sq.rear]=x sq.rear=sq.rear+1 C. sq.rear=(sq.rear+1)% maxsize; sq.data[sq.rear]=x D. sq.data[sqrear]=x sq.rear=(sq.rear+1)% maxsize 13. 在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（　　）。 A. q-next=p-next;p-next=q; B. p-next=q-next;q=p; C. q-next=p-next;p-next=q; D. p-next=q-next;q-next=p; 14. 对有n个记录的有序表采用二分查找，其平均查找长度的量级为（　） A. O(log2n) B. O(nlog2n) C. O(n) D. O(n2) 15. 以下关于数据的存储结构的叙述哪一条是正确的（ ）。 A. 数据的存储结构是数据间关系的抽象描述 B. 数据的存储结构是逻辑结构在计算机存储器中的实现 C. 数据的存储结构分为线性结构和非线性结构 D. 数据的存储结构对数据运算的具体实现没有影响 16. 队列的删除操作是在（ ）进行。 A. 队首 B. 队尾 C. 队前 D. 队后 17. 算法的时间复杂度是指（ ）。 A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数 18. 在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为()。 A. e B. 2e C. n的平方－e D. n的平方－2e 19. 设矩阵A是一对称矩阵(aij=aji,1=i,j=8)，若每个矩阵元素占3个单元，将其上三角部分（包括对角线）按行序为主序存放在数组B中，B的首地址为10