《数据结构与算法习题库资料》由会员分享，可在线阅读，更多相关《数据结构与算法习题库资料（24页珍藏版）》请在金锄头文库上搜索。
1、第一章 绪论一选择题1数据结构被形式地定义为（K，R），其中K是_B_的有限集合，R是K上的_D_的有限集合。 A算法 B数据元素 C数据操作 D逻辑结构 A操作 B映象 C存储 D关系2算法分析的目的是C，算法分析的两个主要方面是A。 A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性 A空间复杂性和时间复杂性 B正确性和简明性 C可读性和文档性 D数据复杂性和程序复杂性3 在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为(B)A逻辑结构 B顺序存储结构C链表存储结构 D以上都不对4数据结构中，在逻辑上可以把数据结构
2、分成：( C ）。 A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构5以下属于顺序存储结构优点的是（ A ）。 A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示 6数据结构研究的内容是（ D ）。 A数据的逻辑结构 B数据的存储结构 C建立在相应逻辑结构和存储结构上的算法 D包括以上三个方面 7链式存储的存储结构所占存储空间（A ）。 A分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B只有一部分，存放结点值 C只有一部分，存储表示结点间关系的指针 D分两部分，一部分存放结点值，另一部分存放结点所占单元数
3、8一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（ A ）。 A确定性、可行性、有穷性 B易读性、确定性、有效性 C有穷性、稳定性、确定性 D可行性、易读性、有穷性 9以下关于数据的逻辑结构的叙述中正确的是（ A）。 A数据的逻辑结构是数据间关系的描述 B数据的逻辑结构反映了数据在计算机中的存储方式 C数据的逻辑结构分为顺序结构和链式结构 D数据的逻辑结构分为静态结构和动态结构 10算法分析的主要任务是（ C ）。 A探讨算法的正确性和可读性 B探讨数据组织方式的合理性C为给定问题寻找一种性能良好的解决方案 D研究数据之间的逻辑关系二解答设有一数据的逻辑结构为：B=
4、(D, S)，其中：D=d1, d2, , d9S=, , , , , , , , , , 画出这个逻辑结构示意图。d1d8d3d2d4d5d9d7d6第二章 线性表一、选择题1下述哪一条是顺序存储结构的优点？（ A）A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示2下面关于线性表的叙述中，错误的是哪一个？（ B）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。3若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插
5、入和删除运算，则利用（A ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表4某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表5在一个长度为n的顺序表中删除第i个元素(0=inext=p-next-next;Bp=p-next;Cp=p-next-next; Dp-next=p;8在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（B）As-next=p-next; p-next=sBq-next=s; s
6、-next=pCp-next=s-next; s-next=pDp-next=s; s-next=q9线性表的顺序存储结构是一种（A）的存储结构。A随机存取B顺序存取C索引存取D散列存取二、填空1在线性表的顺序存储中，元素之间的逻辑关系是通过 物理位置相邻 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 指针 决定的。2在双向链表中，每个结点含有两个指针域，一个指向 .直接前驱 结点，另一个指向 直接后继 结点。3当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_顺序 存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用 链式 存储结构为宜。三、算法设计1设有一
7、个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法（要求用最少的时间和最小的空间）确定在序列中比正整数x大的数有几个（相同的数只计算一次）将单链表中比正整数x小的偶数从单链表中删除int count(Linklist h,int x) int num=0; Linknode *p; p=h-next; while(p&p-datanext; while(p)if(p-next&p-data=p-next-data) /若p没有指向链表中同一数值的最后一个结点，则向后移动 p=p-next; else /若p指向数值相同的结点中的最后一个，则num
8、加1，p指针后移，继续执行while循环 num+; p=p-next; return num;void delevenl(Linklist &h,int x) Linknode *p,*r; p=h-next;r=h; while(p&p-datadata%2=0) r-next=p-next; free(p); p=r-next; else r=p; p=p-next; 2设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。phh2void converse(Linklist &h
9、)Linknode *p,*q;p=h-next;h-next=NULL; q=p-next;while(q)p-next=h; h=p; p=q; q=q-next;p-next=h;h=p;3设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。3void decompose(Linklist La,Linklist &Lb,Linklist &Lc)Linknode *p;Lc=(Linknode *)malloc(sizeof(Linknode)
10、;Lc-next=NULL;p=La-next;Lb=La;Lb-next=NULL;while(p)La=p-next;if(p-data0)p-next=Lc-next;Lc-next=p;elsep-next=Lb-next;Lb-next=p;p=La;4. 假设链表A、B分别表示一个集合，试设计算法以判断集合A是否是集合B的子集，若是，则返回1，否则返回0，并分析算法的时间复杂度。4int subset(LinkList la, LinkList lb) LinkNode * pa,*pb; pa=la-next; while(pa) pb=lb-next; while(pb&(pb
11、-data!=pa-data) pb=pb-next; if(!pb) return 0; pa=pa-next; return 1;算法时间复杂度O（A.Length*B.Length）5设有一单循环链表la，其结点有三个域：prior、data与next，其中data为数据域,，next域指向直接后继，prior域应指向直接前驱，但目前空着。试写一算法将此单循环链表改造为双向循环链表。5void priorset(DuLinkList &la) p=la;q=la-next; while(q!=la)q-prior=p; p=q;q=q-next; q-prior=p; 第三章 栈和队列一、选择题1已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C）A.5，4，3，2，1，6B.2，3，5，6，1，4C.3，2，5，4，1，6D.1，4，6，5，2，3设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列（C ）AA, B, C, D, E BB, C, D, E, ACE, A, B, C, D DE, D, C, B, A2在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈
