湖南人文科技学院-数据结构测试卷.doc

《湖南人文科技学院-数据结构测试卷.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、任课教师学号姓名湖南人文科技学院通控系通信工程专业2009级2010---2011学年第二学期数据结构课程考核试卷(A)考核方式:（闭卷)考试时量：120分钟题号一二三四总分合分人复查人实得分评卷人一、填空题：（每空1分，共20分）1、数据结构被形式地定义为（D,R），其中D是的有限集合，R是D上的有限集合。2、一个算法的效率可分为效率和效率。3、在n个结点的单链表中，查找某个数据的时间复杂度为_______________。n个结点的顺序表存储时，查找某个数据的时间复杂度为_______________。4、在一个循环队列中，队首指针指向队首元素的位置。5、在具有n个单元的循环队列中，

2、队列满时共有个元素。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、在解决计算机主机与打印机之间速度不匹配时通常设置一

3、个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个_________结构，其主要特点是__________。10、算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是__________、___________、_____________、有零或多个输入和有一或多个输出。11、在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的____________、____________和_______三项。得分评卷人二、选择题：（每空2分，共30分）共7页第1页1．（）是具有相同特性数据元

4、素的集合，是数据的子集。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=fr

5、ont5．设有一个对称矩阵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;

6、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需要的

7、操作为（）。   A.p->next=p->next->next     B.p=p->next         C.p=p->next->next             D.p->next=p14.将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（ ）。  A.100      B.40      C.55     D.8015．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。  A.3