数据结构练习题.doc

一 单项选择1 数据结构在计算机中的表示称为数据的（）A存储结构 B逻辑结构 C抽象结构 D顺序结构2 在线性表中，一个数据元素可以由若干个数据项组成，在这种情况下，常把数据元素称为（）A数据项 B文件 C记录 D数据对象3 若线性表中最常用的操作是存取第i个元素及其前驱的值，则采用（）存储方式最节省时间A单链表 B双链表 C单循环链表 D顺序表4 设循环队列中数组下标范围是0n-1，头尾指针分别为front和rear，则当一个元素进队时指针变化为（）Arear=rear+1 Brear=（rear+1）MOD n Cfront=front+1 Dfront=（front+1）MOD n 5 设一个栈的输入序列为ABCD，则借助一个栈所得到的输出序列不可能是（）AABCD BDCBA CACDB DDABC6 串长是（）A串中字符个数 B串中不同字符个数C串中相同字符个数 D串中除空格字符外的字符个数7 数组A56的每个元素占有4个单元，将其按行优先次序存储在起始地址为1000的连续内存单元中，则元素A44的地址为（）A1096 B1112C1120 D11168 对于稀疏矩阵的压缩存储只需存储（）A零元 B非零元C对角线上元素 D所有元素9 对二叉树从1开始进行编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）A先序遍历 B中序遍历C后序遍历 D从根开始的层次遍历10 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）A高度等于其结点数 B空或只有一个结点C任一结点无左孩子 D任一结点无右孩子11 一棵深度为5的满二叉树的结点数为（）A16 B15 C32 D3112 对有18个元素的有序表做二分查找，则查找A3的比较序列下标为（）A1，2，3 B9，5，2，3 C9，5，3 D9，4，2，313 若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方式最节省运算时间A单链表 B带头结点的单链表C单循环链表 D带头结点的双循环链表14 判断下面序列中，哪一个不是线性表（）A（78，53，45） B（A，B，C）C（1，3，A） D（“MON”，“TUE”，“SUN”）15 单循环链表的尾结点指针域的值为（）ANULL BC首结点地址 D尾结点地址16 设数组QM中有一循环队列,F、R是队头、队尾指针，空队列的条件是（）An=0 BF=R CF=R-1 DF=R+117 采用循环队列的目的是为了解决（）的问题A溢出 B假溢出 C冲突 D节省时间18 长为n的顺序存储的线性表，执行INSERT（L，i，b）操作之后，元素b的位置在（） Ai-1 Bi+1 Cn+1 Di19 表头指针为L，则L-next=L时,链表这时是()A单链表 B空单链表C单循环链表 D空单循环链表20 哈希提出的查找方法的理想情况是（）A冲突 B散列地址编码 C不比较关键字 D省空间21 栈应用的典型例子是（）A排队 B表达式求值 C归并 D查找22 L是带表头的单链表的表头指针，该表为空的条件是（）An=0 BL=NULL CL-next=NULL DL-next=L23 设D=A,B,C,D,E, R=(A,B),(C,D),(D,B),(C,E),结构(D,R)是( )A线性表 B树 C栈 D图24 栈上可进行的操作是（）A访问栈的第i个元素 B在栈的第i个元素之后插入元素XC在栈顶后插入一个元素X D删除栈底元素25 中序遍历和后序遍历所得序列完全相同的二叉树是（）A空二叉树 B所有左儿子域均为空C所有右儿子域均为空 D儿子域中至少有一个为空26 设一棵二叉树中没有度为1的结点，已知叶结点数为n，该树的结点数为（）A2n+2 B2n+1 C2n D2n-127 已知某二叉树的先序序列为ABCDE，它可能的中序序列为（）ABDAEC BBCADE CCBADE DBEACD28 具有n个顶点的强连通图，其弧条数的最小值为（）An+1 Bn Cn-1 Dn-229 具有n个顶点的强连通图，它可能具有弧的条数的最大值为（）An2+n Bn2 Cn2-n Dn30 设哈希表的长度为7，哈希函数H（K）=K mod 7，冲突处理为：d0=H（K），di=（di-1+3）mod 7设哈希表中位置1，2，4中已有元素，现将关键字K=25插入哈希表中，插入位置是（）A0 B3 C5 D631 一个三对角矩阵An*n，已按行压缩存储到一维数组B中，则B的长度至少是（）A3n+1 B3n C3n-1 D3n-232二 多项选择1 对于线性结构，基本的操作有（）A插入 B删除 C更新 D查找 E排序2 队列的操作特性是（）A先进先出 B先进后出 C后进先出 D后进后出 EFILO3 对二叉树有n0个叶结点，n1个度为1的结点，n2个度为2的结点，则下面结论中（）是正确的A该二叉树共有2n0个空链域 Bn0= n2+1 C该二叉树共有n0+ n1+ n2+1个空链域D结点总数= n0+ n1+ n2 E非空链域数= n0+ n1+ n2-14 限定性的数据结构有（）A线性表 B树 C栈 D图 E队列5 线性表的特性有（）A元素的逻辑关系与物理位置一致 B可随机访问任意元素C可在常数时间内完成插入操作 D执行插入、删除操作之后，结果仍是线性表E每一个元素都有一个直接后继6 具有n个结点、高为h的二叉树有（ ）An0 B第K层最多有2K-1个元素 Cn=2K -1D至少有一个叶结点 E每个结点都至少有一个儿子7 队列的特征有（）A结构上与线性表相同 B可随机访问队中元素 C操作都在同一端执行D插入可在队中任意位置进行 E删除只在队头进行8 数组结构的特性是（）A它是线性表的扩充 B可进行随机访问 C可进行随机插入D可进行随机删除 E行列可任意扩充9三 判断分析1 线性表的长度是线性表所占用的存储空间大小2 数组可以看成是线性结构的一种推广，因此可以对它进行插入、删除等操作3 串是不少于一个字母的序列4 二叉树只能采用二叉链表来存储5 对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点6 有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数7 对链队列做退栈操作时，不会改变队头指针四 简答1 已知一棵二叉树的先序序列和中序序列