数据结构期中试题.docVIP

一、填空题 1.线性表若采用顺序存储结构,要求内存中可用存储单元的地址______________（是否必须连续） 2.在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=________________ 3. 在一个循环顺序队列Q中,判断队空的条件为_______________ 4. 链式存储结构是通过__________________表示数据元素之间的逻辑关系的。 5. 广义表 ((((a),b),c),d) 的表头是 __________________________ 6. 设s=‘YOU ARE JUDGING IT RIGHT OR WRONG’，顺序执行下列操作：SubString(sub1,s,1,8); SubString(sub2,s,20,5); ConCat(sub1,sub1,sub2); 则最后sub1的值为：_________________________ 7.数组A[8][9]按行优先顺序存储,若数组元素A[2][3]的存储地址为1087,A[4][7]的存储地址为1153,则数组元素A[6][7]的存储地址为__________________ 8.线性表可用顺序存储或链表存储。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时应采用_____________________存储表示。 9. 在一个单链表中，删除P所指结点的后继结点，执行___________________________ 10. 表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素需移动元素的平均次数为________________删除一个元素需要移动的元素平均次数为_________________。 二、选择题 1.算法分析的两个主要方面是（ ）。 A 空间复杂性和时间复杂性 B 正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性 2. 一个n*n的对称矩阵，如以行为主序放入内存，则容量为（ ）。 A n2 B n2/2 C n(n+1)/2 D (n+1)2/2 3.在一个长度为n的顺序存储线性表中,向第i+1个元素(0≤i≤n)之前插入一个新元素时,需要从后向前依次后移（ ）个元素。 A n-i B n-i+1 C n-i-1 D i 4.若进栈序列为1,2,3,4,5,6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ ）。 A 3,2,6,1,4,5 B 3,4,2,1,6,5 C 1,2,5,3,4,6 D 5,6,4,2,3,1 5.在一个单链表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; 6.设数组data[m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作后其头指针front值为（ ）。 A front=front+1 B front=(front+1)%(m-1) C front=(front-1)%m D front=(front+1)%m 7. 算法在发生非法操作时能做出有效处理的特性称为算法的（ ）。 A健壮性 B易读性 C正确性 D高效率 8. 循环队列A[0…m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（ ）。 A (rear-front+m)%m B rear-front+1 C rear-front-1 D rear-front 三、分析下面各程序段的时间复杂度 1. for (i=0; in; i++) for (j=0; jm; j++) A[i][j]=0; 2. x=0; for(i=1; in; i++) for (j=1; j=n-i; j++) x++; 四、综合应用题 1. 设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。 2. 写出下列程序段的输出结果（栈的元素类