2011数据结构习题.docVIP

题1.1 数据结构在计算机内存中的表示是指———。 A．数据的存储结构 B．数据元素 C．数据的逻辑结构 D．数据元素之间的关系 题1.2 从逻辑上可把数据结构分为——。 A.动态结构和静态结构 B.顺序结构和链式结构 C.线性结构和非线性存储结构 D.内部结构和外部结构 题1.3 判断正误：数据元素是数据的最小单位。 题1.4 分析下列程序段的时间复杂度： (1) x=1; for (i=1;i=n;i++) for (j=1;j=i;j++) for (k=1;k=j;k++) x++; (2) for (i=1;in;i++) { y=y+1; for (j=0; j=(2*n); j++) x++; } (3) i=1; while (i=n) i=i*2 (4) i=0; s=0; while(sn) { i=i+1; s=s+i; } 题1.5 设n是偶数，试计算运行下列程序段后m的地址并给出该程序段的时间复杂度。 m=0； for(i=1;i=n;i++) for(j=2*i;j=n;j++) m=m+1; 题2.1 线性表的静态链表存储结构与顺序存储结构相比优点是——。 A．所有的操作算法实现简单 B．便于随机存取 C. 便了插入和删除 D．便于利用零散的存储器空间 题2.2 判断正误 1.顺序存储只能用于存储线性结构 2.顺序查找法适用于存储结构为线性或链接存储的线性表。 题2.3 若较频繁地对一个线性表进行插入和删除操作，该线性表宜用什么存储结构，为什么？ 题2.4 线性链表中各链接点的位置——。 A．必须连续 B．部分地址必须连续 C. 不一定连续 D．连续与否无所谓 题2.5 线性表是具有n个（ ）的有限序列。 (1)表元素 (2)字符 (3)数据元素 (4)数据项 (5)信息项 题2.6 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个元素的时间复杂度为（1= i = n+1 ）。 A.O(0) B.O(1) C.O(n) D.O(n2) 题2.7 表长为n的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素需移动元素的平均个数 ，删除一个元素需移动元素的平均个数 。 题2.8 已知结点指针p、q分别表示双向链表中任意两个相邻结点(即p-next=q，q-prior=p)，请写出删除q所指向结点的程序段。 题2.9 将两个各有n个元素的有序表归并成一个有序表，其最小的比较次数是 。 A.n B.2n-1 C.2n D.n-1 题2.10 填空：在一个单链表的p结点之前插入一个人结点s时，可执行如下操作： (1)s-next = ; (2)p-next = s; (3)t = p-data; (4)p-data = ; (5)s-data = ; 题2.11 带头结点的双向循环链表L为空表的条件是 。 题2.12 需要分配较大存储空间，插入和删除不需要移动元素的线性表，其存储结构是 。 A.单链表 B.静态链表 C.线性链表 D.顺序存储结构 题2.13 有一个单链表L，其结点的元素值以非递减有序排列，编写算法删除该单链表中多余的元素值相同的结点。 题2.14 有一个单链表L(至少有一个结点)，其头结点指针为L，编写一个过程将L置逆，要求逆转在原链表上进行 题3.1 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列删除一个元素，再加入两个元素后，rear和front的值分别为 。 A.1和5 B.2和4 C.4和2 D.5和1 题3.2 用数组表示的循环队列的队首位置和队尾位置分别为1和max_size，试给出判断队列为空和满的条件(队列长度最大为MAXSIZE)。 题3.3 若某堆栈的输入序列为1,2,3,…,n，输出序列的