2007-2010自考数据结构导论试题1

《2007-2010自考数据结构导论试题1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、全国2007年1月数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1．关于栈和队列的说法中正确的是（）A．栈和队列都是线性结构B.栈是线性结构，队列不是线性结构C.栈不是线性结构，队列是线性结构D.栈和队列都不是线性结构2．关于存储相同数据元素的说法中正确的是（）A．顺序存储比链式存储少占空间B.顺序存储比链式存储多占空间C.顺序存储和链式存储都要求占用整块

2、存储空间D.链式存储比顺序存储难于扩充空间3．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（）A．线性结构B.树形结构C.线性结构和树型结构D.线性结构和图状结构4．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（）A．q→next=s；p→next=s；B.q→next=s；s→next=p；C.q→next=s；q→next=p；D.q→next=s；s→next=q；5．在长度为n的线性表中删除一个指针p所指结点的时

3、间复杂度是（）A．O(n)B.O(1)C.O(log2n)D.O(n2)6．设一个栈的输入序列是a，b，c，d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（）A．a，b，c，dB.a，b，d，cC.d，c，b，aD.c，d，a，b7．关于串的叙述中，正确的是（）A．空串是只含有零个字符的串B.空串是只含有空格字符的串C.空串是含有零个字符或含有空格字符的串D.串是含有一个或多个字符的有穷序列308．在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（）A．fr

4、ont==rearB.(front+1)%m==rearC.rear+1==frontD.(rear+1)%m==front9．设有二维数组A［n］［n］表示如下：，则A［i］［i］（0≤i≤n-1）的值为（）A．i*(i-1)/2B.i*(i+1)/2C.(i+2)*(i+1)/2D.i2/210．高度为h的完全二叉树中，结点数最多为（）A．2h-1B.2h+1C.2h-1D.2h11．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（）A．mnB.mn

5、-1C.n(m-1)D.m(n-1)12．在一个具有n个顶点的无向图中，每个顶点度的最大值为（）A．nB.n-1C.n+1D.2(n-1)13．关于无向图的邻接矩阵的说法中正确的是（）A．矩阵中非全零元素的行数等于图中的顶点数B.第i行上与第i列上非零元素总和等于顶点Vi的度数C.矩阵中的非零元素个数等于图的边数D.第i行上非零元素个数和第i列上非零元素个数一定相等14．设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=keymod13，则它的开

6、散列表中散列地址为1的链中的结点个数是（）A．1B.2Ｃ．3D.415．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为（）A．36，44，49，55，81，88B.44，36，49，55，81，88C.44，36，49，81，55，88D.44，36，49，55，88，8130二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。错填、不填均无分。16．在数据结构中，各个结点按逻辑关系互相缠绕，任

7、意两个结点可以邻接的结构称为_______。17．每个存储结点只含一个数据元素，所有存储结点连续存放。此外增设一个索引表，索引表中的索引指示各存储结点的存储位置或位置区间端点。按这种方式组织起来的存储结构称为_______。18．在顺序表上读表元算法的时间复杂度为_______。19．双链表中前驱指针为prior，后继指针为next，在指针P所指结点前插入指针S所指的结点，需执行下列语句：S→next=P;S→prior=P→prior;P→prior=S;_______;20．设数组A［0..8］［0.

8、.8］的起始元素位置为a，每个元素占2L个存储单元，按行序为主序存储。若元素A［i］［j］的存储位置为a+66L，则元素A［j］［i］的存储位置为_______。21．有4个结点且深度为4的二叉树的形态共有_______种。22．某二叉树的先根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则该二叉树中根结点的右孩子是_______。23．第一个顶点和最后一个顶点相同的路径称为回路或者环，除第一个顶点和最后一个顶点外，