数据结构试题及答案

数据结构试题及答案

数据结构试题 一、 单选题

1、 在数据结构的讨论中把数据结构从逻辑上分为 (C ) A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。

2、采用线性链表表示一个向量时，要求占用的存储空间地址(D ) A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续

3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为( D )。

A n B n/2 C (n-1)/2 D (n+1)/2

4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行( D )。

A s?link = p?link; p?link = s; B p?link = s; s?link = q; C p?link = s?link; s?link = p; D q?link = s; s?link = p;

5、如果想在4092个数据中只需要选择其中最小的5个，采用( C )方法最好。

A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序

6、设有两个串t和p，求p在t中首次出现的位置的运算叫做 ( B )。

A 求子串 B 模式匹配 C 串替换 D 串连接

7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是( C )。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用( A )。

A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为( C )。

10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是( D )。 A ( front - rear + 1) % m B ( rear - front + 1) % m

C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与( A )的表示等价。 A *(a+i) B a+i C *a+i D &a+i

12、若需要利用形参直接访问实参，则应把形参变量说明为( B )参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为( C ) for (int i=0;i

22A O(m) B O(n) C O(m*n) D O(m+n) B ) 14、下面程序段的时间复杂度为( int f(unsigned int n) { if(n= =0 || n= =1) return 1; else return n*f(n-1); }

2A O(1) B O(n) C O(n) D O(n!)

15、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址( D )。

A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 连续或不连续都可以

16、数据结构的定义为(D，S)，其中D是( B )的集合。 A 算法 B数据元素 C 数据操作 D 逻辑

结构

17、算法分析的目的是( A )。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易懂性和文档性

18、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( B )。

A s->link=p;p->link=s;

B s->link=p->link;p->link=s; C s->link=p->link;p=s; D p->link=s;s->link=p;

19、设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q 与*p之间插入结点*s，则应执行下列哪一个操作( B )

A s->link=p->link; p->link=s; B q->link=s; s->link=p

C p->link=s->link; s->link=p; D p->link=s; s->link=q;

20、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继，则应执行下列哪一个操作( A )

A p->link=p->link->link;

B p=p->link; p->link=p->link->link;

C p->link=p->link; D p=p->link->link; 21、设单循环链表中结点的结构为(data,link),且rear是指向非

空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个 结点，则应执行下列哪一个操作( D ) A s=rear; rear=rear->link; delete s; B rear=rear->link; delete rear;

C rear=rear->link->link; delete rear; D s=rear->link->link; rear->link->link=s->link; delete s;s

为第一个结点硫

22、设单循环链表中结点的结构为(data,link),且first为指向链 表表头的指针，current为链表当前指针，在循环链表中检测current 是否达到链表表尾的语句是( D )。

A current->link =null B first->link=current C first=current D current->link=first

,23、一个栈的入栈序列为a，b，c，则出栈序列不可能的是( C )。 A c,b,a B b,a,c C c,a,b D a,c,b 24、栈的数组表示中，top为栈顶指针，栈空的条件是( A )。

A top=0 B top=maxSize C top=maxSize D top=-1 25、栈和队列的共同特点是( C )。

A 都是先进后出 B 都是先进先出

C 只允许在端点处插入和删除 D 没有共同点

26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r , 则判断队空的条件为( D ).

A f+1= =r B r+1= =f C f= =0 D f= =r 27、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长

度为( B )

A n-2 B n-1 C n D n+1 28、当利用大小为n 的数组顺序存储一个栈时，假定用top= =n 表

示栈空，则向这个栈插入一个元素时，首先应执行( )语句修改 top指针。

A top++; B top--; C top=0; D top;

29、设链式栈中结点的结构为(data, link),且top是指向栈顶的 指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中， 则应执行下列( A )操作。

A x=top->data; top=top->link; B top=top->link; x=top->data;

C x=top; top=top->link; D x=top->data; 30、设循环队列的结构是: const int Maxsize=100; typedef int Data Type; typedef struct {