资源描述：
《《数据结构01》复习题_答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一选择题（每小题2分，共20分）1．数据结构中，与所使用的计算机无关的是数据的___c___结构；A）存储B）物理C）逻辑D）物理和存储2．算法分析的目的是：cA）找出数据结构的合理性B）研究算法中的输入和输出的关系C）分析算法的效率以求改进D）分析算法的易懂性和文档性3．计算机算法必须具备输入．输出和_b______等５个特性．Ａ）可行性、可移植性和可扩充性B)可行性、确定性和有穷性Ｃ）确定性、有穷性和稳定性 Ｄ）易懂性 、稳定性和安全性４．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是___b____A）110B）108C）100D）1205设有两
2、个串p和q,求q在p中首次出现的位置的运算称作:A)连接B)模式匹配C)求子串D)求串长6.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动____b___个元素A)8B)63.5C)63D)77设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中,对下三角部分中任一元素ai,j(i≤j),在一维数组B中下标K的值是:（矩阵是A[1][1]开始）BA)i(i-1)/2+j-1B)i(i_1)/2+jC)i(i+1)/2+j-1D)i(i+1)/2+j8.二叉树是非线性数据结构,所以__c_____A)它不能用顺序存
3、储结构存储B）它不能用链式存储结构存储C）顺序存储结构和链式存储结构都能存储D）顺序存储结构和链式存储结构都不能使用9.有8个结点的无向连通图最少有__c_____条边（边数＝节点－1）A)5B)6C)7D)810.所有排序方法中,关键字比较的次数与记录的初始排列次数无关的是___d____A)希尔B)冒泡C)插入D)选择二.填空题(每小题2分,共20分)1.数据的存储结构可用四种基本的存储方法表示,它们分别是顺序_______、链式_______、索引_______和散列_______。2.在一个循环队列中,队首指针指向队首元素的前一个_______位置。3.向一个长度为n的向量的第i
4、个元素(1≤i≤n=1)之前插入一个元素时,需向后移动____n-i+1__个元素,删除第i个元素(1≤i≤n)时,需向前移动_n-i_____个元素。4.向量、栈和队列都是__线性_____结构,可以在向量的任何_______位置插入和删除元素;对于栈只能在_栈顶______插入和删除元素;对于队列只能在__队尾____插入和_____队头__删除元素。5.在动态存储管理中的三种分配策略是首次拟合_______、_最佳拟合______和___最差拟合____。6.广义表(((a)))的表头是__（（A））_____,表尾是_____（）__。7.已知主串s=’ADBADABBAABAD
5、ABBADADA’,模式串pat=’ADABBAD’。写出模式串的nextval函数值_______。P（77）8.一棵具有257个结点的完全二叉树，它的深度为不大于k=log2(n)最大整数8_____。9．n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为___O（n^2）____；若采用邻接表存储时，该算法的时间复杂度为O(n+e)_______。10．已知序列{32，17，18，60，40，7，73，65，85}，给出快速排序第一趟的结果（升序），并给出该序列的初始小根堆_______。(堆排序先右后左。先建树，快速排序：记位置，交换)三．判断题（每小题2分，共1
6、0分）1、线性表的每个结点只能是一个简单类型（栈和队列），而链表的每个结点可以是一个复杂类型。f2、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（说反了）f3、链表的每个结点中都恰好包含一个指针。（双向链表）f4、用二叉链表法（llink-rlink）存储包含n 个结点的二叉树，结点的２ｎ个指针区域中有n＋1个为空指针。t５、二分查找同顺序查找一样，对数据表没有什么要求。F（有序）四．应用题（每小题５分，共３０分）１、已知一单向链表Ｌ，写出在指定的Ｐ结点前成功插入一个新结点的有关语句（包括产生一个新结点的有关语句，并画出链表结构图）。Link*q,q=(link*)mallo
7、c(sizeof(link));q->data=p->data;q->next=p->next;p->next=q;２、已知二叉树的先序、中序遍历序列分别为ＡＢＤＦＪＧＫＣＥＨＩＬＭ和ＢＦＪＤＧＫＡＣＨＥＬＩＭ，试写出后序遍历时得到的结点序列。３、设给定权集Ｗ＝｛２，３，４，７，８，９｝，试构造关于Ｗ的一棵哈夫曼树和哈夫曼编码，并求其加权路径长度ＷＰＬ。４、给出入如图Ｇ所示的无向图的邻接表，从１点出发的ＤＳＦ序列和使用Ｐrim算法构
