数据结构习题及答案汇.doc

数据结构习题及答案 第1章 数据结构 一、选择题 1.算法指的是（）。 A计算机程序 B解决问题的计算方法 C排序方法 D解决问题的有限运算序列 2.在数据的树形结构中，数据元素之间为（ ）的关系。 A 0:0 B 1:1 C 1:n D m:n 3.数据的存储结构包括顺序、链接、散列和（ ）4种基本类型。 A索引 B数组 C集合 D向量 4.一个数组元素a[i]与（ ）的表示等价。 A a+i B *(a+i) C *a+i D a+i 5.若只需要利用形参间接访问实参指针所指向的对象，而形参本身具有相应的存储空间，则应把形参变量说明为（ ）参数。 A指针 B引用 C值 D指针引用 6.若只需要利用形参实现对实参值的拷贝，函数体操作形参时与实参无关，则应把形参变量说明为（ ）参数。 A指针 B引用 C值 D指针引用 7.下面程序的时间复杂性的量级为（）。 int i=0，s1=，s2=0； while（i++n） {if (i%2) s1+=i; else s2+=i; } A.O(1) B.O(1bn) C.O（n） D.O(2n) 8.下面程序段的时间复杂度为（ ）。 for(int i=0;im;i++) for(int j=0;jn;j++) a[i][j]=i*j; A.O(m2) B.O(n2) C.O(m+n) D.O(m*n) 9.执行下面程序段时，S语句的执行次数为（）。 for(int i=1;i=n;i++) for(int j=1,j=i;j++) S; A.n(n-1)/2 B.n(n+1)/2 C.n2/2 D.n 10.在一个长度为n的顺序存储结构的线性表中，向第i个元素（1≤i≤n+1）位置插入一个元素时，需要从后向前依次后移（）个元素。 A.n-i B.n-i+l C.n-i-l D.i 11. 在一个长度为n的顺序存储结构的线性表中，删除第i个元素（1≤i≤n+1）时，需要从前向后依次后移（）个元素。 A.n-i B.n-i+l C.n-i-l D.i 12.在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）。 A.(n+1)/2 B.n/2 C.n D.n+1 13.在一个顺序表的表尾插入一个元素的时间复杂度为（）。 A. O(n) B. O(1) C. O(n*n) D. O(lbn) 14.在一个顺序表中的任何位置插入一个元素的时间复杂度为（）。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 15.在一个单链表中删除p所指向结点的后继结点时，其算法的时间复杂度为（）。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 16.线性表的链式存储比顺序存储更有利于进行（）操作。 A.查找 B.表尾插入和删除 C.按值插入和删除 D.表头的插入和删除 17.线性表的顺序存储比链式存储更有利于进行（）操作。 A.查找 B.表尾插入和删除 C.按值插入和删除 D.表头的插入和删除 18.在一个单链表中，若要在P所指向的结点之后插入一个新结点，则需要相继修改（）个指针域的值. A.1 B.2 C.3 D.4 19.在一个带头结点的循环双向链表中，若要在P所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A.2 B.3 C.4 D.6 20.在一个表头指针为ph的单链表中，若要向表头插入一个由指针p指向的结点，则应执行（）操作。 A. ph=p; p-next=ph; B. p-next=ph; ph=p; C. p-next=ph; p=ph; D. p-next=ph-next; ph-next=p; 21.在一个表头指针为ph的单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）操作。 A. q-next=p-next; p-next=q; B. p-next=q-next; q=p; C. q-next=p-next; p-next=q; D. p-next=q-next; q-next=p; 22.在一个单链表HL中，若要删除由指针q所指向结点的后继结点（若存在的话），则执行（）操作。 A. p=q-next; p-next=q-next; B. p=q-next; q-next=p; C. p=q-next; q-next=p-next; D. q-next=q-next-next; q-nex