2004----01
16下列程序段的时间复杂性量级是____0(n*i)_________。
for (i=1;i for (j=1; j t=t+1; 17在顺序存储的线性表a1,a2…a n中的第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,…,r i-1已经是排好顺序的子序列取出第i个元素r i在已排好序的子序列里为r i找到一个合适的位置并把它插到该位置上。这种排序方法被称为____直接插入排序_______。 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.对于栈只能在____栈顶____插入和删除元素。 20.在循环队列中，存储空间为0～n-1,设队头指针front指向队头元素前一个空闲元素，队 尾指针指向队尾元素，那么队满标志为front=(rear+1)%n，队空标志为__front= rear ______。 21.三个结点可构成__5______种不同形态的二叉树。 22.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为 2n个，其中___n-1_____个用于链接孩子结点。(n+1个空闲节点) 23.有向图G用邻接矩阵A［1··n，1··n］存储，其第i列的所有元素之和等于顶点V i的_____ 度___。 24.对二叉排序树进行____中序____遍历，可得到排好序的递增结点序列。 25.采用折半查找方法进行查找的数据序列应为__有序表______且__顺序存储结构______。 27.在插入和选择排序中，若初始数据基本正序，则选用___插入_____；若初始数据基本反 序，则选用___选择_____。 基本正序时用插入排序，因为这时的关键字比较次数和记录移动次数都很少 基本反序用选择排序，此时两者的关键字比较次数差不多，选择排序的记录移动次数很少 28.快速排序最好情况下的时间复杂度为__O(nlog2n次方)______，最坏情况下的时间复杂度为__O(n2平方)______。 2007---01 16．在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为___图结构____。 17．每个存储结点只含一个数据元素，所有存储结点连续存放。此外增设一个索引表，索引表中的索引指示各存储结点的存储位置或位置区间端点。按这种方式组织起来的存储结构称为___索引存储方式____。 18．在顺序表上读表元算法的时间复杂度为__0(n)_____。 19．双链表中前驱指针为prior，后继指针为next，在指针P所指结点前插入指针S所指的结点，需执行下列语句： S→next=P;S→prior=P→prior;P→prior=S;_______; 20．设数组A［0..8］［0..8］的起始元素位置为a，每个元素占2 L个存储单元，按行序为主序存储。若元素A［i］［j］的存储位置为a+66 L，则元素A［j］［i］的存储位置为__a+114L_____。 21．有4个结点且深度为4的二叉树的形态共有___4____种。 22．某二叉树的先根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则该二叉树中根结点的右孩子是____M___。 23．第一个顶点和最后一个顶点相同的路径称为回路或者环，除第一个顶点和最后一个顶点外，其余顶点都不重复的回路，称为____简单回路或简单环___。 24．一个具有10个顶点的完全无向图中有___45____条边。 26．二分查找的时间复杂度为___ O(log2n次方)____。 27．二路归并排序算法的时间复杂度为__O(nlog2n次方)_____。 2007----10 17.设有指针head指向不带表头结点的单链表用next表示结点的一个链域指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中使之成为第一个结点则所需的操作为“p→next=head”和“__________”。 18.单链表中逻辑上相邻的两个元素在物理位置上_____未必_____相邻。 19.在一个长度为n的数组中删除第i个元素1≤i≤n时需要向前移动的元素的个数是_____n-i_____。 20.设F、C是二叉树中的两个结点若F是C的祖先结点则在采用后根遍历方法遍历该二叉树时F和C的位置关系为F必定在C的_____后边_____。 21.若用后根遍历法遍历题21图所示的二叉树其输出序列为__________。 题21图 22.具有n个顶点的连通图至少需有__________条边。 23.在无向图G的邻接矩阵A中若Aij等于1则Aji等于____1______。 24.设顺序表的表长为n且查找每个元素的概率相等则采用顺序查找法查找表中任一元素在查找成功时的平均查找长度为__________。 25.在索引顺序表上的查找分两个阶段一是查找___索引表_______二是查找块。 27.在对一组关键字为54,38,96,23,15,72,60,45,83的记录采用直接选择排序法进行排序时整个排序过程需进行____9______趟才能够完成。 28.冒泡排序是一种稳定排序方法。该排序方法的时间复杂度为____O(n2平方)______。 2008----01 16.数据的逻辑结构通常包括集合、线性结构、____树形结构________和图状结构。 17.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，指针s指向双链表中的一个结点（该结点既非头结点，也非尾结点），则删除s指针所指向结点的操作为“s->tl->r1=s->r1；”和“____ s->r1->t1=s->t1;________”。 18.对稀疏矩阵进行压缩存储的目的是节省_____储存空间_______。 19.在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则需平均比较的结点数为____n+1/2____。 20.深度为15的满二叉树上，第11层有______1024______个结点。 21.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为_____98_______。 i 的左孩子是2i,右孩子是2i+1.所以49的右孩子编号为98+1. 22.一个具有4个顶点的无向完全图有______6______条边。 n(n-1)/2 23.一个有向图G中若有孤 24.在一棵二叉排序树上按______中序______遍历得到的结点序列是一个有序序列。 25.实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是_____有序表_______的。 27.在插入排序和选择排序中，若原始记录已基本有序，则较适合选用_____插入排序_______。 28.对n个元素的序列进行冒泡排序时，最多需进行____n-1________趟。 2008---10 16.在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为___图状结构_____。 17.存储结点之间通常有四种基本存储方式，即顺序存储方式、索引存储方式、___链式存储方式_____和散列存储方式。 18.在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动___n-i+1_____个元素。 19.对一棵深度为10的满二叉树按层编号，则编号为51的结点，它的双亲结点编号为____25____。 20.用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342的出栈顺序，相应的S和X操作串为___ SXSSXSXX_____。 21.具有n个叶子结点的哈夫曼树，其结点总数为___2n-1_____。 22.一棵具有n个结点的树，所有非终端结点的度均为k，则该树中叶子结点个数为________。 一棵具有n个结点的树，所有非终端结点的度均为k，则此二叉树为K叉树，这棵树只右度为K和度为0的结点，设度为K的结点数为a，度为0的结点数为b，则n=a+b。又设二叉树的所有分支为m,则m=k*a,同样可以得到n=m+1。 综上可以得到b=[(n-1)*(k-1)/k-1]。 23.在无向图G的邻接矩阵A中，若A［i］［j］等于0，则A［j］［i］等于___0_____。25.某二叉树的后根遍历序列为abd，中根遍历序列为adb，则它的先根遍历序列为____ dab____。 26.先在所有的记录中选出键值最小的记录，将它与第一个记录交换；然后在其余的记录中再选出最小的记录与第二个记录交换，依此类推，直至所有记录排序完成。这种排序方法称为___直接选择排序_____。 27.对含有n个结点e条边的无向连通图，利用prim算法生成最小生成树的时间复杂度为____O(n2次方)____。 28.对n个元素进行冒泡排序时，最少的比较次数为__n-1______。 2009----01 16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、__索引存储方式_______和散列存储方式等四种。 17. 作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为_算法的输入规模和问题的规模________。 18.在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向____直接前驱_____和____直接后继_____。 19.在有n个元素的链队列中，入队和出队操作的时间复杂度分别为__O(1)_______和__O(n)_______。 20.在栈结构中，允许插入的一端称为____栈顶_____；在队列结构中，允许插入的一端称为_____队尾____。 21.在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为_(rear+1)%maxsize==front________。 22.深度为k的二叉树至多有__2k次方-1_______个结点，最少有___2(k次方-1)______个结点。 23.设有一稠密图G，则G采用____邻接矩阵_____存储结构较省空间。设有一稀疏图G，则G采用_____邻接表____存储结构较省空间。 24.在一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较____(n+1)/2_____个元素结点。 25.假定对线性表R［0…59］进行分块检索，共分为10块，每块长度等于6。若检索索引表和块均用顺序检索的方法，则检索每一个元素的平均检索长度为___9______。 27.在插入排序、冒泡排序、快速排序、归并排序等排序算法中，占用辅助空间最多的是____归并排序_____。 28.冒泡排序最好的时间复杂度为___O（n）______，平均时间复杂度为__ O（n的平方）_______，是一种稳定的排序算法。 2009---10 16.下列程序段的时间复杂度为___O(n)_____。 i=0s=0 whilei { i++ s=s+i } 17.数据的逻辑结构被分为集合结构、___线性结构_____、树形结构和图状结构4种。 18.线性表中所含结点的个数称为___表长_____。 19.向一个栈顶指针为top的链栈中插入一个新结点*p时应执行__top-->next_=p____和top=p操作。 20.设一个顺序栈S元素s1s2s3s4s5s6依次进栈如果6个元素的退栈顺序为s2s3s4s6s5s1则顺序 栈的容量至少为____3____。 21.若满二叉树的结点数为n则其高度为___【log2(n)】+1_____。 22.在一棵具有n个结点的完全二叉树中从树根起自上而下、从左到右地给所有结点编号。若编号为i的结点有父结点那么其父结点的编号为___[i/2]____。 23.深度为k的二叉树结点数最多有____2k次方-1____个。 24.某二叉树的后根遍历为ABKCBPM则该二叉树的根为_____M___。 25.在一个具有n个顶点的无向图中顶点的度最大可达____n-1____。 26.有向图G的邻接矩阵为A如果图中存在弧 27.顺序查找算法的平均查找长度为___n+1/2_____。 28.二路归并排序的平均时间复杂度为________。 2010---01 16.下列程序段的时间复杂度为_____O(n3次方)_______。 for(i=1；i<=n；i++) for(j=1；j<=n；j++) for(k=1；k<=n；k++) s=i+j+k； 17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____图状结构________。 18.在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点__直接后继__________的。 19.在栈结构中，允许插入的一端称为_____栈顶_______。 20.从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动_____n-i______个元素。 21.一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为_____ n-i+1_______。 22.循环队列被定义为结构类型，含有三个域：data、front和rear，则循环队列sq为空的条件是___sq.front==sq.rear_________。 23.一个10阶对称矩阵A，采用行优先顺序压缩存储上三角元素，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为_______19_____。 24.对于一棵满二叉树，若有m个叶子，则树中结点数为____2m-1________。 25.含有n个顶点和n-1条边的连通图G采用____邻接表________存储结构较省空间。 26.在图中，第一个顶点和最后一个顶点相同的路径称为_____简单回路或简单环_______。 27.动态查找中两个元素X，Y存入同一个散列表时，X、Y键值相同，则这种情况称为_____冲突_______。 28.堆排序需______一_____个记录大小的辅助存储空间。 2010---10 16．下列程序段的时间复杂度为__O(根号n)_____。 i=0；s=0； while（s {i++； s=s+i； } 17．数据的存储结构被分为顺序存储结构、___链式存储结构____、散列存储结构和索引存储结构4种。 18．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动___n-i____个元素。19．在单链表中，插入一个新结点需修改__2_____个指针。 20．在队列结构中，允许插入的一端称为___队尾____。 21．稀疏矩阵采用的压缩存储方法是___三元组表____。 22．向一个栈顶指针为top的链栈中插入一个新结点*p时，应执行p->next=top和___top=p____操作。 23．有m个叶结点的哈夫曼树所具有的结点数为__2m-1_____。 24．在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结点编号。设根结点编号为1。若编号为i的结点有右孩子，那么其右孩子的编号为___2i+1____。25．在一棵树中，____根___结点没有前驱结点。 26．一个具有n个顶点的有向完全图的弧数是__n(n-1)_____。 27．n个顶点的无向图G用邻接矩阵A［n］［n］存储，其中第i列的所有元素之和等于顶点V i的___度____。 28．选择排序的平均时间复杂度为__O(n的平方)_____。 2011---01 16.下列程序段的时间复杂度为___O(log2n)________。 i=1； while（i i=i*2； 17.向一个长度为n的顺序表中第i（1≤i≤n）个元素之前插入一个元素时，需向后移动___n-i+1________个元素。 18.在循环双链表中，删除最后一个结点，其算法的时间复杂度为_____0(1)______。 19.队列的插入操作在队列的___队尾________部分进行。 20.一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为_____n-i+1______。 21.一个10阶对称矩阵A，采用行优先顺序压缩存储下三角，a00为第一个元素，其存储地址为1，每个元素占有1个存储地址空间，则a85的地址为_____42______。 22.设字符串S=″I□AM□A□STUDENT″（其中□表示空格字符），则S的长度为___14________。 23.在树形结构中，没有后继的结点是_____叶子______结点。 24.一棵深度为n(n>1)的满二叉树中共有___2n次方-1________个结点。 25.在无向图中，如果从顶点v到顶点v′有路径，则称v和v′是____连通的_______。 26.无向完全图G采用____邻接矩阵_______存储结构较省空间。 27.在顺序查找、二分查找、索引查找和散列查找四种查找方法中，平均查找长度与元素个数没有关系的查找方法是____散列查找_______。 28.快速排序最好情况下的时间复杂度为____ O(nlog2n)_______。 2011----10 16.下列程序段的时间复杂度为__O(n的平方)______。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) x++; 17.数据结构中结点按逻辑关系依次排列形成一条“锁链”的结构是___线性结构______。 18.在表长为n的顺序表上做删除运算，平均要移动的结点个数为___（n-1）/2______。 19.在带有头结点的单循环链表head中，指针p所指结点为尾结点的条件是___p->next==head______。 20.队列又称为___先进先出______的线性表。 21.顺序栈被定义为结构类型，含有两个域：data和top，则对栈*sq进行初始化的操作是_sq—>top=0________。 22.对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n2=_n0-1_______。 23.一棵具有n个结点的二叉树，采用二叉链表存储，则二叉链表中指向孩子结点的指针有__n-1_______个。 24.若连通图G的顶点个数为n，则图G的生成树的边数为___n-1______。 25.一个具有n个顶点的无向图的边数最多为___n(n-1)/2______。 26.中根遍历二叉排序树所得到的结点访问序列是键值的____递增_____序列。 27.冒泡排序的平均时间复杂度为___O(n2)______。 28.将序列{60，20，23，68，94，70，73}建成堆，则只需把20与____60_____互相交换。 2012----01 16.数据的不可分割的最小标识单位是___数据项___，它通常不具有完整确定的实际意义， 或不被当作一个整体对待。 17.运算分为加工型运算和引用型运算，读取操作是__引用类型____ 运算。 18.带有头结点的单向循环链表L（L为头指针）中，指针p所指结点为尾结点的条件是 __p next=L____。 19.在双链表中，前趋指针和后继指针分别为prior和next。若使指针p往后移动两个结点， 则需执行语句__*p=p-->next-->next____。 20.元素s1，s2，s3，s4，s5，s6依次进入顺序栈S，如果6个元素的退栈顺序为 s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为____3__。 21. 稀疏矩阵一般采用的压缩存储方法是__三元组表示法____ 。 22. 在一棵树中，___根___ 结点没有双亲。 23.一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右给所有结点编号。 设根结点编号为1，若编号为i的结点有父结点，那么其父结点的编号为__i/2（取下整数）____。 24.二叉树的二叉链表存储结构中判断指针p所指结点为叶子结点的条件是 __（p-->lchild==null）&&( p-->rchild==null)____。 25.边稀疏的无向图采用__邻接表____存储较省空间。 26.除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为__简单回路____。 27.二分查找算法的时间复杂度是___ O(n*log2n)___。 28.要将序列{51，18，23，68，94，70，73}建成堆，则只需把18与__51____相互交换。2012----10 16.下面算法程序段的时间复杂度为__0(n的3次方)____。 for (i=1; i<=n; i++) for (j=1; j<=n; j++) for (k=1;k<=n;k++) x++ 17.所有存储结点存放在一个连续的存储区里利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。这种存储方式是___顺序存储方式___。 18.单链表中指针p指向结点A若要删除A之后的结点存在且不释放存储空间则需要修改指针的操作为p->next=__p->next-->next____。 19.在带有头结点的单链表head中首结点的指针为__head-->next____。 20.在栈结构中允许插入和删除的一端称为__栈顶____。 21.C程序中将对称矩阵Ann的下三角元素压缩存储到n(n+1)/2个元素的一维数组M中设aiji≥j存放在数组Mk中则k的值用i,j表示为__(i+1)*i/2+j____。 22.具有64个结点的完全二叉树的深度为___7___。 23.某二叉树的先序遍历序列为AJKLMNO中序遍历序列为JLKANMO则根结点A的右子树中的结点个数为___3___。 24.三个顶点v1,v2,v3的图的邻接矩阵为 011 101 000 ?? ?? ?? ?? ?? 则该图中顶点v2的出度为__2____。 25.除第一个顶点和最后一个顶点相同外其余顶点不重复的回路称为__简单回路或简单环____。 26.在顺序查找、二分查找、散列查找和索引顺序查找四种查找方法中平均查找长度与元素个数没有关系的查找方法是___散列查找___。 27.堆排序算法的时间复杂度为_O(n*logn2(n))_____。 28.如果要将序列{60182869997578}建成堆则只需把60与___18___相互交换。 2013----01 16.下面算法程序段的时间复杂度为___0(n2平方)_______。 for(i=1;i<=n;i++) for(j=1;j<=i;j++) {x=a［i］［j］; a［i］［j］=a［j］［i］; a［j］［i］=x;} 17.设p指向单链表的最后一个结点，要在最后一个结点之后插入q所指的结点，需执行的语句序列是①p->next=q;②___p=q_______;③p->next=NULL。 18.向一个长度为100的顺序表中第50个元素之前插入一个元素时，需向后移动的元素个数为_____51_____。 19.一个带头结点的链栈LS，现将一个新结点入栈，指向该结点的指针为p，入栈操作为p->next=LS->next和____ls->next=p______。 20.队列操作的原则是___先进先出_______。 21.含有n个顶点的连通图中的任意一条简单路径，其最大长度为____n-1______。 22.在一棵度为3的树中，度为3的结点数为1个，度为2的结点数为2个，度为1的结点数为3个，则度为0的结点数为_____6_____个。 23.某二叉树的中序遍历序列为BACDEFGH，后序遍历序列为BCAEDGHF，则根结点F的左子树上共有____5______个结点。 24.设有向图G的邻接矩阵为A,如果 25.一个有序表A含有15个数据元素，且第一个元素的下标为1，按二分查找算法查找元素A［14］，所比较的元素下标依次是__8,12,14________。 二分查找算法是从low=1开始的。Hgih=有序表长度 1+15/2=8(8<14), 9+15/2=12(12<14) 13+15/2=14(14==14) 26.用n个值构造一棵二叉排序树，它的最大深度为__[log2n]+1________。 27.设记录数为n，则冒泡排序算法在最好情况下所作的比较次数为___n-1_______。 28.二路归并排序算法的时间复杂度为____ O(n*logn2(n))______。 2013---10 16数据中不可分割的最小标识单位是____数据项______。 17双向循环链表中在p所指结点的后面插入一个新结点*t需要修改四个指针分别为t->prior=p__t->next=p->next________p->next->prior=tp->next=t。 18.在带有头结点的循环链表中头指针为head 判断指针p 所指结点为首结点的条件是____p==head->next______。 19元素的进栈次序为123…n 出栈的第一个元素是n 则第k 个出栈的元素是___n-k+1_______。 20在栈结构中允许插入和删除的一端称为_____栈顶_____。 21 100个结点的二叉树采用三叉链表存储时空指针域NULL 有______102____个。 100个结点的二叉树用三叉链表存储共有101+ 1 = 102个空指针域 1代表双亲指针，只有根没有双亲 101：每个结点有两个孩子域，因此一共100*2= 100个指针域，但100个结点中间的连接边一定是100-1=99个，所以空的指针域有200-99=101，也就是n 个结点有n+1个空的指针域 这样加上双亲域，n 个结点的三叉链表共有n+2个空指针域 101是二叉树的空指针域，而三叉树比二叉树每个节点多了父指针。此种存储跟节点是没有父节点的。所以二叉树的空指针域+1(跟节点父指针为空)=三叉树空节点 22.某二叉树的先序遍历序列为ABKLMNO 中序遍历序列为BLKANMO 则该二叉树中结点A 的右孩子为结点___M_______。 23一个二叉树的最少结点个数为____0______。 24图中第一个顶点和最后一个顶点相同的路径称为回路。除第一个顶点和最后一个顶点相同外其余顶点不重复的回路称为___简单回路或简单环_______。 25设查找表有n 个数据元素则二分查找算法的平均查找长度为____（n+1）/n*log2(n+1)--1______。 26用键值通过散列函数获取存储位置的这种存储方式构造的存储结构称为_____散列值_____。 27若在线性表中采用二分查找法查找元素则该线性表必须按值有序并且采用____顺序______存储结构。 28堆分为最小堆和最大堆若键值序列{k 1,k 2,…k n }满足i 2i i 2i 1 k k n (i 1,2,,)k k 2+≥???=???≥??? 则这n 个键值序列{k 1,k 2,…k n }是____最小堆(或最大堆)______。 2014---4 16.数据的基本单位是__数据元素_______。 17.双向循环链表中，在p 所指结点的后面插入一个新结点*t ，需要修改四个指针，分别为 t->prior=P ；t->next=p->next ；___p->next->prior=t______；p->next=t ；。 18.在带有头结点的循环链表中，尾指针为rear ，判断指针P 所指结点为首结点的条件是___ rear->next->next ______。 19.若线性表中最常用的操作是求表长和读表元素，则顺序表和链表这两种存储方式中，较节省时间的是___顺序表______。 20.不含任何数据元素的栈称为___空栈______。 21.稀疏矩阵一般采用的压缩存储方法是____三元组表示法_____。 22.100个结点的二叉树采用二叉链表存储时，用来指向左、右孩子结点的指针域有___99______个。 23.已知完全二叉树的第5层有5个结点，则整个完全二叉树有____20_____个结点。 24.n个顶点的有向图G用邻接矩阵A[1..n，1..n]存储，其第i列的所有元素之和等于顶点V i的____入度_____。 25.具有10个顶点的有向完全图的弧数为____90___。 26.要完全避免散列所产生的“堆积’’现象，通常采用___公共溢出区______解决冲突。 27.在长度为n的带有岗哨的顺序表中进行顺序查找，查找不成功时，与关键字的比较次数为____N+1_。 28.归并排序算法的时间复杂度是____ O(NLOG2N) _____。 全国2005年10月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.若要描述数据处理的变化过程，其正确的次序应为( ) A.处理要求、基本运算和运算、算法 B.处理要求、算法、基本运算和运算 C.基本运算和运算、处理要求、算法 D.算法、处理要求、基本运算和运算 2.从运算类型角度考虑，属于引用型的运算是( ) A.插入、删除 B.删除、修改 C.查找、读取 D.查找、删除 3.若在长度为n的顺序表中插入一个结点，则其结点的移动次数( ) A.最少为0，最多为n B.最少为1，最多为n C.最少为0，最多为n+1 D.最少为1，最多为n+1 4.在一个单链表中，若p所指结点是q所指结点的前驱结点，则在结点p、q之间插入结点s的正确操作是( ) A.s->next=q；p->next=s->next B.p->next=q；p->next=s C.s->next=q->next；p->next=s D.s->next=q->next；p->next=s->next 5.若有一串数字5、6、7、8入栈，则其不可能 ．．．的输出序列为( ) A.5、6、7、8 B.8、7、6、5 C.8、7、5、6 D.5、6、8、7 6.FORTRAN语言对数组元素的存放方式通常采用( ) A.按行为主的存储结构 B.按列为主的存储结构 C.按行或列为主的存储结构 D.按行和列为主的存储结构 7.树是n个结点的有穷集合，( ) A.树的结点个数可以为0，此时称该树为空树 B.树至少含有一个根结点，不能为空 C.树至少含有一个根结点和一个叶子结点 D.树至少含有一个根结点和两个叶子结点 8.深度为k的二叉树至多有( ) A.2k个叶子 B.2k-1个叶子 C.2k-1个叶子 D.2k-1-1个叶子 9.具有10个顶点的有向完全图应具有( ) 浙02142# 数据结构导论试题第 1 页（共 4 页） 全国2011年1月自学考试数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为( ) A.O(1) B.O(n) C.O(log2n) D.O(n) 2.树形结构中，度为0的结点称为( ) A.树根 B.叶子 C.路径 D.二叉树 3.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={ 二00一年下半年全国高等教育自学考试 数据结构导论试卷 一、单项选择题 1.若给定有n个元素的向量,则建立一个有序单向链表的时间复杂性的量级是( ) A.O(1) B.O(n) C.O(n2) D.O(nlog2n) 2.在一个具有n个结点的单链表达中查找值为m的某结点,若查找成功，则平均比较（） A．n B.n/2 C.(n-1)/2 D.(n+1)/2 3．研究数据结构就是研究（） A.数据的逻辑结构 B.数据的存储结构 C.数据的逻辑结构和存储结构 D.数据的逻辑结构,存储结构及其数据在运算上的实现 4.为了方便地对图状结构的数据进行存取操作，则其数据存储结构宜采用（）方式。 A、顺序存储 B、链式存储 C、索引存储 D、散列存储 5．二维数组A[10……20，5……10]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[10，5]的存储地址是1000，则A[18，9]的地址是（） A、1208 B、1212 C、1368 D、1364 6．设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有（）个结点。 A、13 B、12 C、26 D、25 7．下列几种结构中属于树型结构的是（） 8．设无向图G=（V、E）和G’=（V’，E’），如G’为G的生成树，则下面不正确的说法是（） A、G’为G的连通分量 B、G’为G的无环子图 C、G’为G的子图 D、G’为G的极小连通子图且V’=V 9．下列说法中不正确的是（） A、无向图的极大连通子图称为连通分量 B、连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C、图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D、有向图的遍历不可采用广度优先搜索方法 10．对有序表（18，20，25，34，48，62，74，85）用二分查找法查找85，所需的比较次数为（） A、1次 B、2次 C、3次 D、4次 11．散列表的平均查找长度（） A、与处理冲突方法有关而与表的长度无关 B、与处理冲突方法无关而与表的长度有关 C、与处理冲突方法有关且与表的长度有关 D、与处理冲突方法无关且与表的长度无关 12．对ISAM文件的删除记录时，一般（） A、只需做删除标志 B、需移动记录 C、需改变指针 D、一旦删除就需做整理 13．顺序文件适宜于（） A、直接存取 B、成批处理 C、按关键字存取 D、随机存取 14．一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用（）方法。 A、快速排序 B、堆排序 C、插入排序 D、二路归并排序 全国2012年1月数据结构导论试题课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( )A.集合 B.线性结构 C.树形结构 D.图状结 构 2.下面算法程序段的时间复杂度为( ) for ( int i=0; i 数据结构导论复习 第一章概论 1．数据：凡能被计算机存储、加工处理的对象。 2．数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑和处理 3．数据项：又叫字段或域，它是数据的不可分割的最小标识单位。 4．逻辑结构需要注意的几点： ①逻辑结构与数据元素本身的内容无关 ②逻辑结构与数据元素相对位置无关 ③逻辑结构与所有结点的个数无关 5．数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。 6．四类基本逻辑结构（集合、线性结构、树形结构和图形结构）的不同特点？ 答：集合中任何两个结点之间都没有逻辑关系，组织形式松散； 线性结构中结点按逻辑关系依次排列形成一条“锁链”； 树形结构具有分支、层次特性，其形态有点像自然界中的树； 图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以领接。 7．运算是在逻辑结构层次上对处理功能的抽象 8．基本运算的含义？ 答：假如是S上的一些运算的集合，是的一个子集，使得中每一运算都可以“归约”为中的一个或多个运算，而中任一运算不可归约为别的运算，则称中运算为基本运算 9．数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体（S ，）。 10．数据结构涉及数据表示和数据处理两个方面 11．存储结构的含义和四种基本存储方式的基本思想？ 答：存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。 一个存储结构应包含三个主要的部分：存储结点、机内表示和附加设施。 存储结构包括四种存储方式，顺序存储方式、链式存储方式、索引存储方式和散列存储方式。 12．运算实现与运算的联系与区别？ 答：运算指的是数据在逻辑结构S上的某种操作，运算只描述处理功能，不包括处理步骤和方法；而运算实现是指一个完成该运算功能的程序，运算实现的核心是处理步骤的规定，即算法设计。 13．算法的概念和分类？ 答：算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被 全国2014年4月高等教育自学考试 数据结构导论试题 课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.下列几种算法时间复杂度中，最小的是( A ) A.O(log2n) B.O(n) C.O(n2) D.O(1) 2.数据的存储方式中除了顺序存储方式和链式存储方式之外，还有( D ) A.索引存储方式和树形存储方式 B.线性存储方式和散列存储方式 C.线性存储方式和索引存储方式 D.索引存储方式和散列存储方式 3.表长为n的顺序表中做删除运算的平均时间复杂度为( C ) A.O(1) B.O(log2n) C.O(n) D.O(n2) 4.顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为( C ) A.O(1) B.O(log2n) C.O(n) D.O(n2) 5.元素的进栈次序为A，B，C，D，E，出栈的第一个元素为E，则第四个出栈的元素为( C ) A.D B.C C.B D.A 6.带头结点的链队列中，队列头和队列尾指针分别为front和rear，则判断队列空的条件为( A ) A.front==rear B.front!=NULL C.rear!==NULL D.front==NULL 7.深度为5的二叉树，结点个数最多为( A ) 2010年1月高等教育自学考试全国统一命题考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下述文件中适合于磁带存储的是（） A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件 2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（） A.acbed B.becab C.deabc D.cedba 3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 4.在一个图中，所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1 5.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( ) A.O(1) B.O(1og2n) C.O(n) D.O(n2) 6.下述几种排序方法中，要求内存量最大的是( ) A.插入排序 B.快速排序 C.归并排序 D.选择排序 7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( ) A.n-1 B.n C.n+1 D.n(n-1)／2 8.对线性表进行二分查找时，要求线性表必须( ) A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列 9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( ) A.O(1) B.O(n) C.O(nlog2n) D.O(n2) 10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( ) A.n-2 B.n-1 C.n D.n+1 11.有关插入排序的叙述，错误的 ．．．是( ) A.插入排序在最坏情况下需要O(n2)时间 B.插入排序在最佳情况可在O(n)时间内完成 C.插入排序平均需要O(nlog2n)时间 D.插入排序的空间复杂度为O(1) 12.有关树的叙述正确的是( ) A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 13.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为( ) A.rear=rear+1 B.rear=(rear+1)％(m-1) C.rear=(rear+1)％m D.rear=(rear+1)％(m+1) 14.关于串的的叙述，不正确 ．．．的是( ) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 15.对称矩阵A[N][N]，A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)／2]中，则任一上三角元素A[i][j]存于T[k]中，下标k为( ) A.i(i-1)／2+j B.j(j-1)／2+i C.i(j-i)／2+1 D.j(i-1)／2+l 二、填空题(本大题共13小题，每小题2分，共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++) for(j=1；j<=n；j++) 全国20XX 年10月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在表长为n 的顺序表上做插入运算，平均要移动的结点数为（ C ） A.n/4 B.n/3 C.n/2 D.n 2.顺序表中有19个元素，第一个元素的地址为200，且每个元素占一个字节，则第14个元素的存储地址为（ B ）b+(i-1)l A.212 B.213 C.214 D.215 3.由顶点V 1，V 2，V 3构成的图的邻接矩阵为???? ??????010100110，则该图中顶点V 1的出度为（ C ） A.0 B.1 C.2 D.3 4.元素的进栈次序为A ，B ，C ，D ，E ，则退栈中不可能．．． 的序列是（ C ） A.A ，B ，C ，D ，E B.B ，C ，D ，E ，A C.E ，A ，B ，C ，D D.E ，D ，C ，B ，A 5.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（C ） A.23 B.37 C.44 D.46 6.在已知尾指针的单循环链表中，插入一个新结点使之成为首结点，其算法的时间复杂度为（ A ） A.O （1） B.O （log 2n ） C.O （n ） D.O (n 2) 7.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时，查找成功时需比较的次数为（ B ） A.1 B.2 C.3 D.4 8.在查找顺序表各结点概率相等的情况下，顺序按值查找某个元素的算法时间复杂度为 （ B ） A.O (1) B.O (n) C.O (n ) D.O (log 2n) 《数据结构导论》考纲、试题、答案 一、考试说明 本课程为闭卷考试（开卷考试、上交论文、上交作品等考查类课程无考试指导）（根据课程考核实际方式选择），考试时间90分钟，考试题型包括以下题型中的三种（根据每门课程的实际确定题型及分值所占比例）： 1、判断题（正确打√，错误打×，每题3分，共15分） 2、填空（每空2分，共20分） 3、选择题（每题3分，共15分） 4、名词解释（每小题4分，共20分） 5、简答题（每题6分，共30分） 备注：以上题型供参考 二、课程知识要点 第一章 ◆数据结构 ◆实例 第二章 ◆银行排队顺序存储 ◆学生健康登记表 第三章 ◆栈和队列 ◆回文 ◆杨辉三角 第四章 ◆串 ◆文本加密 第五章 ◆内部排序 ◆查找 ◆二叉树 第六章 ◆树 ◆图 ◆数组 第七章 ◆文件 ◆外部排序 备注：根据教材实际章节汇总要点，突出需要掌握的重点内容 三、重点习题 1、判断题 ◆具有n 个结点的线索二叉树上，含有n+1个线索。 ◆三叉链表属于二叉树存储结构。 ◆哈夫曼树不存在度为1的结点。 ◆栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 ◆栈和队列的存储方式既可是顺序方式，也可是链接方式。 ◆二叉树中每个结点的两棵子树是有序的。 2、填空 ◆数据的逻辑结构指 ◆一个算法的时间复杂度 ◆单链表中，增加头结点的目的 ◆表长为0的线性表 ◆串的长度 ◆若两个串的长度相等且对应位置上的字符也相等 ◆常用的插入排序 ◆常用的处理冲突的方法 ◆常用的选择排序方法 ◆衡量一个算法的优劣主要考虑 ◆在有n个结点的二叉链表中，空链域的个数 ◆常用的选择排序方法 全国2010年1月自学考试数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下述文件中适合于磁带存储的是（） A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件 2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（） A.acbed B.becab C.deabc D.cedba 3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 4.在一个图中，所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1 5.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( ) A.O(1) B.O(1og2n) C.O(n) D.O(n2) 6.下述几种排序方法中，要求内存量最大的是( ) A.插入排序 B.快速排序 C.归并排序 D.选择排序 7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( ) A.n-1 B.n C.n+1 D.n(n-1)／2 8.对线性表进行二分查找时，要求线性表必须( ) A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列 9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( ) A.O(1) B.O(n) C.O(nlog2n) D.O(n2) 10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( ) A.n-2 B.n-1 C.n D.n+1 11.有关插入排序的叙述，错误的 ．．．是( ) A.插入排序在最坏情况下需要O(n2)时间 B.插入排序在最佳情况可在O(n)时间内完成 C.插入排序平均需要O(nlog2n)时间 D.插入排序的空间复杂度为O(1) 12.有关树的叙述正确的是( ) A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 13.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为( ) A.rear=rear+1 B.rear=(rear+1)％(m-1) C.rear=(rear+1)％m D.rear=(rear+1)％(m+1) 14.关于串的的叙述，不正确 ．．．的是( ) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 15.对称矩阵A[N][N]，A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)／2]中，则任一上三角元素A[i][j]存于T[k]中，下标k为( ) A.i(i-1)／2+j B.j(j-1)／2+i C.i(j-i)／2+1 D.j(i-1)／2+l 二、填空题(本大题共13小题，每小题2分，共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++) for(j=1；j<=n；j++) for(k=1；k<=n；k++) s=i+j+k； 17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。 ??????????????????????精品自学考料推荐?????????????????? 全国 2019 年 10 月高等教育自学考试 数据结构导论试题 课程代码： 02142 一、单项选择题（本大题共15 小题，每小题 2 分，共 30 分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的 括号内。错选、多选或未选均无分。 1.要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为（） A. 逻辑结构、存储结构、机外表示 B. 存储结构、逻辑结构、机外表示 C.机外表示、逻辑结构、存储结构 D. 机外表示、存储结构、逻辑结构 2.若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常（） A.对数阶量级复杂性大于线性阶量级 B.对数阶量级复杂性小于线性阶量级 C.对数阶量级复杂性等于线性阶量级 D.两者之间无法比较 3.下列关于线性表的基本操作中，属于加工型的操作是（） A. 初始化、求表长度、插入操作 B. 初始化、插入、删除操作 C.求表长度、读元素、定位操作 D. 定位、插入、删除操作 4.在一个单链表中，若p 所指结点不是最后结点， s 指向已生成的新结点，则在p 之后插入 s 所指结点的正确操作是（）A.s–>next=p –>next; p –>next=s; C.s–>next=p; p –>next=s; B.p –>next=s –>next; s –>next=p; D.s–>next=p –>next; p=s; 5.若有三个字符的字符串序列执行入栈操作，则其所有可能的输出排列共有（） A.3 种 B.4 种 C.5 种 D.6 种 6.C 语言对数组元素的存放方式通常采用（） A. 按行为主的存储结构 B. 按列为主的存储结构 C.按行或列为主的存储结构 D. 具体存储结构无法确定 7.根据定义，树的叶子结点其度数（） A. 必大于 0 B. 必等于 0 C.必等于 1 D. 必等于 2 8.二叉树若采用二叉链表结构表示，则对于n 个结点的二叉树一定有（） A.2n 个指针域其中n 个指针为 NULL B.2n 个指针域其中n+1 个指针为 NULL C.2n-1 个指针域其中n 个指针为 NULL D.2n-1 个指针域其中n+1 个指针为 NULL 9.在一个无向图中，所有顶点的度数之和等于边数的（） A.1 倍 B.2 倍 C.3 倍 D.4 倍 10.若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（） 1 全国 2004年 1 月高等教育自学考试 数据 结构导论试题 课程代码： 02142 、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分） 在每小题列出的四个备选项中只有一个是符合题目要求的， 请将其代码填写在题后的 括号内。错选、多选或未选均无分。 1．下列数据组织形式中， （ ）的各个结点可以任意邻接。 A ．集合 B ．树形结构 C ．线性结构 D ．图状结构 2．设某二维数组 A[ 1..n ，1..n]，则在该数组中用顺序查找法查找一个元素的时间复杂 性的量级为（ ） A ．O （log 2n ） B ． O （n ） 2 C ．O （nlog 2n ） D ．O （n 2） 3．在线性表的下列存储结构中，读取元素花费时间最少的是（ A ．单链表 B ．双链表 C ．循环链表 D ．顺序表 4．将一个头指针为 p 的单链表中的元素按与原单链表相反的次序存放，则下列算法段 中的空白处应为 q=NULL; while (p!=NULL) { ( D ． 5．数组通常具有两种基本运算， 即（ A ．创建和删除 C ．读和写 6．除根结点外，树上每个结点（ A ．可有任意多个孩子、任意多个双亲 B ．可有任意多个孩子、一个双亲 C ．可有一个孩子、任意多个双亲 D ．只有一个孩子、一个双亲 p=q; r=q; q=p; p=p -> next; q -> next=r; q=p; r=q; p=p -> next; q -> next=r; r=q; p=p -> next; q=p; q A ． B ． C ． ） B ．索引和修改 7．具有 100 个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、 右孩子，其余（）个指针域为空。 9．如果无向图 G 必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（） A．G 肯定不是完全图B．G 一定不是连通图 C．G 中一定有回路D． G 有 2 个连通分量 10．若构造一棵具有 n 个结点的二叉排序树，最坏的情况下其深度不会超过（ ）A ． n/2 C．（n+1）/2 D． n+1 11．若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值 的前面，下次的查找区间为从原开始位置至（） B．该中间位置－ 1 D ．该中间位置／ 2 ） B．索引存取 D．直接存取 13．若检索顺序文件各个记录的概率相同，设文件占用的页块数为n，则按关键字存取 时的平均访问外存次数为 （ ） A ．n/2 B ．n C ．n/4 D ． log n 1 4 ．下列关键码序列 中， 属于堆的是 （ ） A ．（15，30，22，93，52 ， 71) B ． （15 ， 71 ， 30 ， 22 ， 93 ， 52) C（15，52，22，3071) D（933052221571) 15．已知 10 个数据元素为（ 54，28， 16，34，73， 62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为（） A16283454736260264395 B ．28 ， 16 ， 34 ， 54 ， 62 ， 73 ， 60 ， 26 ， 43 ， 95 C ．28 ， 16 ， 34 ， 54 ， 62 ， 60 ， 73 ， 26 ， 43 ， 95 D ．16 ， 28 ， 34 ， 54 ， 62 ， 60 ， 73 ， 26 ， 43 ， 95 A ． 50 C．100 8．邻接表是图的一种（ A ．顺序存储结构C．索引存储结构 B． 99 D．101 ） B．链式存储结构 B．n A ．该中间位置 C ．该中间位置＋ 1 12．散列文件不能（ A ．随机存取 C．按关键字存取 第一张概论 1.1 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 处理要求-----基本运算和运算-------算法 1.2 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 1.2.2数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。 假如X是S上的一些运算的集合，Y是X的一个子集，使得X中每一运算都可以规约为Y中的一个或多个运算，而Y中任何运算不可规约为别的运算，则称Y中运算（相对于X）为基本运算。 将逻辑结构S和在S上的基本运算集X的整体（S,X）称为一个数据结构。数据结构包括逻辑结构和处理方式。 2012年10月高等教育自学考试全国统一命题考试 数据结构导论试题 课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的。错选、多选或未选均无分。 1.下面几种算法时间复杂度阶数中，值最大的是 A.O(nlog2n) B.O(n2) C.O(n) D.O(2n) 2.即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为 A.正确性 B.易读性 C.健壮性 D.时空性 3.设顺序表的长度为100，则在第40个元素之后插入一个元素所需移动元素的个数为 A.40 B.60 C.61 D.100 4.设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是 A. head->next==head B. head->next==NULL C. head!=NULL D. head==NULL 5.在链栈的运算中，不需要 ．．．判断栈是否为空的是 A.出栈 B.进栈 C.取栈顶元素 D.求链栈的元素个数 6.一个队列的输入序列是A，B，C，D，则该队列的输出序列是 A.A，B，C，D B.B，C，D，A C.D，C，B，A D.C，D，B，A 7.以行序为主序的二维数组a［3］［5］中，第一个元素a［0］［0］的存储地址是100，每个元素占2个存储单元，则a［1］［2］的存储地址是 A.100 B.108 C.114 D.116 8.对任何一棵二叉树T，若叶结点数为5个，则度为2的结点个数为 A.4 B.5 C.6 D.无法确定 9.m个叶结点的哈夫曼树中，其结点总数为 A.m B.2m+1 全国2012年1月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( ) A.集合 B.线性结构 C.树形结构 D.图状结构 2.下面算法程序段的时间复杂度为( ) for ( int i=0; i A. 先进先出的线性表 B. 先进后出的线性表 C. 后进先出的线性表 D.随意进出的线性表 8.10阶上三角矩阵压缩存储时需存储的元素个数为( ) A.11 B.56 C.100 D.101 9.深度为k（k≥1）的二叉树，结点数最多有( ) A.2k个 B.(2k -1)个 C.2k-1个 D.(2k+1)个 10.具有12个结点的二叉树的二叉链表存储结构中，空链域NULL的个数为( ) A. 11 B.13 C. 23 D. 25 11.具有n个顶点的无向图的边数最多为( ) A.n+1 B.n(n+1) C.n(n-1)/2 D.2n(n+1) 12.三个顶点v1,v2,v3的图的邻接矩阵为 010 001 010 ?? ?? ?? ?? ?? ，该图中顶点v3的入度为( ) A. 0 B. 1 C. 2 D. 3 13.顺序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找 的概率是相同的，且每个元素的关键字值不相同。用顺序查找法查找时，平均比较次数约为( ) A.20000 B.30000 C.40000 D.60000 14.外存储器的主要特点是( ) A.容量小和存取速度低 B.容量大和存取速度低 C.容量大和存取速度高 D.容量小和存取速度高 15.在待排数据基本有序的前提下，效率最高的排序算法是( ) A.直接插入排序 B.直接选择排序 C.快速排序 D.归并排序 浙02142# 数据结构导论试题第 2 页共 5 页 绝密★考试结束前 全国2018年4月高等教育自学考试 数据结构导论试题 课程代码:02142 请考生按规定用笔将所有试题的答案涂二写在答题纸上三 选择题部分 注意事项: 1.答题前,考生务必将自己的考试课程名称二姓名二准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上三 2.每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑三如需改动,用橡皮擦干净后,再选涂其他答案标号三不能答在试题卷上三 一二单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将 答题纸”的相应代码涂黑三错涂二多涂或未涂均无分三 1.数据的逻辑结构分为四种,其中结构最复杂的是 A.集合 B.线性结构 C.树形结构 D.图结构 2.下面程序是矩阵转置算法MM的实现过程,其时间复杂度为 const int n=3; void MM(int A[n][n]) { int i,j,temp; for(i=0;i 3.设顺序表的表长为n,则删除一个元素在最坏情况下元素移动次数为 A.n-2 B.n-1 C.n D.n+1 4.带头结点的双向循环链表L为空的条件是 A.L->next==L->prior B.L->prior==NULL C.(L->next==L)&&(L->prior==L) D.(L->next==L)&&(L->prior=NULL) 5.执行进栈操作,在元素x进栈前需要进行的操作是 A.判断栈是否满,若栈未满,top值加1 B.判断栈是否空,若栈未空,top值加1 C.判断栈是否满,若栈未满,top值减1 D.判断栈是否空,若栈未空,top值减1 6.关于队列,下列叙述正确的是 A.队列的元素个数可以无穷大 B.队列中元素的类型可以不同 C.队列是一个非线性的序列 D.队列的特点是先进先出 7.设循环队列的元素存放在一维数组Q[30]中,队列非空时,front指示队列首结点的前一个位置,rear指示队列尾结点三如果队列中元素的个数为10,front的值为25,则rear应指向的元素是 A.Q[4] B.Q[5] C.Q[14] D.Q[15] 8.二叉树第i(i≥1)层上的结点数最多为 A.2i-1 B.i-1 C.2*i D.2*(i-1) 9.关于二叉链表,下列叙述正确的是 A.二叉链表是二叉树唯一的链式存储结构 B.对二叉链表的访问可以从任意结点开始 C.每个二叉链表不需要有一个指向根节点的指针 D.二叉链表的结点结构包含一个数据域和两个指针域 10.假设初始森林中共有n棵二叉树,每棵树中都仅有一个孤立的结点三将该森林构造成哈夫 曼树,则最终求得的哈夫曼树的结点数为 A.n-1 B.n C.2n-1 D.2n 11.无向图中的极大连通子图是 A.连通分量 B.生成树 C.强连通分量 D.强连通图 12.在用邻接表表示图时,对图进行深度优先搜索遍历的算法的时间复杂度为 A.O(n) B.O(n+e) C.O(n2) D.O(n3) ： 第一张概论 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 ~ 处理要求-----基本运算和运算-------算法 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 — 1.2.2 数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 { 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。自考数据结构导论20051年10月试卷
全国自学考试数据结构导论试题及答案(4套)
数据结构导论年月试题
数据结构导论试题和部分答案
自考数据结构导论复习资料
自考数据结构导论
02142数据结构导论2010年1 月份真题及答案
全国数据结构导论10月高等教育自学考试试题与答案
《数据结构导论》考纲、试题、答案
2010年1月自考数据结构导论真题
2020年10月全国数据结构导论自考试题及答案解析.doc
自考数据结构导论试题真题
自考02142《数据结构导论》串讲笔记
02142数据结构导论份真题及答案.doc
自考数据结构导论20120年01月试卷
【自考真题】2018年4月数据结构导论02142试题
自考02142《数据结构导论》串讲笔记
相关主题
文本预览