算法与数据结构习题.doc

《算法与数据结构习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法与数据结构》习题1一、单项选择题1.数据结构从逻辑上分为（）。A．动态结构和静态结构B．内部结构和外部结构C．紧凑结构和非紧凑结构D．线性结构和非线性结构2.栈和队列的共同点是（）。A．都是先进后出B．都是后进先出C．只允许在端点处插入和删除元素D．没有共同点3．若按从左到右的顺序读入已知序列a、b、c、d、e、f、g中的元素，然后结合栈的操作，能得到下列序列中的哪些序列？（）A．decfbgaB．fegdacbC．efdgbcaD．dcbefag4.在一个单链表中，若q结点是p结点的前驱结点，

2、若在q与p之间插入结点s，则执行（）。A．s→link=p→link；p→link=s；B．p→link=s；s→link=q；C．p→link=s→link；s→link=p；D．q→link=s；s→link=p；5．算法的计算量的大小称为计算的（）。A．效率B.复杂性C.现实性D.难度6.一个算法应该是（）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C7.从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造

3、型结构8.以下数据结构中，哪一个是线性结构？（）A．广义表B.二叉树C.稀疏矩阵D.串二、多项选择题1.以下说法正确的是（）。A.二叉树的特点是每个结点至多只有两棵子树B.二叉树的子树无左右之分C.二叉树只能进行链式存储D.树的结点包含一个数据元素及若干指向其子树的分支2．在数组上能做的操作有（）。A. 插入B. 删除C. 取值操作D. 赋值操作3.图的应用算法有（）。A.克鲁斯卡尔算法B.哈弗曼算法C.迪杰斯特拉算法D.拓扑排序算法4.计算机算法必须具备（）等特性。A.可行性、确定性B.可行性、可移

4、植性C.输入、输出D.有穷性E.易读性F.稳定性三、填空题1.一个算法的效率可分为效率和效率。2.向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素。3.栈只能在插入和删除元素；对于队列只能在插入和删除元素。4.一棵具有257个结点的完全二叉树，它的深度为。四、判断题1.链表的每个结点中都恰好包含一个指针。（）2.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）3.数和二叉树都是分支结构。（）4.优先队列是一种给每个元素增加了优先级的队列

5、，它具有队列的基本特性。（）5.数据元素是数据的最小单位。（）6.记录是数据处理的最小单位。（）7.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（）五、简答题1.能否讲二叉树是一种特殊的树？为什么？2.在C语言中字符串可以用字符指针来表示。字符串的长度隐含在字符指针所指的字符数组中，通过特殊的字符‘’判定。写一个递归算法，以字符指针为参数，在屏幕上打印出它反转后得到的字符串。3.算法与程序有什么区别？4.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。5.什么是网络的最小生

6、成树？6.已知两个串为S1=“bccadcabcadf”,S2=”abc”,试求两个串的长度，并判断S2串是否是S1串的子串；如果是，请指出S2在S1中的位置。《算法与数据结构》习题1答案一、单项选择题题号12345678答案DCABBBCD二、多项选择题题号1234答案ADCDACDACD三、填空题题号答案1时间；空间2n-i+13栈顶；队尾；队首49四、判断题题号1234567答案××√××××五、简答题1.答：不能。二叉树并不是树的特例。树和二叉树的定义及操作都是不同的，周游算法也有很大的区别。

7、二叉树可以与一般树林建立对应，它的提出可以为研究树提供一种简单而统一的范型。2.答：voidprintRevString(char*s){If(s[0]==‘’)return;/*空串*/If(s[1]==‘’)putchar(s[0]);/*只有一个字符，直接打印*/Else{PrintRevString（s+1）；Putchar（s[0]）;}}3.答：算法与程序的关系十分密切，但并不等同。一般来说，一个程序并不需要满足算法的有穷性等条件，例如操作系统的程序，只要整个系统不遭到破坏，操

8、作系统程序就永不结束。另外，程序是用机器可执行的语言书写的，而算法通常并没有这种限制。4.答：DLR：ABDFJGKCEHILMLDR：BFJDGKACHELIMLRD：JFKGDBHLMIECA5.答：因为网络是带权的连通图，其生成树中的边也带权，将生成树各边的权值总和称为生成树的权，并把权值最小的生成树成为最小生成树。6.答:S1的长度为14，S2的长度为3;S2是S1的子串，起始位置是S1中第九个字符。