搜索
湖南人文科技学院通控系通信工程专业2009级2010---2011学年第二学期数据结构课程考核试卷(A)考核方式:（闭卷)考试时量：120分钟题号一二三四总分合分人复查人实得分一、填空题：（每空1分，共20分）1、数据结构被形式地定义为（D,R），其中D是的有限集合，R是D上的有限集合。2、一个算法的效率可分为效率和效率。3、在n个结点的单链表中，查找某个数据的时间复杂度为_______________。n个结点的顺序表存储时，查找某个数据的时间复杂度为_______________。4、在一个循环队列中，队首指针指向队首元素的位置。5、在具有n个单元的循环队列中，队列满时共有个元素。6、设串t=“Iamastudentgood”，串Sub=Substring(t,8,7)，那么Sub=__________。7、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A[0][0]的存储位置为1000，按行优先存储，则A[3][4]的地址为；若按列优先存储时，则A[3][4]的地址为。8、设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。9、在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个_________结构，其主要特点是__________。10、算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是__________、___________、_____________、有零或多个输入和有一或多个输出。11、在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的____________、____________和_______三项。二、选择题：（每空2分，共30分）共7页第1页1．（）是具有相同特性数据元素的集合，是数据的子集。A.数据符号B.数据对象C.数据D.数据结构2．用链表表示线性表的优点是()。A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同3．堆栈的输入序列为（A,B,C,D），不可能的输出有（）。A.(A,B,C,D)B.(D,C,B,A)C.(A,C,D,B)D.(C,A,B,D)4．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是()。A.front=maxSizeB.(rear+1)%maxSize=frontC.rear=maxSizeD.rear=front5．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（）。A.23B.33C.18D.406．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为()。A.CDBGFEAB.CDBFGEAC.CDBAGFED.BCDAGFE7．采用折半查找方法进行查找，数据文件应为（），且限于（）。A.有序表顺序存储结构B.有序表链式存储结构C.随机表顺序存储结构D.随机表链式存储结构8．执行下面程序段时，执行S语句的次数为（）for(intI=1;I=n;I++)for(intj=1;j=I;j++)S;A.n2B.n2/2C.n(n+1)D.n(n+1)/29．串是一种特殊的线性表，其特殊性体现在（）A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符10．由五个分别带权值为9，2，3，5，14的叶子结点构成的一棵哈夫曼树，该树的带权路径长度为()。A.60B.66C.67D.50共7页第2页评卷人得分评卷人任课教师学号姓名11．深度为5的二叉树至多有()个结点。A．10B．16C．31D．3212.数组的逻辑结构不同于下列（）的逻辑结构。A．线性表B.栈C.队列D.树13．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。A.p-next=p-next-nextB.p=p-nextC.p=p-next-nextD.p-next=p14.将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。A.100B.40C.55D.8015．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。A.3B.4C.5D.1得分评卷人三、判断题（每题1分，共10分）1．三个结点的二叉树和三个结点的树一样，都具有三种不同的形态。（）2．算法可以没有输入，但是必须有输出。（）3．对链表进行插入和删除操作时不必移动链表中结点。（）4．子串“ABC”在主串“AABCABCD”中的位置为2。（）5．入栈操作和入队列操作在链式存储结构上实现时需要考虑栈溢出的情况。（）6．顺序表查找指的是在顺序存储结构上进行查找。（）7．列是插入与删除操作分别在表的两端进行的线性表，是一种先进后出结构（）8.线性表在顺序存储时，逻辑上相邻的元素必在存储的物理位置次序上相邻。（）9．链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。（）10.二叉树中的叶子结点就是二叉树中没有左右子树的结点。（）得分评卷人四、程序题（1、2题每题5分，3、4题每题6分，5、6题每题9分，共40分）1．写出程序段的功能,如果输入数据为254，写出输出结果。(5分)共7页第3页voidconversion(){Stacks;intn;SElemTypee;initstack(s);printf(Pleaseinputnumber:);scanf(“%d”,&n);while(n){push(s,n%9);n=n/9;}while(!stackempty(s)){pop(s,e);printf(“%d”,e);}}该程序的功能为：输入254，输出数据为：2、读函数，指出函数的功能。(5分)LinkListmynote(LinkListL){//L是不带头结点的单链表的头指针if(L&&L-next){q=L；L=L－next；p=L；S1：while(p－next)p=p－next；S2：p－next=q；q－next=NULL；}共7页第4页returnL；}请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。3.请在标号处填写合适的语句。完成下列程序。(每空2分，共6分)intBinary_Search(SStableST，KeyTypekey){/*在关键字升序排列的表ST中查找关键字为key的数据元素，若找到返回该元素在表中的位置，否则，返回0*/intmid，low，high；low=1；high=length；while(low=high){/*非空，进行比较测试*/mid=⑴；if(keyST.elem[mid].key)⑵；elseif(keyST.elem[mid].key)⑶；elsereturnmid；}return0；}⑴⑵⑶4.指出下面函数f的功能及返回值的含义。(6分)intf(chars1[],chars2[]){inti=0,j=0;共7页第5页while(s1[i]&&s2[j]){if(s1[i]s2[j])return1;elseif(s1[i]s2[j])return-1;elsei++,j++;}if(s1[i])return1;elseif(s2[j])return-1;elsereturn0;}函数f的功能是：返回值-1的含义：返回值0的含义：返回值1的含义：5．设计判断单链表中元素是否是递增的算法。(9分)结点定义如下：typedefstructLnode{intdate;structLnode*next;}LNode，*Link；函数定义如下：BOOLInSort（Linkhead）head为链表的头结点，头结点中存有数据。若是升序排列，返回true；否则返回false；如果head==NULL或者链表只有一个结点，返回true。写出该函数的函数体。BOOLInSort（Linkhead）{共7页第6页}6．写出链栈中数据出栈的函数。(9分)堆栈中的结点定义如下：tyedefstructStack{chardate;structStack*next;}*LinkStack;出栈函数定义如下：voidPop（LinkStackhead）；head为栈顶指针。VoidPop（LinkStackhead）{}共7页第7页