数据结构习题及标准答案

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.不带头结点的单链表hea

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

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

4、. 若 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.

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

6、B ）。A. 112B. 144C.148D. 41216、若长度为n 的线性表采用顺序存储结构，在表的第i 个位置插入一个数据元素，i的合法值应该是( D )。A. i>0B.i<=nC.1<=i<=nD. 1<=i<=n+117、若长度为n 的非空线性表采用顺序存储结构，删除表的第i 个数据元素， i 的合法值应该是（ C ）。A. i>0B.y<=nC.1<=i<=nD. d<=i<=i+118、若长度为n 的非空线性表采用顺序存储结构，删除表的第i 个数据元素， 首先需要移动表中（B ）个数据元素。A. n-iB.

7、n+iC. n-i+1D. n-i-119、若长度为n 的非空线性表采用顺序存储结构，在表的第i 个位置插入一个数据元素，首先需要移动表中（C ）个数据元素。A. iB. n+iC.n-i+1D.n-i-120、若频繁地对线性表进行插入和删除操作，该线性表应该采用（C ）存储结构。A. 散列B.顺序C.链式D.索引21、链表中的每一个链结点所占用的存储单元（B ）。A. 不必连续B.一定连续C.部分连续D.连续与否无所谓22、在一个具有n 个链结点的线性链表中查找某一个链结点，若查找成功， 需要平均比较（ C）个链结点。A. nB. n/2C.(n+1)/2D. (n-1)/223、给定具有n

8、 个元素的顺序表，建立一个有序线性链表的时间复杂度为（C ）。A. O(1)B.O(n)C.O(n2)D. O(log2n)24、在非空线性链表中由p 所指的链结点后面插入一个由q 所指的链结点的过程是依次执行（B）。A. q->next=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;

9、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=pB. q->next->prior=

10、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->next=p;C. p->next->prior=p; D. p->prior->next=p;28、顺序存储的线性表 (a1,a2,an), 在任一结点前插入一个新结点时所需移动结点的平均次数为（

11、D）。A. n B. n/2C. n+1D. (n+1)/229、在长度为 n 的顺序表的第i（ 1i n+1）个位置上插入一个元素，元素的移动次数是 ( A ) 。A. n-i+1B. n-i C. iD. i-130、在线性表的下列存储结构中，读取元素花费时间最少的是（D ）。A. 单链表B.双链表 C.循环链表D.顺序表31、在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（C ）。A.数据元素的相邻地址表示B.数据元素在表中的序号表示C.指向后继元素的指针表示D.数据元素的值表示25、假设指针p 指向单链表中的某一结点，若把 p 指针后面的结点删除，只需修改下列哪个指针值即可（

12、）。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->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 用（

13、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. edcbaB.decbaC. dceabD. adcbe3、设 n 个元素的进栈序列为 1,2,3, ,n ，出栈序列为 p1,p2,p3, ,pn ，若 p1=n，则 pi(1<=i<=n) 的值为（ C ）。A. iB. n-iC.n-i

14、+1D.有多种可能4、判断下面的说法是否正确（1）插入和删除操作比较简单，是链式栈和链式队列的优点之一。X（2）堆栈允许删除的一端称为栈顶，而栈底元素是不能删除的。X.5、设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6 依次进栈，如果6 个元素的出栈顺序为s2,s3,s4,s6,s5,s1，则顺序栈的容量至少应为多少？6、若数组s0.n-1 为两个栈， s1 和 s2 的共用存储空间，且仅当s0.n-1 全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1 和 s2 的栈顶指针的初值分别为（C）。A. 1 和 n+1B. 1和 n/2C. -1和 nD. -1和 n

15、+17、判定一个顺序栈st（最多元素为Maxsize ）为空的条件为 （ B ），判断栈满的条件为(D ).A. st.top!=-1B. st.top=0C.st.top!=MaxsizeD.st.top=Maxsize8、循环顺序队列中是否可以插入下一个元素，（ A ）A. 与队头指针和队尾指针的值有关B. 只与队尾指针的值有关，与队头指针的值无关C. 只与数组的大小有关，与队首头指针和队尾指针的值无关D. 与曾经进行过多少次插入操作有关9、若用一个大小为6 的一维数组来实现循环队列，且当前 rear和 front 的值分别为0和 3，当从队列中删除 1 个元素，然后再插入 2 个新元素后

16、， rear和 front的值分别为（B ）。A.1 和 5 B.2和4 C.4和2 D.5和 110、用单链表表示队列时，队头应该在单链表的（A）位置。A. 链头 B.链尾C. 链中 D.任意11、堆栈和队列的共同之处在于它们具有相同的（A）。A. 逻辑特性B.物理特性 C.运算方法 D.元素类型12、堆栈和队列都是特殊的线性表，其特殊性在于（C ）。A. 它们具有一般线性表所没有的逻辑特性B. 它们的存储结构特殊C. 对它们的使用方法做了限制D. 它们比一般线性表更简单13、若 5 个元素的出栈序列为1， 2， 3，4， 5，则进栈序列可能是（D）。A.24315 B.23154C. 31

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

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