数据结构期中试题

《数据结构期中试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、………………………………………密…………………………………封………………………………………线……………………………………………河北北方学院2012-2013学年第一学期期中考试试卷专业________班级________姓名__________学号________《数据结构》（供11级计算机科学与技术使用）注意事项：1．请按要求在试卷的密封区填写专业、班级、姓名和学号。2．请仔细阅读各种题目的答题要求，在规定的位置填写答案。3．不要在试卷上乱写乱画，不要在密封区填写无关的内容。题号一二三四总分得分总分合计人

2、：复核人：得分评卷人一、单选题（每题2分，共30分）1、下列算法是时间复杂度是___。for(i=0;i

3、的存储单元。D)线性表采用链接存储，便于插入和删除操作。4、链接存储的存储结构所占存储空间：___。A)分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B)只有一部分，存放结点值本试卷共6页第5页C)只有一部分，存储表示结点间关系的指针D)分两部分，一部分存放结点值，另一部分存放结点所占单元数5、在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是___。A)访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B)在第i个结点后插入一个新结点（1≤i≤n）C)删除第i个结点（1

4、≤i≤n）D)将n个结点从小到大排序6、线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。A）必须是连续的B）部分地址必须是连续的C）一定是不连续的D）连续或不连续都可以7、设一个栈的输入序列为a，b，c,d，则所得出栈的输出序列不可能是___。A)a,b,c,dB)d,a,b,cC)a,c,d,bD)d,c,b,a8、非空的循环单链表head的尾结点（由p所指向）满足___。A)p->next==NULLB)p==NULLC)p->next==headD)p==head9、以下数据结构中，哪

5、一个是线性结构___。A)广义表B)二叉树C)稀疏矩阵D)串10、假设有60行70列的二维数组a[1…60,1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为___。（无第0行第0列元素）A)16902B）16904C）14454D）答案A,B,C均不对11、任何一棵二叉树的叶子结点在先序，中序，和后序遍历序列中相对次序___。A)不发生改变B)发生改变C)不能确定D)以上都不对12、对一个满二叉树，m个树叶，n个结点，深度为

6、h，则___。A)n=h+mB)h+m=2nC)m=h-1D)n=2h-113、某二叉树只有度为0和度为2的结点，其中度为2结点数为8个，则该二叉树共有_____个结点。A)15B)17C)16D)无法计算14、若由树转化得到的二叉树是非空的二叉树，则二叉树的形状是___。A)根结点无右子树B)根结点无左子树C)根结点只有左子树或只有右子树D)左、右子树都可能有15、树最适合用来表示___。A)有序数据元素B)无序数据元素C)元素之间具有分支层次关系的数据D)元素之间无联系的数据12345678910111

7、2131415得分评卷人二、填空题（每题2分，共30分）1、数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。本试卷共6页第5页2、一个算法具有5个特性、、、有零个或多个输入、有一个或多个输出。3、在线性结构中，第一个结点前驱结点，其余每个结点有且只有1个前驱结点；4、在单链表中，除了首元结点外，任一结点的存储位置由指示。5、在单循环链表中，已知q指向p指向结点的前驱结点，若在q，p所指结点之间插入一个s所指向的新结点，则执行的操作是6、一个队列的入队序列是1,3,5,7,9

8、，则出队的输出序列只能是7、设字符串s1=‘abcdefg’，s2=‘pqrst’，则运算s=substr（s1，2，length（s2）后串值为___。8、判断一个循环队列cq（元素最多为QueueSize）为满队列的条件是__9、三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。10、二维数组M的元素是1个字符，行下标i的范围是从0到7，列下标j的范围从0到9，则存