《数据结构》重修试卷

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

1、︵︶成都理工大学《数据结构》重修考试试卷大题一二三四五总分得分得分一、选择题（20分）单项选择题，共19个小题，20个选项，每个选项1分。1.树型结构是指数据元素之间存在哪种关系。（）A）一对多关系B）多对多关系C）多对一关系D）一对一关系2.数据结构中算法分析的目的是（）。A)找出数据结构的合理性B)研究算法中的输入和输出的关系C)分析算法的效率以求改进D)分析算法的易懂性和文档性3．数据结构的二元组表示S=（D,R），D表示数据元素，R表示数据关系。下面表示为树型结构的是（）。A)D={d1,d2,d3,d4}R={,

2、3>,,}B)D={d1,d2,d3,d4}R={,,}C)D={d1,d2,d3,d4}R={,,>d3,d2>}D)D={d1,d2,d3,d4}R={(d1,d2),(d1,d3),(d3,d4),(d4,d2)}4．已知C++语言中的字符型数组A[4][5],第一个元素A[0][0]的存储单元位置为100，元素A[3][3]的存储位置为（）A）117B）118C）119D）1205.在n个结点的单链表存储中，算法的时间复杂度是O（1）的操作是

3、（）。A）访问第i个结点（1≤i≤n）B）在第i个结点后插入一个新结点（1≤i≤n）第9页C）删除第1个结点D）在链表最后插入一个结点6.判定一个队列QU（最多元素为m0）为空队列的条件是()。A)QU->rear－QU->front==m0B)QU->rear－QU->front－1==m0C)QU->front==QU->rearD)QU->front==QU->rear+17．队列中元素的进出原则是（）。A)先进先出B)后进先出C)空则进入D)任意位置8．一个字符栈的入栈序列依此为ABDCE，则通过栈调度后不可能存在的输出序列有（）。A)A

4、BCDEB)EDCBAC)DBACED)ACEDB9．串是一种特殊的线性表，其特殊性体现在（）。A）可以顺序存储B）数据元素是一个字符C）可以链式存储D）数据元素可以是多个字符10.有8个结点的无向连通图最少有（）条边。A）5B）6C）7D）811．广度优先遍历类似于二叉树的（）。A)先序遍历B)中序遍历C)后序遍历D)层次遍历12．对22个记录的有序表作折半查找，当查找成功时，至多需要比较次关键字。（）A)3B)4C)5D)613．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（）。A)希尔排序B)归并排序C)

5、插入排序D)选择排序14．堆的形状是一棵（）。第9页A)二叉排序树B)满二叉树C)完全二叉树D)平衡二叉树15．对有n个记录的表作简单交换排序，在最坏情况下，算法的时间复杂度是A)O(n)B)O(n2)C)O(nlog2n)D)O(n3)16．中序遍历二叉树，是指（）。A)先访问根结点，再依次访问左子树和右子树B)先访问左子树，再访问根结点，然后访问右子树C)先访问左子树，再访问右子树，然后访问根结点D)先访问根结点，再依次访问右子树和左子树17．线性表指的是（）。A)一个有限数据元素序列，允许是空B)一个有限数据元素序列，不能为空C)一个无限数

6、据元素序列，允许是空D)一个无限数据元素序列，不能为空18.设矩阵A是一个下三角矩阵，按行序存放在一维数组B[0,n(n-1)/2-1]中，对下三角部分中任一元素ai,j(i≥j),在一维数组B中下标k的值是（）。A)i(i-1)/2+j-1B)i(i-1)/2+jC)i(i+1)/2+j-1D)i(i+1)/2+j19.树是结点的有限集合，它(①)根结点，记为T。其余的结点分成为m（m≥0）个(②)的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。供选择的答案①：A)有0个或1个B)有0

7、个或多个C)有且只有1个D)有1个或1个以上②:A)互不相交B)允许相交C)允许叶结点相交D)允许树枝结点相交第9页得分二、填空题（20分）共12个小题，20个空，每空1分。1．数据结构按物理存储结构划分为、、和索引存储。2．在树型结构中，树根结点没有结点，其余每个结点有且只有个前驱结点；叶子结点没有结点，其余每个结点的后续结点数可以3．向一个长度为n的线性表中删除第i个元素(1≤i≤n)时，需向前移动个元素。4．是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。5．子串的定位运算称为串的模式匹配；称为目标串，称为模式。6．

8、三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。7．一棵深度为6的满二叉树有个分支结点和个