数据结构练习题及答案

得 分 评卷人 一、单项选择题（本大题共15小题，每小题2分，共30分） （1）一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ B ）

A）12345ABCDE B）EDCBA54321 C）ABCDE12345 D）54321EDCBA （2）下列叙述中正确的是（ D ）

A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构 B）在循环队列中，只需要队头指针就能反应队列中元素的动态变化情况 C）在循环队列中，只需要队尾指针就能反应队列中元素的动态变化情况 D）循环队列中元素的个数是由队头和队尾指针共同决定

（3）在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（ C ） A）O(N) B）O(n2) C）O(log2n) D）O(n log2n) （4）下列叙述中正确的是（ A ）

A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的 B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构 C）顺序存储结构能存储有序表，链式存储结构不能存储有序表

D）链式存储结构比顺序存储结构节省存储空间

（5）下列叙述中正确的是（ BD ）

A） 栈是“先进先出”的线性表 B） 队列是“先进先出”的线性表 C） 循环队列是非线性结构

D） 有序性表既可以采用顺序存储结构，也可以采用链式存储结构

（6）支持子程序调用的数据结构是（ A ） A） 栈 B） 树 C） 队列 D）二叉树

（7）某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是（ C ） A）10 B）8 C）6 D）4

（8）若一个算法的时间复杂度用T(n)表示，其中n的含义是（ A ） A．问题规模 B．语句条数 C．循环层数 D．函数数量 （9）具有线性结构的数据结构是（ C ）

A．树 B．图 C．栈和队列 D．广义表

（10）将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（ B ）

A．O(1) B．O(m) C．O(n) D．O(m+n)

（11）在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（ C ）

A．2个 B．3个 C．4个 D．6个

第 1 页 共 6 页

（12）假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ B ） A．3 B．37 C．50 D．97

（13）若栈采用链式存储结构，则下列说法中正确的是（ B ）

A．需要判断栈满且需要判断栈空 B．不需要判断栈满但需要判断栈空 C．需要判断栈满但不需要判断栈空 D．不需要判断栈满也不需要判断栈空 （14）若串str=”Software”，其子串的数目是（ C ） A．8 B．9 C．36 D．37

（15）设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为 （ C ） A．1012 B．1017 C．1032 D．1039 二、填空题（本大题共9小题，每空2分，共20分）

请在每小题的空格中填上正确答案。错填、不填均无分。

评卷人

1．假设一个长度为50的数组（数组元素的下标从0到49）作

为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有 19 个元素。

2.以下程序把三个NODETYPE型的变量链接成一个简单的链表，并在while循环中输出链表结点数据域中的数据，请填空 #include struct node {int data;

struct node *next;};

typedef struct node NODETYPE; void main()

{NODETYPE a,b,c,*h,*p;

a.data=10; b.data=20; c.data=30; h=&a; b.next=&b; b.next=&c; c.next=’\\0’; p=h;

while(p){printf(“&d”,p->data); p=p->next ；}} 3.数据元素及其关系在计算机存储器内的表示称为 (逻辑关系)。

4．长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是 (0（n）)。

5．下面是在顺序栈上实现的一个栈基本操作，该操作的功能是(取出栈顶元素)。 typedef struct{

DataType data[100]； int top； }SeqStack；

DataType f18(SeqStack*S) { if(StackEmpty(S))

Error(”Stack is empty”)； 得 分

第 2 页 共 6 页

return S->data[S->top]；}

6．数据的链式存储结构的特点是借助 (指针) 表示数据元素之间的逻辑关系。 7．如果需要对线性表频繁进行 (插入) 或 (删除) 操作，则不宜采用顺序存储结构。 8．如图所示，可以利用一个向量空间同时实现两个类型相同的栈。其中栈1为空的条件是top1=0，栈2为空的条件是top2=n-1，则“栈满”的判定条件是(top1==top-1、top2==top1+1)。

9. 若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现 （5）个不同的出栈序列。 三、简答题（本大题共6小题，第3小题10分，其余每小题8

得 分 分，共50分）

评卷人

1. 链栈中为何不设置头结点?

得分 链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果

加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。

2．循环队列的优点是什么? 如何判别它的空和满?

得分 循环队列的优点是：它可以克服顺序队列的\假上溢\现象，能够使存

储队列的向量空间得到充分的利用。判别循环队列的\空\或\满\不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。

3.指出下述程序段的功能是什么?

得分 (1) void Demo1(SeqStack *S){

int i; arr[64] ; n=0 ;

while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } //Demo1

(1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。 (2) SeqStack S1, S2, tmp;

第 3 页 共 6 页

DataType x;

...//假设栈tmp和S2已做过初始化 while ( ! StackEmpty (&S1)) {

x=Pop(&S1) ; Push(&tmp,x); }

while ( ! StackEmpty (&tmp) ) {

x=Pop( &tmp); Push( &S1,x); Push( &S2, x); }

(2)程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。 (3) void Demo2( SeqStack *S, int m) { // 设DataType 为int 型 SeqStack T; int i; InitStack (&T);

while (! StackEmpty( S))

if(( i=Pop(S)) !=m) Push( &T,i); while (! StackEmpty( &T)) {

i=Pop(&T); Push(S,i); } }

(3)程序段的功能是利用栈T，将一个非空栈S中值等于m的元素全部删去。 (4)void Demo3( CirQueue *Q)

{ // 设DataType 为int 型 int x; SeqStack S; InitStack( &S);

while (! QueueEmpty( Q ))

{x=DeQueue( Q); Push( &S,x);} while (! StackEmpty( &s))

{ x=Pop(&S); EnQueue( Q,x );} }// Demo3

(4)程序段的功能是将一个循环队列Q经过S栈的处理，反向排列，原来的队头变成队尾，原来的队尾变成队头。

(5) CirQueue Q1, Q2; // 设DataType 为int 型 int x, i , n= 0;

... // 设Q1已有内容， Q2已初始化过 while ( ! QueueEmpty( &Q1) )

第 4 页 共 6 页

{ x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n++;} for (i=0; i< n; i++)

{ x=DeQueue(&Q2) ;

EnQueue( &Q1, x) ; EnQueue( &Q2, x);}

(5)这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素复制到队列1中。

4. 为什么在单循环链表中设置尾指针比设置头指针更好?

得分 尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找

链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和 rear, 查找时间都是O(1)。

若用头指针来表示该链表，则查找终端结点的时间为O(n)。

5．已知下列程序，Ls指向带头结点的单链表。

得分 Typedefstruct node {

DataType data; struct node * next; } * LinkList;

void f30( LinkList Ls ) { LinkList p, q; q = Ls->next;

if ( q && q->next ) { Ls->next = q->next; p=q

while ( p->next ) p = p->next; p->next = q;

q->next = NULL; }}

请回答下列问题：

(1)当Ls指向的链表如下图所示，请画出执行本函数之后的链表的结果。

(2)请简述算法的功能。

（1）Ls -> 头节点 -> 2 -> 3 -> 4 -> 5 -> 1

（2）把首节点移至末端

6．假设学生成绩按学号增序存储在带头结点的单链表中，类型定义

得分 如下：

typedef struct Node { int id; /*学号*/

int score； /*成绩*/

第 5 页 共 6 页

struct Node *next； } LNode， *LinkList； 阅读算法f31，并回答问题： (1)设结点结构为

f31(A，B)后A所指的链表；

，成绩链表A和B如图所示，画出执行算法

(2)简述算法f31的功能。

void f31(LinkList A, LinkList B) { LinkList p, q; p=A->next; q=B->next; while (p && q)

{ if (p->idid) p=p->next; else if (p->id>q->id) q=q->next; else

{ if (p->score<60) if (q->score<60)

p->score=q->score; else p->score=60; p=p->next; q=q->next; } } }

（1）A -> 头节点 -> 1,70 -> 2,38 -> 3,90 -> 4,60 -> 5,60

（2）将链表A中与链表B中id值相同的节点，按照参照链表B中的score值不小于60取60，否则取原值的规则来更新链表A中的score值

第 6 页 共 6 页

struct Node *next； } LNode， *LinkList； 阅读算法f31，并回答问题： (1)设结点结构为

f31(A，B)后A所指的链表；

，成绩链表A和B如图所示，画出执行算法

(2)简述算法f31的功能。

void f31(LinkList A, LinkList B) { LinkList p, q; p=A->next; q=B->next; while (p && q)

{ if (p->idid) p=p->next; else if (p->id>q->id) q=q->next; else

{ if (p->score<60) if (q->score<60)

p->score=q->score; else p->score=60; p=p->next; q=q->next; } } }

（1）A -> 头节点 -> 1,70 -> 2,38 -> 3,90 -> 4,60 -> 5,60

（2）将链表A中与链表B中id值相同的节点，按照参照链表B中的score值不小于60取60，否则取原值的规则来更新链表A中的score值

第 6 页 共 6 页

本文来源：https://www.bwwdw.com/article/k0p3.html