数据结构习题及答案

1、第一章 1 在数据结构中，从逻辑上可以把数据结构分为（ C ）B. 紧凑结构和非紧凑结构A 动态结构和静态结构内部结构和外部结构.线性结构和非线性结构D. C2.在数据结构中（A ）, 与所使用的计算机无关的是逻辑和存储结构B. A.逻辑结构存储结构D. 物理结构 C.3.下面程序的时间复杂度为 O （mn） 。 for （int i=1;i<=m; i+）for （int j=1; j<=n; j+ ）S+=i第二章线性表） A 链表不具备的特点是（插入删除不需要移动元素 B（顺序） A 可以随机访问任一结点所需空间与其长度成正比 C不必事先估计空间 Dhead 不带头结点的单链

2、表为空的判定条件为 （ A ） ， 带头结点的单链表 head 为空的判定2.） B 条件为（ A head=null B head ->next=null Chead ->next=head D head!=null） D3. 在线性表的下列存储结构中，读取元素花费时间最少的是（顺序表D循环链表 A 单链表B 双链表C 4. 对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C)用头指针表示的单循环链表用尾指针表示的单循环链表单链表C 顺序表ABD5.在一个具有n 个结点的有序单链表中插入一个新的结点， 并保持链表元素仍然有序，则操作的时间复杂度为 ( D )2n)

3、 C O(n) D O(n)A O(1) B O(log 2(B)操作与链表的长 n (n>1)6.在一个长度为的单链表上， 设有头和尾两个指针， 执行度有关删除单链表中最后一个元素 BA 删除单链表中第一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 (D)7. 与单链表相比， 双向链表的优点之一是可以进行随机访问 A 插入删除操作更简单 BC 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易是某带头结点的循环链表的头结点指针， 则该链表最后那个链结点的指针域list8. 若 (头结点的地址) 中存放的是( B )的地址B list 指的链结点的

4、值的内容A list C listD链表第一个链结点的地址分别为一个单链表与一个双向链表的第一个结点的指针，则若9.list1list2( B )和B list1A list2 与 list2 占用相同的存储单元占用更多的存储单元比list1 应该是相同类型的指针变量list2 D 双向链表比单链表占用更多的存储单元 C list1 和 10.（不正确 ）链表中的每个链结点占用的存储空间不必连续， 这句话正确吗？11. 某线性表采用顺序存储结构， 元素长度为 4， 首地址为 100 ，则下标为 12 的（第 13 个） 100+4*12=148148 。元素的存储地址为 V） 插入一个新的数据

5、元素不必移动任何元素。 11. 在顺序表的 （最后一个结点之后 12. ）存储结构，若顺序若对线性表进行的操作主要不是插入删除， 则该线性表宜采用 （频繁地对线性表进行插入和删除操作，则该线性表宜采用存储结构。 ）链 （13、一个顺序表所占用存储空间的大小与（ B）无关。元素的类型 C.D.元素中各的类型A.表的长度B.元素的存放顺序4个存储单元，则某元素若每个元素占用 14 、设存储分配是从低地址到高地址进行的。的地址是指它所占用的单元的（ A ） 。 A. 第1 个单元的地址B. 第 2 个单元的地址第 4 第 3 个单元的地址D.个单元的地址C.15 、若线性表采用顺序存储结构，每个元素

6、占用 4 个存储单元，第 1 个元素的存储地址为。 ， 则第 12 个元素的存储地址是（ B ）100A. 112 B. 144C.148 D. 41216 、若长度为 n 的线性表采用顺序存储结构，在表的第 i 个位置插入一个数据元素， i。 （ D ）的合法值应该是A. i>0 B.i<=nC.1<=i<=n D. 1<=i<=n+1删除表的第 i 个数据元素， i 的合法值应 17 、若长度为 n 的非空线性表采用顺序存储结构， 。 ）该是（ CA. i>0 B.y<=n C.1<=i<=n D. d<=i<=i+1

7、删除表的第 i 个数据元素， 、若长度为 n 的非空线性表采用顺序存储结构，首先需要18 ）个数据元素。移动表中（ BA. n-i B.n+i C. n-i+1 D. n-i-1在表的第i19、若长度为n的非空线性表采用顺序存储结构，个位置插入一个数据元素， 首） 个数据元素。 先需要移动表中 （ CA. i B. n+i C.n-i+1D.n-i-1C 、若频繁地对线性表进行插入和删除操作，该线性表应该采用（）存储结构。 20 索引散列 B.链式D.顺序C.A. 、链表中的每一个链结点所占用的存储单元（ 21 B ） 。连续与否无所谓部分连续 D.B.A.不必连续一定连续C.若查找成功，需要

8、平均比22、在一个具有n 个链结点的线性链表中查找某一个链结点， 较（ C ）个链结点。 A. n B. n/2C.（n+1）/2 D. （n-1）/223 、 给定具有 n 个元素的顺序表， 建立一个有序线性链表的时间复杂度为（ C ） 。 2） D. O（logn）A. O(1) B.O(n) C.O(n 2q 所指的链结点的过程是依次执行p 所指的链结点后面插入一个由、 24 在非空线性链表中由。 )( BA. q ->next=p; p ->next=q; B. q ->next=p ->next;p->next=q;C. q ->next=p -&

9、gt;next; p =q; D. p->next=q; q ->next=p;p 所指的链结点的直接后继链结点的过程过程是依次执行25 、 若删除非空线性链表中由。 ) ( BA. 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);pq 在非空双向循环链表中由、所指的链结点后面插入一个

10、由所指的链结点的操作依次为 26p->prior=q;p->next=q ->next;q ->next=p; () C 。 A. q->prior=p B.q->next->prior=pC. 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-

11、>prior->next=p;C. p ->next ->prior=p; D. p ->prior ->next=p;28、顺序存储的线性表(a1,a2,an), 在任一结点前插入一个新结点时所需移动结点的平。 ）均次数为（ DA. n B. n/2 C. n+1 D. （n+1）/2（1<i<n+1i） 29、在长度为n的顺序表的第个位置上插入一个元素，元素的移动次数是（ A ）。 A. n-i+1 B. n-i C. iD. i-130 、在线性表的下列存储结构中，读取元素花费时间最少的是（ D ） 。顺序表D.单链表B.双链表C.循环链表

12、 A.、 在以单链表为存储结构的线性表中， 数据元素之间的逻辑关系用 （ 31 C ） 。 数据元素在表中的序号表示B. 数据元素的相邻地址表示A.数据元素的值表示D.C. 指向后继元素的指针表示25 、 假设指针 p 指向单链表中的某一结点， 若把 p 指针后面的结点删除，只需修改下列哪个。 指针值即可（） B p->next=p ->next->next A p=p ->next;D p->next=p;C p=p ->next ->next;q 所指结点的后面插入一个由指针 P 中，若要在指针26 、在一个单链表HL所指向的结。点，则执行（D ）

13、A. q->next = p->next ； p->next = qB. p->next =q->next ； q = p； C. q->next =p->next; p->next =q； D. p->next =q->next ; q->next = p； 27、构造个空的线 性表 L 用( A) A.InitList(&L)B.DestroyList (&L)C.ListEmpty(L)D.ClearList(&L)第三章) 、栈和队列的共同点是( C 1 都是先进先出在A.都是先进后出只允许在端点

14、处插入和删除元素 B. C.没有共同点 D.) ，则栈的出栈顺序不可能是( a,b,c,d,e2 、一个栈的进栈顺序是CD. adcbe A. edcba B.decbaC. dceab3、设 n 个元素的进栈序列为，则，若, ，出栈序列为1,2,3,np1,p2,p3,pnp1=n 的值为 ( C ) 。 pi(1<=i<=n)A. i B.n-i C.n-i+1 D. 有多种可能、 判断下面的说法是否正确 4 X ( 1 )插入和删除操作比较简单，是链式栈和链式队列的优点之一。 ) 堆栈允许删除的一端称为栈顶， 而栈底元素是不能删除的。2 ( X 5、设有一个顺序栈 S,元素s

15、1,s2,s3,s4,s5,s6依次进栈，如果6 个元素的出栈顺序为 s2,s3,s4,s6,s5,s1 ，则顺序栈的容量至少应为多少？ 6、 若数组 s0.n -1为两个栈，s1s0.n -1全满时， 各栈才不和 s2 的共用存储空间，且仅当能进行进栈操作，则为这两个栈分配空间的最佳方案是： s1 和 s2 的栈顶指针的初值分别为。 C ） （ n+1和和 A. 1 和 n+1 B. 1 和 n/2 C. -1n D. -1 ，判断栈满的条件为） （D ）.7、判定一个顺序栈 Maxsize （最多元素为st）为空的条件为（BA. st.top!= -1 B. st.top=0 C.st.t

16、op!=MaxsizeD.st.top=Maxsize8 （ A ） 、循环顺序队列中是否可以插入下一个元素， A. 与队头指针和队尾指针的值有关B. 只与队尾指针的值有关，与队头指针的值无关C. 只与数组的大小有关，与队首头指针和队尾指针的值无关 D. 与曾经进行过多少次插入操作有关 9 、若用一个大小为 6 的一维数组来实现循环队列， 且当前 rear 和 front 的值分别为 0 和 3 ， 1 个元素，然后再插入2 个新元素后， rear 和 front的值分别为（ B 当从队列中删除） 。 12 D. 55 B. 2和和和 4 C. 4 和 A. 110A ）位置。 、用单链表表示

17、队列时，队头应该在单链表的（链尾C.链头 B.任意链中 D.A.11） A。、堆栈和队列的共同之处在于它们具有相同的（ A.逻辑特性 B.物理特性C.运算方法D.元素类型、堆栈和队列都是特殊的线性表，其特殊性在于（。） 12C它们具有一般线性表所没有的逻辑特性 A.它们的存储结构特殊 B.对它们的使用方法做了限制C.它们比一般线性表更简单 D.1 ， 2， 3， 4， 513、若 5 个元素的出栈序列为，则进栈序列可能是（ D ）。 A.24315B.23154 C. 31425 D. 3125414 、 若堆栈采用顺序存储结构， 正常情况下， 向堆栈中插入一个元素， 栈顶指针 top 的变化

18、是 （D ）A. 不变 B. top=0 C.top -D. top+15 、 若堆栈采用顺序存储结构， 正常情况下， 删除堆栈中一个元素， 栈顶指针 top 的变化是） C （ B. top=0 C.top - D.top+A. 不变。 B ） 16 、若队列采用顺序存储结构，元素的排列顺序 （由元素进入队列的先后顺序决定与元素的值的大小有关B.A.与作为顺序存储结构的数组的大小有关 D. 与队头指针和队尾指针的取值有关C.“链接队列” 这一概念不涉及（ B ） 。 、 17 数据的逻辑结构C.对数据进行的操作D.链表的种类B.A.数据的存储结构18,向堆栈插入一个由 topp 、若堆栈采用

19、链式存储结构，栈顶指针为所指的新结点的过程C )是依次执行( ,top=pA. p=top B. top=p C. p->next=top D.top->next=p19 、 若非空堆栈采用链式存储结构， 栈顶指针为， 删除堆栈一个元素的过程是依次执行topfree(p)B ； p= top () ;A.top=p B. top=p ->next C. p=top ->next D. p=p -next20 、 若队列采用链式存储结构， 队头元素指针与队尾元素指针分别为 front 和 rear ，向队列 ;rear=p;C ) 中插入一个由 p 所指的新结点的过程是依次执行： ( A. rear=pB. front=p C. rear ->next=p D. front ->next=p21 、若非空队列采用链式存储结构， ，队头元素指针与队尾元素指针分别为front 和 rear ，删 free(p) ( D ); 除队列的一个元素的过程是依次执行： p=