山东建筑大学数据结构期末复习题.docx

《山东建筑大学数据结构期末复习题.docx》由会员分享，可在线阅读，更多相关《山东建筑大学数据结构期末复习题.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、选择题1 .在长度为n的顺序表的第i个位置上插入一个元素(lWign+1),元素的移动次数为：()oA、n-i+1B、n-iC、iD、i-1答案：A2 .与单链表相比,双链表的优点之一是()oA、插入、删除操作更简单B、可以进行随机访问C、可以省略表头指针或表尾指针D、顺序访问相邻结点更灵活答案：D3 .链表不具备的特点是()。A、可随机访问任一结点B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与其长度成正比答案：A4 .在决定选取何种存储结构时，一般不考虑()oA、各结点的值如何B、结点个数的多少C、对数据有哪些运算D、所用的编程语言实现这种结构是否方便。答案：A5 .算

2、法分析的目的和算法分析的两个主要方面是0A、分析算法的效率以求改进；空间复杂度和时间复杂度B、找出数据结构的合理性；可读性和文档性C、分析算法的易读性和文档性；数据复杂性和程序复杂性D、正确性和简明性；研究算法中的输入和输出的关系答案：A6 .在以下的叙述中，正确的是()oA、线性表的顺序存储结构优于链表存储结构B、二维数组是其数据元素为线性表的线性表C、栈的操作方式是先进先出D、队列的操作方式是先进后出答案：B7 .在一个具有不个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是()A、0(1)B、0(n)C、0(n2)D、O(nlog2n)答案：B8 .设森林F对应的二叉树为B,

3、它有m个结点,B的根为p,p的右子树的结点个数为n,森林F中第一 棵树的结点的个数是()oA、m-nB、m-n-1C、n+1D、不能确定答案：A9 .下述哪一条是顺序存储结构的优点()oA、入运算方便B、方便地用于各种逻辑结构的存储表示C、储密度大D、除运算方便答案：C10 .在数据结构中，与所使用的计算机无关的是数据的()结构。A、逻辑B、存储C、逻辑和存储D、物理答案：A11 .线性表是具有n个()的有限序列。A、字符B、数据元素C、数据项D、表元素答案：B12 .一个队列的入队序列是1,2,3,4,则队列的输出序列是()。A、4,3,2B、123,4C、1,4,3,2D、3,2,41答案

4、：B13 .一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是()。A、edcbaB、decbaC、dccabD、abcde答案：C14 .输入序列为ABC,可以变为CBA时，经过的栈操作为()。A、push,pop,push,pop,push,popB、push,push,push,pop,pop, popC、push,push,pop,pop,push,popD、push,pop,push,push, pop,pop答案：B15 .在循环队列中，若front与rear分别表示对头元素和队尾元素的位置，则判断循环队列空的条件 是()。A、front=rear+1B、rear=fr

5、ont+lC、front=rearD、front=0答案：C16 .在数据结构中，从逻辑上可以把数据结构分为()。A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构答案：C17 .需要分配较大空间，插入和删除不需要移动元素的线性表,其存储结构是()oA、单链表B、静态链表C、线性链表D、顺序存储结构答案：B18 .线性表(al,a2,an)以链式方式存储,访问第i位置元素的时间复杂度为()。A、0(0)B、0(1)C、0(n)D、0(n2)答案：C二、填空题1 .具有10个顶点的无向图，边的总数最多为O o答案：452 .在树形结构中，树根结点没有前驱

6、结点，其余每个结点有且只有()个前驱结点;叶子结点没 有后续结点，其余每个结点的后续结点可以()O答案：1,任意多个3,带头结点的循环链表L中只有一个元素结点的条件是()o答案：L-next- next=L4 .在顺序表中插入或删除一个数据元素，需要平均动()个数据元素，移动数据元素的个数与 0有关。答案：几位置5 .在各种查找方法中，平均查找长度与结点个数n无关的查找方法是()o答案：散列杳找法6 .数据逻辑结构包括()、()和()三种类型。答案：线性结构，树形结构，图状结构7 .算法的5个重要特性是()、()、()、()和()o答案：有穷性，确定性,可行性，输入，输出8 .在有n个结点的二

7、叉链表中，空链域的个数为()。答案：n+19 .深度为5的二叉树至多有()个结点。答案：311。一个字符串中任意个连续字符构成的部分称为该串的O o答案：子串三、判断题1 .线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。()A、正确B、错误答案：错误2 .若已知一棵二叉树的前序遍历序列和后序遍历序列，则可以恢复该二叉树。()A、正确B、错误答案：错误3 .在平衡二叉树中,任意结点左右子树的高度差(绝对值)不超过1。()A、正确B、错误答案：正确4 .直接选择排序算法在最好情况下的时间复杂度为0(n) o ()A、正确B、错误答案：错误5 .在决定选取何种存储结构时，一般不考

8、虑各结点的值如何。()A、正确B、错误答案：正确6 .对线性表进行折半查找时，要求线性表必须以链式方式存储，且结点按关键字有序排列。()A、正确B、错误答案：错误7 .抽象数据类型与计算机内部表示和实现无关。()A、正确B、错误答案：正确8 .二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的后面。()A、正确B、错误答案：正确9 .串是一种特殊的线性表，其特殊性体现在可以顺序存储。()A、正确B、错误答案：错误10 .链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序表中效率高。0A 正确B、错误答案：正确四、程序题1-单链表中结点的结构如下所示：lypedef st

9、ruct node int data; struct node *next; node请设计满足下述功能的函数。要求：建立带头结点的单链表H,要求函数从屏幕上读入m个整数，每读入一个，便生成相应的结点，并且把它插入到链表H的尾部。函数形式为 void CreateLinkList(node *H)。答：参考程序：void CreateList(node *11)U/H指向头指针int m, temp;coutm;/int i=l;nodeH-next=NULL;tail=H;while(i=m) couttemp;node *t=new node ;t-data=temp;t-next=tai1-next;tail-next=t;tail=t;i+；