数据结构作业一概论.doc

作业一一、单项选择题1. 一个数组元素a 与( )的表示等价。　　A. *(a+i) B. a+i C. *a+i D. a+I2．执行下面程序段时，执行S语句的次数为( )。　　 for(int i=1; i=n; i++)　　 for(int j=1; j=i; j++) S;　　A. n2 B. n2/2 C. n(n+1) D. n(n+1)/23. 当一个作为实际传递的对象占用的存储空间较大并可能被修改时，应最好说明为( )，以节省参数值的传输时间和存储参数的空间。　　A. 基本类型 B. 引用型 C. 指针型 D. 常值引用型4. 输出一个二维数组b[m][n]中所有元素值的时间复杂度为( )。　　A. O(n) B. O(m+n) C. O(n2) D. O(m*n)5. 某算法仅含程序段1和程序段2，程序段1的执行次数3n2，程序段2的执行次数为0.01n3，则该算法的时间复杂度为( )。　　A. O(n) B. O(n2) C. O(n3) D. O(1)6. 多维数组实际上是由嵌套的( )实现的。　　A. 一维数组 B. 多项式 C. 三元组表 D. 简单变量7. 在一个长度为n的顺序表中删除第i个元素（0≤i≤n-1）时，需要从前向后依次前移( )个元素。　　A. n-i B. n-i+1 C. n-i-1 D. i8. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为( )。　　A. O(n) B. O(n/2) C. O(1) D. O(n2)9. 设有一个nn的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A存放于B中( )处。　　A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/210. 不带头结点的单链表first为空的判定条件是( )。　　 A. first == NULL; B. first-link == NULL;　　 C. first-link == first; D. first != NULL;11. 设单链表中结点的结构为（data, link）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行的操作是( )。　　A.s-link=p; p-link=s; B. p-link=s; s-link=p;　　C.s-link=p-link; p=s; D. s-link=p-link; p-link=s;12. 设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行的操作是( )。　　A.s = rear; rear = rear-link; delete s;　　B.rear = rear-link; delete rear;　　C.rear = rear-link-link; delete rear; 　　D.s = rear-link-link; rear-link-link = s-link; delete s;二、填空题1.数据结构包括逻辑结构、和数据的运算三个方面。2.基本数据类型是计算机已经实现了的。3.在程序运行过程中不能扩充的数组是分配的数组。这种数组在声明它时必须指定它的大小。.对于一个长度为n的顺序存储的线性表在表头插入元素的时间复杂度为在表尾插入元素的时间复杂度为对于一个长度为n的单链式存储的线性表,在表头插入元素的时间复杂度为在表尾插入元素的时间复杂度为6.若设一个nn的矩阵A的开始存储地址LOC(0, 0) 及元素所占存储单元数d已知，按行存储时其任意一个矩阵元素a[j]的存储地址为。7.将一个n阶对称矩阵A的上三角部分按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中，则A[I][J]在I≤J时将存放于数组B的位置。8.若设串S = “documentHash.doc\0”，则该字符串S的长度为。9.在链表中进行插入和操作的效率比在顺序存储结构中进行相同操作的效率高。10.单链表中逻辑上相邻的结点而在物理位置上相邻。11.若设L是指向带表头的单链表, 语句 L-link=L-link-link的作用是单链表中的第一个结点。在以HL为表头指针的带表头结点的单链表和循环单链表中,链表为空的条件分别为和三、判断题1. ( )算法和程序原则上没有区别，在讨论数据结构时二者是通用的。2. ( )只有用面向对象的计算机语言才能描述数据结构算法。3. ( )数组是一种静态的存储空间分配，就是说，在程序设计时