《数据结构》习题集
2014年8月
1
第一章——第五章 习题
一、 单选或填空题
1. 下列程序段中S语句的执行频度为 。
for(i＝0；i＜n；i++ ） for(j＝0；j＜i；j++ ）
S；
2. 下列算法的时间复杂度是（ ）。 for(i＝0；i＜n；i++ ） c[i]＝i；
3. 算法的时间复杂度可表示为 O(1)、线性
2n
阶 、平方阶O(n)、对数阶O(logn)和指数阶O(2)等。 4 以下关于数据结构的基本概念中，叙述正确的是 A) 数据元素是数据不可分割的最小单位。 B) 数据是数据对象的子集。
C) 数据元素之间的关系在计算机中可用顺序映像和非顺序映像两种不同的方法表示。
D) 数据结构在计算机中的表示又称为逻辑结构。 5. 在数据结构中，数据的逻辑结构包括（ ）。
线性结构和非线性结构 B) 逻辑结构和物理
结构
顺序结构和链式结构 D) 虚拟结构和抽象
结构
6. 在数据结构中，数据的存储结构包括 。
线性结构和非线性结构 B) 逻辑结构和物理结构
C) 顺序结构和链式结构 D) 虚拟结构和抽象结构
7. 线性结构的数据元素之间存在一种( )。 A．一对多关系 B．多对多关系 C．多对一关系 D．一对一关系
8. 在长度为n的顺序表中插入一个元素，需要平均移动 个元素。
A) n/2 B)n
C) n(n-1) D) n(n+1)
9. 在有n个元素的顺序表中做插入、删除运算，平均时间复杂度为 。
10. 顺序表中逻辑上相邻的元素物理位置 相邻，单链表中逻辑上相邻的元素的物理位置 相邻。
A)必然、必然 B)必然、不一定 C)不一定、必然 D)不一定、不一定
2
11．相对于顺序存储而言，链式存储的优点是（ ）。 A．随机存取 B．节约空间
C．增、删操作方便 D．节点间关系简单 12 以下关于头结点的描述中，叙述错误的是 ．．A) 头结点是对链表首元结点的别称
B) 若链表中附设头结点，则头指针一定不为空
C) 头结点中不存储链表的数据元素，而是一些诸如表长之类的辅助信息
D) 在单链表中附设头结点，插入或删除首元素时不必进行特殊处理
13．已知L是无表头结点的单链表，且P所指结点既不是首元结点，也不是尾元结点，则在P之后插入S所指结点，则执行（ ）。
A) S->next=P->next； P->next=S； B) P->next=S->next； S->next=P； C) S->next=P； P->next＝S； D) P->next=S； S->next=P；
14. 已知L是带表头结点的非空单链表，且P结点是S结点的直接前驱。则删除S结点的语句序列为 。
I. P->next = S ;free(P)
II. P->next = P->next->next; free(S) III. P->next = S->next; free(S) IV. P = P->next ;free(S)
A) I和II正确 B) II和 III正确 C) III和IV正确 D) 全部正确 15. 已知L是带表头结点的单链表，则删除首元结点的语句序列是（ ）。
A) L->next =L->next->next; free(L) B) P = L ;L= P->next ;free(P)
C) P = L->next ; L->next= P->next ;free(P) D) P = L ;L= P->next ;free(P)
16. 已知L是一带有头结点的单链表的头指针，则该单链表为空的条件是 。
17. 已知P结点是某双向链表的中间结点，则删除P结点的语句序列是 ， ，free(P);
18. 设将整数1，2，3，4，5依次进栈，最后都出栈，出栈可以在任何时刻(只要栈不空)进行，则出栈序列不可能的是（
3
）。
A) 32415 B) 45231 C) 32145 D) 45321
19. 设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列__________。
A) A, B, C, D, E B) B, C, D, E, A C) E, A, B, C, D D) E, D, C, B, A
20. 设有栈S和队列Q，其初始状态为空，元素a1,a2,a3,a4,a5,a6依次入栈，出栈的元素进入队列Q。若元素出队列的顺序是a2,a4,a3,a6,a5,a1，则栈的容量至少是 。
21. 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则abcde顺序入队，不可能得到的顺序是（ ）。
A．bacde B．dbace C．dbcae D．ecbad 22. 设用一维数组A[n]存储一个栈，令A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。当从栈中弹出一个元素时，变量T的变化为（ ）。
A) T=T+1 B) T=T-1 C) T不变 D) T=n-1 23. 在具有m个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是（ ）
A. front== (rear＋1) % m B. front＋1== rear C. front== rear D. rear== m 24. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是（ ） A)front== (rear＋1) % n B)front＋1==rear C)front==rear D)front==0
25. 循环队列用数组A[n]存放其数据元素。设f指向其实际的队头，r指向其实际队尾的下一个位置，则计算队列中元素个数的公式为 。
A) r-f B) (n+f-r)%n C) n+f-r D)
(n+r-f)%n
26 在串的运算中，StrLength(Concat (’aa’，’bb’))的返回值为
A) 0 B) 8 C) 6 D) 4
27．设s1＝”I have_”，s2＝”a dream”，则strcat(s1, s2)的值是 ，SubString(s1,4,3)的值是 。 28. 设s1＝”I am a student”，s2＝”a student”，则Index(s1,s2)的值是 。
29. 设二维数组A[0?m-1][0?n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为__________。
A．p +[i*n+j]*k B．p+[(i-1)*n+j-1]*k
4
C．p+[(j-1)*n+i-1]*k D．p+[j*n+i]*k 30. 一个非空广义表的表头（ ）。
A．一定是子表 B．一定是原子
C．不能是子表 D．可以是原子，也可以是子表 31. 设广义表L＝（(a,b),c,( )），则head(L)＝ ，tail(L)＝ 。
32. 设循环队列的存储空间为Queue[30]，初始状态为front=rear=0。现经过一系列入队与出队操作后，front=16,rear=15,则循环队列中有A)1 C)30 个元素。 D)0
B)29 33. 已知二维数组A[0..5，0..7]按行存放，其起始存储位置为1000，每个元素占用4个字节，则元素A[4,6]的第一个字节的地址为 。
A) 1148 B) 1168 C) 1152 D) 1172
二、
算法题 1. Status A(LinkedList L) {//L写出下列程序段的功能。If(L &&L->next){
是无表头结点的单链表
Q=L; L=L->next; P=L; 2. 简述以下算法的功能（栈的元素类型 While (P->next) P=P->next; Return OK; P->next=Q; Q->next=NULL; } }
SElemType为int）。{
(1) status algo1(Stack S) int i,n,A[255]; n=0;
while(!StackEmpty(S)) { n++; Pop(S,A[n]); } for(i=1;i<=n;i++) Push(S,A[i]); (2) status algo2(Stack S,int e) }
{
Stack T; int d; InitStack(T);
while(!StackEmpty(S)){ Pop(S,d);
if(d!=e) Push(T,d); }
while(!StackEmpty(T)){
5