数据结构习题及答案

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

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

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

4、list 的地址 B list 的内容 C list 指的链结点的值 D 链表第一个链结点 的地址9. 假设 list1 和 list2 分别为一个单链表与一个双向链表的第一个结点的指针，那么 ( B ) A list2 比 list1 占用更多的存储单元 B list1 与 list2 占用相同的存储单元C list1 和 list2 应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元10. 链表中的每个链结点占用的存储空间不必连续，这句话正确吗？( 不正确 )11. 某线性表采用顺序存储结构， 元素长度为 4，首地址为 100 ，那么下标为 12 的(第 13 个) 元素的存

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

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

7、lt;=i<=n D. d<=i<=i+118、假设长度为 n 的非空线性表采用顺序存储结构， 删除表的第 i 个数据元素， 首先需要 移动表中 B 个数据元素。A. n-i B.n+i C. n-i+1 D. n-i-119、假设长度为 n 的非空线性表采用顺序存储结构， 在表的第 i 个位置插入一个数据元素， 首 先需要移动表中 C 个数据元素。A. i B. n+i C.n-i+1D.n-i-120、 假设频繁地对线性表进行插入和删除操作，该线性表应该采用C 存储结构。A. 散列 B. 顺序 C. 链式 D. 索引21、 链表中的每一个链结点所占用的存储单元B 。A.

8、不必连续 B. 一定连续 C. 局部连续 D. 连续与否无所谓22、在一个具有 n 个链结点的线性链表中查找某一个链结点， 假设查找成功， 需要平均比 较C个链结点。A. n B. n/2C.n+1/2 D. n-1/223、给定具有 n 个元素的顺序表，建立一个有序线性链表的时间复杂度为C。2A. O1 B.On C.On2 D. Olog2n24、 在非空线性链表中由p所指的链结点后面插入一个由 q所指的链结点的过程是依次执行 B 。A. q->next=p; p->next=q; B. q->next=p->next; p->next=q;C. q->

9、next=p->next; p =q; D. p->next=q; q->next=p;25、 假设删除非空线性链表中由p 所指的链结点的直接后继链结点的过程过程是依次执行 B 。A. r=p->next; p->next=r; freer;B. r=p->next; p->next=r->next; freer;C. r=p->next; p->next=r->next; freep;D. p->next=p->next->next; freep;26、 在非空双向循环链表中由q 所指的链结点后面插入一个由

10、p 所指的链结点的操作依次为p->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->prior->

11、;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)/229、 在长度为n的顺序表的第i( K i < n+)个位置上插入一个元素，元素的移动次数是(A )。A. n-i+1 B. n-i C. i D. i-130、 在线性表的以下存储结构中，读取元素花费时间最少的是(D)。A. 单链表 B. 双链表 C. 循环链表 D. 顺序表31、 在以单链表为

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

13、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)第三章1、 栈和队列的共同点是(C )A. 都是先进后出 B. 都是先进先出在 C. 只允许在端点处插入和删除元素D.

14、 没有共同点2、 一个栈的进栈顺序是a,b,c,d,e,那么栈的出栈顺序不可能是( C )A. edcba B.decbaC. dceab D. adcbe3、设n个元素的进栈序列为 1,2,3,n，出栈序列为p1,p2,p3, ,pn,假设p仁n,那么pi(1<=i<=n) 的值为( C )。A. i B. n-i C.n-i+1 D.有多种可能4、判断下面的说法是否正确1) 插入和删除操作比拟简单,是链式栈和链式队列的优点之一。X2) 堆栈允许删除的一端称为栈顶,而栈底元素是不能删除的。5、设有一个顺序栈S ，元素 s1,s2,s3,s4,s5,s6 依次进栈，如果 6 个元素

15、的出栈顺序为s2,s3,s4,s6,s5,s1,那么顺序栈的容量至少应为多少？6、 假设数组 s0.n-1 为两个栈， s1 和 s2 的共用存储空间，且仅当 s0.n-1 全满时，各栈才不 能进行进栈操作，那么为这两个栈分配空间的最正确方案是：si和s2的栈顶指针的初值分别为 ( C )。A. 1 和 n+1 B. 1 和 n/2 C. -1 和 n D. -1 和 n+17、 判定一个顺序栈st (最多元素为 Maxsize)为空的条件为(B)，判断栈满的条件为(D ).A. st.top!=-1 B. st.top=0 C.st.top!=Maxsize D.st.top=Maxsize

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

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

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

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