《数据结构》复习一．填空题1.“数据结构”课程研究的主要内容包括数据的逻辑结构、对各种数据进行的运算和数据的存储结构三方面。2.数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度。3.一个完整的算法应该具有输入、输出、有穷行、确切性和完整性5个特征。4.在一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动n-1个元素。5.在一个长度为n的顺序表中第i(1≤i≤n)个位置插入一个新元素时，需向后移动n-i个元素。6.若频繁地对线性表进行插入、删除操作，应采用链式存储结构合适。7.双向循环链表中，在p所指的结点之前插入指针为s所指的结点，则需依次执行下列语句：s->rlink=p;s->llink=p->llink;p->llink=s;sllink->rlink=s。8.空格串的长度是0；两串相等的充分必要条件是__长度相等_。9．设二维数组A[5][6]按列优先顺序存储在内存中，已知A[0][0]起始地址为1000，每个数组元素占用5个存储单元，则元素A[4][4]的地址为1095。10．已知二维数组A[1..50,1..80]的基地址为1000，每个元素占用2个存储单元。若以行序为主序存储方式，则元素A[45,68]的存储地址是6176；若以列序为主序存储方式，则元素A[45,68]的存储地址是6030。11.设有一个空栈，push和pop分别表示对栈进行一次入栈和出栈操作，假设有入栈序列为1,2，3，4，5，经过push,push,pop,push,pop,push,push之后，得到的出栈序列是2，3，5，4，1。12.设n个元素的进栈序列为1,2,3，…,n，出栈序列为p1,p2,p3,…,pn，若p1=n,则pi(1≤i<n)的值为n+1-i。13.设计一个递归问题的非递归算法通常需要设置栈数据结构。14.循环队列Q[0..M-1]中，用f和r分别表示队头和队尾，则当前队列中的元素个数是m-1。15.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据打印，该缓冲区应该是一个队列数据结构。16.广义表M=()的深度为0，长度为0;广义表N=（（）,N），则N的长度和深度分别为1、2。17.按照二叉树的定义，具有3个结点的二叉树有5种形态(不考虑数据信息的组合情况)18.某完全二叉树的深度为h，则该完全二叉树中至少有2n+1个结点。19.二叉树的先序遍历序列为：ABDCEFG，中序遍历序列为：DBCAFEG，则该二叉树根的左子树的根是B，右子树的根是E，其后序遍历序列是DCBFGEA。20.已知一棵二叉树的中序遍历序列为BDAECF,后序遍历结果为DBEFCA,则前序遍历结果为ABDCEF，层次遍历序列是ABCDEF。21.二叉树的四种遍历方法分别是先序遍历，中序遍历，后序遍历,层次遍历。22．具有n个顶点的连通图的生成树一定有n-1条边。23.图的常见的两种遍历方法分别是深度优先遍历、广度优先遍历。24.折半查找有序表（5，8，11，12，15，20，32，41，57），若查找表中元素32，它将依次与表中元素15,32比较大小。25.对n个元素采用冒泡排序法排序，排序的趟数为n-1。26.若一个待散列存储的线性表为K=（18,25,63,5,42,32,9,54），散列函数为H(K)=KMOD9，则与元素18发生冲突的元素有2个。27.假设排序过程中序列的变化情况如下，则采用的排序方法是选择排序。初始状态：50,72,28,39,81,15第1趟：15,72,28,39,81,50第2趟：15,28,72,39,81,50第3趟：15,28,39,72,81,50第4趟：15,28,39,50,81,72第5趟：15,28,39,50,72,81二．选择题1.算法分析的主要任务是分析D。A．算法中是否存在语法错误B．算法是否具有较好的可读性C．算法的功能是否符合设计要求D．算法的执行时间与问题规模之间的关系2.设栈的输入序列为1，2，3，4，则下列不可能的出栈序列是（A）。A．4,3,1,2B．3,4,2,1C．2,3,4,1D．1,3,2,43.设计一个递归问题的非递归算法通常需要设置（D）结构。A.数组B.线性表C.队列D.堆栈4.设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A8,5在一维数组B中的下标是（D）。A．33B．32C．85D．415.通常情况下数组最基本的操作是：（D）。A.插入和删除B.删除和修改C.查找和修