数据结构导论真题分类整理详细
第一章概述真题
16.下列程序段的时间复杂度为____________。
for(i=1；i<=n；i++)
for(j=1；j<=n；j++)
for(k=1；k<=n；k++)
s=i+j+k；
17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。
16.下列程序段的时间复杂度为________。
i=0；s=0；
while（i 17.数据的逻辑结构被分为集合结构、_____、树形结构和图状结构4种。 1.数据的不可分割的最小标识单位是（） A.数据项 B.数据记录 C.数据元素 D.数据变量 2. for（i=0；i for（j=0；j c［i］［j］=0； for（i=0；i for（j=0；j for（k=0；k c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］； 上列程序的时间复杂度为（） A.O(m+n×t) B.O(m+n+t) C.O(m×n×t) D.O(m×t+n) 16.在数据结构中，数据的存储结构有顺序存储方式、链式存储方式、_____和散列存储方式等四种。 17.作为一个算法输入的数据所含数据元素的数目，或与此数目有关的其他参数，称为______。 1.从逻辑上可以把数据结构分为（） A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 2.关于算法的描述，不正确的是（） A.算法最终必须由计算机程序实现 B.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 C.健壮的算法不会因非法的输入数据而出现莫名其妙的状态 D.算法的优劣与算法描述语言无关 16.在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为_____。 17.存储结点之间通常有四种基本存储方式，即顺序存储方式、索引存储方式、_____和散列存储方式。 1.在数据结构中，数据的基本单位是( ) A.数据项 B.数据元素 C.数据对象 D.数据文件 2. k=1; for（i=0；i for（j=0；j A［i］［j］=k++； 上述程序段的时间复杂度为( ) A.O（n2） B.O（n）C.O（2n）D.O（1） 16.数据的逻辑结构通常包括集合、线性结构、____________和图状结构。 1.在数据结构中，从逻辑上可以把数据结构分成( ) A.线性结构和非线性结构 B.紧凑结构和非紧凑结构 C.动态结构和静态结构 D.内部结构和外部结构 2.for（i=0；i for（j=0；j A［i］［j］=i*j； 上面算法的时间复杂度为( ) A.O(m2) B.O(n2) C.O(m×n) D.O(m+n） 16.如果操作不改变原逻辑结构的―值‖，而只是从中提取某些信息作为运算结果，则称该类运算为_ _型运算。 3．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（） A．线性结构 B.树形结构 C.线性结构和树型结构 D.线性结构和图状结构 16．在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为_______。17．每个存储结点只含一个数据元素，所有存储结点连续存放。此外增设一个索引表，索引表中的索引指示各存储结点的存储位置或位置区间端点。按这种方式组织起来的存储结构称为_______。 1.数据的基本单位是（）A.数据项 B.数据类型 C.数据元素 D.数据变量 2.下列程序的时间复杂度为（） i=0；s=0； while（s A.O（n） B.O（n2） C.O（n） D.O（n2） 16.在数据结构中，数据的逻辑结构分为集合、_____、树形结构和图状结构等四类。 17.通常从正确性、易读性、_____和高效率等4个方面评价算法（包括程序）的质量。 1.数据结构中所定义的数据元素，是用于表示数据的（） A.最小单位 B.最大单位 C.基本单位 D.不可分割的单位 2.数据的四种基本存储结构是指（） A.顺序存储结构、索引存储结构、直接存储结构、倒排存储结构 B．顺序存储结构、索引存储结构、链式存储结构、散列存储结构 C．顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构 D.顺序存储结构、链式存储结构、树型存储结构、图型存储结构 16.数据表示和________________是程序设计者所要考虑的两项基本任务。 17.一个算法通常可从正确性、易读性、健壮性和________________等四个方面评价、分析。 1.若要描述数据处理的变化过程，其正确的次序应为( ) A.处理要求、基本运算和运算、算法 B.处理要求、算法、基本运算和运算 C.基本运算和运算、处理要求、算法 D.算法、处理要求、基本运算和运算 2.从运算类型角度考虑，属于引用型的运算是( ) A.插入、删除 B.删除、修改 C.查找、读取 D.查找、删除 16.算法通常可分为程序、伪语言算法和__________三种类型。 17.时间复杂性描述量级中，若某算法达到__________量级，则该算法通常是不可计算的。 1.数据的四种基本逻辑结构是指( ) A.数组、链表、树、图形结构 B.线性表、链表、栈队列、数组广义表 C.线性结构、链表、树、图形结构 D.集合、线性结构、树、图形结构 2.数据结构中，通常采用两种方法衡量算法的时间复杂性，即( ) A.最大时间复杂性和最小时间复杂性 B.最好时间复杂性和最坏时间复杂性 C.部分时间复杂性和总体时间复杂性 D.平均时间复杂性和最坏时间复杂性 16.根据不同的描述方式，对数据的操作运算通常可分为加工型运算和_______两种基本类型。 17.数据结构中的算法，通常采用最坏时间复杂度和______两种方法衡量其效率。 1.要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为（） A.逻辑结构、存储结构、机外表示 B.存储结构、逻辑结构、机外表示 C.机外表示、逻辑结构、存储结构 D.机外表示、存储结构、逻辑结构 2.若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常（） A.对数阶量级复杂性大于线性阶量级 B.对数阶量级复杂性小于线性阶量级 C.对数阶量级复杂性等于线性阶量级 D.两者之间无法比较 16.从数据结构的观点，数据通常可分为三个层次，即：数据、数据元素和___________。 17.用程序设计语言、伪程序设计语言并混合自然语言描述的算法称为___________算法。 1．下列数据组织形式中，（）的各个结点可以任意邻接。 A．集合 B．树形结构 C．线性结构 D．图状结构 2．设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（ A．O（log2n） B．O(n) C．O(nlog2n) D．O(n2) 16．下列程序段的时间复杂性量级是_____________。 for (i=1;i for (j=1; j t=t+1; 第二章线性表第三章栈、队列、数组真题 5.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( ) A.O(1) B.O(1og2n) C.O(n) D.O(n2) 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 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 18.在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点___的。 19.在栈结构中，允许插入的一端称为____________。 20.从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动____________个元素。 21.一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为____________。 22.循环队列被定义为结构类型，含有三个域：data、front和rear，则循环队列sq为空的条件是 ____________。 29.有一字符串的次序为-3*y+a／y！2，试利用栈将输出次序改变为3y*-ay！2／+，试写出进栈和退栈的操作步骤。(用push(x)表示x进栈，pop(x)表示x退栈) 1.在表长为n的顺序表上做插入运算，平均要移动的结点数为（） A.n/4 B.n/3 C.n/2 D.n 2.顺序表中有19个元素，第一个元素的地址为200，且每个元素占一个字节，则第14个元素的存储地址为（） A.212 B.213 C.214 D.215 4.元素的进栈次序为A，B，C，D，E，则退栈中不可能 ．．．的序列是（） A.A，B，C，D，E B.B，C，D，E，A C.E，A，B，C，D D.E，D，C，B，A 6.在已知尾指针的单循环链表中，插入一个新结点使之成为首结点，其算法的时间复杂度为( ) A.O（1） B.O（log2n） C.O（n） D.O(n2) 10.在线性表的下列存储结构中进行插入、删除运算，花费时间最多的是（） A.单链表 B.双链表 C.顺序表 D.单循环链表 11.在栈中进行插入和删除操作的一端称为（） A.栈顶 B.栈底 C.任意位置 D.指定位置 15.带表头结点链队列的队头和队尾指针分别为front和rear，则判断队空的条件为（） A.front==rear B.front!=NULL C.rear!=NULL D.front==NULL 18.线性表中所含结点的个数称为______。 19.向一个栈顶指针为top的链栈中插入一个新结点*p时，应执行______和top=p操作。 20.设一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的退栈顺序为s2，s3，s4， s6，s5，s1，则顺序栈的容量至少为______。 35.设顺序表va中的数据元素递增有序。试编写算法实现将x插入到顺序表的适当位置上，以保持该 表的有序性。 3.若线性表最常用的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储方式是（） A.单链表 B.双链表 C.单循环链表 D.顺序表 4.设单链表中指针p指向结点A，要删除A之后的结点(若存在)，则修改指针的操作为（） A.p—>next=p—>next—>next B.p=p—>next C.p=p—>next—>next D.p—>next=p 5.向一个栈顶指针为hs的链栈中插入一个*s结点时，应执行的操作为（） A.hs—>next=s; B.s—>next=hs;hs=s; C.s—>next=hs—>next;hs—>next=s; D.s—>next=hs;hs=hs—>next; 6.设循环队列的元素存放在一维数组Q[0‥30]中，队列非空时，front指示队头元素的前一个位置，rear 指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应指向的元素是（） A.Q[4] B.Q[5] C.Q[14] D.Q[15] 7.定义二维数组A[1‥8，0‥10]，起始地址为LOC，每个元素占2L个存储单元，在以行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（） A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L 18.在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向____和_____。 19.在有n个元素的链队列中，入队和出队操作的时间复杂度分别为______和______。 20.在栈结构中，允许插入的一端称为______;在队列结构中，允许插入的一端称为______。 21.在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为______。 3.在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（）A.直接前趋 B.直接后继 C.开始结点 D.终端结点 4.将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（） A.n B.2n-1 C.2n D.n2 5.栈和队列共同具有的特点是（） A.都是先进后出 B.都是先进先出 C.只允许在端点进行操作运算 D.既能先进先出，也能先进后出 6.若用一个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为（）A.1和5 B.2和4 C.4和2 D.5和1 7.数组A[0..5][0..5]的每个元素占5个字节，将其以列为主序存储在起始地址为1000的内存单元中，则元素A［5］［5］的地址是（）A.1175 B.1180 C.1205 D.1210 18.在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动______个元素。 24.两个串是相等的，当且仅当两个串的长度相等且________的字符都相同。 34.设两个数据元素均为整型数据的线性表A=(a1，a2，…，an)和B=(b1，b2，…，bm)。若n=m且ai=bi（i=1，2,…，n）则认为A=B；若ai=bi（i=1，2,…，j）且aj+1 3.线性表采用链式存储结构时，要求内存中可用存储单元的地址( ) A.必须是连续的 B.必须是部分连续的 C.一定是不连续的 D.连续和不连续都可以 4.设h是指向非空带表头结点的循环链表的头指针，p是辅助指针。执行程序段 p=h; while (p->next->next!=h) p=p->next; p->next=h; 后（其中，p->next为p指向结点的指针域），则( ) A.p->next指针指向链尾结点 B.h指向链尾结点 C.删除链尾前面的结点 D.删除链尾结点 5.设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( ) A.236 B.239 C.242 D.245 6.一个栈的入栈序列是a,b,c,d,e，则栈的输出序列不可能是( )A.dceab B.decba C.edcba D.abcde 7.元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top作为栈顶指针，则出栈处理后，top的值应修改为( ) A.top=top B.top=n-1 C.top=top-1 D.top=top+1 17.设双链表中结点的前趋指针和后继指针的域名分别为t1和r1，指针s指向双链表中的一个结点（该结点既非头结点，也非尾结点），则删除s指针所指向结点的操作为―s->tl->r1=s->r1；‖和―_______‖。 32.如题32图所示，在栈的输入端有6个元素，顺序为A，B，C，D，E，F。能否在栈的输出端得到序列DCFEBA及EDBFCA？若能，给出栈操作的过程，若不能，简述其理由。 35.某带头结点的单链表的结点结构说明如下： typedef struct node1 { int data; struct node1 *next }node； 试设计一个算法int copy(node *head1, node *head2)，将以head1为头指针的单链表复制到一个不带头结点且以head2为头指针的单链表中。 3.设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为( ) A.5 B.6 C.7 D.9 4.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→r link 表示，则同样表示p指针所指向结点的表达式是( ) A.p→llink B.p→rlink C.p→llink→llink D.p→llink→rlink 5.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是( ) A. 110 B. 108 C. 100 D. 120 6.设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是( ) A.DCBA B.CDAB C.DBAC D.DCAB 7.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top为栈顶指针，则当做出栈处理时，top变化为( ) A.top++ B.top-- C.top不变 D.top=0 17.设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表中，使之成为第一个结点，则所需的操作为―p→next=head；‖和―________‖。 18.单链表中逻辑上相邻的两个元素在物理位置上______相邻。 19.在一个长度为n的数组中删除第i个元素（1≤i≤n）时，需要向前移动的元素的个数是________。 31.如题31图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，试写出在栈的输入端三个可能的输入序列。 34.下面程序段为删除循环链表中第一个info域值等于x的结点，请填上程序中缺少的部分。循环链表的结构如题34图所示： struct node{ int info; struct node *link; } int Delete (struct node *head, int x) { struct node *p, *q; /*p:当前处理的结点；q：p的前驱结点*/ if (! head ) return (0); if (head→link ==head) { if (head→info==x) { free (head); head=NULL；return (x) } return (0); } p=head; q=head; while (q→link!=head) q=(1) ; while (p→link!=head) { if (p→info==x) { (2) ; if (p==head) head=(3) ; free (p);return (x); } else { q=p ;（4）;} } return (0); } 1．关于栈和队列的说法中正确的是（） A．栈和队列都是线性结构 B.栈是线性结构，队列不是线性结构 C.栈不是线性结构，队列是线性结构 D.栈和队列都不是线性结构 2．关于存储相同数据元素的说法中正确的是（） A顺序存储比链式存储少占空间 B.顺序存储比链式存储多占空间 C.顺序存储和链式存储都要求占用整块存储空间 D.链式存储比顺序存储难于扩充空间 3．从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（） A．线性结构 B.树形结构 C.线性结构和树型结构 D.线性结构和图状结构 4．已知一个单链表中，指针q指向指针p的前趋结点，若在指针q所指结点和指针p所指结点之间插入指针s所指结点，则需执行（） A．q→next=s；p→next=s；B.q→next=s；s→next=p；C.q→next=s；q→next=p；D.q→next=s；s→next=q；5．在长度为n的线性表中删除一个指针p所指结点的时间复杂度是（） A．O(n) B.O(1) C.O(log2n) D.O(n2) 6．设一个栈的输入序列是a,b,c,d，则所得到的输出序列（输入过程中允许出栈）不可能出现的是（）A．a，b，c，d B.a，b，d，c C.d，c，b，a D.c，d，a，b 7．关于串的叙述中，正确的是（） A．空串是只含有零个字符的串 B.空串是只含有空格字符的串 C.空串是含有零个字符或含有空格字符的串 D.串是含有一个或多个字符的有穷序列 8．在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（）A．front==rear B.(front+1)%m==rear C.rear+1==front D.(rear+1)%m==front 9．设有二维数组A［n］［n］表示如下：，则A［i］［i］（0≤i≤n-1）的值为（） A．i*(i-1)/2 B.i*(i+1)/2 C.(i+2)*(i+1)/2 D.i2/2 18．在顺序表上读表元算法的时间复杂度为_______。 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］的存储位置为_______。 29．有一字符串序列为5*-x-y/x+2，利用栈的运算将其输出结果变为5x-*yx+/-2，试写出该操作的入 栈和出栈过程（采用push(a)表示a入栈，pop(a)表示a出栈）。 34．设单链表的结点结构如下： struct node{datatype data; struct node*next; } 试编写一个函数int count(struct node *head,datatype x)统计单链表中数据域为x的结点个数。 3.若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（） A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表 4.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动的元素的个数是（） A.n-i B.n-i+1 C.n-i-1 D.i 5.顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为（） A.s.elem［top］=e；s.top=s.top+1； B.s.elem［top+1］=e；s.top=s.top+1； C.s.top=s.top+1；s.elem［top+1］=e； D.s.top=s.top+1；s.elem［top］=e； 6.循环队列sq中，用数组elem［0··25］存放数据元素，sq.front指示队头元素的前一个位置，sq.rear 指示队尾元素的当前位置，设当前sq.front为20，sq.rear为12，则当前队列中的元素个数为（） A.8 B.16 C.17 D.18 7.设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（） A.13 B.35 C.17 D.36 18.顺序表的存储密度为________，而链表的存储密度为______。 19.对于栈只能在________插入和删除元素。 20.在循环队列中，存储空间为0～n-1,设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么队满标志为front=(rear+1)%n，队空标志为________。 3.对于长度为n的顺序表执行删除操作，则其结点的移动次数（） A.最少为0，最多为n B.最少为1，最多为n C.最少为0，最多为n-1 D.最少为1，最多为n-1 4.在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的正确操作是（ A. p->next=q B. p->next=q->next C. p=q->next D. p->next=q->next->next 5.有关栈的描述，正确的是（） A.栈是一种先进先出的特殊的线性表 B.只能从栈顶执行插入、删除操作 C.只能从栈顶执行插入、栈底执行删除 D.栈顶和栈底均可执行插入、删除操作 6.二维数组A［10］［20］采用按行为主序的存储方式，每个元素占4个存储单元，若A［0］［0］的存储地址为300，则A［10］［10］的地址为（） A.700 B.1120 C.1180 D.1140 18.对长度为n的顺序表执行删除操作，其删除算法在最坏情况下的时间复杂性为________________。 19.串是一种特殊的线性表，串常见的存储结构有顺序存储和________________两种方式。 20.我们通常把队列中允许插入的一端称为________________。 21.二维数组在机器级的具体实现，通常均采用________________存储结构。 34.试编写一个函数，以读取单链表的第i个元素。 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.按行和列为主的存储结构 18.对顺序表执行删除操作，其删除算法的平均时间复杂性为__________。 19.若head表示循环链表的头指针，t表示尾结点，则头指针head与尾结点t之间的关系可表示为_____。 20.我们通常把队列中允许删除的一端称为_______。 21.二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是__________。 34.若循环单链表长度大于1，p为指向链表中某结点的指针，试编写一算法删除p结点的前驱结点。 3.下列关于线性表的叙述中，不正确的是( ) A.线性表是n个结点的有穷序列 B.线性表可以为空表 C.线性表的每一个结点有且仅有一个前趋和一个后继 D.线性表结点间的逻辑关系是1:1的联系 4.在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是( ) A.p=p->next B.p->next=p->next C.p->next=p->next->next D.p->next=p 5.栈和队列( ) A.共同之处在于二者都是先进先出的特殊的线性表 B.共同之处在于二者都是先进后出的特殊的线性表 C.共同之处在于二者都只允许在顶端执行删除操作 D.没有共同之处 6.二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是( )A.127 B.142 C.150 D.157 18.判断带头结点head的单链表为空的条件是___________。 19.若顺序表每个元素长度均为5，其中第一个元素的存储地址为30，则第6个元素的存储地址为____。 20.若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则判断循环队列为满的条件是_______。 21.对于顺序存储结构的二维数组，通常采用___________两种存放方式存储数据元素。 34.试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。 3.下列关于线性表的基本操作中，属于加工型的操作是（） A.初始化、求表长度、插入操作 B.初始化、插入、删除操作 C.求表长度、读元素、定位操作 D.定位、插入、删除操作 4.在一个单链表中，若p所指结点不是最后结点，s指向已生成的新结点，则在p之后插入s所指结点的正确操作是（） A.s–>next=p–>next; p–>next=s; B.p–>next=s–>next; s–>next=p; C.s–>next=p; p–>next=s; D.s–>next=p–>next; p=s; 5.若有三个字符的字符串序列执行入栈操作，则其所有可能的输出排列共有（） A.3种 B.4种 C.5种 D.6种 6.C语言对数组元素的存放方式通常采用（） A.按行为主的存储结构 B.按列为主的存储结构 C.按行或列为主的存储结构 D.具体存储结构无法确定 18.对顺序表执行插入操作，其插入算法的平均时间复杂性为___________。 19.在具有n个单元、且采用顺序存储的循环队列中，队满时共有___________个元素。 20.若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则循环队列为空的条件是___________。 21.二维数组A[10][20]采用按行为主序的存储方式，每个元素占4个存储单元，若A[0][0]的存储地址为300，则[A][10][10]的地址为___________。 34.设某单链表中，存在多个结点其数据值均为D，试编写一算法统计该类结点的个数。 2．设某二维数组A［1..n，1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为（ A．O（log2n） B．O(n) C．O(nlog2n) D．O(n2) 3．在线性表的下列存储结构中，读取元素花费时间最少的是（） A．单链表 B．双链表 C．循环链表 D．顺序表 4．将一个头指针为p的单链表中的元素按与原单链表相反的次序存放，则下列算法段中的空白处应为（） q=NULL; while (p!=NULL) { （） } p=q; A．r=q; q=p; p=p -> next; q -> next=r; B．q=p; r=q; p=p -> next; q -> next=r; C．r=q; p=p -> next; q=p; q -> next=r; D．q=p; p=p -> next; r=q; q -> next=r; 5．数组通常具有两种基本运算，即（） A．创建和删除 B．索引和修改 C．读和写 D．排序和查找 17．在顺序存储的线性表（a1,a2…，an）中的第i (1≤i≤n)个元素之前插入一个元素，则需向后移动___个元素。 18．在栈的顺序实现中，若栈不满，则进栈操作可以用下列算法片断实现： ______； sq -> data[sq -> top]=x； 19．链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的______。 29．如图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可能的输入序列。（5分） 34．设某头指针为head的单链表的结点结构说明如下：（6分） typedef struct node1 { int data; struct node1*next }node; 试设计一个算法void change (node*head),将该单链表中的元素按原单链表相反的次序重新存放，即第一个结点变成最后一个结点，第二个结点变为倒数第二个结点，如此等等。 35．编写一个算法void DisplayQueue ()，产生50个300～600之间的随机整数（调用一次MyRand()可产生一个符合条件的随机整数）。每产生一个数据，若是奇数，则入队列，若是偶数，则从队首取出一个数据。要求：（8分） （1）队列用链表实现； （2）每产生一个数显示一次相应操作后的队列当前状态； （3）无需定义函数int MyRand()； （4）显示队列可调用函数void DisOne (QueptrTp lq)，也无需定义； （5）设链队列定义为： typedef struct linked_queue { int data; struct linked_queue*next; }LqueueTp; typedef struct queueptr { LqueueTp *front, *rear; }QueptrTp; QueptrTp lq; 第四章树真题 2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（） A.acbed B.becab C.deabc D.cedba 3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 12.有关树的叙述正确的是( ) A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 24.对于一棵满二叉树，若有m个叶子，则树中结点数为____________。 30.已知一棵二叉树的先根遍历序列为ABCDEGHF，中根遍历序列为CBEDAGFH，画出该二叉树。 34.二叉树按二叉链表形式存储，编写一个算法判别给定的二叉树是否为完全二叉树。 5.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（） A.23 B.37 C.44 D.46 12.用n个值构造一棵二叉排序树，它的最大高度为（） A.n/2 B. n C. n+1 D.log2n 21.若满二叉树的结点数为n，则其高度为________。 22.在一棵具有n个结点的完全二叉树中，从树根起，自上而下、从左到右地给所有结点编号。若编号为i的结点有父结点，那么其父结点的编号为_____。 23.深度为k的二叉树，结点数最多有________个。 24.某二叉树的后根遍历为ABKCBPM，则该二叉树的根为______。 29.某通讯电文由A，B，C，D，E，F六个字符编码组成，每个字符编码在电文中出现的次数分别是6， 5，9，10，20，1，试画出这六个字符编码所用的哈夫曼树。 30.已知一棵二叉树的顺序存储结构如题30图所示，其中∧表示虚结点，试构造该二叉树。 34.若两棵二叉树B1和B2皆为空，或者皆不空且B1的左、右子树和B2的左、右子树分 别相似，则称二叉树B1和B2相似。试编写算法，判别给定两棵二叉树是否相似。 8.具有n个结点的二叉树，拥有指向孩子结点的分支数目是（） A.n-1 B.n C.n+1 D.2n 9.对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（） A.99 B.98 C.97 D.50 10.有m个叶子结点的哈夫曼树，其结点总数是（） A.2m-1 B.2m C.2m+1 D.2(m+1) 22.深度为k的二叉树至多有______个结点，最少有______个结点。 29.已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请构造出该二叉树，并给出该二叉树的后序序列。 30.将题30图所示的由三棵树组成的森林转化为一棵二叉树。 8.含有n个结点的二叉树采用二叉链表存储时，空指针域的个数为（） A.n-1 B.n C.n+1 D.n+2 9.在一棵深度为H的完全二叉树中，所含结点的个数不少于（） A.2H-1-1 B.2H-1 C.2H-1 D.2H 19.对一棵深度为10的满二叉树按层编号，则编号为51的结点，它的双亲结点编号为_______。 21.具有n个叶子结点的哈夫曼树，其结点总数为________。 22.一棵具有n个结点的树，所有非终端结点的度均为k，则该树中叶子结点个数为________。 25.某二叉树的后根遍历序列为abd，中根遍历序列为adb，则它的先根遍历序列为________。 30.画出题30图所示的二叉树的二叉链表存储结构。 35.设二叉树的结点类型定义如下： typedef struct node{ datatype data; struct node*lchild,*rchild; }Bitree; Bitree*t; 试编写一个计算二叉树深度的递归算法(int Depth(Bitree*t))。 8.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是( ) A.高度等于其结点数 B.任一结点无左孩子 C.任一结点无右孩子 D.空或只有一个结点 9.在完全二叉树中，若一个结点是叶结点，则它没有( ) A.左孩子结点 B.右孩子结点 C.左孩子结点和右孩子结点 D.左孩子结点，右孩子结点和兄弟结点 12.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不超过( )A.n/2 B.n C.n+1/2 D.n+1 19.在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则需平均比较的结点数为____。 20.深度为15的满二叉树上，第11层有_______个结点。 21.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的左孩子的编号为________。 30.已知一棵二叉树的中根遍历序列和后根遍历序列分别为BDAFEHGC和DBFHGECA，试画出这棵二叉树。 8.除根结点外，树上每个结点( ) A.可有任意多个孩子、一个双亲 B.可有任意多个孩子、任意多个双亲 C.可有一个孩子、任意多个双亲 D.只有一个孩子、一个双亲 9.题9图中树的度为( ) A.2 B.3 C.5 D.8 20.设F、C是二叉树中的两个结点，若F是C的祖先结点，则在采用后根遍历方法遍历该二叉树时，F和C的位置关系为：F必定在C的__________。 21.若用后根遍历法遍历题21图所示的二叉树，其输出序列为__________。 29.分别写出题29图中二叉树的先根、中根、后根遍历序列。 10．高度为h的完全二叉树中，结点数最多为（）A．2h-1 B.2h+1 C.2h-1 D.2h 11．由m棵结点数为n的树组成的森林，将其转化为一棵二叉树，则该二叉树中根结点的右子树上具有的结点个数是（）A．mn B.mn-1 C.n(m-1) D.m(n-1) 21．有4个结点且深度为4的二叉树的形态共有_______种。 22．某二叉树的先根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则该二叉树中根结点的右孩子是_______。 30．某二叉树的先根遍历序列为ABIJCDFGHE，中根遍历序列为IJBADGFHCE，试画出该二叉树，并写出它的后序遍历序列。 8.含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为（） A.3 B.4 C.5 D.6 9.对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（） A.24 B.25 C.98 D.99 21.三个结点可构成________种不同形态的二叉树。 22.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中______个用于链接孩子结点。 29.已知一棵二叉树的中根序列和后根序列分别为B、D、C、E、A、F、H、G和D、E、C、B、H、 G、F、A，试画出这棵二叉树，并给出其先根序列。 7.关于二叉树性质的描述，正确的是（） A.二叉树结点的个数可以为0 B.二叉树至少含有一个根结点 C.二叉树若存在两个结点，则必有一个为根，另一个为左孩子 D.二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子 8.具有4个结点的二叉树可有（） A.4种形态 B.7种形态 C.10种形态 D.11种形态 22.深度为k的满二叉树其叶子结点个数共有________________个。 23.二叉树通常采用________________两种存储结构表示。 29.试采用类C语言，给出二叉树的二叉链表结构描述。 35.若二叉树采用二叉链表表示，试给出二叉树先根遍历的非递归算法描述 7.树是n个结点的有穷集合，( ) A.树的结点个数可以为0，此时称该树为空树 B.树至少含有一个根结点，不能为空 C.树至少含有一个根结点和一个叶子结点 D.树至少含有一个根结点和两个叶子结点 8.深度为k的二叉树至多有( ) A.2k个叶子 B.2k-1个叶子C.2k-1个叶子 D.2k-1-1个叶子 22.树在数据结构中常采用孩子链表表示法、__________三种存储结构表示。 23.若某二叉树中度为1的结点数为4，度为2的结点数为6，则该树叶子结点数为__________。29．对于如题29图所示二叉树，分别写出其先根遍历，中根遍历，后根遍历的结点访问序列。 35.若二叉树用二叉链表表示，试编写一算法计算一棵二叉树的叶子总数（可采用递归算法描述）。7．深度为k的二叉树最多有（）个结点 22.若某二叉树的先根遍历序列为CEDBA，中根遍历序列为DEBAC，则其后根遍历序列为______。 23.具有n个结点的完全二叉树，其深度为___________。 29．已知某二叉树的顺序存储结构如图所示，试画出该二叉树。 35.二叉树是由所有度数不大于2的结点构成的一种特定树，若某结点度为2，则该结点有左右两个孩子，请编写算法计算一二叉树所有度数为2的结点个数。 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 22.树的遍历主要有先根遍历、后根遍历和___________三种。 23.深度为k的完全二叉树至少有___________个结点。 29.已知某二叉树如下图所示，试给出其二叉链表及顺序存储结构表示。 35.若二叉树存储结构采用二叉链表表示，试编写一算法，计算一棵二叉树的所有结点数 6．除根结点外，树上每个结点（） A．可有任意多个孩子、任意多个双亲 B．可有任意多个孩子、一个双亲 C．可有一个孩子、任意多个双亲 D．只有一个孩子、一个双亲 7．具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余（）个指针域为空。 A．50 B．99 C．100 D．101 20．设有k个结点，在用哈夫曼算法构造哈夫曼树的过程中，若第i次合并时已找到权最小的结点x 和权次小的结点y，用T［x］.wt表示结点x的权值，已知T［x］.wt=m,T［y］.wt=n，则合并成新的二叉树后给新根结点的权值赋值的语句为__________。 21．在下列树中，结点H的祖先为__________。 30．分别写出下列二叉树的先根、中根、后根遍历序列。（6分） 第五章图真题 4.在一个图中，所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1 25.含有n个顶点和n-1条边的连通图G采用____________存储结构较省空间。 26.在图中，第一个顶点和最后一个顶点相同的路径称为____________。 32.下述题32图矩阵表示一个无向网，画出该无向网，并构造出其最小生成树。 3.由顶点V 1，V 2 ，V 3 构成的图的邻接矩阵为，则该图中顶点V 1 的出度为（） A.0 B.1 C.2 D.3 14.设无向图的邻接表如题14图所示，则该图的边数为（） 题14图 A.4 B.5 C.10 D.20 25.在一个具有n个顶点的无向图中，顶点的度最大可达_____。 26.有向图G的邻接矩阵为A，如果图中存在弧 i ，V j >，则A［i］［j］的值为____。 题32图 32.写出题32图所示的有向图的邻接矩阵及该图的所有拓扑排序序列。 11.有n个结点的无向图的边数最多为（） A.n+1 B.n(n-1)/2 C.n(n+1) D.2n(n+1) 12.设图的邻接矩阵为，则该图为（） A.有向图 B.无向图 C.强连通图 D.完全图 23.设有一稠密图G，则G采用__存储结构较省空间。设有一稀疏图G，则G采用__存储结构较省空间。 31.已知某图的邻接表存储结构如题31图所示： (1)画出该图。 (2)根据该邻接表从顶点A出发，分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。 10.一个具有n个顶点的无向连通图，它所包含的连通分量数为（） A.0 B.1 C.n D.不确定 11.下列说法中不正确的是（） A.无向图的极大连通子图称为连通分量 B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D.有向图的遍历不可采用广度优先搜索算法 23.在无向图G的邻接矩阵A中，若A[i][j]等于0，则A[j][i]等于________。 27.对含有n个结点e条边的无向连通图，利用prim算法生成最小生成树的时间复杂度为________。 31.对于题31图，试给出： 1）邻接矩阵；2）邻接表。 10.邻接矩阵为对称矩阵的图是( ) A.有向图 B.带权有向图 C.有向图或无向图 D.无向图 11.在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为( ) A.n-1 B.n C.n+1 D.n/2 22.一个具有4个顶点的无向完全图有_________条边。 23.一个有向图G中若有孤 33.已知无向图G的邻接表如题33图所示，请画出该无向图，并写出其按广度优先搜索时的访问序列。其中nil表示空。 10.有4个顶点的无向完全图的边数为( ) A.6 B.12 C.16 D.20 11.设图的邻接矩阵为，则该图为( ) A.有向图 B.无向图 C.强连通图 D.完全图 22.具有n个顶点的连通图至少需有__________条边。 23.在无向图G的邻接矩阵A中，若A［i］［j］等于1，则A［j］［i］等于__________。 32.已知无向图G的邻接矩阵如题32图所示。请画出该无向图，并写出按深度优先搜索时的访问序列。 12．在一个具有n个顶点的无向图中，每个顶点度的最大值为（）A．n B.n-1 C.n+1 D.2(n-1) 13．关于无向图的邻接矩阵的说法中正确的是（） A．矩阵中非全零元素的行数等于图中的顶点数 B.第i行上与第i列上非零元素总和等于顶点Vi的度数 C.矩阵中的非零元素个数等于图的边数 D.第i行上非零元素个数和第i列上非零元素个数一定相等 23．第一个顶点和最后一个顶点相同的路径称为回路或者环，除第一个顶点和最后一个顶点外，其余顶点都不重复的回路，称为_______。 24．一个具有10个顶点的完全无向图中有_______条边。 33．已知连通网的邻接矩阵A如33题图，试画出它所表示的连通网并画出该连通网的最小生成树。 11.有n个结点的有向完全图的弧数是（） A.n2 B.2n C.n(n-1) D.2n(n+1) 全国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《数据结构导论》串讲笔记
- 全国自学考试数据结构导论试卷与答案(4套)
- 4《数据结构导论》复习题
- 全国自学考试数据结构导论试题及答案(4套)
- 复习资料(数据结构导论)
- 数据结构导论年月试题
- 全国自学考试数据结构导论试题及答案(4套)
- 2010年5月衔接自考02142数据结构导论复习资料606
- 全国自学考试数据结构导论试题及答案(4套)
- 全国2017年4月自考《数据结构导论》试题02142
- 【历年自考真题6套】数据结构导论02142试题(2015年10月-2020年8月)
- 全国数据结构导论10月高等教育自学考试试题与答案
- 浙江省1月自学考试数据结构导论试题及答案解析
- 2010年5月衔接自考02142数据结构导论复习资料6435
- 数据结构导论选择
- 数据结构导论-自学考试-概念整理
- 全国自学考试数据结构导论试题及答案(4套)
- 数据结构导论2142复习资料
- 02142《数据结构导论》复习题.
- 数据结构导论复习题
- 自考数据结构导论复习资料