《数据结构自测题资料》由会员分享，可在线阅读，更多相关《数据结构自测题资料（9页珍藏版）》请在金锄头文库上搜索。
1、一绪论1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的、数据信息在计 算机中的以及一组相关的运算等的课程。 A.操作对象计算方法C.逻辑结构D.数据映象 A存储结构B 关系C 运算D 算法2. 数据结构DS(Data Struct)可以被形式地定义为DS= (D, R),其中D是的有限集合，R是D上的的有限集合。 A.算法数据元素C.数据操作D.数据对象 A.操作映象C.存储D.关系3. 在数据结构中，从逻辑上可以把数据结构分 。A. 动态结构和静态结构紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4. 算法分析的目的是，算法分析的两个主要方
2、面是。 A. 找出数据结构的合理性C. 分析算法的效率以求改进 A. 空间复杂性和时间复杂性C. 可读性和文档性B. 研究算法中的输入和输出的关系D. 分析算法的易懂性和文档性B. 正确性和简明性D. 数据复杂性和程序复杂性5. 计算机算法指的是，它必具备输入、输出和等五个特性。B. 排序方法D. 调度方法B. 可行性、确定性和有穷性D. 易读性、稳定性和安全性 A. 计算方法C. 解决问题的有限运算序列 A. 可行性、可移植性和可扩充性C. 确定性、有穷性和稳定性1.2 填空题(将正确的答案填在相应的空中)1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。2. 在线性结构中，第一
3、个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可 。4. 在图形结构中，每个结点的前驱结点数和后续结点数可。5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。6. 算法的五个重要特性是, ,。7. 分析下面算法(程序段)，该算法的时间复杂度是。for (i=0;in;i+)for (j=0;jn; j+)Aij=0;8. 分析下面算法(程序段)，该算法的时间复杂度是_ for (i=
4、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;kn;k+)s=s+Bijk;sum=s;10. 分析下面算法(程序段)，该算法的时间复杂度是 i=s=0;while (sn) i+;s+=i; /s=s+i11. 分析下面算法(程序段)，该算法的时间复杂度是 i=1;while (i=n)i=i*2;第二章基础知识 一、选择题1、线性表是。A.个有限序列，可以为空B.一个有限序列，不能为空C. 一个无限序列，可以为空D.个无限序列，不能为空
5、2、在一个长度为n的顺序存储的线性表中，向第i个元素(1i next;D. next=p;A. p-next=p-next-next;C. p=p-next-next;6、设单链表中指针p指向结点a ,指针f指向将要插入的新结点x,问:i(1)当x插在链表中两个数据元素a和a之间时，只要先修改后修改即可。A. p-next=fC. p-next=f-nextE. f-next=NULLi i+1B. p-next=p-next-next D. f-next=p-nextF. f-next=p(2)在链表中最后一个结点a之后插入时，只要先修改后修改即n 可。A. f-next=pB. f-nex
6、t=p-nextC. p-next=fD. p-next=f-nextE. f=NULL7、在一个单链表中，若要在p所指向的结点之前插入一个新结点，则此算法的 时间复杂度为。A. 0(n)B. 0(n/2)C. O(1)D. 0(庙)8、 不带头结点的单链表L为空的判定条件为。A. L=NULLB.L-next=NULLC. L-next=LD. L!=NULL9、 带头结点的单链表L为空的判定条件为。A. L=NULLB.L-next=NULLC. L-next=LD. L!=NULL 10、指针p指向双向链表中的结点a，a为a的前驱结点，指针f指向将要插i i 1 i入的新结点x。x插在a
7、和a之间，此时需要修改指针的操作依次为i 1 iA. p-prior-next=fB. p-prior=fC. f-next=pD. f-prior=p-prior11、在一个带头结点的双向循环链表中，若要在指针p所指的结点之后插入一个 q 指针所指向的结点，则需要对 q-next 赋值为。A. p-priorB. p-nextC. p-next-nextC. p-prior-prior二、填空题:1、 线性表的两种存储结构分别为和。2、 若经常需要对线性表进行插入和删除运算，则最好采用存储结构，若经常需要对线性表进行查找运算，则最好采用存储结构。3、 访问一个线性表中具有给定值元素的时间复杂
8、度为。4、对于一个长度为 n 的顺序存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为。5、单链表是的链接存储表示。6、在一个单链表中指针 p 所指向的结点的后面插入一个指针 q 所指向的结点时， 首先把的值赋给q-next，然后把的值赋给p-next。7、在一个单链表中的 p 所指结点之前插入一个 s 所指结点时，可执行如下操作：(1) s-next=;( 2) p-next=s;( 3) t=p-data;(4) p-data=;(5) s-data=;8、假定指向单链表中第一个结点的表头指针为head，则向该单链表的表头插入指针 p 所指向的新结点时，首先执行赋值
9、操作，然后执行赋值操作。9、在一个单链表中删除指针p所指向结点的后继结点时，需要把的值赋给p-next指针域。10、在一个单链表中删除指针p所指结点时，应执行以下操作：q=p-next;p-data=p-next-data;p-next=;free(q);11、 在链表中，既可以通过设定一个头指针也可以通过设定一个尾指针 来确定它，即通过头指针或尾指针可以访问到该链表中的每个结点。12、在一个双向循环链表中指针p所指向的结点之前插入一个新结点时，其时间复杂性的量级为。三、简答题1、对于线性表的两种存储结构，如果线性表的总数基本稳定，并且很少进行插 入和删除操作，但是要求以最快的速度存取线性表中
10、的元素，则应该选用哪种存 储结构？试说明理由。2、有哪些链表可仅由一个尾指针来唯一确定，即从尾指针出发能访问到链表上任何一个结点？3、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头 指针，能否将结点*卩从相应的链表中删除？若可以，其时间复杂度各为多少？ 四、算法阅读题 读下面的程序段，画出执行过程的示意图及所完成的功能 1.# define N 6void main ( )SqList L ;int A N ;int i ,j,m, elem ;InitList_Sq(L); /初始化顺序表for (j=0; jN; j+) scanf(%d,&A j ) ;for ( m
11、=0; mnext)Q=L; L=L-next; P=L; while (P-next) P=P-next; P-next=Q; Q-next=NULL; return 1;3.void BB(LNode *s, LNode *q) p=s;while (p-next !=q ) p=p-next; p-next=s;void AA(LNode *pa, LNode *pb)/*pa 和 pb 分别指向单循环链表中两个节点*/BB(pa,pb);BB(pb,pa);五、算法设计题1、分别编写在顺序表和带头结点的单链表上统计出值为 x 的元素个数的算法， 统计结果由函数值返回。2、设线性表存放于
12、顺序表A中，其中有n个元素，且递减有序，请设计一算法, 将x插入到线性表的适当位置，以保持线性表的有序性。3、已知两个单链表A和B,指向头结点的指针分别为La和Lb,试编写一个算 法从单链表A中删除自第i个元素起的共length个元素，然后将它们插入到单链 表B的第j个元素之前。4、已知A，B和C为三个元素值递增有序的单链表，现要求对表A作如下运算: 删去那些既在表 B 中出现又在表 C 中出现的元素。试分别以两种存储结构（一 种顺序的，一种链式的）编写实现上述运算的算法。5、已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。试编写 一个删除表中所有值大于 mink 且小于 maxk
13、 的元素（若表中存在这样的元素） 的算法。6、有两个循环不带头结点的单链表如图所示，编写一个算法将链表 1 连接到链 表 2 之后，并仍然保持循环链表形式。7、假设有一个单向循环链表，其结点含有三个域：pre, data和next，其中data 为数据域；next为指针域，它指向后继结点；pre为指针域，它的值为空指针(NULL)。试编写算法将此表改为双向循环链表。8、编写算法实现顺序表的就地逆置，即利用原顺序表的存储单元把数据元素序歹列 女口 ( a , a a )，逆置为( a , a a )。12nn n119、假设在长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链 表中某个结点的指针，编写一个算法删除该结点的前趋结点。10、设头指针为head，编写算法实现带头结点单链表head的就地逆置，即利用 原带头结点单链表head的结点空间把数据元素序列(a , a，,a )逆置为0
