《数据结构》(本)模拟试题二

《《数据结构》(本)模拟试题二》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《数据结构》（本）模拟试题二一、填空题（每小题2分，共24分）1．结构中的数据元素存在多对多的关系称为________结构。2．要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为________和。3．设有一个头指针为head的单向循环链表，p指向链表中的结点，若p->next==_______，则p所指结点为尾结点。4．向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s->next=h和。5．在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为________和r=s;(结点的指针域为next)6．设有n阶对称矩

2、阵A，用数组S进行压缩存储，当i

3、的。(回答正确或不正确)12．按某关键字对记录序列排序，若在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。二、单项选择题（每小题2分，共30分）1．在C语言中，顺序存储长度为3的字符串，需要占用（）个字节。A．4B．3C．6D．122．数据的物理结构（）。A．与数据的逻辑结构无关B．仅仅包括数据元素的表示C．只包括数据元素间关系的表示D．包括数据元素的表示和关系的表示3．串函数StrCat（a,b）的功能是进行串（）。A．比较B．复制C．赋值D．连接4．从n个数中选取最大元素（）。A．基本操作是数据元素间的交换B．算法的时间复杂度是O(n2)C．算法的时间复杂度

4、是O(n)D．需要进行(n+1)次数据元素间的比较5．一棵有n个结点采用链式存储的二叉树中，共有（）个指针域为空。A．n+1B．nC．n-1D．n-26．线性表的顺序结构中，（）。A．逻辑上相邻的元素在物理位置上不一定相邻B．数据元素是不能随机访问的C．逻辑上相邻的元素在物理位置上也相邻D．进行数据元素的插入、删除效率较高7．设一棵哈夫曼树共有n个非叶结点，则该树有（）个叶结点。A．nB．n+1C．n-1D．2n8．带头结点的单向链表为空的判断条件是（）（设头指针为head）。A．head==NULLB．head->next==NULLC．head->next==headD．head!=

5、NULL9．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（）。A．x=top->data;top=topànext;B．x=top->data;C．top=top->next;x=top->data;D．top=top->next;x=data;10．线性结构中数据元素的位置之间存在（）的关系。A．一对一B．一对多C．多对多D．每一个元素都有一个直接前驱和一个直接后继11．一棵完全二叉树共有5层，且第5层上有六个结点，该树共有（）个结点。A．30B．20C．21D．2312．设顺序存储的线性表长度为n，要删除第i个元素，按课本的算法，当i=（）时，移动元

6、素的次数为3A．3B．n/2C．n-3D．413．在一个无向图中，所有顶点的度数之和等于边数的（）倍。A．3B．2.5C．1.5D．214.以下说法不正确的是（）。A．栈的特点是后进先出B．队列的特点是先进先出7C．栈的删除操作在栈底进行，插入操作在栈顶进行D．队列的插入操作在队尾进行，删除操作在队头进行15．已知如图2所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A．V1V2V4V8V5V3V6V7B．V1V2V4V5V8V3V6V7C．V1V2V4V8V3V5V6V7D．V1V3V6V7V2V4V5V8V6V7V1V2V3V8V4V5图2三

7、、综合题（每小题10分，共30分）1．一组记录的关键字序列为（46，79，56，38，40，84）（1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要求以升序排列）（2）对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。2．设查找表为(16,15,20,53,64,7),(1)用冒泡法对该表进行排序（要求升序排列），写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟