《数据结构考试必过宝典》由会员分享，可在线阅读，更多相关《数据结构考试必过宝典（22页珍藏版）》请在金锄头文库上搜索。
1、期末复习：1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的、数据信息在计算 机中的以及一组相关的运算等的课程。 A.操作对象B.计算方法C.逻辑结构 A.存储结构B.关系C.运算2. 数据结构DS(Data Struct)可以被形式地定义为DS= (D 合，R是D上的. A.算法 A.操作3. 在数据结构中A.动态结构和静态结构 C.线性结构和非线性结构4. 算法分析的目的是, A.找出数据结构的合理性 C.分析算法的效率以求改进 A.空间复杂性和时间复杂性 C.可读性和文档性5. 计算机算法指的是.C.D.D.R),数据映象算法其中D是的有限集_有限集合。B.数据元素C.数据操
2、作B.映象C.存储从逻辑上可以把数据结构分成。B.紧凑结构和非紧凑结构D.内部结构和外部结构算法分析的两个主要方面是。B.研究算法中的输入和输出的关系D.分析算法的易懂性和文档性:B.正确性和简明性D.数据复杂性和程序复杂性，它必具备输入、输出和等五个特性。B.排序方法D.调度方法B.可行性、确定性和有穷性D.易读性、稳定性和安全性D.数据对象 。.关系A.计算方法解决问题的有限运算序列A.可行性、可移植性和可扩充性C.确定性、有穷性和稳定性答案：1、C,A 2、B,D 3、C 4、C,A 5、C,B1. 数据逻辑结构包括、和 三种类型，树形结构和图形结构合称为。2. 在线性结构中，第一个结,
3、前驱结点，其余每个结点有且只有个前驱结点；最后一个结点 后续结点，其余每个结点有且只有 个后续结点。3. 在树形结构中，树根结点没 结点，其余每个结点有且只有个直接前驱结点，叶子结点没有 结点，其余每个结点的直接后续结点可以。4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。6. 算法的五个重要特性是,。7. 分析下面算法(程序段)，给出最大语句频度，该算法的时间复杂度是。for (i=0;in;i+)for (j=0;jn; j+)Aij=0;8. 分析下面算法(程序段)，给出最大语句频度，该算
4、法的时间复杂度是。for (i=0;in;i+)for (j=0; ji; j+)Aij=0;9. 分析下面算法(程序段)，给出最大语句频度，该算法的时间复杂度是。s=0;for (i=0;in;i+)for （j=0;jn;j+）for （k=0;knext= =NULLC. head-next= =headD. head!=NULL8. 带头结点的单链表head为空的判定条件是。A. head= =NULLB. head-next= =NULLC. head-next= =headD. head!=NULL9. 非空的循环单链表head的尾结点（由p所指向）满足_。A. p-next= =
5、NULLB. p= =NULLC. p-next= =headD. p= =head10. 在双向循环链表的p所指结点之后插入s所指结点的操作是。A. p-right=s; s-left=p; p-right-left=s; s-right=p-right;B. p-right=s; p-right-left=s; s-left=p; s-right=p-right;C. s-left=p; s-right=p-right; p-right=s; p-right-left=s;D. s-left=p; s-right=p-right; p-right-left=s; p-right=s;11.
6、 在一个单链表中，已知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;12. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行。A. s-next=p; p-next=s;B. s-next=p-next; p-next=s;C. s-next=p-next; p=s;D. p-next=s; s-next=p;13. 在一个单链表中，若删除p所指结点
7、的后续结点，则执行。A. p-next= p-next-next ；B. p= p-next; p-next= p-next-next；C. p-next= p-next;D. p= p-next-next ；14. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均 比较 个结点。A. n B. n/2 C. (n-1)/2D, (n+1)/215. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是_。A. O(1) B. O(n) C. O (n2)D. O (nlog2n)16. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是。A.
8、 O(1)B. O(n) C. O (n2)D. O (n*log2n)答案：1、B2、A,C 3、B 4、D 5、C6、A7、A 8、B 9、C 10、D11、C12、B 13、A 14、D 15、B 16、C1. 单链表可以做 的链接存储表示。2. 在双链表中，每个结点有两个指针域，一个指向，另一个指向。3. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作：q=head;while (q-next!=p) q=q-next;s= new Node; s-data=e;q-next=;填空s-next=;填空4. 在一个单链表中删除p所指结点的后继结点时，应执行
9、以下操作：q= p-next;p-next=;填空delete;填空5. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行s-next= 和 p-next=的操作。6. 对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是 _；在给定值为x的结点后插入一个新结点的时间复杂度是。答案：1、线性结构表2、前驱结点，后继结点3、s，p 4、q-next，q 5、p-next，s 6、O(1)，O(n)1, 设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以 保持该表的有序性。例1设线性表L是一个递增有序表，试写一算法，将x插入L中，并使L仍
10、是一个有序表。void InsertIncreaseList(SqList *L ,DataType x)(int i;for(i=1;iLength & L-datai-1Length-1;j=i-1;j-)L-dataj+1 = L-dataj;/* 移动结点*/L-datai-1 = x;L-Length+;例2：有顺序表A和B,其元素均按从小到大的升序排列，编写一个算法将它们合并成一个 顺序表C,要求C的元素也是从小到大的升序排列。例如 A=(a,c,d,e,h,j,k)，B=(b,c,f,g),贝0，C=(a,b,c,d,e,f,g,h,j,k)void Merge(SqList *
11、La, SqList *Lb,SqList *Lc)int i,j,k;i=j=0;k=0;while (iLength-1 & jLength-1)if(La-dataidataj) InsertList(Lc,La-datai,k+1);i+;k+;elseInsertList(Lc,Lb-dataj,k+1);j+;k+;/ end while/*将La和Lb的元素插入到Lc中*/while (iLength-1) InsertList(Lc,La-datai,k+1);i+;k+;while (jLength-1) InsertList(Lc,Lb-dataj,k+1);j+;k+;例
12、3、已知L是无头结点的单链表的头指针，其中*p结点既不是首元结点，也不是尾元结 点，试写出下列操作的语句序列：(1) 在*?结点后插入*$结点；s-next=p-next;p-next=s;(2) 在*?结点前插入*结点；q=L;While(q-next!=p)q=q-next;s-next=q-next;q-next=s;(3) 在表首插入*$结点；S-next=L;L =S;(4) 在表尾插入*$结点。While(P-next!=null)P=P-next;P-next=S;S-next=null;例4、将顺序表原地逆置Typedef struct( datatype datalistsize;Int
