《数据结构与算法习题库(考前必备)》由会员分享，可在线阅读，更多相关《数据结构与算法习题库(考前必备)（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研究数据之间的逻辑关系二解答二解答设有一数据的逻
4、辑结构为：B=(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 个元素(0next=p-next-next;Bp=p-next; Cp=p-next-next; Dp-next=p; 8在一个单链表中，已知 q 结点是 p 结点的前趋结点，若在 q 和 p 之间插入 s 结点，则须
6、 执行（B） As-next=p-next; p-next=s Bq-next=s; s-next=p Cp-next=s-next; s-next=p Dp-next=s; s-next=q 9线性表的顺序存储结构是一种（A）的存储结构。A随机存取B顺序存取C索引存取D散列存取二、填空1在线性表的顺序存储中，元素之间的逻辑关系是通过 物理位置相邻 决定的；在线 性表的链接存储中，元素之间的逻辑关系是通过 指针 决定的。 2在双向链表中，每个结点含有两个指针域，一个指向 .直接前驱 结点，另一个指 向 直接后继 结点。 3当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_顺序
7、 存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用 链式 存储结构 为宜。三、算法设计1设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在） ， 试编写能实现下列功能的算法（要求用最少的时间和最小的空间） 确定在序列中比正整数 x 大的数有几个（相同的数只计算一次） 将单链表中比正整数 x 小的偶数从单链表中删除 int count(Linklist h,int x) int num=0;Linknode *p;p=h-next;while(pwhile(p) if(p-nextelse /若 p 指向数值相同的结点中的最后一个，则 num 加 1，p 指针后
8、移，继续执行 while 循环num+;p=p-next;return num; void delevenl(Linklist p=h-next;r=h;while(pfree(p);p=r-next;elser=p;p=p-next; 2设有一个表头指针为 h 的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针 h 指向原链表的最后一个结点。2void converse(Linklist p=h-next; h-next=NULL;q=p-next; while(q) p-next=h;h=p;p=q;q=q-next; p-n
9、ext=h; h=p; 3设计算法将一个带头结点的单链表 A 分解为两个具有相同结构的链表 B、C，其中 B 表的结点为 A 表中值小于零的结点，而 C 表的结点为 A 表中值大于零的结点（链表 A 的 元素类型为整型，要求 B、C 表利用 A 表的结点） 。 3void decompose(Linklist La,Linklist phhLc=(Linknode *)malloc(sizeof(Linknode); Lc-next=NULL; p=La-next; Lb=La; Lb-next=NULL; while(p) La=p-next; if(p-data0) p-next=Lc-n
10、ext; Lc-next=p; else p-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(pbif(!pb) return 0;pa=pa-next; return 1; 算法时间复杂度 O（A.Length*B.Length） 5设有一单循环
11、链表 la，其结点有三个域：prior、data 与 next，其中 data 为数据域,，next 域指向直接后继，prior 域应指向直接前驱，但目前空着。试写一算法将此单循环链表改造 为双向循环链表。 5void priorset(DuLinkList 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，4
12、 C.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, A CE, A, B, C, D DE, D, C, B, A 2在一个具有 n 个单元的顺序栈中，假定以地址低端（即 0 单元）作为栈底， 以 top 作为栈顶指针，当做出栈处理时，top 变化为（C ） Atop 不变 Btop=0 Ctop- Dtop+ 3向一个栈顶指针为 hs 的链栈中插入一个 s 结点时，应执行（B ） Ahs-next=s; Bs-next=hs; hs=s; Cs
13、-next=hs-next;hs-next=s; Ds-next=hs; hs=hs-next; 4在具有 n 个单元的顺序存储的循环队列中，假定 front 和 rear 分别为队头 指针和队尾指针，则判断队满的条件为（ D） Arearn= = front B （front+l）n= = rear Crearn -1= = front D(rear+l)n= = front 5在具有 n 个单元的顺序存储的循环队列中，假定 front 和 rear 分别为队头 指针和队尾指针，则判断队空的条件为（ C） Arearn= = front Bfront+l= rear Crear= = fro
14、nt D(rear+l)n= front 6在一个链队列中，假定 front 和 rear 分别为队首和队尾指针，则删除一个 结点的操作为（ A） Afront=front-next Brear=rear-next Crear=front-next Dfront=rear-next 7某堆栈的输入序列为 1，2，3，n，输出序列的第一个元素是 n，则第 i 个输出元素为（ C） Ai Bn-i Cn-i+1 D哪个元素无所谓 8用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指 向队尾结点，则在进行删除操作时( D )。 A仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改二、解答题1一个双向栈 S 是在同一向量空间内实现的两个栈，它们的栈底分别设在向量 空间的两端。 试为此双向栈设计初始化 InitStack ( S ) 、入栈 Push( S , i , x) 和 出栈 Pop( S , i )等算法， 其中 i 为 0 或 1， 用以表示栈号。1双向栈./双向栈类型定义 #define STACK_SIZE 100; Typedef
