数据结构习题及答案.doc

第一章1在数据结构中，从逻辑上可以把数据结构分为（C ）A动态结构和静态结构 B. 紧凑结构和非紧凑结构C线性结构和非线性结构 D. 内部结构和外部结构l 2. 在数据结构中,与所使用的计算机无关的是( A )A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构3.下面程序的时间复杂度为_O（mn）_。 for (int i=1; i=m; i+) for (int j=1; jnext=null C head-next=head D head!=nulll 3.在线性表的下列存储结构中，读取元素花费时间最少的是（D）A 单链表 B 双链表 C 循环链表 D 顺序表l 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C)A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表l 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序，则操作的时间复杂度为( D )A O(1) B O(log2n) C O(n2) D O(n)l 6.在一个长度为n (n1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长度有关A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素l 7.与单链表相比，双向链表的优点之一是(D)A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易l 8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域(头结点的地址)中存放的是( B )A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址l 9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B )A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确)11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。V 100+4*12=14811.在顺序表的（ 最后一个结点之后 ）插入一个新的数据元素不必移动任何元素。12.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（ 顺序 ）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用( 链 )存储结构。13、一个顺序表所占用存储空间的大小与（B）无关。A表的长度 B.元素的存放顺序 C. 元素的类型 D.元素中各的类型l 14、设存储分配是从低地址到高地址进行的。若每个元素占用4个存储单元，则某元素的地址是指它所占用的单元的（A）。A. 第1个单元的地址 B. 第2个单元的地址 C. 第3个单元的地址 D. 第4个单元的地址 15、若线性表采用顺序存储结构，每个元素占用4个存储单元，第1个元素的存储地址为100，则第12个元素的存储地址是（ B）。A. 112 B. 144 C.148 D. 412 l 16、若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是( D )。A. i0 B.i=n C.1=i=n D. 1=i0 B.y=n C.1=i=n D. d=inext=p; p-next=q; B. q-next=p-next; p-next=q; C. q-next=p-next; p =q; D. p-next=q; q-next=p; 25、若删除非空线性链表中由p所指的链结点的直接后继链结点的过程过程是依次执行（ B）。A. r=p-next; p-next=r; free(r);B. r=p-next; p-next=r-next; free(r); C. r=p-next; p-next=r-next; free(p); D. p-next=p-next-next; free(p); 26、在非空双向循环链表中由q所指的链结点后面插入一个由p所指的链结点的操作依次为p-prior=q; p-next=q-next;q-next=p;（ C ）。A. q-prior=p B. q-next-prior=p C. p-next-prior=p; D. p-prior-next=p; 27、在非空双向循环链表中由q所指的链结点前面插入一个由p所指的链结点的操作依次为p-next=q; p-prior=q-prior;q-prior=p;（ D ）。A.q-next=p; B. q-prior-next=p; C. p-next-prior=p; D. p-prior-next=p; 28、顺序存储的线性表(a1,a2,an),在任一结点前插入一个新结点时所需移动结点的平均次数为（ D ）。A. n B. n/2 C. n+1 D. (n+1)/2 29、在长度为n的顺序表的第i（1in+1）个位置上插入一个元素，元素的移动次数是( A )。A. n-i+1 B. n-i C. i D. i-1 30、在线性表的下列存储结构中，读取元素花费时间最少的是（ D）。A. 单链表 B. 双链表 C. 循环链表 D. 顺序表 31、在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ C ）。A. 数据元素的相邻地址表示 B. 数据元素在表中的序号表示 C. 指向后继元素的指针表示 D. 数据元素的值表示 25、假设指针p指向单链表中的某一结点，若把p指针后面的结点删除，只需修改下列哪个指针值即可（ ）。 Ap=p-next; Bp-next=p-next-next Cp=p-next-next; Dp-next=p; 26、在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针P所指向的结点，则执行(D )。Aq-nextp-next；p-nextq Bp-nextq-next；qp；Cq-nextp-next；p-nextq；Dp-nextq-next；q-nextp；27、构造一个空的线性表L用（A ）A.InitList(&L)B.DestroyList (&L) C.ListEmpty(L)D.ClearList(&L)第三章1、栈和队列的共同点是（ C ）A. 都是先进后出 B. 都是先进先出在 C. 只允许在端点处插入和删除元素D. 没有共同点2、一个栈的进栈顺序是a,b,c,d,e，则栈的出栈顺序不可能是（ C ）A. edcba B.decba C. dceab D. adcbe 3、设n个元素的进栈序列为1,2,3,n，出栈序列为p1,p2,p3,pn，若p1=n，则pi(1=inext=top D.top-next=p 19、若非空堆栈采用链式存储结构，栈顶指针为top，删除堆栈一个元素的过程是依次执行p= top；（ B ）; free(p)A.top=p B. top=p-next C. p=top-next D. p=p-next 20、若队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，向队列中插入一个由p所指的新结点的过程是依次执行：（ C ）;rear=p;A. rear=p B. front=p C. rear-next=p D. front-next=p 21、若非空队列采用链式存储结构，队头元素指针与队尾元素指针分别为front和rear，删除队列的一个元素的过程是依次执行：p=front; ( D ); free(p)A.rear=p B. rear=p-next C. p-next=rear D. front=p-next 22、在循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断循环队列队空的条件是（ C ）。A. front=rear+1 B. rear=front+1 C. front=rear D. front=rear=0 23、若描述某循环队列的数组为为CircleM ，当循环队列满时，队列中有（ B ）个元素。A. M B. M-1 C. M+1 D. M+2 24、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据打印，该缓冲区应该是一个（ D ）结构。A. 线性表 B.数组 C. 堆栈 D. 队列 25、设计一个递归问题的非递归算法通常需要设置（ C ）结构。A. 线性表 B.数组 C. 堆栈 D. 队列 26