《数据结构习题及标准答案》由会员分享，可在线阅读，更多相关《数据结构习题及标准答案（5页珍藏版）》请在金锄头文库上搜索。
1、第一章1在数据结构中，从逻辑上可以把数据结构分为（C ）A动态结构和静态结构 B. 紧凑结构和非紧凑结构C线性结构和非线性结构 D. 内部结构和外部结构l 2. 在数据结构中,与所使用的计算机无关的是( A )A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构3.下面程序的时间复杂度为_O（mn）_。 for (int i=1; i=m; i+) for (int j=1; jnext=null C head-next=head D head!=nulll 3.在线性表的下列存储结构中，读取元素花费时间最少的是（D）A 单链表 B 双链表 C 循环链表 D 顺序表l 4.对于
2、只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C)A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表l 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序，则操作的时间复杂度为( D )A O(1) B O(log2n) C O(n2) D O(n)l 6.在一个长度为n (n1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长度有关A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素l 7.与单链表相比，双向链表的优点之一是(D)A
3、插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易l 8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域(头结点的地址)中存放的是( B )A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址l 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=14811.在顺序表的（ 最后一个结点之后 ）插入一个新的数据元素不必移动任何元素。12.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（ 顺序 ）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用( 链 )存储结构。13、一个顺序表所占用存储空间的大小与（B）无关。l 14、设存储分配是从低地址到高地址进行的。若每个元素占用4个存储单元，则某元素的地址是指它所占用的单元的（A
5、）。A. 第1个单元的地址 B. 第2个单元的地址 C. 第3个单元的地址 D. 第4个单元的地址 15、若线性表采用顺序存储结构，每个元素占用4个存储单元，第1个元素的存储地址为100，则第12个元素的存储地址是（ B）。A. 112 B. 144 C.148 D. 412 l 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-next; p-next=q; C. q-next=p-n
6、ext; 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 ）。A. q
7、-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
8、 29、在长度为n的顺序表的第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-ne
9、xt=p-next-next Cp=p-next-next; 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. 只允许
10、在端点处插入和删除元素D. 没有共同点2、一个栈的进栈顺序是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=i=n)的值为（ C ）。A. i B. n-i C.n-i+1 D. 有多种可能 4、判断下面的说法是否正确（1）插入和删除操作比较简单，是链式栈和链式队列的优点之一。 X（2）堆栈允许删除的一端称为栈顶，而栈底元素是不能删除的。 X5、设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素
11、的出栈顺序为s2,s3,s4,s6,s5,s1，则顺序栈的容量至少应为多少？6、若数组s0.n-1为两个栈，s1和s2的共用存储空间，且仅当s0.n-1全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为（ C ）。A. 1和n+1 B. 1和n/2 C. -1和n D. -1和n+1 7、判定一个顺序栈st（最多元素为Maxsize）为空的条件为（ B ），判断栈满的条件为(D ).A. st.top!=-1 B. st.top=0 C.st.top!=Maxsize D.st.top=Maxsize 8、循环顺序队列中是否可以插入下一个元素，（ A ）A. 与队头指针和队尾指针的值有关 B. 只与队尾指针的值有关，与队头指针的值无关 C. 只与数组的大小有
