2004----01
16下列程序段的时间复杂性量级是____0(n*i)_________。 for (i=1;i t=t+1; 17在顺序存储的线性表a1,a2…an中的第i (1≤i≤n)个元素之前插入一个元素则需向后移动_____n-i+1________个元素。 18在栈的顺序实现中若栈不满则进栈操作可以用下列算法片断实现 ____ sq -> top ++_________ sq -> data[sq -> top]=x 19链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的______队尾结点_______。 20设有k个结点在用哈夫曼算法构造哈夫曼树的过程中若第i次合并时已找到权最小的结点x和权次小的结点y用Tx.wt表示结点x的权值已知Tx.wt=m, Ty.wt=n则合并成新的二叉树后给新根结点的权值赋值的语句为____m+n_________。 21在下列树中结点H的祖先为_____F________。 22顶点数为n、边数为n(n-1)/2的无向图称为___无向完全图__________。 任何两点之间都有的边的无向图称为无向完全图；边数(n(n-1)/2) 任何两点之间都有弧的有向图称为有向完全图；弧数(n*(n-1)) 23动态查找表在开散列表上通常采用___线性探测法和链地址法__________来解决冲突问题。 24对于有10个元素的有序表采用二分查找需要比较3次方可找到其对应的键值则该元素在有序表中的位置可能是___1,3,6,9___________。 25查找表的逻辑结构与线性结构、树型结构等相比根本区别在于____数据元素之间无逻辑关系__________。 27在排序方法中依次将每个记录插入到一个有序的子序列中去即在第i(i≥1)遍整理时r1,r2,…,ri-1已经是排好顺序的子序列取出第i个元素ri在已排好序的子序列里为ri找到一个合适的位置并把它插到该位置上。这种排序方法被称为____直接插入排序_______。 28快速排序法在待排序数据____已基本有序_________的情况下最不利于发挥其长处。 2004---10 16.从数据结构的观点，数据通常可分为三个层次，即：数据、数据元素和____数据项_______。 18.对顺序表执行插入操作，其插入算法的平均时间复杂性为____ O(n)_______。 19.在具有n个单元、且采用顺序存储的循环队列中，队满时共有_____ n-1______个元素。 20.若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则循环队列为空的条件是___ Q·front==Q·rear ________。 21.二维数组A[10][20]采用按行为主序的存储方式，每个元素占4个存储单元，若A[0][0]的存储地址为300，则[A][10][10]的地址为_____1056______。 22.树的遍历主要有先根遍历、后根遍历和___中根遍历________三种。 23.深度为k的完全二叉树至少有______2(k次方)-1_____个结点。 24.若图的邻接矩阵是一个对称矩阵，则该图一定是一个_____无向图______。 25.对于具有n个元素的数据序列，采用二叉排序树查找，其平均查找长度为____log2(n+1)-1______。 26.要完全避免散列所产生的“堆积”现象，通常采用___公共溢出区________法。 28.在最好的情况下，对于具有n个元素的有序序列，若采用冒泡排序，所需的比较次数为_____ n-1______次。 2005---01 17.数据结构中的算法，通常采用最坏时间复杂度和____平均时间复杂度________两种方法衡量其效率。 18.判断带头结点head的单链表为空的条件是___head-->next=null________。 19.若顺序表每个元素长度均为5，其中第一个元素的存储地址为30，则第6个元素的储地 址为____55_( 30+5*(6-1))______。 20.若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则判断循环队列为满的条件是__(sq.rear+1)%maxsize==sq.front_________。 21.对于顺序存储结构的二维数组，通常采用_____行序优先存储和列序优先存储______两种存放方式存储数据元素。 22.若某二叉树的先根遍历序列为CEDBA，中根遍历序列为DEBAC，则其后根遍历序列为___DABEC________。 23.具有n个结点的完全二叉树，其深度为_____「log2n」+1______。 24.图主要采用___邻接矩阵和邻接表________两种存储结构存放。 25.索引顺序查找通常分两个阶段进行，首先采用顺序查找法或二分法确定所要查找的块，然后再用______顺序查找_____法在块中找到具体的元素值。 26.二叉排序树是一种特殊的有序表，若要保证输出序列其键值完全按递增排列，则应对二叉排序树采用_____中根遍历______法遍历。 28.在各种内部排序中，占用存储空间较大的排序通常是____并归 _______排序。 2005---10 17.时间复杂性描述量级中，若某算法达到___指数_______量级，则该算法通常是不可计算的。 18.对顺序表执行删除操作，其删除算法的平均时间复杂性为____(n-1)/2______。 19.若head表示循环链表的头指针，t表示尾结点，则头指针head与尾结点t之间的关系可表示为___t->next==head_______。 20.我们通常把队列中允许删除的一端称为___队头_______。 21.二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是____157______。 以行为主序存储A[i][j]的首地址 = 数组的在内存中的基地址+ i * 列数* 每个元素占单元数+ j * 每 个元素占单元数 若二维数组A[L1..U1,L2..U2]以列为主序存储，每个元素占用d个存储单元，则元素A[i,j]的存储位置相对于数组空间首地址的偏移量为((J-L2)×(U1-LI+1)+I-L1)×d 22.树在数据结构中常采用孩子链表表示法、______孩子兄弟链表和双亲表示法____三种存储结构表示。 23.若某二叉树中度为1的结点数为4，度为2的结点数为6，则该树叶子结点数为_____7_____。 24.对于n个顶点的生成树，其边的个数为__n-1________ 。 25.对于具有n个元素的数据序列，若采用二分查找法，当n的值较大时其平均查找长度为__log2（n+1）-1________。 26.解决散列所引起冲突的方案中，___建立公共溢出区_______法是介于开散列表与闭散列表之间的一种方法。 28.排序通常可分为内部排序和外部排序，其中内部排序是指排序的整个过程中，数据全部存放在计算机的___内存_______中。 2006---01 16.数据表示和_____数据处理___________是程序设计者所要考虑的两项基本任务。 17.一个算法通常可从正确性、易读性、健壮性和____时空性____________等四个方面评价、分析。 18.对长度为n的顺序表执行删除操作，其删除算法在最坏情况下的时间复杂性为______0（n）__________。 20.我们通常把队列中允许插入的一端称为_____队尾___________。 21.二维数组在机器级的具体实现，通常均采用_______顺序和二叉链表_________存储结构。 22.深度为k的满二叉树其叶子结点个数共有_______2(k次方)-1_________个。 23.二叉树通常采用___顺序储存结构和链式储存结构_____________两种存储结构表示。 24.若一个完全无向图具有n条边，则该图的顶点个数为________________。 25.查找表的逻辑组织结构实际上是_______集合_________结构。 26.对于具有n个元素的数据序列，采用顺序查找法，其平均查找长度为____(n+1)/2____________。 28.对于具有n个元素的有序序列，若采用冒泡排序，最多需要进行______n-1__________趟起泡。 2006----10 16.在数据结构中，数据的逻辑结构分为集合、__线性结构______、树形结构和图状结构等四类。 17.通常从正确性、易读性、___健壮性_____和时空性等4个方面评价算法（包括程序）的质量。 18.顺序表的存储密度为___1_____，而链表的存储密度为___小于1_____。 19.对于栈只能在____栈顶____插入和删除元素。