2022年太原理工大学数据结构试题库及答案.docx

精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆数据结构试题库及答案第一章 概论一、选择题1、讨论数据结构就是讨论（ D ）；B. 数据的储备结构A. 数据的规律结构C. 数据的规律结构和储备结构D. 数据的规律结构、储备结构及其基本操作2、算法分析的两个主要方面是（ A ）； A. 空间复杂度和时间复杂度 B. 正确性和简洁性 C. 可读性和文档性 D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）；A. 图 B. 树 C. 广义表 D. 栈6、算法是（ D ）；A. 运算机程序 B. 解决问题的运算方法 C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog 2n+n 2+8 ）, 其时间复杂度表示（ C ）；A. On B. Onlog 2n C. On 2 D. Olog 2n 11 、抽象数据类型的三个组成部分分别为（ A ）；A. 数据对象、数据关系和基本操作 B. 数 据 元 素 、 逻 辑 结 构 和 存 储 结 构C. 数据项、数据元素和数据类型 二、填空题 三、综合题D. 数据元素、数据结构和数据类型1、将数量级O1,ON,ON2,ON3,ONLOG2N,OLOG2N,O2N 按增长率由小到大排序；答案：O1 Olog 2N ON ONlog 2N ON2 ON3 O2N 一、填空题1. 数据结构被形式地定义为 有限集合；（D, R ）,其中 D 是数据元素 的有限集合, R 是 D 上的 关系2. 数据结构包括数据的 规律结构 、数据的 储备结构 和数据的 运算 这三个方面的内容；3. 数据结构按规律结构可分为两大类,它们分别是线性结构 和非线性结构 ；名师归纳总结 8数据的储备结构可用四种基本的储备方法表示,它们分别是次序、链式、索引、第 1 页,共 37 页- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆散列 ；9. 数据的运算最常用的有5 种,它们分别是 插入、删除、修改、查找、排序；二、单项选择题（ C ）2. 数据结构中,与所使用的运算机无关的是数据的 结构；A 储备 B 物理 C 规律 D 物理和储备三、简答题1.数据结构和数据类型两个概念之间有区分吗？答：简洁地说,数据结构定义了一组按某些关系结合在一起的数组元素；数据类型不仅定义了一组带结构的数据元素,而且仍在其上定义了一组操作；2. 简述线性结构与非线性结构的不同点；答：线性结构反映结点间的规律关系是一对一的,点间的规律关系是多对多的；非线性结构反映结四、分析下面各程序段的时间复杂度2. s=0; 1. for i=0; i<n; i+ for i=0; i<n; i+ for j=0; j<m; j+ forj=0; j<n; j+ Aij=0;s+=Bij; sum=s; 3. x=0; 4. i=1; fori=1; i<n; i+ whilei<=n for j=1; j<=n-i; j+ i=i*3; x+; Mn nn nn log3n 五、设有数据规律结构S=（D,R）,试按各小题所给条件画出这些规律结构的图示,并确定其是哪种规律结构；名师归纳总结 1. D=d1,d2,d3,d4 R=d1,d2,d2,d3,d3,d4 第 2 页,共 37 页- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆2 D=d1,d2, ,d9 R=d1,d2,d1,d3,d3,d4,d3,d6,d6,d8,d4,d5, d6,d7,d8,d9 3D=d1,d2, ,d9 R=d1,d3,d1,d8,d2,d3,d2,d4,d2,d5,d3,d9, d5,d6,d8,d9,d9,d7, d4,d7, d4,d6 其次章 线性表一、选择题1、如长度为 n 的线性表采纳次序储备结构,杂度（）；在其第 i 个位置插入一个新元素算法的时间复A. Olog2n B.O1 C. On D.On2 ）2、如一个线性表中最常用的操作是取第i 个元素和找第i 个元素的前趋元素, 就采纳（储备方式最节约时间； A. 次序表 B. 单链表 C. 双链表 D. 单循环链表7、在双向循环链表中,在 p指针所指的结点后插入一个指针 q所指向的新结点,修改指针的操作是（ c ）；A. p->next=q;q->prior=p;p->next->prior=q;q->next=q; B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next; C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q; D. q->next=p->next;q->prior=p;p->next=q;p->next=q; 10 、线性表是 n 个（）的有限序列；A. 表元素 B. 字符 C. 数据元素 D. 数据项11 、从表中任一结点动身,都能扫描整个表的是（）；A. 单链表 B. 次序表 C. 循环链表 D. 静态链表12 、在具有 n个结点的单链表上查找值为 x 的元素时,其时间复杂度为（）；A. On B. O1 C. On 2 D. On-1 15 、在线性表的以下储备结构中,读取元素花费的时间最少的是（）； A. 单链表 B. 双链表 C. 循环链表 D. 次序表16 、在一个单链表中,如删除 p所指向结点的后续结点,就执行（）；A. p->next=p->next->next; B. p=p->next;p->next=p->next->next; C. p =p->next; D. p=p->next->next; 名师归纳总结 17 、将长度为 n 的单链表连接在长度为m的单链表之后的算法的时间复杂度为（）；第 3 页,共 37 页A. O1 B. On C. Om D. Om+n 18 、线性表的次序储备结构是一种（ a ）储备结构； N A. 随机存取B. 次序存取C. 索引存取D. 散列存取19 、次序表中,插入一个元素所需移动的元素平均数是（）； A. n-1/2 B. n C. n+1 D. n+1/211 、不带头结点的单链表head 为空的判定条件是（ b ）；A. head=NULL B. head->next=NULL - - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆C. head->next=head D. head.=NULL 12 、在以下对次序表进行的操作中,算法时间复杂度为 O1 的是（）；A. 拜访第 i个元素的前驱（1< i n）B. 在 第 i 个 元 素 之 后 插 入 一 个 新 元 素 1 i n C. 删除第 i个元素 1 i n D. 对次序表中元素进行排序13 、已知指针 p和q分别指向某单链表中第一个结点和最终一个结点；假设指针 s 指向另一个单链表中某个结点,就在 s 所指结点之后插入上述链表应执行的语句为（ a ）；A. q->next=s->next；s->next=p；B. s->next=p；q->next=s->next；C. p->next=s->next；s->next=q；D. s->next=q；p->next=s->next；15、在表长为 n 的次序表中, 当在任何位置删除一个元素的概率相同时,删除一个元素所需移动的平均个数为（ a ）；A. n-1/2 B. n/2 C. n+1/2 D. n 二、填空题1、设单链表的结点结构为（data,next）；已知指针 p 指向单链表中的结点,q指向新结点,；欲将 q插入到 p结点之后,就需要执行的语句：；答案： q->next=p->next p->next=q3、写出带头结点的双向循环链表L 为空表的条件；答案： L->prior=L->next=L5、在一个单链表中删除 p所指结点的后继结点时,应执行以下操作：q = p->next; p->next=_ q->next _; 三、判定题3、用循环单链表表示的链队列中,可以不设队头指针,仅在队尾设置队尾指针；x4、次序储备方式只能用于储备线性结构；5、在线性表的次序储备结构中,规律上相邻的两个元素但是在物理位置上不肯定是相邻的；6、链式储备的线性表可以随机存取；四、程序分析填空题1、函数 GetElem实现返回单链表的第i 个元素,请在空格处将算法补充完整；int GetElemLinkList L,int i,Elemtype *e LinkList p；int j；p=L->next;j=1; whilep&&j<i p=p->next ;+j; if.p|j>i return ERROR; *e= p->data ; return OK; 名师归纳总结 - - - - - - -第 4 页,共 37 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆2、函数实现单链表的插入算法,请在空格处将算法补充完整；int ListInsertLinkList L,int i,ElemType e LNode *p,*s;int j; p=L;j=0; whilep.=NULL&&j<i-1 p=p->next;j+; ifp=NULL|j>i-1 return ERROR; s=LNode *mallocsizeofLNode; s->data=e; s->next=p->next ; p->next=s ; return OK; /*ListInsert*/ 3、函数 ListDelete_sq 实现次序表删除算法,请在空格处将算法补充完整；int ListDelete_sqSqlist *L,int i int k; ifi<1|i>L->length return ERROR; fork=i-1;k<L->length-1;k+ L->slistk= L->slistk+1 ; ; -L->Length return OK; 4、函数实现单链表的删除算法,请在空格处将算法补充完整；int ListDeleteLinkList L,int i,ElemType *s LNode *p,*q; int j; p=L;j=0; while p->next.=NULL &&j<i-1 p=p->next;j+; ifp->next=NULL|j>i-1 return ERROR; q=p->next; p->next=q->next ; *s=q->data; freeq; return OK; /*listDelete*/ 5、写出算法的功能；int Lhead node * head; int n=0; node *p; p=head; whilep.=NULL 名师归纳总结 - - - - - - -第 5 页,共 37 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆 p=p->next; n+; returnn; 答案：求单链表 head的长度五、综合题1、编写算法,实现带头结点单链表的逆置算法；答案： void inventLnode *head Lnode *p,*q; if.head->next return ERROR; p=head->next; q=p->next; p->next =NULL; whileq p=q; q=q->next; p->next=head->next; head->next=p; 2、有两个循环链表,链头指针分别为L1 和 L2 ,要求写出算法将L2 链表链到L1 链表之后,且连接后仍保持循环链表形式；答案： void mergeLnode *L1, Lnode *L2 Lnode *p,*q ; whilep->next.=L1 p=p->next; whileq->next.=L2 q=q->next; q->next=L1; p->next =L2; 3、设一个带头结点的单向链表的头指针为head,设运算法,将链表的记录,依据data 域的值递增排序；答案： void assendingLnode *head Lnode *p,*q , *r, *s; p=head->next; q=p->next; p->next=NULL; whileq r=q; q=q->next; ifr->data<=p->data r->next=p; head->next=r; p=r; else while.p && r->data>p->data s=p; p=p->next; r->next=p; s->next=r; p=head->next; 4、编写算法 ,将一个头指针为 算法的时间复杂度；答案：head 不带头结点的单链表改造为一个单向循环链表,并分析void linklist_cLnode *head 名师归纳总结 - - - - - - -第 6 页,共 37 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆Lnode *p; p=head; if.p return ERROR; whilep->next.=NULL p=p->next; p->next=head; 设单链表的长度（数据结点数）为N,就该算法的时间主要花费在查找链表最终一个结点上（算法中的 while 循环）,所以该算法的时间复杂度为 O（N）；5 、已知 head 为带头结点的单循环链表的头指针,链表中的数据元素依次为（a1 ,a2,a3,a4, ,an ）,A 为指向空的次序表的指针；阅读以下程序段,并回答疑题：（1 ）写出执行以下程序段后的次序表 A中的数据元素；（2 ）简要表达该程序段的功能；ifhead->next.=head p=head->next; A->length=0; whilep->next.=head p=p->next; A->dataA->length +=p->data; ifp->next.=headp=p->next; 答案：1 a2, a4, , 2 将循环单链表中偶数结点位置的元素值写入次序表 A 6、设次序表 va 中的数据元数递增有序；试写一算法,将 x 插入到次序表的适当位置上,以 保持该表的有序性；答案：void Insert_sqSqlist va, ElemType x int i, j, n; n=lengthva; ifx>=vai van=x; else i=0; whilex>vai i+; forj=n-1;j>=I;j- vaj+1=vaj; vai=x; n+; 7 、 假 设 线 性 表 采 用 顺 序 存 储 结 构 , 表 中 元 素 值 为 整 型 ； 阅 读 算 法 f2 , 设 顺 序 表 L=3,7,3,2,1,1,8,7,3, 写出执行算法 f2 后的线性表 L的数据元素, 并描述该算法的功 能；名师归纳总结 - - - - - - -第 7 页,共 37 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆 void f2SeqList *L int i,j,k; k=0; fori=0;i<L->length;i+ forj=0;j<k && L->datai.=L->dataj;j+; ifj=k ifk.=iL->datak=L->datai; k+; L->length=k; 答案：3,7,2,1,8 删除次序表中重复的元素8、已知线性表中的元素以值递增有序排列,并以单链表作储备结构；试写一算法,删除表 中全部大于 x 且小于 y 的元素（如表中存在这样的元素）同时释放被删除结点空间；答案：void Delete_listLnode *head, ElemType x, ElemType y Lnode *p, *q; if.head return ERROR; p=head; q=p; while.p ifp->data>x && p->data<yi+; ifp=head head=p->next; freep; p=head; q=p; else q->next=p->next; freep; p=q->next; else q=p; p=p->next; 9、在带头结点的循环链表L 中,结点的数据元素为整型,且按值递增有序存放；给定两个整数 a 和 b,且 a<b,编写算法删除链表 L 中元素值大于 a 且小于 b 的全部结点；第三章 栈和队列一、选择题名师归纳总结 - - - - - - -第 8 页,共 37 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆2、判定一个循环队列Q（最多 n个元素）为满的条件是（c ）；A. Q->rear=Q->front B. Q->rear=Q->front+1 C. Q->front=Q->rear+1%n D. Q->front=Q->rear-1%n 3、设计一个判别表达式中括号是否配对的算法,采纳（）数据结构正确；A. 次序表 B. 链表 C. 队列 D. 栈4、带头结点的单链表 head 为空的判定条件是（）；A. head=NULL B. head->next=NULL C. head->next.=NULL D. head.=NULL 5、一个栈的输入序列为：1,2,3,4,就栈的不行能输出的序列是（）；A. 1243 B. 2134 C. 1432 D. 4312 E. 3214 6、如用一个大小为 6 的数组来实现循环队列,且当 rear 和 front 的值分别为 0,3；当从队列中删除一个元素,再加入两个元素后,rear 和front 的值分别为（）；A. 1 和5 B. 2 和4 C. 4 和2 D. 5 和1 7、队列的插入操作是在（）；A. 队尾 B. 队头 C. 队列任意位置 D. 队头元素后8、循环队列的队头和队尾指针分别为 front 和rear,就判定循环队列为空的条件是（）；A. front=rear B. front=0 C. rear=0 D. front=rear+1 9、一个次序栈 S,其栈顶指针为 top ,就将元素 e 入栈的操作是（）；A. *S->top=e;S->top+; B. S->top+;*S->top=e; C. *S->top=e D. S->top=e; 10 、表达式 a*b+c-d 的后缀表达式是（）；A. abcd+-B. abc+*d-C. abc*+d- D. -+*abcd 11 、将递归算法转换成对应的非递归算法时,通常需要使用（）来储存中间结果；名师归纳总结 A. 队列B. 栈C. 链表D. 树第 9 页,共 37 页12 、栈的插入和删除操作在（）； A. 栈底B. 栈顶C. 任意位置D. 指定位置13 、五节车厢以编号1,2,3,4,5次序进入铁路调度站（栈）,可以得到（）的编组；A. 3, 4,5,1 ,2 B. 2,4,1 ,3,5 C. 3, 5,4,2 ,1D. 1,3,5 ,2,4 14 、判定一个次序栈S（栈空间大小为n）为空的条件是（）；A. S->top=0 B. S->top.=0 C. S->top=n D. S->top.=n 15 、在一个链队列中,front和rear分别为头指针和尾指针,就插入一个结点s 的操作为（）；A. front=front->next B. s->next=rear;rear=s C. rear->next=s;rear=s;D. s->next=front;front=s; 16 、一个队列的入队序列是1,2 ,3 ,4,就队列的出队序列是（）；A. 1, 2,3,4B. 4,3 ,2 ,1C. 1, 4,3,2 D. 3,4 ,1 ,2 17 、依次在初始为空的队列中插入元素a,b,c,d以后,紧接着做了两次删除操作,此时的队头元素是（）；A. a B. b C. cD. d 18 、正常情形下, 删除非空的次序储备结构的堆栈的栈顶元素,栈顶指针 top 的变化是（）；- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆A. top不变 B. top=0 C. top=top+1 D. top=top-119 、判定一个循环队列Q（空间大小为M）为空的条件是（）；A. Q->front=Q->rear B. Q->rear-Q->front-1=M C. Q->front+1=Q->rear D. Q->rear+1=Q->front 20、设计一个判别表达式中左右括号是否配对显现的算法,采纳（）数据结构正确；A. 线性表的次序储备结构B. 队列C. 栈D. 线性表的链式存储结构21、当用大小为 N的数组储备次序循环队列时,该队列的最大长度为（）；A. N B. N+1 C. N-1 D. N-2 22、队列的删除操作是在（）；A. 队首 B. 队尾 C. 队前 D. 队后23、如让元素 1,2,3依次进栈,就出栈次序不行能是（）；A. 3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,224 、循环队列用数组 A0 ,m-1 存放其元素值,已知其头尾指针分别是 front 和rear,就当前队列中的元素个数是（）；A. rear-front+m%m B. rear-front+1 C. rear-front-1 D. rear-front 25 、在解决运算机主机和打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机就从该缓冲区中取走数据打印；该缓冲区应当是一个（）结构；C. 数组 D. 线性表A. 堆栈B. 队列26 、栈和队列都是（）；A. 链式储备的线性结构 C. 限制存取点的线性结构B. 链式储备的非线性结构 D. 限制存取点的非线性结构27 、在一个链队列中,假定 front 和 rear分别为队头指针和队尾指针,删除一个结点的操作是（）；A. front=front->next B. rear= rear->next C. rear->next=front D. front->next=rear 28、队和栈的主要区分是（）；A. 规律结构不同 B. 储备结构不同C. 所包含的运算个数不同 二、填空题D. 限定插入和删除的位置不同1、设栈 S和队列 Q的初始状态为空,元素 e1,e2,e3,e4,e5,e6 依次通过栈 S,一个元素出栈后即进入队列 Q,如 6个元素出队的序列是 e2,e4,e3,e6,e5,e1,就栈的容量至少应当是；答案： 3 2、一个循环队列 Q的储备空间大小为M, 其队头和队尾指针分别为front和rear,就循环队列中元素的个数为：；答案： rear-front+M%M3、在具有 n个元素的循环队列中,队满时具有 个元素；答案： n-1名师归纳总结 4、设循环队列的容量为70 ,现经过一系列的入队和出队操作后,front为20 ,rear为11 ,第 10 页,共 37 页就队列中元素的个数为；- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆答案： 615、已知循环队列的储备空间大小为20,且当前队列的头指针和尾指针的值分别为8和3,且该队列的当前的长度为_；三、判定题 1、栈和队列都是受限的线性结构；2、在单链表中,要拜访某个结点,只要知道该结点的地址即可；因此,单链表是一种随机 存取结构；3、以链表作为栈的储备结构,出栈操作必需判别栈空的情形；四、程序分析填空题1、已知栈的基本操作函数：int InitStackSqStack *S; / 构造空栈 int StackEmptySqStack *S;/ 判定栈空 int PushSqStack *S,ElemType e;/ 入栈int PopSqStack *S,ElemType *e;/ 出栈 函数 conversion 实现十进制数转换为八进制数,请将函数补充完整；void conversion InitStackS; scanf“ %d” ,&N; whileN （1） ; N=N/8; while （2） PopS,&e; “ %d” ,e; printf /conversion 答案：（1）PushS,N%8 （2）.StackEmptyS2、写出算法的功能；int functionSqQueue *Q,ElemType *e ifQ->front=Q->rear return ERROR; *e=Q->baseQ->front; Q->front=Q->front+1%MAXSIZE; return OK; 3、阅读算法 f2, 并回答以下问题：（1）设队列 Q=（ 1,3 ,5 ,2,4,6）；写出执行算法 f2 后的队列 Q; （2）简述算法 f2 的功能；void f2Queue *Q DataType e; if .QueueEmptyQ 名师归纳总结 - - - - - - -第 11 页,共 37 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆 e=DeQueueQ; f2Q; EnQueueQ,e; 答案：（1）6,4,2,5,3,1 （ 2）将队列倒置五、综合题1、假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾结点,但不设头指针,请写出相应的入队列算法（用函数实现）；rear答案： void EnQueueLnode *rear, ElemType e Lnode *new; New=Lnode *mallocsizeofLnode; If.new return ERROR; new->data=e; new->next=rear->next; rear->next=new; rear =new; S 是一个空栈；编写算法,仅用队列和栈的 ADT 函数和少量工 2、已知 Q 是一个非空队列,作变量,将队列 Q 的全部元素逆置；栈的 ADT 函数有：void makeEmptySqStack s; 置空栈 void pushSqStack s,ElemType e; 元素 e 入栈 ElemType popSqStack s; 出栈,返回栈顶元素 int isEmptySqStack s; 判定栈空 队列的 ADT 函数有：void enQueueQueue q,ElemType e; 元素 e 入队 ElemType deQueueQueue q; 出队,返回队头元素int isEmptyQueue q; 判定队空 答案： void QueueInventQueue q ElemType x; makeEmptySqStack s; while.isEmptyQueue q x=deQueueQueue q; pushSqStack s, ElemTypex; while.isEmptySqStack s x=popSqStack s; enQueueQueue q, ElemType x; 名师归纳总结 3、对于一个栈,给出输入项A,B,C,D,假如输入项序列为A,B,C,D,试给出全部可能的第 12 页,共 37 页- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆输出序列；答案：出栈的可能序列：ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BCDA CBDA CBAD CDBA DCBA 第五章 数组和广义表一、选择题1、设广义表 L=a,b,c,就 L的长度和深度分别为（ C ）；A. 1 和1 B. 1 和3 C. 1 和2 D. 2 和3 2、广义表 a,a 的表尾是（ B ）；A. a B. a C. D. a 3、稀疏矩阵的常见压缩储备方法有（ C ）两种；A. 二维数组和三维数组 B. 三元组和散列表 C. 三 元 组 和 十字链表 D. 散列表和十字链表4、一个非空广义表的表头（ D ）；A. 不行能是子表 B. 只能是子表 C. 只能是原子 D. 可以是子表或原子5、数组 A0.5,0.6 的每个元素占 5 个字节, 将其按列优先次序储备在起始地址为 1000的内存单元中,就元素 A55 的地址是（ A ）；A. 1175