2022年数据结构期中试卷及答案 .pdf
一、选择题（每小题2 分，共 30 分）1. 数据结构是（ D ） 。A一种数据类型 B数据的存储结构C一组性质相同的数据元素的集合D相互之间存在一种或多种特定关系的数据元素的集合2以下与数据的存储结构无关的术语是（ D ） 。A链队列 B. 链表 C. 顺序表 D. 栈3以下数据结构中， （ A ）是非线性数据结构A树 B字符串 C队 D栈4一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第 6 个元素的存储地址是（B） 。 A 98 B100 C102 D 106 5在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D ）。A插入 B删除 C排序 D查找6线性表采用链式存储时，其地址(D )。 A必须是连续的 B一定是不连续的 C 部分地址必须连续 D连续与否均可以7线性表是 (A ) 。A一个有限序列，可以为空 B一个有限序列，不可以为空C一个无限序列，可以为空 D一个无限序列，不可以为空8若进栈序列为1，2， 3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（B ）。A 3，2，6，1， 4，5 B3，4， 2，1，6，5 C1，2，5， 3，4，6 D5， 6，4，2，3，1 9. 若一个栈的输人序列是1，2，3， n，输出序列的第一个元素是n，则第 k 个输出元素是（C ） 。Ak Bn-k-1 Cn-k+1 D不确定10. 对于队列操作数据的原则是（ A ） 。A. 先进先出 B. 后进先出 C. 先进后出 D. 不分顺序11. 栈和队列的共同点是（ C ） 。A. 都是先进先出 B. 都是先进后出C. 只允许在端点处插入和删除元素 D. 没有共同点12在一个链队列中，假定front和 rear 分别为头指针和尾指针，删除一个结点的操作是（ A ） 。 Afront=front-next B rear=rear-next Crear-next=front D front-nextrear 13. 空串与空格串（ B ） 。 A相同 B不相同 C可能相同 D无法确定14. 串与普通的线性表相比较，它的特殊性体现在（C ） 。 A顺序的存储结构 B链接的存储结构 C数据元素是一个字符 D数据元素可以任意15. 串的长度是指（ B ） 。A.串中所含不同字母的个数 B.串中所含字符的个数C.串中所含不同字符的个数 D.串中所含非空格字符的个数二、填空题（每空2 分，共 20 分）1 线性表、栈和队列，串都是_线性 _结构。2 数据的基本单位是_数据元素 _。3 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_顺序 _存储结构。4 已知具有n 个元素的一维数组采用顺序存储结构，每个元素占k 个存储单元，第一个元素的地址为Loc(a1) ，那么，第i 个元素的存储地址Loc(ai)= Loc(a1)+(i-1)*k 。5 栈（ stack ）是限定在表尾进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为_栈顶 _，而另一端称为_栈底_。6 一个循环队列Q中，头指针和尾指针分别为Q.front和 Q.rear ，且最大队列长度为MaxQSize ，则判断队空的条件为 Q.rear=Q.front,判断队满的条件为 (Q.rear+1)%MaxQSize=Q.front。队列的长度为 (.rear-Q.front+MaxQSize )%MaxQSize 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 7 两个串相等的充分必要条件是两个串的长度相等，且各个对应位置的字符都相等。三、程序填空题（每空3 分，共 30 分）1. 在带头结点的单链表L中第 i 个数据元素之前插入数据元素e 的 C语言描述算法如下， 其中 L 为链表头结点指针。 请填充算法中标出的空白处，完成其功能。typedef struct node int data；struct node *next； linknode,*link；int ListInsert_L(link &L, int i, int e) Linknode *p；int j；p = L ； j = 0；while (p & j next ； +j ； / 寻找第 i-1个结点if (!p | j i-1) return 0； s=(link)malloc(sizeof(linknode) ；/ 生成新结点s s-data = e；s-next=p-next ； p-next = s； / 插入 L 中return 1； 2. 对顺序栈的C语言描述算法如下，其中top 为栈顶指针，请填充算法中标出的空白处，插入元素e 为新的栈顶元素。#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct char *base; char *top; int stacksize; SqStack; int Push( SqStack &S, char e) /if ( (s.top-s.base)=s.stacksize ) /栈满，追加存储空间 S.base=(SElemType *)realloc(S.base,S.stacksize+STACKINCREMENT) *sizeof(SElemType)；if (! S.base) return 0；S.top = s.base+s.stacksize ； /修改栈顶指针S.stacksize += STACKINCREMENT ； *s.top+=e ；/ 插入元素return 1； 3. 对链队列的C语言描述算法如下，请填充算法中标出的空白处，删除队列Q 的队头元素并用e 返回其值。typedef struct QNode QElemType data； struct QNode *next； QNode, *QueuePtr； typedef struct QueuePtr front； QueuePtr rear； LinkQueue；int DeQueue(LinkQueue &Q, QElemType &e) Linknode *p； if( Q.front=Q.rear ) retrun 0；/ 队列空，返回 p = Q.front - next； e = p-data； Q.front - next=p-next；/ 修改指针 if(Q.rear=p) Q.rear= Q.front ； /队列只有一个元素的情况 free(p) ；/ 释放结点空间 return 1； 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - 三、算法设计与分析题（每题10 分，共 20 分）1、简述下列算法实现的功能：（每题 5 分，共 10 分）（ 1）typedef struct LNode Char data; struct LNode *next; LNode,*LinkList; LinkList Demo(LinkList &L) / L 是无头结点单链表LNode *Q,*P; if(L&L-next) Q=L; L=L-next; P=L; while (P-next) P=P-next; P-next=Q; Q-next=NULL; return L; / Demo 答：将单链表的第一个结点删除，放到链尾。（2）#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct int *base; int *top; int stacksize; Stack; void Demo1( Stack &S, int m) Stack 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); 答：删除栈S中所有值为m的数据元素2. 有一个带头结点的单链表，头指针为head，编写一个算法计算所有数据域为X的结点的个数（不包括头结点）。typedef struct node int data; struct node *next; linknode,*link; int sample(link head, int X) int count=0; link p=head-next; while(p) if(p-data=X)count+; p=p-next; return count; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -
