数据结构习题及答案.pdf

《数据结构习题及答案.pdf》由会员分享，可在线阅读，更多相关《数据结构习题及答案.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章 1在数据结构中，从逻辑上可以把数据结构分为C A动态结构和静态结构 B.紧凑结构和非紧凑结构 C线性结构和非线性结构 D.内部结构和外部结构 2.在数据结构中,与所使用的计算机无关的是(A)A.逻辑结构 B.存储结构 C.逻辑和存储结构 D.物理结构 3.下面程序的时间复杂度为_Omn_。for(int i=1;i=m;i+)for(int j=1;jnext=null C head-next=head D head!=null 3.在线性表的以下存储结构中，读取元素花费时间最少的是D A 单链表 B 双链表 C 循环链表 D 顺序表 4.对于只在表的首、尾两端进行手稿操作的线性表，宜

2、采用的存储结构为(C)A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 5.在一个具有 n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序，那么操作的时间复杂度为(D)A O(1)B O(log2n)C O(n2)D O(n)6.在一个长度为 n(n1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 7.与单链表相比，双向链表的优点之一是(D)A 插入删除操作更简单 B 可以进行随机访问 C 可以省略

3、表头指针或表尾指针 D 顺序访问相邻结点更容易 8.假设 list 是某带头结点的循环链表的头结点指针，那么该链表最后那个链结点的指针域(头结点的地址)中存放的是(B)A list 的地址 B list 的内容 C list 指的链结点的值 D 链表第一个链结点的地址 9.假设 list1 和 list2 分别为一个单链表与一个双向链表的第一个结点的指针，那么(B)A list2 比 list1 占用更多的存储单元 B list1 与 list2 占用相同的存储单元 C list1 和 list2 应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的

4、存储空间不必连续，这句话正确吗？(不正确)11.某线性表采用顺序存储结构，元素长度为 4，首地址为 100，那么下标为 12 的第 13个元素的存储地址为 148。V 100+4*12=148 11.在顺序表的 最后一个结点之后 插入一个新的数据元素不必移动任何元素。12.假设对线性表进行的操作主要不是插入删除，那么该线性表宜采用 顺序 存储结构，假设频繁地对线性表进行插入和删除操作，那么该线性表宜采用(链)存储结构。13、一个顺序表所占用存储空间的大小与B无关。A表的长度 B.元素的存放顺序 C.元素的类型 D.元素中各的类型 14、设存储分配是从低地址到高地址进行的。假设每个元素占用 4

5、个存储单元，那么某元素的地址是指它所占用的单元的A。A.第 1 个单元的地址 B.第 2 个单元的地址 C.第 3 个单元的地址 D.第 4 个单元的地址 15、假设线性表采用顺序存储结构，每个元素占用 4 个存储单元，第 1 个元素的存储地址为100，那么第 12 个元素的存储地址是 B。A.112 B.144 C.148 D.412 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-ne

6、xt;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

7、。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 的顺序

8、表的第 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-nex

9、t;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、一个栈的

10、进栈顺序是 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，向队列中插

11、入一个由 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=f

12、ront+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、栈和队列都是 AD 。A.限制存取位置的线性结构 B.顺序存储的线性结构 C.链式存储的线性结构 D.限制存取位置的线性结构 27、顺序栈是一种规定了元素进栈顺序的栈。X 28、在循环队列中少用一个存储空间，队满的条件是 A A rear+1%maxsize=front Braer=front C front+1%maxsize=rear Drear=0