数据结构试题库及答案.docx

数据构造试题库与答案第一章 概论一, 选择题1, 探讨数据构造就是探讨 D 。A. 数据的逻辑构造 B. 数据的存储构造 C. 数据的逻辑构造和存储构造 D. 数据的逻辑构造, 存储构造与其根本操作2, 算法分析的两个主要方面是 A 。 A. 空间困难度和时间困难度B. 正确性和简洁性 C. 可读性和文档性 D. 数据困难性和程序困难性3, 具有线性构造的数据构造是 D 。A. 图 B. 树C. 广义表 D. 栈4, 计算机中的算法指的是解决某一个问题的有限运算序列，它必需具备输入, 输出, B 等5个特性。A. 可执行性, 可移植性和可扩大性B. 可执行性, 有穷性和确定性C. 确定性, 有穷性和稳定性 D. 易读性, 稳定性和确定性5, 下面程序段的时间困难度是 C 。for(i=0;i<m;i+)for(j=0;j<n;j+)aij=i*j;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)i=i*3;A. O(n)B. O(3n)C. O(log3n) D. O(n3)9, 数据构造是一门探讨非数值计算的程序设计问题中计算机的数据元素以与它们之间的 和运算等的学科。A. 构造B. 关系C. 运算D. 算法10, 下面程序段的时间困难度是 。i=s=0;while(s<n)i+;s+=i;A. O(n) B. O(n2)C. O(log2n) D. O(n3)11, 抽象数据类型的三个组成局部分别为 。A. 数据对象, 数据关系和根本操作 B. 数据元素, 逻辑构造和存储构造 C. 数据项, 数据元素和数据类型 D. 数据元素, 数据构造和数据类型12, 通常从正确性, 易读性, 强健性, 高效性等4个方面评价算法的质量，以下说明错误的选项是 。A. 正确性算法应能正确地实现预定的功能B. 易读性算法应易于阅读和理解，以便调试, 修改和扩大C. 强健性当环境发生变更时，算法能适当地做出反响或进展处理，不会产生不须要的运行结果D. 高效性即到达所须要的时间性能13, 以下程序段的时间困难度为B。x=n;y=0;while(x>=(y+1)*(y+1)y=y+1;A. O(n) B. C.O(1) D. O(n2)二, 填空题1, 程序段“i=1;while(i<=n) i=i*2;的时间困难度为 。2, 数据构造的四种根本类型中， 树形构造 的元素是一对多关系。三, 综合题1, 将数量级O(1),O(N),O(N2),O(N3),O(NLOG2N),O(LOG2N),O(2N)按增长率由小到大排序。答案： O(1) O(log2N) O(N) O(Nlog2N) O(N2) O(N3) O(2N) 一, 填空题1. 数据构造被形式地定义为D, R，其中D是数据元素的有限集合，R是D上的关系有限集合。2. 数据构造包括数据的逻辑构造, 数据的存储构造和数据的运算这三个方面的内容。3. 数据构造按逻辑构造可分为两大类，它们分别是线性构造和非线性构造。4. 线性构造中元素之间存在一对一关系，树形构造中元素之间存在一对多关系，图形构造中元素之间存在多对多关系。5 在线性构造中，第一个结点没有前驱结点，其余每个结点有且只有 1个前驱结点；最终一个结点没有后续结点，其余每个结点有且只有1个后续结点。6. 在树形构造中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以随意多个。7. 在图形构造中，每个结点的前驱结点数和后续结点数可以随意多个。8数据的存储构造可用四种根本的存储方法表示，它们分别是依次, 链式, 索引, 散列。9. 数据的运算最常用的有5种，它们分别是插入, 删除, 修改, 查找, 排序。10. 一个算法的效率可分为时间效率和空间效率。11. 任何一个C程序都由一个主函数和假设干个被调用的其它函数组成。二, 单项选择题 B 1. 非线性构造是数据元素之间存在一种：A一对多关系 B多对多关系 C多对一关系 D一对一关系 C 2. 数据构造中，与所运用的计算机无关的是数据的 构造；A) 存储 B) 物理 C) 逻辑 D) 物理和存储 C 3. 算法分析的目的是：A) 找出数据构造的合理性 B) 探讨算法中的输入和输出的关系C) 分析算法的效率以求改良 D) 分析算法的易懂性和文档性 A 4. 算法分析的两个主要方面5是：A) 空间困难性和时间困难性 B) 正确性和简明性C) 可读性和文档性 D) 数据困难性和程序困难性 C 5. 计算机算法指的是：A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法 B 6. 计算机算法必需具备输入, 输出和 等5个特性。A) 可行性, 可移植性和可扩大性 B) 可行性, 确定性和有穷性C) 确定性, 有穷性和稳定性 D) 易读性, 稳定性和平安性三, 简答题1.数据构造和数据类型两个概念之间有区分吗？ 答：简洁地说，数据构造定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带构造的数据元素，而且还在其上定义了一组操作。2. 简述线性构造与非线性构造的不同点。答：线性构造反映结点间的逻辑关系是一对一的，非线性构造反映结点间的逻辑关系是多对多的。四, 分析下面各程序段的时间困难度2. s=0; for (i=0; i<n; i+)for(j=0; j<n; j+) s+=Bij;sum=s; 1. for (i=0; i<n; i+)for (j=0; j<m; j+)Aij=0; 3. x=0;for(i=1; i<n; i+) for (j=1; j<=n-i; j+)x+; 4. i=1; while(i<=n) i=i*3; 五, 设有数据逻辑构造S=D,R，试按各小题所给条件画出这些逻辑构造的图示，并确定其是哪种逻辑构造。 1. D=d1,d2,d3,d4 R=(d1,d2),(d2,d3),(d3,d4) 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. O(log2n) B.O(1)C. O(n) D.O(n2)2, 假设一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，那么采纳 存储方式最节约时间。 A. 依次表 B. 单链表 C. 双链表 D. 单循环链表3, 具有线性构造的数据构造是 。A. 图 B. 树C. 广义表 D. 栈4, 在一个长度为n的依次表中，在第i个元素之前插入一个新元素时，需向后移动 个元素。A. n-i B. n-i+1C. n-i-1 D. i5, 非空的循环单链表head的尾结点p满意 。A. p->next=head B. p->next=NULL C. p=NULL D. p=head6, 链表不具有的特点是 。A. 可随机访问任一元素B. 插入删除不须要移动元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正比7, 在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是 。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;8, 线性表采纳链式存储时，结点的存储地址 。A. 必需是连续的B. 必需是不连续的C. 连续与否均可 D. 和头结点的存储地址相连续9, 在一个长度为n的依次表中删除第i个元素，须要向前移动 个元素。A. n-i B. n-i+1C. 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(n-1)13, 线性表L=(a1,a2,an)，以下说法正确的选项是 。A. 每个元素都有一个干脆前驱和一个干脆后继 B. 线性表中至少要有一个元素C. 表中诸元素的排列依次必需是由小到大或由大到小D. 除第一个和最终一个元素外，其余每个元素都由一个且仅有一个干脆前驱和干脆后继14, 一个依次表的第一个元素的存储地址是90，每个元素的长度为2，那么第6个元素的存储地址是 。A. 98 B. 100C. 102 D. 10615, 在线性表的以下存储构造中，读取元素花费的时间最少的是 。 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的单链表之后的算法的时间困难度为 。A. O(1)B. O(n)C. O(m)D. O(m+n)18, 线性表的依次存储构造是一种 存储构造。A. 随机存取B. 依次存取C. 索引存取D. 散列存取19, 依次表中，插入一个元素所需移动的元素平均数是 。 A. (n-1)/2 B. n C. n+1 D. (n+1)/210, 循环链表的主要优点是 。A. 不再须要头指针 B. 某结点位置后能简洁找到其干脆前驱 C. 在进展插入, 删除运算时能保证链表不断开 D. 在表中任一结点动身都能扫描整个链表11, 不带头结点的单链表head为空的判定条件是 。A. head=NULL B. head->next=NULL C. head->next=head D. head!=NULL12, 在以下对依次表进展的操作中，算法时间困难度为O(1)的是 。A. 访问第i个元素的前驱1<B. 在第i个元素之后插入一个新元素()C. 删除第i个元素()D. 对依次表中元素进展排序13, 指针p和q分别指向某单链表中第一个结点和最终一个结点。假设指针s指向另一个单链表中某个结点，那么在s所指结点之后插入上述链表应执行的语句为 。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；14, 在以下的表达中，正确的选项是 。A. 线性表的依次存储构造优于链表存储构造B. 线性表的依次存储构造适用于频繁插入/删除数据元素的状况C. 线性表的链表存储构造适用于频繁插入/删除数据元素的状况D. 线性表的链表存储构造优于依次存储构造15, 在表长为n的依次表中，当在任何位置删除一个元素的概率一样时，删除一个元素所需移动的平均个数为 。A. (n-1)/2 B. n/2 C. (n+1)/2D. n16, 在一个单链表中，q所指结点是p所指结点的前驱结点，假设在q和p之间插入一个结点s，那么执行 。A. s->next=p->next; p->next=s; B. p->next=s->next;s->next=p; C. q->next=s;s->next=p; D. p->next=s;s->next=q;17, 在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是 。A. p=p->next; B. p->next=p->next->next; C. p->next=p;D. p=p->next->next;18, 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，假设p->next->next=head，那么 。A. p指向头结点B. p指向尾结点C. p的干脆后继是头结点D. p的干脆后继是尾结点二, 填空题1, 设单链表的结点构造为data,next。指针p指向单链表中的结点，q指向新结点，欲将q插入到p结点之后，那么须要执行的语句： ； 。答案：q->next=p->next p->next=q2, 线性表的逻辑构造是 ，其所含元素的个数称为线性表的 。答案：线性构造 长度3, 写出带头结点的双向循环链表L为空表的条件 。答案：L->prior=L->next=L4, 带头结点的单链表head为空的条件是 。答案：head->next=NULL5, 在一个单链表中删除p所指结点的后继结点时，应执行以下操作：q = p->next;p->next=_ _;答案：q->next三, 推断题1, 单链表不是一种随机存储构造。 P2, 在具有头结点的单链表中，头指针指向链表的第一个数据结点。O3, 用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。P4, 依次存储方式只能用于存储线性构造。O5, 在线性表的依次存储构造中，逻辑上相邻的两个元素但是在物理位置上不确定是相邻的。O6, 链式存储的线性表可以随机存取。O 四, 程序分析填空题1, 函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。int GetElem(LinkList L,int i,Elemtype *e)LinkList p；int j；p=L->next;j=1;while(p&&j<i) (1) ;+j;if(!p|j>i) return ERROR;*e= (2) ;return OK;答案：(1)p=p->next (2)p->data2, 函数实现单链表的插入算法，请在空格处将算法补充完整。int ListInsert(LinkList L,int i,ElemType e) LNode *p,*s;int j; p=L;j=0; while(p!=NULL)&&(j<i-1) p=p->next;j+; if(p=NULL|j>i-1) return ERROR; s=(LNode *)malloc(sizeof(LNode); s->data=e; (1) ; (2) ; return OK;/*ListInsert*/答案：(1)s->next=p->next (2)p->next=s3, 函数ListDelete_sq实现依次表删除算法，请在空格处将算法补充完整。int ListDelete_sq(Sqlist *L,int i) int k; if(i<1|i>L->length) return ERROR;for(k=i-1;k<L->length-1;k+) L->slistk= 1 ; 2 ; return OK;答案：1L->slistk+1 2 -L->Length 4, 函数实现单链表的删除算法，请在空格处将算法补充完整。int ListDelete(LinkList L,int i,ElemType *s) LNode *p,*q; int j; p=L;j=0; while( 1 )&&(j<i-1) p=p->next;j+; if(p->next=NULL|j>i-1) return ERROR; q=p->next; 2 ; *s=q->data; free(q); return OK;/*listDelete*/答案：(1)p->next!=NULL (2)p->next=q->next5, 写出算法的功能。int L(head)node * head;int n=0;node *p;p=head;while(p!=NULL) p=p->next; n+; return(n);答案：求单链表head的长度五, 综合题1, 编写算法，实现带头结点单链表的逆置算法。答案：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=q->next; p->next=head->next; head->next=p; 2, 有两个循环链表，链头指针分别为L1和L2，要求写出算法将L2链表链到L1链表之后，且连接后仍保持循环链表形式。答案：void merge(Lnode *L1, Lnode *L2) Lnode *p,*q ; while(p->next!=L1)p=p->next;while(q->next!=L2)q=q->next;q->next=L1; p->next =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=q->next;if(r->data<=p->data) r->next=p; head->next=r; p=r; elsewhile(!p && r->data>p->data)s=p; p=p->next; r->next=p; s->next=r;p=head->next; 4, 编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间困难度。答案：void linklist_c(Lnode *head) Lnode *p; p=head; if(!p) return ERROR;while(p->next!=NULL)p=p->next;p->next=head; 设单链表的长度数据结点数为N，那么该算法的时间主要花费在查找链表最终一个结点上算法中的while循环，所以该算法的时间困难度为ON。5, head为带头结点的单循环链表的头指针，链表中的数据元素依次为a1，a2,a3,a4,an,A为指向空的依次表的指针。阅读以下程序段，并答复以下问题：1写出执行以下程序段后的依次表A中的数据元素；2简要表达该程序段的功能。if(head->next!=head)p=head->next;A->length=0;while(p->next!=head)p=p->next;A->dataA->length +=p->data;if(p->next!=head)p=p->next;答案： (1) (a2, a4, , ) (2)将循环单链表中偶数结点位置的元素值写入依次表A6, 设依次表va中的数据元数递增有序。试写一算法，将x插入到依次表的适当位置上，以保持该表的有序性。答案：void Insert_sq(Sqlist va, ElemType x) int i, j, n; n=length(va); if(x>=vai)van=x;elsei=0;while(x>vai) i+;for(j=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的数据元素，并描述该算法的功能。 void f2(SeqList *L) int i,j,k;k=0;for(i=0;i<L->length;i+) for(j=0;j<k && L->datai!=L->dataj;j+); if(j=k) if(k!=i)L->datak=L->datai; k+; L->length=k;答案： (3,7,2,1,8) 删除依次表中重复的元素8, 线性表中的元素以值递增有序排列，并以单链表作存储构造。试写一算法，删除表中全部大于x且小于y的元素假设表中存在这样的元素同时释放被删除结点空间。答案：void Delete_list(Lnode *head, ElemType x, ElemType y) Lnode *p, *q; if(!head) return ERROR;p=head; q=p;while(!p) if(p->data>x) && (p->data<y)i+;if(p=head)head=p->next; free(p); p=head; q=p; elseq->next=p->next; free(p);p=q->next; elseq=p; p=p->next; 9, 在带头结点的循环链表L中，结点的数据元素为整型，且按值递增有序存放。给定两个整数a和b，且a<b，编写算法删除链表L中元素值大于a且小于b的全部结点。第三章 栈和队列一, 选择题1, 一个栈的输入序列为：a，b，c，d，e，那么栈的不行能输出的序列是 。A. a,b,c,d,e B. d,e,c,b,a C. d,c,e,a,b D. e,d,c,b,a2, 推断一个循环队列Q最多n个元素为满的条件是 。A. Q->rear=Q->front B. Q->rear=Q->front+1 C. Q->front=(Q->rear+1)%n D. Q->front=(Q->rear-1)%n3, 设计一个判别表达式中括号是否配对的算法，采纳 数据构造最正确。A. 依次表 B. 链表 C. 队列 D. 栈4, 带头结点的单链表head为空的判定条件是 。A. head=NULLB. head->next=NULLC. head->next!=NULL D. head!=NULL5, 一个栈的输入序列为：1,2,3,4，那么栈的不行能输出的序列是 。A. 1243 B. 2134 C. 1432 D. 4312E. 32146, 假设用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除一个元素，再参与两个元素后，rear和front的值分别为 。A. 1和5 B. 2和4C. 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. 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. -+*abcd11, 将递归算法转换成对应的非递归算法时，通常须要运用 来保存中间结果。A. 队列 B. 栈C. 链表 D. 树12, 栈的插入和删除操作在 。 A. 栈底 B. 栈顶 C. 随意位置 D. 指定位置13, 五节车厢以编号1，2，3，4，5依次进入铁路调度站栈，可以得到 的编组。A. 3，4，5，1，2B. 2，4，1，3，5C. 3，5，4，2，1D. 1，3，5，2，414, 判定一个依次栈S栈空间大小为n为空的条件是 。A. S->top=0 B. S->top!=0C. S->top=nD. S->top!=n15, 在一个链队列中，front和rear分别为头指针和尾指针，那么插入一个结点s的操作为 。A. front=front->next B. s->next=rear;rear=sC. 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，2D. 3，4，1，217, 依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是 。A. a B. b C. c D. d18, 正常状况下，删除非空的依次存储构造的堆栈的栈顶元素，栈顶指针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->front20, 设计一个判别表达式中左右括号是否配对出现的算法，采纳 数据构造最正确。A. 线性表的依次存储构造B. 队列C. 栈 D. 线性表的链式存储构造21, 当用大小为N的数组存储依次循环队列时，该队列的最大长度为 。A. NB. N+1C. N-1D. N-222, 队列的删除操作是在 。A. 队首B. 队尾C. 队前D. 队后23, 假设让元素1，2，3依次进栈，那么出栈次序不行能是 。A. 3，2，1B. 2，1，3C. 3，1，2 D. 1，3，224, 循环队列用数组A0，m-1存放其元素值，其头尾指针分别是front和rear，那么当前队列中的元素个数是 。A. (rear-front+m)%mB. rear-front+1C. rear-front-1D. rear-front25, 在解决计算机主机和打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机那么从该缓冲区中取走数据打印。该缓冲区应当是一个 构造。A. 堆栈 B. 队列C. 数组 D. 线性表26, 栈和队列都是 。A. 链式存储的线性构造 B. 链式存储的非线性构造 C. 限制存取点的线性构造 D. 限制存取点的非线性构造27, 在一个链队列中，假定front和rear分别为队头指针和队尾指针，删除一个结点的操作是 。A. front=front->next B. rear= rear->nextC. rear->next=frontD. front->next=rear28, 队和栈的主要区分是 。A. 逻辑构造不同 B. 存储构造不同C. 所包含的运算个数不同 D. 限定插入和删除的位置不同二, 填空题1, 设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，假设6个元素出队的序列是e2,e4,e3,e6,e5,e1，那么栈的容量至少应当是 。答案：32, 一个循环队列Q的存储空间大小为M,其队头和队尾指针分别为front和rear，那么循环队列中元素的个数为： 。答案：(rear-front+M)%M3, 在具有n个元素的循环队列中，队满时具有 个元素。答案：