1、完整版数据结构试题集包含答案完整版第一章 概论一、选择题1、研究数据结构就是研究（ D ）。A。 数据的逻辑结构 B。 数据的存储结构 C。 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A )。A。 空间复杂度和时间复杂度 B。 正确性和简单性 C。 可读性和文档性 D。 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ).A。 图 B。 树 C. 广义表 D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。A。 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性
2、C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C ）。 for（i=0；im；i+） for(j=0；jn;j+) aij=ij; A。 O（m2） B. O(n2) C. O(m*n） D. O（m+n）6、算法是（ D ）。A。 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列7、某算法的语句执行频度为(3n+nlog2n+n2+8），其时间复杂度表示（ C ）。A. O(n） B。 O(nlog2n） C. O（n2) D。 O（log2n）8、下面程序段的时间复杂度为( C ）。 i=1; while(i=n
3、) i=i3;A. O（n） B. O（3n） C. O(log3n） D. O(n3） 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（ ）和运算等的学科。A。 结构 B。 关系 C. 运算 D。 算法10、下面程序段的时间复杂度是（A ). i=s=0； while（snext=NULL C。 p=NULL D. p=head6、链表不具有的特点是( ）.A。 可随机访问任一元素 B. 插入删除不需要移动元素 C。 不必事先估计存储空间 D. 所需空间与线性表长度成正比7、在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（
4、 ）。 A。 p-next=q;qprior=p;p-nextprior=q;qnext=q； B。 p-next=q；pnextprior=q;qprior=p;qnext=p-next； C。 qprior=p;q-next=pnext;p-nextprior=q;p-next=q; D。 qnext=p-next;q-prior=p；p-next=q;p-next=q；8、线性表采用链式存储时，结点的存储地址( ).A. 必须是连续的 B。 必须是不连续的 C。 连续与否均可 D. 和头结点的存储地址相连续9、在一个长度为n的顺序表中删除第i个元素，需要向前移动（ ）个元素.A. ni
5、B. n-i+1 C。 n-i-1 D. i+110、线性表是n个（ ）的有限序列。A。 表元素 B。 字符 C。 数据元素 D. 数据项 11、从表中任一结点出发，都能扫描整个表的是( ）。A。 单链表 B. 顺序表 C。 循环链表 D. 静态链表12、在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（ )。A. O(n) B。 O（1） C。 O（n2) D。 O（n1）13、线性表L=（a1，a2，an)，下列说法正确的是（ ）。A. 每个元素都有一个直接前驱和一个直接后继 B。 线性表中至少要有一个元素C。 表中诸元素的排列顺序必须是由小到大或由大到小 D. 除第一个和最后一
6、个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继14、一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的存储地址是（ ）.A. 98 B。 100 C。 102 D。 10615、在线性表的下列存储结构中，读取元素花费的时间最少的是（ ). A. 单链表 B。 双链表 C. 循环链表 D. 顺序表16、在一个单链表中，若删除p所指向结点的后续结点,则执行（ ）。A。 pnext=p-nextnext;B. p=p-next；pnext=pnext-next;C. p =p-next;D。 p=p-next-next;17、将长度为n的单链表连接在长度为m的单链
7、表之后的算法的时间复杂度为（ ）.A。 O（1） B. O（n) C。 O（m） D. O（m+n)18、线性表的顺序存储结构是一种（ ）存储结构。A。 随机存取 B. 顺序存取 C。 索引存取 D。 散列存取 19、顺序表中，插入一个元素所需移动的元素平均数是( ）. A. (n1)/2 B。 n C. n+1 D。 （n+1）/210、循环链表的主要优点是( ）.A。 不再需要头指针 B。 已知某结点位置后能容易找到其直接前驱 C。 在进行插入、删除运算时能保证链表不断开 D. 在表中任一结点出发都能扫描整个链表 11、不带头结点的单链表head为空的判定条件是（ A ）.A。 head=
8、NULL B。 headnext=NULL C。 head-next=head D。 head！=NULL答案B是带头结点的12、在下列对顺序表进行的操作中,算法时间复杂度为O(1）的是（ ）. A. 访问第i个元素的前驱（1) B. 在第i个元素之后插入一个新元素（） C。 删除第i个元素(） D. 对顺序表中元素进行排序答案是A.假设顺序表L,长度为n，求第i个节点Li,直接前驱Li-1，因此为O（1）答案B需要移动ni+1个节点，因此为O(n)答案C也需要移动n-i个节点答案D根据排序方法不同最慢O(n2)，最快O（nlogn)13、已知指针p和q分别指向某单链表中第一个结点和最后一个结
9、点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为( )。A. qnext=s-next；snext=p； B. s-next=p;q-next=snext； C。 pnext=s-next；s-next=q; D。 snext=q；p-next=snext；14、在以下的叙述中，正确的是（ )。 A. 线性表的顺序存储结构优于链表存储结构 B。 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况 C。 线性表的链表存储结构适用于频繁插入/删除数据元素的情况 D。 线性表的链表存储结构优于顺序存储结构15、在表长为n的顺序表中，当在任何位置删除一个元素的
10、概率相同时，删除一个元素所需移动的平均个数为（ ）.A。 (n-1)/2 B. n/2 C. (n+1）/2 D。 n16、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入一个结点s，则执行( ).A. s-next=pnext; pnext=s； B. p-next=snext；snext=p; C. qnext=s；snext=p; D. p-next=s；s-next=q； 17、在单链表中,指针p指向元素为x的结点,实现删除x的后继的语句是( )。A. p=pnext； B. pnext=p-nextnext; C. p-next=p; D。 p=pnext-n
11、ext；18、在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若pnextnext=head,则（ ）。A. p指向头结点 B. p指向尾结点 C. p的直接后继是头结点 D。 p的直接后继是尾结点二、填空题1、设单链表的结点结构为（data,next）。已知指针p指向单链表中的结点,q指向新结点,欲将q插入到p结点之后，则需要执行的语句： ; .答案：qnext=p-next p-next=q2、线性表的逻辑结构是 ，其所含元素的个数称为线性表的 。答案：线性结构 长度3、写出带头结点的双向循环链表L为空表的条件 。答案:L-prior=Lnext=L4、带头结点的单链
12、表head为空的条件是 。答案:headnext=NULL5、在一个单链表中删除p所指结点的后继结点时，应执行以下操作:q = p-next；p-next= _ qnext _； 三、判断题1、单链表不是一种随机存储结构。 2、在具有头结点的单链表中,头指针指向链表的第一个数据结点. 3、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。 4、顺序存储方式只能用于存储线性结构。 5、在线性表的顺序存储结构中，逻辑上相邻的两个元素但是在物理位置上不一定是相邻的. 6、链式存储的线性表可以随机存取。X四、程序分析填空题1、函数GetElem实现返回单链表的第i个元素,请在空格处将
13、算法补充完整。 int GetElem(LinkList L,int i，Elemtype e) LinkList p;int j；p=L-next;j=1; while（pjdata2、函数实现单链表的插入算法,请在空格处将算法补充完整。int ListInsert(LinkList L,int i,ElemType e） LNode *p，s；int j; p=L;j=0; while(（p！=NULL)&(jnext;j+； if（p=NULLji-1） return ERROR; s=(LNode )malloc(sizeof(LNode); s-data=e； (1） ; (2) ;
14、 return OK;/ListInsert*/答案：(1）s-next=p-next （2）p-next=s3、函数ListDelete_sq实现顺序表删除算法,请在空格处将算法补充完整。int ListDelete_sq(Sqlist L，int i） int k； if(i1|iL-length） return ERROR;for（k=i1;kLlength1；k+) L-slistk= （1） ; （2) ； return OK；答案：（1)Lslistk+1 （2） -LLength 4、函数实现单链表的删除算法，请在空格处将算法补充完整。int ListDelete（LinkLis
15、t L，int i,ElemType s) LNode p，q； int j； p=L；j=0; while（( （1) )&（ji1） return ERROR; q=p-next; （2） ; *s=qdata; free(q); return OK;/*listDelete*/答案：（1)pnext!=NULL （2）pnext=qnext5、写出算法的功能.int L(head) node * head; int n=0; node *p; p=head; while（p!=NULL) p=p-next； n+； return（n）; 答案:求单链表head的长度五、综合题1、编写算法
16、，实现带头结点单链表的逆置算法.答案:void invent(Lnode *head) Lnode *p，*q； if(！head-next） return ERROR; p=head-next； q=p-next； p-next =NULL； while(q) p=q； q=qnext; pnext=headnext； head-next=p; 2、有两个循环链表，链头指针分别为L1和L2，要求写出算法将L2链表链到L1链表之后,且连接后仍保持循环链表形式。答案：void merge（Lnode L1， Lnode *L2) Lnode *p，*q ; while（p-next!=L1）p=
17、p-next;while（qnext!=L2)q=qnext;q-next=L1; pnext =L2; 3、设一个带头结点的单向链表的头指针为head，设计算法，将链表的记录，按照data域的值递增排序。答案：void assending(Lnode *head） Lnode p，*q ， *r, s； p=head-next； q=p-next; p-next=NULL； while(q)r=q; q=qnext;if（rdata=pdata） r-next=p； headnext=r; p=r； elsewhile（!p & rdatap-data)s=p; p=pnext； r-nex
18、t=p； s-next=r；p=headnext； 4、编写算法，将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度.答案:void linklist_c(Lnode head) Lnode p； p=head; if（!p） return ERROR；while（p-next！=NULL）p=pnext；pnext=head; 设单链表的长度（数据结点数)为N,则该算法的时间主要花费在查找链表最后一个结点上（算法中的while循环),所以该算法的时间复杂度为O（N).5、已知head为带头结点的单循环链表的头指针，链表中的数据元素依次为（a1，a2，a3，
19、a4,，an）,A为指向空的顺序表的指针.阅读以下程序段，并回答问题:(1)写出执行下列程序段后的顺序表A中的数据元素;（2）简要叙述该程序段的功能。if（headnext！=head)p=head-next；Alength=0；while（p-next！=head）p=pnext；A-dataA-length +=p-data;if（pnext！=head）p=pnext;答案： （1) （a2， a4, ， ) （2）将循环单链表中偶数结点位置的元素值写入顺序表A6、设顺序表va中的数据元数递增有序。试写一算法,将x插入到顺序表的适当位置上，以保持该表的有序性。答案：void Insert
20、_sq(Sqlist va， ElemType x) int i, j， n; n=length(va)； if(x=vai)van=x；elsei=0；while（xvai） i+;for（j=n1；j=I;j-)vaj+1=vaj；vai=x； n+; 7、假设线性表采用顺序存储结构,表中元素值为整型。阅读算法f2,设顺序表L=（3,7,3,2,1,1，8,7,3）,写出执行算法f2后的线性表L的数据元素,并描述该算法的功能。 void f2(SeqList L) int i,j，k;k=0；for（i=0；iLlength;i+) for(j=0；jnext； free（p）； p=he
21、ad; q=p; elseq-next=p-next; free(p）;p=q-next; elseq=p; p=p-next; 9、在带头结点的循环链表L中,结点的数据元素为整型，且按值递增有序存放.给定两个整数a和b,且arear=Q-front B。 Qrear=Q-front+1 C。 Qfront=(Qrear+1)n D. Qfront=（Qrear1）%n3、设计一个判别表达式中括号是否配对的算法，采用( ）数据结构最佳。A。 顺序表 B。 链表 C. 队列 D。 栈4、带头结点的单链表head为空的判定条件是( ）。A。 head=NULL B。 head-next=NULL
22、C. headnext!=NULL D. head!=NULL5、一个栈的输入序列为：1,2,3,4，则栈的不可能输出的序列是（ ）。A. 1243 B. 2134 C. 1432 D. 4312 E。 32146、若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0,3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。A. 1和5 B. 2和4 C。 4和2 D。 5和17、队列的插入操作是在( ）。A. 队尾 B. 队头 C. 队列任意位置 D. 队头元素后8、循环队列的队头和队尾指针分别为front和rear，则判断循环队列为空的条件是（ ）。A. front=rear B。 front=0 C. rear=0 D. front=rear+19、一个顺序栈S，其栈顶指针为top，则将元素e入栈的操作是（ ）。A. *S-top=e;S-top+; B. Stop+；Stop=e； C. *S-top=e D。 Stop=e;10、表达式a*(b+c)d的后缀表达式是（ )。A. abcd+ B。 abc+d C。 abc*+d- D. -+*abcd11、将递归算法转换成对应的非递归算法时，通常需要使用（ ）来保存中间结果。A。 队列 B。 栈 C。 链表 D. 树12、栈的插入和删除操作在（ ）。 A.
